Dualität (Logik)

In der klassischen Aussagenlogik bezeichnet man zwei Aussagen als dual zueinander, wenn die Wahrheitstabelle der einen Aussage in die Wahrheitstabelle der anderen Aussage übergeht, sofern man darin jedes Vorkommnis eines Wahrheitswertes durch den jeweils anderen Wahrheitswert ersetzt.

Ersetzt man zum Beispiel in der Wahrheitswertetabelle der Konjunktion jedes Auftreten eines Wahrheitswerts durch den jeweils anderen Wahrheitswert, so erhält man, in veränderter Reihenfolge, die Wahrheitswertetabelle der Disjunktion. Dies zeigt die folgende Tabelle:

A	B	$A \and B$	A	B	$A \or B$
W	W	W	F	F	F
W	F	F	F	W	W
F	W	F	W	F	W
F	F	F	W	W	W

Im Allgemeinen gibt es zu jeder zusammengesetzten Aussage mehr als eine duale Aussage; im obigen Beispiel liefert nicht nur $A \or B$ den zu $A \and B$ dualen Wahrheitswertverlauf, sondern etwa auch $\neg A \rightarrow B$.

Syntaktische Definition

Für Aussagen in Negationsnormalform, das heißt für Aussagen, in denen als Junktoren nur Konjunktionen, Disjunktionen und Negationen vorkommen und in denen nur atomare Aussagen verneint werden, lässt sich eine einfache syntaktische Definition für Dualität angeben:

Zwei Aussagen V₁ und V₂ sind genau dann dual, wenn jedes Vorkommnis des Junktors $\and$ (Konjunktion) durch $\or$ (Disjunktion) und wenn jedes Vorkommnis des Junktors $\or$ durch $\and$ ersetzt wird.

Da sich für jede Aussage eine Negationsnormalform bilden lässt, liefert diese Definition ein syntaktisches Verfahren, zu jeder Aussage φ eine duale Aussage zu bilden: Man bildet eine Negationsnormalform zu φ und ersetzt jedes darin vorkommende $\and$ durch $\or$ und umgekehrt.

Um zum Beispiel eine zu $A \rightarrow (B \vee C)$ duale Aussage zu bilden, formt man sie zuerst in eine Negationsnormalform um, etwa in $(\neg A \or B) \or C$. Nach dem Ersetzen von $\and$ durch $\or$ und umgekehrt entsteht die Aussage $(\neg A \and B) \and C$, und diese ist dual zur ursprünglichen Aussage.

Elementare Dualitäten

1. A ist dual zu A ; $\overline{A}$ ist dual zu $\overline{A}$ ;
2. $~ A ~ \and ~ B$ ist dual zu $A ~\or ~ B$ ;
3. $~ A ~ \rightarrow ~ B$ ist dual zu $~ \overline {B ~ \rightarrow ~ A}$ ;
4. $~ A ~ \leftrightarrow ~ B$ ist dual zu $A ~ \dot\or ~ B$ (ausschließende Disjunktion) ;

Fünf Dualitätssätze

Dualität von Konjunktion und Disjunktion

V₁ sei eine zusammengesetzte Aussage, die nur aus Konjunktionen, Disjunktionen und Negationen besteht (aber keine Negationsnormalform sein muss). Diejenige Verknüpfung V₂, die dadurch entsteht, dass bei V₁ überall die Konjunktionen mit den Disjunktionen und umgekehrt vertauscht werden, ist dann dual zu V₁.

Beispiel: $(A \and \neg B) \or C$ ist dual zu $(A \or \neg B) \and C$

Dualität und Negation

Wenn V₁ eine Aussage ist, so erhält man eine duale Verknüpfung V₂, wenn alle Variablen und die gesamte Verknüpfung V₁ selbst negiert werden.

Beispiele: $A\leftrightarrow B$ ist dual zu $\overline{\overline{A}\leftrightarrow\overline{B}}$; $A \and (B \or C)$ ist dual zu $\overline{\overline{A} \and (\overline{B} \or \overline{C})}$.

Dualität bei Tautologie und Kontradiktion

Wenn eine Aussage eine Tautologie ist, so ist jede zu ihr duale Aussage eine Kontradiktion und umgekehrt.

Beispiel: $A\and B\and\overline{A}$ ist eine Kontradiktion (immer falsch), also ist das duale $\overline{A}\or \overline{B}\or A$ eine Tautologie (immer wahr).

Dualität und Implikation

Eine Aussage V₁ impliziert genau dann eine Aussage V₂, wenn eine (und damit jede) zu V₂ duale Aussage eine (und damit jede) zu V₁ duale Aussage impliziert.

Beispiel: $(A \and B) \Rightarrow A$ genau dann, wenn dual gilt: $A \Rightarrow (A \or B)$.

Dualität und Äquivalenz

Eine Aussage V₁ ist genau dann äquivalent zu einer Aussage V₂, wenn eine (und damit jede) zu V₁ duale Aussage auch äquivalent zu einer (und damit jeder) zu V₂ dualen Aussage ist.

Beispiel: $(A \and B) \Leftrightarrow (B \and A)$ genau dann, wenn dual gilt: $(A \or B) \Leftrightarrow (B \or A)$.

Weblinks

• Dualitätsprinzip im Skriptum Einführung in die Technische Informatik und Digitaltechnik (Helmut Dispert, FH Kiel)
• Vorlesungsfolien Aussagenlogik und Gatter (Kapitel „Dualität“ auf Seite 9) in den Unterlagen zur Vorlesung „Digitale Schaltungstechnik“ (Peter Fischer, Universität Mannheim, Sommersemester 2006)