Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 26

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Semantik der Modallogik
Von Gottfried Wilhelm Leibniz stammt die Idee, Notwendigkeiten über mögliche Welten zu verstehen.
Saul Kripke schuf die formale Modelltheorie für die Modallogik.


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


Definition  

Unter einem modallogischen Modell versteht man einen gerichteten Graphen zusammen mit einer Wahrheitsbelegung für die Aussagenvariablen für jeden Knotenpunkt .

Die Knotenpunkte des gerichteten Graphen nennt man in diesem Zusammenhang auch Welten oder Weltpunkte. Die von einer Welt aus verbundenen Welten , also die mit , nennt man die von aus erreichbaren Welten, die Relation heißt auch Erreichbarkeitsrelation. Durch die übliche Interpretation die 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.


Definition  

In einem modallogischen Modell (mit einer punktweisen Wahrheitsbelegung ) definiert man die Gültigkeit von modallogischen Ausdrücken induktiv wie folgt: Sei der modallogische Ausdruck schon für jeden Weltpunkt definiert. Dann setzt man für einen jeden Weltpunkt

genau dann, wenn in jeder von aus erreichbaren Welt die Beziehung

gilt.


Beispiel  

Baby Category 2.svg

Wir arbeiten mit den Aussagenvariablen . Im Weltpunkt gelte

und im Weltpunkt gelte

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

oder

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 , wobei ein rein aussagenlogischer Ausdruck ist (also ohne jede Box). Die Gültigkeit von in einem Weltpunkt bedeutet, dass in jedem von diesem Weltpunkt aus erreichbaren Weltpunkt gilt. Somit gilt beispielsweise

und

und

ferner

und

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

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

u.s.w.


Kripke frame.png


Kripke model.png


Frames.png

Definition  

Man sagt, dass ein modallogischer Ausdruck in einem modallogischen Modell gilt, geschrieben

wenn

für alle gilt.



Lemma  

  1. Die aussagenlogischen Tautologien der modallogischen Sprache gelten in jedem modallogischen Modell.
  2. In jedem modallogischen Modell gilt das -Axiom, also
  3. Die in einem (jeden) modallogischen Modell gültigen Ausdrücke sind abgeschlossen unter dem Modus Ponens.
  4. Wenn ein modallogischer Ausdruck in einem (jedem) modallogischen Modell gilt, so gilt auch in diesem (jedem) modallogischen Modell.

Beweis  

(1) und (3) sind klar, da die Gültigkeit in einem Knoten die aussagenlogischen Gesetze respektiert. (2). Sei und

und

Dann gilt in jeder von aus erreichbaren Welt

und damit

Also ist

(4). Wenn in einem modallogischen Modell gilt, so gilt für jede Welt auch . Wegen dieser allgemeinen Gültigkeit gilt auch für jede von aus erreichbare Welt und damit . Dies gilt in jedem Punkt dieses Modells.



Definition  

Man sagt, dass eine Menge von modallogischen Ausdrücken in einem modallogischen Modell gilt, geschrieben

wenn

für alle gilt.


Definition  

Man sagt, dass ein modallogischer Ausdruck in einem gerichteten Graphen gilt, geschrieben

wenn für jede Wahrheitsbelegung

gilt.


Definition  

Es sei eine Menge von modallogischen Ausdrücken und ein modallogischer Ausdruck. Man sagt, dass aus folgt, geschrieben , wenn für jedes modallogische Modell mit

auch

gilt.

Für ergeben sich die modallogisch allgemeingültigen Ausdrücke. Aufgrund von Lemma 26.5 gehören alle in der -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 ein -modallogisches System und ein modallogischer Ausdruck. Es gelte

Dann ist auch

Beweis  

Dies folgt aus Lemma 26.5.


Diese Aussage erlaubt es insbesondere, zu zeigen, dass aus einem gegebenen modallogischen Axiomensystem ein gewisser modallogischer Ausdruck nicht ableitbar, indem man ein modallogisches Modell angibt, in dem gilt, aber nicht.



Semantik der einzelnen modallogischen Systeme

Der durch die -Modallogik gegebene axiomatische Rahmen gilt in jedem gerichteten Graphen, aufgefasst als modallogisches Modell. Wir fragen uns, wie speziellere modallogische Axiome mit Eigenschaften von gerichteten Graphen zusammenhängen. Der folgende Satz liefert eine Übersetzung zwischen diesen beiden Konzepten.



Satz  

  1. In einem gerichteten Graphen gilt das Möglichkeitsaxiom genau dann, wenn jeder Punkt einen Nachfolger besitzt.
  2. In einem gerichteten Graphen gilt das Reflexivitätsaxiom genau dann, wenn reflexiv ist.
  3. In einem gerichteten Graphen gilt das Symmetrieaxiom genau dann, wenn symmetrisch ist.
  4. In einem gerichteten Graphen gilt das Transitivitätsaxiom genau dann, wenn transitiv ist.
  5. In einem gerichteten Graphen gilt das euklidische Axiom genau dann, wenn euklidisch ist.
  6. In einem gerichteten Graphen gilt das Löb-Axiom genau dann, wenn transitiv ist und es in keine unendlichen Ketten gibt.

Beweis  

(1). Es sei gegeben. Sei zunächst vorausgesetzt, dass in jedes Element einen Nachfolger besitzt und sei

für eine Welt . Es sei mit . Dann ist

und somit

also

Sei umgekehrt angenommen, dass eine Sackgassenwelt besitzt. Dann ist für eine beliebige Aussagenvariable

aber

und das Möglichkeitsaxiom kann nicht gelten.

(2). Es sei gegeben. Sei zunächst reflexiv und sei

Wegen ist insbesondere

Wenn nicht reflexiv ist, so sei und gelte nicht. Es sei die Belegung, bei der

gelte, aber in allen anderen Welten . Dann ist

und somit ist

(3). Es sei gegeben. Sei zunächst symmetrisch und sei

Es sei eine von aus erreichbare Welt gegeben, also . Wegen der Symmetrie ist auch und somit ist

Also ist

Wenn hingegen nicht symmetrisch ist, so seien Welten mit , aber nicht . Es sei eine Aussagenvariable und es sei die Belegung, bei der

gelte und so, dass in allen von aus erreichbaren Welten gelte. Dann ist

und somit ist

also

(4). Es sei gegeben. Sei zunächst transitiv und sei

Es sei und und somit

Also ist

und damit

Es sei nun nicht transitiv und seien Punkte mit , , aber nicht . Es sei eine Aussagenvariable und sei die Belegung, bei der in allen von aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist

und

da ja , und somit ist

also

(5). Es sei gegeben. Sei zunächst euklidisch und sei

Somit gibt es eine Welt mit und mit

Es sei eine Welt mit . Nach der euklidischen Eigenschaft ist dann auch , daher ist

Somit ist

Es sei nun nicht euklidisch und seien Punkte mit , , aber nicht . Es sei eine Aussagenvariable und sei die Belegung, bei der in allen von aus erreichbaren Welten gelte, in allen anderen Welten nicht. Dann ist

und somit

In gilt hingegen , also

Somit gilt

und damit

(6). Wir arbeiten mit der Kontraposition des Löb-Axioms, also mit

Sei zunächst vorausgesetzt, dass die graphentheoretischen Eigenschaften besitzt. Sei und

Dann gibt es eine Welt mit und mit

Wir betrachten Ketten mit . Da es keine unendliche Kette gibt, bricht eine solche Kette ab, sagen wir in . In gilt dann

Wegen der Transitivität ist von aus erreichbar und somit ist

Sei nun vorausgesetzt, dass nicht die Eigenschaften erfüllt. Wenn nicht transitiv ist, so ist nach Lemma 25.18 in Verbindung mit Lemma 26.9 die Gültigkeit des Löb-Axioms ausgeschlossen. Es sei also eine unendlich lange Kette der Form gegeben. Wir belegen für alle und für alle anderen Welten. Dann gilt

da außerhalb der Kette stets gilt und innerhalb der Kette stets gilt.


Bemerkung  

Ein Modell des Löb-Axioms ist insbesondere frei von Schleifen, d.h. es ist reflexivitätsfrei, es gilt also nie . Eine solche Schleife würde ja direkt eine unendliche Kette produzieren. Der gerichtete Graph

mit der durch , falls gegebenen Relation und der Belegung für alle zeigt, dass das Löb-Axiom (in der Form ) bei einer unendlichen transitiven Kette ohne Schleifen nicht gelten muss.



Beispiel  

Wir betrachten für die modallogische Ausdrucksmenge, die durch

gegeben ist. Da sich die Ausdrücke, die innerhalb des -Operators von stehen, gegenseitig ausschließen, bruacht man zur Realisierung von mindestens Punkte. Daher ist

nicht durch einen endlichen gerichteten Graphen erfüllbar. Die Ausdrucksmenge ist problemlos durch einen unendlichen gerichteten Graphen erfüllbar: Von einer Grundwelt aus sind die unendlich vielen Welten , , erreichbar, und in gilt (die Wahrheitsbelegung ist ansonsten unerheblich).



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2018) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)