Aussagenlogik/Modellbeziehung/Folgerung/Textabschnitt

Aussagenlogische Interpretationen

Definition

Es sei ${}V$ eine Menge von Variablen und ${}L^{V}$ die zugehörige aussagenlogische Sprache. Unter einer Wahrheitsbelegung versteht man eine Abbildung

$\lambda \colon V\longrightarrow \{0,1\}$

(oder mit ${}\{f,w\}$ als Wertebereich).

Eine Wahrheitsbelegung ist also einfach dadurch gegeben, dass einer jeden Aussagenvariablen ein Wahrheitswert, nämlich ${}0$ oder ${}1$ bzw. ${}f$ oder ${}w$ 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 ${}V$ eine Menge von Variablen, ${}L^{V}$ die zugehörige aussagenlogische Sprache und

$\lambda \colon V\longrightarrow \{0,1\}$

eine Wahrheitsbelegung. Unter der zugehörigen Interpretation ${}I=I^{\lambda }$ versteht man die über den rekursiven Aufbau der Sprache festgelegte Abbildung

$I\colon L^{V}\longrightarrow \{0,1\}$

mit

1. ${}I(v)=\lambda (v)$ für jede Aussagenvariable ${}v\in V$.
2. Bei ${}\alpha =\neg (\beta )$ ist

   ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0\,,\\0,{\text{ falls }}I(\beta )=1\,.\end{cases}}\,$

3. Bei ${}\alpha =(\beta )\wedge (\gamma )$ ist

   ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )=1\,,\\0{\text{ sonst}}\,.\end{cases}}\,$

4. Bei ${}\alpha =(\beta )\vee (\gamma )$ ist

   ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=1{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=I(\gamma )=0\,.\end{cases}}\,$

5. Bei ${}\alpha =(\beta )\rightarrow (\gamma )$ ist

   ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=0{\text{ oder }}I(\gamma )=1\,,\\0,{\text{ falls }}I(\beta )=1{\text{ und }}I(\gamma )=0\,.\end{cases}}\,$

6. Bei ${}\alpha =(\beta )\leftrightarrow (\gamma )$ ist

   ${}I(\alpha )={\begin{cases}1,{\text{ falls }}I(\beta )=I(\gamma )\,,\\0,{\text{ falls }}I(\beta )\neq I(\gamma )\,.\end{cases}}\,$

Bei

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

sagt man, dass der Ausdruck ${}\alpha$ bei der Wahrheitsbelegung ${}\lambda$ (oder der Interpretation ${}I$) wahr wird (oder gilt), andernfalls, dass er falsch wird (nicht gilt). Dafür schreibt man auch ${}I\vDash \alpha$ bzw. ${}I\not \vDash \alpha$. Mit ${}I^{\vDash }$ bezeichnen wir die Menge aller bei der Interpretation ${}I$ wahren Ausdrücke aus der Sprache. Wenn ${}\Gamma \subseteq L^{V}$ eine Menge an Ausdrücken ist, so bedeutet ${}I\vDash \Gamma$, dass ${}I\vDash \alpha$ für alle ${}\alpha \in \Gamma$ gilt. Dafür sagt man auch, dass ${}\Gamma$ bei der Interpretation ${}I$ gilt oder dass ${}I$ ein Modell für ${}\Gamma$ ist.

Beispiel

Es sei ${}V=\{p,q,r\}$ und ${}\lambda$ sei die Wahrheitsbelegung mit ${}\lambda (p)=1,\,\lambda (q)=1,\,\lambda (r)=0$. Es sei ${}I$ die zugehörige Interpretation. Zur Berechnung des Wahrheitswertes von

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

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

${}I((\neg q))=0\,$

und somit

${}I((p)\wedge (\neg (q)))=0\,.$

Also ist

${}I{\left(\neg {\left((p)\wedge (\neg (q))\right)}\right)}=1\,.$

Andererseits ist

${}I(r)=0\,$

und daher ist

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

Der Ausdruck ist also bei dieser Wahrheitsbelegung nicht wahr.

Tautologien

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$

Folgerung

Definition

Es sei ${}V$ eine Menge von Variablen und ${}L^{V}$ die zugehörige aussagenlogische Sprache. Es sei ${}\Gamma \subseteq L^{V}$ eine Teilmenge und ${}\alpha \in L^{V}$. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, geschrieben ${}\Gamma \vDash \alpha$, wenn für jede Interpretation ${}I$ (gegeben durch eine Wahrheitsbelegung ${}\lambda$) mit ${}I\vDash \Gamma$ auch ${}I\vDash \alpha$ gilt.