de Morgan’s laws

In set theory, de Morgan’s lawsrelate the three basic set operations to each other;the union, the intersection, and the complement.de Morgan’s laws are named after theIndian-born British mathematician and logicianAugustus De Morgan (1806-1871) [1].

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

${(A\cup B)}^{\mathrm{\complement }}$$=$$A^{\mathrm{\complement }}\cap B^{\mathrm{\complement }},$

${(A\cap B)}^{\mathrm{\complement }}$$=$$A^{\mathrm{\complement }}\cup B^{\mathrm{\complement }}.$

Here, $\cup$ denotes the union, $\cap$ denotes the intersection,and $A^{\mathrm{\complement }}$ denotes the set complement of $A$ in $X$, i.e.,$A^{\mathrm{\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 elementthat 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 areas 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

${\left({\displaystyle \bigcup _{i\in I}}{A}_i\right)}^{\mathrm{\complement }}$$=$${\displaystyle \bigcap _{i\in I}}{A}_i^{\mathrm{\complement }},$

${\left({\displaystyle \bigcap _{i\in I}}{A}_i\right)}^{\mathrm{\complement }}$$=$${\displaystyle \bigcup _{i\in I}}{A}_i^{\mathrm{\complement }}.$

(proof (http://planetmath.org/DeMorgansLawsProof))

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

${(x\wedge y)}^{\prime }$$=$$x^{\prime }\vee y^{\prime },$

${(x\vee y)}^{\prime }$$=$$x^{\prime }\wedge y^{\prime }.$

Not surprisingly, de Morgan’s laws form an indispensable toolwhen simplifying digital circuits involving and, or, and notgates [2].