Two Boolean expressions are equivalent when they give the same output for every combination of inputs. A full truth table is the only evidence that settles it, because agreement on a few rows proves nothing.
This lesson follows building a truth table from a nested Boolean expression in Boolean logic and representation.
What is the method?
Put both expressions in one table and compare their final columns.
- List every input combination.
- Add helper columns for each expression.
- Compare the two final columns row by row.
- If every row matches, the claim is true. If any row differs, the claim is false, and that row is your evidence.
Worked example: a true claim
Claim: NOT (A AND B) is equivalent to NOT A OR NOT B.
| 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 |
Compare the fourth and seventh columns. Both read 1, 1, 1, 0, so they match in all four rows and the claim is true. In words, both expressions are true unless A and B are both on.
The mistake: a false claim that looks true
A common slip is to stop after two or three rows match. Test this claim: NOT (A OR B) is equivalent to NOT A OR NOT B. This looks like the law above, with AND changed to OR.
| A | B | A OR B | NOT (A OR B) | NOT A | NOT B | NOT A OR NOT B | Match? |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | Yes |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | No |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | No |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | Yes |
Rows 1 and 4 match, so a quick test at A = 0, B = 0 would wrongly say the claim is true. Row 2 breaks it: with A = 0 and B = 1, the left side is 0 and the right side is 1. The claim is false.
The correct version is NOT (A OR B) = NOT A AND NOT B. In row 2, NOT A AND NOT B is 1 AND 0 = 0, which matches the left side.
How do I write the conclusion?
State the result and the evidence together. For a false claim, give the row: “Not equivalent. When A = 0 and B = 1, the first expression is 0 and the second is 1.”
For a true claim, say that all rows match and give the number of rows: “Equivalent. All 4 rows give the same output.” Do not write “it works for the cases I tried”.
Check yourself
Is A AND (A OR B) equivalent to A? Build the table and state your conclusion.
Answer
| A | B | A OR B | A AND (A OR B) | A |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
The fourth and fifth columns match in all 4 rows, so the two are equivalent. In words: if A is off, the AND is off whatever the bracket is. If A is on, the bracket A OR B is on, so the AND is on.
What to study next
Equivalence is used to simplify conditions, and conditions start as words. Next, read converting a written requirement into an unambiguous logical condition. Use the Boolean expression and truth-table explorer to check any pair.
If you want a teacher to go through your tables, see online one-to-one Computer Science tuition.