Predicate logic and quantifiers

Propositional logic cannot express a statement like every list has a length, or some user has administrator rights. Those statements talk about all or some members of a collection. Predicate logic, also called first-order logic, adds variables, predicates and quantifiers so that we can say such things precisely. It is the language of mathematical definitions, of database queries and of program specifications.

Predicates and domains

A predicate is a statement containing variables that becomes a proposition when the variables are given values. Write \(P(x)\) for x is prime. Then \(P(7)\) is true and \(P(8)\) is false. A predicate can have several variables: \(L(x, y)\) for x is less than y gives \(L(2, 5)\) true and \(L(5, 2)\) false. In programming terms, a predicate is a function that returns a Boolean.

Every variable ranges over a domain (also called the universe of discourse): the set of values it may take. The domain must be stated, because the truth of a quantified statement depends on it. The statement every number has a square root that is also a number is false if the domain is the integers (2 has no integer square root) and true if the domain is the non-negative real numbers.

The two quantifiers

The universal quantifier \(\forall\) means for all. The statement \(\forall x\, P(x)\) is true when \(P(x)\) is true for every \(x\) in the domain. The existential quantifier \(\exists\) means there exists. The statement \(\exists x\, P(x)\) is true when \(P(x)\) is true for at least one \(x\) in the domain. Over a finite domain \(\{a_1, \ldots, a_n\}\), the universal is a big conjunction and the existential is a big disjunction.

Python's built-in functions all and any implement exactly these two quantifiers over a finite collection. all returns True for an empty collection and any returns False, which matches the logic: a universal statement about nothing is vacuously true, and an existential statement about nothing is false.

nums = [4, 8, 15, 16, 23, 42]
is_even = lambda n: n % 2 == 0
print("for all n, n even?   ", all(is_even(n) for n in nums))
print("exists n, n even?    ", any(is_even(n) for n in nums))
print("for all n, n < 50?   ", all(n < 50 for n in nums))
print("exists n, n > 100?   ", any(n > 100 for n in nums))
print("empty domain: all ->", all(is_even(n) for n in []), " any ->", any(is_even(n) for n in []))

for all n, n even?    False
exists n, n even?     True
for all n, n < 50?    True
exists n, n > 100?    False
empty domain: all -> True  any -> False

The fourth and fifth rows make a point that matters in practice. A property that holds for mathematical integers can fail for the fixed-width integers inside a computer, as you saw with two's complement overflow in CMPUT-174 and as C programmers meet in CMPUT-201. Stating the domain is not pedantry; it is part of a correct specification.

Restricted quantifiers

We often want to quantify over part of a domain: every student in the class passed, or some prime is even. There are standard patterns. A universal restricted to elements with property \(S\) uses a conditional: \(\forall x\, (S(x) \to P(x))\). An existential restricted to \(S\) uses a conjunction: \(\exists x\, (S(x) \wedge P(x))\). Getting these the wrong way round is a classic error.

Negating quantified statements

Negation interacts with quantifiers through De Morgan's laws for quantifiers. It is not the case that every \(x\) has property \(P\) means some \(x\) lacks it. It is not the case that some \(x\) has property \(P\) means every \(x\) lacks it.

To negate a statement with several quantifiers, move the negation inward one quantifier at a time, flipping each \(\forall\) to \(\exists\) and each \(\exists\) to \(\forall\), and finally negate the predicate using the propositional laws from lesson 3. This mechanical procedure is how you find what a counterexample must look like.

Nested quantifiers

Statements with more than one quantifier are where predicate logic becomes powerful and where most errors happen. The order of quantifiers of different kinds matters. Consider the domain of people and \(L(x, y)\) meaning x loves y.

The difference between \(\forall x\, \exists y\) and \(\exists y\, \forall x\) is the difference between a choice that depends on \(x\) and a single choice that works for all \(x\). For every integer there is a larger integer, \(\forall x\, \exists y\, (y > x)\), is true: take \(y = x + 1\). There is an integer larger than every integer, \(\exists y\, \forall x\, (y > x)\), is false: no largest integer exists. Quantifiers of the same kind can be swapped freely: \(\forall x\, \forall y\) and \(\forall y\, \forall x\) mean the same.

D = range(5)                      # a small finite domain {0,...,4}
L = lambda x, y: (x + y) % 5 == 0  # "y is an additive inverse of x mod 5"

forall_exists = all(any(L(x, y) for y in D) for x in D)
exists_forall = any(all(L(x, y) for x in D) for y in D)
print("forall x exists y L(x,y):", forall_exists)
print("exists y forall x L(x,y):", exists_forall)
for x in D:
    print(f"  x = {x}: witness y = {[y for y in D if L(x, y)][0]}")

forall x exists y L(x,y): True
exists y forall x L(x,y): False
  x = 0: witness y = 0
  x = 1: witness y = 4
  x = 2: witness y = 3
  x = 3: witness y = 2
  x = 4: witness y = 1

Nested quantifiers are how mathematics defines its central concepts. In calculus, a sequence converges to \(L\) if for every tolerance \(\varepsilon > 0\) there exists an index \(N\) such that for every \(n \ge N\), \(|a_n - L| < \varepsilon\). In algorithm analysis, which you will study in CMPUT-204, a function \(f(n)\) is \(O(g(n))\) if there exist constants \(c > 0\) and \(n_0\) such that for all \(n \ge n_0\), \(f(n) \le c\, g(n)\). Reading such definitions requires exactly the skills of this lesson.

Translating English and specifications

Translating English into predicate logic forces you to resolve ambiguity. Words such as every, each, all and any usually signal \(\forall\); some, there is, at least one and a usually signal \(\exists\). But English is slippery: a dog is a mammal is universal (every dog), while a dog is barking is existential (some dog). Any can mean either: if any test fails, stop is existential, while any integer squared is non-negative is universal.

Predicate logic and databases

SQL is applied predicate logic. A query such as SELECT name FROM users WHERE age >= 18 AND country = 'CA' evaluates a predicate on each row. EXISTS in SQL is the existential quantifier. SQL has no direct FOR ALL, so universal queries are written with double negation: find the students for whom there does not exist a required course they have not taken. That is \(\neg \exists c\, (R(c) \wedge \neg T(s, c))\), which is equivalent to \(\forall c\, (R(c) \to T(s, c))\). You will write such queries in CMPUT-291.

required = {"CMPUT-174", "CMPUT-272", "MATH-125"}
taken = {
    "Ana":   {"CMPUT-174", "CMPUT-272", "MATH-125", "STAT-151"},
    "Ben":   {"CMPUT-174", "MATH-125"},
    "Chloe": {"CMPUT-174", "CMPUT-272", "MATH-125"},
}
for s, courses in taken.items():
    universal = all(c in courses for c in required)                 # for all c: R(c) -> T(s,c)
    double_neg = not any(c not in courses for c in required)        # not exists c: R(c) and not T(s,c)
    print(f"{s:6s} completed all required: {universal}  (double-negation form: {double_neg})")

Ana    completed all required: True  (double-negation form: True)
Ben    completed all required: False  (double-negation form: False)
Chloe  completed all required: True  (double-negation form: True)

Free and bound variables

In \(\forall x\, P(x, y)\) the variable \(x\) is bound by the quantifier, and \(y\) is free. A formula with free variables is a predicate, not a proposition; its truth depends on the free variables. This is the same idea as local and global variables in programming: inside the quantifier, \(x\) is a local name, and renaming it consistently, as in \(\forall z\, P(z, y)\), does not change the meaning. Using the same letter for two different bound variables in one formula is legal but confusing; good style gives each quantifier its own variable.