De Morgan's laws

De Morgan's laws are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan. The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation, and relates the logical quantifiers similarly.

Expressed as truth-functional tautologies or theorems of propositional logic:

\neg (P \land Q) \Leftrightarrow (\neg P \lor \neg Q)

\neg (P \lor Q) \Leftrightarrow (\neg P \land \neg Q)

\neg (\exists x, P (x)) = (\forall x, \neg P (x))

\neg (\forall x, P (x)) = (\exists x, \neg P (x))

(A \cup B)^{∁} = A^{∁} \cap B^{∁}

(A \cap B)^{∁} = A^{∁} \cup B^{∁}

A ∖ (B \cup C) = (A ∖ B) \cap (A ∖ C)

A ∖ (B \cap C) = (A ∖ B) \cup (A ∖ C)

{(⋃_{i} E_{i})}^{∁} = ⋂_{i} E_{i}^{∁}

{(⋂_{i} E_{i})}^{∁} = ⋃_{i} E_{i}^{∁}