非古典論理(non-classical logic)とは、古典論理の法則の一部を落とす、語彙を足す、真理値の集合を取り替えるなどして得られる論理の総称である。直観主義論理、多値論理、矛盾許容論理、線形論理、様相論理などが含まれる。古典論理のどの法則が何に依存するか、法則を変えると何が証明でき、どんな意味論が得られるかが中心の問いになる。
非古典論理(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 値の論理の性質を完全に証明する。
$\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$ がその反例である。
シークエント計算 で書くと、論理の違いの多くは、結合子の規則ではなく構造規則の違いとして見える。弱化は $\Gamma\vdash\Delta$ から $\Gamma,A\vdash\Delta$ を導く規則、縮約は $\Gamma,A,A\vdash\Delta$ から $\Gamma,A\vdash\Delta$ を導く規則で、右辺についても同様の規則がある。
排中律の古典の導出では、$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)。このように、古典論理の法則は、結合子の意味だけでなく証明の中で論理式をどう扱うかにも依存している。
どの論理も、命題論理 と 古典論理、証明の形式の シークエント計算 や 自然演繹 を読んでから入るとよい。そこから動機ごとに道が分かれる。
| 動機 | 順に読む記事 | 着く先 |
|---|---|---|
| 構成と証明 | 直観主義論理、Heyting代数、Kripke意味論、構成的数学 | Martin-Löf型理論、ホモトピー型理論 |
| 証明の形と資源 | シークエント計算、カット除去定理、線形論理 | 分離論理 |
| 必然性と計算機科学 | 様相論理、Kripke意味論 | 型理論 |
| 表現力とモデル | 二階論理、無限論理、連続論理 | 数理論理学 |
| 圏と幾何 | Heyting代数、内部論理、二重否定位相 | 型理論 |
多値論理と様相論理、直観主義論理の教科書としての入口は OLT26 の Part X から Part XIII にある。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する