Predicates & Quantifiers

Propositional logic cannot express "every student passed" or "some number is prime" in a useful way. Predicate logic adds variables, predicates and quantifiers.

#Predicates

A predicate P(x) is a statement with a variable; it becomes a proposition once x is given a value.

• P(x): "x > 3". Then P(5) is true and P(1) is false.
• Q(x, y): "x + y = 10". Q(4, 6) is true.

The set of values x may take is the domain (universe of discourse).

#Quantifiers

With domain = {1, 2, 3, 4}:

• ∀x (x > 0) — true.
• ∀x (x is even) — false (counterexample: 1).
• ∃x (x is even) — true (witness: 2).
• ∃x (x > 10) — false.

On a finite domain, ∀ is a big AND and ∃ is a big OR — exactly Python's all and any:

domain = range(1, 21)
print("∀x x² ≥ x:          ", all(x * x >= x for x in domain))
print("∃x x² = 49:         ", any(x * x == 49 for x in domain))
print("∀x ∃y y > x:        ", all(any(y > x for y in domain) for x in domain))   # false here: nothing in 1..20 exceeds 20
print("∃y ∀x y ≥ x:        ", any(all(y >= x for x in domain) for y in domain))
print("counterexample to 'all odd numbers are prime':", next(x for x in domain if x % 2 == 1 and x > 1 and any(x % d == 0 for d in range(2, x))))

∀x x² ≥ x:           True
∃x x² = 49:          True
∀x ∃y y > x:         False
∃y ∀x y ≥ x:         True
counterexample to 'all odd numbers are prime': 9

#Negating quantifiers (De Morgan for quantifiers)

"Not every student passed" = "some student did not pass". "There is no perfect algorithm" = "every algorithm is imperfect".

#Nested quantifiers

The order of different quantifiers matters:

• ∀x ∃y (y > x): "for every number there is a bigger one" — true for the integers.
• ∃y ∀x (y > x): "there is a number bigger than every number" — false for the integers.

Negate nested quantifiers by flipping each one and negating the inside: ¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y).

#Translating English

Let S(x): "x is a student", C(x): "x has a laptop", the domain being all people.

#Rules of inference for quantifiers

Classic argument: "All humans are mortal; Socrates is human; therefore Socrates is mortal" uses universal instantiation followed by modus ponens.