Propositions and logical form
A proposition is a sentence that is either true (T) or false (F). "Delhi is in India" is a proposition. "Close the door!" and "Is it raining?" are not, because they are neither true nor false.
A simple proposition has no connective; we name it with a letter: p, q, r. A compound proposition joins simple ones with connectives. The logical form is the pattern left when we replace each simple proposition with a letter: "If it rains, the match stops" has the form p → q.
Tips for symbolising: "but" and "although" are ∧; "unless" is usually ∨; "p only if q" is p → q; "p if q" is q → p; "neither p nor q" is ¬p ∧ ¬q.
Connectives and truth functions
| Name | Symbol | Read | True when… |
|---|---|---|---|
| Negation | ¬p | not p | p is false |
| Conjunction | p ∧ q | p and q | both are true |
| Disjunction | p ∨ q | p or q | at least one is true |
| Conditional | p → q | if p then q | except when p is T and q is F |
| Biconditional | p ↔ q | p if and only if q | p and q have the same value |
Each connective is a truth function: the value of the whole depends only on the values of its parts. In p → q, p is the antecedent and q is the consequent. The conditional is a promise; it is broken only when the antecedent is true and the consequent is false.
Useful equivalences: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p (contrapositive). De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q.
Building truth tables
With n letters there are 2ⁿ rows: 2 letters → 4 rows, 3 letters → 8 rows. Fill the first column with half T then half F, the next column alternating in smaller blocks, and so on. Then work out each connective column from the inside out, like brackets in arithmetic.
A formula that is true in every row is a tautology (e.g. p ∨ ¬p). One that is false in every row is a contradiction (e.g. p ∧ ¬p). Otherwise it is contingent. Two formulas are equivalent if their columns are identical.
Testing validity
An argument is valid if it is impossible for all premises to be true and the conclusion false. Validity is about form, not about whether the premises are actually true. A valid argument with true premises is sound.
Full truth-table method: make columns for every premise and the conclusion; look for a row where all premises are T and the conclusion is F. If such a row exists, the argument is invalid (that row is a counterexample); if not, it is valid.
Short method (reduction to absurdity): assume the conclusion is F and all premises are T, and work out the values. If this leads to a contradiction, the argument is valid; if you find consistent values, you have built a counterexample.
| Form | Pattern | Verdict |
|---|---|---|
| Modus ponens | p → q, p ∴ q | valid |
| Modus tollens | p → q, ¬q ∴ ¬p | valid |
| Hypothetical syllogism | p → q, q → r ∴ p → r | valid |
| Disjunctive syllogism | p ∨ q, ¬p ∴ q | valid |
| Affirming the consequent | p → q, q ∴ p | invalid |
| Denying the antecedent | p → q, ¬p ∴ ¬q | invalid |
Natural deduction and other proof methods
Truth tables grow fast (5 letters = 32 rows). Natural deduction proves a conclusion step by step using valid rules. Each line is a premise or follows from earlier lines by a rule.
- ∧-introduction: from p and q, write p ∧ q. ∧-elimination: from p ∧ q, write p (or q).
- ∨-introduction: from p, write p ∨ q.
- →-elimination (modus ponens): from p → q and p, write q.
- →-introduction (conditional proof): assume p, derive q, then write p → q.
- Reductio (¬-introduction): assume p, reach a contradiction, then write ¬p.
Example: premises p → q, q → r, p. 1) p → q (premise) 2) q → r (premise) 3) p (premise) 4) q (MP 1, 3) 5) r (MP 2, 4).
Other methods: an axiomatic system starts from a few axioms and one rule (modus ponens); semantic tableaux (truth trees) break formulas into branches and close a branch when it contains a contradiction.
Try it: the light-switch truth table
Use the free-play step: before each tap, predict whether p → q will be on or off, then switch p or q and check. Next, on paper, write the truth table for (p → q) ∧ p → q and show that every row is T: you have proved modus ponens is a tautology.
Key formulas and definitions
- ¬p is T when p is F
- p ∧ q is T only when both are T
- p ∨ q is F only when both are F
- p → q is F only when p is T and q is F; p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
- p ↔ q is T when p and q have the same value
- Rows in a truth table = 2ⁿ (n letters)
Worked examples
1. Symbolise: "If it is a holiday and the sun shines, we go to the beach." (h, s, b)
(h ∧ s) → b.
2. Find the value of (p ∨ q) → ¬p when p is T and q is F.
p ∨ q = T. ¬p = F. T → F = F. So the whole formula is F.
3. Show that p ∨ ¬p is a tautology.
p = T: T ∨ F = T. p = F: F ∨ T = T. True in both rows, so it is a tautology.
4. Is this valid? "If the phone is charged, it turns on. It turns on. So it is charged."
Form: p → q, q ∴ p (affirming the consequent). Row p = F, q = T: premises T, T; conclusion F. Invalid: it may turn on because it is plugged in.
5. Test with the short method: p → q, ¬q ∴ ¬p.
Assume conclusion F: ¬p = F, so p = T. Premise ¬q = T, so q = F. Then p → q = T → F = F, but it should be T. Contradiction, so the argument is valid (modus tollens).
6. Prove by natural deduction: from p ∧ q and q → r, derive r.
1) p ∧ q (premise) 2) q → r (premise) 3) q (∧-elim 1) 4) r (MP 2, 3).
Common mistakes
- Thinking p → q is false when p is false. A false antecedent makes the conditional true.
- Reading "p only if q" as q → p. It means p → q.
- Confusing valid with true. A valid argument can have a false conclusion if a premise is false.
- Forgetting rows: 3 letters need 8 rows, not 6.