Moving from Propositional Logic to Predicate Logic
This week we extend our logical framework to handle statements about properties, relations, and quantities.
Argument 1:
• If n is an even number, then n² is also even.
• 6 is an even number.
• Therefore, 6² is even.
Argument 2:
• Everyone in the room is a suspect.
• Poirot is in the room.
• Therefore, Poirot is a suspect.
These are clearly valid arguments!
But we cannot express them properly using only propositional logic (p, q, ∧, ∨, →, ¬, ↔).
We need to talk about properties, variables, and quantification!
We can't express "for any number x"
We can't express "x is even" as a general property
We can't express "all", "some", "every", "there exists"
• "This apple is red" – True or False
• "The light is red" – True or False
• "My shoes are red" – True or False
They all have the form: "[something] is red"
The thing that "is red" changes – this is our variable!
P(x) = "x is red" where x is a thing
Now: P(this apple), P(the light), P(my shoes) are all propositions
A predicate is a statement with one or more variables, such that:
Predicate + Values = Proposition
Example: Let P(x) denote "x is greater than 5"
where x is a natural number.
• P(x) by itself is NOT a proposition (it's neither true nor false)
• P(7) is a proposition: ✓ TRUE
• P(3) is a proposition: ✗ FALSE
P(x) = "x is red"
• P(this apple) – True or False
• This expresses a property of one thing
R(x, y) = "x has the colour y"
• R(this apple, red) – True or False
• R(my shoes, blue) – True or False
• This expresses a relationship between two things
⚠️ Order Matters!
R(this apple, red) means "this apple has the colour red" ✓
R(red, this apple) means "red has the colour this apple" ✗ (nonsense!)
The universe or domain of a variable is the set of all possible values that the variable can take.
Case 1: x and y are natural numbers
• S(3, 5) is TRUE
• S(5, 3) is FALSE
• S(-1, 1) is undefined (−1 is not a natural number!)
Case 2: x and y are integers
• S(3, 5) is TRUE
• S(5, 3) is FALSE
• S(-1, 1) is TRUE (now it makes sense!)
Always specify your universe clearly!
Statement 1: "All my mum's children like football"
Let P(x) = "x likes football" where x is one of my mum's children
Using conjunction:
P(Ceel) ∧ P(Soph) ∧ P(Jan) ∧ P(Clare)
This works for 4 children, but what about larger or infinite sets?
Statement 2: "Every integer n satisfies n² ≥ n"
Let S(n) = "n² ≥ n" where n is an integer
We'd need:
... ∧ S(-2) ∧ S(-1) ∧ S(0) ∧ S(1) ∧ S(2) ∧ ... ∧ S(3765) ∧ ...
Impossible to write! We need infinite conjunction!
Let P(x) be a predicate where x takes values in universe U.
∀xP(x)
means "For all values of x in U, P(x) is true"
Let P(n) = "n² ≥ n" where n is an integer
∀nP(n) means "Every integer n satisfies n² ≥ n"
This is much cleaner than an infinite conjunction!
P(x) = "x < x + 1" where x is a real number
∀xP(x) is TRUE
Every real number is less than itself plus one.
Q(x) = "x < x²" where x is a real number
∀xQ(x) is FALSE
Why? Because Q(0) is false (0 is not less than 0²)
We only need one counterexample to disprove ∀xP(x)!
To PROVE ∀xP(x) is TRUE: Must show P(x) is true for EVERY x in the universe
To DISPROVE ∀xP(x): Only need to find ONE x where P(x) is false
Let P(x) be a predicate where x takes values in universe U.
∃xP(x)
means "There exists at least one x in U such that P(x) is true"
Let P(x) = "x's phone is not on silent"
where x is a student in this class
∃xP(x) means "At least one student has their phone not on silent"
P(x) = "x < x + 1" where x is a real number
∃xP(x) is TRUE
We can find at least one real number that is less than itself plus one.
(In fact, P(0) is true: 0 < 0 + 1)
Q(x) = "x < x²" where x is a real number
∃xQ(x) is TRUE
We can find at least one real number less than its square.
(For example, Q(2) is true: 2 < 4)
To PROVE ∃xP(x) is TRUE: Only need to find ONE x where P(x) is true
To DISPROVE ∃xP(x): Must show P(x) is false for EVERY x in the universe
If P(x) is true for every x in a non-empty universe U, then P(x) is true for at least one x in U.
∀xP(x) → ∃xP(x)
(This implication is true)
⚠️ But the converse is NOT generally true!
∃xP(x) does NOT imply ∀xP(x)
Example:
Let P(x) = "x is even" where x is a natural number
• ∃xP(x) is TRUE (because 2 is even)
• ∀xP(x) is FALSE (because 3 is not even)
ALL elements satisfy P
AT LEAST ONE satisfies P
∀xP(x) is always TRUE (vacuously true)
∃xP(x) is always FALSE
Let U = {all unicorns in reality}
Let P(x) = "x has golden wings"
∀xP(x): "All unicorns have golden wings" is TRUE!
Why? There are no unicorns to check, so the statement is vacuously true.
∃xP(x): "There exists a unicorn with golden wings" is FALSE
Why? There are no unicorns, so we can't find one with this property.
This is why mathematicians say "All unicorns are pink" is technically a true statement!
Let P(x) = "x² = x" where x is a real number.
Is ∀xP(x) true or false?
Answer: FALSE. Counterexample: P(2) is false because 2² = 4 ≠ 2
Let Q(x) = "x² ≥ 0" where x is a real number.
Which is true: ∀xQ(x) or ∃xQ(x) or both?
Answer: BOTH are true. Every real number squared is ≥ 0, so ∀ is true, and therefore ∃ is also true.
Let R(x) = "x is prime and x is even" where x is a natural number.
Is ∃xR(x) true or false?
Answer: TRUE. R(2) is true because 2 is both prime and even.
¬(∀xP(x)) ≡ ∃x(¬P(x))
¬(∃xP(x)) ≡ ∀x(¬P(x))
"It is NOT the case that P(x) holds for all x"
is the same as
"There EXISTS some x for which P(x) is false"
"There does NOT EXIST an x such that P(x) holds"
is the same as
"For ALL x, P(x) is false"
Original: ∀x(x² > x) where x is a real number
"Every real number is less than its square"
Negation: ¬(∀x(x² > x)) ≡ ∃x(¬(x² > x)) ≡ ∃x(x² ≤ x)
"There exists a real number that is NOT less than its square"
Is the negation true? YES! Take x = 0: 0² = 0 ≤ 0
Therefore, the original statement ∀x(x² > x) is FALSE
Let F(x) = "x speaks French", G(x) = "x speaks German"
where x is a delegate at a conference
Original: ∀x(F(x) ∨ G(x))
"Everyone speaks French or German"
Negation: ∃x¬(F(x) ∨ G(x)) ≡ ∃x(¬F(x) ∧ ¬G(x))
"There is someone who speaks neither French nor German"
Step 1: ¬(∀x∃yP(x, y))
Step 2: ∃x¬(∃yP(x, y))
Changed ∀ to ∃, moved negation in
Step 3: ∃x∀y¬P(x, y)
Changed ∃ to ∀, moved negation in
Result: ¬(∀x∃yP(x, y)) ≡ ∃x∀y(¬P(x, y))
⚠️ Common Mistake: Don't forget to negate the predicate itself!
¬(∀xP(x)) ≠ ∃xP(x) ✗ WRONG!
¬(∀xP(x)) ≡ ∃x(¬P(x)) ✓ CORRECT!
The scope of a quantifier is the part of the expression to which the quantifier applies.
∀x(F(x) ∧ G(x))
The scope of ∀x is the entire expression (F(x) ∧ G(x))
⚠️ Be Careful!
∀xF(x) ∧ G(x) means (∀xF(x)) ∧ G(x)
The quantifier only applies to F(x), not to G(x)!
This is a predicate, not a proposition (x in G(x) is free)
Bound variable: A variable that is controlled by a quantifier
Free variable: A variable that is NOT controlled by a quantifier
∀x(F(x) ∧ G(x))
• The variable x appears in F(x) and G(x)
• x is bound by ∀x
• This is a proposition (no free variables)
∀xF(x) ∧ G(x)
• The first x (in F(x)) is bound by ∀x
• The second x (in G(x)) is free (not in scope of ∀x)
• This is a predicate (has a free variable)
A statement is a proposition only if ALL variables are bound.
If there are any free variables, it's a predicate.
"For every real number x ≥ 0, there is a real number y such that y² = x"
Breaking it down:
Complete translation:
∀x((x ≥ 0) → ∃y(y² = x))
This says: "Every non-negative number has a square root"
The order of DIFFERENT quantifiers matters!
∀x∃yP(x, y) is NOT the same as ∃y∀xP(x, y)
Let B(p, s) = "person p has booked seat s"
Statement 1: ∀s∃pB(p, s)
"For every seat, there exists a person who booked it"
Meaning: Every seat has been booked (possibly by different people)
Statement 2: ∃p∀sB(p, s)
"There exists a person who booked every seat"
Meaning: One person booked the entire theatre!
These mean completely different things!
Seat 1
→ booked by Alice
Seat 2
→ booked by Bob
Seat 3
→ booked by Alice
Each seat must have someone, but can be different people
Alice
↓
Seat 1, Seat 2, Seat 3
One person must have booked ALL seats
The order of LIKE quantifiers doesn't matter:
∀x∀yP(x, y) ≡ ∀y∀xP(x, y)
∃x∃yP(x, y) ≡ ∃y∃xP(x, y)
∀p∀s(¬B(p, s)) ≡ ∀s∀p(¬B(p, s))
"No person has booked any seat" ≡ "No seat has been booked by anyone"
These say the same thing!
∃s∃pB(p, s) ≡ ∃p∃sB(p, s)
"At least one seat has been booked by someone" ≡ "At least one person has booked some seat"
These say the same thing!
With ∀ (for all): Use →
"All students passed" → ∀x(Student(x) → Passed(x))
Think: "IF student, THEN passed"
With ∃ (exists): Use ∧
"Some student passed" → ∃x(Student(x) ∧ Passed(x))
Think: "BOTH student AND passed"
∀x(Student(x) ∧ Passed(x)) would mean "Everything in the universe is both a student AND passed"
This would mean chairs, tables, and numbers are all students who passed! ✗
∃x(Student(x) → Passed(x)) would mean "There exists something such that if it's a student, it passed"
This is true for any non-student thing (like a chair)! ✗
Let P(x) = "x has done MA1000"
Universe = {students in discrete math}
"Every student in discrete math has done MA1000"
∀xP(x)
Simple! Universe already contains only discrete math students.
Let P(x) = "x has done MA1000"
Let D(x) = "x is in discrete math"
Universe = {all people on Earth}
"Every student in discrete math has done MA1000"
∀x(D(x) → P(x))
Need implication to restrict to discrete math students!
Negate the statement: ∀x(x > 0 → x² > 0)
where x is a real number
Answer: ∃x(x > 0 ∧ ¬(x² > 0)) ≡ ∃x(x > 0 ∧ x² ≤ 0)
Let L(x, y) = "x loves y" where x and y are people.
Translate: "Everyone loves someone"
Answer: ∀x∃yL(x, y)
Let L(x, y) = "x loves y" where x and y are people.
Translate: "Someone is loved by everyone"
Answer: ∃y∀xL(x, y)
Do the statements in Q2 and Q3 mean the same thing?
Answer: NO! Q2: each person loves someone (possibly different). Q3: one person is loved by all.
Step 1: Variables
• s (seats), p and q (people)
Step 2: Universe
• s ranges over all seats
• p, q range over all people
Step 3: Predicate
• B(p, s) = "person p has booked seat s"
Step 4: Thinking Process
"No seat" → ∀s (for every seat...)
"has been booked by more than one person" → if two people booked it, they must be the same person
Step 5: Translation
∀s∀p∀q((B(p, s) ∧ B(q, s)) → (p = q))
Step 6: Read back
"For all seats, for all people p and q, if both p and q booked the seat, then p equals q"
Step 1: Variables
• x, y (real numbers)
Step 2: Universe
• x and y are real numbers
Step 3: Thinking Process
"For every positive real number x" → ∀x(x > 0 → ...)
"there is a smaller positive real number y" → ∃y((y > 0) ∧ (y < x))
Step 4: Translation
∀x((x > 0) → ∃y((y > 0) ∧ (y < x)))
Step 5: Is this true?
YES! For any positive x, we can take y = x/2
This proves there is no smallest positive real number.
∃!xP(x)
means "There exists a unique x such that P(x)"
Method 1:
∃x(P(x) ∧ ∀y(P(y) → (y = x)))
"There exists an x such that P(x), and for all y, if P(y), then y equals x"
Method 2:
∃xP(x) ∧ ∀x∀y((P(x) ∧ P(y)) → (x = y))
"There exists an x such that P(x), and for all x and y, if both satisfy P, then they're equal"
Both say: Something with property P exists, and there's only one such thing.
Step 1: Predicates
• R(x, y) = "x + y = 0"
Step 2: Without uniqueness
∀x∃yR(x, y)
"For every x, there exists a y such that x + y = 0"
This is true (y = −x), but doesn't say y is unique!
Step 3: With uniqueness (Method 1)
∀x∃y(R(x, y) ∧ ∀z(R(x, z) → (y = z)))
"For every x, there exists y such that x + y = 0, and for all z, if x + z = 0, then z = y"
Step 4: Is this true?
YES! For any x, only y = −x satisfies x + y = 0
SQL concept: "Find all students who passed every course"
∀c(Enrolled(s, c) → Passed(s, c))
This translates to nested queries in SQL!
Specification: "For all valid inputs, there exists a valid output"
∀input(Valid(input) → ∃output(Correct(input, output)))
Used in formal verification of software correctness!
Requirement: "Every request must have at least one authentication token"
∀request∃token(HasAuth(request, token))
Ensures security constraints are met!
✗ ∀x(Student(x) ∧ Passed(x)) for "all students passed"
✓ ∀x(Student(x) → Passed(x))
✗ ¬(∀xP(x)) = ∃xP(x)
✓ ¬(∀xP(x)) = ∃x(¬P(x))
∀x∃yLoves(x, y) ≠ ∃y∀xLoves(x, y)
"Everyone loves someone" ≠ "Someone is loved by everyone"
∀xP(x) ∧ Q(x) means (∀xP(x)) ∧ Q(x)
The second x is FREE!
| Original Statement | Negation |
|---|---|
| ∀xP(x) | ∃x(¬P(x)) |
| ∃xP(x) | ∀x(¬P(x)) |
| ∀x(P(x) → Q(x)) | ∃x(P(x) ∧ ¬Q(x)) |
| ∃x(P(x) ∧ Q(x)) | ∀x(P(x) → ¬Q(x)) |
| ∀x∀yP(x, y) | ∃x∃y(¬P(x, y)) |
| ∀x∃yP(x, y) | ∃x∀y(¬P(x, y)) |
| ∃x∀yP(x, y) | ∀x∃y(¬P(x, y)) |
Memorize the first two rows - the rest follow from them!
| English Pattern | Formal Logic | Notes |
|---|---|---|
| All S are P | ∀x(S(x) → P(x)) | Use implication with ∀ |
| Some S are P | ∃x(S(x) ∧ P(x)) | Use conjunction with ∃ |
| No S are P | ∀x(S(x) → ¬P(x)) | Equivalently: ¬∃x(S(x) ∧ P(x)) |
| Not all S are P | ∃x(S(x) ∧ ¬P(x)) | Negation of "all S are P" |
| Everyone loves someone | ∀x∃yL(x, y) | ∀ then ∃ |
| Someone is loved by everyone | ∃y∀xL(x, y) | ∃ then ∀ - different! |
| There is exactly one x such that P(x) | ∃x(P(x) ∧ ∀y(P(y) → y = x)) | Uniqueness |
"Every computer science student has taken at least one programming course"
Given:
• CS(x) = "x is a computer science student"
• T(x, c) = "student x has taken course c"
• P(c) = "course c is a programming course"
• Universe for x: all students
• Universe for c: all courses
Step 1: "Every computer science student" → ∀x(CS(x) → ...)
Step 2: "has taken at least one programming course" → ∃c(P(c) ∧ T(x, c))
Step 3: Combine:
∀x(CS(x) → ∃c(P(c) ∧ T(x, c)))
∀x(P(x) → ∃y(Q(y) ∧ R(x, y)))
"For all x, if P(x) then there exists y such that Q(y) and R(x,y)"
Step 1: ¬(∀x(P(x) → ∃y(Q(y) ∧ R(x, y))))
Step 2: ∃x¬(P(x) → ∃y(Q(y) ∧ R(x, y)))
Changed ∀ to ∃
Step 3: ∃x(P(x) ∧ ¬(∃y(Q(y) ∧ R(x, y))))
Negated implication: ¬(p → q) ≡ p ∧ ¬q
Step 4: ∃x(P(x) ∧ ∀y¬(Q(y) ∧ R(x, y)))
Changed ∃ to ∀
Step 5: ∃x(P(x) ∧ ∀y(¬Q(y) ∨ ¬R(x, y)))
De Morgan's law on final predicate
Final Answer: ∃x(P(x) ∧ ∀y(¬Q(y) ∨ ¬R(x, y)))
Statements with variables
P(x), R(x,y)
Domains for variables
Must specify clearly!
"For all"
Use → for restrictions
"There exists"
Use ∧ for requirements
• Start with simple statements
• Build to complex multi-quantifier statements
• Always read your translation back in English to verify
• Practice negating statements systematically
• Work left to right, one quantifier at a time
• Memorize: ¬∀ becomes ∃¬, and ¬∃ becomes ∀¬
• Create your own examples showing why order matters
• Visualize with concrete scenarios (like the theatre example)