# De Morgan laws

Instances of duality principles, expressing the effect of complementation in set theory on union and intersection of sets; the analogous relationship between negation in propositional calculus and conjunction and disjunction. They were published by Augustus de Morgan (1806-1871) in 1858, in the forms "The contrary of an aggregate is the compound of the contraries of the aggregants" and "The contrary of a compound is the aggregation of the contraries of the components". Both laws were known in the 14th century to William of Ockham.

Let \$A\$, \$B\$ be sets in some universal domain \$\Omega\$ and \$\complement\$ denote complementation relative to \$\Omega\$. Then \$\$ \complement (A \cap B) = (\complement A) \cup (\complement B) \$\$ and \$\$ \complement (A \cup B) = (\complement A) \cap (\complement B) \$\$

Let \$p\$ and \$q\$ be propositions. \$\$ \neg(p \wedge q) = (\neg p) \vee (\neg q) \$\$ and \$\$ \neg(p \vee q) = (\neg p) \wedge (\neg q) \$\$

A de Morgan algebra is an abstract algebra with binary operations \$\wedge,\vee\$ and an involution satisfying the analogous relations.

#### References

• Augustus de Morgan, Trans. Cambridge Philos. Soc. 10 (1858) 208
• Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley (2014) ISBN 0133488853
How to Cite This Entry:
De Morgan laws. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=De_Morgan_laws&oldid=35218