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äytämällä samanlaista menetelmää.