Łukasiewicz論理(Łukasiewicz logic)とは、真理値を $0$ から $1$ までの数とし、否定を $1-x$、含意を $\min\{1,1-x+y\}$ で解釈する多値論理である。値を等間隔の $n$ 点にとれば $n$ 値の論理、単位区間にとれば無限値の論理になる。論理式の定める関数は連続で区分的に整数係数の 1 次式である。排中律と縮約が成り立たず、無限値では帰結がコンパクトでない。
Łukasiewicz論理(Łukasiewicz logic)とは、真理値を $0$ から $1$ までの数とし、否定を $1-x$、含意を $\min\{1,1-x+y\}$ で解釈する 多値論理 である。$x\to y$ の値は、$x$ が $y$ を上回る分だけ $1$ から減る。値の集合を $n$ 個の等間隔の点にとれば $n$ 値の論理 $\text{Ł}_n$、単位区間全体にとれば無限値の論理 $\text{Ł}_\infty$ が得られる。
Łukasiewicz は未来についての文の値として第 3 の値を導入し、3 値の論理を作った。その表は上の式の $x,y\in\{0,\tfrac12,1\}$ の場合である(OLT26 §46.2、Prop. 47.2)。無限値の論理は Łukasiewicz と Tarski が 1930 年に調べた(CFN21 §3)。
無限値の論理の特徴は、真理関数がすべて連続で、しかも整数係数の区分的 1 次式になることである。古典論理の真理値表が Boole 代数の話なら、ここでは「整数の傾きをもつ折れ線」の話になる。一方で、同じ仮定を 2 回使うことに制限があり、排中律が成り立たない。有限の証明では捉えられない帰結も現れる。
この記事では次のことを示す。
言語は $\lnot$ と $\to$ とする。残りの結合子は後で定める。
$x,y\in[0,1]$ について
$$
\lnot x:=1-x,\qquad x\to y:=\min\{1,\ 1-x+y\}
$$
とする。指定値は $1$ だけとする。
$V_n$ は $\lnot,\to$ で閉じているので、行列として意味をもつ。$\text{Ł}_2$ は古典論理である。文献によっては値の集合を有理数 $[0,1]\cap\mathbb{Q}$ とするが(OLT26 Def. 47.1)、恒真式は同じである(prop-lk-rational)。
$$
\varphi\lor\psi:=(\varphi\to\psi)\to\psi,\quad
\varphi\land\psi:=\lnot(\lnot\varphi\lor\lnot\psi),\quad
\varphi\oplus\psi:=\lnot\varphi\to\psi,\quad
\varphi\odot\psi:=\lnot(\varphi\to\lnot\psi)
$$
とする。$\varphi^{k}$ は $\varphi$ の $k$ 個の $\odot$、$k\cdot\varphi$ は $\varphi$ の $k$ 個の $\oplus$ とする。
$1-(x\to y)$ は $x$ が $y$ を上回る量 $\max\{x-y,0\}$ である。そこで $1-x$ を「$x$ の不足」と読むと、$x\to y$ の不足は「$y$ の不足のうち $x$ の不足で説明できない分」になる。$p$ と $p\to q$ から $q$ を導くと、不足は足し算で増える。不足が $\tfrac14$ の前提 2 つから導いた結論の不足は $\tfrac12$ まで増えうる。
この読みでは、同じ前提を何度も使うことに費用がかかる。Sorites のパラドックスが典型である。ほぼ確実な小さな一歩を繰り返すと、確実さが少しずつ失われて、やがて $0$ まで落ちる。$\odot$ は「両方を使う」ことを表す連言で、$\land$ は「どちらか一方を選んで使う」ことを表す。2 つの連言の区別は 線形論理 の乗法と加法の区別と同じ形である。
$p=\tfrac12$ のように値を入れると、法則の成否が計算できる。$\text{Ł}_n$ の列で ○ は恒真式を表す。
| 法則 | 古典 | $\text{Ł}_3$ | $\text{Ł}_4$ | $\text{Ł}_\infty$ |
|---|---|---|---|---|
| $p\lor\lnot p$ | ○ | × | × | × |
| $\lnot(p\land\lnot p)$ | ○ | × | × | × |
| $\lnot\lnot p\to p$ | ○ | ○ | ○ | ○ |
| $(p\to q)\lor(q\to p)$ | ○ | ○ | ○ | ○ |
| $p\to(q\to p)$ | ○ | ○ | ○ | ○ |
| $\lnot(p\land q)\to(\lnot p\lor\lnot q)$ | ○ | ○ | ○ | ○ |
| $(p\to(p\to q))\to(p\to q)$ | ○ | × | × | × |
| $p\to p\odot p$ | ○ | × | × | × |
| $p^2\to p^3$ | ○ | ○ | × | × |
| $((p\to q)\to p)\to p$ | ○ | × | × | × |
排中律は値 $\max\{x,1-x\}$ をとるので、$x\ne0,1$ で $1$ にならない。二重否定の除去が成り立つことと、$(p\to q)\lor(q\to p)$ が成り立つことは、それぞれ $1-(1-x)=x$ と $x,y$ の大小の比較から分かる。直観主義論理 ではこの 2 つがともに証明できず、逆に 直観主義論理 で証明できる $(p\to(p\to q))\to(p\to q)$ がここでは成り立たない。したがって 2 つの論理に包含の関係はない。
$v(p)=\tfrac12$、$v(q)=0$ とする。$p\to q$ の値は $\tfrac12$、$p\to(p\to q)$ の値は $\tfrac12\to\tfrac12=1$ である。よって $(p\to(p\to q))\to(p\to q)$ の値は $\tfrac12$ である。
$v(p)=x$ とすると $p^{k}$ の値は $\max\{0,kx-(k-1)\}$ である。$V_3$ では $x<1$ なら $x\le\tfrac12$ で $p^2$ の値は $0$ だから、$p^2\to p^3$ は $\text{Ł}_3$ の恒真式である。$V_4$ では $x=\tfrac23$ で $p^2$ の値は $\tfrac13$、$p^3$ の値は $0$ だから、値は $\tfrac23$ である。成り立つかどうかを分けるのは値の間隔で、間隔が細かいほど同じ前提を使える回数が増える。
1 変数の論理式が定める関数 $f\colon[0,1]\to[0,1]$ は連続なので(prop-lk-pl)、$f(x)-x$ に 中間値の定理 を使うと $f(x)=x$ となる $x$ がある。したがって、$L$ が $\varphi(L)$ と同じ値をとるという形の自己言及には矛盾なく値を割り当てられる。嘘つきの文 $f(x)=1-x$ の値は $\tfrac12$ である。
中間論理 の Gödel の論理では否定が $\{0,1\}$ に値をとるので、$\lnot x=x$ の解はない。真理関数の連続性がこの差を生む。
$x,y,z\in[0,1]$ について次が成り立つ。
4 は定義から直ちに従う。
1 を示す。$x\le y$ なら $x\to y=1$ で、$1\to y=y$ である。$x>y$ なら $x\to y=1-x+y$ で、$(1-x+y)\to y=\min\{1,x\}=x$ である。よって $(x\to y)\to y=\max\{x,y\}$ で、$\land$ は $1-\max\{1-x,1-y\}=\min\{x,y\}$ である。
2 を示す。$(1-x)\to y=\min\{1,x+y\}$ である。$x\to(1-y)=\min\{1,2-x-y\}$ の $1$ からの差が $\max\{0,x+y-1\}$ である。
3 を示す。$z=1$ なら両辺はともに成り立つ。$z<1$ のとき、右辺の $y\to z$ が $1$ なら $y\le z$ なので $x+y-1\le z$ であり、両辺が成り立つ。$y\to z=1-y+z<1$ なら、右辺は $x\le1-y+z$、すなわち $x+y-1\le z$ で、$z\ge0$ と合わせて左辺と同値である。$\square$
3 は $\odot$ と $\to$ が 1 組の随伴であることを述べている。古典論理や Heyting代数 では同じ役割を $\land$ が担う。$\odot\ne\land$ であることが、縮約が成り立たない原因である。
次の公理図式と前件肯定を公理系とする(CFN21 §3)。
この公理系で証明できる論理式は $\text{Ł}_\infty$ の恒真式である。
公理の値がつねに $1$ であることと、前件肯定が値 $1$ を保つことを示す。$\varphi,\psi,\chi$ の値を $x,y,z$ とする。prop-lk-residuation の 4 を使う。
(A1) は $x\le y\to x$ で、$1-y+x\ge x$ から従う。
(A2) は残余を 2 回使うと $(x\to y)\odot(y\to z)\odot x\le z$ と同値である。$\odot$ は可換、結合的、単調で、prop-lk-residuation の 3 から $x\odot(x\to y)\le y$、$y\odot(y\to z)\le z$ である。これらをつなげばよい。
(A3) は $\max\{x,y\}\to\max\{y,x\}=1$ である。
(A4) は $(1-y)\to(1-x)=\min\{1,1+y-x\}=x\to y$ からいえる。
(A5) は場合分けによる。$x\le y$ なら $x\to y=1$ だから、前件の値は $1\to(y\to x)=y\to x$ で、全体の値は $1$ である。$x>y$ なら $y\to x=1$ なので全体の値は $1$ である。
前件肯定については、$x=1$ かつ $x\to y=1$ なら $y=1$ である。$\square$
$\Gamma$ が論理式の有限集合のとき、$\Gamma$ からこの公理系で $\varphi$ が証明できることと、$\Gamma$ の値をすべて $1$ にする $[0,1]$ の付値がつねに $\varphi$ の値も $1$ にすることは同値である。
論理式 $\varphi$ の命題変数が $p_1,\dots,p_k$ のとき、$x\in[0,1]^k$ を $p_i$ の値とする付値での $\varphi$ の値を $f_\varphi(x)$ と書く。
$f_\varphi\colon[0,1]^k\to[0,1]$ は連続である。さらに、整数係数の 1 次式(定数項も整数)$g_1,\dots,g_r$ があって、各点 $x$ で $f_\varphi(x)$ はどれかの $g_j(x)$ に等しい。
$\varphi$ の組み立てについての帰納法による。変数は座標関数である。$f_{\lnot\varphi}=1-f_\varphi$ で、$f_\varphi$ の各式 $g_j$ を $1-g_j$ に替えればよい。$f_{\varphi\to\psi}=\min\{1,1-f_\varphi+f_\psi\}$ は連続で、各点の値は $1$ か、$1-g_i+h_j$($g_i,h_j$ は $f_\varphi,f_\psi$ の式)のどれかである。$\square$
この性質は多くのことを禁じる。
$f\colon[0,1]^k\to[0,1]$ が連続で、整数係数の 1 次式 $g_1,\dots,g_r$ があって各点の値がどれかの $g_j$ の値に等しいとする。このとき $f=f_\varphi$ となる論理式 $\varphi$ がある。
論理式 $\varphi$ について次は同値である。
$V_n\subset[0,1]\cap\mathbb{Q}\subset[0,1]$ はどれも $\lnot,\to$ で閉じているので、1 ⇒ 2 ⇒ 3 である。
3 ⇒ 1 の対偶を示す。$f_\varphi(a)<1$ となる $a\in[0,1]^k$ があるとする。$f_\varphi$ は連続なので、$a$ の近くの有理点 $b\in[0,1]^k$ でも $f_\varphi(b)<1$ である。$b$ の座標の共通の分母を $d$ とすると $b\in V_{d+1}^k$ なので、$\varphi$ は $\text{Ł}_{d+1}$ の恒真式でない。$\square$
恒真式が同じでも、prop-lk-sat の後で見るように、値の集合を有理数に替えると別のところで違いが出る。
$\text{Ł}_\infty$ の恒真式の全体は決定可能である。thm-lk-complete により恒真式は機械的に列挙でき、prop-lk-rational により恒真式でない式は有限の $\text{Ł}_n$ の反例で列挙できるからである。計算量は古典論理と同じ coNP 完全であることが知られている(MP26 §2.4。この記事では証明しない)。
$m,n\ge2$ について、$\text{Ł}_m$ の恒真式がすべて $\text{Ł}_n$ の恒真式であることと、$n-1$ が $m-1$ を割り切ることは同値である。
$n-1$ が $m-1$ を割り切るなら $V_n\subset V_m$ で、$V_n$ は結合子で閉じているので、$V_m$ で値 $1$ をとる式は $V_n$ でも値 $1$ をとる。
割り切らないとする。このとき $\tfrac1{n-1}\notin V_m$ である。$N:=m-1$ として
$$
f(x):=\max_{0\le i\le N}\ \max\{0,\ 1-|Nx-i|\}
$$
とおく。$f$ は連続で、各点の値は $0$ か $1\pm(Nx-i)$ であり、$f(x)=1\iff x\in V_m$ である。thm-lk-mcnaughton により $f=f_\varphi$ となる論理式 $\varphi$ がある。$\varphi$ は $\text{Ł}_m$ の恒真式だが、$v(p)=\tfrac1{n-1}\in V_n$ の値は $1$ でない。$\square$
特に $\text{Ł}_3$ と $\text{Ł}_4$ の恒真式には包含がない($2$ と $3$ はどちらも他方を割り切らない)。値の個数が増えると論理が弱くなる、という単純な形ではない。包含の主張は MP26 §3.3 にある。中間論理 の Gödel の鎖では、値の個数に沿って論理が 1 列に並ぶのと対照的である。
多値論理 の例「反例:演繹定理が成り立たないこと」のとおり、$\text{Ł}_3$ で古典の演繹定理は成り立たない。$n\ge3$ の $\text{Ł}_n$ でも、$v(p)=\tfrac1{n-1}$、$v(q)=0$ で同じ計算になる。しかし $\text{Ł}_n$ では冪を使って修正できる。
1 は prop-lk-residuation の 2 と $k$ についての帰納法による。
2 を示す。$x<1$ なら $x\le1-\tfrac1{n-1}$ なので $(n-1)x-(n-2)\le0$ である。
3 を示す。2 より、付値 $v$ について、$v(\varphi)=1$ なら $v(\varphi^{n-1}\to\psi)=v(\psi)$、$v(\varphi)\ne1$ なら $v(\varphi^{n-1}\to\psi)=0\to v(\psi)=1$ である。よって $\Gamma$ を充足する付値について、「$\varphi$ を充足するなら $\psi$ を充足する」と「$\varphi^{n-1}\to\psi$ を充足する」は同値である。
4 を示す。$v(p)=1$ なら $v(p^{k})=1$ なので前半が成り立つ。$e:=\tfrac1{2k+2}$、$x=1-e$ とすると、1 により $x^k=1-ke$、$x^{k+1}=1-(k+1)e=\tfrac12$ である。よって $x^{k}\to x^{k+1}=1-e<1$ である。$\square$
2 は、$\text{Ł}_n$ では「$p$ の値がちょうど $1$ である」という判定を論理式で書けることを意味する。$\text{Ł}_\infty$ ではこれが連続性によって不可能で、それが 4 の一様性が成り立たない理由である。
論理式の集合 $\Gamma$ について、$\Gamma$ のすべての有限部分集合が $[0,1]$ の付値で充足可能なら、$\Gamma$ も充足可能である。
付値の全体 $[0,1]^{\text{(命題変数)}}$ は Tychonoffの定理 によりコンパクトである。各論理式の値は有限個の座標の連続関数なので、$\{v:v(\psi)=1\}$ は閉集合である。仮定はこの閉集合の族の有限交叉性だから、全体の交わりは空でない。$\square$
無限個の値でも、値が $1$ であるという条件が閉集合を定めるので、コンパクト性が残る。有理数の値ではこの証明が使えず、結論も成り立たない。
$\varphi\leftrightarrow\psi:=(\varphi\to\psi)\land(\psi\to\varphi)$ の値が $1$ であることは、両辺の値が等しいことを意味する。$d\ge2$ について、変数 $r_d$ の論理式 $\lnot r_d\leftrightarrow(d-1)\cdot r_d$ の値が $1$ なら $r_d=\tfrac1d$ である。$1-y=\min\{1,(d-1)y\}$ の解は $y=\tfrac1d$ だけだからである。
無理数 $\alpha\in(0,1)$ を固定する。これらの論理式と、$1\le j\le d$ で $\tfrac jd<\alpha$ なら $j\cdot r_d\to p$、$\tfrac jd>\alpha$ なら $p\to j\cdot r_d$ をすべて集めた集合を $\Gamma$ とする。$\Gamma$ を充足する実数値の付値は $p$ に $\alpha$ を割り当てる。
帰結の方は、$[0,1]$ でもコンパクトでない。多値論理 の定理「有限値の論理のコンパクト性」の 2 にあたる主張が成り立たない。
$\Gamma:=\{\,(n\cdot p)\to q:n\ge1\,\}$ とする。$[0,1]$ の付値について、$\Gamma\vDash\lnot p\lor q$ であるが、どの有限部分集合 $\Gamma_0\subset\Gamma$ についても $\Gamma_0\vDash\lnot p\lor q$ は成り立たない。
$p,q$ の値を $x,y$ とする。$(n\cdot p)\to q$ の値が $1$ であることは $\min\{1,nx\}\le y$ と同値である。
$\Gamma$ を充足する付値を考える。$x>0$ なら $nx\ge1$ となる $n$ があるので $y=1$ である。$x=0$ なら $\lnot p$ の値が $1$ である。どちらの場合も $\lnot p\lor q$ の値 $\max\{1-x,y\}$ は $1$ である。
$\Gamma_0$ が $n\le N$ の式だけを含むとする。$x=\tfrac1{2N}$、$y=\tfrac12$ なら、$n\le N$ で $\min\{1,nx\}\le\tfrac12$ なので $\Gamma_0$ は充足される。一方 $\max\{1-\tfrac1{2N},\tfrac12\}<1$ である。$\square$
$p$ の値は無限小になれない、という実数の Archimedes 性がこの帰結を生んでいる(MP26 §2.4)。証明は有限個の前提しか使わないので、thm-lk-complete を無限の $\Gamma$ へ広げることはできない。
$\text{Ł}_\infty$ の代数的な対応物が MV 代数である。
MV 代数 とは、集合 $A$ と 2 項演算 $\oplus$、1 項演算 $\lnot$、元 $0$ の組で、$(A,\oplus,0)$ が可換モノイドで、次を満たすものをいう。ここで $1:=\lnot0$ である。
$$
\lnot\lnot x=x,\qquad x\oplus1=1,\qquad \lnot(\lnot x\oplus y)\oplus y=\lnot(\lnot y\oplus x)\oplus x.
$$
$[0,1]$ は $x\oplus y=\min\{1,x+y\}$、$\lnot x=1-x$ で MV 代数である。第 3 の等式の両辺は $\max\{x,y\}$ に等しい(prop-lk-residuation の 1)。$V_n$ はその部分代数である。Boolean代数 は $x\oplus y=x\lor y$ で MV 代数で、このとき第 3 の等式の両辺はともに $x\lor y$ である。
Chang の完全性の証明は、MV 代数を全順序な MV 代数の積へ分解し、順序アーベル群の理論を使うものである(DF23 §1)。
$G=\mathbb{Z}\times\mathbb{Z}$ に辞書式順序を入れ、$u=(1,0)$ とする。$A=\{g\in G:(0,0)\le g\le u\}$ に、$x\oplus y:=\min\{u,x+y\}$、$\lnot x:=u-x$ を定めると、prop-lk-residuation と同じ計算により MV 代数になる。$\varepsilon=(0,1)$ とすると、すべての $n$ で $n\cdot\varepsilon=(0,n)\ne u$ である。
$A$ で $p$ に $\varepsilon$、$q$ に $\lnot\varepsilon$ を割り当てる。$A$ の順序で $n\cdot\varepsilon\le\lnot\varepsilon$ なので、prop-lk-noncompact の $\Gamma$ の値はすべて $1$ である。一方 $\lnot p\lor q$ の値は $\lnot\varepsilon\ne u$ である。
| 外す条件 | 例 | 成り立たなくなる主張 |
|---|---|---|
| 値の個数が有限 | $\text{Ł}_\infty$ | $\varphi^{n-1}$ による演繹定理(prop-lk-delta の 4) |
| 値の個数が有限 | $\text{Ł}_\infty$ | 帰結のコンパクト性(prop-lk-noncompact) |
| 値の集合が閉区間 | $[0,1]\cap\mathbb{Q}$(ex-lk-rational-sat) | 充足可能性のコンパクト性 |
| Archimedes 性 | ex-lk-chang の $A$ | $\Gamma\vDash\lnot p\lor q$ |
| $\odot$ の冪等性 $x\odot x=x$ | $\text{Ł}_3$ の $x=\tfrac12$ | 縮約 $(p\to(p\to q))\to(p\to q)$ |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する