Two Boolean expressions are equivalent when they give the same output for every possible input. To compare them, build a column for each over all the input cases and look for a row where the columns differ.
This lesson uses the truth table method and the order of evaluation. It is part of the Boolean logic module.
How do you compare using cases?
- List all input cases. Two inputs give 4 cases.
- Evaluate expression 1 for each case.
- Evaluate expression 2 for each case.
- Compare row by row. If every row matches, they are equivalent. If any row differs, they are not.
A single mismatch is a counterexample. It settles the question at once, so you can stop.
Worked example
Are NOT (A AND B) and (NOT A) OR (NOT B) equivalent?
| A | B | A AND B | NOT (A AND B) | NOT A | NOT B | (NOT A) OR (NOT B) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
The two result columns are 1, 1, 1, 0 and 1, 1, 1, 0. All four rows match, so the expressions are equivalent.
Now compare NOT (A OR B) with (NOT A) OR (NOT B). For A = 0, B = 1: NOT (0 OR 1) = NOT 1 = 0, but (NOT 0) OR (NOT 1) = 1 OR 0 = 1.
The values differ, so the expressions are not equivalent. The counterexample is A = 0, B = 1.
The mistake to watch for
A common mistake is to test one case and conclude they are equal.
Mistaken reasoning: “For A = 0, B = 0, NOT (A OR B) = 1 and (NOT A) OR (NOT B) = 1. They match, so they are equivalent.”
One matching row proves nothing. The same two expressions differ at A = 0, B = 1. The correct approach is to check all four cases, or to stop as soon as you find a row that differs.
Check yourself
1. Are A AND (A OR B) and A equivalent?
Show answer
If A = 0: 0 AND (0 OR B) = 0, which equals A. If A = 1: 1 AND (1 OR B) = 1 AND 1 = 1, which equals A. Both cases match, so they are equivalent.
2. Are NOT (A AND B) and (NOT A) AND (NOT B) equivalent? Give a counterexample if not.
Show answer
Not equivalent. For A = 1, B = 0: NOT (1 AND 0) = NOT 0 = 1, but (NOT 1) AND (NOT 0) = 0 AND 1 = 0. The counterexample is A = 1, B = 0.
3. Are A OR ((NOT A) AND B) and A OR B equivalent?
Show answer
If A = 1: the left side is 1 OR (0 AND B) = 1, and the right side is 1 OR B = 1. If A = 0: the left side is 0 OR (1 AND B) = B, and the right side is 0 OR B = B. All cases match, so they are equivalent.
Where this leads next
Next, look at how everyday sentences can hide more than one logical reading in distinguishing logical AND from ordinary language. Then try the Boolean logic practice set. The Boolean and number-representation lab can confirm your case tables.
If you can compare expressions in class but are unsure how much working earns the mark, our teachers can go through it in online one-to-one Computer Science tuition.