WikiDer > Kripke-Modell

EIN Kripke-Modell ist ein Model vor dem Modale Logiks und andere nicht-klassische Logikist wie die Intuitionistische Logik. Kripke-Modelle verdanken ihren Namen ihrem Erfinder, Saul Kripke. Sie formalisieren die Idee mehrerer möglicher Welten.

Definition

Formal ist ein Kripke-Modell ${displaystyle {mathcal {M}}}$ ein bestellter Dreier ${displaystyle langle W,R,Vangle }$ bei welchem ${Anzeigestil W}$ ist eine Sammlung von "Welten" (oder Punkten), ${Anzeigestil R}$ ein Beziehung auf ${Anzeigestil W}$ (das Zugänglichkeitsbeziehung) und ${Anzeigestil V}$ ein Funktion das zu a atomarer Satz${displaystyle p}$ weist eine Sammlung von Welten zu, in denen ${displaystyle p}$ wo ist.

${Anzeigestil V}$ wird zu einer Wahrheitsrelation erweitert ${displaystyle Vdash }$ zwischen Modellen, Welten und Sätzen der Modallogik wie folgt:

• ${displaystyle {mathcal {M}},wVdash p}$desda${displaystyle win V(p)}$ (${displaystyle p}$ ein atomarer Satz)
• ${displaystyle {mathcal {M}},wVdash zB A}$ desda ${displaystyle {mathcal {M}},wot Vdash A}$ (Negation)
• ${displaystyle {mathcal {M}},wVdash Aland B}$ desda ${displaystyle {mathcal {M}},wVdash A}$ und ${displaystyle {mathcal {M}},wVdash B}$ (Verbindung)
• (Ähnliche Regeln für Disjunktion usw.)
• ${displaystyle {mathcal {M}},wVdash Box A}$ desda ${displaystyle forall w'in W(wRw' o {mathcal {M}},w'Vdash A)}$

Die letzte Zeile formalisiert die Idee der notwendigen Wahrheit: ${Anzeigestil A}$ ist wahr in ${Anzeigestil w}$dann und nur dann, wenn${Anzeigestil A}$ wo ist alles getroffen ${Anzeigestil w}$ verbundene Welten. Je nachdem, wie die Beziehung ${Anzeigestil R}$ interpretiert sind dies zum Beispiel alle denkbaren Welten für die in der Welt lebenden Menschen ${Anzeigestil w}$ Leben, nach allen zukünftigen Welten ${Anzeigestil w}$, alle wünschenswerten Welten usw.

In dem epistemische Logik Häufig werden umfangreiche Kripke-Modelle verwendet, die eine ganze Kollektion abdecken Zugänglichkeitsbeziehungen verwenden (einer pro Akteur).

Beispiel

Ein Kripke-Modell mit einer zugänglichen Beziehung zwischen den Welten w₁, ..., w₅.

Das gezeigte Kripke-Modell kann wie folgt definiert werden:

${displaystyle W={w_{1},w_{2},w_{3},w_{4},w_{5}}}$

${displaystyle R={(w_{1},w_{2}),(w_{2},w_{3}),(w_{2},w_{4}),(w_{3},w_{3 }),(w_{3},w_{5}),(w_{4},w_{5})}}$

${Anzeigestil V(phi)={w_{3},w_{4}}}$, ${Anzeigestil V(psi)={}}$ vor dem ${Anzeigestil psi eq phi }$

Im gegebenen Beispiel gelten beispielsweise die folgenden Formeln in Welt ${displaystyle w_{1}}$:

${displaystyle {mathcal {M}},w_{1}Vdash zB phi}$,

${displaystyle {mathcal {M}},w_{1}Vdash Box zB phi }$,

${displaystyle {mathcal {M}},w_{1}Vdash Diamond Diamond phi }$.

Rahmeneigenschaften

Die Komponente ${displaystyle langle W,Rangle}$ wird es sein Rahmen eines Kripke-Modells. Dieser Rahmen kann bestimmte Eigenschaften haben, wie zum Beispiel, dass jede Welt w eine zugängliche Welt v ist das erreichbar von w. Wenn die Beziehung R Wenn es bestimmte Eigenschaften hat, soll der Rahmen diese auch haben. Zum Beispiel: ein Rahmen ist reflexiv wenn die Relation R a . ist reflexive Beziehung ist. In einem reflexiven Rahmen gelten Modalformeln, die nicht auf einen Rahmen zutreffen müssen, der diese Eigenschaft nicht besitzt. Zum Beispiel in einem reflexiven Rahmen, ${Displaystyle Box StärkePfeil p}$ in jeder Welt.

Bisimulation

sehen Bisimulation für den Hauptartikel zu diesem Thema.

Das Konzept der Bisimulation wird verwendet, um Kripke-Modelle zu vergleichen: Die Idee ist, dass Welten in verschiedenen Modellen bisimilar sind, wenn sie die gleichen Aussagen- und Modalformeln erfüllen. Mit anderen Worten, in solchen Welten gelten die gleichen Formeln und es ist möglich, von beiden bisimilaren Welten über die Zugänglichkeitsbeziehung. In diesem Fall gibt es keine Modalformeln, die verwendet werden können, um die Welten zu unterscheiden: Es gibt keine Formel, die in der einen Welt gilt, aber nicht in der anderen. Wenn dies möglich ist, sind die Welten nicht biähnlich.

Ein Beispiel: Angenommen, wir haben ein Modell ich mit einer Welt w mit einem Pfeil zu sich. In dieser Welt gilt die Atomformel geldt p. Wir haben auch ein Modell Nein mit einer Welt v und eine Welt Sie auf was trifft das zu v ist erreichbar von Sie und Sie erreichbar von v. Sowohl Sie wenn v gilt die formel p. Das gilt jetzt w ist der Welt bisimähnlich v und auch mit der welt Sie. Jede Formel, die in gilt w gilt auch in der Welt v und in der Welt Sie. Dies gilt für die Atomformeln (${displaystyle {mathcal {M}},wVdash p}$ und ${displaystyle {mathcal {N}},vVdash p}$, ${displaystyle {mathcal {N}}, uVdash p}$) aber auch für Modalformeln wie ${displaystyle {mathcal {M}},wVdash Diamond p}$ oder ${displaystyle {mathcal {M}},wVdash Diamond Diamond p}$.

Siehe die Kategorie Kripke-Modelle von Wikimedia Commons für Mediendateien zu diesem Thema.