← all problems

Equivalent Boolean Expressions 🌶️

Two boolean expressions are equivalent when they produce the exact same result for every possible combination of their inputs — in other words, when their truth tables match on every single row. It doesn't matter how different the two expressions look written out; what matters is whether they always agree.

This is worth taking seriously: "usually agree" is not the same as equivalent. Two expressions that give the same answer on 3 out of 4 rows of a truth table are NOT equivalent — a single disagreeing row is enough to prove they're different functions, even if that row represents a rare case.

1. Fill in both columns. Look closely once you're done: what do you notice about the two columns?

Fill in T or F for each row.

2. Based on the table you just filled in for A and !!A, are they equivalent? Answer yes or no.

3. Fill in both columns for this pair.

Fill in T or F for each row.

4. Based on the table you just filled in, are A && B and B && A equivalent? Answer yes or no.

5. a && b and a agree with each other on 3 of the 4 rows of a truth table — they only disagree when a is true and b is false. Are a && b and a equivalent?

6. Which of these is equivalent to a || a?

7. Now try a 3-variable pair. Fill in both columns.

Fill in T or F for each row.

8. You just confirmed A && (B || C) and (A && B) || (A && C) are equivalent — the same idea as multiplication distributing over addition in arithmetic (a (b + c) = ab + a*c). In your own words: what does it mean, in general, for two boolean expressions to be equivalent, and what's the one reliable way to prove it?

Your score for your class is recorded when you click Submit all — checking individual questions doesn't save it. You can submit again to improve your score; your best one counts.