The Foundations — Predicate Logic, Quantifiers & Direct Proofs
Predicates and propositional functions, compound expressions, ∀ / ∃ / ∃!, negating quantifiers, translating English into logic, and constructing direct proofs.
▶Lecture videos
Click any timestamp — here or inside the notes — to jump the video to that moment. Your position is remembered.
Logic & Proofs – Part I
Propositions vs predicates, propositional functions, and compound expressions.
00:11Lesson 1: the foundations of logic and proofs02:20Propositions: "2 + 1 = 5" is false04:42Predicates: the subject and the predicate06:08Notation: P(x)08:01Evaluating P(2) and other values10:31Predicates with more than one variable: P(x, y, z)13:17Compound expressions14:58Combining with ∧, ∨ and ¬19:37Next: quantifiersLogic & Proofs – Part II
Quantifiers, negating quantified statements, and translating English into logic.
00:02Section 2: quantifiers01:42The universal quantifier ∀03:46When ∀x P(x) is false: counterexamples06:47The existential quantifier ∃11:16The uniqueness quantifier ∃!14:39Examples with several quantifiers18:34Truth depends on the domain: x < 219:32Negating quantified expressions (De Morgan)24:44Translating English into logic28:11Example: speeding tickets31:36Translation with propositional functions and quantifiers39:45Next: direct proofsLogic & Proofs – Part III
Direct proofs: the two examples and the even/odd definitions.
00:02Section 3: introduction to proofs01:57Direct proofs: assume P, show Q02:57Example: the sum of consecutive integers is odd06:08Example: if n is odd, then n² is odd10:03Using 2k and 2k + 1 for even and odd numbers10:40Summary of Lesson 11From propositions to predicates
Recall: a proposition is a declarative statement that is either true or false, but not both.
- "Colombo is in Sri Lanka" → a proposition (true)
- "2 + 3 = 7" → a proposition (false)
- "x is greater than 5" → not a proposition. You can't tell if it's true until you know x.
Propositional logic can't handle statements with variables, and these are everywhere in maths and CS. So we use predicate logic.
In "x is greater than 5":
- x is the subject (also called the variable or argument).
- "is greater than 5" is the predicate: a property the subject can have.
Predicate logic has three features: variables, predicates and quantifiers.
2Propositional functions
- We write "x is greater than 3" as P(x), where P is the predicate "is greater than 3" and x is the variable.
- P(x) is called the value of the propositional function P at x.
- Once x gets a value, P(x) becomes a proposition with a truth value.
P(x): "x > 3"
- P(4): "4 > 3" → True
- P(2): "2 > 3" → False
The truth value of a predicate depends on the value of the variable.
- A propositional function becomes a proposition when every variable is replaced by a value from the domain, or bound by a quantifier.
- The domain is usually called U.
- Remark 2: the domain (the set of possible values of the arguments) is also called the universe of discourse.
Let P(x, y, z) denote "x + y = z", with U = the integers.
| Expression | Check | Value |
|---|---|---|
| P(2, −1, 5) | 2 + (−1) = 1 ≠ 5 | F |
| P(3, 4, 7) | 3 + 4 = 7 | T |
| P(x, 3, z) | x and z still unknown | Not a proposition |
3Compound expressions
Compound propositions combine propositions with logical operators. The same works with predicates.
| Symbol | Name | Read as | True when |
|---|---|---|---|
| ¬p | Negation | not p | p is false |
| p ∧ q | Conjunction | p and q | both are true |
| p ∨ q | Disjunction | p or q | at least one is true |
| p ⇒ q | Implication | if p then q | false only when p is T and q is F |
| p ⇔ q | Biconditional | p if and only if q | p and q have the same value |
- P(3) is T (since 3 > 0) and P(−1) is F (since −1 < 0).
| Expression | Working | Value |
|---|---|---|
| P(3) ∨ P(−1) | T ∨ F | True |
| P(3) ∧ P(−1) | T ∧ F | False |
| P(3) ⇒ P(−1) | T ⇒ F | False |
| P(−1) ⇒ P(3) | F ⇒ T | True |
4Quantifiers: ∀, ∃, ∃!
Universe of discourse (domain) = the set of everything we can sensibly assign to a variable. Does it make sense to set x = "blue" in "x > 0"? No.
P(x) = "The test will be on x the 23rd". U = {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}.
A predicate becomes a proposition either by assigning values or by quantifying it, i.e. saying it holds for all values or some values.
| Quantifier | Notation | Read as | True when |
|---|---|---|---|
| Universal | ∀x P(x) | "for all x" | P(x) is true for every x in U |
| Existential | ∃x P(x) | "there exists an x" | P(x) is true for at least one x in U |
| Uniqueness | ∃!x P(x) | "there exists a unique x" | P(x) is true for exactly one x in U |
| P(x) | U | Statement | Value | Why |
|---|---|---|---|---|
| x > 0 | integers | ∀x P(x) | F | −1 isn't > 0 |
| x > 0 | positive integers | ∀x P(x) | T | every positive integer > 0 |
| x is even | integers | ∀x P(x) | F | 3 is odd |
| x > 0 | integers | ∃x P(x) | T | e.g. x = 1 (also T for positive integers) |
| x < 0 | positive integers | ∃x P(x) | F | no positive integer is negative |
| x is even | integers | ∃x P(x) | T | e.g. x = 2 |
| x + 1 = 0 | integers | ∃!x P(x) | T | only x = −1 |
| x > 0 | integers | ∃!x P(x) | F | many values work |
Several variables
- Example 1.4.3: R(x, y) = "x + y > 10", U = integers. "For every x and every y, x + y > 10" is ∀x∀y R(x, y), shorthand ∀x, y R(x, y).
- Example 1.4.5: R(x, y) = "x² + y² = −5". "There exist x and y such that x² + y² = −5" is ∃x∃y R(x, y), shorthand ∃x, y R(x, y). It's false, since squares are never negative.
Truth depends on the predicate and the domain (Example 1.4.7)
| U | P(x) | ∃x P(x) | ∀x P(x) |
|---|---|---|---|
| positive integers | x < 2 | T (x = 1) | F |
| negative integers | x < 2 | T | T |
| {3, 4, 5} | x > 2 | T | T |
| {3, 4, 5} | x < 2 | F | F |
5Negating quantified expressions
"Every student in your class has a computer" is ∀x P(x), where P(x) = "x has a computer".
- Its negation: "It is not the case that every student has one."
- That means "there is a student who does not have one", which is ∃x ¬P(x).
¬∃x P(x) ≡ ∀x ¬P(x)
These are De Morgan's laws for quantifiers. Flip the quantifier and push the ¬ inside.
| Statement | Negation |
|---|---|
| ∀x (x² + 1 = 5) | ∃x (x² + 1 ≠ 5) |
| ∃x (x + 5 > 0) | ∀x (x + 5 ≤ 0) |
∀ and ∃ have higher precedence than all the logical operators:
- ∀x P(x) ∨ Q(x) means (∀x P(x)) ∨ Q(x).
- ∀x (P(x) ∨ Q(x)) means something different.
People often write ∀x P(x) ∨ Q(x) when they mean ∀x (P(x) ∨ Q(x)). Use brackets.
6Translating English into logic
English is ambiguous. Translating sentences into logic removes the ambiguity and lets us analyse truth values.
"The election is decided and the votes have been counted."
Let p = "the election is decided", q = "the votes have been counted". Then the sentence is p ∧ q.
p = "You drive over 100 miles per hour", q = "You get a speeding ticket".
| Sentence | Logic |
|---|---|
| You do not drive over 100 mph | ¬p |
| You drive over 100 mph, but you do not get a ticket | p ∧ ¬q ("but" = "and") |
| If you drive over 100 mph, then you will get a ticket | p ⇒ q |
| If you do not drive over 100 mph, then you will not get a ticket | ¬p ⇒ ¬q |
The 3-step method with quantifiers
- Rewrite the sentence so the quantifier is obvious ("For every student in this class…").
- Introduce a variable x.
- Introduce predicates and write the formula.
"Every student in this class has studied calculus."
- "For every student in this class, that student has studied calculus."
- "For every student x in this class, x has studied calculus."
- P(x) = "x has studied calculus", with U = students in the class.
Result: ∀x P(x)
Let Q(x) = "x has studied Java" and R(x) = "x has studied Python".
- "Some student in this class has studied Java" → ∃x Q(x)
- "Every student in this class has studied either Java or Python" → ∀x (Q(x) ∨ R(x))
| English | Logic |
|---|---|
| "Every / all A are B" | ∀x (A(x) ⇒ B(x)), or ∀x B(x) if U is already the A's |
| "Some A is B" | ∃x (A(x) ∧ B(x)), or ∃x B(x) |
| "No A is B" | ∀x (A(x) ⇒ ¬B(x)) ≡ ¬∃x (A(x) ∧ B(x)) |
| "but" | ∧ |
| "unless" | ∨ |
7Introduction to proofs — direct proof
| Term | Meaning |
|---|---|
| Proof | A logical argument showing a statement is true |
| Theorem | A mathematical statement proven to be true |
| Lemma | A statement proven true to help prove another statement |
| Methods | Direct proof, proof by contradiction, proof by induction (this lesson: direct) |
- Assume P (the hypothesis) is true.
- Use P to show that Q (the conclusion) must be true.
Useful definitions:
- Even: n = 2k
- Odd: n = 2k + 1, for some integer k
Assume a and b are consecutive integers. Then b = a + 1.
So a + b = a + (a + 1) = 2a + 1. Let k = a, so a + b = 2k + 1.
2k is even, and an even number plus 1 is odd. Therefore a + b is odd. ∎
Assume n is odd, so n = 2k + 1 for some integer k. Square both sides:
n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
This is one more than twice the integer (2k² + 2k), so n² is odd. ∎
- "Assume [hypothesis]."
- "By definition, [n = 2k + 1, etc.]."
- Do the algebra until the result has the form of the conclusion's definition.
- "Therefore [conclusion]. ∎"
The same pattern proves "if n is even then n² is even" (n = 2k ⇒ n² = 2(2k²)) and "odd × odd = odd" ((2a+1)(2b+1) = 2(2ab+a+b)+1).
Typical questions:
- Evaluate predicates at given values.
- Find the truth value of ∀ / ∃ / ∃! statements for a given domain (and see how changing the domain changes it).
- Negate quantified statements.
- Translate English ⇄ logic.
- Write a direct proof.
Always state the domain and show the definition you use (2k / 2k + 1).
8Assignment 1: worked answers
From ITE3822 Assignment 1_25S2_2.pdf. The course only accepts handwritten answers, so use these to check your work.
| Formula | Value | Why |
|---|---|---|
| (∀x)(∃y)(x + y = x) | True | Take y = 0 for every x |
| (∀x)(∃y)(x + y = 0) | True | Take y = −x, which is always an integer |
| (∀x)(∀y)(x < y ∨ y < x) | False | Counterexample x = y = 1: neither 1 < 1 nor 1 < 1 |
| (∃x)(∃y)(x² = y) | True | x = 2, y = 4 |
(a) Inverse. Let y = ln(4 − 2x). Then eʸ = 4 − 2x, so x = (4 − eʸ)/2.
f⁻¹(x) = (4 − eˣ)/2 = 2 − eˣ/2
(b) Domain and range.
- As x runs over (−∞, 2), the value 4 − 2x takes every positive value, so ln(4 − 2x) takes every real value.
- Domain of f⁻¹ = range of f = ℝ
- Range of f⁻¹ = domain of f = (−∞, 2)
(c) Sketch.
- y-intercept: f⁻¹(0) = (4 − 1)/2 = (0, 1.5)
- x-intercept: eˣ = 4, so (ln 4, 0) ≈ (1.386, 0)
- As x → −∞, f⁻¹(x) → 2, so there's a horizontal asymptote y = 2
- The curve is decreasing everywhere
| Function | Injective? | Surjective? | Verdict |
|---|---|---|---|
| f : ℝ → ℝ, f(x) = x² | No: f(1) = f(−1) = 1 | No: −1 has no preimage | Neither |
| g : ℝ → [0, ∞), g(x) = x² | No: g(2) = g(−2) | Yes: for y ≥ 0, take x = √y | Surjective only |
| k : ℝ → ℝ, k(x) = x³ − x | No: k(0) = k(1) = 0 | Yes: k is continuous, k → −∞ as x → −∞ and k → +∞ as x → +∞, so by the IVT it hits every real number | Surjective only |
Changing the codomain from ℝ to [0, ∞) turns the non-surjective f into the surjective g.
9Quick revision sheet
| Concept | Remember it as |
|---|---|
| Proposition | Declarative, T or F, not both |
| Predicate | A property of the subject; P(x) |
| Propositional function | Becomes a proposition when the variables get values or are quantified |
| Domain | Universe of discourse U |
| ∀x P(x) | True for every x (one counterexample makes it false) |
| ∃x P(x) | True for at least one x (one witness makes it true) |
| ∃!x P(x) | Exactly one x |
| Negation | ¬∀x P ≡ ∃x ¬P; ¬∃x P ≡ ∀x ¬P |
| Precedence | Quantifiers bind tighter than ∧ ∨ ⇒; use brackets |
| p ⇒ q | False only when T ⇒ F |
| English | "but" = ∧; 3 steps: rewrite → variable → predicate |
| Direct proof | Assume P, derive Q; even = 2k, odd = 2k + 1 |
?Self-check quiz
11 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.