De Morganin lait

De Morganin lait ovat logiikan päättelysääntöjä.

$\neg(p\wedge q)\iff(\neg p)\vee(\neg q)$

$\neg(p\vee q)\iff(\neg p)\wedge(\neg q)$

missä:

• $\neg$ negaatio (ei)
• $\wedge$ konjunktio (ja)
• $\vee$ disjunktio (tai)
• $\iff$ ekvivalenssi (jos ja vain jos)

tai joukko-opissa käytettynä:

$\overline{A \cup B}=\overline{A} \cap \overline{B}.$

$\overline{A \cap B}=\overline{A} \cup \overline{B}$

missä:

• $\overline A$ on $\,A$:n komplementtijoukko
• $\cap$ on leikkaus (ja)
• $\cup$ on yhdiste tai unioni (tai)

Säännöt on nimetty löytäjänsä Augustus De Morganin (1806–1871) mukaan.

Todistus

$\overline{A \cap B}=\overline{A} \cup \overline{B}$ jos ja vain jos $\overline{A \cap B}\subseteq\overline{A} \cup \overline{B}$ ja $\overline{A \cap B}\supseteq\overline{A} \cup \overline{B}$.

mielivaltaiselle x:lle:

$\subseteq$:

$x \in \overline{A \cap B}$

$x \notin {A \cap B}$

$x \notin A$ tai $x \notin B$

$x \in \overline A$ tai $x \in \overline B$

$x \in \overline A \cup \overline B$

Joten $\overline{A \cap B}\subseteq\overline{A} \cup \overline{B}$

$\supseteq$:

$x \in \overline A \cup \overline B$

$x \in \overline A$ tai $x \in \overline B$

$x \notin A$ tai $x \notin B$

$x \notin {A \cap B}$

$x \in \overline{A \cap B}$

Joten $\overline{A \cap B}\supseteq\overline{A} \cup \overline{B}$

$\overline{A \cap B}\subseteq\overline{A} \cup \overline{B}$ ja $\overline{A \cap B}\supseteq\overline{A} \cup \overline{B}$ joten $\overline{A \cap B}= \overline{A} \cup \overline{B}$

$\overline{A \cup B}=\overline{A} \cap \overline{B}$ voidaan todistaa käyttämällä samanlaista menetelmää.