命題論理の標準形 | 数理論理

1 リテラルと標準形

定義 1.1. 命題変数 $p$ またはその否定 $\neg p$ をリテラル (literal) という。有限個のリテラルの連言を連言項 (conjunctive term)、有限個のリテラルの選言を選言節 (disjunctive clause) という。空の連言は $\top$ 、空の選言は $\bot$ とする。

定義 1.2. 有限個の連言項の選言を選言標準形 (disjunctive normal form)（DNF）という。有限個の選言節の連言を連言標準形 (conjunctive normal form)（CNF）という。空個の連言項からなる DNF は $\bot$ 、空個の選言節からなる CNF は $\top$ と解釈する。

$p_1,\ldots,p_n$ を相異なる命題変数とし、 $a=(a_1,\ldots,a_n)\in\mathbf 2^n$ とする。真理表の行 $a$ でだけ真となる論理式と、行 $a$ でだけ偽となる論理式を次のように作る。

定義 1.3. $a\in\mathbf 2^n$ に対して

\ell_i^a= \begin{cases} p_i&a_i=1,\\ \neg p_i&a_i=0 \end{cases}

と置く。最小項 (minterm) と最大項 (maxterm) を

m_a=\bigwedge_{i=1}^n\ell_i^a, \qquad M_a=\bigvee_{i=1}^n\neg\ell_i^a

によって定める。結合の順序は、例えば左から結合する規約で固定する。

補題 1.4. $b\in\mathbf 2^n$ に対応する付値 $v_b:P\to\mathbf 2$ を

v_b(p)= \begin{cases} b_i&p=p_i\text{ となる }i\in\{1,\ldots,n\}\text{ が存在する場合},\\ 0&p\notin\{p_1,\ldots,p_n\} \end{cases}

と定める。 $p_1,\ldots,p_n$ は相異なるため、この定義は一意である。このとき

v_b\models m_a\iff b=a, \qquad v_b\not\models M_a\iff b=a

である。

証明. $v_b\models\ell_i^a$ であることと $b_i=a_i$ であることは同値である。したがって、 $m_a$ のすべてのリテラルが真であることと、すべての $i$ について $b_i=a_i$ であることは同値である。また、 $M_a$ が偽であることと、すべての $\neg\ell_i^a$ が偽であることは同値である。後者も $b=a$ と同値である。▨

例 1.5. $p,q$ のうち少なくとも一方が真である真理関数は

(\neg p\land q)\lor(p\land\neg q)\lor(p\land q)

という DNF で表される。吸収則を用いると $p\lor q$ に簡約することができるが、標準形の構成には簡約を必要としない。

2 標準形の存在

定理 2.1. $\varphi$ が $p_1,\ldots,p_n$ 以外の命題変数を含まない論理式であり、 $n\ge 1$ とする。集合

T_\varphi=\{a\in\mathbf 2^n:v_a\models\varphi\}, \qquad F_\varphi=\mathbf 2^n\setminus T_\varphi

を定める。このとき

D_\varphi=\bigvee_{a\in T_\varphi}m_a, \qquad C_\varphi=\bigwedge_{a\in F_\varphi}M_a

はそれぞれ DNF と CNF であり、すべての付値 $v$ について

v\models\varphi\iff v\models D_\varphi \iff v\models C_\varphi

が成り立つ。

証明. $v$ の $p_1,\ldots,p_n$ 上の値を $b=(v(p_1),\ldots,v(p_n))$ とする。真理値の局所性により、 $v\models\varphi$ であることと $b\in T_\varphi$ であることは同値である。

補題 1.4により、 $v\models D_\varphi$ であることは、 $b=a$ を満たす $a\in T_\varphi$ が存在すること、すなわち $b\in T_\varphi$ と同値である。空の選言の場合も、 $T_\varphi=\varnothing$ であるから両辺はすべての付値で偽である。

同じ補題により、 $v\not\models C_\varphi$ であることは、 $b=a$ を満たす $a\in F_\varphi$ が存在すること、すなわち $b\in F_\varphi$ と同値である。ゆえに $v\models C_\varphi$ であることと $b\in T_\varphi$ であることは同値である。空の連言の場合も、 $F_\varphi=\varnothing$ であるから両辺はすべての付値で真である。▨

標準形定理の構成では、論理式の真理表を作り、真となる行または偽となる行から再び論理式を作る。否定を原子の直前まで移動する規則と分配則を用いる変換もあるが、上の構成では、停止性と正しさを真理表から直接確認することができる。

例 2.2. $p\to q$ が偽である行は $(1,0)$ だけである。したがって標準形定理により得られる CNF は

\neg p\lor q

である。真である三行を用いる DNF は

(\neg p\land\neg q)\lor(\neg p\land q)\lor(p\land q)

である。両者は同じ真理関数を表すが、構文木としては異なる論理式である。

3 真理関数の表現可能性

定義 3.1. $f:\mathbf 2^n\to\mathbf 2$ とし、 $p_1,\ldots,p_n$ を相異なる入力変数とする。論理式 $\varphi$ が $f$ を表現する (represent a truth function) とは、すべての付値 $v$ について

\widehat v(\varphi)=f(v(p_1),\ldots,v(p_n))

が成り立つことをいう。 $n=0$ では右辺を、 $\mathbf2^0=\{()\}$ の唯一の入力における値 $f(())$ と読む。この場合、 $\varphi$ に補助変数が現れてもよいが、その値はすべての付値で一定でなければならない。

定理 3.2. $n\ge 0$ とし、 $p_1,\ldots,p_n$ を相異なる命題変数とする。背景の命題変数集合 $P$ が空でないなら、任意の真理関数 $f:\mathbf 2^n\to\mathbf 2$ は、 $\neg$ と $\to$ から作る論理式によって表現される。

証明. $n=0$ とする。 $P$ から一つの変数 $q$ を取る。 $\mathbf2^0$ の入力は $()$ だけである。 $f(())=1$ なら $q\to q$ を、 $f(())=0$ なら $\neg(q\to q)$ を取る。任意の付値 $v$ について前者の値は $1$ 、後者の値は $0$ であるから、いずれも定義どおり $f$ を表現する。この議論は $q$ の真理値に依存しない。

$n\ge1$ とする。 $S=f^{-1}(\{1\})$ と置き、

D_f=\bigvee_{a\in S}m_a

とする。 $S=\varnothing$ の場合は、 $\bot=\neg(p_1\to p_1)$ とする。補題 1.4により、任意の $b\in\mathbf 2^n$ について

v_b\models D_f\iff b\in S\iff f(b)=1

である。連言と選言は $\neg$ と $\to$ の略記として定義されているため、 $D_f$ は $\neg$ と $\to$ だけから作る論理式を表す。▨

注意 3.3 (変数が零個の場合). $n=0$ の真理関数は、唯一の入力 $()$ を $0$ へ送る関数と $1$ へ送る関数の二つである。原始論理定数がなくても、空でない背景変数集合から取った $q$ により $\neg(q\to q)$ と $q\to q$ がそれぞれを表現する。背景変数集合自体が空の場合は論理式が存在しないため、Boolean 商の記事では定数付きの保守的拡大を別に定める。

4 恒真性の決定手続き

定理 4.1. 有限の命題論理式 $\varphi$ に対して、 $\varphi$ が恒真であるか否かを有限回の操作で判定する手続きが存在する。

証明. $\varphi$ に現れる相異なる命題変数を $p_1,\ldots,p_n$ とする。 $n$ は有限である。 $n=0$ の論理式は本稿の構文には存在しないので $n\ge1$ である。

$\mathbf 2^n$ の $2^n$ 個の要素を列挙する。各 $a\in\mathbf 2^n$ について、構文木を下から上へ有限回たどり、原子、否定、含意の真理値規則を適用して $\widehat{v_a}(\varphi)$ を計算する。構文木は有限であり、調べる付値も有限個であるから手続きは停止する。

すべての行で値が $1$ なら、任意の付値は $p_1,\ldots,p_n$ 上で列挙した行の一つと一致する。真理値の局所性により、その付値でも $\varphi$ は真であるから $\varphi$ は恒真である。値が $0$ の行があれば、対応する付値が恒真性への反例である。したがって手続きの出力は正しい。▨

例 4.2. 論理式 $(p\to q)\to p$ を調べる。 $v(p)=0,v(q)=0$ とすると $p\to q$ は真であり、外側の含意は偽である。したがって論理式は恒真ではない。判定手続きは否定の答えだけでなく、この付値を反例として与える。

5 演習

問題 5.1.

排他的選言を表す真理関数について、標準形定理から DNF を構成せよ。
$p\leftrightarrow q$ の CNF を、偽となる行から構成せよ。
命題変数の集合 $P$ は無限集合でもよいとする。有限集合 $\Gamma\subseteq\operatorname{Form}(P)$ と $\varphi\in\operatorname{Form}(P)$ に対して、 $\Gamma\models_{\mathrm{PL}}\varphi$ であるか否かを有限回の操作で判定する手続きを与え、その出力が正しいことを証明せよ。また、この手続きにより $\{p\to q,\ q\to r\}\models_{\mathrm{PL}}p\to r$ であることと、 $\{p\to q,\ q\}\models_{\mathrm{PL}}p$ ではないことを判定せよ。ここで $p,q,r$ は相異なる命題変数である。

解答 (確認問題の解答).

真となる行は $(1,0)$ と $(0,1)$ であるから、 $(p\land\neg q)\lor(\neg p\land q)$ となる。
偽となる行は $(1,0)$ と $(0,1)$ である。対応する最大項を連言して $(\neg p\lor q)\land(p\lor\neg q)$ を得る。
$\Gamma\cup\{\varphi\}$ の各論理式に現れる命題変数は有限個であり、 $\Gamma$ は有限集合であるから、 $\Gamma\cup\{\varphi\}$ のいずれかの論理式に現れる相異なる命題変数の全体は有限集合 $\{p_1,\ldots,p_n\}$ である。手続きは、各 $a\in\mathbf 2^n$ について、補題 1.4の付値 $v_a$ のもとで $\Gamma$ の各論理式と $\varphi$ の真理値を定理 4.1の証明と同じく構文木を下からたどって計算し、 $\Gamma$ のすべての論理式が真で $\varphi$ が偽となる $a$ が存在しなければ「帰結である」と出力し、存在すれば「帰結でない」と出力する。調べる $a$ は $2^n$ 個であり、各計算は有限回の操作で終わるので、手続きは停止する。

出力の正しさを示す。 $\Gamma$ のすべての論理式が真で $\varphi$ が偽となる $a$ が存在すれば、 $v_a$ は $\Gamma\models_{\mathrm{PL}}\varphi$ への反例であるから、「帰結でない」は正しい。逆に $\Gamma\models_{\mathrm{PL}}\varphi$ でないとすると、 $\Gamma$ のすべての論理式を真にし $\varphi$ を偽にする付値 $v:P\to\mathbf 2$ が存在する。 $b=(v(p_1),\ldots,v(p_n))$ とおくと、 $v$ と $v_b$ は $\Gamma\cup\{\varphi\}$ の各論理式に現れる変数の上で一致するので、§E19.1 命題 2.3により $v_b$ も $\Gamma$ のすべての論理式を真にし $\varphi$ を偽にする。したがって手続きは行 $b$ を見つけて「帰結でない」と出力する。対偶により、「帰結である」と出力するのは $\Gamma\models_{\mathrm{PL}}\varphi$ のときに限り、上の二つから出力は正しい。 $P$ の残りの変数の値は計算に現れないので、 $P$ が無限集合であっても調べる付値は $2^n$ 個で足りる。

$\{p\to q,\ q\to r\}$ と $p\to r$ では $n=3$ である。 $p\to r$ が偽となる行は $p=1$ かつ $r=0$ の行に限る。その行で $p\to q$ が真であるには $q=1$ でなければならず、 $q\to r$ が真であるには $q=0$ でなければならないので、二つの前提がともに真で $p\to r$ が偽となる行は存在しない。よって手続きは「帰結である」と出力し、 $\{p\to q,\ q\to r\}\models_{\mathrm{PL}}p\to r$ である。 $\{p\to q,\ q\}$ と $p$ では $n=2$ であり、 $p=0$ 、 $q=1$ の行で $p\to q$ と $q$ はともに真で $p$ は偽である。よって手続きは「帰結でない」と出力し、この行の付値が反例である。

▨

§E19.2命題論理の標準形

1 リテラルと標準形

2 標準形の存在

3 真理関数の表現可能性

4 恒真性の決定手続き

5 演習

参考文献

前提記事