What is a proposition?
A proposition (also called a statement) is a sentence that is either true (T) or false (F), not both. This is its truth value.
- "5 > 2" is a true proposition.
- "7 is even" is a false proposition.
- "Close the door!" and "Is it raining?" are not propositions.
- "x + 2 = 5" is not yet a proposition. Its truth depends on x. Such a sentence with a variable is a predicate (or open sentence), written P(x).
Joining propositions: NOT, AND, OR, ⇒, ⇔
| p | q | not p (¬p) | p ∧ q | p ∨ q | p ⇒ q | p ⇔ 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 |
- Negation ¬p: the opposite value.
- Conjunction p ∧ q (and): true only if both are true.
- Disjunction p ∨ q (or): true if at least one is true.
- Implication p ⇒ q (if p then q): false only when p is T and q is F.
- Equivalence p ⇔ q (if and only if): true when both have the same value.
De Morgan's laws: not (p and q) = (not p) or (not q); not (p or q) = (not p) and (not q).
Converse, inverse and contrapositive
Start with p ⇒ q: "If a shape is a square, then it is a rectangle."
- Converse q ⇒ p: "If it is a rectangle, it is a square." False.
- Inverse ¬p ⇒ ¬q: "If it is not a square, it is not a rectangle." False.
- Contrapositive ¬q ⇒ ¬p: "If it is not a rectangle, it is not a square." True, like the original.
A statement and its contrapositive are always equivalent. So to prove p ⇒ q you may prove ¬q ⇒ ¬p instead (proof by contrapositive).
Proof by contradiction: assume the opposite of what you want, and reach something impossible. Then the opposite was false, so your statement is true.
Necessary and sufficient conditions, and sets
If p ⇒ q is true:
- p is a sufficient condition for q (p is enough to be sure of q).
- q is a necessary condition for p (without q, p cannot happen).
With sets: let P = things for which p is true, Q = things for which q is true. Then p ⇒ q means P ⊆ Q (P is inside Q). If both p ⇒ q and q ⇒ p, then P = Q and p is necessary and sufficient for q (p ⇔ q).
Example: "x = 2" ⇒ "x² = 4". x = 2 is sufficient for x² = 4, but not necessary (x = −2 also works).
Quantifiers: for all and there exists
- Universal ∀ ("for all"): ∀x, x² ≥ 0. True for every real x.
- Existential ∃ ("there exists"): ∃x, x + 3 = 5. True, x = 2.
To negate, swap the quantifier and negate the inside:
- not (∀x, P(x)) = ∃x, not P(x). "Not all birds fly" = "some bird does not fly".
- not (∃x, P(x)) = ∀x, not P(x).
One counterexample is enough to prove a "for all" statement false.
Try it
Write "If it rains, the ground is wet" on paper. Write its converse, inverse and contrapositive. Which two always agree? Then check with the free-play lamp in the 3D (choose p ⇒ q).
Key formulas and definitions
- p ⇒ q is false only when p = T and q = F
- p ⇒ q ≡ ¬q ⇒ ¬p (contrapositive)
- p ⇒ q ≡ ¬p ∨ q
- ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
- p ⇒ q: p sufficient for q, q necessary for p; P ⊆ Q
- ¬(∀x P(x)) ≡ ∃x ¬P(x); ¬(∃x P(x)) ≡ ∀x ¬P(x)
Worked examples
1. Which are propositions? (a) 12 is divisible by 4 (b) Shut the window (c) x > 5 (d) 3 + 3 = 7
(a) true proposition, (d) false proposition. (b) is an order and (c) is a predicate; neither is a proposition until x is fixed.
2. p: 'it is a weekday', q: 'school is open'. p is T, q is F. Find p ∧ q, p ∨ q, p ⇒ q.
p ∧ q = F (q is false). p ∨ q = T (p is true). p ⇒ q = F (true leads to false).
3. Write the converse and contrapositive of: 'If n is divisible by 6, then n is even.' Which are true?
Converse: if n is even, n is divisible by 6. False (n = 4). Contrapositive: if n is not even, n is not divisible by 6. True.
4. Is 'x > 5' necessary, sufficient, both or neither for 'x > 3'?
x > 5 ⇒ x > 3, so x > 5 is sufficient. But x = 4 shows x > 3 does not give x > 5, so it is not necessary.
5. Negate: 'Every student in the class has a phone.'
'There is at least one student in the class who does not have a phone.' (∀ becomes ∃, and the inside is negated.)
6. Prove by contradiction that √2 is not a fraction a/b in lowest terms.
Assume √2 = a/b in lowest terms. Then a² = 2b², so a is even, a = 2k. Then 4k² = 2b², b² = 2k², so b is even too. Both even contradicts 'lowest terms'. So the assumption is false.
Common mistakes
- Thinking the converse is true just because the original is true.
- Thinking p ⇒ q is false when p is false. A promise with a false 'if' part is never broken, so it is true.
- Negating 'all are' as 'all are not'. The correct negation is 'some are not'.
- Swapping necessary and sufficient. In p ⇒ q, the 'if' part p is sufficient; the 'then' part q is necessary.