Erweiterungen von K

Seminar: Einführung in die Modallogik (WS 16/17)
Lehrender: Daniel Milne-Plückebaum, M.A. ([email protected])
Handout: Erweiterungen von K
Im Folgenden wollen wir uns einige Erweiterungen der Logik K ansehen. Das sind
Logiken, deren Folgerungs- und Tautologie-Begriffe nur für bestimmte Klassen von KModellen definiert sind, und für die es auch einige neue Wahrheitsbaum-Regeln gibt.1
1
Klassen von K-Modellen
Die Zugänglichkeitsrelationen von K-Modellen können bestimmte formale Eigenschaften haben. Wir wollen uns auf die folgenden fünf Eigenschaften beschränken:
Sei W eine nichtleere Menge von Welten. Eine Zugänglichkeitsrelation R ⊆ W × W ist
• reflexiv gdw. für alle w ∈ W gilt: ⟨w, w⟩ ∈ R;
• symmetrisch gdw. für alle w, w′ ∈ W gilt: Falls ⟨w, w′ ⟩ ∈ R, so auch ⟨w′ , w⟩ ∈ R;
• transitiv gdw. für alle w, w′ , w′′ ∈ W gilt: Falls ⟨w, w′ ⟩ ∈ R und ⟨w′ , w′′ ⟩ ∈ R, so
auch ⟨w, w′′ ⟩ ∈ R;
• extendabel gdw. es für alle w ∈ W ein w′ ∈ W gibt mit ⟨w, w′ ⟩ ∈ R;
• universal gdw. für alle w, w′ ∈ W gilt: ⟨w, w′ ⟩ ∈ R.
Auf der Grundlage dieser Eigenschaften können wir verschiedene K-Rahmenklassen
definieren: Für jede Eigenschaft E bilden alle und nur die K-Rahmen eine Klasse, deren
Zugänglichkeitsrelationen E sind. Speziell haben wir:
Sei K = ⟨W, R⟩ ein K-Rahmen.
• Ist R reflexiv, so ist K ein Kr -Rahmen.
• Ist R symmetrisch, so ist K ein Ks -Rahmen.
• Ist R transitiv, so ist K ein Kt -Rahmen.
Vgl. für die folgenden Erläuterungen Priest, G. (2008). Introduction to Non-Classical Logic: From If
to Is. Cambridge University Press, 36-45.
1
1
• Ist R extendabel, so ist K ein Ke -Rahmen.
• Ist R universal, so ist K ein Ku -Rahmen.2
Besitzt die Zugänglichkeitsrelation eines K-Rahmens K mehrere der obigen Eigenschaften,
wobei keine Eigenschaft die andere einschließt, so fällt K nicht nur in verschiedene KRahmenklassen, sondern auch in eine kombinierte K-Rahmenklasse. Ist z.B. K ein
Kr - und ein Ks -Rahmen, so ist K auch ein Krs -Rahmen; ist K ein Krs - und ein Kt Rahmen, so ist K ein Krst -Rahmen; und so weiter. Insgesamt haben wir damit folgende
weitere verschiedene K-Rahmenklassen:
Sei K = ⟨W, R⟩ ein K-Rahmen.
• Ist R reflexiv und symmetrisch, so ist K ein Krs -Rahmen.
• Ist R reflexiv und transitiv, so ist K ein Krt -Rahmen.
• Ist R symmetrisch und transitiv, so ist K ein Kst -Rahmen.
• Ist R symmetrisch und extendabel, so ist K ein Kse -Rahmen.
• Ist R transitiv und extendabel, so ist K ein Kte -Rahmen.
• Ist R reflexiv, symmetrisch und transitiv, so ist K ein Krst -Rahmen.
Erweitern wir einen Kx⃗ -Rahmen K, wobei x⃗ ∈ {r, s, t, e, u, rs, rt, st, se, te, rst},3 um eine
(basale) K-Interpretationsfunktion, so erhalten wir ein (basales) Kx⃗ -Modell. Und hier
noch einmal in einem Kasten:
Da die Eigenschaft der Universalität eine Zugänglichkeitsrelation praktisch überflüssig macht, können
wir einen Ku -Rahmen auch einfach als Paar ⟨W, IW ⟩ definieren, wobei W eine Weltenmenge und IW eine
basale Ku -Interpretationsfunktion auf W ist. Daraus ergeben sich folgende vereinfachten Ku -Wahrheitsbedingungen für Box- und Diamantformeln:
2
Sei ⟨W, IW ⟩ ein Ku -Modell. Dann gilt:
• I W (w, ◻A) = t gdw. für alle w′ ∈ W gilt: I W (w′ , A) = t
• I W (w, ◇A) = t gdw. es ein w′ ∈ W gibt mit: I W (w′ , A) = t
In vielen Einführungsbüchern wird dies als die Semantik der Modallogik eingeführt. In diesem Seminar
betrachten wir Ku jedoch nur als eine spezielle aus einer Familie von Modallogiken und behalten daher
die allgemeine Sicht- und Schreibweise mit konzeptueller Hinzunahme und expliziter Angabe universaler
Zugänglichkeitsrelationen bei.
3
Im Folgenden wird die Spezifikation implizit gelassen
2
Ein (basales) Kx⃗ -Modell ist ein Tripel ⟨W, R, IW,R ⟩, wobei
• ⟨W, R⟩ ein Kx⃗ -Rahmen und
• IW,R eine (basale) K-Interpretationsfunktion ist.
Auf der Grundlage der verschiedenen K-Modellklassen können wir nun die Erweiterungen
der Logik K über deren logische Grundbegriffe definieren.
2
Grundbegriffe der Erweiterungen von K
Die Erweiterungen von K sind Logiken, deren logische Grundbegriffe (logische Folgerung,
logische Wahrheit) nur für bestimmte K-Modellklassen definiert sind. Die folgenden Definitionsschemas decken all diese Grundbegriffe ab.
Sei P = {P1 , ..., Pn } eine Menge von K-Formeln (die Prämissen) und C eine KFormel (die Konklusion). C ist genau dann eine Kx⃗ -Folgerung aus P (wir schreiben:
P ⊧Kx⃗ C), wenn für alle basalen Kx⃗ -Modelle ⟨W, R, IW,R ⟩ gilt: Für alle w ∈ W : Falls
I W,R (w, P ) = t für alle P ∈ P, so auch I W,R (w, C) = t.
Eine K-Formel A ist genau dann eine Kx⃗ -Tautologie (wir schreiben: ⊧Kx⃗ A), wenn
für alle basalen Kx⃗ -Modelle ⟨W, R, IW,R ⟩ gilt: Für alle w ∈ W ∶ I W,R (w, A) = t.
Jede Modallogik Kx⃗ ist eine Erweiterung von K in dem Sinne, dass für alle P, C gilt:
Salls P ⊧K C, so auch P ⊧Kx⃗ C. Wenn Wahrheit in allen Welten aller K-Modelle beibehalten wird, dann wird sie erst recht in allen Welten aller K-Modelle einer bestimmten Klasse
beibehalten. Dabei gilt: Je weniger K-Modelle betrachtet werden, desto mehr Folgerungen
und Tautologien gibt es, oder zumindest gibt es nicht weniger.4 Um zu überprüfen, ob
eine K-Formel C aus einer K-Formelmenge P Kx⃗ -folgt, oder ob es sich bei einer K-Formel
A um eine Kx⃗ -Tautologie handelt, verwenden wir wieder das Wahrheitsbaumverfahren.
3
Wahrheitsbäume für die Erweiterungen von K
An der grundsätzlichen Funktionsweise des Wahrheitsbaumverfahrens ändert sich für die
Erweiterungen von K nichts. Je nach Erweiterung kommen lediglich eine oder mehrere
Auf einer endlichen Weltenmenge W gibt es z.B. mehr Krst -Modelle als Ku -Modelle. Dennoch gilt
für alle P, C: P ⊧Krst C genau dann, wenn P ⊧Ku C.
4
3
neue Regeln hinzu. Diese neuen Regeln dienen einem anderen Zweck als die bereits bekannten Regeln für die Logik K. Sie basieren nicht auf den K-Wahrheitsbedingungen und
dienen somit nicht dem weltenrelativen Formelabbau; stattdessen erlauben sie es uns,
zusätzliche Annahmen in Bezug auf die jeweiligen Zugänglichkeitsrelationen zu machen.
Damit liefern die Regeln neue Wahrheitsbaumeinträge der Form wRw′ , wodurch möglicherweise die Anzahl der möglichen BOX-Regelanwendungen erhöht wird. Für jede der
neuen Regeln gilt: Es ist erlaubt, die Regel anzuwenden, wenn wir uns in einer bestimmten
Erweiterung von K bewegen.
3.1
Neue Regeln und charakteristische Tautologien
Bewegen wir uns in einer einfachen K-Erweiterung (Kr , Ks , Kt , Ke , Ku ), wird dem Wahrheitsbaumverfahren genau eine Regel hinzugefügt; bewegen wir uns in einer kombinierten
K-Erweiterung (Krs , Krt , Kst , Kse , Kte , Krst ), werden dem Wahrheitsbaumverfahren zwei
oder drei neue Regeln hinzugefügt. Wir müssen also jeweils schauen, für welche Logik wir
überprüfen wollen, ob eine Folgerung besteht oder ob eine Tautologie vorliegt, und können
uns dementsprechend die jeweilige(n) Regel(n) für den zu entwickelnden Wahrheitsbaum
genehmigen. Gehen wir die einfachen K-Erweiterungen nacheinander durch.
3.1.1
Die Logik Kr
Bewegen wir uns in der Logik Kr , oder einer Erweiterung von Kr , dürfen wir neben den
13 Regeln für die Logik K auch folgende Regel im Wahrheitsbaumverfahren verwenden.
Die r-Regel: Befindet sich in einem offenen Ast an einem Knoten die Angabe einer
Welt w,5 so ist jeder offene Ast, der durch den Knoten führt, an seinem Blatt um einen
Knoten für die Annahme der Zugänglichkeit von w zu w zu erweitern. Schematisch:
⋮
⋯w⋯
⋮
wRw
Für die Logik Kr gibt es sogenannte charakteristische Tautologien, also K-Formeln,
die in der Logik Kr , aber nicht in den Logiken K, Ks , Kt oder Ke tautologisch sind.6
Die Eigenschaft, tautologisch zu sein, geht für diese K-Formeln somit Hand in Hand
D.h. an dem Knoten befindet sich ein Eintrag der Form w ∶ A oder wRw′ oder w′ Rw.
Charakteristische Kr -Tautologien sind natürlich auch Ku -Tautologien, da jede Zugänglichkeitsrelation, die universal ist, auch reflexiv ist.
5
6
4
mit der Eigenschaft von Zugänglichkeitsrelationen, reflexiv zu sein. Charakteristische Kr Tautologien sind z.B. K-Formeln der Form ◻A → A. Schauen wir, wie wir mithilfe des
Wahrheitsbaumverfahrens nachweisen können, dass es sich bei der K-Formel ◻p0 → p0
um eine Kr -Tautologie handelt.
w0 ∶ ¬(◻p0 → p0 )
w0 ∶ ◻p0
w0 ∶ ¬p0
w0 Rw0
w 0 ∶ p0
×
Es gilt also: ⊧Kr ◻p0 → p0 . Um zu zeigen, dass ◻p0 → p0 auch eine charakteristische
Kr -Tautologie ist, müssten wir noch zeigen, dass ◻p0 → p0 keine K-, Ks -, Kt - oder Ke Tautologie ist.
3.1.2
Die Logik Ks
Bewegen wir uns in der Logik Ks , oder einer Erweiterung von Ks , dürfen wir neben den
13 Regeln für die Logik K auch folgende Regel im Wahrheitsbaumverfahren verwenden.
Die s-Regel: Befindet sich in einem offenen Ast an einem Knoten die Annahme der
Zugänglichkeit einer Welt w zu einer Welt w′ , so ist jeder offene Ast, der durch den
Knoten führt, an seinem Blatt um einen Knoten für die Annahme der Zugänglichkeit
von w′ zu w zu erweitern. Schematisch:
⋮
wRw′
⋮
w′ Rw
Für die Logik Ks gibt es ebenfalls charakteristische Tautologien, also K-Formeln, die
in der Logik Ks , aber nicht in den Logiken K, Kr , Kt oder Ke tautologisch sind.7 Die
Eigenschaft, tautologisch zu sein, geht für diese K-Formeln also Hand in Hand mit der
Charakteristische Ks -Tautologien sind natürlich auch Ku -Tautologien, da jede Zugänglichkeitsrelation, die universal ist, auch symmetrisch ist.
7
5
Eigenschaft von Zugänglichkeitsrelationen, symmetrisch zu sein. Charakteristische Ks Tautologien sind z.B. K-Formeln der Form A → ◻ ◇ A. Schauen wir, wie wir mithilfe des
Wahrheitsbaumverfahrens nachweisen können, dass es sich bei der K-Formel p0 → ◻◇p0
um eine Ks -Tautologie handelt.
w0 ∶ ¬(p0 → ◻◇p0 )
w 0 ∶ p0
w0 ∶ ¬◻◇p0
w0 ∶ ◇¬◇p0
w0 Rw1
w1 ∶ ¬◇p0
w1 Rw0
w1 ∶ ◻¬p0
w0 ∶ ¬p0
×
Es gilt also: ⊧Ks p0 → ◻◇p0 . Um zu zeigen, dass p0 → ◻◇p0 eine charakteristische Ks Tautologie ist, müssten wir noch zeigen, dass p0 → ◻◇p0 keine K-, Kr -, Kt - oder Ke Tautologie ist.
3.1.3
Die Logik Kt
Bewegen wir uns in der Logik Kt , oder einer Erweiterung von Kt , dürfen wir neben den
13 Regeln für die Logik K auch folgende Regel im Wahrheitsbaumverfahren verwenden.
Die t-Regel: Befindet sich in einem offenen Ast an einem Knoten die Annahme
der Zugänglichkeit einer Welt w zu einer Welt w′ , und befindet sich im selben Ast an
einem anderen Knoten die Annahme der Zugänglichkeit der Welt w′ zu einer Welt w′′ ,
so ist jeder offene Ast, der durch die beiden Knoten führt, an seinem Blatt um einen
Knoten für die Annahme der Zugänglichkeit von w zu w′′ zu erweitern. Schematisch:
6
⋮
wRw′
⋮
w′ Rw′′
⋮
wRw′′
Für die Logik Kt gibt es ebenfalls charakteristische Tautologien, also K-Formeln, die in der
Logik Kt , aber nicht in den Logiken K, Kr , Ks oder Ke tautologisch sind.8 Die Eigenschaft,
tautologisch zu sein, geht für diese K-Formeln also Hand in Hand mit der Eigenschaft
von Zugänglichkeitsrelationen, transitiv zu sein. Charakteristische Kt -Tautologien sind
z.B. K-Formeln der Form ◻A → ◻ ◻ A. Schauen wir, wie wir mithilfe des Wahrheitsbaumverfahrens nachweisen können, dass es sich bei der K-Formel ◻p0 → ◻◻p0 um eine
Kt -Tautologie handelt.
w0 ∶ ¬(◻p0 → ◻◻p0 )
w0 ∶ ◻p0
w0 ∶ ¬◻◻p0
w0 ∶ ◇¬◻p0
w0 Rw1
w1 ∶ ¬◻p0
w1 ∶ ◇¬p0
w1 Rw2
w2 ∶ ¬p0
w0 Rw2
w 2 ∶ p0
×
Charakteristische Kt -Tautologien sind natürlich auch Ku -Tautologien, da jede Zugänglichkeitsrelation, die universal ist, auch transitiv ist.
8
7
Es gilt also: ⊧Kt ◻p0 → ◻◻p0 . Um zu zeigen, dass ◻p0 → ◻◻p0 eine charakteristische
Kt -Tautologie ist, müssten wir noch zeigen, dass ◻p0 → ◻◻p0 keine K-, Kr -, Ks - oder
Ke -Tautologie ist.
3.1.4
Die Logik Ke
Bewegen wir uns in der Logik Ke (oder einer Erweiterung von Ke ), dürfen wir neben den
13 Regeln für die Logik K auch folgende Regel im Wahrheitsbaumverfahren verwenden.
Die e-Regel: Befindet sich in einem offenen Ast an einem Knoten die Angabe einer
Welt w, und befindet sich im selben Ast an keinem Knoten die Annahme einer Zugänglichkeit der Welt w zu irgendeiner Welt, dann ist jeder offene Ast, der durch den
Knoten führt, an seinem Blatt um einen Knoten für die Annahme der Zugänglichkeit
der Welt w zu einer Welt w′ zu erweitern, wobei w′ in dem zu erweiternden Ast noch
nicht vorkommt. Schematisch:
⋮
⋯w⋯
⋮
wR . . .
⋮
wobei w′ in dem Ast neu ist.
wRw′
Für die Logik Ke gibt es ebenfalls charakteristische Tautologien, also K-Formeln, die in
der Logik Ke , aber nicht in den Logiken K, Ks oder Kt tautologisch sind.9 Die Eigenschaft,
tautologisch zu sein, geht für diese K-Formeln also Hand in Hand mit der Eigenschaft von
Zugänglichkeitsrelationen, extendabel zu sein. Charakteristische Ke -Tautologien sind z.B.
K-Formeln der Form ◻A → ◇A. Schauen wir, wie wir mithilfe des Wahrheitsbaumverfahrens nachweisen können, dass es sich bei der K-Formel ◻p0 → ◇p0 um eine Ke -Tautologie
handelt.
Charakteristische Ke -Tautologien sind natürlich auch Ku -Tautologien, da jede Zugänglichkeitsrelation, die universal ist, auch extendabel ist. Außerdem sind charakteristische Ke -Tautologien auch Kr Tautologien, da jede Zugänglichkeitsrelation, die reflexiv ist, auch extendabel ist.
9
8
¬(◻p0 → ◇p0 ) (w0 )
◻p0 (w0 )
¬◇p0 (w0 )
◻¬p0 (w0 )
w0 Rw1
p0 (w1 )
¬p0 (w1 )
×
Es gilt also: ⊧Ke ◻p0 → ◇p0 . Um zu zeigen, dass ◻p0 → ◇p0 eine charakteristische Ke Tautologie ist, müssten wir noch zeigen, dass ◻p0 → ◇p0 keine K-, Ks - oder Kt -Tautologie
ist.
3.1.5
Die Logik Ku
Bewegen wir uns in der Logik Ku , dürfen wir neben den 13 Regeln für die Logik K auch
folgende Regel im Wahrheitsbaumverfahren verwenden.10
Die u-Regel: Befindet sich in einem offenen Ast an einem Knoten die Angabe einer
Welt w, und befindet sich an einem Knoten im selben Ast die Angabe einer Welt
w′ , so ist jeder offene Ast, der durch diese Knoten führt, an seinem Blatt um einen
Knoten für die Annahme der Zugänglichkeit von w zu w′ zu erweitern. Schematisch:
Lassen wir Zugänglichkeitsrelationen in Ku -Modellen außer Acht und erhalten so vereinfachte Ku Wahrheitsbedingungen für Box- und Diamantformeln (siehe Fußnote 2), müssen wir auch die entsprechenden Ku -Wahrheitsbaumregeln modifizieren. Zusätzliche Regeln sind dann nicht nötig.
10
Die Regel DIAu : Befindet sich in einem offenen Ast an einem Knoten eine K-Formel des
Typs ◇A zusammen mit der Angabe einer Welt w, so ist jeder offene Ast, der durch diesen
Knoten führt, an seinem Blatt um einen Knoten für die K-Formel A zusammen mit der Angabe
einer Welt w′ zu erweitern, wobei w′ in dem zu erweiternden Ast noch nicht vorkommt. Schematisch:
⋮
w ∶ ◇A
⋮
w′ ∶ A
wobei w in dem Ast neu ist.
′
9
⋮
⋯w⋯
⋮
⋯ w′ ⋯
⋮
wRw′
Für die Logik Ku gibt es ebenfalls charakteristische Tautologien, also K-Formeln, die in
der Logik Ku , aber nicht in den Logiken K, Kr , Ks , Kt oder Ke tautologisch sind. Die
Eigenschaft, tautologisch zu sein, geht für diese K-Formeln Hand in Hand mit der Eigenschaft von Zugänglichkeitsrelationen, universal zu sein. Charakteristische Ku -Tautologien
sind z.B. K-Formeln der Form ◇A → ◻◇A. Schauen wir, wie wir mithilfe des Wahrheitsbaumverfahrens nachweisen können, dass es sich bei der K-Formel ◇p0 → ◻◇p0 um eine
Ku -Tautologie handelt.
Die Regel BOXu : Befindet sich in einem offenen Ast an einem Knoten eine K-Formel des Typs
◻A zusammen mit der Angabe einer Welt w, und befindet sich im selben Ast an einem Knoten eine
K-Formel B zusammen mit der Angabe einer Welt w′ , so ist jeder offene Ast, der durch diese Knoten
führt, an seinem Blatt um einen Knoten für die K-Formel A zusammen mit der Angabe einer Welt
w′ zu erweitern. Schematisch:
⋮
w ∶ ◻A
⋮
w′ ∶ B
⋮
w′ ∶ A
10
w0 ∶ ¬(◇p0 → ◻◇p0 )
w0 Rw0
w0 ∶ ◇p0
w0 ∶ ¬◻◇p0
w0 ∶ ◇¬◇p0
w0 Rw1
w 1 ∶ p0
w1 Rw0
w1 Rw1
w0 Rw2
w2 ∶ ¬◇p0
w2 Rw0
w2 Rw1
w1 Rw2
w2 Rw2
w2 ∶ ◻¬p0
w1 ∶ ¬p0
×
Es gilt also: ⊧Ku ◇p0 → ◻◇p0 . Um zu zeigen, dass ◇p0 → ◻◇p0 eine charakteristische
Ku -Tautologie ist, müssten wir noch zeigen, dass ◇p0 → ◻◇p0 keine K-, Kr -, Ks -, Kt oder Ke -Tautologie ist.
Bevor wir uns noch einige Wahrheitsbäume anschauen, kommt hier noch einmal eine
Übersicht der besprochenen charakteristischen Tautologien:
11
Charakteristische Tautologien für die Erweiterungen von K sind z.B.:
Für die Logik Kr : ◻p0 → p0
Für die Logik Ks : p0 → ◻◇p0
Für die Logik Kt : ◻p0 → ◻◻p0
Für die Logik Ke : ◻p0 → ◇p0
Für die Logik Ku : ◇p0 → ◻◇p0
3.2
Weitere Beispiele
Schauen wir uns noch ein paar Beispiele an. Zuerst einen schließenden Wahrheitsbaum;
dann einen offenen Wahrheitsbaum, von dem wir ein Gegenmodell ablesen können; und
zum Schluss einen unendlichen Wahrheitsbaum.
3.2.1
Ein schließender Wahrheitsbaum
Zu zeigen ist: ⊧Kst ◇p0 → ◻◇p0 . Da wir uns in der Logik Kst bewegen, werden die s- und
die t-Regel zugelassen. Die Ausgangsliste:
w0 ∶ ¬(◇p0 → ◻◇p0 )
Darauf wenden wir die Regel NI an:
w0 ∶ ¬(◇p0 → ◻◇p0 )
w0 ∶ ◇p0
w0 ∶ ¬◻◇p0
Nun wenden wir die Regel NBOX auf den letzten Eintrag an:
⋮
w0 ∶ ¬◻◇p0
w0 ∶ ◇¬◇p0
12
Wir können die s- oder t-Regel nur anwenden, wenn bereits mindestens eine Zugänglichkeit im Wahrheitsbaum angenommen wurde. In unserem Beispiel erhalten wir eine solche
Annahme, indem wir die Regel DIA auf den letzten Eintrag anwenden:
⋮
w0 ∶ ◇¬◇p0
w0 Rw1
w1 ∶ ¬◇p0
Nun können wir die s-Regel auf den Eintrag w0 Rw1 anwenden:
⋮
w0 Rw1
⋮
w1 Rw0
Sobald möglich sollten immer alle herleitbaren Annahmen über die Zugänglichkeitsrelation hinzugefügt werden, damit wir diese für den weltenrelativen Boxformel-Abbau
verwenden können. Unser Wahrheitsbaum enthält nun die beiden Einträge w0 Rw1 und
w1 Rw0 . Daraus ergibt sich durch zweimalige Anwendung der t-Regel:
⋮
w0 Rw1
⋮
w1 Rw0
w1 Rw1
w0 Rw0
Der Wahrheitsbaum enthält noch keine Boxformel, die wir zusammen mit einer passenden Zugänglichkeits-Annahme weltenrelativ abbauen können. Allerdings erhalten wir eine
13
Box-Formel, wenn wir die Regel NDIA auf den Eintrag w1 ∶ ¬◇p0 anwenden:
⋮
w1 ∶ ¬◇p0
⋮
w1 ∶ ◻¬p0
Die für den neuen Eintrag relevanten Zugänglichkeits-Annahmen sind w1 Rw1 und w1 Rw0 .
Wir können die Regel BOX also gleich zweimal anwenden:
⋮
w1 Rw0
w1 Rw1
⋮
w1 ∶ ◻¬p0
w1 ∶ ¬p0
w0 ∶ ¬p0
Der Wahrheitsbaum enthält noch eine weltenrelativ abbaubare Diamantformel. Diese erfordert die Annahme der Zugänglichkeit zu einer neuen Welt:
⋮
w0 ∶ ◇p0
⋮
w0 Rw2
w 2 ∶ p0
Da der Wahrheitsbaum nun eine neue Zugänglichkeits-Annahme enthält, können wir weitere Zugänglichkeits-Annahmen hinzufügen. Angewendet auf w0 Rw2 ergibt die s-Regel:
14
⋮
w0 Rw2
⋮
w2 Rw0
Die Anwendung der t-Regel auf die Zugänglichkeits-Annahmen w2 Rw0 und w0 Rw1 ergibt:
⋮
w0 Rw1
⋮
w2 Rw0
w2 Rw1
Die Anwendung der s-Regel auf den letzten Eintrag ergibt:
⋮
w2 Rw1
w1 Rw2
Schließlich können wir die t-Regel auf w2 Rw1 und w1 Rw2 anwenden:
⋮
w2 Rw1
w1 Rw2
w2 Rw2
Nun haben wir alle möglichen Zugänglichkeits-Annahmen hinzugefügt und können ◻¬p0
weltenrelativ abbauen. Daraus ergibt sich der vollständig entwickelte Wahrheitsbaum:
15
¬(◇p0 → ◻◇p0 ) (w0 )
◇p0 (w0 )
¬◻◇p0 (w0 )
◇¬◇p0 (w0 )
w0 Rw1
¬◇p0 (w1 )
w1 Rw0
w1 Rw1
w0 Rw0
◻¬p0 (w1 )
¬p0 (w1 )
¬p0 (w0 )
w0 Rw2
p0 (w2 )
w2 Rw0
w2 Rw1
w1 Rw2
w2 Rw2
¬p0 (w2 )
×
Alle Äste schießen. Also gilt: ⊧Krs ◇p0 → ◻◇p0 .11
Wir sehen also, dass Reflexivität und Symmetrie bereits ausreichen, um aus ◇p0 → ◻◇p0 eine
Tautologie zu machen. Wir betrachten ◇p0 → ◻◇p0 jedoch trotzdem als charakteristische Ku -Tautologie,
da ◇p0 → ◻◇p0 für alle nicht-kombinierten K-Erweiterungen nur in Ku tautologisch ist.
11
16
3.2.2
Ein offener Wahrheitsbaum
Das Ablesen von Gegenmodellen von einem offenen, aber vollständig entwickelten Wahrheitsbaum funktioniert für die K-Erweiterungen genauso wie für K selbst: Jeder offene
Ast liefert uns eine Weltenmenge W , eine Zugänglichkeitsrelation R auf W und eine (unvollständige) basale K-Interpretationsfunktion IW,R . Betrachten wir den Wahrheitsbaum,
der zeigt, dass ◻p0 → ◻◻p0 keine Krs -Tautologie ist:
w0 ∶ ¬(◻p0 → ◻◻p0 )
w0 ∶ ◻p0
w0 ∶ ¬◻◻p0
w0 Rw0
w 0 ∶ p0
w0 ∶ ◇¬◻p0
w0 Rw1
w1 ∶ ¬◻p0
w1 Rw1
w1 Rw0
w 1 ∶ p0
w1 ∶ ◇¬p0
w1 Rw2
w2 ∶ ¬p0
w2 Rw2
w2 Rw1
Dieser Wahrheitsbaum wurde vollständig entwickelt, da sich keine weitere Regel anwenden
lässt. Von seinem offenen Ast können wir nun ein Krs -Gegenmodell ablesen, also ein Krs Modell ⟨W, R, IW,R ⟩ mit I W,R (w, ◻p0 → ◻◻p0 ) = f für ein w ∈ W :
17
• W = {w0 , w1 , w2 }
• R = {⟨w0 , w0 ⟩, ⟨w0 , w1 ⟩, ⟨w1 , w0 ⟩, ⟨w1 , w1 ⟩, ⟨w1 , w2 ⟩, ⟨w2 , w1 ⟩, ⟨w2 , w2 ⟩}
• IW,R (p0 , w0 ) = t
• IW,R (p0 , w1 ) = t
• IW,R (p0 , w2 ) = f
• Der Rest von IW,R sei beliebig.
Wichtig bei Gegenmodellen der K-Erweiterungen ist, die Zugänglichkeitsrelationen genau unter die Lupe zu nehmen: Haben sie wirklich alle geforderten Eigenschaften? Das
Krs -Gegenmodell für den obigen Baum muss reflexiv und symmetrisch sein – sonst ist es
kein Krs -Gegenmodell. Wurde ein zugrundeliegender Wahrheitsbaum wirklich vollständig entwickelt, so enthält er auch alle relevanten Zugänglichkeits-Annahmen, die dann
einfach abgelesen werden können. Dementsprechend gilt natürlich: Hat die Zugänglichkeitsrelation eines vermeintlichen Kx⃗ -Gegenmodell nicht alle von der Erweiterung geforderten Eigenschaften, so muss der zugrundeliegende Wahrheitsbaum noch um weitere
Zugünglichkeits-Annahmen erweitert werden. Betrachten wir die Zugänglichkeitsrelation
R unseres obigen Krs -Gegenmodell, so sehen wir: Die Paare ⟨w0 , w0 ⟩, ⟨w1 , w1 ⟩ und ⟨w2 , w2 ⟩
sind enthalten – also ist R reflexiv; und alle von der Symmetriebedingung geforderten
Paare sind ebenfalls enthalten – also ist R symmetrisch.
3.2.3
(Unendliche Wahrheitsbäume
Zum Schluss betrachten wir noch einen besonderen Fall: Für manche K-Erweiterungen
gibt es unendliche Wahrheitsbäume. Es ist nicht möglich, von solchen Wahrheitsbaum
ein endliches Gegenmodell einfach abzulesen.12 Schauen wir uns den Wahrheitsbaum an,
der zeigt, dass ◻p0 keine Ke -Tautologie ist: Die Ausgangsliste:
12
Bei einem endlichen Gegenmodell sind Weltenmenge und Zugänglichkeitsrelation endlich.
18
w0 ∶ ¬◻p0
w0 ∶ ◇¬p0
w0 Rw1
w1 ∶ ¬p0
w1 Rw2
w2 Rw3
w3 Rw4
⋮
Dieser Wahrheitsbaum lässt sich immer weiter fortsetzen, da er sich nicht schließen lässt
und da aufgrund der e-Regel von jeder neu hinzugekommenen Welt wieder die Zugänglichkeit zu einer weiteren neuen Welt angenommen werden kann. Somit lässt sich kein
endliches Ke -Gegenmodell vom Wahrheitsbaum ablesen. Da ◻p0 aber keine Ke -Tautologie
ist, muss es ein Ke -Gegenmodell geben. Doch wie ergibt es sich? Nun, ungünstigerweise
nur durch geduldiges Ausprobieren. Überlegen wir noch einmal, wie ein Ke -Gegenmodell
für die Behauptung, dass ◻p0 eine Ke -Tautologie ist, beschaffen sein muss: Es muss ein
Ke -Modell sein, in dem es mindestens eine Welt w gibt, sodass ◻p0 relativ zu w falsch ist.
Probieren wir es mit einer 1-elementigen Weltenmenge, also W = {w0 }. Damit ◻p0 relativ
w0 falsch ist, muss es mindestens eine Welt w geben, sodass w0 Zugang zu w hat und p0
relativ zu w falsch ist. Wir könnten natürlich eine von w0 verschiedene Welt annehmen,
zu der w0 Zugang hat – das hätte allerdings die Nachteile, dass wir unsere Weltenmenge
W vergrößern müssten, und dass diese neue Welt wiederum Zugang zu einer Welt haben
müsste (wegen der geforderten Extendabilität). So groß muss unser Ke -Gegenmodell gar
nicht werden. Stattdessen nehmen wir einfach an, dass w0 Zugang zu sich selbst hat, also
R = {⟨w0 , w0 ⟩}. Nun müssen wir nur noch fordern, dass p0 relativ zu w0 falsch ist, also
IW,R (w0 , p0 ) = f. Der Rest der basalen K-Interpretationsfunktion kann beliebig aufgefüllt
werden. Und fertig ist unser Ke -Gegenmodell.
Auch Kt kann unendliche Wahrheitsbäume erzeugen. Betrachten wir als letztes Beispiel
einen Wahrheitsbaum, der zeigt, dass ¬(◇p0 ∧ ◻◇p0 ) keine Kt -Tautologie ist:
19
w0 ∶ ¬¬(◇p0 ∧ ◻◇p0 )
w0 ∶ ◇p0 ∧ ◻◇p0
w0 ∶ ◇p0
w0 ∶ ◻◇p0
w0 Rw1
w 1 ∶ p0
w1 ∶ ◇p0
w1 Rw2
w 2 ∶ p0
w0 Rw2
w2 ∶ ◇p0
w2 Rw3
w 3 ∶ p0
w0 Rw3
⋮
Dieser Wahrheitsbaum lässt sich unendlich lang fortsetzen. Dennoch gibt es auch hier
ein sehr kleines Kt -Gegenmodell, welches zwar nicht vom Wahrheitsbaum selbst geliefert
wird, aber schnell gefunden werden kann:
• W = {w0 }
• R = {⟨w0 , w0 ⟩}
• IW,R (w0 , p0 ) = t
• Der Rest von IW,R sei beliebig.
20

Download Report