De Morganin lait

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

$\mathrm{\neg }(p\wedge q)\iff (\mathrm{\neg }p)\vee (\mathrm{\neg }q)$

$\mathrm{\neg }(p\vee q)\iff (\mathrm{\neg }p)\wedge (\mathrm{\neg }q)$

missä:

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

tai joukko-opissa käytettynä:

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

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

missä:

• $\bar{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}=\bar{A}\cup \bar{B}$ jos ja vain jos $\overline{A\cap B}\subseteq \bar{A}\cup \bar{B}$ ja $\overline{A\cap B}\supseteq \bar{A}\cup \bar{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 \bar{A}$ tai $x\in \bar{B}$

$x\in \bar{A}\cup \bar{B}$

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

$\supseteq$:

$x\in \bar{A}\cup \bar{B}$

$x\in \bar{A}$ tai $x\in \bar{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 \bar{A}\cup \bar{B}$

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

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

Lähteet

• Malline:Verkkoviite
• Malline:Kirjaviite