De Morganin lait

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

${\displaystyle \neg (p\wedge q)\Leftrightarrow (\neg p)\vee (\neg q)}$

${\displaystyle \neg (p\vee q)\Leftrightarrow (\neg p)\wedge (\neg q)}$

missä:

• ${\displaystyle \neg }$ negaatio (ei)
• ${\displaystyle \wedge }$ konjunktio (ja)
• ${\displaystyle \vee }$ disjunktio (tai)
• ${\displaystyle \Leftrightarrow }$ ekvivalenssi (jos ja vain jos)

tai joukko-opissa käytettynä:

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

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

missä:

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

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

Todistus

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

mielivaltaiselle ${\displaystyle x}$:lle:

${\displaystyle \subseteq }$:

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

${\displaystyle x\notin {A\cap B}}$

${\displaystyle x\notin A}$ tai ${\displaystyle x\notin B}$

${\displaystyle x\in {\overline {A}}}$ tai ${\displaystyle x\in {\overline {B}}}$

${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

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

${\displaystyle \supseteq }$:

${\displaystyle x\in {\overline {A}}\cup {\overline {B}}}$

${\displaystyle x\in {\overline {A}}}$ tai ${\displaystyle x\in {\overline {B}}}$

${\displaystyle x\notin A}$ tai ${\displaystyle x\notin B}$

${\displaystyle x\notin {A\cap B}}$

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

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

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

${\displaystyle {\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.