First-order logic: domains and quantifiers
Objectives and prerequisites
Read a quantified statement with its domain and scope, translate “every,” “some” and “exactly one,” negate quantified formulas correctly, and decide when the order of quantifiers changes meaning. Prerequisites: propositions, implication, conjunction and negation from Propositional logic and truth tables. This is a first-order-logic foundation, not a complete treatment of proof systems, resolution, formal semantics or all GATE logic questions.
We use classical two-valued logic, ordinary equality and a stated nonempty domain. Restricted categories, such as the students inside a larger universe of people, may be empty. We do not silently change the domain halfway through a question.
1. Predicates need inputs and a domain
A predicate is a statement form with variables. For example P(x): “x is even” can be evaluated after choosing x from an appropriate domain. Over integers, P(4) is true and P(5) is false. The open expression P(x) is not yet a closed sentence with one truth value unless an assignment for x is supplied or x is bound by a quantifier.
The universal quantifier ∀ means “for every.” The existential quantifier ∃ means “there exists at least one.” Thus ∀x P(x) says every domain element satisfies P; ∃x P(x) says at least one does. “Some” in logic means at least one, possibly all, not “some but not all.”
Domain matters. The sentence ∀x(x²≥x) is true over integers: x(x−1)≥0 for x≤0 and for x≥1. It is false over real numbers because x=1/2 gives 1/4<1/2. The symbols did not change; the allowed inputs did. Always write the domain beside the formula before judging it.
2. Scope, free variables and bound variables
A quantifier controls the formula in its scope. In ∀x(P(x)→Q(x)), x is bound in both predicates. In (∀x P(x))→Q(x), the quantifier ends at the closing parenthesis; the x in Q(x) is free. These are not merely two visual layouts of the same sentence. Prefer full parentheses to relying on shorthand conventions.
In ∀x∃y R(x,y), both variables are bound. In ∀x R(x,y), y remains free and the formula can depend on the assigned y. A bound variable is a placeholder: ∀x P(x) and ∀z P(z) say the same thing if the renaming does not capture a variable that was free. For example, changing ∀x R(x,y) to ∀y R(y,y) is not a safe renaming; it changes the roles of y.
3. Translate restricted statements
Let the domain be all people. S(x) means “x is a student” and P(x) means “x passed.”
- Every student passed: ∀x(S(x)→P(x)). A nonstudent does not violate this conditional.
- Some student passed: ∃x(S(x)∧P(x)). The witness must be both a student and someone who passed.
- No student passed: ∀x(S(x)→¬P(x)), equivalently ¬∃x(S(x)∧P(x)).
- Not every student passed: ∃x(S(x)∧¬P(x)). At least one student failed to pass.
For “every student,” using ∀x(S(x)∧P(x)) would incorrectly assert that every person is a student. For “some student,” using ∃x(S(x)→P(x)) is too weak: a nonstudent makes the implication true even if no student passed.
If there are no students, “every student passed” is true vacuously: there is no student counterexample. “Some student passed” is false. This concerns an empty restricted category within a nonempty universe of people; it does not require an empty first-order domain. A universal claim by itself does not establish that students exist.
4. Negate one quantifier at a time
Negation exchanges “all” and “exists” and moves inward:
¬∀x P(x) ≡ ∃x ¬P(x).
¬∃x P(x) ≡ ∀x ¬P(x).
Apply propositional negation laws after crossing the quantifiers. For example:
¬∀x(S(x)→P(x)) ≡ ∃x ¬(S(x)→P(x)) ≡ ∃x(S(x)∧¬P(x)).
The final conjunction comes from ¬(a→b)≡a∧¬b. Merely putting a negation on P while leaving a universal quantifier would mean “no student passed,” a different assertion, not the general negation. If no students exist, “no student passed” is true but “not every student passed” is false. Only with at least one student does “no student passed” imply that a student did not pass.
With two quantifiers, ¬∀x∃y R(x,y) ≡ ∃x∀y ¬R(x,y). Read this as: there is one x for which no y works. Do not reverse the order while negating; flip each quantifier in place and negate the inner predicate.
5. Worked example: a witness can depend on x
Let D={1,2,3} and R(x,y) mean x+y=4. The possible witnesses are easy to list:
| x | A y making x+y=4 true |
|---|---|
| 1 | 3 |
| 2 | 2 |
| 3 | 1 |
Therefore ∀x∃y R(x,y) is true: for each x, at least one suitable y lies in D. The witness is allowed to vary after x is chosen.
But ∃y∀x R(x,y) is false. One common y would need to equal 3 for x=1 and 2 for x=2, which is impossible. The existential quantifier comes first, so its witness must be fixed before considering every x.
A general implication is ∃y∀x R(x,y) → ∀x∃y R(x,y): a single witness that works for everyone can also be used for each individual x. The converse need not hold, as this example shows. Consecutive universal quantifiers commute with each other; consecutive existential quantifiers commute with each other. Mixed quantifiers cannot generally be swapped.
6. Worked example: an infinite domain
Over integers, ∀x∃y(y>x) is true: for each integer x, choose the integer y=x+1. One formula gives a valid witness for every x, so listing integers one at a time is unnecessary.
Over the same domain, ∃y∀x(y>x) is false. Given any proposed y, choose x=y. Then y>x is false because y is not greater than itself. This refutes every possible candidate y, not just one unlucky choice.
For the finite domain {1,2,3}, even ∀x∃y(y>x) is false: x=3 has no larger domain element. Again, both the quantifier order and the domain are essential.
7. Exactly one and practical proof tests
“At least one object has P” is ∃x P(x). “Exactly one object has P” also needs uniqueness:
∃x(P(x)∧∀y(P(y)→y=x)).
This says choose one object with P, and require every object with P to be that same object. The formula ∃x∃y(P(x)∧P(y)) alone does not say two distinct objects exist, because x and y may denote the same object. Add x≠y if distinctness is required.
For a finite domain, a universal statement can be expanded as a conjunction and an existential statement as a disjunction. On D={a,b}, ∀x P(x) means P(a)∧P(b); ∃x P(x) means P(a)∨P(b). This is a useful small-instance check, not a method for listing an infinite domain.
To prove a universal statement, handle an arbitrary allowed element. To refute it, one counterexample suffices. To prove an existential statement, supply one valid witness. To refute it, show every candidate fails. For nested quantifiers, apply these tests in order and track which earlier variables each witness may depend on.
Quick reference and traps
- Name the domain before evaluating the formula.
- Read ∃ as “at least one,” not “exactly one.”
- Restricted universal statements usually use implication; restricted existential statements use conjunction.
- “Not all” and “none” are different.
- A later existential witness may depend on an earlier universal variable.
- Scope determines which variable occurrences are bound; parentheses are part of the meaning.
- The absence of a counterexample in a few tested cases is not a proof over an infinite domain.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option. All stated domains and operations matter.
C01. The domain is people. S(x) means student and P(x) means passed. Which is the negation of ∀x(S(x)→P(x))?
A. ∀x(S(x)→¬P(x)) B. ∃x(S(x)∧P(x)) C. ∃x(S(x)∧¬P(x)) D. ∀x(¬S(x)∧¬P(x))
Answer: C
A: This says no student passed. It is not equivalent to the required negation: with no students, this universal statement is true but the required existential statement is false.
B: This asserts a student passed, not that the universal claim has a counterexample.
C: Flip ∀ to ∃, then negate the implication: a student exists who did not pass.
D: This says every person is a nonstudent who did not pass; it does not negate the given rule.
C02. For D={1,2,3} and R(x,y): x+y=4, what are the truth values of ∀x∃y R(x,y) and ∃y∀x R(x,y), respectively?
A. F, T B. T, F C. T, T D. F, F
Answer: B
A: The values are reversed: each x has a witness, but no single y works for all x.
B: Witnesses for x=1,2,3 are y=3,2,1. A common y would have to equal both 3 and 2, so only the first statement is true.
C: The second statement fixes one y for all x; the different required values make that impossible.
D: The first statement permits the witness y to change with x and is true.
C03. Which variable is free in the formula ∀x R(x,y)?
A. Only x B. Only y C. Both x and y D. Neither x nor y
Answer: B
A: The universal quantifier binds x in R(x,y).
B: The formula binds x but contains no quantifier binding y, so y remains free.
C: Only y is free; x lies in the universal quantifier’s scope.
D: A quantifier for x does not automatically bind every other variable.
C04. With people as the domain, which formula correctly says “some student passed”?
A. ∀x(S(x)→P(x)) B. ∃x(S(x)→P(x)) C. ∀x(S(x)∧P(x)) D. ∃x(S(x)∧P(x))
Answer: D
A: This says every student passed and does not establish that a student exists.
B: A nonstudent can make the implication true without providing a student who passed.
C: This requires every person to be a student and to have passed, much more than requested.
D: The existential witness must satisfy both conditions: student and passed.
C05. How does the truth of ∀x(x²≥x) compare over the integers and over the real numbers?
A. True over integers; false over reals B. False over integers; true over reals C. True over both D. False over both
Answer: A
A: For integers, x≤0 or x≥1 gives x(x−1)≥0. The real input x=1/2 yields 1/4<1/2.
B: Integers satisfy the inequality; the counterexample 1/2 is real, not an integer.
C: The real-number claim fails at x=1/2.
D: The integer claim is true; testing only nonintegers cannot refute it.
C06. Which formula says that exactly one domain element satisfies P?
A. ∃x P(x) B. ∀x P(x) C. ∃x(P(x)∧∀y(P(y)→y=x)) D. ∃x∃y(P(x)∧P(y))
Answer: C
A: This supplies existence but does not rule out two or more satisfying elements.
B: This says every element satisfies P, not that exactly one does.
C: Choose a satisfying x and require every satisfying y to equal it; this supplies existence and uniqueness.
D: The two witnesses may be equal, and the formula does not prohibit further satisfying elements.
Sources and scope
This original foundation lesson aligns with Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. It is not full-topic or full-syllabus coverage. The syllabus confirms relevance; the NPTEL course is a primary institutional further-study reference. Examples and practice are original, not copied examination questions.
Sources checked 2026-10-14.
Sign in to keep your progress. Sign in