Predicate Logic and Quantifiers MCQs: 10 Solved Questions with Explanations

A witness proves an existential claim, while one counterexample defeats a universal claim. Quantifier order controls whether a witness may depend on another variable, and model size can constrain what a formula can express. For integers, reals, finite models, and divisibility, the decisive step is usually a witness, counterexample, or equivalence.

Read the universe, quantifier order, and connective first

Before solving:

1. Name the universe: integers, reals, or another domain.

2. Read quantifiers left to right. In forall x exists y, y may depend on x; exists y forall x needs one common y.

3. Try a witness for an existential claim and a counterexample for a universal claim.

4. Falsify P -> R with true P and false R; test both directions of a biconditional.

Remember: P -> R means not P or R, while P(c) or Q(c) proves neither disjunct alone.

Solved MCQs 1-3: integer truth values and function types

Q1. Truth statements over the integers

Which of the following statement are truth statements if universe of disclosure is set of integers :

(A) ∀n(n² ≥ 0)

(B) ∃n(n² = 2)

(C) ∀n(n² ≥ n)

(D) ∃n (n² < 0)

Choose the correct answer from the options given below :

A. (A) and (B) Only

B. (B) and (C) Only

C. (C) and (D) Only

D. (A) and (C) Only

Answer: D. Integer squares are non-negative, so (A) is true and (D) false; none equals 2, so (B) is false. For (C), n^2-n=n(n-1)>=0: every integer satisfies either n<=0 or n>=1.

Q2. Evaluate P(x) over the integers

The statement P(x): "x = x²". If the universe of disclosure consists of integers, which of the following have truth values :

(A) P(0)

(B) P(1)

(C) P(2)

(D) ∃x P(x)

(E) ∀x P(x)

Choose the correct answer from the options given below :

A. (A), (B) and (E) Only

B. (A), (B) and (C) Only

C. (A), (B) and (D) Only

D. (B), (C) and (D) Only

Answer: C. The predicate forces x(x-1)=0, so only x=0 and x=1 satisfy it. P(0), P(1), and the existential statement are therefore true, while P(2) and the universal statement are false.

Q3. Match quantified definitions of a function

Match the following in List-I and List-II, for a function f :

List-I: (a) ∀x ∀y (f(x)=f(y) → x=y); (b) ∀y ∃x (f(x)=y); (c) ∀x f(x)=k

List-II: (i) Constant; (ii) Injective; (iii) Surjective

Code :

A. (a)-(i), (b)-(ii), (c)-(iii)

B. (a)-(iii), (b)-(ii), (c)-(i)

C. (a)-(ii), (b)-(i), (c)-(iii)

D. (a)-(ii), (b)-(iii), (c)-(i)

Answer: D. Equal outputs forcing equal inputs makes (a) injective. Every y having a preimage makes (b) surjective. One fixed output k makes (c) constant: (a)-(ii), (b)-(iii), (c)-(i).

Solved MCQs 4-6: invalid inference and concrete witnesses

Q4. Find the invalid inference steps

Consider the following argument with premise ∀x(P(x) ∨ Q(x)) and conclusion (∀x P(x)) ∧ (∀x Q(x))

(A) ∀x (P(x) ∨ Q(x)) | Premise

(B) P(c) ∨ Q(c) | Universal instantiation from (A)

(C) P(c) | Simplification from (B)

(D) ∀x P(x) | Universal Generalization of (C)

(E) Q(c) | Simplification from (B)

(F) ∀x Q(x) | Universal Generalization of (E)

(G) (∀x P(x)) ∧ (∀x Q(x)) | Conjunction of (D) and (F)

A. This is a valid argument

B. Steps (C) and (E) are not correct inferences

C. Steps (D) and (F) are not correct inferences

D. Step (G) is not a correct inference

Answer: B. A disjunction gives neither disjunct alone. On {a,b}, set P(a)=true, Q(a)=false and P(b)=false, Q(b)=true. The premise holds everywhere, but both universal conclusions fail.

Q5. Test four quantified claims over the reals

If universe of disclosure are all real numbers, then which of the following are true ?

(A) ∃x ∀y (x + y = y)

(B) ∀x ∀y (((x ≥ 0) ∧ (y < 0)) → (x - y > 0))

(C) ∃x ∃y (((x ≤ 0) ∧ (y ≤ 0)) ∧ (x - y > 0))

(D) ∀x ∀y ((x ≠ 0) ∧ (y ≠ 0) ↔ (xy ≠ 0))

Choose the correct answer from the options given below :

A. (A) and (B) Only

B. (A), (C) and (D) Only

C. (A), (B) and (D) Only

D. (A), (B) ,(C) and (D) Only

Answer: D. Choose x=0 for (A). In (B), x-y=x+(-y)>0. For (C), x=0,y=-1 gives x-y=1>0. Statement (D) is the real zero-product property in both directions. All four are true.

Q6. Choose true integer statements by constructing values

If the universe of disclosure is set of integers, then which of the followings are TRUE ?

(A) ∀n ∃m (n² < m)

(B) ∃n ∀m (n < m²)

(C) ∃n ∀m (n m = m)

(D) ∃n ∃m (n² + m² = 6)

(E) ∃n ∃m (n + m = 4 ∧ n − m = 1)

Choose the correct answer from the options given below :

A. (A), (B) and (C) Only

B. (B) and (C) Only

C. (C), (D) and (E) Only

D. (C) and (E) Only

Answer: A. Use m=n^2+1 for (A), n=-1 for (B), and n=1 for (C). Squares {0,1,4,9,...} cannot sum to 6, so (D) fails. Equation (E) gives (n,m)=(5/2,3/2), not integers.

Solved MCQs 7-10: equivalence, small models, implication, and divisibility

Q7. Test whether quantifiers distribute across an implication

Which predicate formula is NOT logically valid? W has no free occurrence of x.

A. ∀x(P(x) ∨ W) ≡ (∀x P(x)) ∨ W

B. ∃x(P(x) ∧ W) ≡ (∃x P(x)) ∧ W

C. ∀x(P(x) → W) ≡ (∀x P(x)) → W

D. ∃x(P(x) → W) ≡ (∀x P(x)) → W

Answer: C. Let the domain be {a,b}, let W be false, set P(a) true, and set P(b) false. The left side becomes ∀x ¬P(x), which is false, while the right side becomes ¬∀x P(x), which is true. In A and B, W can move outside because it has no free x; in D, both sides reduce to ∃x ¬P(x) ∨ W on a non-empty domain.

Q8. Bound the size of a model

Consider the first-order logic sentence

𝜑 ≡ ∃𝑠∃𝑡∃𝑢∀𝑣∀𝑤∀𝑥∀𝑦 𝜓(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦)

where 𝜓(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose 𝜑 has a model with a universe containing 7 elements.

Which one of the following statements is necessarily true?

A. There exists at least one model of 𝜑 with universe of size less than or equal to 3.

B. There exists no model of 𝜑 with universe of size less than or equal to 3.

C. There exists no model of 𝜑 with universe of size greater than 7.

D. Every model of 𝜑 has a universe of size equal to 7.

Answer: A. Let a,b,c be the existential witnesses. With no function symbols, restrict the model to the induced substructure on {a,b,c}; the universal suffix still holds. Its size is at most 3, or 1 or 2 if witnesses coincide.

Q9. Determine what follows from ∀x ∃y R(x,y)

Consider the first-order logic sentence F: ∀x(∃y R(x,y)). Assuming non-empty logical domains, which of the sentences below are implied by F ?

I. ∃y(∃x R(x,y))

II. ∃y(∀x R(x,y))

III. ∀y(∃x R(x,y))

IV. ¬∃x(∀y¬R(x,y))

A. IV only

B. I and IV only

C. II only

D. II and III only

Answer: B. A non-empty domain guarantees one related pair, so I follows. Quantifier-negation laws turn IV into F exactly. II demands one common y; III demands a preimage for every y. Neither follows.

Q10. Evaluate quantified divisibility statements

Let P(m,n) mean "m divides n", with both variables ranging over the positive integers. Determine the truth values:

(a) ∀m ∀n P(m,n)

(b) ∀n P(1,n)

(c) ∃m ∀n P(m,n)

A. (a) False, (b) True, (c) True

B. (a) True, (b) False, (c) False

C. (a) False, (b) False, (c) False

D. (a) True, (b) True, (c) True

Answer: A. Statement (a) is false because 2 does not divide 3. Statement (b) is true because every positive integer n equals 1 multiplied by n. Statement (c) is also true: m = 1 is a single witness that divides every positive integer.

Review and continue

For connective-heavy fundamentals and English translation, use Propositional and Predicate Logic MCQs: 12 solved questions with explanations. Quantifiers and Predicate Logic MCQs: 10 Practice Problems Explained owns distribution laws, uniqueness, English exceptions, and graph reachability. Quantifiers MCQs: 12 Solved Universal and Existential Questions focuses on translation, dependency, and quantifier movement. Here, the distinct practice is mathematical domains, invalid inference, small-model arguments, and divisibility.

Continue with GATE Guidance by Sanchit Sir or the wider GATE catalogue.