Boolean Algebra
De Morgan's Laws
- The negation of a disjunction is the conjunction of the negations
- The negation of a conjunction is the disjunction of the negations
or
- The complement of a union of two sets is the same as the intersection of their complements
- The complement of an intersection of two sets is the same as the union of their complements
or
- not (A or B) = not A and not B
- not (A and B) = not A or not B
Formally written, these are:
$$ \neg(P \vee Q) \Leftrightarrow (\neg P) \wedge (\neg Q) $$
and
$$ \neg(P \wedge Q) \Leftrightarrow (\neg P) \vee (\neg Q) $$