Modallogik/Semantik/Einführung/Textabschnitt

Wir besprechen nun die Semantik der Modallogik, die mit gerichteten Graphen arbeitet, die die Idee von erreichbaren Welten modellieren.

Von Gottfried Wilhelm Leibniz stammt die Idee, Notwendigkeiten über mögliche Welten zu verstehen.

Saul Kripke schuf die formale Modelltheorie für die Modallogik.

Definition

Unter einem modallogischen Modell versteht man einen gerichteten Graphen ${}(M,R)$ zusammen mit einer Wahrheitsbelegung ${}\mu$ für die Aussagenvariablen für jeden Knotenpunkt ${}w\in M$.

Die Knotenpunkte des gerichteten Graphen nennt man in diesem Zusammenhang auch Welten oder Weltpunkte. Die von einer Welt ${}x$ aus verbundenen Welten ${}y$, also die mit ${}xRy$, nennt man die von ${}x$ aus erreichbaren Welten, die Relation ${}R$ heißt auch Erreichbarkeitsrelation. Durch die übliche Interpretation der aussagenlogischen Junktoren erhält man in jedem Weltpunkt eine Belegung für alle aussagenlogischen Ausdrücke in den gegebenen Aussagenvariablen. Darauf aufbauend kann man auch jedem modallogischen Ausdruck an jedem Knotenpunkt einen Wahrheitswert zuordnen, und zwar in folgender Weise. Dabei wird die Gültigkeit einer Aussage ${}\alpha$ in einer Welt ${}w$ als ${}w\vDash \alpha$ notiert.

Definition

In einem modallogischen Modell ${}(M,R,\mu )$ (mit einer punktweisen Wahrheitsbelegung ${}\mu$) definiert man die Gültigkeit von modallogischen Ausdrücken induktiv wie folgt: Es sei der modallogische Ausdruck ${}\alpha$ schon für jeden Weltpunkt definiert. Dann setzt man für einen jeden Weltpunkt ${}w\in M$

$w\vDash \Box \alpha$

genau dann, wenn in jeder von ${}w$ aus erreichbaren Welt ${}v$ die Beziehung

$v\vDash \alpha$

gilt.

Beispiel

Wir arbeiten mit den Aussagenvariablen ${}p,q,r$. Im Weltpunkt ${}a$ gelte

$a\vDash p,q,\neg r$

und im Weltpunkt ${}b$ gelte

$b\vDash p,\neg q,r.$

Daraus kann man die Gültigkeit von aussagenlogischen Ausdrücken jeweils erschließen, beispielsweise gilt

$a\vDash p\wedge \neg r$

oder

$b\vDash \neg q\rightarrow r.$

Für modallogische Ausdrücke muss man den gerichteten Graphen berücksichtigen, wobei man induktiv über die Anzahl der Boxen vorgeht. Es geht also zunächst um Ausdrücke der Form ${}\Box \alpha$, wobei ${}\alpha$ ein rein aussagenlogischer Ausdruck ist (also ohne jede Box). Die Gültigkeit von ${}\Box \alpha$ in einem Weltpunkt bedeutet, dass in jedem von diesem Weltpunkt aus erreichbaren Weltpunkt ${}\alpha$ gilt. Somit gilt beispielsweise

$a\vDash \Box p$

und

$a\vDash \neg \Box q$

und

$a\vDash \Box (q\vee r),$

ferner

$b\vDash \Box p$

und

$b\vDash \Box \neg q.$

Damit kann man dann in jedem Punkt aussagenlogisch den Wahrheitswert von jeder modallogischen Aussage bestimmen, in der die Box nur einfach (also ohne Verschachtelungen) auftritt, beispielsweise

$a\vDash \Box p\wedge \neg r\wedge \neg \Box \neg r.$

Unter Berücksichtigung des gerichteten Graphen kann man dann auch den Wahrheitswert für jeden modallogischen Ausdruck mit modallogischer Verschachtelungstiefe ${}\leq 2$ bestimmen, also etwa

$a\vDash \Box \Box p,$

u.s.w.

Definition

Man sagt, dass ein modallogischer Ausdruck ${}\alpha$ in einem modallogischen Modell ${}(M,R,\mu )$ gilt, geschrieben

$(M,R,\mu )\vDash \alpha ,$

wenn

$w\vDash \alpha$

für alle ${}w\in M$ gilt.

Lemma

1. Die aussagenlogischen Tautologien der modallogischen Sprache gelten in jedem modallogischen Modell.
2. In jedem modallogischen Modell ${}(M,R,\mu )$ gilt das ${}K$-Axiom, also

   $M\vDash \Box (\alpha \rightarrow \beta )\rightarrow (\Box \alpha \rightarrow \Box \beta ).$

3. Die in einem (jeden) modallogischen Modell gültigen Ausdrücke sind abgeschlossen unter dem Modus ponens.
4. Wenn ein modallogischer Ausdruck ${}\alpha$ in einem (jedem) modallogischen Modell gilt, so gilt auch ${}\Box \alpha$ in diesem (jedem) modallogischen Modell.

Beweis

(1) und (3) sind klar, da die Gültigkeit in einem Knoten die aussagenlogischen Gesetze respektiert. (2). Sei ${}w\in M$ und

$w\vDash \Box (\alpha \rightarrow \beta )$

und

$w\vDash \Box \alpha .$

Dann gilt in jeder von ${}w$ aus erreichbaren Welt ${}v$

$v\vDash \alpha \rightarrow \beta {\text{ und }}v\vDash \alpha$

und damit

$v\vDash \beta .$

Also ist

$w\vDash \Box \beta .$

(4). Wenn ${}(M,R,\mu )\vDash \alpha$ in einem modallogischen Modell ${}(M,R,\mu )$ gilt, so gilt für jede Welt ${}w\in M$ auch ${}w\vDash \alpha$. Wegen dieser allgemeinen Gültigkeit gilt auch ${}v\vDash \alpha$ für jede von ${}w$ aus erreichbare Welt und damit ${}w\vDash \Box \alpha$. Dies gilt in jedem Punkt dieses Modells.

$\Box$

Definition

Man sagt, dass eine Menge ${}\Gamma$ von modallogischen Ausdrücken in einem modallogischen Modell ${}(M,R,\mu )$ gilt, geschrieben

$(M,R,\mu )\vDash \Gamma ,$

wenn

$(M,R,\mu )\vDash \alpha$

für alle ${}\alpha \in \Gamma$ gilt.

Definition

Man sagt, dass ein modallogischer Ausdruck ${}\alpha$ in einem gerichteten Graphen ${}(M,R)$ gilt, geschrieben

$(M,R)\vDash \alpha ,$

wenn für jede Wahrheitsbelegung ${}\mu$

$(M,R,\mu )\vDash \alpha$

gilt.

Definition

Es sei ${}\Gamma$ eine Menge von modallogischen Ausdrücken und ${}\alpha$ ein modallogischer Ausdruck. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ folgt, geschrieben ${}\Gamma \vDash \alpha$, wenn für jedes modallogische Modell ${}(M,R,\mu )$ mit

$(M,R,\mu )\vDash \Gamma$

auch

$(M,R,\mu )\vDash \alpha$

gilt.

Für ${}\Gamma =\emptyset$ ergeben sich die modallogisch allgemeingültigen Ausdrücke. Aufgrund von Fakt gehören alle in der ${}K$-Modallogik ableitbaren Ausdrücke dazu. Wie in der Aussagenlogik und der Prädikatenlogik ist also der Ableitungskalkül korrekt und es erhebt sich die Frage, ob er auch vollständig ist.

Lemma

Es sei ${}\Gamma$ ein ${}K$-modallogisches System und ${}\alpha$ ein modallogischer Ausdruck. Es gelte

$\Gamma \vdash \alpha .$

Dann ist auch

$\Gamma \vDash \alpha .$

Beweis

Dies folgt aus Fakt.

$\Box$

Diese Aussage erlaubt es insbesondere, zu zeigen, dass aus einem gegebenen modallogischen Axiomensystem ${}\Gamma$ ein gewisser modallogischer Ausdruck ${}\alpha$ nicht ableitbar, indem man ein modallogisches Modell ${}(M,R,\mu )$ angibt, in dem ${}\Gamma$ gilt, aber ${}\alpha$ nicht.