imported>Wassermaus: /* Darstellung boolescher Funktionen */ Link

2022-11-24T14:17:11Z

Darstellung boolescher Funktionen: Link

Neue Seite

[[Datei:Construction of a logical value table.gif|rechts|gerahmt|Animation zur Erstellung einer Wahrheitstafel]]

Eine '''Wahrheitstabelle''' oder '''Wahrheitstafel''', auch ''Wahrheitswert-Tabelle'' oder ''Wahrheitsmatrix'' genannt, ist eine [[Tabelle|tabellarische]] Aufstellung des Wahrheitswertverlaufs einer [[Logische Aussage|logischen Aussage]].

Die Wahrheitstabelle zeigt für alle möglichen Zuordnungen von endlich vielen (häufig zwei) [[Wahrheitswert]]en zu den [[Aussagenlogik|aussagenlogisch]] nicht weiter zerlegbaren Teilaussagen, aus denen die Gesamtaussage zusammengesetzt ist, welchen Wahrheitswert die Gesamtaussage unter der jeweiligen Zuordnung annimmt. Die Wahrheitstabelle wird genutzt, um [[Wahrheitswertefunktion]]en beziehungsweise [[Boolesche Algebra|boolesche Funktionen]] darzustellen oder zu definieren und um einfache aussagenlogische Nachweise zu führen. Beispielsweise werden Wahrheitstabellen verwendet, um die Bedeutung von [[Junktor]]en festzulegen.

== Darstellung boolescher Funktionen ==
Für den zweiwertigen Fall wird der Wahrheitswert „wahr“ im Folgenden als <math>w</math> und „falsch“ als <math>f</math> bezeichnet.

Für [[Mehrwertige Logik|mehrwertige]] Fälle werden oft numerische Werte im Bereich von <math>0</math> bis <math>1</math> verwendet (im dreiwertigen Fall z. B. die Werte <math>0</math>, <math>\tfrac{1}{2} = 0{,}5</math> und <math>1</math>, im fünfwertigen Fall die Werte <math>0</math>, <math>\tfrac{1}{4} = 0{,}25</math>, <math>\tfrac{1}{2} = 0{,}5</math>, <math>\tfrac{3}{4} = 0{,}75</math> und <math>1</math>). Im mehrwertigen Fall wird oft nicht von Wahrheitswerten, sondern von Quasiwahrheitswerten oder von Pseudowahrheitswerten gesprochen.

Allgemein gibt es für eine m-wertige Logik, d. h. für eine Logik mit endlich vielen Wahrheitswerten, deren Anzahl m ist, <math>m^{m^{n}}</math> n-stellige wahrheitsfunktionale Junktoren bzw. boolesche Funktionen. Für die zweiwertige Aussagenlogik gibt es also <math>2^{2^{1}}=4</math> einstellige Junktoren und <math>2^{2^{2}}=16</math> zweistellige Junktoren. Schon für die dreiwertige Aussagenlogik gibt es <math>3^{3^{1}}=27</math> einstellige und <math>3^{3^{2}}=19\,683</math> zweistellige Junktoren.

{|
|-
|style="width:20%"|
{| class="wikitable centered hintergrundfarbe2" style="text-align:center;"
|+ Negation
|-
!<math>a</math>
!<math>\lnot a</math>
|-
!w
|f
|-
!f
|w
|}
|style="width:80%"|Als ein Beispiel für eine einstellige Wahrheitswertefunktion einer zweiwertigen Logik dient hier die nebenstehende Wahrheitstafel, die das Ergebnis der Anwendung der [[Negation]] auf die Aussage <math>a</math> in der klassischen Aussagenlogik zeigt.
|}

Die folgende Tabelle gibt für jeden [[Wahrheitswert]] der [[Logische Aussage|Aussagen]] <math>a</math> und <math>b</math> das Resultat einiger zweiwertiger [[Logische Verknüpfung|Verknüpfungen]] an:
{| class="wikitable hintergrundfarbe2" style="text-align:center;"
|-
! colspan="2"| Belegung !! [[Konjunktion (Logik)|Konjunktion]] !![[Disjunktion]]!! materiale [[Implikation]] !!Äquivalenz Bikonditional
|-
!<math>a</math>
!<math>b</math>
!AND
!OR
!Konditional
!XNOR
|-
!w!!w
|w||w||w||w
|-
!w!!f
|f||w||f||f
|-
!f!!w
|f||w||w||f
|-
!f!!f
|f||f||w||w
|}
Eine besondere Stellung haben folgende nach [[Henry Maurice Sheffer]] bzw. [[Charles Sanders Peirce]] benannte zweiwertige Funktionen (siehe hierzu [[Junktor#Reduzierbarkeit und funktionale Vollständigkeit|Funktionale Vollständigkeit]] und [[Shefferscher Strich]]), denen das [[NAND-Gatter|NAND]]- und das [[NOR-Gatter]] entsprechen:
{| class="wikitable hintergrundfarbe2" style="text-align:center;"
|-
!<math>a</math>
!<math>b</math>
!Shefferscher Strich (NAND, <math>|</math>)
!Peirce-Pfeil (NOR, <math>\downarrow</math>)
|-
!w!!w
|f||f
|-
!w!!f
|w||f
|-
!f!!w
|w||f
|-
!f!!f
|w||w
|}
In einer [[Dreiwertige Logik|dreiwertigen Logik]] sind 332 = 19 683 zweistellige Verknüpfungen möglich. In der folgenden Tabelle sind zwei von ihnen dargestellt: Die Konjunktion aus der logischen Sprache Ł3 von [[Jan Łukasiewicz]] (1920) und die Konjunktion aus dem Kalkül B3 von [[Dmitrij Anatoljewitsch Botschwar|Dmitrij Anatol'evič Bočvar]] (1938).
{| class="wikitable hintergrundfarbe2" style="text-align:center;"
|-
! colspan="2"| Belegung !!colspan="2"| Konjunktion
|-
!<math>a</math>
!<math>b</math>
!in Ł3!!in B3
|-
!1!!1
|1||1
|-
!1!!½
|½||½
|-
!1!!0
|0||0
|-
!½!!1
|½||½
|-
!½!!½
|½||½
|-
!½!!0
|0||½
|-
!0!!1
|0||0
|-
!0!!½
|0||½
|-
!0!!0
|0||0
|}
Eine vierwertige Logik hat bis zu <math>4^{4^{2}}=4\,294\,967\,296</math> mögliche zweistelligen Operatoren. Hier als Beispiel die Wahrheitstafel für das [[Implikation|Konditional]] bzw. die materiale Implikation im logischen System G4 von [[Kurt Gödel]] (1932).
{| class="wikitable hintergrundfarbe2" style="text-align:center;"
|-
! colspan="2"|Belegung!!Konditional
|-
!<math>a</math>
!<math>b</math>
!in G4
|-
!1!!1
|1
|-
!1!!{{Bruch|2|3}}
|{{Bruch|2|3}}
|-
!1!!{{Bruch|1|3}}
|{{Bruch|1|3}}
|-
!1!!0
|0
|-
!{{Bruch|2|3}}!!1
|1
|-
!{{Bruch|2|3}}!!{{Bruch|2|3}}
|1
|-
!{{Bruch|2|3}}!!{{Bruch|1|3}}
|{{Bruch|1|3}}
|-
!{{Bruch|2|3}}!!0
|0
|-
!{{Bruch|1|3}}!!1
|1
|-
!{{Bruch|1|3}}!!{{Bruch|2|3}}
|1
|-
!{{Bruch|1|3}}!!{{Bruch|1|3}}
|1
|-
!{{Bruch|1|3}}!!0
|0
|-
!0!!1
|1
|-
!0!!{{Bruch|2|3}}
|1
|-
!0!!{{Bruch|1|3}}
|1
|-
!0!!0
|1
|}

== Beweis- und Entscheidungsverfahren ==
Wahrheitstabellen eignen sich dazu, einfache aussagenlogische Beweise auf der semantischen Modellebene zu führen, insbesondere für die Gültigkeit von grundlegenden Gesetzen, auf denen logische Beweisverfahren aufbauen. Zum Beispiel zeigt die [[logische Äquivalenz]] der 3. und 4. Spalte in den folgenden Wahrheitstabellen die Gültigkeit der [[De Morgansche Gesetze|De Morganschen Gesetze]]:
{| class="centered"
|-
! <math>\lnot (a \land b) = (\lnot a) \lor(\lnot b)</math>
! <math>\lnot (a \lor b) = (\lnot a) \land (\lnot b)</math>
|-
|
{| class="wikitable hintergrundfarbe2"
|-
!<math>a</math>
!<math>b</math>
!<math>\lnot (a \land b)</math>
!<math>(\lnot a) \lor(\lnot b)</math>
|-
!w!!w
|f||f
|-
!w!!f
|w||w
|-
!f!!w
|w||w
|-
!f!!f
|w||w
|}
|
{| class="wikitable hintergrundfarbe2"
|-
!<math>a</math>
!<math>b</math>
!<math>\lnot (a \lor b)</math>
!<math>(\lnot a) \land (\lnot b)</math>
|-
!w!!w
|f||f
|-
!w!!f
|f||f
|-
!f!!w
|f||f
|-
!f!!f
|w||w
|}
|}

In der Praxis eignet sich diese Art der Beweisführung allerdings nur für Aussagen mit einer kleinen Anzahl von Aussagenvariablen, da die Größe exponentiell mit der Anzahl der Variablen wächst.

Für die [[Aussagenlogik]] mit endlich vielen Wahrheitswerten und klassischem Folgerungsbegriff (siehe [[Klassische Logik]]) sind Wahrheitstafeln ein Entscheidungsverfahren für viele wichtige Fragestellungen, das heißt ein Verfahren, mit dem sich die jeweilige Fragestellung für jede Aussage in endlicher Zeit mechanisch entscheiden lässt. So lässt sich mit Hilfe von Wahrheitstafeln die Frage entscheiden, ob eine gegebene Aussage erfüllbar, unerfüllbar oder [[Tautologie (Logik)|tautologisch]] ist (siehe [[Erfüllbarkeitsproblem der Aussagenlogik]]); ebenso lässt sich entscheiden, ob ein Argument gültig oder ungültig ist.

== Umformung in andere Darstellungsformen ==
Der Inhalt einer Wahrheitstabelle kann zur weiteren Verarbeitung oder Vereinfachung in andere, äquivalente Darstellungen überführt werden, beispielsweise in ein [[Karnaugh-Veitch-Diagramm]].

== Eine Alternative: Wahrheitswertanalyse nach Quine ==
Wahrheitstabellen sind in vielen Fällen eine rationelle und einfach zu handhabende Methode der Wahrheitswertanalyse. Sie haben jedoch den Nachteil, dass immer alle Fälle durchgegangen werden müssen. Die Anzahl der Fälle steigt aber mit der Anzahl der Variablen (Satzbuchstaben) im Verhältnis <math>2^n</math> an. Bei 2 Variablen gibt es 4 Fälle, bei 3 Variablen 8 Fälle, bei 4 Variablen 16 Fälle usw. Bei vielen Variablen kann die Wahrheitswertanalyse durch Wahrheitstabellen recht aufwändig werden.

Deshalb schlägt [[Willard Van Orman Quine|Quine]] in seinem Buch ''Grundzüge der Logik''<ref>{{Literatur |Autor=Quine, Willard Van Orman |Titel=Grundzüge der Logik |Auflage=6. |Verlag=Suhrkamp |Ort=Frankfurt am Main |Datum=1988 |ISBN=3-518-27665-4 |Seiten=49–56 |Kommentar=§5 Wahrheitswertanalyse}}</ref> eine alternative Form der Wahrheitswertanalyse vor. Auf Seite 54 gibt Quine das folgende Beispiel mit drei Variablen bzw. Satzbuchstaben (P, Q und R):

{{Stammbaum/Start |style=margin:1em;}}
{{Stammbaum|border=0| | | | | | | | | A | | | | | | | | |A=(P ∧ Q) ∨ (¬P ∧ ¬R) → (Q ↔ R)}}
{{Stammbaum|border=0| | | | | B | | | | | | C | | | | |B=(w ∧ Q) ∨ (f ∧ ¬R) → (Q ↔ R)|C=(f ∧ Q) ∨ (w ∧ ¬R) → (Q ↔ R)}}
{{Stammbaum|border=0| | | | | D | | | | | | E | | | | |D=Q
 ∨ (f ∧ ¬R) → (Q ↔ R)|E=f ∨
 (w ∧ ¬R) → (Q ↔ R)}}
{{Stammbaum|border=0| | | | | F | | | | | | G | | | | |F=(Q ∨ f) → (Q ↔ R)|G=(w ∧ ¬R) → (Q ↔ R)}}
{{Stammbaum|border=0| | | | | H | | | | | | I | | | | |H=Q → (Q ↔ R)|I=¬R → (Q ↔ R)}}
{{Stammbaum|border=0| | | J | | K | | L | | M | | |J=w → (w ↔ R)|K=f → (f ↔ R)|L=f → (Q ↔ w)|M=w → (Q ↔ f)}}
{{Stammbaum|border=0| | | N | | O | | P | | Q | | |N=w ↔ R|O=w|P=w|Q=Q ↔ f}}
{{Stammbaum|border=0| | | R | | | | | | | | | | S | | |R=R|S=¬Q}}
{{Stammbaum|border=0| T | | U | | | | | | V | | W |T=w|U=f|V=f|W=w|boxstyle_T =background-color:#afa;|boxstyle_U ="text-align:left"|boxstyle_V ="text-align:right"|boxstyle_W ="text-align:left"}}
{{Stammbaum/Ende}}

Der Beispielterm (P ∧ Q) ∨ (¬P ∧ ¬R) → (Q ↔ R) ist also in zwei Fällen falsch: bei P/w|Q/w|R/f und bei P/f|Q/w|R/f. Die Wahrheitstabelle dazu sieht so aus:

{| class="wikitable hintergrundfarbe2" style="text-align:center;"
|-
! P !! Q !! R !! (P !! ∧ !! Q) !! ∨ !! (¬P !! ∧ !! ¬R) !! → !! (Q !! ↔ !! R)
|-
! w !! w !! w
| w || w || w || ''w'' || f || f || f || '''w''' || w || ''w'' || w
|-
! w !! w !! f
| w || w || w || ''w'' || f || f || w || '''f''' || w || ''f'' || f
|-
! w !! f !! w
| w || f || f || ''f'' || f || f || f || '''w''' || f || ''f'' || w
|-
! w !! f !! f
| w || f || f || ''f'' || f || f || w || '''w''' || f || ''w'' || f
|-
! f !! w !! w
| f || f || w || ''f'' || w || f || f || '''w''' || w || ''w'' || w
|-
! f !! w !! f
| f || f || w || ''w'' || w || w || w ||'''f''' || w || ''f'' || f
|-
! f !! f !! w
| f || f || f || ''f'' || w || f || f || '''w''' || f || ''f'' || w
|-
! f !! f !! f
| f || f || f || ''w'' || w || w || w || '''w''' || f || ''w'' || f
|-
|}

Ein einfacheres Beispiel ist die Definition der Implikation:

(A → B) ↔ (¬A ∨ B)

Die Wahrheitstabelle dazu sieht so aus:

{| class="wikitable hintergrundfarbe2" style="text-align:center;"
|-
! A
! B !! (A !! → !! B) !! ↔ !! (¬A !! ∨ !! B)
|-
! w !! w
|class="hintergrundfarbe2" style="text-align:center;"| w || ''w'' || w || '''w''' || f || ''w'' || w
|-
! w !! f
| w || ''f'' || f || '''w''' || f || ''f'' || f
|-
! f !! w
| f || ''w'' || w || '''w''' || w || ''w'' || w
|-
! f !! f
| f || ''w'' || f || '''w''' || w || ''w'' || f
|-
|}

Die Wahrheitswertanalyse nach Quine sieht bei diesem Beispiel so aus:

{{Stammbaum/Start |style=margin:1em;}}
{{Stammbaum|border=0| | | | | | AB | | | |AB=(A → B) ↔ (¬A ∨ B)}}
{{Stammbaum|border=0| | | WB | | | | fB |WB=(w → B) ↔ (f ∨ B)|fB=(f → B) ↔ (w ∨ B)}}
{{Stammbaum|border=0| ww1 | | wf | | ww2 |ww1=(w → w) ↔ (f ∨ w)|wf=(w → f) ↔ (f ∨ f)|ww2=(w ↔ w)}}
{{Stammbaum|border=0| ww | | ff | | w |ww=(w → w)|ff=(f ↔ f)|w=w}}
{{Stammbaum|border=0| w1 | | w2 | | | | |w1=w|w2=w}}
{{Stammbaum/Ende}}

Bei der von Quine vorgeschlagenen Methode der Wahrheitswertanalyse werden die Variablen bzw. Satzbuchstaben also schrittweise durch ihre Wahrheitswerte ersetzt. Dabei werden dann zeilenweise Fallunterscheidungen vorgenommen, so dass eine baumartige Struktur entsteht. In beiden Beispielen, dem von Quine und der Definition der Implikation, ist auch zu sehen, dass nicht immer alle Fälle durchgegangen werden müssen, was bei vielen Variablen ein Vorteil gegenüber Wahrheitstabellen sein kann. Durch beide Methoden können die Fälle, in denen ein Term wahr bzw. falsch wird exakt ermittelt werden. Daher leisten beide Methoden dasselbe, sind also äquivalent.

== Zur Geschichte ==
Wenn man unter einer Wahrheitstabelle die homomorphe Zuordnung von Wahrheitswerten zu den in einer Aussage vorkommenden [[Aussage (Logik)|atomaren Aussagen]] versteht, dann geht die Wahrheitstabelle auf [[Philon von Megara]] zurück, der auf diese Weise im [[4. Jahrhundert v. Chr.|4. Jahrhundert vor unserer Zeitrechnung]] die Wahrheitsfunktion für die materiale [[Implikation]] definierte.<ref>{{" |Sprache=en |Text=The device of tabulation was not introduced until recently, but the idea of truth-functional dependence was obviously quite clear to Philo. |Quelle={{Literatur |Autor=Martha Kneale, [[William Kneale]] |Titel=The Development of Logic |Verlag=Clarendon Press |Datum=1962 |ISBN=0-19-824773-7 |Seiten=130 |Sprache=en}}}}; in diesem Sinne auch Bocheński {{" |in Anlehnung an die Antike |3={{Literatur |Autor=Bocheński |Titel=Formale Logik |Auflage=2 |Datum=1962 |Seiten=384 ff.}}}}</ref> Auch in der von [[Chrysippos von Soloi]] geprägten [[Stoa|stoischen Logik]] wurden Wahrheitstabellen in diesem Sinn umfassend verwendet.<ref>{{" |Sprache=en |Text=The Stoics gave truth-functional definitions of all the more important propositional connectives […] |Quelle={{Literatur |Autor=[[Benson Mates]] |Titel=Stoic Logic |Reihe=University of California Publications in Philosophy |NummerReihe=26 |Verlag=University of California Press |Ort=Berkeley |Datum=1953 |ISBN=0-520-02368-4 |Seiten=42 |Sprache=en |Kommentar=ISBN des Nachdrucks von 1973}}}}</ref>

In der modernen Logik benutzte [[George Boole]] 1847 Wahrheitstafeln unter dem Namen „Module einer Funktion“ zur semantischen Entscheidbarkeit von logischen Termen (Funktionen).<ref>{{Literatur |Autor=Boole |Titel=The Mathematical Analysis of Logic |Datum=1847 |Seiten=60 ff.}}</ref> Später benützten auch [[Gottlob Frege]] und [[Charles Sanders Peirce]] dieses Entscheidungsverfahren, wobei Peirce den Zweck der Ermittlung von [[Tautologie (Logik)|Tautologien]] deutlicher betonte. Wahrheitstabellen im wörtlichen Sinn als Tabellen wurden allerdings erst 1921 von [[Emil Leon Post]]<ref>{{Literatur |Autor=Emil Leon Post |Titel=Introduction to a General Theory of Elementary Propositions |Sammelwerk=American Journal of Mathematics |Band=43 |Datum=1921 |Seiten=163–185}}</ref> und [[Ludwig Wittgenstein]]<ref>{{Literatur |Autor=Ludwig Wittgenstein |Titel=Tractatus Logico-Philosophicus |Datum=1921 |Kommentar=Abschnitt 4.31}}</ref> eingeführt; durch ihren Einfluss wurden Wahrheitstabellen als Verfahren zur Entscheidung für Tautologien Allgemeingut.

== Literatur ==
* {{Literatur
|Autor=[[Martha Kneale]], [[William Kneale]]
|Titel=The Development of Logic
|Verlag=Clarendon Press
|Datum=1962
|ISBN=0-19-824773-7
|Sprache=en
|Kommentar=zur Geschichte}}

== Weblinks ==
{{Wikibooks|Mathe für Nicht-Freaks: Wahrheitstabelle}}
* [http://www.p-roocks.de/truthtable2.php PHP-Script zur Ausgabe von Wahrheitstafeln] (Open Source)
* [http://www.duplexnegatioaffirmat.de/wahrheitstafel-trainer/ Wahrheitstafel-Trainer] in JavaScript

== Einzelnachweise ==
<references />

[[Kategorie:Logik]]
[[Kategorie:Sprachphilosophie]]
[[Kategorie:Digitale Schaltungstechnik]]
[[Kategorie:Schaltalgebra]]
[[Kategorie:Aussagenlogik]]

Wahrheitstabelle - Versionsgeschichte

imported>Wassermaus: /* Darstellung boolescher Funktionen */ Link