Wikia

Math Wiki

De Morgan's laws

Talk0
873pages on
this wiki

De Morgan's laws are a pair of simple statements relating disjunction and conjunction in formal logic. Specifically:

  1. The negation of the conjunction of two statements is logically equivalent to the disjunction of their negations.
  2. The negation of the disjunction of two statements is logically equivalent to the conjunction of their negations.

Since the English description is obviously very unwieldy, they are better described here in terms of logical operators, respectively:

  1. \neg(p \wedge q) \equiv \neg p \vee \neg q
  2. \neg(p \vee q) \equiv \neg p \wedge \neg q

Both of these laws can easily be verified using truth tables:

p q \neg(p \wedge q) \neg p \vee \neg q
T T F F
T F T T
F T T T
F F T T
p q \neg(p \vee q) \neg p \wedge \neg q
T T F F
T F F F
F T F F
F F T T


Application of De Morgan's LawsEdit

Even though De Morgan's laws seem useless at the outset, they are really an important part of the logician's toolbox.[1] Here is an example of a short formal logical proof which relies strongly on DeMorgan's surprisingly important discovery:

  1. (A \vee B) \to (C \wedge D)
  2. \neg C / \therefore \neg B
  3. \neg C \vee \neg D (2, Add.)
  4. \neg (C \wedge D) (3, De M.)
  5. \neg (A \vee B) (1,4, M.T.)
  6. \neg A \wedge \neg B (5, De M.)
  7. \neg B \wedge \neg A (6, Com.)
  8. \neg B (7, Simp.)

De Morgan's first law is used twice in this proof. ('De Morgan' is conventionally shortened to 'De M.' in logical proofs.) In the first instance, the premiss \neg C is used to form the disjunctive statement \neg C \vee \neg D—perfectly legal in formal logic—and then transformed into its conjunctive form with the first law. This form easily demonstrates the negation of A \vee B through the principle of modus tollens, and since \neg (A \vee B) is also a candidate for transformation through De Morgan's first law, it becomes \neg A \wedge \neg B. \neg B then follows trivially from this statement. De Morgan's laws are a powerful tool for simplifying proofs greatly, not only for humans, but for automated theorem provers as well.

NotesEdit

  1. Probably the ball peen hammer.

Around Wikia's network

Random Wiki