Quantifiers and Predicate Logic MCQs: 10 Practice Problems Explained

Quantifier questions are difficult because they mix order, scope, implication, distribution, uniqueness, graph reachability, and the difference between truth and validity. Memorising ∀ = all and ∃ = some is not enough when one changed quantifier can change who depends on whom. Several items have imperfect source notation, so treat the formula itself as the authority rather than the listed answer. Use a solve-check-explain routine throughout. If the notation feels unfamiliar, revise propositional and predicate logic first. Attempt every item on paper before reading its answer beat.

Related reading: predicate logic practice and predicate logic MCQs.

The four checks to run before choosing an option

Fix the domain, then mark each quantifier's scope. Rewrite A→B as ¬A∨B when useful. Search for a witness to prove an existential or one counterexample to refute a universal. Keep truth separate from validity because Q9 depends on that distinction.

For a quick scope check, take the domain {1,2} and let P(x,y) mean x=y. Then ∀x∃y P(x,y) is true: choose y=1 for x=1 and y=2 for x=2. But ∃y∀x P(x,y) is false because no fixed y equals both elements. Use the GATE CS Exam Preparation path for the broader subject sequence.

Integer-domain quantifier practice

Q1. Universally quantified square-root statement, Q704 (NAT)

Consider the following universally quantified statements where the domain for all variables consists of all integers S:

∀p ∃q (p = √q)

The largest value of p for which q exist would be ?

Options: none. This is a NAT record.

Result: The listed answer 1 is mathematically invalid. For p=0,1,2,100, the construction q=p² gives the integer witnesses 0,1,4,10000, and it works for every non-negative integer p. Negative p cannot equal an integer’s principal square root, so the universal statement over all integers is false. Among the admissible non-negative values, no largest p exists.

Q2. Integer predicates with a missing source connective, Q697 (MCQ)

Consider the following predicates with the domain as set of integers for all variables.

P(m):m²>-1

Q(m):m²-6m+8=0

R(m,n):m²=n

Which of the following statement is TRUE?

• A. ∀m [Qm ⋀Pm]

• B. ∀m Pm ∃n Qn

• C. ∀n ∀m [Pm→R(m,n)]

• D. Both (a) and (c)

Answer: B, under the intended reading ∀m Pm ∧ ∃n Qn. The displayed statement omits that conjunction. For every integer, m²≥0>-1. Also, m²-6m+8=(m-2)(m-4), so n=2 and n=4 witness Q. A fails at m=0 because Q(0) is false. C fails at m=3,n=5: P(3) is true but R(3,5) is false since 9≠5.

Q3. Corrected rendering of the same integer-predicate family (MCQ)

Consider the following predicates, where the domain of all variables is the set of integers.

Pₘ: m² > −1

Qₘ: m² − 6m + 8 = 0

Rₘ, ₙ: m² = n

Which of the following statements is TRUE?

• A. ∀m [Qₘ ∧ Pₘ]

• B. ∀m Pₘ ∧ ∃n Qₙ

• C. ∀n ∀m [Pₘ → Rₘ, ₙ]

• D. Both ∀m [Qₘ ∧ Pₘ] and ∀n ∀m [Pₘ → Rₘ, ₙ]

Answer: B. This version restores the missing conjunction and expands option D. Every integer satisfies m²>-1. The factorisation m²-6m+8=(m-2)(m-4) gives witnesses 2 and 4. A still fails at m=0, while C fails at m=3,n=5 because 9 is not 5. Therefore D also fails.

Distribution laws and quantifier order

Q4. Distribution over conjunction and disjunction, Q717 (MSQ)

Consider the following first order logic statements, where P(x) and Q(x) are predicates. Which of the following are true?

• A. ∀x (P(x) ∧ Q(x)) → ∀x P(x) ∧ ∀x Q(x)

• B. ∀x P(x) ∧ ∀x Q(x) → ∀x (P(x) ∧ Q(x))

• C. ∃x (P(x) ∨ Q(x)) → ∃x P(x) ∨ ∃x Q(x)

• D. ∃x P(x) ∨ ∃x Q(x) → ∃x (P(x) ∨ Q(x))

Answer: A, B, C, and D. A and B are the two directions of ∀x(P∧Q) ≡ (∀xP∧∀xQ). C and D are the two directions of ∃x(P∨Q) ≡ (∃xP∨∃xQ). On {1,2}, set P(1) and Q(2) true, with P(2) and Q(1) false. Both existential sides are true; the equivalences hold generally.

Q5. Which quantifier-order implications are valid? Q745 (MSQ)

Consider the following statements:

(i) ∀x ∃y P(x,y) ⇒ ∃y ∀x P(x,y)

(ii) ∃x ∀y P(x,y) ⇒ ∀y ∃x P(x,y)

(iii) ∀x ∀y P(x,y) ⇒ ∃x ∃y P(x,y)

(iv) ∀x ∃y P(x,y) ⇒ ∃x ∃y P(x,y)

Which of the above statements are valid?

• A. (i)

• B. (ii)

• C. (iii)

• D. (iv)

Answer: B, C, and D, for a non-empty domain. Refute (i) using {1,2} and P(x,y):x=y: each x has its own y, but no single y works for both. In (ii), the witness chosen by ∃x works for every y. For (iii), choose the pair (1,1). For (iv), start with x=1 and take the y promised by the premise.

Existence plus uniqueness

Q6. There is only one apple, Q721 (MSQ)

Which of the following represents that there is only one apple when A(x): x is an apple?

• A. (∃x A(x))∧(∀y ((y≠x)→¬A(y)))

• B. (∃x A(x))∧(∀y (A(y)→y=x))

• C. ∀x ∀y [(A(x) ∧ A(y))→x = y]

• D. ∃x ∀z (A(z)↔z=x)

Answer: A, B, and D under the intended scoping. In {red,green}, let only A(red) be true. A and B choose red and exclude every other apple; D says A(z) holds exactly when z=red. C says at most one, so it remains true with no apples. In options A and B, the parentheses leave x outside ∃x. Their intended closed forms put uniqueness inside the existential's scope.

Translating an English exception into predicate logic

Q7. “No prime except 5 is divisible by 5” (MSQ)

Consider the following statement: “No prime except 5 is divisible by 5.” Assume the domain is the set of natural numbers. Which of the following are equivalent predicate-logic representations of the above statement?

• A. ∀x∈N [(x≠5 ∧ Prime(x)) → ~Divisible by 5(x)]

• B. ~∃x∈N [x≠5 ∧ Prime(x) ∧ Divisible by 5(x)]

• C. ∀x∈N [Divisible by 5(x) → ~(x≠5) ∨ ~Prime(x)]

• D. ∃x∈N [x=5 ∨ Prime(x) ∧ Divisible by 5(x)]

Answer: A, B, and C. Write D₅(x) for “is divisible by 5.” A states directly that any prime other than 5 fails D₅. B is the existential negation of the same forbidden case. C is the contrapositive form: divisibility implies x=5 or non-primality. D is too weak because x=5 makes its existential true without excluding any other divisible prime.

Tautology, validity, and graph-reachability questions

Q8. Which formulae are tautologies? (MCQ)

Which of the following are Tautologies

I) ((a->b) ∧ (b->c)) -> (a->c)

II) (( a<->c) -> ~b ) ->(a∧c)

III) a-> (b->a)

• A. I is tautology

• B. II, III are tautologies

• C. I, II, III are tautologie

• D. I and III are tautology

Answer: D. I chains a→b and b→c to get a→c. III is true when a is false, and when a is true its inner b→a is true. For II, set a=false, b=false, and c=false. Then a↔c and ¬b are true, making the outer antecedent true, while a∧c is false. Thus II is not a tautology.

Q9. Truth and falsity versus validity (MCQ, UGC NET Paper I December 2023)

Given below are two statements :

Statement (I) : Truth and falsity are attributes of individual propositions.

Statement (II) : Validity can be attributed to any single proposition by itself.

In the light of the above statements, choose the most appropriate answer from the options given below :

• A. Both Statement I and Statement II are correct

• B. Both Statement I and Statement II are incorrect

• C. Statement I is correct but Statement II is incorrect

• D. Statement I is incorrect but Statement II is correct

Answer: C under the distinction between propositions and arguments used here. 2+2=4 is true, while 2+2=5 is false. An argument is valid when its conclusion follows from its premises, as in P→Q, P, therefore Q. Here, validity is not assigned to an isolated proposition.

Q10. A quantified graph-connectivity statement, Q708 (MCQ)

Let G be an undirected graph. Let P(x,y) mean that there is a path from vertex x to vertex y.

∃x,y,z, ~Px,y⋀~P(x,z)⋀~P(y,z) represents that

• A. G has at least three connected components

• B. G has exactly three connected components

• C. G has at most three connected components

• D. None of these

Answer: A. Take vertices {a,b,c,d} with the sole edge {a,b}. Choose x=a, y=c, and z=d. No path connects any chosen pair, and the components are {a,b}, {c}, and {d}. The formula forces at least three distinct components, but does not forbid a fourth or fifth, so “exactly” and “at most” are too strong.

Revision table, important cautions, and the next practice step

Propositional connectives and inference receive a broader treatment in Propositional and Predicate Logic MCQs: 12 Solved Questions. Apply the formula-first audit to quantified notation, witness dependency, uniqueness, and countermodels.

The short version

Quantifier order controls dependency. Existence and uniqueness are separate obligations. One witness proves an existential; one counterexample refutes a universal. Check the displayed notation before trusting any answer key.

Theory-first readers can follow GATE Guidance by Sanchit Sir. Practice-first readers can use the GATE Test Series.