1 De Morgan’s Laws
De Morgan’s Laws are fundamental results in logic and set theory formalizing the intuitive relationship between negation (or complements in set theory) and the concepts of conjunction and disjunction.
- Law for negation of a conjunction: \(\sim(𝑝∧𝑞)≡~𝑝∨\sim 𝑞\);
- Law for the negation of a disjunction: \(\sim(𝑝∨𝑞)≡~𝑝∧\sim𝑞\);
- Negation of a conditional: \(\sim(𝑝→𝑞)≡𝑝∧\sim𝑞\);
- Writing conditional as a disjunction: \(𝑝→𝑞≡\sim𝑝∨𝑞\).
We can write equivalent laws in set theoretic notation: \[ \left( \bigcup_{n}A_{n} \right)^c=\bigcap_{n}A_{n}^c\quad \& \quad \left( \bigcap_{n}A_{n} \right)^c=\bigcup_{n}A_{n}^c. \] Proof: For the first law we see quickly that \[ \omega \in(\cup_{n}A_{n})^c\iff \omega \not\in \cup_{n}A_{n}\iff \omega \not\in A_{n},~\forall n\iff \omega \in A_{n}^c,~\forall n\iff \omega \in \cap_{n}A_{n}^c. \] For the second law similarly we have \[ \omega \in(\cap_{n}A_{n})^c \iff \omega \not\in \cap_{n}A_{n}\iff \exists n~s.t.~\omega \not\in A_{n}\iff \exists n~s.t.~\omega \in A_{n}^c \iff \omega \in \cup_{n}A_{n}^c.\tag*{$\square$ } \]