If $P$ is some sentence or formula, then $\lnot P$ is called the denial of $P$. The ability to manipulate the denial of a formula accurately is critical to understanding mathematical arguments. The following tautologies are referred to as De Morgan's laws: \eqalign{ \lnot (P\lor Q)&\iff (\lnot P\land \lnot Q)\cr \lnot (P\land Q)&\iff (\lnot P\lor \lnot Q)\cr} These are easy to verify using truth tables, but with a little thought, they are not hard to understand directly. The first says that the only way that $P\lor Q$ can fail to be true is if both $P$ and $Q$ fail to be true. For example, the statements "I don't like chocolate or vanilla'' and "I do not like chocolate and I do not like vanilla'' clearly express the same thought. For a more mathematical example of the second tautology, consider "$x$ is not between 2 and 3.'' This can be written symbolically as $\lnot((2< x)\land (x< 3))$, and clearly is equivalent to $\lnot (2< x) \lor \lnot (x< 3),$ that is, $(x\le 2) \lor (3\le x).$

We can also use De Morgan's laws to simplify the denial of $P\implies Q$: \eqalign{\lnot (P\implies Q) & \iff \lnot (\lnot P\lor Q)\cr & \iff (\lnot\lnot P)\land (\lnot Q)\cr & \iff P\land \lnot Q\cr} so the denial of $P\implies Q$ is $P\land \lnot Q$. In other words, it is not the case that $P$ implies $Q$ if and only if $P$ is true and $Q$ is false. Of course, this agrees with the truth table for $P\implies Q$ that we have already seen.

There are versions of De Morgan's laws for quantifiers: \eqalign{ \lnot \forall x\,P(x) &\iff \exists x\,\lnot P(x)\cr \lnot \exists x\,P(x) &\iff \forall x\,\lnot P(x)\cr} You may be able to see that these are true immediately. If not, here is an explanation of $\lnot \forall x\,P(x)\implies \exists x\,\lnot P(x)$ that should be convincing: If $\lnot \forall x\,P(x)$, then $P(x)$ is not true for every $x$, which is to say that for some value $a$, $P(a)$ is not true. This means that $\lnot P(a)$ is true. Since $\lnot P(a)$ is true, it is certainly the case that there is some value of $x$ that makes $\lnot P(x)$ true, which is to say that $\exists x\,\lnot P(x)$ is true. The other three implications may be explained in a similar way.

Here is another way to think of the quantifier versions of De Morgan's laws. The statement $\forall x\,P(x)$ is very much like a big conjunction. If the universe of discourse is the positive integers, for example, then it is equivalent to the statement that $$P(1)\land P(2)\land P(3)\land \cdots$$ or, more concisely, we might write $$\bigwedge_{x\in U} P(x),$$ using notation similar to "sigma notation'' for sums. Of course, this is not really a "statement'' in our official mathematical logic, because we don't allow infinitely long formulas. In the same way, $\exists x\,P(x)$ can be thought of as $$\bigvee_{x\in U} P(x).$$ Now the first quantifier law can be written $$\lnot\bigwedge_{x\in U} P(x) \iff \bigvee_{x\in U} (\lnot P(x)),$$ which looks very much like the law $$\lnot (P\land Q)\iff (\lnot P\lor \lnot Q),$$ but with an infinite conjunction and disjunction. Note that we can also rewrite De Morgan's laws for $\land$ and $\lor$ as \eqalign{ \lnot \bigwedge_{i=1}^2 (P_i(x)) &\iff \bigvee_{i=1}^2 (\lnot P_i(x))\cr \lnot \bigvee_{i=1}^2 (P_i(x)) &\iff \bigwedge_{i=1}^2 (\lnot P_i(x)).\cr} This is more cumbersome, but it reflects the close relationship with the quantifier forms of De Morgan's laws.

Finally, general understanding is usually aided by specific examples: Suppose the universe is the set of cars. If $P(x)$ is "$x$ has four wheel drive,'' then the denial of "every car has four wheel drive'' is "there exists a car which does not have four wheel drive.'' This is an example of the first law. If $P(x)$ is "$x$ has three wheels,'' then the denial of "there is a car with three wheels'' is "every car does not have three wheels.'' This fits the pattern of the second law. In a more mathematical vein, a denial of the sentence "for every $x$, $x^2$ is positive'' is "there is an $x$ such that $x^2$ fails to be positive.'' A denial of "there is an $x$ such that $x^2=-1$'' is "for every $x$, $x^2\ne -1$.''

It is easy to confuse the denial of a sentence with something stronger. If the universe is the set of all people, the denial of the sentence "All people are tall'' is not the sentence "No people are tall.'' This might be called the opposite of the original sentence—it says more than simply "All people are tall' is untrue.'' The correct denial of this sentence is "there is someone who is not tall,'' which is a considerably weaker statement. In symbols, the denial of $\forall x P(x)$ is $\exists x\ \lnot P(x)$, whereas the opposite is $\forall x \lnot P(x)$. ("Denial'' is an "official'' term in wide use; "opposite,'' as used here, is not widely used.)

De Morgan's laws can be used to simplify negations of the "some'' form and the "all'' form; the negations themselves turn out to have the same forms, but "reversed,'' that is, the negation of an "all'' form is a "some'' form, and vice versa. Suppose $P(x)$ and $Q(x)$ are formulas. We then have $$\lnot \forall x (P(x)\implies Q(x)) \iff\ \exists x (P(x) \land \lnot Q(x))$$ $$\lnot \exists x (P(x)\land Q(x) ) \iff\ \forall x (P(x)\implies \lnot Q(x))$$ The denial of the sentence "all lawn mowers run on gasoline'' is the sentence "some lawn mower does not run on gasoline'' (not "no lawn mowers run on gasoline,'' the opposite). We verify the first statement and leave the second for an exercise: $$\lnot \forall x (P(x)\implies Q(x)) \iff \exists x \lnot(P(x)\implies Q(x)) \iff \exists x (P(x) \land \lnot Q(x))$$

A formula is usually simpler if $\lnot$ does not appear in front of any compound expression, that is, it appears only in front of simple statements such as $P(x)$. The following is an example of simplifying the denial of a formula using De Morgan's laws: \eqalign{ \lnot \forall x (P(x)\lor \lnot Q(x))&\iff \exists x \lnot(P(x)\lor \lnot Q(x))\cr &\iff\exists x (\lnot P(x)\land \lnot \lnot Q(x))\cr &\iff\exists x (\lnot P(x)\land Q(x)) \cr} Denials of formulas are extremely useful. In a later section we will see that the techniques called proof by contradiction and proof by contrapositive use them extensively. Denials can also be a helpful study device. When you read a theorem or a definition in mathematics it is frequently helpful to form the denial of that sentence to see what it means for the condition to fail. The more ways you think about a concept in mathematics, the clearer it should become.

Augustus De Morgan. ($y$–1871; De Morgan himself noted that he was $x$ years old in the year $x^2$.) De Morgan's father died when he was ten, after which he was raised by his mother, a devout member of the Church of England, who wanted him to be a minister. Far from becoming a minister, De Morgan developed a pronounced antipathy toward the Church, which would profoundly influence the course of his career.

De Morgan's interest in and talent for mathematics did not become evident until he was fourteen, but already at sixteen he entered Trinity College at Cambridge, where he studied algebra under George Peacock and logic under William Whewell. He was also an excellent flute player, and became prominent in musical clubs at Cambridge.

On graduation, De Morgan was unable to secure a position at Oxford or Cambridge, as he refused to sign the required religious test (a test not abolished until 1875). Instead, at the age of 22, he became Professor of Mathematics at London University, a new institution founded on the principle of religious neutrality.

De Morgan wrote prolifically about algebra and logic. Peacock and Gregory had already focused attention on the fundamental importance to algebra of symbol manipulation; that is, they established that the fundamental operations of algebra need not depend on the interpretation of the variables. De Morgan went one (big) step further: he recognized that the operations ($+$, $-$, etc.) also need have no fixed meaning (though he made an exception for equality). Despite this view, De Morgan does seem to have thought that the only appropriate interpretations for algebra were familiar numerical domains, primarily the real and complex numbers. Indeed, he thought that the complex numbers formed the most general possible algebra, because he could not bring himself to abandon the familiar algebraic properties of the real and complex numbers, like commutativity.

One of De Morgan's most widely known books was A Budget of Paradoxes. He used the word paradox' to mean anything outside the accepted wisdom of a subject. Though this need not be interpreted pejoratively, his examples were in fact of the mathematical crank' variety—mathematically naive people who insisted that they could trisect the angle or square the circle, for example.

De Morgan's son George was himself a distinguished mathematician. With a friend, he founded the London Mathematical Society and served as its first secretary; De Morgan was the first president.

In 1866, De Morgan resigned his position to protest an appointment that was made on religious grounds, which De Morgan thought abused the principle of religious neutrality on which London University was founded. Two years later his son George died, and shortly thereafter a daughter died. His own death perhaps hastened by these events, De Morgan died in 1871 of nervous prostration.'

The information here is taken from Lectures on Ten British Mathematicians, by Alexander Macfarlane, New York: John Wiley & Sons, 1916.

## Exercises 1.3

Ex 1.3.1 Verify these tautologies using truth tables. $$\lnot (P\lor Q)\iff (\lnot P\land \lnot Q)$$ $$\lnot (P\land Q)\iff (\lnot P\lor \lnot Q)$$

Ex 1.3.2 Suppose $R(x)$ is the statement "$x$ is a rectangle,'' and $S(x)$ is the statement "$x$ is a square.'' Write the following symbolically and decide which pairs of statements are denials of each other:

a) All rectangles are squares.

b) Some rectangles are squares.

c) Some squares are not rectangles.

d) No squares are rectangles.

e) No rectangles are squares.

f) All squares are rectangles.

g) Some squares are rectangles.

h) Some rectangles are not squares.

Ex 1.3.3 Write symbolically the following denials of definitions concerning a function $f$:

 a) $f$ is not increasing. c) $f$ is not constant.

 b) $f$ is not decreasing. d) $f$ does not have a root.

Ex 1.3.4 Simplify the following expressions:

 a) $\lnot \forall x>0 (x^2>x)$ c) $\lnot \forall x \forall y (xy=y^2\implies x=y)$

 b) $\lnot \exists x\in [0,1] (x^2+x< 0)$ d) $\lnot\exists x \exists y (x>y \land y>x)$

Ex 1.3.5 Verify the statement: $$\lnot \exists x (P(x)\land Q(x)) \iff\ \forall x (P(x) \implies\lnot Q(x))$$

Ex 1.3.6 Observe that $$P\lor Q \iff \lnot\lnot (P\lor Q)\iff \lnot (\lnot P\land \lnot Q)$$ so $\lor$ can be expressed in terms of $\land$ and $\lnot$.

a) Show how to express $\implies$ in terms of $\land$ and $\lnot$.

b) Show how to express $\land$ in terms of $\lnot$ and $\lor$.

c) Show how to express $\lor$ in terms of $\lnot$ and $\implies$.

Ex 1.3.7 Express the universal quantifier $\forall$ in terms of $\exists$ and $\lnot$. Express $\exists$ in terms of $\forall$ and $\lnot$.

Ex 1.3.8 Compute the year $y$ of De Morgan's birth.