De Morgan's Theorem

De Morgan's Theorem is a Theorem from the field of Logic Systems about the conversion of a CNF Formula into a DNF Formula, and vice versa.

• AKA: De Morgan's Law, DeMorgan's Law.
• Context:
  • CNF<->DNF: not(P and Q) <=> (not P) or (not Q)
  • DNF<->CNF: not(P or Q) <=> (not P) and (not Q)
• See: Logic Sentence.

---

---

References

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/De_Morgan%27s_laws
  • In formal logic, De Morgan's laws are rules relating the logical operators "and" and "or" in terms of each other via negation, namely:
    • NOT (P OR Q) = (NOT P) AND (NOT Q)
    • NOT (P AND Q) = (NOT P) OR (NOT Q)

---