De Morganin lait

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

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

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

missä:

• $\neg$ negaatio (ei)
• $\wedge$ konjunktio (ja)
• $\vee$ disjunktio (tai)
• $\Leftrightarrow$ 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 eli unioni (tai)

Säännöt on nimetty kehittä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ää.

Lähteet

• De Morganin lait Matematiikan verkkosanakirja. Matematiikkalehti Solmu. Viitattu 16.7.2020.
• Jan Thompson: Matematiikan käsikirja, s. 59. Tammi, 1991. ISBN 951-31-0471-0.