Quantifiers and Predicate Logic Practice Problems: Step-by-Step Solutions

A formula containing ∀, ∃, implication and negation can look familiar, yet one changed quantifier order or one misplaced not can reverse its truth value. The reliable method is to fix the domain, translate the sentence, build the predicate rows, find a witness or counterexample, and only then decide whether the formula is true or false.

Related reading: quantifier MCQs and universal and existential quantifiers.

Quantifiers and predicate logic: the minimum toolkit before practice

A predicate P(x) is an open sentence whose truth depends on x; the domain supplies its allowed values. x is free in P(x) and bound in ∀x P(x) or ∃x P(x). ∀x P(x) needs every value; ∃x P(x) needs one witness.

Let D={-1,0,1} and P(x): x^2=x. P(0) and P(1) are true, but P(-1) is false because 1 != -1. Thus ∃x P(x) is true with witnesses 0 and 1, while ∀x P(x) is false with counterexample -1.

The Propositional and Predicate Logic: Truth Tables to Proofs develops truth tables and proof concepts; quantified-formula practice applies those ideas to witnesses, counterexamples and nested scopes. The topic sits within GATE CS Exam Preparation.

Translate English into quantified formulas without changing the claim

Fix this classroom universe. People are Asha and Bharat; logic problems are p1 and p2. Student(x), LogicProblem(y) and Solves(x,y) have their ordinary meanings, with:

Solves={(Asha,p1),(Asha,p2),(Bharat,p1)}

• "Every student solved at least one logic problem" is ∀x(Student(x) -> ∃y(LogicProblem(y) and Solves(x,y))). True: Asha and Bharat each have a witness.

• "Some student solved every logic problem" is ∃x(Student(x) and ∀y(LogicProblem(y) -> Solves(x,y))). True, with Asha as witness.

• "Every student solved every logic problem" is ∀x(Student(x) -> ∀y(LogicProblem(y) -> Solves(x,y))). False because (Bharat,p2) is absent.

Implication restricts a universal claim to students or problems; conjunction identifies an object selected existentially. Keep the parentheses visible. Moving ∃y before ∀x asks for one common problem solved by every student, a different statement.

Fully worked finite-domain problem: evaluate three formulas row by row

Let D={-2,-1,0,1,2}, P(x): x^2 <= 1, and Q(x): x+1 > 0. Evaluate A=∀x(P(x) -> Q(x)), B=∃x(P(x) and not Q(x)), and C=∀x(P(x) or Q(x)).

Read each formula's column. A is false because x=-1 counters P -> Q. B is true because x=-1 witnesses P and not Q. C is false because x=-2 counters P or Q.

Reverse-check x=-2: a false antecedent makes P -> Q true, but the row still has P(x)=F, so it gives no witness for P.

Nested quantifiers: why the order of ∀ and ∃ matters

Use D={1,2,3} for both variables and define R(x,y): x+y=4. The true ordered pairs are exactly {(1,3),(2,2),(3,1)}.

For ∀x∃y R(x,y), choose y=3 for x=1, y=2 for x=2, and y=1 for x=3. It is true because the witness may depend on x. ∃y∀x R(x,y) is false: y=1 works only with x=3, y=2 only with x=2, and y=3 only with x=1. Reordering quantifiers is not algebraic rearrangement.

Over the integers, ∀x∃y(y=x+1) is true by choosing a new y for each x. ∃y∀x(y=x+1) is false because one integer cannot equal every integer's successor.

Negate quantified statements by moving inward one layer at a time

Use two switches: not ∀x P(x) equals ∃x not P(x), and not ∃x P(x) equals ∀x not P(x). When not crosses a quantifier, switch it. Across and or or, apply De Morgan's law. Negate comparisons exactly: not(x>3) becomes x<=3.

Negate the first classroom claim step by step:

not ∀x(Student(x) -> ∃y(LogicProblem(y) and Solves(x,y)))

= ∃x not(Student(x) -> ∃y(LogicProblem(y) and Solves(x,y)))

= ∃x(Student(x) and not ∃y(LogicProblem(y) and Solves(x,y)))

= ∃x(Student(x) and ∀y not(LogicProblem(y) and Solves(x,y)))

= ∃x(Student(x) and ∀y(LogicProblem(y) -> not Solves(x,y)))

This says some student solved no logic problem. It is false because both solved p1. Remove (Bharat,p1), and it becomes true with Bharat as witness.

"Not every student solved p2" is ∃x(Student(x) and not Solves(x,p2)); "no student solved p2" is ∀x(Student(x) -> not Solves(x,p2)). The first is true because Bharat did not; the second is false because Asha did.

Common traps: implication, vacuous truth, scope and counterexamples

For vacuous truth, let D={-3,-1,1}, with Even(x) meaning x is even. ∀x(Even(x) -> x>0) is true because no value is even, although -3 and -1 are not positive. ∃x(Even(x) and x>0) is false because no even witness exists.

• To prove ∀, cover every value or argue generally.

• To disprove ∀, give one counterexample.

• To prove ∃, give one witness.

• To disprove ∃, rule out every value.

Practise Implication and Biconditional Operators in Logic for the connective behind vacuous truth.

Representative exam-style practice and a five-question self-check

Question families include translation, finite-domain evaluation, nested negation, quantifier-order comparison, witness or counterexample search, and equivalence. Try these before reading the answers.

1. Over D={0,1,2}, is ∀x(x^2=x) true?

2. Over the same domain, is ∃x(x^2=2x) true?

3. Negate ∃x∀y R(x,y).

4. Over the integers, compare ∀x∃y(y=x+1) and ∃y∀x(y=x+1).

5. Write "No integer is both even and odd" with quantifiers.

Answers: (1) false, with counterexample 2; (2) true, with witnesses 0 and 2; (3) ∀x∃y not R(x,y); (4) the first is true and the second is false; (5) not ∃x(Even(x) and Odd(x)), equivalently ∀x(Even(x) -> not Odd(x)).

Continue with Propositional and Predicate Logic MCQs: 12 Solved, then use the GATE Test Series for timed practice.

Quantifiers and predicate logic: the short version and next step

• Write the domain.

• Mark each quantifier's scope.

• Translate restrictions with the correct guard.

• Build rows or relation pairs.

• Search for a witness or counterexample.

• Negate by switching quantifiers and pushing not inward.

Reproduce three checkpoints: A=false, B=true, C=false; {(1,3),(2,2),(3,1)} for x+y=4; and why ∀x∃y R(x,y) is true while ∃y∀x R(x,y) is false.

Rebuild the five-value grid without looking, then change Q(x) to x+1>=0. Only the x=-1 row changes: Q becomes true, so A=true, B=false, C=false.