苦しんで覚える選好の論理学

みんなが待ち望んていた(?)Advent calender1日目。まさかの遅刻からスタートですごめんなさい。

トップバッターは渋めな誰得論理学から。こんな記事しかかけなくてすまん。

前提

古典論理学においては、記述された論理式は「正しい」か「正しくない」かのどちらかです。しかし、現実世界では、論理は「より望ましい」「より望ましくない」と比較しなければならない時があるかもしれません。そこで、古典論理学では表現できなかった選好を様相論理を使って表現する方法を紹介します

論理学では、古典論理学に新しい要素を付け足したり差し引いたりして、それらが「意味のある」体系を作ることができるかどうかが焦点となります。具体的に以下のような疑問を解決できるかを議論することが多いです。

• その論理言語はどんな文法で書かれるか?
• その論理言語を「満たす」とはどういうことか？(モデル、解釈の定義)
• その論理言語はどのような推論規則をもつか？
  • その推論規則はモデルの定義と一貫しているか？
• その論理言語は何を表現できるか？
  • 既存の論理言語や概念を表現することはできるか？
  • より複雑な論理体系を表現するのに十分な表現力を持っているか？

これらを踏まえてModal Betterness logicを紹介します。

様相「良さ」論理(modal betterness logic)

文法の定義

Modal Betterness Logicは次の文法で与えられます。(様相論理がわからない人はここまでどうぞ)

\def\or{\mathrel{|}}
\varphi = p \or \neg\varphi\or\varphi\wedge\psi\or\langle\leq\rangle\varphi\or\langle<\rangle\varphi\or E \varphi

通常の論理に$\langle\leq\rangle$と$\langle<\rangle$と$E$の3つの様相が追加された論理です。意味はそれぞれ以下のようになります。

• $\langle\leq\rangle\varphi$の時、現在の世界よりもより良い(望ましい)ある世界、あるいは同等に良いある世界において$\varphi$は真である。
• $\langle<\rangle\varphi$の時、現在の世界よりも厳密により良い(望ましい)ある世界において$\varphi$は真である。
• $E\varphi$の時、$\varphi$が真となる世界が存在する

モデルの定義

Modal Betterness Logicに対応するモデル(解釈)はModal Betterness Modelと呼ばれ、$\mathcal{M}=(S, \leq, V)$で表されます。

• $S$は可能世界の集合
• $\leq$は$S$上の反射的、推移的関係($s\leq t$のとき、$t$は$s$より良いという意味)
• $V$は論理式から可能世界への写像

Modal betterness model とModal betterness logicの関係は次のようになります: $\mathcal{M}, s\models \varphi$(論理式$\varphi$が$\mathcal{M}$の$s$において真であるという意味)が次のように定義されます

• $\mathcal{M}, s\models \top$
• $s\in V(p)$ ならば$\mathcal{M}, s\models p$
• $\mathcal{M}, s\models \varphi$でないならば$\mathcal{M}, s\models \neg\varphi$
• $\mathcal{M}, s\models \varphi$かつ$\mathcal{M}, s\models \psi$ならば$\mathcal{M}, s\models \varphi\wedge\psi$
• ある$s\leq t$を満たす$t$が$\mathcal{M}, t\models \varphi$を満たすならば、$\mathcal{M}, s\models \langle\leq\rangle\varphi$
• ある$s<t$を満たす$t$が$\mathcal{M}, t\models \varphi$を満たすならば、$\mathcal{M}, s\models \langle<\rangle\varphi$
• ある$t\in S$が$\mathcal{M}, t\models \varphi$を満たすならば、$\mathcal{M}, s\models E\varphi$

(具体例)休日の過ごし方

ある休日に暇なので家族でどこかに出かける（あるいは家にいる)ことにしました。選択肢は以下の通りです。

	雨の日に濡れる($p$)	雨の日に濡れない($\neg p$)
安い($q$)	公園($s$)	美術館($t$)
高い($\neg q$)	遊園地($u$)	水族館($v$)

「安いところに行きたい」という選好は次のように表されるでしょう。

\langle\leq\rangle q

(現在のプランにかかわらず)論理式を満たす関係$\leq$として自明なものとして$u = v < s = t$が挙げられますが、$u < s < v < t$なんかもモデルになります(極大値の可能世界が$q$を満たしているため)。

「現在のプランが雨の日に濡れないプランならば(雨が降っている可能性が高いので)、安いところに行きたい」という選好は次のようになります。

\neg p \rightarrow \langle \leq \rangle q

現在の可能世界が$s$か$u$であれば論理式は常に真です。現在の可能世界が$t$か$v$であれば、上記のような選好を持たなければなりません。

公理の定義

以下の公理は

1. 通常の命題論理の公理
2. $[\leq](\varphi\rightarrow\psi) \rightarrow ([\leq]\varphi\rightarrow[\leq]\psi)$
3. $[<](\varphi\rightarrow\psi) \rightarrow ([<]\varphi\rightarrow[<]\psi)$
4. $[\leq]\varphi \rightarrow \varphi$
5. $[\leq]\varphi \rightarrow [\leq][\leq]\varphi$
6. $U(\varphi\rightarrow\psi) \rightarrow (U\varphi\rightarrow U\psi)$
7. $U\varphi \rightarrow \varphi$
8. $U\varphi \rightarrow UU\varphi$
9. $\neg U\varphi \rightarrow U\neg U\varphi$
10. $[\leq]\varphi \rightarrow [<]\varphi$
11. $[<]\varphi \rightarrow [\leq][<]\varphi$
12. $[<]\varphi \rightarrow [<][\leq]\varphi$
13. $[\leq]([\leq]\varphi\vee\psi)\wedge[<]\psi\rightarrow\varphi\vee[\leq]\psi$
14. $U\varphi\rightarrow[\leq]\varphi$
15. $E\varphi\leftrightarrow\neg U\neg\varphi$
16. $\langle\leq\rangle\varphi\leftrightarrow\neg [\leq]\neg\varphi$
17. $\langle<\rangle\varphi\leftrightarrow\neg [<]\neg\varphi$

ただし、様相記号は以下の意味です

• $U\varphi$のとき、$\varphi$は全ての世界で真(公理15）
• $[\leq]\varphi$の時、現在の世界よりもより良い(望ましい)全ての世界、また同等に良い全て世界において$\varphi$は真である。(公理16)
• $[<]\varphi$の時、ある現在の世界よりも厳密により良い(望ましい)全ての世界において$\varphi$は真である。(公理17)

一般選好(Generic preference)

可能世界の選好$s\leq t$から可能世界の集合の選好$S\trianglelefteq T$に昇華させるGeneric preferenceの4つの定義をします。

1. $S \trianglelefteq^{\forall\forall} T \iff \forall s\in S \forall t\in T s\leq t$
2. $S \trianglelefteq^{\forall\exists} T \iff \forall s\in S \exists t\in T s\leq t$
3. $S \trianglelefteq^{\exists\forall} T \iff \exists s\in S \forall t\in T s\leq t$
4. $S \trianglelefteq^{\exists\exists} T \iff \exists s\in S \exists t\in T s\leq t$

可能世界の集合を、可能世界が満たす解釈集合をもつ論理式として扱うと、 Modal betterness logicによってGeneric preferenceを定義できます

1. $\varphi \trianglelefteq^{\forall\forall} \psi \iff U(\psi\rightarrow[<]\neg\varphi)$、ただし$\leq$が完全
2. $\varphi \trianglelefteq^{\forall\exists} \psi \iff U(\varphi\rightarrow\langle\leq\rangle\psi)$
3. $\varphi \trianglelefteq^{\exists\forall} \psi \iff E(\psi\wedge[<]\neg\varphi)$、ただし$\leq$が完全
4. $\varphi \trianglelefteq^{\exists\exists} \psi \iff E(\varphi\wedge\langle\leq\rangle\psi)$

1、3については、$\leq$が完全でない場合は表現できないことが知られています。

(例の続き)

「安いことは雨に濡れないことよりも重要である」 というGeneric preferenceは$\neg p\trianglelefteq q$のように表されます。$\trianglelefteq^{\forall\forall}$を使うと、

U(q\rightarrow[<]p)

のように表され、

$\trianglelefteq^{\exists\exists}$を使うと、

E(\neg p\wedge\langle \leq\rangle q)

のように表され、選択肢$t$が存在する限り、$\neg p\wedge q\not\models\bot$よりトートロジーとなります。

条件選好(conditional preference)

Conditional preference $P^\psi \varphi$は「$\psi$を満たす可能世界のうち、最も良い物は、$\varphi$を満たす」という意味です。これは以下のように表現できます

P^\psi\varphi := U((\psi \wedge \neg\langle<\rangle\psi)\rightarrow\varphi)

ただし、$<$が上の整礎関係である(極大値が定義できる)時に限ります。

(例の続き)

外を見ると雨が降っていることに気がつきました。雨に濡れない($q$)という条件で最も良い物は安いものであるという条件は次のように表されます

P^{\neg p} q = U((\neg p \wedge \neg\langle<\rangle p)\rightarrow q)

$v < t$を満たす選好が当てはまります。

関連

• 認識論理(epistemic logic)
  • 「〇〇であることがある」ということと「必ず〇〇」ということを分離させた様相論理。選好論理の$E$と$U$のみが使われる論理といって良い(というかこっち先に紹介すべきだったかも)
• 信念基底改訂(belief base revision)
  • 自分の信念を、新しい情報を元に更新するフレームワーク。新しい情報が真である中で（選好関係において）最も良い信念に置き換えるという変換を行う

え?これプログラミングの記事だったの?

え？

参考文献

Reasoning about Preference Dynamics - Fenlong Liu