Answers · The mathematics underneath

Why does the negation of "A and B" become "not A or not B"?

In shortNegating 'A and B' asserts that at least one of the two fails, so the and becomes an or.

The negation of $A \land B$ is $(\lnot A)\lor(\lnot B)$ . It says that at least one of the two claims fails, not that both fail.

The four rows

Write $1$ for true and $0$ for false. There are only four possible combinations of $A$ and $B$ , so checking those four rows is not a sample; it is every case. The third column is $A\land B$ . The fourth column is its negation, built by reversing the third. The fifth column is built the other way: negate each part and join with inclusive or. If the two columns agree in all four rows, the identity is proved, because no other combination exists.

FIG 1The four cases, with both sides of the identity

	A	B	A and B	not (A and B)	(not A) or (not B)
both true	1	1	1	0	0
A true, B false	1	0	0	1	1
A false, B true	0	1	0	1	1
both false	0	0	0	1	1

One in each column means true and nought means false. The fourth and fifth columns agree in every row, which is the identity. The row with both parts true is the one that rules out the natural guess: there is true, so its negation is false, and both and are false, so their inclusive or is false too.

The equation is not an extra rule to memorise beside the table. It is the table read as a sentence: the only way for $A\land B$ to be true is for both parts to be true, so the only way for it to be false is for at least one part to be false. That sentence is exactly $(\lnot A)\lor(\lnot B)$ .

\lnot(A\land B) \;=\; (\lnot A)\lor(\lnot B)

Take $A$ as 'the order is paid' and $B$ as 'the stock is available'. The original claim $A\land B$ is true only in the first row. Its negation must therefore be true in the other three rows. Paid but no stock: $B$ is false, so $\lnot B$ is true, and the inclusive or is true. Unpaid but stock available: $A$ is false, so $\lnot A$ is true, and the or is true. Both fail: both negated parts are true, and the or is true. Both hold: both negated parts are false, and the or is false, which is exactly what negating a true original requires.

The natural guess

The natural guess is to keep the connective and negate each part: $(\lnot A)\land(\lnot B)$ . That is a different and much stronger claim. It is true only in the last row, when both $A$ and $B$ fail. But if $A$ is false and $B$ is true, the original $A\land B$ is false, so its negation is true, while $(\lnot A)\land(\lnot B)$ is false because $B$ still holds. This is the error to avoid: 'not both' is not 'neither'. In a condition, writing 'not (active and adult)' as 'not active and not adult' silently treats an inactive adult as though the original condition had held.

Put numbers on it. Let $A$ be 'the user is active' and $B$ be 'the age is at least eighteen'. The original condition is true for an active user aged $18$ or more. Its negation is 'the user is not active, or the age is under eighteen'. At age $18$ with an active user, $A$ and $B$ are both true, so the original is true and the negation is false: the equality boundary sits on the original side, which is correct. At age $17$ with an active user, $B$ is false, so the original is false and the negation is true because the age is under eighteen. At age $20$ with an inactive user, $A$ is false, so the original is false and the negation is true because the user is not active. The wrong version, 'not active and under eighteen', is false for that inactive twenty year old, so it misses a case where the original condition failed.

Why the or is inclusive

The swap uses inclusive or: at least one, including both. That is the reading in mathematics and in code. With that reading, the last row has both negated parts true, and the or is still true, which is needed because the original conjunction is false there. If or were read as exactly one, the right hand side would be false in that row while $\lnot(A\land B)$ is true, so the identity would fail. The rule is therefore not a convention about wording; it follows from 'at least one fails'.

The identity depends only on the truth values of $A$ and $B$ , not on what the sentences mean. It applies to any two claims that are each true or false. If a connective is given a different reading, such as exclusive or, the table changes and the swap no longer holds. Parentheses matter when connectives are mixed: $A\land B\lor C$ is normally read as $(A\land B)\lor C$ , because and binds tighter than or, so a negation of the whole expression needs the swap applied to the outermost connective first.

Worth keeping

Not both true is the same as at least one false, which is why the conjunction turns into an or.
The natural guess 'not A and not B' says both fail, a stronger claim, and it misses the cases where exactly one fails.
The swap uses inclusive or; if or means exactly one, the identity fails when both parts are false.

Where this goes next

This question is one step of Arguing That It Always Holds, a course that works through its subject from the beginning. The page that teaches this part of it is And, Or, and Not, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course