数理解析研究所講究録1093 巻 1999 年 168-172

168

最小 normal 論理 K より小さい擬論理の標準形展開
椙山女学園大学 大芝 猛 (Takeshi

知識論理または multi-modal logi$\mathrm{n}$個の modal operator$\cdots$$\mathrm{K}_{1},$は命題論理の標準形展開の拡張により特性化される。

,Kn に関する様々な公理をもついくつかの n-modal logic(m)「命題論理の最小項の集合$\mathrm{c}$oshiba)$\mathrm{W}^{(0)}=\{\mathrm{p}_{1}\wedge\delta 1\ldots\wedge \mathrm{p}_{\mathrm{m}}\delta \mathrm{m} | \delta 1, \cdots, \delta \mathrm{m}\in \mathrm{t}0,1\}1$

但し$\langle\delta=1)$$\mathrm{p}^{\delta}$$(\delta=0)$$\mathrm{K}_{1}[\mathrm{U}_{1}]$$=\{<\mathrm{g}$$\}\mathrm{m})\mathrm{W}^{\mathrm{t}+}\mathrm{k}1)$:,$>|\mathrm{g}\in \mathrm{W}(\mathrm{m})(\mathrm{k}),$$\mathrm{U}1,$$\cdots$, Un$\subseteq(\mathrm{m})\mathrm{W}^{(\mathrm{k})}\}$$\mathrm{k}_{\mathrm{n}}[\mathrm{u}_{\mathbb{R}}]$$(\mathrm{k}=0,1,2, \cdots)\lrcorner$を

以下は mul i-modal でも可能であるが、 un i-modal の場合に限って述べる。
$\mathrm{t}$論理式 Alm)

(k)
$l$

に対し

$(^{(\mathrm{m})}f\langle \mathrm{k})$は高々 m 変数 P1,,Pm を含で判定することにある :$\perp \mathrm{g}1$

(m)

但し、

であり、

$\mathrm{w}_{\mathrm{A}\cdot\llcorner}=\mathrm{W}(\mathrm{m})\mathrm{A}\cap(\mathrm{m})\mathrm{W}_{\mathrm{L}}(\mathrm{k}1$

(m)

WA

$(\subseteq(\mathrm{m})\mathrm{W}^{(\mathrm{k})})$の定義は後述の$(\mathrm{d}\mathrm{e}\mathrm{f})$内に記述される。
特に$\mathrm{L}$が命題論理 L(の場合には ($*\rangle$

は(m)

め、よく知られたつぎの形となる。

LO$\vdash$A$\mathrm{t}\mathrm{m}$$\Leftrightarrow$)$\eta_{\mathrm{A}}=^{\mathrm{t})}\mathrm{w}^{()}\mathrm{m}0$

ここで、つぎの Proposition が成立する。

WLO$(-)=\mathrm{W}(\mathrm{m})(0)$,(m)$\mathrm{W}_{\mathrm{A}\cdot \mathrm{L}0}=\mathrm{t}\mathrm{m}$)WA であるた169(1) A のでの setwise-expansion(m)WA$(\underline{\mathrm{N}1})$

:

A

ト

$\mathrm{L}$(2) 各基底集合(m)$\equiv*(\mathrm{m})\mathrm{W}_{\mathrm{A}}$$\mathrm{W}\langle \mathrm{k}$

)

の

mean

$\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{l}$$\mathrm{i}\mathrm{n}\mathrm{g}$(内の最小項の論理和) が$\mathrm{W}(\mathrm{k})$$\mathrm{L}$

で証明可能

なこと :
$(\mathrm{N}A2 :\mathrm{L} \vdash *\langle \mathrm{m})\mathrm{w}\langle \mathrm{k})$$\langle \mathrm{d}\mathrm{e}\mathrm{f})$このような標準形展開に用いられる、基礎集合 (m)の要素 (最小項) などの$\langle$

1)$\mathrm{U}=\mathrm{t}\mathrm{f}\mathrm{l},$(2)$\langle$$\cdots,\mathrm{r}\mathrm{r}$$\langle *\mathrm{f}=\rangle*<\mathrm{g}$

3)

}

“

logical meaning$\equiv \mathrm{K}(^{*}\mathrm{U})\wedge$$\mathrm{u}$(m)$(\mathrm{d}\mathrm{e}\mathrm{f})$

窪X

$($

.

$\neg \mathrm{K}\langle^{*}\mathrm{X}\rangle$$)$

W\alpha )WA の定義 : 論理式 A の set-wise expansion (論理

(m)

1)

$*\mathrm{U}\equiv \mathrm{r}*\mathrm{l}\mathrm{v}\cdots\vee*\mathrm{f}\mathrm{r}$$\mathrm{K}[\mathrm{U}]>\equiv*\mathrm{g}\wedge*\mathrm{K}[\mathrm{U}]$$\wedge$$*\mathrm{K}[\mathrm{U}]$、その部分集合、それらは次のように定義する :

”

につき、

$(\subseteq(\mathrm{m})\mathrm{w}^{(\mathrm{k}}))$

,

$*$

(k)
$\mathrm{W}$$\mathrm{w}_{\mathrm{p}_{\mathrm{j}}=}\{\mathrm{p}1\delta 1_{\wedge\cdots\Lambda \mathrm{P}\mathrm{j}1}-\delta$

j-l$\mathrm{L}$に独立な)$|\delta 1,$$\mathrm{p}_{\mathrm{j}+1}\delta \mathrm{j}+1_{\wedge}\ldots\wedge \mathrm{p}_{\mathrm{m}}\delta \mathrm{m}$$\cdots,$$\delta \mathrm{j}-1,$$(\mathrm{m})\mathrm{W}\mathrm{B}\wedge \mathrm{C}=$3)$\langle \mathrm{m})\mathrm{W}_{\mathrm{B}}<\mathrm{k}>\cap (\mathrm{m})\mathrm{W}_{\mathrm{C}}<\mathrm{k}\succ , \mathrm{k}=\max(\deg(\mathrm{B}),\deg(\mathrm{C})\rangle$$( \mathrm{m}\}\mathrm{W}_{\mathrm{B}^{\backslash }}\sqrt \mathrm{c}= (\mathrm{m})\mathrm{W}_{\mathrm{B}}<\mathrm{k}>\cup.

$4\rangle$$(\mathrm{m})\mathrm{W}_{\neg \mathrm{B}}=$

5)

(m)

6)

(m)

$(\mathrm{m})\mathrm{W}<\mathrm{k}\succ-$(\mathrm{m})\mathrm{W}_{\mathrm{C}}<\mathrm{k}\succ .’,$(\mathrm{m})\mathrm{W}_{\mathrm{B}}$$\mathrm{K}[\mathrm{X}]>$$\mathrm{W}_{\kappa}(\mathrm{B}\rangle=\mathrm{t}<\mathrm{g},$$|$\mathrm{k}=\max\langle\deg(\mathrm{B}),\deg(\mathrm{C}))$$\mathrm{k}=\deg(\mathrm{B})$,$\mathrm{W}_{\mathrm{B}\supset}\mathrm{c}=(^{(\mathrm{m}\rangle}\eta^{<}\mathrm{k}>-(\mathrm{m})\mathrm{W}\mathrm{B}^{<})\mathrm{k}>\mathrm{U}(\mathrm{m})\mathrm{w}_{\mathrm{c}}<\mathrm{k}\succ$

但し、$\cdots$$\delta \mathrm{m}\in\{0,1\}\}$$\ldots,$

2)$\delta \mathrm{J}+1,$$\mathrm{g}\in(\mathrm{m})\mathrm{w}(\mathrm{k}),$$\mathrm{k}=\max\langle\deg\langle \mathrm{B}),\deg(\mathrm{C}))$,$\chi\subseteq(\mathrm{m})\eta_{\mathrm{B}}\}$$\mathrm{k}=\deg(\bm{\mathrm{B}})$,$\mathrm{U}^{<\mathrm{k}>}=\mathrm{U}’ \mathrm{k}-\downarrow$$\mathrm{U}\subseteq^{-}(\mathrm{m})\eta^{<\iota}>,$.

対し、$\mathrm{k}\geqq 1$$\mathrm{U}’$[註] これらの定義から直接 :$=\dagger<\mathrm{g}.\ovalbox{\tt\small REJECT}$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{D}\mathrm{O}\mathrm{S}$とし、$\mathrm{K}[\mathrm{X}]>$

’

ition

O ある論理 にたいし、 $(\#)$ をみたす$\mathrm{L}$$|$$\mathrm{g}\in \mathrm{U}$,$\mathrm{X}\subseteq(\mathrm{m})\mathrm{W}^{(}1)\}$$\langle \mathrm{m})\underline{\mathrm{W}*\mathrm{u}=\mathrm{u}\mathrm{l}\mathrm{u}\subseteq \mathrm{t}\mathrm{m})\mathrm{w}(\mathrm{k})})(\underline{.\mathrm{X}.\cdot}\rangle$$\langle$$\mathrm{m})\mathrm{w}_{\mathrm{L}}(\mathrm{k})\langle \mathrm{k}=0,1,2$, .. : $\mathrm{m}=0,1,2,$$\cdot$とする。.
が証明される。
$\cdots$)$\text{は}\mathrm{r}_{\underline{\mathrm{L}}}$(set-wize expression1ike に)$\mathrm{O}$

Lが

(m)

$\underline{\mathrm{K}}$$\mathrm{W}_{\mathrm{K}}\mathrm{t}\mathrm{k}),$$()^{1})7$

キの最小 normal 論理) ,$(\mathrm{m})\mathrm{W}\mathrm{s}4(\mathrm{k}),$$(\mathrm{m})\mathrm{W}_{\mathrm{s}}5(\mathrm{k}$}等は$\underline{\mathrm{S}4}$. 鐘等について、 それらを characterize する

170

例えば、

最小 normal 論理 K [公理:$\mathrm{K}\langle\psi\supset\phi$)$\supset(\mathrm{K}(\psi)\supset \mathrm{K}(\emptyset))$mm. .

とト\leftrightarrow 印 “jn-l 推論:$\mathrm{p}^{\frac{\psi}{\mathrm{K}(\emptyset)}]}$$\mathrm{P}$に対しては、,$(\mathrm{m})\mathrm{W}_{\mathrm{K}}\mathrm{t}0)=\underline{(\mathrm{m})\mathrm{N}10)}$

(m)

$=$

$\mathrm{W}\mathrm{K}\mathrm{t}\mathrm{k}+2)${$<\mathrm{g},$$\mathit{1}\mathrm{B}|-$$\text{て^{}:\epsilon\grave{\nu}}- \mathrm{A}h\mathrm{X}$’$\mathrm{K}$$\underline{(\mathrm{m})\mathrm{N}\kappa^{()}1}$[Ul,$\mathrm{K}$[Vl$\rangle|\underline{\mathrm{g}\in(\mathrm{m})\mathrm{W}(\mathrm{k})}$$\mathrm{V}=\mathit{1}\mathrm{f}|<\mathrm{f},$,$=\underline{(\mathrm{m})\mathrm{N}^{\mathrm{t}1})}$$\mathrm{K}[\mathrm{X}]\rangle\in \mathrm{V}$

, UC

(m)

for some$\mathrm{w}_{\mathrm{K}}(\mathrm{k}),$$\mathrm{X}\subseteq$

V.

$\subseteq(\mathrm{m})\mathrm{W}^{(\mathrm{k}}+1)$

,

’

}

$\mathrm{V}=1\mathrm{J}$$\langle \mathrm{m})\mathrm{W}_{\mathrm{K}}(\mathrm{k})\}0$,$\Leftrightarrow\forall\emptyset\forall\emptyset(\max(\deg(\emptyset), \deg(\emptyset))=\mathrm{k}\Rightarrow\langle_{\mathrm{g}}$

のように

一般に

$\underline{\mathrm{V}=\mathrm{U}},$は公理)$\mathrm{K}\{\psi\supset\emptyset$$\supset(\mathrm{K}1\psi)\supset \mathrm{K}\{\emptyset\})$からくる制約条件である。

.

$.\backslash$を成立させるための NI,N2 が証明されるためには、 論理 L の中の公理$(\#)$$\mathrm{K}\{_{\{\beta}\supset\emptyset\}\supset(\mathrm{K}\{\emptyset)\supset \mathrm{K}\{\phi)\}$が用いられている。

最小 normal 論理 K も (S4, めも) この公

理濠合 X 、でい孟

に基礎集合

(m)

$\mathrm{W}^{(\mathrm{k})}$の真部分集合であって、 基礎集合)$\langle$$\mathrm{m}).\eta\langle \mathrm{k}$の項全体は展開のために用いられていない。そこで、つぎのように
PROBLEM : 基礎集合($\mathrm{m}\rangle \mathrm{w}(\mathrm{k})$のすべての項が標準形展開のために必要となる論理

O 通常の意味での論理は公理と推論で規定される。従ってもし PROBLEM のような論理推論が K の推論$( \mathrm{m}.\mathrm{p}., \frac{\psi}{\mathrm{K}(\phi)})$$\mathrm{L}$$\mathrm{L}$でと同じ論理があれば、かかる論理 L を規定する公理は、 K のしかし、 NI,N2 が公理示される程度には強い公理である。

(このような公理は通常の代入法則を許す意味では、現在不明と考えられる$\mathrm{O}$$?$)

この問題に対する解答の 1 つはによって与えることができる。

$\underline{\mathrm{A}1^{\mathrm{r}}}$:$\text{「}[2]$によれば、かかる$\mathrm{P}$も’ 論理’ である。

$\text{」}$... (t)171,$\underline{\mathrm{m}.\mathrm{p}.}$この$\mathrm{P}$を用いるならば、:$\mathrm{P}$$\vdash$(V):$\mathrm{P}$$\vdash$(N–3):$\mathrm{P}$$\vdash$$(\underline{\mathrm{N}1})$$\cdot\frac{.\phi}{\mathrm{K}(\phi)}$Aを示すことができ、$\vdash^{(\mathrm{m})}\mathrm{w}_{\mathrm{P}}(\mathrm{k})=(\mathrm{m})\mathrm{W}^{(\mathrm{k})}$$\mathrm{P}$$\equiv*\langle \mathrm{m})\mathrm{W}_{\mathrm{A}}$$*(\mathrm{m})\mathrm{W}(\mathrm{k})$A(m)$\Leftrightarrow$

WA

$=$

$(\mathrm{m})\mathrm{W}^{(}\mathrm{k})$を証明することができる。

いえる。

参考文献
[1] M.

Study of$\mathrm{S}\mathrm{a}\mathrm{t}\mathrm{o}:\mathrm{A}$$\mathrm{K}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{k}\mathrm{e}-_{\mathrm{t}}\mathrm{y}\mathrm{P}\mathrm{e}$Models for some Modal Logics by Gentzen’$\mathrm{s}$Se-quential Method, Publications Research Institute for Mathematical Science,

Kyouto University , 1977
[2] R. Goldbratt: Logics of Time and Computation, Center for Study of Languages andInformat on, 1992$\mathrm{i}$: 知識命題の標準形を用いる妥当性, 数理解析研究所講究 Bqr, 1%$5[41$ 大芝猛, 小橋–秀 : 知識論理・様相論理の標準形展開基底による特性化,
数理解析研究[3] 大芝猛, 小橋–秀

所講究録 BO, lffl$\mathrm{A}_{\mathrm{P}\mathrm{P}^{\mathrm{e}\mathrm{n}\mathrm{d}}}\mathrm{i}\mathrm{x}$$\langle$

「

:

{Nll&
$\langle$$[\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{t}\mathrm{l}]$–Nl):任意の A\in (m)$\perp \mathrm{g}\perp$$\vdash$

$)$

part:

$(\mathrm{N}2))\Rightarrow \mathrm{t}\mathrm{H}\mathrm{l}$$(\underline{\mathrm{N}\Sigma}):\mathrm{L}$}$ (#) の証明( $\underline{\{\mathrm{N}1\}\{N2) \Leftrightarrow

(k)

$l$

に対し

(k)
$L/$

(Proof) if Part:仮定 (m)$\equiv*(\mathrm{m})\mathrm{W}_{\mathrm{A}}$」が成立するならば、$*(\mathrm{m})\mathrm{N}(\mathrm{k})$任意の A\in (m)A$\mathrm{L}\vdash$に対し$\mathrm{N}_{\mathrm{A}\cdot\llcorner}=\mathrm{N}(\mathrm{m})\mathrm{L}\mathrm{t}\mathrm{k})$から (m)$\mathrm{w}_{\mathrm{L}}(\mathrm{k})\subseteq(\mathrm{m})$$\mathrm{W}_{\mathrm{A}}$. 従って、(1)

only if part:

はない故、
と

$\langle$$\mathrm{N}1)$(m)$\exists \mathrm{f}_{0}\in \mathrm{w}_{\mathrm{L}}(\mathrm{m})(\mathrm{k})\mathrm{s}$から、$\mathrm{L}\vdash$とせよ。 従って、 (m)$\mathrm{N}_{\mathrm{A}\cdot \mathrm{L}}\neq(\mathrm{m})\mathrm{W}\mathrm{L}(\mathrm{k})$.t.

$\mathrm{f}_{0}\not\in(\mathrm{m})\mathrm{W}_{\mathrm{A}}$$*\mathrm{t}^{(\mathrm{m})(\mathrm{k})}\mathrm{W}-\mathrm{f}\mathrm{f}0$

}).

.

(m)

(m)

$\mathrm{W}_{\mathrm{A}}\subseteq(\mathrm{m})\mathrm{W}^{(\mathrm{k})}-\{\mathrm{f}_{0}\}$$\mathrm{W}*\mathrm{f}0=\{\mathrm{f}_{0}\}$($(\mathrm{d}\mathrm{e}\mathrm{f})$$\mathrm{W}_{\mathrm{L}}(\mathrm{k})\subseteq(\mathrm{m})$. 故に$\mathrm{L}$の [註] (※))

WA で$\vdash\cdot \mathrm{A}$

と

172

$\mathrm{L}$$\mathrm{L}^{(\mathrm{k})}$トー$*\mathrm{f}_{0}$. 故に f. これは矛盾。
part:

(N1):

\preceq J 盆 の A として A$\supset*(\mathrm{m})$WA と$*(\mathrm{m})$WA$\supset$$(\mathrm{m})\mathrm{W}\mathrm{t}\mathrm{A}\supset \mathrm{r}(\mathrm{m})\mathrm{W}\mathrm{A})=(^{(\mathrm{m})}\mathrm{W}(\mathrm{k})-\langle \mathrm{m})\mathrm{w}\mathrm{A})\cup(\mathrm{m})ffl\mathrm{s}(\mathrm{m})$$=(^{\langle \mathrm{r}\mathrm{n})}\mathrm{W}(\mathrm{k})-(\mathrm{m})\mathrm{W}_{\mathrm{A}})\cup(\mathrm{m})\mathrm{w}_{\mathrm{A}}$A をとる。
WA$(\mathrm{d}\mathrm{e}\mathrm{f})$[註] の$(\mathrm{X}.\cdot)$$(\mathrm{m})\mathrm{W}^{(\mathrm{k})}$$=$$(\mathrm{m})\mathrm{w}_{(\mathrm{A}\supset}*(\mathrm{m})\mathrm{w}_{\mathrm{A}})\mathrm{n}(\mathrm{m})\mathrm{W}_{\mathrm{L}^{()\langle \mathrm{m})}}\mathrm{k}\mathrm{W}^{\langle \mathrm{k})}=\cap(\mathrm{m})\mathrm{w}_{\mathrm{L}^{()}}\mathrm{k}$$(\mathrm{m})\mathrm{w}$(A$\supset*(\mathrm{m})\mathrm{w}_{\mathrm{A}}$故に、 $[\#]$ より、(N2):$[\#]$(m))$\cdot \mathrm{L}=\mathrm{W}(\mathrm{m})\mathrm{L}(\mathrm{k})$$\mathrm{L}\vdash$の A としてA$\supset*(\mathrm{m})$$\mathrm{r}(\mathrm{m})\mathrm{W}(\mathrm{k})$WA. 同様に、$\mathrm{L}\vdash \mathrm{r}(.\mathrm{m})$

WA

をとる。

$\mathrm{w}_{\langle}*(\mathrm{m})(\mathrm{k}\text{》})\cdot \mathrm{L}=\mathrm{W}\mathrm{w}((\mathrm{m}\text{》}*(\mathrm{m})\mathrm{W}(\mathrm{k}))\cap\langle \mathrm{m})\mathrm{W}_{\mathrm{L}^{(}}\mathrm{k})$$=\mathrm{W}^{(}(\mathrm{m})\mathrm{k})\cap(\mathrm{m})\mathrm{w}_{\mathrm{L}^{(}}\mathrm{k})$$=\mathrm{W}_{\mathrm{L}}(\mathrm{m})(\mathrm{k})$従って、$[\#]$

より、$\mathrm{L}\vdash$$*(\mathrm{m})\mathrm{W}\mathrm{t}\mathrm{k})$も成立。

$(\mathrm{d}\mathrm{e}\mathrm{f})$[註] の$(\cross.\cdot)$$\supset$A .

$0\not\in\langle \mathrm{m})\mathrm{W}$