De Morgan-azonosságok
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/db/DeMorgan_Logic_Circuit_diagram_DIN.svg/220px-DeMorgan_Logic_Circuit_diagram_DIN.svg.png)
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
[szerkesztés]A De Morgan-azonosságokat logikailag a következőképpen fejezhetjük ki:
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
- vagy
A halmazelméletben ezen formulák megfelelői a következők:
ahol A az A komplementerhalmaza, jelöli két halmaz metszetét és 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:
- és .
Következmények
[szerkesztés]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:
Hasonlóképpen egy diszjunkció átalakítható három negáció és egy konjunkció kompozíciójára:
Alkalmazás
[szerkeszté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
[szerkesztés]- 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)