De Morgan-azonosságok

A De Morgan-azonosságok a matematikai logika, illetve a halmazelmélet két alapvető tételét fogalmazzák meg. Az azonosságok Augustus De Morgan angol matematikusról kapták a nevüket, jóllehet William Ockham már a középkorban felismerte őket. Ezek az azonosságok minden Boole-algebrában érvényesek.

Azonosságok

A De Morgan-azonosságokat logikailag a következőképpen fejezhetjük ki:

nem (a és b) = (nem a) vagy (nem b)

nem (a vagy b) = (nem a) és (nem b)

A De Morgan-azonosságok felírására a matematikában számos különböző jelölés használatos. Az ítéletkalkulus formuláival például

${\displaystyle {\begin{matrix}\neg {(a\wedge b)}=\neg {a}\vee \neg {b}\\\neg {(a\vee b)}=\neg {a}\wedge \neg {b}\end{matrix}}}$ vagy ${\displaystyle {\begin{matrix}{\overline {(a\wedge b)}}={\overline {a}}\vee {\overline {b}}\\{\overline {(a\vee b)}}={\overline {a}}\wedge {\overline {b}}\end{matrix}}}$

A halmazelméletben ezen formulák megfelelői a következők:

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

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

ahol A az A komplementerhalmaza, ${\displaystyle \cap }$ jelöli két halmaz metszetét és ${\displaystyle \cup }$ jelöli két halmaz unióját.

Ezek az azonosságok tetszőleges sok elemre is érvényben maradnak, beleértve a véges, megszámlálhatóan végtelen és nem megszámlálható I indexhalmazok esetét is:

${\displaystyle {\overline {\bigcap _{i\in I}A_{i}}}=\bigcup _{i\in I}{\overline {A_{i}}}}$ és ${\displaystyle {\overline {\bigcup _{i\in I}A_{i}}}=\bigcap _{i\in I}{\overline {A_{i}}}}$.

Következmények

Egy konjunkció (ÉS-kapcsolat) a De Morgan-azonosságok segítségével átalakítható három negáció és egy diszjunkció (VAGY-kapcsolat) kompozíciójára a következőképpen:

${\displaystyle a\wedge b=\neg (\neg {a}\vee \neg {b})}$

Hasonlóképpen egy diszjunkció átalakítható három negáció és egy konjunkció kompozíciójára:

${\displaystyle a\vee b=\neg (\neg {a}\wedge \neg {b})}$

Alkalmazás

A De Morgan-azonosságok fontos alkalmazási területe a diszkrét matematika, az elektronika, a fizika és az informatika. Gyakran használják őket a digitális áramkörök fejlesztésében az alkalmazott logikai kapuk típusának egymással való felcserélésére, illetve a használt kapuk számának a csökkentésére.

Források

• De Morgan-azonosságok a MathWorld-ön (angolul)
• De Morgan-azonosságok a PlanetMath-en (angolul)
• Halmazelméleti bizonyítás tetszőleges indexhalmazra (angolul)