De Morgan’s laws describe how mathematical statements and concepts are related through their opposites. The structure of De Morgan’s laws, whether applied to Sets, Propositions, Boolean algebra, or Logic gates is always the same.
The complement of the union of two sets \(A\) and \(B\) is equal to the intersection of their complements. \[ \overline{A \cup B} = \overline{A} \cap \overline{B} \] The complement of the intersection of two set \(A\) and \(B\) is equal to the union of their complements \[ \overline{A \cap B} = \overline{A} \cup \overline{B} \]
\[ \lnot(p \lor q) \equiv \lnot p \land \lnot q \] \[ \lnot(p \land q) \equiv \lnot p \lor \lnot q \]
\[ \lnot \forall x P(x) \equiv \exists x\lnot P(x) \] \[ \lnot \exists x P(x) \equiv \forall x \lnot P(x) \] In the case of nested quantifiers, De Morgan’s Law is applied from left to right, inverting each.
\[ (x + y)' = x' \cdot y' \] \[ (x \cdot y)' = x' + y' \]