Wahrheitsfunktion - Truth function

In der Logik ist eine Wahrheitsfunktion eine Funktion , die Wahrheitswerte als Eingabe akzeptiert und einen eindeutigen Wahrheitswert als Ausgabe erzeugt. Mit anderen Worten: Die Eingabe und Ausgabe einer Wahrheitsfunktion sind alle Wahrheitswerte; Eine Wahrheitsfunktion gibt immer genau einen Wahrheitswert aus. und die Eingabe des gleichen Wahrheitswertes (der gleichen Wahrheitswerte) gibt immer den gleichen Wahrheitswert aus. Das typische Beispiel ist die Aussagenlogik , bei der eine zusammengesetzte Anweisung unter Verwendung einzelner Anweisungen konstruiert wird, die durch logische Verknüpfungen verbunden sind ; Wenn der Wahrheitswert der zusammengesetzten Aussage vollständig durch den Wahrheitswert (die Wahrheitswerte) der konstituierenden Aussage (n) bestimmt wird, wird die zusammengesetzte Aussage als Wahrheitsfunktion bezeichnet , und alle verwendeten logischen Verknüpfungen werden als wahrheitsfunktional bezeichnet .

Klassische Aussagenlogik ist insofern eine wahrheitsfunktionale Logik, als jede Aussage genau einen Wahrheitswert hat, der entweder wahr oder falsch ist, und jeder logische Zusammenhang wahrheitsfunktional ist (mit einer entsprechenden Wahrheitstabelle ), so dass jede zusammengesetzte Aussage eine Wahrheitsfunktion ist. Andererseits ist die Modallogik nicht wahrheitsfunktional.

Überblick

Ein logischer Zusammenhang ist wahrheitsfunktional, wenn der Wahrheitswert eines zusammengesetzten Satzes eine Funktion des Wahrheitswertes seiner Untersätze ist. Eine Klasse von Konnektiven ist wahrheitsfunktional, wenn jedes ihrer Mitglieder es ist. Zum Beispiel ist das Bindeglied " und " wahrheitsfunktional, da ein Satz wie " Äpfel sind Obst und Karotten sind Gemüse " nur dann wahr ist, wenn jeder seiner Untersätze " Äpfel sind Früchte " und " Karotten sind Gemüse " ist wahr, und sonst ist es falsch. Einige Konnektiva einer natürlichen Sprache, wie z. B. Englisch, sind nicht wahrheitsfunktional.

Konnektive der Form "x glaubt, dass ..." sind typische Beispiele für Konnektive, die nicht wahrheitsfunktional sind. Wenn z. B. Mary fälschlicherweise glaubt, dass Al Gore am 20. April 2000 Präsident der USA war, sie aber nicht glaubt, dass der Mond aus grünem Käse besteht, dann das Urteil

" Mary glaubt, dass Al Gore am 20. April 2000 Präsident der USA war "

ist wahr während

" Mary glaubt, dass der Mond aus grünem Käse besteht "

ist falsch. In beiden Fällen ist jeder einzelne Satz (dh " Al Gore war am 20. April 2000 Präsident der USA " und " der Mond besteht aus grünem Käse ") falsch, aber jeder zusammengesetzte Satz, der durch das Präfixieren des Ausdrucks " Mary glaubt das" gebildet wird "unterscheidet sich im Wahrheitswert. Das heißt, der Wahrheitswert eines Satzes der Form " Mary glaubt, dass ... " wird nicht nur durch den Wahrheitswert seines Teilsatzes und damit durch den (unären) Zusammenhang (oder einfach den Operator, da er unär ist) bestimmt ) ist nicht wahrheitsfunktional.

Die Klasse der klassischen Logikverbindungen (z. B. & , ), die bei der Konstruktion von Formeln verwendet wird, ist wahrheitsfunktional. Ihre Werte für verschiedene Wahrheitswerte als Argument werden normalerweise durch Wahrheitstabellen angegeben . Der wahrheitsfunktionale Satzkalkül ist ein formales System, dessen Formeln entweder als wahr oder falsch interpretiert werden können.

Tabelle der binären Wahrheitsfunktionen

In Zwei-Werte - Logik gibt es sechzehn mögliche Wahrheitsfunktionen, die auch als Booleschen Funktionen , von zwei Eingängen P und Q . Jede dieser Funktionen entspricht einer Wahrheitstabelle eines bestimmten logischen Zusammenhangs in der klassischen Logik, einschließlich mehrerer entarteter Fälle, beispielsweise einer Funktion, die nicht von einem oder beiden Argumenten abhängt. Wahrheit und Falschheit werden in den folgenden Wahrheitstabellen der Kürze halber als 1 bzw. 0 bezeichnet.

Widerspruch / Falsch
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm

"Unterseite"
P ∧ ¬ P
O pq
  Q.
0 1
P. 0    0   0 
1    0   0 
Venn0000.svg


Tautologie / Richtig
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm

"oben"
P ∨ ¬ P
V pq
  Q.
0 1
P. 0    1   1 
1    1   1 
Venn1111.svg


Satz P.
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P. p
I pq
  Q.
0 1
P. 0    0   0 
1    1   1 
Venn0101.svg


Negation von P.
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
¬ P
~ P.
N p
F pq
  Q.
0 1
P. 0    1   1 
1    0   0 
Venn1010.svg


Satz Q.
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
Q. q
H pq
  Q.
0 1
P. 0    0   1 
1    0   1 
Venn0011.svg


Negation von Q.
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
¬ Q
~ Q.
N q
G pq
  Q.
0 1
P. 0    1   0 
1    1   0 
Venn1100.svg


Verbindung
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P & Q
P   ·   Q
P  UND  Q.
P ¬ Q
¬ P Q
¬ P ↓ ¬ Q
K pq
  Q.
0 1
P. 0    0   0 
1    0   1 
Venn0001.svg


Alternative Ablehnung
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P | Q
P  NAND  Q.
P → ¬ Q
¬ P Q
¬ P Q
D pq
  Q.
0 1
P. 0    1   1 
1    1   0 
Venn1110.svg


Disjunktion
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P  OR  Q.
P ← ¬ Q
¬ P Q
¬ P ↑ ¬ Q
¬ (¬ P Q )
A pq
  Q.
0 1
P. 0    0   1 
1    1   1 
Venn0111.svg


Gemeinsame Ablehnung
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P  NOR  Q.
P ¬ ¬ Q
¬ P Q
¬ P ¬ Q
X pq
  Q.
0 1
P. 0    1   0 
1    0   0 
Venn1000.svg


Materielle Nichtimplikation
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P Q P Q.
P Q ¬ Q
¬ P Q
¬ P ¬ Q
L pq
  Q.
0 1
P. 0    0   0 
1    1   0 
Venn0100.svg


Materielle Implikation
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P Q
P Q.
P ↑ ¬ Q
¬ P Q
¬ P ← ¬ Q
C pq
  Q.
0 1
P. 0    1   1 
1    0   1 
Venn1011.svg


Umgekehrte Nichtimplikation
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P Q P Q.
P ↓ ¬ Q
¬ P Q
¬ P ¬ Q
M pq
  Q.
0 1
P. 0    0   1 
1    0   0 
Venn0010.svg


Umgekehrte Implikation
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P Q
P Q.
P Q ¬ Q
¬ P Q
¬ P → ¬ Q
B pq
  Q.
0 1
P. 0    1   0 
1    1   1 
Venn1101.svg


Exklusive Disjunktion
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q
P Q
P Q
P  XOR  Q.
P ¬ Q ¬ P Q ¬ PQ J pq


  Q.
0 1
P. 0    0   1 
1    1   0 
Venn0110.svg


Biconditional
Notation Äquivalente
Formeln
Wahrheitstabelle Venn-Diagramm
P Q PQ P  XNOR  Q P  IFF  Q.


P ¬ ¬ Q
¬ P Q
¬ P ¬ Q E pq
  Q.
0 1
P. 0    1   0 
1    0   1 
Venn1001.svg


Funktionale Vollständigkeit

Da eine Funktion als Komposition ausgedrückt werden kann , muss ein wahrheitsfunktionaler logischer Kalkül nicht über dedizierte Symbole verfügen, damit alle oben genannten Funktionen funktional vollständig sind . Dies wird in einem Satzkalkül als logische Äquivalenz bestimmter zusammengesetzter Aussagen ausgedrückt . Zum Beispiel hat die klassische Logik ¬ P  ∨  Q äquivalent zu P  →  Q . Der bedingte Operator "→" ist daher für ein klassisches logisches System nicht erforderlich , wenn "¬" (nicht) und "∨" (oder) bereits verwendet werden.

Eine minimale Menge von Operatoren, die jede im Satzkalkül ausdrückbare Aussage ausdrücken können , wird als minimale funktional vollständige Menge bezeichnet . Ein minimal vollständiger Satz von Operatoren wird durch NAND allein {↑} und NOR allein {↓} erreicht.

Das Folgende sind die minimalen funktional vollständigen Sätze von Operatoren, deren Aritäten 2 nicht überschreiten:

Ein Element
{↑}, {↓}.
Zwei Elemente
, , , , , , , , , , , , , , , , , .
Drei Elemente
, , , , , .

Algebraische Eigenschaften

Einige Wahrheitsfunktionen besitzen Eigenschaften, die in den Theoremen ausgedrückt werden können, die den entsprechenden Zusammenhang enthalten. Einige dieser Eigenschaften, die eine binäre Wahrheitsfunktion (oder eine entsprechende logische Verbindung) haben kann, sind:

  • Assoziativität : Innerhalb eines Ausdrucks, der zwei oder mehr der gleichen assoziativen Konnektiva hintereinander enthält, spielt die Reihenfolge der Operationen keine Rolle, solange die Reihenfolge der Operanden nicht geändert wird.
  • Kommutativität : Die Operanden des Konnektivs können ausgetauscht werden, ohne den Wahrheitswert des Ausdrucks zu beeinflussen.
  • Verteilungsfähigkeit : Eine mit · bezeichnete Konnektivität verteilt sich über eine andere mit + bezeichnete Konnektivität, wenn a · ( b + c ) = ( a · b ) + ( a · c ) für alle Operanden a , b , c .
  • idempotence : Immer wenn die Operanden der Operation gleich sind, gibt der Konnektiv den Operanden als Ergebnis an. Mit anderen Worten, die Operation bewahrt sowohl die Wahrheit als auch die Falschheit (siehe unten).
  • Absorption : Ein Verbindungspaar erfüllt das Absorptionsgesetz, wenn für alle Operanden a , b .

Eine Reihe von Wahrheitsfunktionen ist genau dann funktional vollständig, wenn sie für jede der folgenden fünf Eigenschaften mindestens ein Mitglied enthält, dem sie fehlt:

  • monoton : Wenn f ( a 1 , ..., a n ) ≤ f ( b 1 , ..., b n ) für alle a 1 , ..., a n , b 1 , ..., b n ∈ {0,1} so dass a 1 b 1 , a 2 b 2 , ..., a n b n . ZB , .
  • affin : Wenn Sie für jede Variable ihren Wert entweder immer oder nie ändern, ändert sich der Wahrheitswert der Operation für alle festen Werte aller anderen Variablen. Zum Beispiel , .
  • self dual : Das Lesen der Wahrheitswertzuweisungen für die Operation von oben nach unten in der Wahrheitstabelle entspricht dem Lesen von unten nach oben. mit anderen Worten, f a 1 , ..., ¬ a n ) = ¬ f ( a 1 , ..., a n ). ZB , .
  • Wahrheitserhaltung : Die Interpretation, bei der allen Variablen der Wahrheitswert "wahr" zugewiesen wird , erzeugt als Ergebnis dieser Operationen einen Wahrheitswert von "wahr". ZB , . (siehe Gültigkeit )
  • Falschheitserhaltung : Die Interpretation, bei der allen Variablen der Wahrheitswert 'falsch' zugewiesen wird , ergibt als Ergebnis dieser Operationen einen Wahrheitswert von 'falsch'. ZB , . (siehe Gültigkeit )

Arity

Eine konkrete Funktion kann auch als Operator bezeichnet werden . In zweiwertig Logik gibt es 2 nullary Operatoren (Konstanten), 4 unäre Operatoren , 16 binäre Operatoren , 256 ternäre Operatoren und n - ary Operatoren. In dreiwertige Logik gibt es 3 nullary Operatoren (Konstanten), 27 unäre Operatoren , 19683 binäre Operatoren , 7625597484987 ternäre Operatoren und n - ary Operatoren. In der k- bewerteten Logik gibt es k Nulloperatoren, unäre Operatoren, binäre Operatoren, ternäre Operatoren und n- Operatoren. Ein n -ary-Operator in k- bewerteter Logik ist eine Funktion von . Daher ist die Anzahl solcher Operatoren , wie die obigen Zahlen abgeleitet wurden.

Einige der Operatoren einer bestimmten Arität sind jedoch tatsächlich entartete Formen, die an einigen Eingaben eine Operation mit niedrigerer Arität ausführen und den Rest der Eingaben ignorieren. Von den 256 oben genannten ternären Booleschen Operatoren sind solche entartete Formen von binären Operatoren oder Operatoren mit niedrigerer Arität, die das Einschluss-Ausschluss-Prinzip verwenden . Der ternäre Operator ist ein solcher Operator, der tatsächlich ein unärer Operator ist, der auf eine Eingabe angewendet wird und die anderen beiden Eingaben ignoriert.

"Nicht" ist ein unärer Operator , er benötigt einen einzelnen Term (¬ P ). Der Rest sind binäre Operatoren , die zwei Terme verwenden, um eine zusammengesetzte Aussage zu treffen ( P Q , P Q , P Q , P Q ).

Der Satz von logischen Operatoren Ω kann aufgeteilt in getrennten Sub - Sätze wie folgt:

In dieser Partition befindet sich die Menge der Operatorsymbole der Arität j .

In den bekannteren Aussagenkalkülen wird typischerweise wie folgt aufgeteilt:

Nulloperatoren:
unäre Operatoren:
binäre Operatoren:

Prinzip der Komposition

Anstatt Wahrheitstabellen zu verwenden , können logische Verbindungssymbole mittels einer Interpretationsfunktion und eines funktional vollständigen Satzes von Wahrheitsfunktionen interpretiert werden (Gamut 1991), wie dies durch das Prinzip der Kompositionalität der Bedeutung detailliert beschrieben wird . Sei ich eine Interpretationsfunktion, sei Φ , Ψ zwei beliebige Sätze und sei die Wahrheitsfunktion f n und definiert als:

  • f n und (T, T) = F; f NAND- (T, f) = f NAND- (F, T) = f NAND- (F, F) = T

Dann sind der Einfachheit halber f nicht , f oder f und usw. werden mittels definierten f nand :

  • f nicht ( x ) = f n und ( x , x )
  • f oder ( x , y ) = f n und ( f nicht ( x ), f nicht ( y ))
  • f und ( x , y ) = f nicht ( f n und ( x , y ))

oder alternativ f nicht , f oder f und usw. werden direkt definiert:

  • f nicht (T) = F; f nicht (F) = T;
  • f oder (T, T) = f oder (T, F) = f oder (F, T) = T; f oder (F, F) = F.
  • f und (T, T) = T; f und (T, F) = f und (F, T) = f und (F, F) = F.

Dann

  • I (~) = I ( ) = f nicht
  • I (&) = I ( ) = f und
  • I ( v ) = I ( ) = f oder
  • I (~ Φ ) = I ( Φ ) = I ( ) ( I ( Φ )) = f nicht ( I ( Φ ))
  • I ( Φ Ψ ) = I ( ) ( I ( Φ ), I ( Ψ )) = f und ( I ( Φ ), I ( Ψ ))

usw.

Wenn also S ein Satz ist, der eine Folge von Symbolen ist, die aus logischen Symbolen v 1 ... v n, die logische Verknüpfungen darstellen, und nicht logischen Symbolen c 1 ... c n bestehen , dann genau dann, wenn I ( v 1 ) ... I ( v n ) wurde bereitgestellt, indem v 1 bis v n mittels f nand (oder einer anderen Menge funktionaler vollständiger Wahrheitsfunktionen) interpretiert wurden, dann wird der Wahrheitswert von vollständig durch die Wahrheitswerte von c bestimmt 1 ... c n , dh von I ( c 1 ) ... I ( c n ) . Mit anderen Worten, wie erwartet und erforderlich, ist S nur unter Interpretation aller seiner nicht logischen Symbole wahr oder falsch.

Informatik

Logische Operatoren sind als Logikgatter in digitalen Schaltungen implementiert . Praktisch alle digitalen Schaltungen (die Hauptausnahme ist DRAM ) werden aus NAND- , NOR- , NOT- und Übertragungsgattern aufgebaut . NAND- und NOR-Gatter mit 3 oder mehr Eingängen anstelle der üblichen 2 Eingänge sind ziemlich häufig, obwohl sie logisch einer Kaskade von Gattern mit 2 Eingängen entsprechen. Alle anderen Operatoren werden implementiert, indem sie in eine logisch äquivalente Kombination von 2 oder mehr der obigen Logikgatter zerlegt werden.

Die "logische Äquivalenz" von "NAND allein", "NOR allein" und "NICHT und UND" ähnelt der Turing-Äquivalenz .

Die Tatsache, dass alle Wahrheitsfunktionen nur mit NOR ausgedrückt werden können, wird vom Apollo-Leitcomputer demonstriert .

Siehe auch

Anmerkungen

Verweise

Weiterführende Literatur

  • Józef Maria Bocheński (1959), Ein Précis der mathematischen Logik , übersetzt aus der französischen und deutschen Version von Otto Bird, Dordrecht, Südholland: D. Reidel.
  • Alonzo Church (1944), Einführung in die mathematische Logik , Princeton, NJ: Princeton University Press. In der Einführung finden Sie eine Geschichte des Wahrheitsfunktionskonzepts.