Dualität Logik Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen beispielsweise Einzelnachwei

Dualität (Logik)

Zwei Aussagen der klassischen Aussagenlogik über der Aussagenvariablenmenge werden als dual zueinander bezeichnet, wenn für alle Belegungen der Aussagenvariablen mit Wahrheitswerten gilt .


W	W	W	F	F	F
W	F	F	F	W	W
F	W	F	W	F	W
F	F	F	W	W	W

Beispiel: Ersetzt man in der Wahrheitswertetabelle der Konjunktion in jeder Zeile alle drei Wahrheitswerte durch ihr Gegenteil, so erhält man die Wahrheitswertetabelle der Disjunktion. Siehe auch De Morgan’sche Gesetze.

Syntaktische Definition Bearbeiten

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:

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 durch und umgekehrt.

Um zum Beispiel eine zu duale Aussage zu bilden, formt man sie zuerst in eine Negationsnormalform um, etwa in . Nach dem Ersetzen von durch und umgekehrt entsteht die Aussage , und diese ist dual zur ursprünglichen Aussage.

Elementare Dualitäten Bearbeiten

ist dual zu ; ist dual zu ;
ist dual zu ;
ist dual zu ;
ist dual zu (ausschließende Disjunktion) ;

Fünf Dualitätssätze Bearbeiten

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.
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 Bearbeiten

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

Beispiel: ist dual zu

Dualität und Negation Bearbeiten

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

Beispiele: ist dual zu ; ist dual zu .

Dualität bei Tautologie und Kontradiktion Bearbeiten

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

Beispiel: ist eine Kontradiktion (immer falsch), also ist das duale eine Tautologie (immer wahr).

Dualität und Implikation Bearbeiten

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

Beispiel: genau dann, wenn dual gilt: .

Dualität und Äquivalenz Bearbeiten

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

Beispiel: genau dann, wenn dual gilt: .

Siehe auch Bearbeiten

Boolesche Algebra

Weblinks Bearbeiten

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; PDF; 663 kB) in den Unterlagen zur Vorlesung „Digitale Schaltungstechnik“ (Peter Fischer, Universität Mannheim, Sommersemester 2006)

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele

Veröffentlichungsdatum: November 30, 2023, 09:15 am

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen beispielsweise Einzelnachweisen ausgestattet Angaben ohne ausreichenden Beleg konnten demnachst entfernt werden Bitte hilf Wikipedia indem du die Angaben recherchierst und gute Belege einfugst Es ist keine weiterfuhrende Literatur angegeben und es gibt keinen Einzelnachweis Vorlesungsfolien sind nicht hinreichend Zwei Aussagen ϕ ps displaystyle phi psi der klassischen Aussagenlogik uber der Aussagenvariablenmenge V displaystyle V werden als dual zueinander bezeichnet wenn fur alle Belegungen e V W displaystyle e colon V to Omega der Aussagenvariablen mit Wahrheitswerten gilt ϕ e ps e displaystyle lnot phi e psi lnot e A displaystyle A B displaystyle B A B displaystyle A land B A displaystyle A B displaystyle B A B displaystyle A lor B W W W F F FW F F F W WF W F W F WF F F W W WBeispiel Ersetzt man in der Wahrheitswertetabelle der Konjunktion in jeder Zeile alle drei Wahrheitswerte durch ihr Gegenteil so erhalt man die Wahrheitswertetabelle der Disjunktion Siehe auch De Morgan sche Gesetze Inhaltsverzeichnis 1 Syntaktische Definition 2 Elementare Dualitaten 3 Funf Dualitatssatze 3 1 Dualitat von Konjunktion und Disjunktion 3 2 Dualitat und Negation 3 3 Dualitat bei Tautologie und Kontradiktion 3 4 Dualitat und Implikation 3 5 Dualitat und Aquivalenz 4 Siehe auch 5 WeblinksSyntaktische Definition BearbeitenFur Aussagen in Negationsnormalform das heisst fur Aussagen in denen als Junktoren nur Konjunktionen Disjunktionen und Negationen vorkommen und in denen nur atomare Aussagen verneint werden lasst sich eine einfache syntaktische Definition fur Dualitat angeben Zwei Aussagen V 1 displaystyle V 1 nbsp und V 2 displaystyle V 2 nbsp sind genau dann dual wenn jedes Vorkommnis des Junktors displaystyle land nbsp Konjunktion durch displaystyle lor nbsp Disjunktion und wenn jedes Vorkommnis des Junktors displaystyle lor nbsp durch displaystyle land nbsp ersetzt wird Da sich fur jede Aussage eine Negationsnormalform bilden lasst liefert diese Definition ein syntaktisches Verfahren zu jeder Aussage f displaystyle varphi nbsp eine duale Aussage zu bilden Man bildet eine Negationsnormalform zu f displaystyle varphi nbsp und ersetzt jedes darin vorkommende displaystyle land nbsp durch displaystyle lor nbsp und umgekehrt Um zum Beispiel eine zu A B C displaystyle A rightarrow B vee C nbsp duale Aussage zu bilden formt man sie zuerst in eine Negationsnormalform um etwa in A B C displaystyle neg A lor B lor C nbsp Nach dem Ersetzen von displaystyle land nbsp durch displaystyle lor nbsp und umgekehrt entsteht die Aussage A B C displaystyle neg A land B land C nbsp und diese ist dual zur ursprunglichen Aussage Elementare Dualitaten BearbeitenA displaystyle A nbsp ist dual zu A displaystyle A nbsp A displaystyle overline A nbsp ist dual zu A displaystyle overline A nbsp A B displaystyle A land B nbsp ist dual zu A B displaystyle A lor B nbsp A B displaystyle A rightarrow B nbsp ist dual zu B A displaystyle overline B rightarrow A nbsp A B displaystyle A leftrightarrow B nbsp ist dual zu A B displaystyle A dot lor B nbsp ausschliessende Disjunktion Funf Dualitatssatze Bearbeiten nbsp Hasse Diagramm das samtliche 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 uber die Zwischenaussagen hinweggehend zu denken Die blauen Pfeile markieren jeweils den Ubergang zum dualen Element Man sieht dass durch diesen Ubergang alle Implikationen umgedreht werden Dualitat von Konjunktion und Disjunktion Bearbeiten V 1 displaystyle V 1 nbsp sei eine zusammengesetzte Aussage die nur aus Konjunktionen Disjunktionen und Negationen besteht aber keine Negationsnormalform sein muss Diejenige Verknupfung V 2 displaystyle V 2 nbsp die dadurch entsteht dass bei V 1 displaystyle V 1 nbsp uberall die Konjunktionen mit den Disjunktionen und umgekehrt vertauscht werden ist dann dual zu V 1 displaystyle V 1 nbsp Beispiel A B C displaystyle A land neg B lor C nbsp ist dual zu A B C displaystyle A lor neg B land C nbsp Dualitat und Negation Bearbeiten Wenn V 1 displaystyle V 1 nbsp eine Aussage ist so erhalt man eine duale Verknupfung V 2 displaystyle V 2 nbsp wenn alle Variablen und die gesamte Verknupfung V 1 displaystyle V 1 nbsp selbst negiert werden Beispiele A B displaystyle A leftrightarrow B nbsp ist dual zu A B displaystyle overline overline A leftrightarrow overline B nbsp A B C displaystyle A land B lor C nbsp ist dual zu A B C displaystyle overline overline A land overline B lor overline C nbsp Dualitat bei Tautologie und Kontradiktion Bearbeiten Wenn eine Aussage eine Tautologie ist so ist die zu ihr duale Aussage eine Kontradiktion und umgekehrt Beispiel A B A displaystyle A land B land overline A nbsp ist eine Kontradiktion immer falsch also ist das duale A B A displaystyle A lor B lor overline A nbsp eine Tautologie immer wahr Dualitat und Implikation Bearbeiten Eine Aussage V 1 displaystyle V 1 nbsp impliziert genau dann eine Aussage V 2 displaystyle V 2 nbsp wenn eine und damit jede zu V 2 displaystyle V 2 nbsp duale Aussage eine und damit jede zu V 1 displaystyle V 1 nbsp duale Aussage impliziert Beispiel A B A displaystyle A land B Rightarrow A nbsp genau dann wenn dual gilt A A B displaystyle A Rightarrow A lor B nbsp Dualitat und Aquivalenz Bearbeiten Eine Aussage V 1 displaystyle V 1 nbsp ist genau dann aquivalent zu einer Aussage V 2 displaystyle V 2 nbsp wenn eine und damit jede zu V 1 displaystyle V 1 nbsp duale Aussage auch aquivalent zu einer und damit jeder zu V 2 displaystyle V 2 nbsp dualen Aussage ist Beispiel A B B A displaystyle A land B Leftrightarrow B land A nbsp genau dann wenn dual gilt A B B A displaystyle A lor B Leftrightarrow B lor A nbsp Siehe auch BearbeitenBoolesche AlgebraWeblinks BearbeitenDualitatsprinzip im Skriptum Einfuhrung in die Technische Informatik und Digitaltechnik Helmut Dispert FH Kiel Vorlesungsfolien Aussagenlogik und Gatter Kapitel Dualitat auf Seite 9 PDF 663 kB in den Unterlagen zur Vorlesung Digitale Schaltungstechnik Peter Fischer Universitat Mannheim Sommersemester 2006 Abgerufen von https de wikipedia org w index php title Dualitat Logik amp oldid 236919145