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

最終更新

任意の命題論理式は有限個の命題変数だけを含む。したがって、その論理式の意味は有限個の付値からなる真理表に記録することができる。本稿では真理表の各行を論理式へ戻し、選言標準形と連言標準形を構成する。

1 リテラルと標準形

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

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

p1,…,pnp_1,\ldots,p_nを相異なる命題変数とし、a=(a1,…,an)∈2na=(a_1,\ldots,a_n)\in\mathbf 2^nとする。真理表の一行aaを選び出す論理式を次のように作る。

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

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

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

ma=⋀i=1nℓia,Ma=⋁i=1n¬ℓiam_a=\bigwedge_{i=1}^n\ell_i^a, \qquad M_a=\bigvee_{i=1}^n\neg\ell_i^a

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

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

vb(p)={bip=pi となる i∈{1,…,n} が存在する場合,0p∉{p1,…,pn}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}

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

vb⊨ma  ⟺  b=a,vb⊭Ma  ⟺  b=av_b\models m_a\iff b=a, \qquad v_b\not\models M_a\iff b=a

である。

証明.vb⊨ℓiav_b\models\ell_i^aであることとbi=aib_i=a_iであることは同値である。したがって、mam_aのすべてのリテラルが真であることと、すべてのiiについてbi=aib_i=a_iであることは同値である。また、MaM_aが偽であることと、すべての¬ℓia\neg\ell_i^aが偽であることは同値である。後者もb=ab=aと同値である。▨

例 1.5 (三行を表す DNF).p,qp,qのうち少なくとも一方が真である真理関数は

(¬p∧q)∨(p∧¬q)∨(p∧q)(\neg p\land q)\lor(p\land\neg q)\lor(p\land q)

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

2 標準形の存在

定理 2.1 (標準形定理).φ\varphiがp1,…,pnp_1,\ldots,p_n以外の命題変数を含まない論理式であり、n≥1n\ge 1とする。集合

Tφ={a∈2n:va⊨φ},Fφ=2n∖TφT_\varphi=\{a\in\mathbf 2^n:v_a\models\varphi\}, \qquad F_\varphi=\mathbf 2^n\setminus T_\varphi

を定める。このとき

Dφ=⋁a∈Tφma,Cφ=⋀a∈FφMaD_\varphi=\bigvee_{a\in T_\varphi}m_a, \qquad C_\varphi=\bigwedge_{a\in F_\varphi}M_a

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

v⊨φ  ⟺  v⊨Dφ  ⟺  v⊨Cφv\models\varphi\iff v\models D_\varphi \iff v\models C_\varphi

が成り立つ。

証明.vvのp1,…,pnp_1,\ldots,p_n上の値をb=(v(p1),…,v(pn))b=(v(p_1),\ldots,v(p_n))とする。真理値の局所性により、v⊨φv\models\varphiであることとb∈Tφb\in T_\varphiであることは同値である。

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

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

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

例 2.2 (含意の CNF と DNF).p→qp\to qが偽である行は(1,0)(1,0)だけである。したがって標準形定理が与える CNF は

¬p∨q\neg p\lor q

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

(¬p∧¬q)∨(¬p∧q)∨(p∧q)(\neg p\land\neg q)\lor(\neg p\land q)\lor(p\land q)

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

3 真理関数の表現可能性

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

v^(φ)=f(v(p1),…,v(pn))\widehat v(\varphi)=f(v(p_1),\ldots,v(p_n))

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

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

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

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

Df=⋁a∈SmaD_f=\bigvee_{a\in S}m_a

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

vb⊨Df  ⟺  b∈S  ⟺  f(b)=1v_b\models D_f\iff b\in S\iff f(b)=1

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

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

4 恒真性の決定手続き

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

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

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

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

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

5 演習

問題 5.1.

  1. 排他的選言を表す真理関数について、標準形定理から DNF を構成せよ。
  2. p↔qp\leftrightarrow qの CNF を、偽となる行から構成せよ。
  3. 真理表による判定手続きが、命題変数の集合PP全体の有限性を必要としない理由を述べよ。
解答 (確認問題の解答).
  1. 真となる行は(1,0)(1,0)と(0,1)(0,1)であるから、(p∧¬q)∨(¬p∧q)(p\land\neg q)\lor(\neg p\land q)となる。
  2. 偽となる行は(1,0)(1,0)と(0,1)(0,1)である。対応する最大項を連言して(¬p∨q)∧(p∨¬q)(\neg p\lor q)\land(p\lor\neg q)を得る。
  3. 一つの論理式に現れる命題変数は有限個であり、真理値の局所性によって現れない変数の値は結果を変えないからである。

▨

標準形は真理関数を論理式として表現する。次稿では、意味論的同値類に演算を入れ、命題論理式が生成する Boolean 代数として同じ構造を記述する。

参考文献

  1. Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd ed., Academic Press, 2001.
  2. E. Mendelson, Introduction to Mathematical Logic, 6th ed., CRC Press, 2015.

前提記事