標準形

この単元のこれまでの課では、論理式に意味が与えられた。命題論理の意味論の課は各付値をすべての論理式に拡張した。意味論的帰結と同値の課は同値 $\varphi \eqsem \psi$ を定義し、意味論的置換を証明した。一般化されたド・モルガンの法則と分配法則の課はそれらの法則を $n$ 個の論理式の連言と選言に拡張した。そして関数的完全性の課は、すべての真理関数がある論理式によって表されることを示した。ところが、一つの真理関数は無限に多くの論理式によって表され、それらは互いに大きく異なりうる。$(v_1 \rightarrow v_2)$、$\neg(v_1 \wedge \neg v_2)$、$(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ は同じものの三つの名前である。そうであるならば、各同値類から決まった形の代表を選ぶのがよい。それは苦労なく読め、いくつかの問いには見るだけで答えられる。それが標準形である。

リテラル、節、標準形

一般化された法則の課から、$n$ 個の論理式の連言と選言の記法を思い出そう。これは再帰によって左結合で定義され、論理式が一つだけのときはその論理式自身である。

同じ課で、項の順序とまとめ方は同値を除いて論理式を変えないこと（一般化された結合律と、順序と重複への非依存性）が証明された。そのため、括弧を省いて $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ とも書き、左結合のまとめ方を了解する。

リテラルとは、変数 $v_n$（正リテラルという）、または変数の否定 $\neg v_n$（負リテラルという）である。リテラル $\ell$ の反対のリテラルを $\ell^{*}$ と書き、それは同じ変数で符号が逆のリテラルである。

定義から $(\ell^{*})^{*} = \ell$ が従う。二つのリテラルは、一方が他方の反対のリテラルであるとき相補対をなす。たとえば $v_3$ と $\neg v_3$ である。

節とはリテラルの選言 $\bigvee_{j=1}^{k} \ell_j$ であり、基本連言とはリテラルの連言 $\bigwedge_{j=1}^{k} \ell_j$ である。どちらの場合も $k \geq 1$ である。したがって、リテラル一つは節でもあり基本連言でもある。リテラルが節または基本連言の $\ell_j$ の一つであるとき、そのリテラルはそこに現れるという。

論理式は、基本連言の選言であるとき選言標準形にあり、節の連言であるとき連言標準形にある。すなわち、それぞれ次の二つの形のいずれかであるときである。ここで $m$ と $k_1, \ldots, k_m$ は自然数であり、各 $\ell_{i,j}$ はリテラルである。

$\Phi$ が $\varphi$ の選言標準形であるとは、それが選言標準形にあり、かつ $\varphi \eqsem \Phi$ であることをいう。連言標準形についても同様である。長さ $k_i$ は連言（または節）ごとに異なってよい。すべてに同じ個数のリテラルを要求すれば、繰り返しで埋めなければならなくなり、何も付け加えない。

「標準形にある」とは何を意味するのか、立ち止まって考える価値がある。それは白丸と黒丸の記号列の性質であって、その意味の性質ではない。自然数と論理式に関する帰納法の課は一意読み取り可能性を証明したので、論理式が選言であるかどうか、そして何の選言であるかという問いには答えがただ一つしかない。ところが、公式の略記のために、標準形に見えないのに標準形にある論理式がある。含意 $(v_1 \rightarrow v_2)$ は $(\neg v_1 \vee v_2)$ と定義される。それがこの節と同値なのではなく、同じ記号列そのものなのであり、したがってすでに標準形にある。さらに意外なのは二重否定である。$\neg$ と $\vee$ の定義により、記号列 $(\varphi \vee \varphi)$ は $\neg(\varphi \downarrow \varphi)$、すなわち $\neg\neg\varphi$ である。ゆえに $\neg\neg v_1$ はリテラルではないが、一字一字、節 $(v_1 \vee v_1)$ である。

連言と選言の値

意味論の課から派生結合子の値を借りる。$v(\neg\varphi) = 1 - v(\varphi)$。$v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$ は値 $1$ をとり、それは両方が値 $1$ をとるとき、かつそのときに限る。$v(\varphi \vee \psi) = 0$ は、両方が値 $0$ をとるとき、かつそのときに限る。一般化されたド・モルガンの法則と分配法則の課は、項の個数に関する帰納法によって、これらを $n$ 個の論理式に拡張した。それが値の補題である。すべての付値 $v$ について、連言 $\bigwedge_{i=1}^{n} \varphi_i$ が値 $1$ を $v$ でとるのは、各 $\varphi_i$ が値 $1$ を $v$ でとるとき、かつそのときに限り、選言 $\bigvee_{i=1}^{n} \varphi_i$ が値 $1$ を $v$ でとるのは、ある $\varphi_i$ が値 $1$ を $v$ でとるとき、かつそのときに限る。ここでは証明を繰り返さずに引用するこの補題が、任意の標準形の値を計算する道具である。

二つ目の場合は見落としやすい。標準形を否定するとき、リテラルの代わりに $\neg\ell_{i,j}$ と書きたくなるが、$\neg\neg v_n$ はリテラルではない。結果を型に戻すのは二重否定である。