De Morgan-azonosságok forrásának megtekintése

[[Fájl:DeMorgan Logic Circuit diagram DIN.svg|bélyegkép|A de Morgan-féle azonosságok [[logikai kapu]]kkal á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-algebra (informatika)|Boole-algebrában]] érvényesek.

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

:[[Negáció|nem]] (a [[Konjunkció|és]] b) = (nem a) [[Diszjunkció|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

:<math>\begin{matrix}
\neg {(a \wedge b)} = \neg{a} \vee \neg{b} \\
\neg {(a \vee b)} = \neg{a} \wedge \neg{b}
\end{matrix}</math> vagy <math>\begin{matrix}
\overline{(a \wedge b)} = \overline{a} \vee \overline{b} \\
\overline{(a \vee b)} = \overline{a} \wedge \overline{b}
\end{matrix}</math>

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

:<math>\overline{A \cap B} = \overline{A} \cup \overline{B}</math>
:<math>\overline{A \cup B} = \overline{A} \cap \overline{B}</math>

ahol ''<font style="text-decoration:overline">A</font>'' az ''A'' [[Halmaz (matematika)#Komplementer halmaz|komplementerhalmaza]], <math>\cap</math> jelöli két [[Halmaz (matematika)|halmaz]] [[metszet (halmazelmélet)|metszetét]] és <math>\cup</math> jelöli két halmaz [[unió (halmazelmélet)|unióját]].

Ezek az azonosságok tetszőleges sok elemre is érvényben maradnak, beleértve a [[számosság#Véges halmaz|véges]], [[megszámlálhatóan végtelen]] és nem megszámlálható ''I'' indexhalmazok esetét is:

:<math>\overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i}</math> és <math>\overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i}</math>.

== 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:

:<math>a \wedge b = \neg(\neg{a} \vee \neg{b})</math>

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

:<math> a \vee b = \neg(\neg{a} \wedge \neg{b})</math>

== 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 kapu]]k típusának egymással való felcserélésére, illetve a használt kapuk számának a csökkentésére.
<!--
== Beispiel in der Mengenlehre ==

Es soll anhand der Beziehung
: <math> \overline{A} \cup \overline{B} = \overline{A \cap B} </math>
die Gültigkeit der De Morganschen Regeln illustriert werden.
Es sind zwei Mengen A und B gegeben, die Teilmengen einer Obermenge Ω sind. Die Grafik 1 zeigt die Lage der Mengen und ihrer Gegenmengen <font style="text-decoration:overline">A</font> und <font style="text-decoration:overline">B</font>.

In der Grafik 2 wird gezeigt, wie <math>\overline{A} \cup \overline{B}</math> gebildet wird. In der Grafik 3 wird das Komplement zu <math>A \cap B</math> dargestellt und man sieht, dass beide Mengen gleich sind.

{| border="1" cellspacing="0" align="center" cellpadding="3"
|-
| align="center" | [[Bild:DeMorgan1.jpg|200px]]
| align="center" | [[Bild:DeMorgan2.jpg|200px]]
| align="center" | [[Bild:DeMorgan3.jpg|200px]]
|-
| align="center" | Aufteilung der Obermenge in A und B
| align="center" | <math>\overline{A}\cup\overline{B} </math>
| align="center" | <math>\overline{A\cap B} </math>
|}
<br style="clear: left"/>

* Eine Interpretation wäre:

In einer Abnahmeprüfung werden hochwertige Kochmesser überprüft, ob die Schneide fehlerfrei ist (Menge A) und ob die Schneide ordnungsgemäß im Griff verankert ist (Menge B). Ein Messer wird nicht angenommen, wenn es zur Menge <font style="text-decoration:overline">A</font> oder zur Menge <font style="text-decoration:overline">B</font> oder zu beiden gehört, also wenn mindestens eine Beanstandung vorliegt: <math>\overline{A} \cup \overline{B}</math>. Das Messer wird angenommen, wenn es beide Anforderungen erfüllt, wenn es also zur Menge <math>A \cap B</math> gehört, das heißt, es wird nicht angenommen, wenn es zu <math>\overline{A \cap B}</math> gehört.
-->

== Források ==
*[http://mathworld.wolfram.com/deMorgansLaws.html De Morgan-azonosságok a MathWorld-ön] {{en}}
*[http://planetmath.org/DeMorgansLaws De Morgan-azonosságok a PlanetMath-en] {{en}}
*[http://planetmath.org/demorganslawsforsetsproof Halmazelméleti bizonyítás tetszőleges indexhalmazra] {{en}}

{{Portál|Matematika}}

[[Kategória:Halmazalgebra]]
[[Kategória:Matematikai logika]]