DemorgansLaw.md (1307B)
1 # Demorgan's Laws 2 3 1.3.2 4 5 **Definition:** These are two fundamental laws of boolean algebra that can be simply derived. 6 7 $\neg (p \wedge q) \equiv \neg p \vee \neg q$ 8 9 $\neg (p \vee q) \equiv \neg p \wedge \neg q$ 10 11 #### Showing these laws are true with truth tables 12 13 First law (columns 4 and 7 are being shown as equivalent): 14 15 | p | q | $p \wedge q$ | $\neg(p \wedge q)$ | $\neg p$ | $\neg q$ | $\neg p \vee \neg q$ | 16 | - | - | - | - | - | - | - | 17 | T | T | T | F | F | F | F 18 | T | F | F | T | F | T | T 19 | F | T | F | T | T | F | T 20 | F | F | F | T | T | T | T 21 22 Second law (columns 4 and 7 are being shown as equivalent): 23 24 | p | q | $p \vee q$ | $\neg(p \vee q)$ | $\neg p$ | $\neg q$ | $\neg p \wedge \neg q$ | 25 | - | - | - | - | - | - | - | 26 | T | T | T | F | F | F | F 27 | T | F | T | F | F | T | F 28 | F | T | T | F | T | F | F 29 | F | F | F | T | T | T | T 30 31 #### What these are saying 32 33 The first law states that not p and q is the same as not p or not q. 34 35 The second law states that not p or q is the same is not p and not q. 36 37 This is basically the distributive property of boolean logic whereby we flip the and/or connective and distribute the negation. 38 39 #### For Quantifiers 40 41 See [Quantifiers](Quantifiers.md) section on negation which describes the distribution of a negation when quantifiers are involved.