home

De Morgans laws

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, or logic gates, is always the same.

Sets

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} \]

Propositions

\[ \lnot(p \lor q) \equiv \lnot p \land \lnot q \] \[ \lnot(p \land q) \equiv \lnot p \lor \lnot q \]

Logic

\[ \lnot [(\forall x) P(x)] \equiv (\exists x)[\lnot P(x)] \] \[ \lnot [(\exists x) P(x)] \equiv (\forall x)[\lnot P(x)] \]