Namespaces
Variants
Actions

De Morgan laws

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


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=54396