Propositions, truth tables and Karnaugh maps
Master propositions, truth tables and Karnaugh maps in Year 11 VCE Specialist Mathematics. A proposition is a statement that is either true or false, and the connectives \(\lnot,\ \land,\ \lor,\ \to,\ \leftrightarrow\) combine them into compound statements you test with truth tables. It sits in the Algebra, number and structure area of study of the VCE Mathematics Study Design (VCAA), within the Logic and algorithms topic of Unit 1.
You will learn to build truth tables over \(2^{n}\) rows, identify tautologies and contradictions, test logical equivalence including De Morgan's laws and the contrapositive, and simplify Boolean functions with Karnaugh maps.
Theory
A proposition is a statement that is either true or false. In Year 11 Specialist Mathematics you combine propositions with the connectives and \((\land)\), or \((\lor)\), not \((\lnot)\), implies \((\to)\) and if and only if \((\leftrightarrow)\), then test them with truth tables. This page builds truth tables, checks tautologies, contradictions and logical equivalence, and simplifies Boolean functions with Karnaugh maps.
A proposition is a statement with a definite truth value — either true (T) or false (F). "\(7\) is prime" is a proposition; a question or a request is not.
Simple propositions \(p, q, r\) are joined by connectives to make compound propositions:
- Negation \(\lnot p\) (“not \(p\)”) reverses the truth value.
- Conjunction \(p\land q\) (“\(p\) and \(q\)”) is true only when both are true.
- Disjunction \(p\lor q\) (“\(p\) or \(q\)”) is true when at least one is true.
- Implication \(p\to q\) (“if \(p\) then \(q\)”) is false only when \(p\) is true and \(q\) is false.
- Biconditional \(p\leftrightarrow q\) (“\(p\) if and only if \(q\)”) is true when both sides have the same truth value.
A truth table lists every combination of truth values for the simple propositions — \(2^n\) rows for \(n\) propositions — and works out the value of the compound proposition in each row.
A proposition true in every row is a tautology; one false in every row is a contradiction. Two propositions are logically equivalent (\(\equiv\)) when their truth-table columns are identical. A Karnaugh map is a grid of the same truth values, arranged so that adjacent cells differ in one variable, which makes simplifying a Boolean function easy.
| \(p\) | \(q\) | \(\lnot p\) | \(p\land q\) | \(p\lor q\) | \(p\to q\) | \(p\leftrightarrow q\) |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
| \(q\) | \(\lnot q\) | |
|---|---|---|
| \(p\) | 1 | 0 |
| \(\lnot p\) | 1 | 0 |
For \(n\) simple propositions a truth table has
The connectives are defined row by row; the implication is the one to watch:
De Morgan's laws push a negation through a bracket, swapping \(\land\) and \(\lor\):
The contrapositive is logically equivalent to the original implication, and an implication can be rewritten as a disjunction:
Building a truth table
- List every assignment. Write \(2^{n}\) rows covering all T/F combinations of the simple propositions (\(4\) rows for two, \(8\) for three).
- Add a column for each part. Work outwards from the innermost brackets, filling one connective column at a time.
- Read the final column. All T means a tautology; all F a contradiction; a mix is neither.
- Compare columns to test logical equivalence: two propositions are equivalent exactly when their columns agree in every row.
Using a Karnaugh map
- Draw the grid so adjacent cells differ in one variable (for two variables, rows \(p,\lnot p\) and columns \(q,\lnot q\)).
- Enter a \(1\) in every cell where the function is true, \(0\) elsewhere.
- Group the \(1\)s into the largest blocks of \(1,2,4,\dots\) cells; a whole row or column drops the variable that changes across it.
- Read off the simplified expression from the surviving variables.
A full \(q\) column of \(1\)s (the value does not depend on \(p\)) simplifies straight to \(q\):
| \(q\) | \(\lnot q\) | |
|---|---|---|
| \(p\) | 1 | 0 |
| \(\lnot p\) | 1 | 0 |
There are two propositions, so \(2^{2}=4\) rows. An implication fails only when a true premise gives a false conclusion:
| \(T\to T\) | \(=\) | \(T\) |
| \(T\to F\) | \(=\) | \(F \quad(\text{the only false row})\) |
| \(F\to T\) | \(=\) | \(T\) |
| \(F\to F\) | \(=\) | \(T\) |
| \(p\) | \(q\) | \(p\to q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The column for \(p\to q\) is \(T,F,T,T\); it is false only when \(p\) is true and \(q\) is false.
With one proposition there are \(2^{1}=2\) rows. Evaluate each compound proposition:
| \(p\lor\lnot p\) | \(=\) | \(T\lor F = T \quad(p=T)\) |
| \(=\) | \(F\lor T = T \quad(p=F)\) | |
| \(p\land\lnot p\) | \(=\) | \(T\land F = F \quad(p=T)\) |
| \(=\) | \(F\land T = F \quad(p=F)\) |
| \(p\) | \(\lnot p\) | \(p\lor\lnot p\) | \(p\land\lnot p\) |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
\(p\lor\lnot p\) is always true (a tautology); \(p\land\lnot p\) is always false (a contradiction).
Build the column for each side over all four rows and compare:
| \(\lnot(p\land q)\) | \(:\) | \(F,\,T,\,T,\,T\) |
| \(\lnot p\lor\lnot q\) | \(:\) | \(F,\,T,\,T,\,T \quad(\text{identical})\) |
| \(\lnot p\land\lnot q\) | \(:\) | \(F,\,F,\,F,\,T \quad(\text{differs})\) |
| \(p\) | \(q\) | \(p\land q\) | \(\lnot(p\land q)\) | \(\lnot p\lor\lnot q\) |
|---|---|---|---|---|
| T | T | T | F | F |
| T | F | F | T | T |
| F | T | F | T | T |
| F | F | F | T | T |
The columns for \(\lnot(p\land q)\) and \(\lnot p\lor\lnot q\) match in every row, so \(\lnot(p\land q)\equiv\lnot p\lor\lnot q\).
| \(q\) | \(\lnot q\) | |
|---|---|---|
| \(p\) | 1 | 0 |
| \(\lnot p\) | 1 | 0 |
Read the \(2\)-variable map. The \(1\)s fill the whole \(q\) column and the value does not change with \(p\), so \(p\) drops out:
| \(q=T\) | \(:\) | \(1,\,1 \quad(\text{true for both } p)\) |
| \(q=F\) | \(:\) | \(0,\,0 \quad(\text{false for both } p)\) |
| \(\Rightarrow\) | \(\text{function} = q\) |
For three variables the columns run \(qr=00,01,11,10\). The two \(1\)s where \(p=1,\ q=1\) form one block in which \(r\) changes, so \(r\) drops out:
| \(qr=00\) | \(qr=01\) | \(qr=11\) | \(qr=10\) | |
|---|---|---|---|---|
| \(p=0\) | 0 | 0 | 0 | 0 |
| \(p=1\) | 0 | 0 | 1 | 1 |
The surviving variables are \(p\) and \(q\):
| \(\Rightarrow\) | \(\text{function} = p\land q\) |
The \(2\)-variable map simplifies to \(q\); the \(3\)-variable map simplifies to \(p\land q\).
Common pitfalls
Frequently asked questions
What is a proposition?
A proposition is a statement that is either true or false — for example "\(7\) is a prime number". Questions, requests and expressions such as \(x+3\) are not propositions because they have no definite truth value.
How many rows does a truth table have?
For \(n\) simple propositions the table has \(2^{n}\) rows: \(4\) rows for two propositions and \(8\) rows for three, covering every combination of true and false.
When is the implication \(p\to q\) false?
Only when \(p\) is true and \(q\) is false. In the other three rows \(p\to q\) is true, so its column is \(T,F,T,T\).
What is the difference between a tautology and a contradiction?
A tautology is true in every row of its truth table (for example \(p\lor\lnot p\)); a contradiction is false in every row (for example \(p\land\lnot p\)).
What are De Morgan's laws?
They rewrite the negation of a bracket by swapping the connective: \(\lnot(p\land q)\equiv\lnot p\lor\lnot q\) and \(\lnot(p\lor q)\equiv\lnot p\land\lnot q\).
How does a Karnaugh map simplify a Boolean function?
Enter a \(1\) where the function is true, then group the \(1\)s into the largest blocks. Any variable that changes across a block drops out; the surviving variables give the simplified expression, such as a full \(q\) column simplifying to \(q\).