View source for De Morgan laws

{{TEX|done}}

Instances of [[duality principle]]s, expressing the effect of [[complementation]] in [[set theory]] on [[union of sets|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 operation]]s $\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