Mathematics · Ch 1 — Mathematical Logic
Negations of compound statements
Negations of compound statements
Some compound statements have negations that deserve naming in their own right, because they let us rewrite 'not (A and B)' or 'not (A or B)' as a positive-looking statement instead of leaving a sitting in front of a bracket.
Negation of a conjunction. Ask when the statement '6 is an even number and 6 is a perfect number' is false. It fails exactly when 6 is not even, or 6 is not a perfect number (or both) — a conjunction breaks the moment either half breaks. In symbols, .
Negation of a disjunction. Ask when 'x is prime or y is even' is false. It fails only when both halves fail together — x is not prime and y is not even. In symbols, . These two rules together are De Morgan's laws: negating flips to (or to ) and pushes the onto each piece separately.
Both rules, and the two negations that follow, check out on all four combinations of p and q:
| p | q | ~(p∧q) | ~p∨~q | ~(p∨q) | ~p∧~q | ~(p→q) | p∧~q | ~(p↔q) | (p∧~q)∨(q∧~p) |
|---|---|---|---|---|---|---|---|---|---|
| T | T | F | F | F | F | F | F | F | F |
| T | F | T | T | F | F | T | T | T | T |
| F | T | T | T | F | F | F | F | T | T |
| F | F | T | T | T | T | F | F | F | F |
Columns 3–4 agree in every row, confirming the first De Morgan's law, and columns 5–6 agree in every row, confirming the second. …
Worked out. De Morgan's Laws state that ~(p ∧ q) ≡ ~p ∨ ~q (a conjunction fails when at least one part fails) and ~(p ∨ q) ≡ ~p ∧ ~q (a disjunction fails only when both parts fail) — for instance the negation of '6 is even and perfect' is '6 is not even or 6 is not perfect', and the negation of 'x is prime or y is even' is 'x is not prime and y is not even'. Separately, since a conditional p → q is false only when p is true and q is false, its negation is exactly that single case: ~(p → q) ≡ p ∧ ~q. And since the biconditional p ↔ q can be rewritten as (p → q) ∧ (q → p), applying De Morgan's law to it gives ~(p ↔ q) ≡ (p ∧ ~q) ∨ (q ∧ ~p) — 'p if and only if q' fails prec …