Negation of Quantifiers: Rules, Worked Examples and Exam Traps

Learn a mechanical way to negate universal, existential and nested quantifiers. Worked finite-domain examples show how to preserve scope and verify the result.

KnowledgeGate Team

Exam prep & CS education

Updated 5 Nov 20266 min read
Negation of Quantifiers: Rules, Worked Examples and Exam Traps

A common mistake is to change forall to exists but forget to negate the predicate. Another is to read "not everyone" as "no one", although those claims are very different. A mechanical method translates plain English into nested quantifiers, and each step can be audited line by line. It fits into the wider GATE preparation context without requiring guesswork or memorised shortcuts.

Quantifiers make claims over a domain

A quantifier tells you how many values must satisfy a predicate. The expression forall x in D, P(x) claims that P(x) survives every value in the stated domain. The expression exists x in D, P(x) needs at least one value, called a witness, for which the predicate is true.

Let D = {1, 2, 3, 4} and let P(x) mean "x is even". Then forall x in D, P(x) is false because x = 1 is a counterexample. In contrast, exists x in D, P(x) is true because x = 2 is a witness.

Negation reverses this burden of proof. One counterexample defeats a universal claim, while defeating an existential claim requires failure for every value. The domain is part of the meaning, not decoration. Propositional and Predicate Logic: Truth Tables and Quantifiers establishes the broader connective and quantifier framework. Negation adds a narrower task: preserve the domain and variable order while each crossed quantifier flips and the complete predicate is negated.

The two negation laws and the inside-out rule

The two basic laws are:

  • not(forall x, P(x)) is equivalent to exists x, not P(x). In words, "not every" means "at least one does not".

  • not(exists x, P(x)) is equivalent to forall x, not P(x). In words, "there is no" means "every candidate fails".

For a bounded domain, write the laws as:

  • not(forall x in D, P(x)) = exists x in D, not P(x)

  • not(exists x in D, P(x)) = forall x in D, not P(x)

Use the same mechanical process every time: preserve the domain, move the negation one layer inward, flip the quantifier you cross, and negate the entire predicate within its original scope. For nested statements, repeat the process one layer at a time.

Flip each quantifier you cross, then negate what remains.

This mnemonic does not allow you to change the domain or drop parentheses. Those details determine which variables and connectives the negation controls.

Fully worked example: negate and evaluate a nested statement

Flow showing nested quantifier negation and x = 1 counterexample for x + y = 6.

Take D = {1, 2, 3, 4} and define

S = forall x in D, exists y in D such that x + y = 6.

Negate it one layer at a time. First cross the outer universal quantifier:

not S = exists x in D, not(exists y in D, x + y = 6).

Now cross the inner existential quantifier:

not S = exists x in D, forall y in D, x + y != 6.

All three required changes are visible. The outer forall becomes exists, the inner exists becomes forall, and the equality = becomes the inequality !=.

Now evaluate the original statement. For x = 1, test every permitted value of y:

  • 1 + 1 = 2

  • 1 + 2 = 3

  • 1 + 3 = 4

  • 1 + 4 = 5

No allowed y makes the sum 6. Therefore the original universal statement S is false.

A universal statement needs a successful y for every x. Once x = 1 fails, the values x = 2, x = 3, and x = 4 cannot repair the claim, even though each has a suitable partner.

Evaluate the negation using the same row. The value x = 1 is a witness because every allowed y produces a sum unequal to 6. Therefore not S is true. The truth values are exact opposites, as logical negation requires. Keeping the intermediate expression makes it possible to audit which quantifier each negation crossed.

Sum table of x + y for x and y in {1, 2, 3, 4}, with the x = 1 row marked as the counterexample and the cells equal to 6 highlighted.

Apply the rule when the predicate contains connectives

Quantifier flipping is only the outer part of the job. You must also negate the complete predicate correctly.

Let U = {Asha, Bharat, Charu}. Asha solved Q1 but not Q2, Bharat solved both, and Charu solved neither. Consider:

forall s in U, SolvedQ1(s) or SolvedQ2(s).

Its negation is:

exists s in U, not SolvedQ1(s) and not SolvedQ2(s).

The or becomes and by De Morgan's law. Charu is a witness for the negation, so the universal statement is false and its negation is true. Asha and Bharat are not witnesses because each solved at least one question.

Now consider an implication:

I = forall n in {1, 2, 3, 4}, Even(n) implies Even(n^2).

Since not(A implies B) = A and not B, its negation is:

not I = exists n in {1, 2, 3, 4}, Even(n) and not Even(n^2).

Only n = 2 and n = 4 can satisfy the first part. But 2^2 = 4 and 4^2 = 16, and both results are even. No witness exists for not I, so I is true.

Negation preserves quantifier order

Let D = {1, 2, 3} and let R(x, y) mean x != y. The statement forall x, exists y, R(x, y) is true. Choose y = 2 for x = 1, and choose y = 1 for x = 2 or x = 3. The witness may vary with x.

Reverse the quantifier order. The statement exists y, forall x, R(x, y) is false because any fixed y fails when x = y. For y = 1, x = 1 is a counterexample; the same failure occurs for y = 2 and y = 3.

Negate each statement without reordering it by intuition:

  • not(forall x, exists y, x != y) = exists x, forall y, x = y

  • not(exists y, forall x, x != y) = forall y, exists x, x = y

The first negation is false because no single x equals every y. The second is true because, for each y, choosing x = y supplies a witness. Both truth values are exact opposites of the original statements. The variables remain in their original left-to-right positions while each quantifier type flips.

Four traps and their repairs

These four incorrect transformations all come from changing only part of the statement.

Trap

Wrong

Right

Universal quantifier

not(forall x, P) becomes forall x, not P

exists x, not P

Existential quantifier

not(exists x, P) becomes exists x, not P

forall x, not P

Disjunction

not(P or Q) becomes not P or not Q

not P and not Q

Implication

not(P implies Q) becomes not P implies not Q

P and not Q

Two more checks prevent scope errors. Retain the same domain, and parenthesise the complete predicate before negating it. In the nested worked example, x = 1 is the counterexample that catches an incorrect formula. The correct negation must accept x = 1 as a witness for forall y in D, x + y != 6.

How assessment questions test the idea

An assessment can ask you to choose an equivalent negation, translate an English sentence, evaluate truth over a finite domain, or find a witness or counterexample for nested quantifiers. The surface wording changes, but the logic does not.

Use this quick scratch method:

  1. Box the domain.

  2. Underline the quantifiers in order.

  3. Flip each quantifier as the negation crosses it.

  4. Push the negation through and, or, or implication.

  5. Test the result with one concrete witness or a complete finite-domain check.

Apply the method to the solved Discrete Mathematics Propositional Logic MCQs, then use the GATE Test Series as a broader testing step.

The short version and next step

not forall becomes exists not. not exists becomes forall not. In a nested statement, flip quantifiers one by one without changing their order. On D = {1, 2, 3, 4}, x = 1 defeats forall x exists y, x + y = 6 because no allowed y completes the sum.

For the full subject sequence, continue with GATE Guidance by Sanchit Sir, then practise negating nested quantifier statements until each flip is automatic.