Negation of Quantified Statements

Negation of universal quantifier

Assume the statement $\forall x P(x)$, for some domain $D$. This statement asserts that every element of $D$ has the property $P$. By negation, we mean that it is not the case. If it is not the case that every element of $D$ has the property $P$, then there must be at least one element in $D$ that does not have the property $P$. That is,

$$\neg (\forall_{x\in D} P(x)) \equiv \exists_{y \in D} \neg P(y).$$

Similarly, the negation has the same effect for more than one universal quantifier. Again, with a generic domain $D$, assume the following statement:

$$\forall_{x\in D} \forall_{y\in D} \forall_{z\in D} P(x,y,z).$$

This statement asserts that for every selection of three elements $a,b,$ and $c$, from $D$, the predicate $P(a,b,c)$ is true. The negation of this statement means that it is not the case. This means there must be at least one selection of three elements $e,f,$ and $g$, such that $P(e,f,g)$ is not true. We can state this fact as follows:

$$\neg\left(\forall_{x\in D} \forall_{y\in D} \forall_{z\in D} P(x,y,z)\right) \equiv \exists_{x\in D} \exists_{y\in D} \exists_{z\in D} \neg P(x,y,z).$$

Let’s look at a few examples.

Examples

Let’s look at a few examples:

---

Assume the domain to be $M$, which is the set of all mammals. That is,

$M = \{x | x$ is a mammal.$\}$

---

Make a predicate as follows:

• $P(x)$: $x$ has four legs.

Quantify this predicate to make the following statement:

• $\forall x P(x)$: Every mammal has four legs.

The negation of this statement is as follows:

• $\neg\left(\forall x P(x)\right)$: It is not the case that every mammal has four legs.

The logical equivalent of this statement is as follows:

• $\exists x \neg P(x)$: There exists a mammal that does not have four legs.

---

Let’s make another predicate as follows:

• $F(x)$: $x$ can not fly.

---

Let’s universally quantify it for $M$.

• $\forall x F(x)$: No mammal can fly.

Negation of the above statement is as follows:

• $\neg (\forall x F(x))$: It is not the case that no mammal can fly.

The logical equivalent of this statement is as follows:

• $\exists x \neg F(x)$: There is a mammal that can fly:

Negation of existential quantifier

Assume the statement $\exists x P(x)$ for some domain $D$. This statement asserts that at least one element of $D$ has the property $P$. By negation, we mean that it is not the case. If it is not the case that even one element of $D$ has the property $P$, then that means no element in $D$ has the property $P$. That is,

$$\neg \left(\exists_{x\in D} P(x)\right) \equiv \forall_{y \in D} \neg P(y).$$

Similarly, the negation has the same effect for more than one existential quantifier. Again, with a generic domain $D$, assume the following statement:

$$\exists_{x\in D} \exists_{y\in D} \exists_{z\in D} P(x,y,z).$$

This statement asserts that there is at least one selection of three elements $a,b,$ and $c$, from $D$, such that predicate $P(a,b,c)$ is true. The negation of this statement means that it is not the case. This means that there is no selection of three elements $e,f,$ and $g$, such that $P(e,f,g)$ is true. We can state this fact as follows:

$$\neg\left(\exists_{x\in D} \exists_{y\in D} \exists_{z\in D} P(x,y,z)\right) \equiv \forall_{x\in D} \forall_{y\in D} \forall_{z\in D} \neg P(x,y,z).$$

Examples

Let’s look at a few examples.

---

Assume the domain to be $S$, the set of Mathematical Logic students.

• $S=\{x| x$ is a student of Mathematical Logic$\}.$

---

Make a predicate as follows:

• $P(x)$: $x$ can not learn Mathematical Logic.

Quantify this predicate to make the following statement:

• $\exists x P(x)$: There exists a student who can not learn Mathematical Logic.

The negation of the above statement is as follows:

• $\neg(\exists x P(x))$: It is not the case that there exists a student who can not learn Mathematical Logic.

We can simplify the English translation as follows:

• $\neg(\exists x P(x))$: There is no student who can not learn Mathematical Logic.

The logical equivalent of the above statement is as follows:

• $\forall x \neg P(x)$: Every student can learn Mathematical Logic.

---

Consider another domain set, $D$, the set of all ducks.

• $D=\{x|x$ is a duck$\}.$

---

Let’s make a predicate as follows:

• $Q(y)$: $y$ eats green leaves.

Quantify this predicate to make the following statement:

• $\exists y Q(y)$: At least one duck eats green leaves.

The negation of this statement is as follows:

• $\neg (\exists y Q(y))$: It is not the case that at least one duck eats green leaves.

We can simplify the English translation as follows:

• $\neg (\exists y Q(y))$: No duck eats green leaves.

The logical equivalent of this statement is as follows:

• $\forall y\neg Q(y)$: Ducks do not eat green leaves.

DeMorgan’s laws for negating quantified statements

Recall the generalized DeMorgan’s laws in propositional logic; it is as follows:

$$\neg \bigwedge_{i=1}^n q_i \equiv \bigvee_{i=1}^n \neg q_i.$$

and

$$\neg \bigvee_{i=1}^n q_i \equiv \bigwedge_{i=1}^n \neg q_i.$$

Consider, $s$, a universally quantified predicate, $P$, for a domain, $D$, having $n$ elements.

$$s = \forall x P(x).$$

Also, consider $r$ to be an existentially quantified predicate.

$$r = \exists xP(x).$$

As the variable $x$ can have $1$ to $n$ different values from the domain, we can write $s$ as follows.

$$\forall x P(x) \equiv P(1)\land P(2)\land P(3)\land \ldots \land P(n).$$

That is,

$$s = \forall x P(x) \equiv \bigwedge_{i=1}^n P(i).$$

Similarly,

$$\exists x P(x) \equiv P(1)\lor P(2)\lor P(3)\lor \ldots \lor P(n).$$

That is,

$$r = \exists x P(x) \equiv \bigvee_{i=1}^n P(i).$$

If we want to negate the universal quantifier, we can see DeMorgan’s law in action.

$$\neg s \equiv \neg \bigwedge_{i=1}^n P(i).$$

Applying generalized DeMorgan’s law on the right-hand side of the above equivalence, we get.

$$\neg s \equiv \bigvee_{i=1}^n \neg P(i).$$

On the right-hand side of the above equivalence, we can see the existential quantifier in the form of a big disjunction. Therefore,

$$\neg \forall x P(x) \equiv \exists x \neg P(x).$$

Now, let’s see how DeMorgan’s laws help us to negate existential quantifiers.

$$\neg r \equiv \neg \bigvee_{i=1}^n P(i).$$

Applying generalized DeMorgan’s law on the right-hand side of the above equivalence, we get.

$$\neg r \equiv \bigwedge_{i=1}^n \neg P(i).$$

On the right-hand side of the above equivalence, we can see the universal quantifier in the form of a big conjunction. Therefore,

$$\neg \exists x P(x) \equiv \forall x \neg P(x).$$

We’ll summarize these results in the following table:

$\neg \forall x P(x)$	$\equiv$	$\exists x \neg P(x)$
$\neg \exists x P(x)$	$\equiv$	$\forall x \neg P(x)$