# Truth Tables and Logical Equivalence

Computer Science I · Basic Digital Design · https://tryals.app/learn/computer-science-i/truth-tables-and-logical-equivalence

## Truth Tables and Equivalence

A **truth table** lists the output of a boolean function for every possible input combination. For $n$ inputs, the table has $2^n$ rows. It provides a complete specification of a function.

Two expressions have **logical equivalence** if and only if their truth tables match row for row. This gives a foolproof test for equality no matter how different the expressions look.

| Inputs ($n$) | Rows ($2^n$) |
| --- | --- |
| 2 | 4 |
| 3 | 8 |

Each row where output is 1 is a **minterm**. OR-ing minterms together creates a canonical sum-of-products expression, proving any function can be built from gates.

## Boolean Laws and Pitfalls

Truth tables verify the laws of **boolean algebra**:

| Law | Equations | Description |
| --- | --- | --- |
| **Identity** | $A + 0 = A$, $A \cdot 1 = A$ | Neutral elements |
| **Complement** | $A + \overline{A} = 1$, $A \cdot \overline{A} = 0$ | Inverse logic |
| **De Morgan** | $\overline{A \cdot B} = \overline{A} + \overline{B}$ | Negation flips operator |
| **De Morgan** | $\overline{A + B} = \overline{A} \cdot \overline{B}$ | Negation flips operator |

> **Common pitfall:** Applying **De Morgan's law** incorrectly by writing $\overline{A \cdot B} = \overline{A} \cdot \overline{B}$ (wrong) instead of $\overline{A} + \overline{B}$ (right). Negation always flips the operator.

## Practice questions

4 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. A synthesis tool replaces a designer's carefully written expression with a completely different gate arrangement. Why is that permitted?

A. Because logical equivalence licenses it, so it optimises area and delay
B. Because gate arrangements have no effect on the resulting circuit
C. Because the tool is required to use only NAND gates
D. Because the tool assumes the designer's expression is incorrect

**Answer:** A. Because logical equivalence licenses it, so it optimises area and delay

**Why:** Equivalence is the licence: same truth table, same behaviour, so everything else is negotiable. That is why designers describe *what* the logic does and let synthesis choose the gates, and why verification after optimisation is stated as an equivalence check rather than a test.

Page: https://tryals.app/practice/computer-science-i/truth-tables-and-logical-equivalence/a-synthesis-tool-replaces-a-designers-carefully-written-expression

### 2. Two boolean expressions with identical truth tables are interchangeable in a circuit, so the choice between them does not matter.

**Answer:** False

**Why:** False. They are logically equivalent, so either computes the right answer, but they differ in gate count, propagation delay and power. That is the entire point of Karnaugh maps and Quine–McCluskey: find the equivalent expression that is *cheapest*, since correctness is already guaranteed by the truth table.

Page: https://tryals.app/practice/computer-science-i/truth-tables-and-logical-equivalence/two-boolean-expressions-with-identical-truth-tables-are

### 3. Order the steps of the foolproof procedure for deciding whether two boolean expressions are equivalent.

**Answer:**

1. List every combination of the input variables, giving 2 to the power n rows
2. Evaluate the first expression on each row and record its output column
3. Evaluate the second expression on the same rows and record its output column
4. Compare the two output columns row by row
5. Declare the expressions equivalent only if the columns agree on every single row

**Why:** The input rows must be fixed first, or the two columns are not comparable. Agreement on every row is required: a single differing row is enough to prove non-equivalence, whereas agreement on some rows proves nothing. This exhaustive check is why the truth table is called the complete specification of a function.

Page: https://tryals.app/practice/computer-science-i/truth-tables-and-logical-equivalence/order-the-steps-of-the-foolproof-procedure-for-deciding-whether-two

### 4. Consider the three-input function (A AND B) OR (NOT C). Evaluate it on each row below and select every row where the output is 1.

A. A = 1, B = 1, C = 0
B. A = 1, B = 0, C = 1
C. A = 0, B = 1, C = 1
D. A = 1, B = 1, C = 1
E. A = 0, B = 0, C = 0

**Answer:** A. A = 1, B = 1, C = 0; D. A = 1, B = 1, C = 1; E. A = 0, B = 0, C = 0

**Why:** Rows 1 and 3 have C = 0, so NOT C is 1 and the OR is satisfied regardless of A and B. Of the rows with C = 1, only the last has both A and B equal to 1. The trap is row 4, where a 1 appears among the inputs but neither half of the expression is satisfied, an OR needs a whole term to be true, not merely a true input somewhere.

Page: https://tryals.app/practice/computer-science-i/truth-tables-and-logical-equivalence/consider-the-three-input-function-a-and-b-or-not-c-evaluate-it