Negating Logical Expressions - Mathematical Sentences

Mathematical Writing - Vivaldi Franco 2014

Negating Logical Expressions
Mathematical Sentences

If $${\fancyscript{L}}$$ is a logical expression, then its negation is $$\lnot {\fancyscript{L}}$$, which is false if $${\fancyscript{L}}$$ is true and vice-versa. Relational expressions are negated by crossing out the operator with a forward slash—see (4.3) and (4.5), Sect. 4.1. The only exceptions are the inequalities, whose negations have dedicated symbols. $$\square $$

Theorem 4.1 provides the negation formulae for the main compound expressions

$$\begin{aligned} \lnot (P\wedge Q)&\Leftrightarrow \lnot P \vee \lnot Q\nonumber \\ \lnot (P\vee Q)&\Leftrightarrow \lnot P \wedge \lnot Q\\ \lnot (P\Rightarrow Q)&\Leftrightarrow P\wedge \lnot Q.\nonumber \end{aligned}$$

(4.26)

The first two formulae are items (i) and (ii) of the theorem (de Morgan’s laws); the third follows immediately from (iii) and (i). Note that the negation of an implication does not have the form of an implication.

If $${\fancyscript{L}}$$ is an expression with quantifiers and boolean operators, then the expression $$\lnot {\fancyscript{L}}$$ unfolds into an equivalent expression which we seek to determine. The following sentences contain a negation and a universal quantifier:

Not all polynomials have real roots. A square matrix is not necessarily invertible.

We recognise that these are disguised existence statements:

There is a polynomial with no real roots. There is a square matrix which is not invertible.

The following theorem confirms this observation.

Theorem 4.3

Let $${\fancyscript{P}}$$ be a predicate on a set $$A$$, and let

$$ {\fancyscript{L}}\,{:=}\,\forall x\in A,\, {\fancyscript{P}}(x) \quad \qquad {\fancyscript{M}}\,{:=}\,\exists x\in A,\, {\fancyscript{P}}(x). $$

Then

$$\begin{aligned} \lnot {\fancyscript{L}}\,\Leftrightarrow \,\exists x\in A,\, \lnot {\fancyscript{P}}(x) \quad \qquad \lnot {\fancyscript{M}}\,\Leftrightarrow \,\forall x\in A,\, \lnot {\fancyscript{P}}(x). \end{aligned}$$

(4.27)

PROOF. From (4.21), we have the boolean equivalence

$$ {\fancyscript{L}}\,\Leftrightarrow \,{\fancyscript{P}}(A)=\{{\textsc {t}}\} $$

where $${\fancyscript{P}}(A)$$ is the image of $$A$$ under $${\fancyscript{P}}$$ (see Sect. 2.2). But then

$$ \lnot {\fancyscript{L}}\,\Leftrightarrow \,{\fancyscript{P}}(A)\ne \{{\textsc {t}}\}\, \Leftrightarrow \, \lnot {\fancyscript{P}}(A)\ne \{{\textsc {f}}\}. $$

Using again (4.21), we obtain

$$ \lnot {\fancyscript{L}}\,\Leftrightarrow \,\exists x\in A,\,\,\lnot {\fancyscript{P}}(x) $$

as claimed.

The second formula is proved similarly—see exercises. $$\square $$

It’s now easy to deduce the rule for negating expressions with two or more quantifiers. Let $${\fancyscript{P}}$$ be a predicate on $$A\times B$$, and let us consider the expression

$$ {\fancyscript{L}}:=\forall x\in A,\,\,\exists y\in B,\,\,{\fancyscript{P}}(x,y). $$

Repeated applications of Theorem 4.3 give

$$\begin{aligned} \lnot {\fancyscript{L}}&\Leftrightarrow \lnot \bigl (\forall x\in A,\,\,(\exists y\in B,\,\,{\fancyscript{P}}(x,y))\bigr )\\&\Leftrightarrow \exists x\in A,\,\,\lnot (\exists y\in B,\,\,{\fancyscript{P}}(x,y))\\&\Leftrightarrow \exists x\in A,\,\,\forall y\in B,\,\,\lnot {\fancyscript{P}}(x,y). \end{aligned}$$

It should be clear how similar formulae may be derived, having any combination of two quantifiers.

Finally, we consider the case of an arbitrary sequence of quantifiers, e.g.,

$$ {\fancyscript{L}}\,=\,\forall x_1\in X_1,\,\,\exists x_2\in X_2,\ldots ,\forall x_n\in X_n, \,\,{\fancyscript{P}}(x_1,\ldots ,x_n) $$

where the $$X_i$$ are sets, and $${\fancyscript{P}}$$ is a predicate on the cartesian product $$X_1\,\times \,X_2\,\times \,\cdots \times X_n$$. Parentheses make it clear that this is a nested array of predicates:

$$ {\fancyscript{L}}\,=\,\forall x_1\in X_1,\,\,(\,\exists x_2\in X_2,\,\,(\ldots ,(\forall x_n\in X_n, \,\,{\fancyscript{P}}(x_1,\ldots ,x_n)))). $$

Repeatedly applying Theorem 4.3, from the outside to the inside, we obtain

$$ \lnot {\fancyscript{L}}\Leftrightarrow \exists \, x_1\in X_1,\,\,\forall x_2\in X_2,\ldots ,\exists x_n\in X_n,\,\,\lnot {\fancyscript{P}}(x_1,\ldots ,x_n). $$

Namely, the negation of $${\fancyscript{L}}$$ is obtained by replacing each $$\forall $$ with $$\exists $$, and vice-versa, without changing their order, and then replacing $${\fancyscript{P}}$$ with $$\lnot {\fancyscript{P}}$$. A formal proof requires the principle of induction (see Chap. 8).

EXAMPLE. The statement

$$\begin{aligned} \forall n,a,b\in \mathbb {Z},\,\,(n|ab)\Rightarrow (n|a \vee n|b) \end{aligned}$$

(4.28)

is false (why?). We negate it using Theorem 4.3, obtaining a true statement:

$$ \exists n,a,b\in \mathbb {Z},\,\,(n|ab)\wedge (n\not |\,a \wedge n\not |\,b). $$

EXAMPLE. Lagrange’s theorem, expressed symbolically in Eq. (4.25), would be false if four squares were replaced by three squares. This fact is written symbolically as

$$ \exists n\in \mathbb {N},\,\,\forall a,b,c\in \mathbb {Z}, \,\,n\not =a^2+b^2+c^2. $$

In words:

There is a natural number which cannot be written as the sum of three squares.