Aussagenlogik/Semantische Tautologien/Einführung/Textabschnitt

Definition

Ein Ausdruck ${}\alpha \in L^{V}$ (zu einer Menge von Aussagenvariablen ${}V$) heißt allgemeingültig (oder eine semantische Tautologie,) wenn für jede Wahrheitsbelegung ${}\lambda$ die Beziehung

${}I^{\lambda }(\alpha )=1\,$

gilt.

Bemerkung  

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

Beispiel

Der Ausdruck

${}\varphi =(\alpha \rightarrow \beta )\leftrightarrow (\neg \beta \rightarrow \neg \alpha )\,,$

genannt Kontraposition, ist eine Tautologie (unabhängig davon, ob ${}\alpha ,\beta$ 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
${}\alpha$ ${}\beta$ ${}\alpha \rightarrow \beta$ ${}\neg \alpha$ ${}\neg \beta$ ${}\neg \beta \rightarrow \neg \alpha$ ${}(\alpha \rightarrow \beta )\leftrightarrow (\neg \beta \rightarrow \neg \alpha )$ 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

${}\varphi ={\left(\neg {\left((p)\wedge (\neg (q))\right)}\right)}\rightarrow (r)\,$

keine Tautologie, da wir in Beispiel eine Wahrheitsbelegung mit dem Gesamtwert ${}f$ angegeben haben.

Definition

Es sei ${}V$ eine Menge von Aussagenvariablen und ${}L^{V}$ die zugehörige aussagenlogische Sprache. Eine Teilmenge ${}\Gamma \subseteq L^{V}$ heißt erfüllbar, wenn es eine Wahrheitsbelegung ${}\lambda$ mit zugehöriger Interpretation ${}I$ derart gibt, dass ${}I(\alpha )=1$ für alle ${}\alpha \in \Gamma$ gilt.

Diese Sprechweise verwendet man insbesondere für einen einzelnen Ausdruck ${}\alpha \in \Gamma ^{V}$.

Lemma

Ein Ausdruck ${}\alpha \in L^{V}$ (zu einer Menge von Aussagenvariablen ${}V$)

ist genau dann eine (semantische) Tautologie, wenn ${}\neg \alpha$ nicht erfüllbar ist.

Beweis

Wir beweisen die kontraponierte Aussage, dass ${}\alpha$ genau dann keine Tautologie ist, wenn ${}\neg \alpha$ erfüllbar ist. Dass keine Tautologie vorliegt, bedeutet, dass es eine Wahrheitsbelegung ${}\lambda$ derart gibt, dass

${}I^{\lambda }(\alpha )=0\,.$

Dies bedeutet aber

${}I^{\lambda }(\neg \alpha )=1\,,$

was gerade die Erfüllbarkeit von ${}\neg \alpha$ besagt.

$\Box$