In set theory, de Morgan’s laws relate the three basic set operations to each other; the union, the intersection, and the complement. 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

Here, $\cup$ denotes the union, $\cap$ denotes the intersection, and $A^{\complement}$ denotes the set complement of $A$ in $X$, i.e., $A^{\complement}=X\setminus A$.

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 $A\cup B$ is not in $A$ and not in $B$. It also states that an elements not in $A$ and not in $B$ is not in $A\cup B$.

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

Theorem. Let $X$ be a set with subsets $A_{i}\subset X$ for $i\in I$, where $I$ is an arbitrary index-set. In other words, $I$ can be finite, countable, or uncountable. Then

(proof)

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

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