Aussagenlogik/Semantische Tautologien/Einführung/Textabschnitt

Aus Wikiversity


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 festzustellen, 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.