Ugrás a tartalomhoz

De Morgan-azonosságok

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából
A de Morgan-féle azonosságok logikai kapukkal ábrázolva

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:

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

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]