Dualität (Logik)

2024-09-29T13:55:35Z

77.188.6.71: /* Weblinks */

{{Quellen|1=Es ist keine weiterführende Literatur angegeben und es gibt keinen Einzelnachweis. Vorlesungsfolien sind nicht hinreichend.}}
Zwei [[Aussage (Logik)|Aussagen]] <math>\phi,\psi</math> der klassischen [[Aussagenlogik]] über der Aussagenvariablenmenge <math>V</math> werden als '''dual''' zueinander bezeichnet, wenn für alle Belegungen <math>e\colon V \to \Omega</math> der Aussagenvariablen mit Wahrheitswerten gilt <math>\lnot [\![\phi]\!](e) = [\![\psi]\!](\lnot e)</math>.

{| class="wikitable floatright" style="padding: 0.5em; width: 15em"
|

{| class="wikitable center" style="padding:3px"; margin-left: 0.5em; border-spacing: 1px;"
|- ----
| <math>A</math> || <math>B</math> || <math>A \land B</math> || || | <math>A</math> || <math>B</math> || <math>A \lor B</math>
|- ----
| W || W || W || || | F || F || F
|- ----
| W || F || F || || | F || W || W
|- ----
| F || W || F || || | W || F || W
|- ----
| F || F || F || || | W || W || W
|- ----
|}
|-
|<small>Beispiel: Ersetzt man in der Wahrheitswertetabelle der [[Konjunktion (Logik)|Konjunktion]] in jeder Zeile alle drei Wahrheitswerte durch ihr Gegenteil, so erhält man die Wahrheitswertetabelle der [[Disjunktion]]. Siehe auch [[De Morgan’sche Gesetze]].</small>
|}

== Syntaktische Definition ==

Für Aussagen in [[Negationsnormalform]], das heißt für Aussagen, in denen als Junktoren nur [[Konjunktion (Logik)|Konjunktionen]], [[Disjunktion]]en und [[Negation]]en vorkommen und in denen nur [[Aussage (Logik)|atomare Aussagen]] verneint werden, lässt sich eine einfache syntaktische Definition für Dualität angeben:
: Zwei Aussagen <math>V_1</math> und <math>V_2</math> sind genau dann '''dual''', wenn jedes Vorkommnis des Junktors <math>\land</math> (Konjunktion) durch <math>\lor</math> (Disjunktion) und wenn jedes Vorkommnis des Junktors <math>\lor</math> durch <math>\land</math> ersetzt wird.

Da sich für jede Aussage eine Negationsnormalform bilden lässt, liefert diese Definition ein syntaktisches Verfahren, zu jeder Aussage <math>\varphi</math> eine duale Aussage zu bilden: Man bildet eine Negationsnormalform zu <math>\varphi</math> und ersetzt jedes darin vorkommende <math>\land</math> durch <math>\lor</math> und umgekehrt.

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

== Elementare Dualitäten ==

# <math>A</math> ist dual zu <math>A</math> ; <math> \overline{A} </math> ist dual zu <math> \overline{A} </math> ;
# <math> ~ A ~ \land ~ B </math> ist dual zu <math> A ~\lor ~ B </math> ;
# <math> ~ A ~ \rightarrow ~ B </math> ist dual zu <math> ~ \overline {B ~ \rightarrow ~ A} </math> ;
# <math> ~ A ~ \leftrightarrow ~ B </math> ist dual zu <math> A ~ \dot\lor ~ B </math> (ausschließende Disjunktion) ;

== Fünf Dualitätssätze ==
[[Datei:Duales Element (Boolesche Algebra).svg|mini|[[Hasse-Diagramm]], das sämtliche aus zwei Elementar-Aussagen gebildeten Kombinationen zeigt. Eine schwarze „Verbindungslinie“ zwischen zwei Aussagen zeigt an, dass die untere Aussage die obere Aussage impliziert. Diese Verbindungslinien sind über die Zwischenaussagen hinweggehend zu denken.<br>
Die blauen Pfeile markieren jeweils den Übergang zum dualen Element. Man sieht, dass durch diesen Übergang alle Implikationen „umgedreht“ werden.]]

=== Dualität von Konjunktion und Disjunktion ===

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

Beispiel: <math>(A \land \neg B) \lor C</math> ist dual zu <math>(A \lor \neg B) \land C</math>

=== Dualität und Negation ===

Wenn <math>V_1</math> eine Aussage ist, so erhält man eine duale Verknüpfung <math>V_2</math>, wenn alle Variablen und die gesamte Verknüpfung <math>V_1</math> selbst negiert werden.

Beispiele: <math>A\leftrightarrow B</math> ist dual zu <math>\overline{\overline{A}\leftrightarrow\overline{B}}</math>; <math>A \land (B \lor C)</math> ist dual zu <math>\overline{\overline{A} \land (\overline{B} \lor \overline{C})}</math>.

=== Dualität bei Tautologie und Kontradiktion ===

Wenn eine Aussage eine [[Tautologie (Logik)|Tautologie]] ist, so ist die zu ihr duale Aussage eine [[Kontradiktion]] und umgekehrt.

Beispiel: <math>A\land B\land\overline{A}</math> ist eine Kontradiktion (immer falsch), also ist das duale <math> A \lor B\lor \overline{A}</math> eine Tautologie (immer wahr).

=== Dualität und Implikation ===
Eine Aussage <math>V_1</math> [[Implikation|impliziert]] genau dann eine Aussage <math>V_2</math>, wenn eine (und damit jede) zu <math>V_2</math> duale Aussage eine (und damit jede) zu <math>V_1</math> duale Aussage impliziert.

Beispiel: <math>(A \land B) \Rightarrow A </math> genau dann, wenn dual gilt: <math>A \Rightarrow (A \lor B)</math>.

=== Dualität und Äquivalenz ===
Eine Aussage <math> V_1 </math> ist genau dann äquivalent zu einer Aussage <math>V_2</math>, wenn eine (und damit jede) zu <math>V_1</math> duale Aussage auch äquivalent zu einer (und damit jeder) zu <math>V_2</math> dualen Aussage ist.

Beispiel: <math>(A \land B) \Leftrightarrow (B \land A) </math> genau dann, wenn dual gilt: <math>(A \lor B) \Leftrightarrow (B \lor A) </math>.

==Siehe auch ==
* [[Boolesche Algebra]]

== Weblinks ==
{{Wiktionary}}
* [http://www.rz.e-technik.fh-kiel.de/~dispert/digital/digital1/dig001_7.htm Dualitätsprinzip] im Skriptum [http://www.rz.e-technik.fh-kiel.de/~dispert/digital/digital/dig0_00.htm Einführung in die Technische Informatik und Digitaltechnik] (Helmut Dispert, FH Kiel)
* Vorlesungsfolien [http://sus.ziti.uni-heidelberg.de/Lehre/DSTVorlesung06/DST06_04_Logik_Gatter.pdf Aussagenlogik und Gatter] (Kapitel „Dualität“ auf Seite 9; PDF; 663 kB) in den Unterlagen zur Vorlesung „Digitale Schaltungstechnik“ (Peter Fischer, Universität Mannheim, Sommersemester 2006)

[[Kategorie:Logik]]
[[en:Duality (mathematics)#Duality in logic and set theory]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Dualität (Logik)