Propositional logic deals with statements that are already complete, true or false. But many interesting claims talk about "all" or "some": every server has a patch, some user has a weak password, for every request there is a response. Expressing them requires predicate logic, also called first-order logic. It is the tool for writing precise specifications, reasoning about queries and stating theorems.
Predicates and domains
A predicate is a statement with one or more free variables, which becomes true or false once the variables are given values. P(x) = "x is even" is neither true nor false; P(4) is true, P(7) is false. A predicate can have several arguments: G(x, y) = "x is greater than y".
Each variable ranges over a domain (or universe of discourse): the integers, the users of a system, the files in a folder. The domain must always be stated, because the same statement can be true in one domain and false in another. "Every x has a predecessor" is true over the integers and false over the natural numbers, where 0 has no predecessor.
The two quantifiers
- Universal ∀x P(x): "for every x, P(x)". It is true if P holds for all elements of the domain.
- Existential ∃x P(x): "there exists x such that P(x)". It is true if P holds for at least one element.
Over a finite domain {a₁, …, aₙ} the quantifiers are just abbreviations: ∀x P(x) is equivalent to P(a₁) ∧ … ∧ P(aₙ), while ∃x P(x) is equivalent to P(a₁) ∨ … ∨ P(aₙ). That is exactly what Python's all() and any() functions do:
all_patched = all(s.patch_applied for s in servers)
someone_weak = any(u.weak_password for u in users)
An instructive detail: all([]) returns True and any([]) returns False. This is not a quirk of the language: a universal statement over an empty domain is true (there is no counterexample), an existential one is false (there is no witness).
Negating quantifiers
The negation rules are the "quantified" version of De Morgan's laws:
- ¬∀x P(x) ≡ ∃x ¬P(x)
- ¬∃x P(x) ≡ ∀x ¬P(x)
"Not all backups succeeded" means "at least one backup failed", not "all backups failed". "There is no user without a password" means "every user has a password".
To negate a formula with several quantifiers, work from the left: each ∀ becomes ∃, each ∃ becomes ∀, and the negation travels down to the predicate. Example:
¬∀x ∃y (y > x) ≡ ∃x ∀y ¬(y > x) ≡ ∃x ∀y (y ≤ x)
That is: "it is not true that for every number there is a larger one" is equivalent to "there is a number greater than or equal to all numbers", in other words a maximum.
The order of quantifiers matters
Quantifiers of the same kind can be swapped: ∀x ∀y is equivalent to ∀y ∀x. But swapping ∀ and ∃ changes the meaning. Consider the predicate K(u, k) = "user u knows key k".
- ∀u ∃k K(u, k): every user knows at least one key (possibly a different one for each).
- ∃k ∀u K(u, k): there is a key that every user knows.
The second is much stronger, and in a security context it describes a very different situation: a key shared by everyone. The second implies the first, but not the other way round.
A classic mathematical example: over the integers, ∀x ∃y (y > x) is true (for every number there is a larger one, just take x + 1), while ∃y ∀x (y > x) is false (there is no integer larger than all of them).
A trick for reading these correctly: in ∀x ∃y, y may depend on x. In ∃y ∀x, y is chosen once and for all, before x is known. Think of it as a game: who moves first and who responds.
Restricted quantifiers
In practice quantifiers are almost always restricted to part of the domain. The correct forms are:
- "all A are B": ∀x (A(x) → B(x))
- "some A is B": ∃x (A(x) ∧ B(x))
Swapping the connectives is a frequent mistake. ∀x (A(x) ∧ B(x)) says that the whole domain is both A and B, which is very different. And ∃x (A(x) → B(x)) is almost always true for trivial reasons: a single element that is not A is enough, because an implication with a false premise is true.
Where you meet them
- SQL:
EXISTSis the existential quantifier; "all" is often expressed as "there is no counterexample", that is withNOT EXISTS, applying precisely the negation rule. - Specifications and tests: the properties to verify are universal statements ("for every valid input, the output is sorted"); a failing test is a witness for the negated existential.
- Contracts and assertions: preconditions and invariants are naturally written with ∀ and ∃.
In short
- A predicate becomes true or false only once its variables take values in a stated domain.
- ∀ is an AND over the whole domain, ∃ an OR; over an empty domain ∀ is true and ∃ is false.
- Negation swaps ∀ with ∃ and pushes the negation down to the predicate.
- Swapping ∀ and ∃ changes the meaning: in ∀x ∃y, y may depend on x.
- "All A are B" uses →, "some A is B" uses ∧.
