Predicates and Quantifiers

Why we need more than propositions

Here is a famous argument, more than two thousand years old:

All humans are mortal. Socrates is a human. Therefore, Socrates is mortal.

Everybody agrees it is correct. Now try to write it in the propositional logic of weeks 2 and 3. The best we can do is three unrelated letters: $p$ = “all humans are mortal”, $q$ = “Socrates is a human”, $r$ = “Socrates is mortal”. The argument becomes $p, q \;\therefore\; r$, and nothing in $p$ and $q$ forces $r$. Propositional logic cannot see inside a sentence. It does not know that “all humans” talks about Socrates.

The same problem shows up in software every day:

• “Every request is authenticated.”
• “Some server in the cluster is overloaded.”
• “No user has two active sessions.”

With 10,000 users we would need 10,000 separate propositions, one per user. What we really want is to write a statement once, with a variable, and say “for all of them” or “for some of them”. That is exactly what predicate logic adds, with two new ingredients: predicates and quantifiers.

Predicates

Take $P(x)$: “$x > 3$”.

In plain words: a predicate is a yes/no question with a blank. “Is ___ greater than 3?” has no answer until you fill in the blank.

If you program, you already know predicates. A predicate is simply a function that returns a boolean:

def P(x):                  # P(x): "x > 3"
    return x > 3

def is_valid_ipv4(s):      # V(s): "s is a valid IPv4 address"
    parts = s.split(".")
    return len(parts) == 4 and all(p.isdigit() and 0 <= int(p) <= 255 for p in parts)

P(4)                       # True
is_valid_ipv4("256.1.1.1") # False

Predicates with several variables

A predicate can have more than one blank. The number of variables is its arity.

• $Q(x, y)$: “$x = y + 3$”. Then $Q(5, 2)$ is true and $Q(1, 2)$ is false.
• $L(x, y)$: “$x$ loves $y$”. $L(\text{Ada}, \text{Mathematics})$ is, we hope, true.
• $T(s, c)$: “student $s$ has taken course $c$”, a predicate a university database answers thousands of times a day.

Building with connectives

Everything from weeks 2 and 3 still works: once the blanks are filled, the results are propositions and we can combine them with $\neg, \land, \lor, \to, \leftrightarrow$. Let $P(x)$ be “$x > 0$”.

The domain

Before we can say “for all $x$” we must answer: all $x$ from where? That set is the domain (also called the universe of discourse), written $U$ or $D$.

The domain is not a detail. It decides the answer:

The universal quantifier ∀

The symbol $\forall$ is an upside-down A, for All. It reads “for all”, “for every”, “for each” or “for any”.

That $x = 3$ has a name.

The asymmetry is the key to this whole topic:

• To show $\forall x\, P(x)$ is false: find one counterexample. Easy.
• To show $\forall x\, P(x)$ is true: you must cover every element. With a finite domain, check them all; with an infinite domain you need an argument, a proof (week 7). A thousand examples that work prove nothing about the thousand-and-first.

∀ is a loop, and a big AND

How would a computer evaluate $\forall x\, P(x)$ over a finite domain? It loops:

def for_all(domain, P):
    for x in domain:
        if not P(x):
            return False      # counterexample found: stop immediately
    return True               # survived every element

Python has this built in: all(P(x) for x in domain). It also stops at the first false value. When the domain is finite, say $U = \{1, 2, 3\}$, the loop is just a long conjunction:

The existential quantifier ∃

The symbol $\exists$ is a backwards E, for Exists. It reads “there exists”, “there is”, “for some” or “at least one”.

The asymmetry is now reversed: proving $\exists$ true needs one example; proving $\exists$ false needs you to rule out every element.

def exists(domain, P):
    for x in domain:
        if P(x):
            return True       # witness found: stop immediately
    return False              # nobody worked

That is any(P(x) for x in domain), and over a finite domain it is a long disjunction:

The two quantifiers side by side

Reading quantified formulas correctly

Precedence

$\forall$ and $\exists$ bind more tightly than every connective. So

When the quantifier should cover more, use parentheses. In this course we always write the parentheses, and you should too.

Bound and free variables

In $\exists x\,(x + y = 1)$ the variable $x$ is bound by the quantifier, while $y$ is free: nothing tells us its value. A formula with a free variable is still a predicate (a question with a blank), not a proposition. It becomes a proposition when every variable is either bound or given a value: $\exists x\,(x + 2 = 1)$ is true over the integers ($x = -1$).

The scope of a quantifier is the part of the formula it covers, usually the parenthesis right after it. A bound variable can be renamed without changing the meaning, exactly like a loop variable in code: $\forall x\, P(x)$ and $\forall y\, P(y)$ say the same thing.

Restricted domains, and the golden rule

Mathematics constantly quantifies over part of a domain: “every negative number”, “some prime number”, “every student in this class”. There is a short notation:

What do these mean in plain predicate logic? Read them slowly.

• “Every negative $x$ has $x^2 > 0$” means: for every $x$, if $x$ is negative, then $x^2 > 0$.
• “Some positive $z$ has $z^2 = 2$” means: there is a $z$ that is positive and has $z^2 = 2$.

This gives the single most useful rule of the week.

The rule is not a convention. The other two combinations say something different, and the next section shows exactly why.

Seeing it with real data

Our domain is eight people. Some are students in this class ($S$), some have taken Java ($J$). Pick a statement with the buttons, then click the S and J values to change the data and watch what happens. Pay attention to the two statements marked ✗.

What the lab shows, in words:

• $\forall x\,(S(x) \to J(x))$, “every student has taken Java”. For people who are not students, $S(x)$ is false, so $S(x) \to J(x)$ is automatically true (week 2: a promise with a false hypothesis is never broken). The implication filters: only the students are tested. This is the correct translation.
• $\forall x\,(S(x) \land J(x))$ says “everyone is a student in this class and has taken Java”. Kerem, Mert and Lina are not students, so it is false even when every student took Java. Wrong translation: it accidentally claims that the whole domain consists of students.
• $\exists x\,(S(x) \land J(x))$, “some student has taken Java”, needs one person who is both. Correct translation.
• $\exists x\,(S(x) \to J(x))$ is true as soon as there is any non-student, since the implication is vacuously true for them. It says almost nothing. Wrong translation. Try it: select it and flip every student’s J to 0. Nobody in the class has taken Java, yet the formula stays true, held up by Kerem, Mert or Lina.

Translating English into logic

Translation is a skill, and a recipe helps.

Worked example: one sentence, two domains

“Every student in this class has taken a course in Java.”

• Domain = students in this class. Everybody in the domain is already a student, so no $S(x)$ is needed: $\forall x\, J(x)$.
• Domain = all people. Now we must filter: $\forall x\,(S(x) \to J(x))$.

Both are correct; they differ only because the domains differ. A narrower domain gives a shorter formula, a wider domain needs the filter.

A dictionary of sentence patterns

Practice with a strange island

Lewis Carroll style, from the lecture slides. The domain is all creatures; $F(x)$: $x$ is a fleegle, $S(x)$: $x$ is a snurd, $T(x)$: $x$ is a thingamabob. Cover the right column and translate first.

The last one hides a trap: “any” here means every. “If any fleegle is a snurd, then it is also a thingamabob” is a rule about each fleegle-snurd, so it is universal.

Specifications from systems

Engineers write requirements in exactly this form. Let $L(m, y)$: message $m$ is larger than $y$ megabytes, $C(m)$: message $m$ is compressed, $A(u)$: user $u$ is active, $V(n)$: network link $n$ is available.

The second one already contains two quantifiers, one inside the other. Nested quantifiers are next week’s topic.

The lions argument

Another classic from the slides. Domain: all creatures. $P(x)$: $x$ is a lion, $Q(x)$: $x$ is fierce, $R(x)$: $x$ drinks coffee.

Is the argument valid? Take the lion that does not drink coffee (the witness of line 2). By line 1 it is fierce. So it is a fierce creature that does not drink coffee, a witness for line 3. In week 6 we will turn this kind of reasoning into formal rules of inference.

From logic back to English

Going the other way is just as important: you must be able to read a formula. Let the domain be all students in your school, $C(x)$: $x$ has a computer, $F(x, y)$: $x$ and $y$ are friends.

Word by word: “for every student $x$, either $x$ has a computer, or there is a student $y$ who has a computer and is a friend of $x$.” Now say it like a human: “Every student either has a computer or has a friend who has one.” A good translation sounds like a sentence a person would actually say.

Negating quantified statements

Your manager says: “Every test passed.” You find one failing test. What is the exact opposite of the manager’s claim?

• Not “no test passed”. That is far too strong.
• It is: “some test did not pass.” One failing test is enough.

That is the whole idea, written as two laws.

Why are they called De Morgan’s laws? Over a finite domain $\{1, 2, 3\}$, $\forall$ is a big ∧ and $\exists$ is a big ∨, so the first law is literally week 3’s De Morgan:

Negating restricted statements, step by step

The negation must keep the filter, so it combines De Morgan for quantifiers with week 3’s $\neg(p \to q) \equiv p \land \neg q$.

Equivalences, and two traps

Two distributive laws hold for quantifiers:

“Everyone is tall and smart” says the same as “everyone is tall, and everyone is smart.” Fine. But the other two combinations fail:

Quantifiers in code and data

You will meet ∀ and ∃ every day as a software engineer, usually without the symbols.

Python. all() is $\forall$ and any() is $\exists$, both with short-circuiting:

grades = {"Ada": 92, "Can": 78, "Deniz": 45}

all(g >= 50 for g in grades.values())     # ∀: did everyone pass?  → False
any(g >= 90 for g in grades.values())     # ∃: did anyone get an A? → True
not any(g < 0 for g in grades.values())   # ¬∃ ≡ ∀¬: no negative grades → True

Note one subtle point: all([]) is True and any([]) is False. A ∀ statement over an empty domain is vacuously true (there is no counterexample), and an ∃ statement over an empty domain is false (there is no witness).

SQL. A WHERE clause is a predicate, and EXISTS is $\exists$. SQL has no FOR ALL. To ask “has every student taken Java?”, a database uses this week’s law, $\forall x\,(S \to J) \equiv \neg\exists x\,(S \land \neg J)$:

SELECT NOT EXISTS (
  SELECT * FROM people
  WHERE is_student AND NOT took_java
) AS every_student_took_java;

Testing. A unit test checks one example: an ∃-style piece of evidence. Property-based testing states a ∀ property and lets the computer hunt for a counterexample:

from hypothesis import given, strategies as st

@given(st.lists(st.integers()))
def test_sorting_keeps_length(xs):        # ∀ lists xs: len(sorted(xs)) == len(xs)
    assert len(sorted(xs)) == len(xs)

If the property is false, Hypothesis prints a counterexample, and usually the smallest one it can find.

A look ahead: nested quantifiers

Many real statements need two quantifiers, one inside the other. “Every user has a password” is $\forall u\, \exists p\; \text{Has}(u, p)$. And the order matters enormously: “for every number there is a bigger one” ($\forall x\, \exists y\; y > x$, true) is very different from “there is a number bigger than every number” ($\exists y\, \forall x\; y > x$, false). That is the whole of week 5.

Summary

• A predicate $P(x)$ is a statement with a variable: a yes/no question with a blank. It becomes a proposition when the blank is filled.
• Always fix the domain; the same statement can be true in one domain and false in another.
• $\forall x\, P(x)$: true for every $x$. Disproved by one counterexample. Over finite data it is a big ∧ and all().
• $\exists x\, P(x)$: true for at least one $x$. Proved by one witness. Over finite data it is a big ∨ and any().
• Golden rule: ∀ goes with →, ∃ goes with ∧. $\forall x\,(A \land B)$ and $\exists x\,(A \to B)$ are the two classic mistakes.
• Negation: swap the quantifier and push ¬ inside. $\neg\forall x\,(A \to B) \equiv \exists x\,(A \land \neg B)$ and $\neg\exists x\,(A \land B) \equiv \forall x\,(A \to \neg B)$.
• ∀ distributes over ∧ and ∃ over ∨, but not the other way round.

Practice

Before the lab

Lab 3 puts this week into code: you will evaluate ∀ and ∃ statements over a real student–course dataset with all() and any(), find witnesses and counterexamples automatically, and check De Morgan’s laws for quantifiers on data.

Tags:predicatepropositional functionquantifieruniversalexistentialforallexistsdomaincounterexamplewitnessnegationDe MorganSQLallany