de Morgan’s laws

In set theoryMathworldPlanetmath, de Morgan’s laws relate the three basic set operationsMathworldPlanetmath to each other; the union, the intersectionMathworldPlanetmath, and the complementPlanetmathPlanetmath. de Morgan’s laws are named after the Indian-born British mathematician and logician Augustus De Morgan (1806-1871) [1].

If A and B are subsets of a set X, de Morgan’s laws state that

(AB) = AB,
(AB) = AB.

Here, denotes the union, denotes the intersection, and A denotes the set complement of A in X, i.e., A=XA.

Above, de Morgan’s laws are written for two sets. In this form, they are intuitively quite clear. For instance, the first claim states that an element that is not in AB is not in A and not in B. It also states that an elements not in A and not in B is not in AB.

For an arbitrary collectionMathworldPlanetmath of subsets, de Morgan’s laws are as follows:

Theorem. Let X be a set with subsets AiX for iI, where I is an arbitrary index-set. In other words, I can be finite, countableMathworldPlanetmath, or uncountable. Then

(iIAi) = iIAi,
(iIAi) = iIAi.

(proof (

de Morgan’s laws in a
For Boolean variables x and y in a Boolean algebraMathworldPlanetmath, de Morgan’s laws state that

(xy) = xy,
(xy) = xy.

Not surprisingly, de Morgan’s laws form an indispensable tool when simplifying digital circuits involving and, or, and not gates [2].


  • 1 Wikipedia’s on de Morgan, 4/2003.
  • 2 M.M. Mano, Computer Engineering: Hardware Design, Prentice Hall, 1988.
Title de Morgan’s laws
Canonical name DeMorgansLaws
Date of creation 2013-03-22 12:24:49
Last modified on 2013-03-22 12:24:49
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 15
Author mathcam (2727)
Entry type Theorem
Classification msc 03E30
Related topic Set
Related topic Complement