Truth Tables

A **truth table** lists **every possible combination** of truth values of the variables in an expression and shows the value of the whole expression in each row. **How many rows?** Each variable can be T or F, so every new variable doubles the number of rows: $$\text{rows} = 2^n \quad (n = \text{number of variables})$$ So 2 variables need $2^2 = 4$ rows and 3 variables need $2^3 = 8$ rows. **Building a table in 4 steps:** 1. Count the variables and write $2^n$ empty rows. 2. Fill the variable columns in a fixed order: the first column is half T, then half F; each next column switches twice as often; the last column alternates T, F, T, F. 3. Add a **helper column** for every part of the expression, innermost part first (a NOT on a single variable, then the brackets). 4. Combine the helper columns into the final column. **Example:** $P \land \neg Q$ | $P$ | $Q$ | $\neg Q$ | $P \land \neg Q$ | |:---:|:---:|:---:|:---:| | T | T | F | F | | T | F | T | **T** | | F | T | F | F | | F | F | T | F | The final column tells you everything: this expression is true in exactly one row, when $P$ is true and $Q$ is false. **Reading the final column:** - All T: the expression is a **tautology** (always true). - All F: it is a **contradiction** (always false). - Two expressions with the **same final column in every row** are **logically equivalent**.

A Table for Two Variables

Build the truth table for $P \lor \neg Q$.

Count the rows: There are 2 variables, $P$ and $Q$, so we need $2^2 = 4$ rows = 4 rows

Fill the variable columns: $P$: T, T, F, F (half T, half F). $Q$: T, F, T, F (alternating) = All 4 combinations appear once

Add the helper column $\neg Q$: Flip every value of $Q$: T, F, T, F becomes F, T, F, T = $\neg Q$: F, T, F, T

Combine with OR: Row by row: T OR F = T, T OR T = T, F OR F = F, F OR T = T = $P \lor \neg Q$: T, T, F, T

Answer: The final column is T, T, F, T. The expression is false only in row 3, where $P$ is false and $Q$ is true.

Setting Up Three Variables

Set up the variable columns of a truth table for $P$, $Q$ and $R$.

Count the rows: 3 variables, so $2^3 = 2 \times 2 \times 2 = 8$ rows = 8 rows

Fill column $P$: Half of 8 is 4: four T, then four F = $P$: T, T, T, T, F, F, F, F

Fill column $Q$: Switch twice as often, in blocks of 2 = $Q$: T, T, F, F, T, T, F, F

Fill column $R$: The last column alternates in blocks of 1 = $R$: T, F, T, F, T, F, T, F

Answer: The 8 rows are TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF. Every combination appears exactly once and none is missing.

A Three-Variable Expression

Build the truth table for $(P \land Q) \lor \neg R$. In how many rows is it true?

Set up 8 rows: Use the order from the previous example: $P$ in blocks of 4, $Q$ in blocks of 2, $R$ alternating = 8 rows

Helper column $P \land Q$: AND is true only when $P$ and $Q$ are both true: rows 1 and 2 = $P \land Q$: T, T, F, F, F, F, F, F

Helper column $\neg R$: Flip $R$: T, F, T, F, T, F, T, F becomes F, T, F, T, F, T, F, T = $\neg R$: F, T, F, T, F, T, F, T

Combine with OR: A row is true if at least one helper column is T: rows 1, 2, 4, 6, 8 = Final: T, T, F, T, F, T, F, T

Count the true rows: Count the T values in the final column = 5 rows

Answer: The expression is true in 5 of the 8 rows and false in rows 3, 5 and 7.

Tautology, Contradiction or Neither?

Classify $P \lor \neg P$, $P \land \neg P$ and $(P \land Q) \lor \neg P$.

Find $\neg P$: With one variable there are $2^1 = 2$ rows. $P$: T, F, so $\neg P$: F, T = $\neg P$: F, T

Check $P \lor \neg P$: T OR F = T and F OR T = T = All T: tautology

Check $P \land \neg P$: T AND F = F and F AND T = F = All F: contradiction

Check $(P \land Q) \lor \neg P$: 4 rows. $P \land Q$: T, F, F, F. $\neg P$: F, F, T, T. OR: T, F, T, T = Mixed: neither

Answer: $P \lor \neg P$ is a tautology, $P \land \neg P$ is a contradiction, and $(P \land Q) \lor \neg P$ is neither, because it is false in row 2.

Checking Equivalence (De Morgan)

Are $\neg(P \land Q)$ and $\neg P \lor \neg Q$ equivalent? What about $\neg(P \land Q)$ and $\neg P \land \neg Q$?

Final column of $\neg(P \land Q)$: $P \land Q$: T, F, F, F. Flip it = F, T, T, T

Final column of $\neg P \lor \neg Q$: $\neg P$: F, F, T, T. $\neg Q$: F, T, F, T. OR row by row = F, T, T, T

Compare every row: F = F, T = T, T = T, T = T = Same in all 4 rows: equivalent

Final column of $\neg P \land \neg Q$: $\neg P$: F, F, T, T AND $\neg Q$: F, T, F, T = F, F, F, T: differs in rows 2 and 3

Answer: $\neg(P \land Q) \equiv \neg P \lor \neg Q$ (one of De Morgan's laws). But $\neg(P \land Q)$ and $\neg P \land \neg Q$ are not equivalent: one row that differs is enough.

A truth table is the most reliable way to check a logical statement, because it leaves no case out: - **Programming**: before shipping a condition like (member OR coupon) AND NOT blocked, testers check every combination of inputs - **Electronics**: engineers use truth tables to design circuits and to replace a complicated circuit with a simpler, cheaper one that does the same job - **Security and alarms**: an alarm with 4 sensors has $2^4 = 16$ possible states, and every one of them must behave correctly - **Arguments and debates**: a truth table shows whether two sentences really say the same thing or only sound alike - **Puzzles and games**: logic puzzles are solved by ruling out rows that cannot be true You already know how AND, OR and NOT work on their own. Truth tables let you combine them into any expression and still be sure of the answer.

Mistake: Writing too few rows, for example 6 rows for 3 variables

Why: The number of rows is not $2 \times n$. Each variable doubles the number of combinations, so 3 variables give $2 \times 2 \times 2 = 8$ rows.

Correct: Always use $2^n$ rows: 4 for 2 variables, 8 for 3 variables, 16 for 4 variables.

Mistake: Filling the variable columns in a random order

Why: Without a system it is easy to write the same combination twice and miss another one. The table then gives a wrong verdict.

Correct: Use the fixed pattern: first column in blocks of half the rows, each next column in blocks half as long, last column alternating T, F.

Mistake: Treating $\neg P \land Q$ as if it were $\neg(P \land Q)$

Why: Without brackets, NOT applies only to the variable right after it. The bracketed version flips the result of the whole AND.

Correct: Make a helper column for exactly what NOT touches: $\neg P$ alone, or $P \land Q$ first and then its negation.

Mistake: Calling two expressions equivalent after checking only a few rows

Why: Two expressions can agree on several rows and still differ in one. $\neg(P \land Q)$ and $\neg P \land \neg Q$ agree in rows 1 and 4 but not in rows 2 and 3.

Correct: Compare the final columns in every single row. Equivalent means identical in all $2^n$ rows.

Alarm Systems

Security engineers list every state of the sensors to make sure the alarm reacts correctly in each one.

An alarm with 3 door sensors has $2^3 = 8$ states, from all doors closed to all doors open.

Testing Software

Programmers test a condition with every combination of inputs, which is exactly a truth table.

A login rule (correct password AND NOT locked) needs $2^2 = 4$ test cases to be fully checked.

Simplifying Circuits

If two circuits have the same truth table, engineers can use the one with fewer or cheaper parts.

De Morgan's laws let a designer swap a NOT-AND for an OR of two NOTs without changing what the circuit does.

A truth table lists every combination of truth values and the value of the expression in each row

With $n$ variables the table has $2^n$ rows: 4 for 2 variables, 8 for 3 variables

Fill the variable columns in a fixed order: blocks of half the rows first, last column alternating T, F

Use helper columns for each part of the expression, innermost part first

All T in the final column means a tautology, all F means a contradiction

Two expressions are equivalent when their final columns match in every row

Q: Why does every new variable double the rows?

A: Each existing row can be continued with the new variable being T or being F. So every row splits into two: 2 rows become 4, 4 become 8, and so on, which gives $2^n$.

Q: Does the order of the rows matter?

A: Any order is correct as long as every combination appears exactly once. The standard order (starting with all T) makes it easy to check and to compare tables. Some books start with F instead; the rows are the same, only listed the other way round. The interactive tables in this lesson use the standard order.

Q: What is an expression called if it is neither a tautology nor a contradiction?

A: It is called a **contingency**: its value depends on the inputs. Most everyday expressions, like $P \land Q$, are contingencies.

Q: Do I always need helper columns?

A: They are not required, but they prevent most mistakes. With practice you can combine small steps in your head, but for 3 variables or brackets inside brackets, helper columns are the safest way.

Exit Presentation

Truth Tables

1 / 14

Logic & Sets / Boolean Logic

Truth Tables

Learn to build a truth table for any compound expression step by step and use it to find tautologies, contradictions and equivalent expressions.

Intermediate25 min

Use arrow keys or spacebar to navigate