様相論理 - 井戸端

様相論理

Modal logic - Wikipedia

最も基本的な箇所に関する記述が抜けていることに注意

もう知っていてつまらないのであとに回しているSummer498.icon

関係意味論

様相論理の標準的な意味論は関係意味論と呼ばれる。

このアプローチでは、式の真偽は、しばしば可能世界と呼ばれる点を基準として決定される。様相演算子を含む式の場合、その真理値は他の到達可能な世界で何が真であるかに依存する可能性がある。

関係意味論は、以下のように定義されるモデルを用いて様相論理の式を解釈する。

関係モデルは組$ \mathfrak{M}=(W,R,V)として定められる。ここで、

$ Wは可能世界集合とする (宇宙とも呼ばれる)

$ Rは$ W上の二項関係とする (到達可能性関係と呼ばれる)

$ Vは各原子論理式と世界のペアに真偽値を割り当てる評価関数とする

$ V:W\times F\rightarrow\{0,1\}ただし、$ Fは原子論理式

ここに宇宙が出てきたか！Summer498.icon

評価関数

モデル$ {\displaystyle {\mathfrak {M}}}の世界$ {\displaystyle {\color{red}w}}における式の真偽を以下のように再帰的に定義する。

$ {\displaystyle {\mathfrak {M}},{\color{red}w}\models P} $ \iff $ {\displaystyle V({\color{red}w},P)=1}

$ {\displaystyle {\mathfrak {M}},{\color{red}w}\models \neg P} $ \iff $ {\displaystyle {\color{red}w}\not \models P}

$ {\displaystyle {\mathfrak {M}},{\color{red}w}\models (P\wedge Q)} $ \iff $ ({\displaystyle {\color{red}w}\models P}) \land ({\displaystyle {\color{red}w}\models Q})

$ {\displaystyle {\mathfrak {M}},{\color{red}w}\models \Box P} $ \iff $ ^{\forall {\color{#0d0}u} \in {W}}\lbrack{(\displaystyle {\color{red}w}R{\color{#0d0}u}})\Rightarrow({\displaystyle {\color{red}w}\models P}\rbrack)

$ {\displaystyle {\mathfrak {M}},{\color{red}w}\models \Diamond P} $ \iff $ ^{\exist{{\color{#0d0}u}}\in\{{{\color{#0d0}u}}\in{W}|{{\color{red}w}R{\color{#0d0}u}}\}}\lbrack{\displaystyle {\color{#0d0}u}\models P}\rbrack

到達可能性

Accessibility relation - Wikipedia

到達可能性関係は、様相論理の関係意味論において、文に真理値を割り当てる際に重要な役割を果たす関係である。

到達可能性関係$ {\displaystyle R}が$ {\displaystyle w}を$ {\displaystyle v}に関連付けている場合のみ、可能世界$ {\displaystyle w}における様相論理式の真理値が、別の可能世界$ {\displaystyle v}における真値に依存する。

例えば、

$ {\displaystyle P}が$ {\displaystyle wRv}となるような世界$ {\displaystyle v}において成立する場合、論理式$ {\displaystyle \Diamond P}は$ {\displaystyle w}において真となる。

$ {\displaystyle R}が$ {\displaystyle w}を$ {\displaystyle v}に関連付けないのであれば、$ {\displaystyle \Diamond P}は$ {\displaystyle w}において偽となる。

ただし、$ {\displaystyle P}が他の世界$ {\displaystyle u}でも成立し、$ {\displaystyle wRu}となる場合はこの限りではない。

フレームと完全性

到達可能性関係$ Rの選択だけで、式の真偽を保証するのに十分なことがある。

$ Gを可能世界集合とし、$ Rを$ G上の二項関係とする。

関係フレームは対$ \mathfrak{M}=(G,R)として定められる。

フレームの一覧

反射性: $ ^{\forall {\color{red}w} \in G}[{\color{red}w}R{\color{red}w}]

対称性: $ ^{\forall {\color{red}w},{\color{#0c0}u}\in G}[{\color{red}w}R{\color{#0c0}u}\Rightarrow {\color{#0c0}u}R{\color{red}w}]

推移性: $ ^{\forall {\color{red}w},{\color{#0c0}u},{\color{#00f}q}}[{\color{red}w}R{\color{#0c0}u}\land {\color{#0c0}u}R{\color{#00f}q}\Rightarrow {\color{red}w}R{\color{#00f}q}]

連続性: $ ^{\forall {\color{red}w},\exist {\color{#0c0}u}\in G}[{\color{red}w}R{\color{#0c0}u}]

ユークリッド性: $ ^{\forall {\color{red}w},{\color{#0c0}u},{\color{#00f}t}}[{\color{red}w}R{\color{#0c0}u}\land {\color{red}w}R{\color{#00f}t}\Rightarrow {\color{#0c0}u}R{\color{#00f}t}]

ユークリッド性と対称性から、$ {\color{#00f}t}R{\color{#00f}t}\land {\color{#0c0}u}R{\color{#0c0}u}と同様に$ {\color{#00f}t}R{\color{#0c0}u}を含意する。

様相論理の体系

様相論理の様々な体系は、フレーム条件を用いて定義される。

これらのフレーム条件から体系を構成する論理は次のとおりである。

各種公理とフレームの関係

体系K: 無条件

可能性演算子の定義: $ \Diamond p:=\neg \Box \neg p

公理N: 必然化規則 : $ Aが無仮定で証明可能ならば、$ \Box Aもまた無仮定で成立する。

公理K (分配律) : $ \Box (A\rightarrow B)\rightarrow (\Box A\rightarrow \Box B)

体系D: 連続的

公理D: $ \Box p\to \Diamond p

公理D := 公理K + 公理D