Aussagenlogik/Modellbeziehung/Folgerung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Aussagenlogische Interpretationen


Definition  

Es sei eine Menge von Variablen und die zugehörige aussagenlogische Sprache. Unter einer Wahrheitsbelegung versteht man eine Abbildung

(oder mit als Wertebereich).

Eine Wahrheitsbelegung ist also einfach dadurch gegeben, dass einer jeden Aussagenvariablen ein Wahrheitswert, nämlich oder bzw. oder zugeordnet wird. Eine solche Wahrheitsbelegung möchte man auf die gesamte Sprache fortsetzen, wobei die folgenden Festlegungen die inhaltliche Bedeutungen der Junktoren widerspiegeln. Die folgende Definition ist möglich, da der rekursive Aufbau einer Aussage eindeutig bestimmt ist.


Definition  

Es sei eine Menge von Variablen, die zugehörige aussagenlogische Sprache und

eine Wahrheitsbelegung. Unter der zugehörigen Interpretation versteht man die über den rekursiven Aufbau der Sprache festgelegte Abbildung

mit

  1. für jede Aussagenvariable .
  2. Bei ist
  3. Bei ist
  4. Bei ist
  5. Bei ist
  6. Bei ist

Bei

sagt man, dass der Ausdruck bei der Wahrheitsbelegung (oder der Interpretation ) wahr wird (oder gilt), andernfalls, dass er falsch wird (nicht gilt). Dafür schreibt man auch bzw. . Mit bezeichnen wir die Menge aller bei der Interpretation wahren Ausdrücke aus der Sprache. Wenn eine Menge an Ausdrücken ist, so bedeutet , dass für alle gilt. Dafür sagt man auch, dass bei der Interpretation gilt oder dass ein Modell für ist.


Beispiel  

Es sei und sei die Wahrheitsbelegung mit . Es sei die zugehörige Interpretation. Zur Berechnung des Wahrheitswertes von

unter dieser Interpretation muss man rekursiv gemäß Definition die einzelnen Bestandteile auswerten. Es ist

und somit

Also ist

Andererseits ist

und daher ist

Der Ausdruck ist also bei dieser Wahrheitsbelegung nicht wahr.




Tautologien


Definition  

Ein Ausdruck

(zu einer Menge von Aussagenvariablen ) heißt allgemeingültig (oder eine semantische Tautologie,) wenn für jede Wahrheitsbelegung die Beziehung

gilt.

Bemerkung  

Den Wahrheitswert eines Ausdrucks unter der Interpretation zu einer Belegung kann man übersichtlich berechnen, wenn man abhängig von den Variablenwerten (für die in auftretenden Variablen) sukzessive die Werte der konstituierenden Bestandteile von berechnet. Um festzustellem, ob eine Tautologie vorliegt, legt man eine Wahrheitstabelle an, bei der die Zeilen durch die möglichen Kombinationen an -Werten der einzelnen (in vorkommenden) Variablen gegeben sind. Am übersichtlichsten wird die Tabelle, wenn man sich bei der Zeilenreihenfolge an das Dualsystem hält. Bei Variablen gibt es (neben der Kopfzeile) Zeilen.



Beispiel  

Der Ausdruck

genannt Kontraposition, ist eine Tautologie (unabhängig davon, ob Aussagenvariablen oder Aussagen bezeichnen). Um dies nachzuweisen, muss man den Wahrheitswert dieses Ausdruckes bei jeder Wahrheitsbelegung berechnen, was wir mit einer Wahrheitstabelle durchführen.

Kontraposition
w w w f f w w
w f f f w f w
f w w w f w w
f f w w w w w

Dagegen ist der Ausdruck

keine Tautologie, da wir in Beispiel eine Wahrheitsbelegung mit dem Gesamtwert angegeben haben.




Definition  

Es sei eine Menge von Aussagenvariablen und die zugehörige aussagenlogische Sprache. Eine Teilmenge heißt erfüllbar, wenn es eine Wahrheitsbelegung mit zugehöriger Interpretation derart gibt, dass für alle gilt.

Diese Sprechweise verwendet man insbesondere für einen einzelnen Ausdruck .



Lemma  

Ein Ausdruck

(zu einer Menge von Aussagenvariablen )

ist genau dann eine (semantische) Tautologie, wenn nicht erfüllbar ist.

Beweis  

Wir beweisen die kontraponierte Aussage, dass genau dann keine Tautologie ist, wenn erfüllbar ist. Dass keine Tautologie vorliegt, bedeutet, dass es eine Wahrheitsbelegung derart gibt, dass

Dies bedeutet aber

was gerade die Erfüllbarkeit von besagt.



Folgerung

Definition  

Es sei eine Menge von Variablen und die zugehörige aussagenlogische Sprache. Es sei eine Teilmenge und . Man sagt, dass aus folgt, geschrieben , wenn für jede Interpretation (gegeben durch eine Wahrheitsbelegung ) mit auch gilt.