Predicates and quantifiers

A predicate is a statement with a variable: P(x) = "x is even". It is not true or false by itself, but it becomes a proposition once x is given: P(4) is true, P(7) is false. The values x may take form the domain.

Quantifiers

The domain matters: ∀x (x² ≥ x) is true for the whole numbers, but false for the real numbers (x = ½ gives ¼ < ½).

domain = [1, 2, 3, 4, 5, 6]

def is_even(x):
    return x % 2 == 0

print("for all x, x is even:", all(is_even(x) for x in domain))
print("there is an even x:", any(is_even(x) for x in domain))

# A counterexample to "for all x, x² > 5"
counterexamples = [x for x in domain if not x * x > 5]
print("counterexamples to x² > 5:", counterexamples)

# Order of quantifiers: x + y = 7
for_all_exists = all(any(x + y == 7 for y in domain) for x in domain)
exists_for_all = any(all(x + y == 7 for x in domain) for y in domain)
print("∀x ∃y x + y = 7:", for_all_exists)
print("∃y ∀x x + y = 7:", exists_for_all)

Negating quantifiers

"Not every student passed" means "some student did not pass":

¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)

So to show that a "for all" statement is false, one counterexample is enough. To show a "there exists" statement is false, you must check (or prove) that no x works.

Nested quantifiers

Quantifiers can be stacked, and their order matters. Over the integers:

• ∀x ∃y (x + y = 0): "every number has a negative". True: for each x, take y = −x.
• ∃y ∀x (x + y = 0): "one number is the negative of every number". False.

In the first, y may depend on x; in the second, one y must work for all x at once. The second half of the example checks both on a small domain.

From English to logic

With the domain "students" and C(x, y) = "x passed course y":

Mark lesson complete