多値論理(many-valued logic)とは、真理値を真と偽の 2 つに限らず、3 つ以上の値を許して、結合子を値の上の関数として解釈する論理の総称である。値の集合、指定値、真理関数の組である行列で定まり、Łukasiewicz・Kleene・Gödel の 3 値論理や逆説の論理が代表例である。指定値の選び方で矛盾許容論理も得られ、値が有限個なら帰結はコンパクトである。
多値論理(many-valued logic)とは、真理値を真と偽の 2 つに限らず、3 つ以上の値を許して、結合子を値の上の関数として解釈する論理の総称である。古典論理 では論理式の値は結合子の真理値表で機械的に決まる。この「値が部分式の値だけで決まる」という形を保ったまま、値の集合だけを取り替えるのが多値論理である。
第 3 の値を入れる理由はいくつかあり、理由ごとに表が変わる。明日の出来事についての文はまだ真でも偽でもないと考えたのが Łukasiewicz で、計算が止まらないために値が定まらない文を考えたのが Kleene である。嘘つきのパラドックスの文を真でも偽でもあるとする立場もある(MP26 §1、§2.2)。同じ第 3 の値でも、$U\to U$ を真とするか不定とするか、$U$ を「成り立つ」側に入れるかどうかで、得られる論理はまったく違う。
この記事は、枠組みである行列と、値の数や表の選び方で何が決まるかを扱う。無限個の値をもつ代表である Łukasiewicz論理、直観主義論理に近い Gödel の鎖は 中間論理 に任せる。非古典論理 の全体の地図の中では、この記事は「真理値を増やすと何が変わるか」の項目にあたる。
この記事では次のことを示す。
命題論理の言語 $\mathcal L$ とは、項数の決まった結合子の集合である。$\mathcal L$ の 行列(matrix)とは、次の組 $\mathcal M=(V,V^+,(\tilde\star)_{\star\in\mathcal L})$ である。
定義は OLT26 Def. 45.5–45.10 による。古典論理は $V=\{T,F\}$、$V^+=\{T\}$ の行列である。
3 値の論理では $V=\{T,U,F\}$ とし、順序 $F< U< T$ を入れる。
次の 4 つでは $\land$ を小さい方、$\lor$ を大きい方とし、$\lnot T=F$、$\lnot F=T$ とする。含意は $F\to x=T$、$T\to x=x$、$x\to T=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$ |
弱 Kleene 論理 $\mathrm{Kw}$ は、$\{T,F\}$ の上では古典の表どおりで、$\lnot U=U$ とし、$\land,\lor,\to$ は引数に $U$ が 1 つでもあれば値を $U$ とする。指定値は $T$ だけである。
OLT26 Def. 46.1、46.3、46.4、46.6、46.7 による。$\mathrm{LP}$ と $\mathrm{Ks}$ は真理関数が同じで、指定値だけが違う。
第 3 の値の読み方は 2 通りに分かれる(MP26 §2.2)。
値がないという読みでは、$U$ は「まだ分からない」「定まらない」を表す。Kleene の強い表は、部分式の値がどう決まっても答えが同じならその答えを返す。これは計算の並列実行として読める。$\varphi\land\psi$ を 2 つ同時に計算し、片方が偽を返せば、もう片方が止まらなくても答えは偽である。弱い表は左から順に計算する場合に近く、片方が止まらなければ全体も止まらない(OLT26 §46.3)。
値が 2 つあるという読みでは、$U$ は「真でも偽でもある」を表す。すると $U$ の文も真の一種として認めてよいので、指定値に入れる。これが $\mathrm{LP}$ である。
Łukasiewicz の表は、未来についての文を動機にしながら、$p\to p$ を恒真式に保つために $U\to U=T$ と定めた(OLT26 §46.2)。この 1 箇所だけが「値が定まらない」という読みから外れている。
どの読みをとるにせよ、多値論理では結合子の意味が値の計算で決まる。値が有限個なら、法則が成り立つかどうかは有限の場合分けで判定できる。
5 つの論理で、次のように法則と推論の振る舞いが分かれる。$\vDash$ は帰結、$\vDash\varphi$ は恒真式を表す。
| 主張 | $\text{Ł}_3$ | $\mathrm{Ks}$ | $\mathrm{Kw}$ | $\mathrm{G}_3$ | $\mathrm{LP}$ |
|---|---|---|---|---|---|
| $\vDash p\to p$ | ○ | × | × | ○ | ○ |
| $\vDash p\lor\lnot p$ | × | × | × | × | ○ |
| $\vDash\lnot(p\land\lnot p)$ | × | × | × | ○ | ○ |
| $\vDash(p\land\lnot p)\to q$ | × | × | × | ○ | ○ |
| $p\vDash p\lor q$ | ○ | ○ | × | ○ | ○ |
| $p,\ p\to q\vDash q$ | ○ | ○ | ○ | ○ | × |
| $p,\ \lnot p\vDash q$ | ○ | ○ | ○ | ○ | × |
$\text{Ł}_3$ で $p,\lnot p\vDash q$ は成り立つ。$p$ と $\lnot p$ がともに $T$ になる付値がないからである。同様に $p\land\lnot p\vDash q$ も成り立つ。しかし $(p\land\lnot p)\to q$ は恒真式でない。$v(p)=U$、$v(q)=F$ のとき、値は $U\to F=U$ である。
$\mathrm{Kw}$ では $p\vDash p\lor q$ が成り立たない。$v(p)=T$、$v(q)=U$ で $v(p\lor q)=U$ となるからである。一方の計算が止まらなければ全体が止まらない、という読みのとおりに、$U$ が式全体へ伝わる。逆に、変数をすべて $T,F$ にすれば結果は古典の値に一致する。
$V=\{0,1,2\}$、$V^+=\{2\}$ とし、$x\lor y=\max\{x,y\}$、$\lnot x=x+1\pmod 3$ とする行列を $\mathrm{P}_3$ と書く。$\lnot^kp$ を否定を $k$ 回重ねた式とする。
$$
\varphi:=\lnot^3p\lor\lnot p\lor\lnot^5p
$$
の値は $p,\ p+1,\ p+2$ のうちの最大だから、つねに $2$ である。よって $\varphi$ は $\mathrm{P}_3$ の恒真式である。一方、古典論理では奇数回の否定はどれも $\lnot p$ と同じなので、$\varphi$ は $\lnot p$ と同値で、恒真式でない。
$\mathcal M$ の言語の結合子はどれも古典論理の結合子($\lnot,\land,\lor,\to$ など)とする。$T,F\in V$、$T\in V^+$、$F\notin V^+$ で、各結合子の真理関数を $\{T,F\}$ に制限すると古典の真理関数になるとする。このとき $\Gamma\vDash_{\mathcal M}\varphi$ なら、古典論理でも $\Gamma\vDash\varphi$ である。特に $\mathcal M$ の恒真式は古典の恒真式である。
対偶を示す。古典の付値 $v\colon$(命題変数)$\to\{T,F\}$ が $\Gamma$ のすべてを $T$ に、$\varphi$ を $F$ にするとする。$v$ は $\mathcal M$ の付値でもある。真理関数の仮定から、論理式の組み立てについての帰納法で、$\mathcal M$ での値と古典の値はすべての論理式で一致する。$T\in V^+$、$F\notin V^+$ なので、この付値は $\Gamma$ を充足し $\varphi$ を充足しない。$\square$
OLT26 Prop. 45.12、Cor. 45.13 と同じ内容である。この記事の 5 つの論理と、Łukasiewicz論理、中間論理 の Gödel の鎖はこの条件を満たす。
同じ言語の行列 $\mathcal M,\mathcal M'$ と全射 $h\colon V\to V'$ があり、各結合子の真理関数と交換し、さらに $x\in V^+\iff h(x)\in V'^+$ を満たすとする。このとき $\vDash_{\mathcal M}$ と $\vDash_{\mathcal M'}$ は一致する。
$\mathcal M$ の付値 $v$ について $h\circ v$ は $\mathcal M'$ の付値であり、帰納法で $(h\circ v)(\varphi)=h(v(\varphi))$ である。よって $v$ が $\varphi$ を充足することと $h\circ v$ が $\varphi$ を充足することは同値である。$h$ は全射なので、$\mathcal M'$ の付値 $w$ はすべて、各命題変数の値の逆像を 1 つ選ぶことで $w=h\circ v$ の形に書ける。したがって、付値が充足する論理式の集合として現れるものは 2 つの行列で同じであり、帰結の関係はこの集合の全体で決まる。$\square$
$\mathrm{G}_3$ の真理関数で $V^+=\{T,U\}$ とした行列を考える。$h(T)=h(U)=T$、$h(F)=F$ は古典の行列への全射である。$\lnot U=F$、$U\to F=F$、$T\to U=U$、$U\to U=T$ などから、$h$ は真理関数と交換し、$x\in V^+\iff h(x)=T$ である。prop-mvl-hom により、この行列は古典論理を定める(OLT26 Prop. 46.11)。3 つの値があっても、$U$ と $T$ を論理が区別できないのである。
同じ指定値を $\mathrm{LP}$ の表に使うと、$h$ は $\lnot$ と交換しない($h(\lnot U)=T\neq F=\lnot h(U)$)。$\mathrm{LP}$ が古典論理にならないのはこのためである。
$V=\{T,U,F\}$ に、$U\sqsubseteq T$、$U\sqsubseteq F$ と $x\sqsubseteq x$ だけからなる半順序を入れる。$x\sqsubseteq y$ は「$y$ は $x$ より情報が多い」と読む。
$x\in V$ の 完成 とは、$x\ne U$ なら $x$ 自身、$x=U$ なら $T,F$ の両方をいう。表を見ると、$\mathrm{Ks}$ の 2 項の結合子について次が成り立つ。$x,y$ の完成のすべての組で古典の $\star$ の値が同じ $c$ なら $\tilde\star_{\mathrm{Ks}}(x,y)=c$ であり、値が分かれるなら $\tilde\star_{\mathrm{Ks}}(x,y)=U$ である。$\lnot$ も同様である。
1 を示す。$x\sqsubseteq x'$、$y\sqsubseteq y'$ なら、$x',y'$ の完成は $x,y$ の完成でもある。したがって $\tilde\star_{\mathrm{Ks}}(x,y)=c\ne U$ なら $\tilde\star_{\mathrm{Ks}}(x',y')=c$ である。値が $U$ のときは不等式は自明である。
2 を示す。$(x',y')$ を $x,y$ の完成の組とすると $(x,y)\sqsubseteq(x',y')$ なので、$f(x,y)\sqsubseteq f(x',y')$ であり、右辺は古典の値である。完成の組で値が $c$ に揃うなら $f(x,y)\sqsubseteq c$ となり、これは主張である。値が $c\ne c'$ と分かれるなら $f(x,y)$ は $c$ と $c'$ の両方の下にあるので $U$ である。
3 は 1 と論理式の組み立てについての帰納法による。$\square$
$\mathrm{Kw}$ も単調だが、たとえば $F\land U$ の値が $U$ で、確定できる値を確定していない。$\text{Ł}_3$ の含意は単調でない。$U\to U=T$ だが $T\to F=F$ である。
強 Kleene の値が確定していれば、$U$ の変数をどう確定させても値は変わらない。逆は成り立たない。
$v(p)=U$ とすると $\mathrm{Ks}$ で $v(p\lor\lnot p)=U$ である。一方、$p$ を $T,F$ のどちらに確定させても $p\lor\lnot p$ は $T$ になる。prop-mvl-monotone の 2 が述べているのは結合子ごとの最大性で、論理式全体の最大性ではない。
単調性は、真理述語を不動点で定義する Kripke の理論で Kleene の表が使われる理由でもある(MP26 §2.2)。
帰結の関係が 矛盾許容(paraconsistent)であるとは、ある論理式 $\varphi,\psi$ について $\varphi,\lnot\varphi\vDash\psi$ が成り立たないことをいう。
$\mathrm{LP}$ は矛盾許容である。$v(p)=U$、$v(q)=F$ とすれば $p,\lnot p$ は指定値をとり $q$ はとらない(PTW26 §3.6)。同じ付値で $v(p\to q)=U$ も指定値なので、前件肯定も成り立たない。ほかにも矛盾許容論理にはさまざまな作り方があるが(PTW26 §3)、多値の行列による作り方はもっとも簡単である。
1 を示す。$\mathrm{LP}$ と $\mathrm{Ks}$ の値は同じで、$\lnot$ は $T$ と $F$ を入れ替え、$U$ を固定する。したがって、どの付値でも $v(\chi)\in\{T,U\}$ と $v(\lnot\chi)\ne T$ は同値である。よって $\varphi\vDash_{\mathrm{LP}}\psi$ は「$v(\lnot\varphi)\ne T$ ならば $v(\lnot\psi)\ne T$」とかけ、その対偶は「$v(\lnot\psi)=T$ ならば $v(\lnot\varphi)=T$」である。これが $\lnot\psi\vDash_{\mathrm{Ks}}\lnot\varphi$ である。
2 を示す。すべての命題変数の値を $U$ とする付値では、$\lnot U=U$ と、$\land,\lor,\to$ の $U$ どうしの値が $U$ であることから、すべての論理式の値が $U$ である。$U$ は $\mathrm{LP}$ の指定値である。同じ付値から、$\mathrm{Ks}$ のどの論理式も恒真式でない。
3 の前半は 非古典論理 の命題「逆説の論理の恒真式」である。$\square$
帰結の方向を反転すると 2 つの論理が移り合う。$\mathrm{Ks}$ が「前提が真なら結論も真」という真の値を保つ論理であるのに対し、$\mathrm{LP}$ は「前提が偽でないなら結論も偽でない」という偽でない値を保つ論理である。$\mathrm{LP}$ の恒真式は古典論理と同じだから、$\mathrm{LP}$ と古典論理の違いは法則ではなく推論にある。
行列が 関数完全 であるとは、すべての $k\ge1$ とすべての関数 $f\colon V^k\to V$ について、$p_1,\dots,p_k$ の論理式 $\varphi$ で、付値 $v$ ごとの値が $v(\varphi)=f(v(p_1),\dots,v(p_k))$ となるものがあることをいう。古典論理は関数完全である。$\text{Ł}_3$ の $\{T,F\}$ は結合子で閉じているので、すべての変数が $T$ のときに $U$ を返す論理式はなく、$\text{Ł}_3$ は関数完全でない。$\mathrm{Ks}$ も、すべての変数が $U$ なら値が $U$ なので関数完全でない。
一方、値の数によらず関数完全な行列がある。これは Post が 1921 年に示した(MP26 §3.3)。ex-mvl-post を $n$ 値へ広げる。
$n\ge2$ とし、$V=\{0,1,\dots,n-1\}$、$x\lor y=\max\{x,y\}$、$\lnot x=x+1\pmod n$ とする。この行列は関数完全である。
以下、論理式と関数を同一視する。$N:=n-1$ とする。
定数。$\bigvee_{i=0}^{N}\lnot^ip_1$ の値は $V$ のすべての元の最大で、つねに $N$ である。これに $\lnot$ を重ねると、すべての定数が得られる。
点の特性関数。$h(x):=\bigvee_{i=1}^{N}\lnot^ix$ は、$x$ 以外のすべての元の最大である。したがって $x\ne N$ なら $N$、$x=N$ なら $N-1$ である。$\delta(x):=\lnot h(x)$ は $x=N$ で $N$、それ以外で $0$ である。$J_a(x):=\delta(\lnot^{N-a}x)$ とおくと、$J_a(x)$ は $x=a$ で $N$、それ以外で $0$ である。
$\{0,N\}$ に値をもつ関数の演算。$u$ がこの形の関数なら $J_0(u)$ は補集合にあたる。$\lor$ は和集合にあたるので、$u\sqcap u':=J_0(J_0(u)\lor J_0(u'))$ は共通部分にあたる。
値の付け替え。$c\in\{1,\dots,N\}$ と $\{0,N\}$ に値をもつ $u$ について、$c*u:=\lnot(J_0(u)\lor(c-1))$ とおく。ここで $c-1$ は定数である。$u=N$ なら $J_0(u)=0$ で値は $\lnot(c-1)=c$、$u=0$ なら $J_0(u)=N$ で値は $\lnot N=0$ である。
まとめ。$f\colon V^k\to V$ が恒等的に $0$ なら定数である。そうでなければ $$ f=\bigvee_{a\in V^k,\ f(a)\ne0}f(a)*\bigl(J_{a_1}(p_1)\sqcap\dots\sqcap J_{a_k}(p_k)\bigr) $$ である。実際、右辺の各項は点 $a$ で $f(a)$、ほかの点で $0$ である。$\square$
証明は「点の特性関数を作り、最大をとる」という形で、古典論理の選言標準形と同じである。巡回する否定があるから、$\{0,N\}$ の外の値へも移れる。
$V$ が有限のとき、次が成り立つ。
$V$ に離散位相を入れ、付値の全体 $X=V^{\text{(命題変数)}}$ に直積位相を入れる。Tychonoffの定理 により $X$ はコンパクトである。各論理式の値は有限個の命題変数の値だけで決まるので、$S(\psi):=\{v\in X: v(\psi)\in V^+\}$ は開かつ閉である。
1 は、閉集合の族 $S(\psi)$($\psi\in\Gamma$)が有限交叉性をもつなら全体の交わりが空でない、というコンパクト性そのものである。
2 は、$\Gamma_0\vDash_{\mathcal M}\varphi$ となる有限の $\Gamma_0$ がないとすると、閉集合の族 $S(\psi)$($\psi\in\Gamma$)と $X\setminus S(\varphi)$ が有限交叉性をもつので、$\Gamma$ を充足し $\varphi$ を充足しない付値が存在することから従う。
3 は、現れる命題変数は有限個で、その付値は有限個だからである。$\square$
$V$ が無限なら 2 は成り立つとは限らない。単位区間を値とする Łukasiewicz論理 では、有限部分集合からは帰結しないのに全体からは帰結する例がある(同記事の命題「帰結のコンパクト性が成り立たないこと」)。
$\mathcal L$ の論理式の集合 $S$ について、次は同値である。
1 ⇒ 2。付値 $v$ と代入 $\sigma$ について $v\circ\sigma$ も(命題変数に制限して)付値で、$v(\sigma(\varphi))=(v\circ\sigma)(\varphi)$ である。よって恒真式の代入例は恒真式である。
2 ⇒ 1。$\mathcal L$ の論理式の全体を $V$ とし、$V^+=S$、$\tilde\star(\varphi_1,\dots,\varphi_n)=\star(\varphi_1,\dots,\varphi_n)$ とする。この行列の付値は、命題変数に論理式を割り当てる写像、すなわち代入 $\sigma$ であり、$v(\varphi)=\sigma(\varphi)$ である。$\varphi\in S$ なら代入で閉じていることから恒真式である。逆に $\varphi$ が恒真式なら、恒等の代入について $\varphi\in S$ である。$\square$
この行列は Lindenbaum の名で呼ばれ、論理をその論理式自身で解釈するものである(Jan22 §6)。帰結の関係まで含めても、どの論理にも行列の族による意味論がある(Jan22 §6)。したがって、行列で書けることに内容があるのは、値が有限の場合と、具体的な代数で書ける場合である。
値が有限個の行列で書けない論理もある。直観主義命題論理がその例で、Gödel が 1932 年に示した(MP26 §4.2)。証明は 中間論理 の定理「有限の行列で書けないこと」にある。様相論理にも同じ現象がある(MP26 §4.2)。
行列の付値 $v$ に対し、$b_v(\varphi):=T$($v(\varphi)\in V^+$ のとき)、$b_v(\varphi):=F$(それ以外)とおくと、論理式全体から $\{T,F\}$ への写像の族が得られ、$\vDash_{\mathcal M}$ はこの族が定める 2 値の帰結と一致する。ただし $b_v$ は真理関数的でない。多値論理の本質は、値の個数よりも、値が部分式の値から計算できることにある(MP26 §4.3)。これは Suszko の名で知られる見方である。
$V=[0,1]$、$V^+=\{1\}$ とする論理は、ファジィ論理の基本の形である(CFN21 §1)。$[0,1]$ 上の可換で結合的、単調で $1$ を単位元とする演算を t ノルム という。左連続な t ノルム $*$ には $x\Rightarrow y:=\max\{z:x*z\le y\}$ が定まり、これを含意とする。$x*y=\max\{x+y-1,0\}$ から Łukasiewicz論理、$x*y=\min\{x,y\}$ から Gödel の論理、積 $x*y=xy$ から積論理が得られる。連続な t ノルムはこの 3 つの順序和として書ける(CFN21 §1。この記事では証明しない)。
| 外す条件 | 例 | 成り立たなくなる主張 |
|---|---|---|
| 結合子が $\{T,F\}$ で閉じる | $\mathrm{P}_3$(ex-mvl-post) | 恒真式は古典の恒真式 |
| $F$ は指定値でない | $\mathrm{Ks}$ の真理関数で $V^+=V$ | 恒真式は古典の恒真式($p\land\lnot p$ も恒真式になる) |
| 指定値は $T$ だけ | $\mathrm{LP}$ | 爆発律 $p,\lnot p\vDash q$ と前件肯定 |
| 真理関数の単調性 | $\text{Ł}_3$ の含意 | 情報を増やしても確定した値は変わらない($U\to U=T$ が $T\to F=F$ に変わる) |
| 値の有限性 | 単位区間の Łukasiewicz論理 | 帰結のコンパクト性 |
| 代入で閉じること | $S=\{p_0\}$ | $S$ が恒真式の全体になること($p_0$ が恒真式なら $p_1$ も恒真式) |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する