非古典論理

同義語:non-classical logicnonclassical logic

概要

非古典論理(non-classical logic)とは、古典論理の法則の一部を落とす、語彙を足す、真理値の集合を取り替えるなどして得られる論理の総称である。直観主義論理、多値論理、矛盾許容論理、線形論理、様相論理などが含まれる。古典論理のどの法則が何に依存するか、法則を変えると何が証明でき、どんな意味論が得られるかが中心の問いになる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 命題論理, 古典論理, 一階述語論理

非古典論理(non-classical logic)とは、古典論理 の法則の一部を落とす、語彙を足す、真理値の集合を取り替えるなどして得られる論理の総称である。中心の問いは、古典論理のどの法則が何に依存しているのか、法則を変えると何が証明でき、どんな意味論と計算の解釈が得られるのか、の 2 つである。
古典論理は 2 つの真理値と、排中律、矛盾からの爆発、仮定の自由な複製と破棄を前提にしている。これらの前提は、それぞれ別の理由で外せる。証明を構成と読むなら排中律は疑わしくなり、仮定を資源と読むなら複製は無料でなくなり、矛盾した情報を扱うなら爆発は避けたくなる。一方で、語彙を足して必然性や高階の量化を語る方向もある。この記事は、これらの論理の違いを 1 つの地図に置く入口である。

定義

非古典論理は、ある 1 つの体系の名前ではない。この記事では次の 3 つに分けて整理する。

型古典論理との関係例
代替同じ語彙で、成り立つ法則を変える直観主義論理、多値論理、矛盾許容論理、線形論理
拡張語彙を足し、古典の法則は保つ様相論理、二階論理、無限論理
値の取り替え真理値を距離などの値に替える連続論理、Heyting代数 の値の意味論

線形論理 は語彙も足すが、古典の構造規則を制限するので代替の型に入れる。この分類は整理のためのもので、厳密な定義ではない。
多値論理の枠組みをここで定義する。詳しい性質は 多値論理 にある。

真理値の行列

命題論理の言語の行列とは、空でない真理値の集合 $V$、指定値の集合 $V^+\subset V$、各 $n$ 項結合子 $\star$ の真理関数 $\tilde\star\colon V^n\to V$ の組である。原子命題への値の割り当ては、真理関数によって論理式全体の付値 $v$ に一意に延びる(OLT26 Def. 45.5)。
$\varphi$ がすべての付値で $V^+$ の値をとるとき、$\varphi$ は恒真式であるという。論理式の集合 $\Gamma$ について、$\Gamma$ のすべてが $V^+$ の値をとる付値で $\varphi$ も $V^+$ の値をとるとき、$\Gamma\vDash\varphi$ と書く。

古典論理は $V=\{T,F\}$、$V^+=\{T\}$ の行列である。3 値の論理では $V=\{T,U,F\}$ とする。次の 4 つの論理は、$\land$ を小さい方、$\lor$ を大きい方(順序 $F< U< T$)とし、否定と含意と指定値だけが違う。

論理$\lnot U$$U\to U$$U\to F$指定値
Łukasiewicz の 3 値論理 $\text{Ł}_3$$U$$T$$U$$T$
強 Kleene 論理 $\mathrm{Ks}$$U$$U$$U$$T$
Gödel の 3 値論理 $\mathrm{G}_3$$F$$T$$F$$T$
逆説の論理 $\mathrm{LP}$$U$$U$$U$$T,U$

他の値の組では、$\lnot T=F$、$\lnot F=T$、$F\to x=T$、$T\to x=x$ で、どの論理でも共通である。$x\to T=T$ も共通である。$\mathrm{LP}$ の真理関数は $\mathrm{Ks}$ と同じで、指定値だけが違う(OLT26 Def. 46.1, 46.3, 46.6, 46.7)。

主な問題と結果の一覧

問い代表的な結果入る先
排中律なしで何が残るか直観主義命題論理は Heyting 代数と Kripke モデルについて健全で完全である直観主義論理、Heyting代数、Kripke意味論
古典論理と直観主義はどう結ぶか命題論理の論理式 $\varphi$ について、$\varphi$ が古典論理で証明できることと $\lnot\lnot\varphi$ が直観主義論理で証明できることは同値であるGlivenkoの定理、黒田の二重否定翻訳
直観主義は様相の言葉で読めるか翻訳 $T$ によって $\vdash_{\mathrm I}\varphi\iff\mathbf{S4}\vdash T(\varphi)$ が成り立つKripke意味論
直観主義と古典の間に論理はあるか$\mathrm{G}_3$ の恒真式は直観主義の定理をすべて含み、$(p\to q)\lor(q\to p)$ も含む中間論理、OLT26 p. 682
真理値を増やすと何が変わるか3 値の論理で法則が個別に成り立たなくなる。値を $[0,1]$ に広げた Łukasiewicz の論理や Gödel の論理もあるex-ncl-table、多値論理、Łukasiewicz論理、OLT26 Ch. 46–47
矛盾から何でも出ないようにできるか$\mathrm{LP}$ では爆発律が成り立たないex-ncl-lp
必然性を語彙にできるか正規様相論理は Kripke フレームの性質と対応し、標準モデルで完全性が示せる様相論理
仮定を資源と見ると何が起こるか$\mathbf{MALL}$ はカット除去をもち、$p\multimap p\otimes p$ は導出できない。線形論理全体は決定不能である線形論理、Gir87
プログラムの状態を論理で語れるか分離の結合子により frame 規則が健全になる分離論理
真理値を距離に替えられるか距離構造の連続論理で超積とコンパクト性定理が成り立つ連続論理
無限の連言を許すと何を失うかコンパクト性と上向きの Löwenheim–Skolem の定理が成り立たない無限論理
量化の範囲を述語に広げると何を失うか標準意味論で自然数が範疇的に特徴づけられ、完全な証明体系は失われる二階論理
トポスの中の論理は何か前層のトポスの内部論理は一般に直観主義的で、Boolean になる条件が分かっている内部論理
証明と計算は対応するか直観主義の証明は型のついた項と対応する型理論、Martin-Löf型理論

具体例

最初の例は、どの法則がどの論理で成り立たなくなるかを表で比べる。

法則の比較

3 値の行列で、法則が成り立つかどうかを計算すると次のようになる。$\mathrm{C}$ は古典論理、$\mathrm{I}$ は直観主義命題論理である。

法則$\mathrm{C}$$\mathrm{I}$$\text{Ł}_3$$\mathrm{Ks}$$\mathrm{G}_3$$\mathrm{LP}$
$p\to p$○○○×○○
$p\lor\lnot p$○××××○
$\lnot\lnot p\to p$○×○××○
$(p\to q)\lor(q\to p)$○×○×○○
$p,\lnot p\vDash q$○○○○○×
$p,p\to q\vDash q$○○○○○×

計算の例を 2 つ挙げる。$v(p)=U$ のとき、$\text{Ł}_3$ で $\lnot p$ は $U$ だから $p\lor\lnot p$ は $U$ で、指定値でない。$\lnot\lnot p\to p$ は $U\to U=T$ となる。$\mathrm{G}_3$ では $\lnot U=F$、$\lnot F=T$ だから $\lnot\lnot p\to p$ は $T\to U=U$ で、指定値でない。
$\mathrm{I}$ の列の × は、Kripke意味論 の反例モデルで確かめられる。$p\lor\lnot p$ と $\lnot\lnot p\to p$ は 2 点の鎖で、上の点だけで $p$ を真とするモデルで偽になる。$(p\to q)\lor(q\to p)$ は、根の上に 2 点が分かれ、一方で $p$ だけ、他方で $q$ だけを真とするモデルで偽になる。

表から分かるように、「排中律が成り立たない」と「二重否定の除去が成り立たない」は別の現象である。$\text{Ł}_3$ は前者だけを成り立たなくする。また $(p\to q)\lor(q\to p)$ は、$\mathrm{G}_3$ が直観主義論理より真に強いことを示す。
次の 2 つの命題は、3 値の論理の性質を完全に証明する。

強 Kleene 論理の恒真式

$\mathrm{Ks}$ に恒真式はない。

すべての原子命題に $U$ を割り当てる付値を考える。$\lnot U=U$、$U\land U=U$、$U\lor U=U$、$U\to U=U$ だから、論理式の構成についての帰納法で、すべての論理式の値が $U$ である。$U$ は指定値でないので、どの論理式もこの付値で指定値をとらない。

逆説の論理の恒真式

$\mathrm{LP}$ の恒真式は、古典論理の恒真式と一致する。

$\{T,F\}$ の値だけをとる付値では、$\mathrm{LP}$ の真理関数は古典の真理関数と一致する。したがって $\mathrm{LP}$ の恒真式は古典論理の恒真式である。
逆を示す。$\varphi$ が $\mathrm{LP}$ の恒真式でないとすると、$v(\varphi)=F$ となる付値 $v$ がある。$v(p)=U$ である原子命題の値を $T$ に替え、他はそのままとして付値 $v'$ を作る。論理式 $\psi$ についての帰納法で、$v(\psi)\ne U$ なら $v'(\psi)=v(\psi)$ であることを示す。
原子命題では定義から成り立つ。$\lnot\psi$ については、$v(\lnot\psi)\ne U$ なら $v(\psi)\ne U$ だから成り立つ。$\psi\land\chi$ については、値が $T$ なら両方が $T$ で、値が $F$ なら一方が $F$ である。どちらの場合も、帰納法の仮定で $v'$ の値が同じになる。$\lor$ も同様である。$\psi\to\chi$ については、$\mathrm{Ks}$ の真理関数が $\lnot\psi\lor\chi$ の値と一致するので、前の場合に帰着する。
よって $v'(\varphi)=F$ で、$v'$ は古典の付値だから、$\varphi$ は古典論理の恒真式でない。

$\mathrm{LP}$ は恒真式を変えないが、推論を変える。

反例:爆発律と前件肯定

「$p$ と $\lnot p$ から任意の $q$ が従う」という含意は $\mathrm{LP}$ で成り立たない。$v(p)=U$、$v(q)=F$ がその反例である。

  • 満たすこと:$v(p)=U$ と $v(\lnot p)=U$ はともに指定値である。
  • 満たさないこと:$v(q)=F$ は指定値でない。
  • 成り立たない含意:$p,\lnot p\vDash q$ が成り立たない。同じ付値で $v(p\to q)=U$ も指定値だから、$p,p\to q\vDash q$ も成り立たない。
    恒真式が同じでも帰結の関係が違うことが、この例の要点である。古典論理では $p\to q$ が恒真式であることと $p\vDash q$ が同値だが、$\mathrm{LP}$ ではこの同値は成り立たない。$p\to(\lnot p\to q)$ は恒真式だが、$p,\lnot p\vDash q$ は成り立たない。

構造規則から見る

シークエント計算 で書くと、論理の違いの多くは、結合子の規則ではなく構造規則の違いとして見える。弱化は $\Gamma\vdash\Delta$ から $\Gamma,A\vdash\Delta$ を導く規則、縮約は $\Gamma,A,A\vdash\Delta$ から $\Gamma,A\vdash\Delta$ を導く規則で、右辺についても同様の規則がある。

制限得られる論理失う例
右辺を高々 1 個の論理式に制限する直観主義論理$p\lor\lnot p$
弱化と縮約を落とす線形論理$p\multimap p\otimes p$

排中律の古典の導出では、$p\vdash p$ から $\vdash\lnot p,p$ を作り、右辺の 2 つの論理式をそれぞれ $p\lor\lnot p$ に変えて、右の縮約で 1 つにまとめる。右辺を 1 個に制限すると、最初の $\vdash\lnot p,p$ が作れない(Bus98 §3.1)。
線形論理では、仮定を 1 回ずつ使うことになるので、$p$ から $p\otimes p$ は出ない。複製と破棄は指数という結合子のついた論理式にだけ許される(Gir87、Bus98 §3.2)。このように、古典論理の法則は、結合子の意味だけでなく証明の中で論理式をどう扱うかにも依存している。

読み進め方

どの論理も、命題論理 と 古典論理、証明の形式の シークエント計算 や 自然演繹 を読んでから入るとよい。そこから動機ごとに道が分かれる。

多値論理と様相論理、直観主義論理の教科書としての入口は OLT26 の Part X から Part XIII にある。

関連項目

参考文献

[2]
Jean-Yves Girard, Linear logic, Theoretical Computer Science, 1987
[3]
Samuel R. Buss, An Introduction to Proof Theory, Handbook of Proof Theory, 1998, §3.1(Intuitionistic logic), §3.2(Linear logic)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する