Consider this argument: "Every CSE student studies discrete mathematics. Asha is a CSE student. Therefore Asha studies discrete mathematics." It is obviously correct. Yet propositional logic cannot even express why. It would treat the three sentences as three unrelated letters p, q, r, and p ∧ q → r is not a tautology. What is missing is the ability to talk about objects, their properties, and the words "every" and "some".
Predicate logic (also called first-order logic) adds exactly these. It is the logic in which mathematical definitions, database queries and program specifications are written. In this chapter we define predicates and domains, the quantifiers ∀ and ∃, bound and free variables, how to negate quantified statements, how to translate English correctly (a favourite GATE topic), nested quantifiers and why their order matters, and the equivalences that hold (and do not hold) for quantifiers. Using quantified statements inside arguments is the subject of the next chapter, Rules of Inference.
Predicates and the Domain
A predicate (or propositional function) P(x1, ..., xn) is a statement containing variables that becomes a proposition when every variable is replaced by a value from a set called the domain (or universe of discourse). n is the number of places (arity) of the predicate.
Let P(x) be "x > 3" over the domain ℤ. Then P(x) itself is not a proposition, but P(5) is the true proposition "5 > 3", and P(2) is false. A two-place example: L(x, y) = "x + y = 10". L(4, 6) is true, L(1, 1) is false.
Predicates behave like Boolean functions in code: def P(x): return x > 3. They can be combined with all the connectives from Propositional Logic: P(x) ∧ ¬Q(x) is again a predicate.
The Two Quantifiers
There are two ways to turn a predicate into a proposition without plugging in a specific value: claim it for all values, or for at least one.
Universal quantification ∀x P(x), read "for all x, P(x)", is true if P(x) is true for every x in the domain, and false if there is at least one x for which P(x) is false (a counterexample).
Existential quantification ∃x P(x), read "there exists an x such that P(x)", is true if P(x) is true for at least one x in the domain, and false if P(x) is false for every x.
Statement | True when | False when |
|---|---|---|
∀x P(x) | P(x) is true for every x | There is an x with P(x) false |
∃x P(x) | There is an x with P(x) true | P(x) is false for every x |
If the domain is finite, say {a1, ..., an}, the quantifiers are just long connectives:
∀x P(x) ≡ P(a1) ∧ P(a2) ∧ ... ∧ P(an) (Python: all(P(x) for x in D))
∃x P(x) ≡ P(a1) ∨ P(a2) ∨ ... ∨ P(an) (Python: any(P(x) for x in D))This view explains almost every rule in this chapter. For infinite domains like ℤ we cannot write the long conjunction, which is precisely why quantifiers are needed.
The Domain Changes the Answer
Statement | Domain ℕ | Domain ℤ | Domain ℝ |
|---|---|---|---|
∀x (x2 ≥ x) | T | T | F (x = 0.5 gives 0.25 < 0.5) |
∃x (x2 = 2) | F | F | T (x = √2) |
∀x (x ≥ 0) | T | F (x = −1) | F |
∃x (x + 1 = 0) | F | T (x = −1) | T |
So a quantified statement has no truth value until the domain is fixed. In this tutorial domains are always assumed to be non-empty, which is the standard convention.
Uniqueness: ∃!
∃!x P(x) means "there exists exactly one x such that P(x)". It is shorthand for ∃x (P(x) ∧ ∀y (P(y) → y = x)): some x works, and anything that works is that same x. Over ℤ, ∃!x (x + 3 = 5) is true (only x = 2), but ∃!x (x2 = 4) is false (both 2 and −2 work).
Scope, Bound and Free Variables
Quantifiers have higher precedence than all connectives. So ∀x P(x) ∨ Q(x) means (∀x P(x)) ∨ Q(x), not ∀x (P(x) ∨ Q(x)). The part of the formula a quantifier applies to is its scope.
An occurrence of a variable is bound if it lies in the scope of a quantifier on that variable; otherwise it is free. A formula with no free variables is a proposition; a formula with free variables is still a predicate.
Example. In ∃x (P(x) ∧ R(x, y)) ∨ Q(x):
the x in P(x) and in R(x, y) is bound by ∃x;
the x in Q(x) is free (it is outside the brackets, so outside the scope);
y is free.
Bound variables are dummy names, like the loop variable in ∑i=1n i. ∀x P(x) and ∀z P(z) mean the same. Free variables are not: P(x) and P(z) are different formulas.
Negating Quantified Statements
What is the opposite of "every student passed"? Not "no student passed", but "some student did not pass". One failure is enough to make "every" false.
De Morgan's laws for quantifiers:
¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)
On a finite domain these are exactly De Morgan's laws from Logical Equivalences & Normal Forms: ¬(P(a1) ∧ ... ∧ P(an)) ≡ ¬P(a1) ∨ ... ∨ ¬P(an). The rule of thumb: move ¬ inward, flipping each quantifier it passes (∀ ↔ ∃), then negate the predicate using the propositional laws.
Worked Examples
¬∀x (x² ≥ x) ≡ ∃x (x² < x)
¬∃x (S(x) ∧ C(x)) ≡ ∀x ¬(S(x) ∧ C(x)) ≡ ∀x (S(x) → ¬C(x))
¬∀x (S(x) → C(x)) ≡ ∃x ¬(S(x) → C(x)) ≡ ∃x (S(x) ∧ ¬C(x))
¬∀x ∃y (x < y) ≡ ∃x ¬∃y (x < y) ≡ ∃x ∀y (x ≥ y)The last line reads: "it is not true that every number has a bigger one" means "some number is at least as big as everything", i.e. there is a largest element. Over ℕ the original is true (no largest natural number), so the negation is false, as it must be.
Translating English into Predicate Logic
This is where most marks are won and lost. The key is the pairing rule:
∀ goes with →. ∃ goes with ∧.
"Every A is B": ∀x (A(x) → B(x)).
"Some A is B": ∃x (A(x) ∧ B(x)).
Why? Let the domain be all people, S(x) = "x is a student in this class", C(x) = "x has a laptop".
"Every student has a laptop" written as ∀x (S(x) ∧ C(x)) says everyone in the world is a student and has a laptop. Wrong. The correct ∀x (S(x) → C(x)) says: for anyone, if they are a student, they have a laptop. Non-students make the implication vacuously true, so they are ignored, which is what we want.
"Some student has a laptop" written as ∃x (S(x) → C(x)) is true as soon as there is any non-student (the implication is then vacuously true). Far too weak. The correct ∃x (S(x) ∧ C(x)) demands one person who is both.
The Four Classic Forms
English | Formula | Equivalent form |
|---|---|---|
Every student has a laptop. | ∀x (S(x) → C(x)) | ¬∃x (S(x) ∧ ¬C(x)) |
Some student has a laptop. | ∃x (S(x) ∧ C(x)) | ¬∀x (S(x) → ¬C(x)) |
No student has a laptop. | ¬∃x (S(x) ∧ C(x)) | ∀x (S(x) → ¬C(x)) |
Not every student has a laptop. (Some student does not.) | ¬∀x (S(x) → C(x)) | ∃x (S(x) ∧ ¬C(x)) |
Two more patterns that are often confused:
"Only students have laptops" means "if someone has a laptop, they are a student": ∀x (C(x) → S(x)). The arrow is reversed compared to "every student has a laptop", just as "only if" reversed it in Propositional Logic.
"None of my friends are perfect" (F(x): x is my friend, P(x): x is perfect): ¬∃x (F(x) ∧ P(x)), equivalently ∀x (F(x) → ¬P(x)).
Nested Quantifiers
With predicates of two or more variables we can stack quantifiers. Read them left to right, like nested loops:
∀x ∃y P(x, y) for each x ... (outer loop)
pick a y, which may depend on x ... (inner loop)
∃y ∀x P(x, y) pick ONE y first,
then it must work for every xOrder Matters
Domain ℤ:
∀x ∃y (x + y = 0): every integer has an additive inverse. True (choose y = −x, a different y for each x).
∃y ∀x (x + y = 0): a single integer y that cancels every x. False (x = 0 forces y = 0, but then x = 1 fails).
With L(x, y) = "x likes y" over all people:
Formula | Meaning |
|---|---|
∀x ∃y L(x, y) | Everybody likes somebody (possibly different people). |
∃y ∀x L(x, y) | There is one person whom everybody likes. |
∃x ∀y L(x, y) | Somebody likes everybody. |
∀y ∃x L(x, y) | Everybody is liked by somebody. |
∀x ∀y L(x, y) | Everybody likes everybody. |
∃x ∃y L(x, y) | Somebody likes somebody. |
Quantifiers of the same kind can be swapped: ∀x ∀y ≡ ∀y ∀x and ∃x ∃y ≡ ∃y ∃x. Quantifiers of different kinds cannot. The only general relation is the one-way implication ∃x ∀y P(x, y) → ∀y ∃x P(x, y).
Why the implication holds: if one x0 works for every y, then for each y we can simply choose that same x0. The converse fails, as the x + y = 0 example shows (rename the variables to see it).
Worked Translation with Nested Quantifiers
"Every teacher is liked by at least one student." Domain: people; T(x): x is a teacher; S(y): y is a student; L(y, x): y likes x.
Step 1, outer: "for every teacher x" → ∀x (T(x) → ...). Step 2, inner: "there is a student y who likes x" → ∃y (S(y) ∧ L(y, x)). Result: ∀x (T(x) → ∃y (S(y) ∧ L(y, x))). Note both pairing rules in use.
Equivalences Involving Quantifiers
Two quantified formulas are logically equivalent if they have the same truth value for every domain and every interpretation of the predicates.
Statement | Status |
|---|---|
∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x) | Equivalent: ∀ distributes over ∧ |
∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x) | Equivalent: ∃ distributes over ∨ |
∀x P(x) ∨ ∀x Q(x) → ∀x (P(x) ∨ Q(x)) | Valid only in this direction |
∃x (P(x) ∧ Q(x)) → ∃x P(x) ∧ ∃x Q(x) | Valid only in this direction |
∀x (P(x) ∨ A) ≡ ∀x P(x) ∨ A | Equivalent when x does not occur free in A |
∀x (A → P(x)) ≡ A → ∀x P(x) | Equivalent when x is not free in A |
∀x (P(x) → A) ≡ ∃x P(x) → A | Equivalent when x is not free in A (note ∀ becomes ∃!) |
Counterexample for the one-way rules. Domain {1, 2}, P(x): x = 1, Q(x): x = 2. Every element is 1 or 2, so ∀x (P(x) ∨ Q(x)) is true, but neither "all are 1" nor "all are 2" holds. And some element is 1 and some element is 2, but no element is both. The program below evaluates exactly this.
The last row of the table surprises many students. Check it by unpacking: ∀x (P(x) → A) ≡ ∀x (¬P(x) ∨ A) ≡ (∀x ¬P(x)) ∨ A ≡ ¬∃x P(x) ∨ A ≡ ∃x P(x) → A. In words: "for every x, if x is a bug then the release is delayed" says the same as "if there is any bug, the release is delayed".
Checking on a Finite Domain
D = range(-5, 6) # a small finite domain: -5 .. 5
# For every x there is a y with x + y = 0
print(all(any(x + y == 0 for y in D) for x in D))
# There is a y such that for every x, x + y = 0
print(any(all(x + y == 0 for x in D) for y in D))
# Distribution over a 2-element domain
D2 = [1, 2]
P = lambda x: x == 1
Q = lambda x: x == 2
print("forall x (P or Q): ", all(P(x) or Q(x) for x in D2))
print("forall x P or forall x Q: ", all(P(x) for x in D2) or all(Q(x) for x in D2))
print("exists x (P and Q): ", any(P(x) and Q(x) for x in D2))
print("exists x P and exists x Q:", any(P(x) for x in D2) and any(Q(x) for x in D2))
# Vacuous truth: every element of an empty list is negative
print(all(x < 0 for x in []))Output:
True
False
forall x (P or Q): True
forall x P or forall x Q: False
exists x (P and Q): False
exists x P and exists x Q: True
TrueThe nesting of all and any mirrors the nesting of ∀ and ∃ exactly. A finite check like this can find counterexamples, but it cannot prove a statement about an infinite domain such as ℤ; that needs a proof. (We also brute-forced every predicate on domains of up to 3 elements to confirm each "equivalent" and "one way" entry in the table above.) The last line shows that Python's all over nothing is True, the programming version of a vacuously true universal statement.
Where You Meet Quantifiers in Practice
SQL:
WHERE EXISTS (subquery)is ∃; "find customers who bought every product" is ∀, written in SQL as a doubleNOT EXISTS, which is exactly ¬∃x ¬P(x).Specifications: "the array is sorted" is ∀i (0 ≤ i < n − 1 → a[i] ≤ a[i + 1]).
Mathematical definitions: "n is even" is ∃k ∈ ℤ (n = 2k); "f is one-to-one" (a property defined later, in Functions) is ∀a ∀b (f(a) = f(b) → a = b).
Common Mistakes
∀ with ∧. "All A are B" is ∀x (A(x) → B(x)), not ∀x (A(x) ∧ B(x)).
∃ with →. "Some A is B" is ∃x (A(x) ∧ B(x)), not ∃x (A(x) → B(x)).
Negating "all" as "none". ¬∀x P(x) is ∃x ¬P(x) ("not all"), not ∀x ¬P(x) ("none").
Swapping ∀ and ∃. ∀x ∃y and ∃y ∀x are different statements; only ∃∀ → ∀∃ holds.
Distributing ∀ over ∨ or ∃ over ∧. These hold only in one direction.
Ignoring the domain. ∀x (x2 ≥ x) is true over ℤ and false over ℝ.
Misreading scope. ∀x P(x) → Q(x) means (∀x P(x)) → Q(x); the last x is free.
Interview and GATE-Style Questions
Translate "None of my friends are perfect" into two equivalent formulas. (F(x): x is my friend, P(x): x is perfect)
¬∃x (F(x) ∧ P(x)) and ∀x (F(x) → ¬P(x)). They are equivalent by De Morgan for quantifiers followed by ¬(a ∧ b) ≡ a → ¬b.
Negate ∀x ∃y (x < y) and decide which of the two is true over ℕ.
The negation is ∃x ∀y (x ≥ y), "there is a largest natural number". Over ℕ the original is true (take y = x + 1) and the negation is false.
Which is valid? (a) ∀x (P(x) ∨ Q(x)) → ∀x P(x) ∨ ∀x Q(x) (b) ∃x (P(x) ∧ Q(x)) → ∃x P(x) ∧ ∃x Q(x)
(b) is valid: the witness for P(x) ∧ Q(x) is a witness for both. (a) is not: on domain {1, 2} with P(x): x = 1 and Q(x): x = 2, the left side is true and the right side is false.
Over the domain ℤ, give the truth values of ∃x ∀y (x · y = 0) and ∀x ∃y (x · y = 1).
∃x ∀y (x · y = 0) is true with x = 0. ∀x ∃y (x · y = 1) is false: for x = 2 there is no integer y with 2y = 1 (and x = 0 fails too).
In ∀x (P(x) → Q(x, y)) ∧ ∃z R(z, x), which variable occurrences are free?
y (in Q) and the x in R(z, x), which is outside the scope of ∀x. The x's in P and Q are bound by ∀x, and z is bound by ∃z.
Translate "Every teacher is liked by at least one student" and "Some student likes every teacher".
∀x (T(x) → ∃y (S(y) ∧ L(y, x))) and ∃y (S(y) ∧ ∀x (T(x) → L(y, x))). The second implies the first (one student liking all teachers is a witness for each teacher), but not conversely.
Is ∃x (P(x) → Q(x)) a good translation of "Some P is Q"?
No. It is true whenever some element is not P (the implication is vacuously true for it), even if no P is Q. The correct translation is ∃x (P(x) ∧ Q(x)).
Summary
A predicate becomes a proposition when its variables get values from the domain or are bound by quantifiers.
∀x P(x) needs P everywhere (one counterexample refutes it); ∃x P(x) needs one witness. On finite domains they are big ∧ and big ∨.
Negation flips quantifiers: ¬∀x P ≡ ∃x ¬P, ¬∃x P ≡ ∀x ¬P.
Translation rule: ∀ with →, ∃ with ∧; "only A are B" is ∀x (B(x) → A(x)).
Same quantifiers commute; mixed ones do not. ∃x ∀y P → ∀y ∃x P is the only general direction.
∀ distributes over ∧ and ∃ over ∨, but not ∀ over ∨ or ∃ over ∧.
Next, Rules of Inference shows how to derive conclusions step by step, in both propositional and predicate logic.