1.1Propositions, connectives and truth tables
The idea
A proposition is a statement that is either true or false. Connectives (¬ not, ∧ and, ∨ or, → implies, ↔ iff, ⊕ xor) build bigger propositions, and a truth table lists the value for every combination of the inputs.
Think of it like this: A row of light switches: each switch is a variable, and the table says whether the lamp is on for each of the 2ⁿ ways to set them.
Why it exists
Every logic question, however fancy, can be settled by a truth table. Knowing how to build one fast, and how → really behaves, wins the easy marks.
How it works
- List the variables; there are 2ⁿ rows (4 for two variables, 8 for three).
- Fill the columns for the sub-formulas from the inside out.
- p → q is false only on the row p = T, q = F; every other row is true.
- Respect precedence: ¬, then ∧, then ∨, then →, then ↔; → groups to the right.
Worked example: p → (q → p)
If p is false, the whole thing is true (false hypothesis). If p is true, then q → p is true, so again true. All rows are true: a tautology. Type it into the lab to see the column of T.
Now play with it
- →Load "p → q" and note that the only false row is p = T, q = F.
- →Type
p -> (q -> p)and confirm it is a tautology.
| p | q | value |
|---|---|---|
| F | F | T |
| F | T | T |
| T | F | F |
| T | T | T |
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q | p ⊕ q | p NAND q |
|---|---|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T | F | F |
| T | F | F | F | T | F | F | T | T |
| F | T | T | F | T | T | F | T | T |
| F | F | T | F | F | T | T | F | T |
The only row where p → q is false is T, F. A false hypothesis makes the implication true (vacuously). p ⊕ q is the negation of p ↔ q.
Check yourself
For which values of p and q is p → q false?
Exam notes (the dense version)
A proposition is a statement that is true or false. Connectives: ¬, ∧, ∨, →, ↔, ⊕. p → q is false only when p is true and q is false; it is true whenever p is false. p ↔ q is true when both agree. A formula with n variables has 2ⁿ rows. Precedence (high to low): ¬, ∧, ∨, →, ↔; → is right associative.
Previous year questions: Propositional & First-Order Logic (25)
PYQs are grouped by topic, so this is the full set for Propositional & First-Order Logic; try the ones that match this subtopic. Open all 25 on the topic page.