Topic 1 of 8
Step 21: Proofs and discrete maths
Logic and quantifiers
Step 21 · Proofs and discrete maths topics
Read and build mathematical statements with and, or, not and if-then, work out when an implication is true, and negate statements that say for all or there exists.
Statements and connectives
A statement is a sentence that is either true or false. Combine statements with and (∧), or (∨) and not (¬). In mathematics, or is inclusive: P ∨ Q is true when either part is true, or both.
| P | Q | P ∧ Q | P ∨ Q | ¬P |
|---|---|---|---|---|
| T | T | T | T | F |
| T | F | F | T | F |
| F | T | F | T | T |
| F | F | F | F | T |
Example: Truth values
Let P be '7 is prime' and Q be '7 is even'. Find P ∧ Q, P ∨ Q and ¬Q.
- P is true and Q is false.
- P ∧ Q needs both, P ∨ Q needs at least one, and ¬Q flips Q.
AnswerFalse, true and true
Implications
P → Q, 'if P then Q', is false only when P is true and Q is false. The promise 'if you finish the job, you get paid' is broken only if you finish and are not paid.
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Example: Related statements
Write the converse and the contrapositive of 'if n is divisible by 4, then n is even'.
- Converse: if n is even, then n is divisible by 4. That is false: think of 6.
- Contrapositive: if n is not even, then n is not divisible by 4. That is true.
AnswerThe contrapositive always agrees with the original; the converse need not
Quantifiers and negation
'For all x' (∀x) claims something about every x; 'there exists x' (∃x) claims at least one. To negate, swap the quantifier and negate what follows: ¬(∀x P(x)) is ∃x ¬P(x).
Example: Negating for all
Negate 'every prime is odd'.
- Swap 'every' for 'some', and negate 'is odd'.
AnswerSome prime is even, and 2 shows the negation is true
Example: Order matters
For real numbers, compare '∀x ∃y: y > x' with '∃y ∀x: y > x'.
- The first says every number has a bigger one: true.
- The second says one number beats every number, itself included: false.
AnswerThe first is true and the second is false
Example: A nested negation
Negate '∀ε > 0 ∃δ > 0 such that |x| < δ implies |f(x)| < ε'.
- Swap each quantifier, then negate the end.
- The negation of 'P implies Q' is 'P and not Q'.
Answer∃ε > 0 ∀δ > 0, some x has |x| < δ but |f(x)| ≥ ε
Try it yourself
Work each one on paper first, then open the answer to check.
Is P ∨ Q true when P is false and Q is true?
Show answer
Yes
When is P → Q false?
Show answer
Only when P is true and Q is false
Write the contrapositive of 'if x > 3 then x² > 9'.
Show answer
If x² ≤ 9 then x ≤ 3
Negate 'all swans are white'.
Show answer
Some swan is not white
Negate '∃x: x² = −1'.
Show answer
∀x: x² ≠ −1
Is 'if 2 + 2 equals 5, then the moon is made of cheese' true?
Show answer
Yes: its hypothesis is false