[Math] What are the rules for negating quantifiers in propositional logic in general, is the “NOT” distributive

logicpredicate-logicquantifiers

I was wondering what the general rules for negating quantifiers was.

I was reading that they follow this rule holds:

$$NOT(\forall x. P(x)) \iff \exists x. NOT(P(x))$$

Which makes sense to me. However, I was worried that if there are more and more predicates and quantifiers involved in the negation, that we have to be extra careful about negating the statement and that its not as simple as just "distributing" the NOT.

For example is just "distributing" the NOT over all predicates and quantifiers really negates a statement correct?

Consider this example:

$$NOT( \exists x. P(x). \forall y. P(x,y). \exists z \exists k. P(z,k)) \iff \forall x. NOT(P(x)). \exists y. NOT(P(x,y)). \forall z \forall k. NOT(P(z,k))$$

Basically, is it safe to just distribute the NOT across all quantifiers and predicates when trying to negate a more general proposition? The order of the statements in the proposition never change when we negate, right? Is there some intuitive proof that distribution of not works for negating a proposition? Why is "distributing" the not correct? Or maybe someone could make the rule precise to me, its not clear to me how to do it for an arbitrary proposition with crazy mixtures of quantifiers and predicates.

Best Answer

The formula :

$NOT(∃x.P(x).∀y.P(x,y).∃z∃k.P(z,k))$

is not correctly written; the issue is not with the dots after the quantifiers; we can delete them and we have still an "un-grammatical" formuala :

$NOT(∃xP(x).∀yP(x,y).∃z∃kP(z,k))$.

The formula is meaningless exactly as is meaningless the natural language expression :

"there exist a prime number all prime numbers are ..."

$∃xP(x)$ is a formula correctly written; thus it can be part of a more complex formula containing also the formula $∀yP(x,y)$ only if there is a connective : $\land, \lor, \rightarrow, \leftrightarrow$ "joining" them.

Having said that, the basic rules for managing the quantifiers are :

$\forall \lnot$ is equivalent to : $\lnot \exists$

$\lnot \forall$ is equivalent to : $\exists \lnot$.

Thus, your example :

$NOT(∀xP(x)) \leftrightarrow ∃x NOT(P(x))$

is correct.

With more "complex" formulae, like e.g. :

$NOT (∀xP(x) \lor ∃y Q(y))$

we have, by De Morgan's laws :

$NOT (∀xP(x)) \land NOT (∃y Q(y)) \leftrightarrow \exists x NOT P(x) \land \forall y NOT Q(y)$.

Examples from your courseware are :

$∀n ∈ Evens ∃p ∈ Primes ∃q ∈ Primes (n = p + q)$ [page 75]

all the quantifers prefix a formula (a "matrix") and the scope of all three quantifiers is the formula : $(n = p + q)$.

Thus, its negation will be :

$\lnot (∀n ∃p ∃q (n = p + q)) \leftrightarrow ∃n \lnot (∃p ∃q (n = p + q)) \leftrightarrow \ldots \leftrightarrow ∃n ∀p ∀q \lnot (n = p + q)$.

In the case of :

$∃x∀yP(x, y) \rightarrow ∀y∃xP(x, y)$ [page 77]

we have two sub-formulae : $∃x∀yP(x, y)$ and $∀y∃xP(x, y)$ "joined" by the connective : $\rightarrow$ (IMPLIES).

Here we have to apply first the rule for the negation of a formula with $\rightarrow$, i.e. : $\lnot (p \rightarrow q)$ is equivalent to : $p \land \lnot q$, in order to "move inside" the negation sign, followed by the rules for the negation of quantifiers.

Thus :

$\lnot (∃x∀yP(x, y) \rightarrow ∀y∃xP(x, y)) \leftrightarrow ((∃x∀yP(x, y) \land \lnot ∀y∃xP(x, y)) \leftrightarrow ((∃x∀yP(x, y) \land ∃y∀x \lnot P(x, y))$

Related Question