De Morgan's laws for statements
Negating “P and Q” looks like it should give “not P and not Q.” It does not. What is the actual negation, and why does the connective itself have to change?
Where you are 3 in Logical equivalence
Why this exists
You already know how to negate a single statement, and you know exactly what \land and \lor each demand: an and is hard to satisfy, since both halves must hold, and an or is easy, since one is enough. So a natural guess for negating a compound statement is to leave the connective alone and just negate each piece: surely “not (raining and cold)” is “not raining and not cold”?
It is not, and a quick check shows why. Suppose it is raining but not cold. “Raining and cold” is false, so its negation should be true. But “not raining and not cold” is also false: it is raining, so “not raining” already fails. The guess and the true negation disagree here, and again in the mirror case, cold but not raining. A conjunction is easy to break, one failing part is enough, so its negation, the statement that is true whenever the conjunction breaks, has to be just as easy to satisfy. That means the negation of an “and” must itself be an “or”.
Getting this exactly right matters whenever an argument has to say precisely what it is ruling out, which is most of the time in a proof.
Definition
For statements P and Q,
where \equiv reads “is logically equivalent to”: the two sides are true in exactly the same rows of a truth table. These are De Morgan’s laws, named for the nineteenth-century mathematician Augustus De Morgan. In words: the negation of an “and” is the “or” of the negations, and the negation of an “or” is the “and” of the negations. Two things happen at once. The connective flips, \land becomes \lor and \lor becomes \land, and the \neg that sat outside the whole statement moves inside, landing separately on P and on Q.
Nothing here depends on what P and Q say. The laws hold for every pair of statements, exactly because they are read off the truth values alone, the way every rule about \land and \lor is.
Intuition
Think of each point in a frame as one situation, with P true inside the P circle and Q true inside the Q circle. The left panel shades “not (P and Q)”: everything except the lens where the two circles overlap. The right panel builds “(not P) or (not Q)” from its two parts: one light layer for everything outside the P circle, a second light layer for everything outside the Q circle. A point counts as shaded if it lies in at least one layer, and the only points in neither layer are the ones inside both circles, the lens. So the two panels shade the same region: a point misses the overlap exactly when it is outside P, or outside Q, or both, which is what an inclusive “or” of the two “not” statements says. The darker area, outside both circles, is where both “not” statements hold at once; an “or” is happy there too.
The same picture explains the flip. P \land Q is the small region, the overlap, so its complement is large: everything that misses even one circle. “Missing at least one circle” is a demand that is easy to satisfy, which is the signature of an “or”, not an “and”.
Results
De Morgan’s laws.
Any finite number of parts. For statements P_1, P_2, \ldots, P_n,
Negating a long chain of “and”s turns it into the matching chain of “or”s of the negations, term by term, and the same for a chain of “or”s. Nothing new is needed to get here: the two-statement law, applied once for every extra term, does the whole job, shown in “Why it is true” below.
Why it is true
Both laws are proved by listing every combination of truth values for P and Q and checking that the two sides agree on each one.
| Row | P | Q | \neg P | \neg Q | {P \land Q} | {\neg(P \land Q)} | {\neg P \lor \neg Q} |
|---|---|---|---|---|---|---|---|
| 1 | T | T | F | F | T | F | F |
| 2 | T | F | F | T | F | T | T |
| 3 | F | T | T | F | F | T | T |
| 4 | F | F | T | T | F | T | T |
The last two columns match in every row, so \neg(P \land Q) and \neg P \lor \neg Q are the same statement. Row 2, P true and Q false, is where the guess that keeps the connective breaks down: \neg P \land \neg Q there is F and T, which is false, while the true negation is true. Row 3 fails the guess the same way. Flipping \land to \lor is not a matter of style; without it two rows disagree.
The “or” law is checked the same way.
| Row | P | Q | \neg P | \neg Q | {P \lor Q} | {\neg(P \lor Q)} | {\neg P \land \neg Q} |
|---|---|---|---|---|---|---|---|
| 1 | T | T | F | F | T | F | F |
| 2 | T | F | F | T | T | F | F |
| 3 | F | T | T | F | T | F | F |
| 4 | F | F | T | T | F | T | T |
Again the last two columns agree in all four rows, so \neg(P \lor Q) and \neg P \land \neg Q are the same statement.
Extending to three or more parts uses the two-statement law twice, not some new rule. Group P \land Q \land R as (P \land Q) \land R, and apply the law once to the outer \land, then once more to the \land left inside:
The brackets on the right can be dropped, since a chain of \lors does not care how it is grouped, giving \neg P \lor \neg Q \lor \neg R. A fourth term repeats the same step once more, on the \land still nested one level deeper, and so on: for n terms, the law is applied n - 1 times, never once needing a truth table with more than four rows. The “or” version follows the same pattern with the connectives swapped.
Worked examples
Negating a conjunction of number facts
Statement: “33 is odd and 33 is a multiple of 8.” Write its negation, and decide the truth of each.
Solution33 = 2(16) + 1, so it is odd: true. 33 \div 8 is not a whole number, so it is not a multiple of 8: the second part is false. One false part makes the conjunction false.
By the “and” law, the negation is
The first part is false, but the second is true, since 33 is not a multiple of 8. One true part is enough, so the negation is true, matching the original’s false.
Negating a disjunction of number facts
Statement: “50 is prime or 50 < 100.” Write its negation, and decide the truth of each.
Solution50 = 2 \times 25, so it is not prime: false. 50 < 100: true. One true part makes the disjunction true.
By the “or” law, the negation is
The first part is true, but the second is false, since 50 < 100. One false part makes a conjunction false, so the negation is false, matching the original’s true.
A compound inequality
The sentence “x \le 4 or x \ge 9” is true for some values of x and false for others. Write its negation.
SolutionBy the “or” law, the negation is
Check the boundary x = 4: the original is true, since 4 \le 4, so the negation must be false there, and it is: 4 > 4 is false. Check x = 6: the original is false, since 6 \le 4 and 6 \ge 9 both fail, and the negation is true there, since 6 > 4 and 6 < 9. Notice \le flips to the strict >, not to \ge: the boundary 4 satisfies the original, so it must fail the negation.
Three statements joined by and
Statement: “n is even and n is a multiple of 3 and n > 50,” evaluated at n = 42. Write its negation and evaluate both.
SolutionAt n = 42: even, true; a multiple of 3, true, since 42 = 3(14); but 42 > 50 is false. One false part makes the three-way conjunction false.
Applying the “and” law twice, as in “Why it is true”, the negation is
At n = 42: odd is false, not a multiple of 3 is false, but n \le 50 is true. One true part makes the disjunction true, matching the original’s false.
A statement built from and inside or
Statement: “(x is even and x is a multiple of 7) or x = 3,” evaluated at x = 14. Write its negation and evaluate both.
SolutionAt x = 14: even, true, and a multiple of 7, true, since 14 = 7(2), so the inner “and” is true. One true part is enough for the outer “or”, so the whole statement is true, without even checking x = 3.
Write A for “x is even”, B for “x is a multiple of 7” and C for “x = 3”, so the statement is (A \land B) \lor C. Two applications are needed: the “or” law on the outside, then the “and” law on the piece it exposes.
Back in words, the negation is
At x = 14: x is odd is false, and x is not a multiple of 7 is false, so the inner “or” is false, which makes the whole “and” false. The negation is false at x = 14, matching the original’s true, regardless of 14 \ne 3.
Double negation inside a De Morgan step
Let P be “40 is a multiple of 6” and Q be “40 is a multiple of 8.” Find the negation of \neg P \land Q, and evaluate both statements.
Solution40 \div 6 is not a whole number, so P is false, and \neg P is true. 40 = 8(5), so Q is true. \neg P \land Q is true and true, which is true.
To negate it, apply the “and” law, then simplify the double negation it produces:
Evaluate the result directly: P is false and \neg Q is false, since Q is true, so P \lor \neg Q is false, correctly the opposite of \neg P \land Q’s true.
Boundaries
Only \land, \lor and \neg are covered. A statement built with “if...then” or “if and only if” is not directly in the scope of either law. “If...then” needs the separate fact \neg(P \to Q) \equiv P \land \neg Q, which comes from writing a conditional as an “or”, before an “and” or “or” sitting inside it can be reached.
Each piece must already be a statement. P and Q need a fixed truth value for \land, \lor and \neg to apply to them at all. “x > 2” is not a statement while x is free; it becomes one once a value is substituted, as in the worked examples with a variable, or once it is quantified.
A finite chain, extended one link at a time. The law scales to any number of statements joined by the same connective, but only by repeating the two-statement version once per extra term. A statement that instead quantifies over a domain, “for every x” or “there is an x”, is not a finite chain of named statements at all, and negating it needs its own argument, even though the pattern looks the same: negating a quantified statement.
The law rewrites one connective at a time. \neg(P \land Q) becomes \neg P \lor \neg Q, and no further; if P or Q is itself built from \land or \lor, that piece needs the law applied to it separately, exactly as Example 5 needed two passes rather than one.
Where this goes next
Writing “if P then Q” as \neg P \lor Q turns its negation into a direct application of the “or” law, the next step once a conditional is in play. The same “flip the connective, negate the pieces” shape reappears once a statement ranges over a whole domain rather than naming finitely many parts, in negating a quantified statement, and the identical law for sets, where \land and \lor become intersection and union, is De Morgan’s laws for sets.
Producing the exact negation of a claim is also the first move in an indirect proof: to argue by contradiction you assume the negation of what you want, and De Morgan’s laws are what turn that negation, when it is an “and” or an “or”, into a statement you can actually use.
Exercises
Negating an and
- Negate “25 is even and 25 is a multiple of 5.” Decide the truth of both.
- Negate “63 is odd and 63 is a multiple of 9.” Decide the truth of both.
- Negate “14 is a multiple of 4 and 14 > 10.” Decide the truth of both.
Negating an or
- Negate “29 is even or 29 is a multiple of 6.” Decide the truth of both.
- Negate “13 is prime or 13 < 100.” Decide the truth of both.
- Negate “18 is a multiple of 5 or 18 is odd.” Decide the truth of both.
Compound inequalities
- Negate “x > -2 and x < 6.” Check your negation at x = -2 and at x = 0.
- Negate “x < 0 or x > 100.” Name one number that satisfies your negation, and check that the original statement is false there.
- Negate “x \ge 7 and x \le 20.” Check your negation at x = 7.
Three or more parts
- Negate “n is prime or n is a multiple of 10 or n < 0,” and evaluate both statements at n = 21.
- Negate “n is odd and n is a multiple of 3 and n < 100,” and evaluate both statements at n = 45.
Nested and mixed connectives
- Negate “x is odd and (x > 20 or x = 1).” Evaluate both statements at x = 1.
- Let P be “54 is a multiple of 9” and Q be “54 is a multiple of 5.” Negate P \lor \neg Q, simplifying any double negation, and evaluate both statements.
- Negate “(x is a multiple of 6 or x is a multiple of 10) and x < 100.” Evaluate both statements at x = 12.
Reasoning
- A classmate negates “P \land Q” as “\neg P \land \neg Q,” keeping the connective the same. Using P: “16 is even” and Q: “16 is a multiple of 3”, show that this “negation” and the real one, \neg P \lor \neg Q, disagree.
- Rewrite \neg(P \lor Q \lor R) so that every \neg sits on a single letter, showing both steps, and explain why the “or” law has to be applied twice rather than once.
- P is “n is a multiple of 4” and Q is “n is a multiple of 10.” Explain why \neg P \lor \neg Q is true for every odd number n, without checking any particular n.
- Explain, using only what \land and \lor each require, why \neg(P \lor Q) and \neg P \land \neg Q must agree on every row of a truth table, without writing the table out again.
Answers
- “25 is odd or 25 is not a multiple of 5.” The original is false: 25 is odd, not even. The negation is true, since 25 is odd.
- “63 is even or 63 is not a multiple of 9.” Original true (63 odd, 63 = 9(7)). Negation false: neither part holds.
- “14 is not a multiple of 4 or 14 \le 10.” Original false, since 14 \div 4 is not whole. Negation true, since 14 is not a multiple of 4.
- “29 is odd and 29 is not a multiple of 6.” Original false (29 is odd, not even). Negation true: both parts hold.
- “13 is not prime and 13 \ge 100.” Original, “13 is prime or 13 < 100,” is true, since 13 is prime. Negation false, since 13 is prime.
- “18 is not a multiple of 5 and 18 is even.” Original false (18 is not a multiple of 5 and not odd). Negation true: both parts hold.
- “x \le -2 or x \ge 6.” At x = -2: the original needs x > -2, which fails, so it is false; the negation is true, since -2 \le -2. At x = 0: the original is true, since 0 > -2 and 0 < 6; the negation is false, since neither 0 \le -2 nor 0 \ge 6 holds.
- “x \ge 0 and x \le 100.” x = 50 satisfies the negation, since 50 \ge 0 and 50 \le 100; the original is false there.
- “x < 7 or x > 20.” At x = 7: the original is true, since 7 \ge 7; the negation is false, since 7 < 7 and 7 > 20 both fail.
- “n is not prime and n is not a multiple of 10 and n \ge 0.” At n = 21: all three parts hold, so the negation is true, and the original, whose three parts all fail, is false.
- “n is even or n is not a multiple of 3 or n \ge 100.” At n = 45: every part of the original holds, so it is true, and every part of the negation fails, so it is false.
- “x is even or (x \le 20 and x \ne 1).” At x = 1: the original is true, since 1 is odd and x = 1 makes the inner “or” true even though 1 > 20 fails. The negation is false: x is even fails, and x \ne 1 fails, so its inner “and” fails too.
- \neg(P \lor \neg Q) \equiv \neg P \land \neg(\neg Q) \equiv \neg P \land Q. P: 54 = 9(6), true. Q: 54 \div 5 is not whole, false. P \lor \neg Q is true; \neg P \land Q is false, the opposite as required.
- “(x is not a multiple of 6 and x is not a multiple of 10) or x \ge 100.” At x = 12: the original is true, since 12 is a multiple of 6 and 12 < 100. The negation is false: x is not a multiple of 6 fails, and 12 \ge 100 fails.
- P is true (16 is even), Q is false (16 is not a multiple of 3), so \neg P is false and \neg Q is true. The classmate’s \neg P \land \neg Q is false; the real negation, \neg P \lor \neg Q, is true. They disagree.
- Group P \lor Q \lor R as (P \lor Q) \lor R. The “or” law on the outer connective gives \neg(P \lor Q) \land \neg R, which still has an “or” nested inside, so the law is applied again to get (\neg P \land \neg Q) \land \neg R, which is \neg P \land \neg Q \land \neg R. Each application only reaches the connective right under the \neg it starts with, so a second \lor needs a second application.
- A multiple of 4 is even, since n = 4k = 2(2k), so no odd number is a multiple of 4: P is false for every odd n, and \neg P is true for every odd n. A disjunction with one true part is true, so \neg P \lor \neg Q is true for every odd n, whatever Q says.
- \neg(P \lor Q) is true exactly when P \lor Q is false, which happens in exactly one case, P false and Q false. \neg P \land \neg Q is true exactly when P is false and Q is false, the same one case, so the two sides agree in every row.