# 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) $$