De Morganin lait

Wikipedia
Loikkaa: valikkoon, hakuun

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[muokkaa | muokkaa wikitekstiä]

\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ää.


Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.