De Morgan-azonosságok

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 | forrásszöveg szerkesztése]

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-féle 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

\begin{matrix}
\neg {(a \wedge b)} = \neg{a} \vee \neg{b} \\
\neg {(a \vee b)} = \neg{a} \wedge \neg{b}
\end{matrix} vagy \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:

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

ahol A az A komplementerhalmaza, \cap jelöli két halmaz metszetét és \cup jelöli két halmaz egyesítésé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:

\overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i} és \overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i}.

Következmények[szerkesztés | forrásszöveg szerkesztése]

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:

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:

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

Alkalmazás[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]