選言標準形と連言標準形
概要
選言標準形と連言標準形（disjunctive and conjunctive normal forms）とは、命題論理の論理式のうち、リテラルの連言を選言でつないだ形（選言標準形）と、リテラルの選言を連言でつないだ形（連言標準形）である。どの論理式も両方と論理的に同値で、すべての変数を含む完全な標準形は、あれば真理値表から節の並べ方を除いて一意に決まり、選言標準形では充足可能性が、連言標準形では恒真性が一目で分かる。一方、$(p_1\lor q_1)\land\cdots\land(p_n\lor q_n)$ と同値な選言標準形は $2^n$ 個以上の項を要するなど、変形で式は指数的に長くなりうる。新しい変数を使えば、充足可能性だけを保つ短い連言標準形に移せる。
選言標準形（disjunctive normal form, DNF）は「リテラルの連言」を選言でつないだ論理式、連言標準形（conjunctive normal form, CNF）は「リテラルの選言」を連言でつないだ論理式である。たとえば $(p\land\lnot q)\lor(\lnot p\land q)$ は選言標準形、$(p\lor q)\land(\lnot p\lor\lnot q)$ は連言標準形で、この 2 つは論理的に同値である（どちらも「$p,q$ のちょうど一方が真」を表す）。
どの論理式も両方の標準形と論理的に同値である。選言標準形は「どの場合に真になるか」を、連言標準形は「どの条件をすべて満たせばよいか」を列挙した形で、前者は充足可能性が、後者は恒真性が一目で分かる。一方、同値な標準形への変形では式が指数的に長くなることがあり、その下界は具体的な論理式で証明できる。この記事では、2 つの標準形の存在と、すべての変数を含む完全な標準形の一意性を証明し、分配律による変形の手順、標準形の大きさの下界、充足可能性だけを保つ短い連言標準形への変換を扱う。
論理式・付値・真理関数の定め方と記号は 命題論理 の記事にそろえる。命題変数は $p,q,r,p_i,q_i$ などで表し、真理値は $\mathrm T$（真）・$\mathrm F$（偽）で書く。
定義
命題変数 $p$ とその否定 $\lnot p$ を リテラル という（論理的同値 の記事の定義「否定標準形」の前の段落）。$\lnot p$ を $p$ の 相補 なリテラル、$p$ を $\lnot p$ の相補なリテラルという。
- 1 個以上のリテラルの連言 $\ell_1\land\cdots\land\ell_m$ を 連言節（項）、選言 $\ell_1\lor\cdots\lor\ell_m$ を 選言節（節）という。
- 1 個以上の連言節の選言 $C_1\lor\cdots\lor C_k$ を 選言標準形 の論理式という。
- 1 個以上の選言節の連言 $D_1\land\cdots\land D_k$ を 連言標準形 の論理式という。
- 命題変数 $p_1,\dots,p_n$ を固定する。各 $p_i$ について $p_i$ か $\lnot p_i$ のちょうど一方を含み、ほかのリテラルを含まない連言節（選言節）を 完全 であるという。完全な連言節を相異なるものだけ選言でつないだ論理式を 完全選言標準形、完全な選言節を相異なるものだけ連言でつないだ論理式を 完全連言標準形 という。
選言標準形の連言節の個数、連言標準形の選言節の個数を、その標準形の 項数 という。
$\land,\lor$ は結合的かつ可換なので（論理的同値 の記事の例「基本的な論理的同値」）、節の中のリテラルの並べ方と括弧の付け方、節の並べ方は論理的同値を変えない。以下、節をリテラルの集合と、標準形を節の集合とみなして扱う。この定義は Gal15 Definition 3.4.7（p. 70）と同じである。
リテラル 1 個も連言節であり選言節でもあるので、$p\lor\lnot q$ は選言標準形（連言節 $p$ と $\lnot q$ の選言）であると同時に、連言標準形（選言節 $p\lor\lnot q$ 1 個）でもある。
付値 $a\in\{\mathrm T,\mathrm F\}^n$（$a_i$ を $p_i$ の値とする）に対し、$a_i=\mathrm T$ なら $\ell_i^a:=p_i$、$a_i=\mathrm F$ なら $\ell_i^a:=\lnot p_i$ とおき、
$$
C_a:=\ell_1^a\land\cdots\land\ell_n^a,\qquad D_a:=\overline{\ell_1^a}\lor\cdots\lor\overline{\ell_n^a}
$$
と定める（$\overline{\ell}$ は相補なリテラル）。$C_a$ は付値 $a$ でだけ真、$D_a$ は付値 $a$ でだけ偽である。$a\mapsto C_a$ は $\{\mathrm T,\mathrm F\}^n$ から完全な連言節の全体への全単射、$a\mapsto D_a$ は完全な選言節の全体への全単射である。
存在と一意性
$n\ge1$ とし、$\varphi$ を $p_1,\dots,p_n$ だけを含む論理式、$f_\varphi$ をその真理関数とする。
- $\varphi$ が恒真式でなければ、$\varphi$ は完全連言標準形 $\displaystyle\bigwedge_{f_\varphi(a)=\mathrm F}D_a$ と論理的に同値である。
- $\varphi$ が充足可能なら、$\varphi$ は完全選言標準形 $\displaystyle\bigvee_{f_\varphi(a)=\mathrm T}C_a$ と論理的に同値である。
- $\varphi$ と論理的に同値な完全連言標準形（完全選言標準形）は、節の並べ方を除いて 1 の（2 の）ものに限る。
- どの $\varphi$ も、選言標準形とも連言標準形とも論理的に同値である。
1：$\psi:=\bigwedge_{f_\varphi(a)=\mathrm F}D_a$ とおく（恒真式でないので節は 1 個以上ある）。付値 $b$ で $\psi$ が偽になるのは、ある $a$ で $f_\varphi(a)=\mathrm F$ かつ $D_a$ が $b$ で偽、すなわち $b=a$ のときに限る。よって $\psi$ が $b$ で偽 $\iff$ $f_\varphi(b)=\mathrm F$ であり、$\psi\equiv\varphi$ である。
2：同様に、$\bigvee_{f_\varphi(a)=\mathrm T}C_a$ が $b$ で真になるのは $f_\varphi(b)=\mathrm T$ のときに限る（命題論理 の記事の定理「選言標準形による関数的完全性」の証明と同じ）。
3：完全連言標準形 $\bigwedge_{a\in A}D_a$（$A$ は付値の集合）が偽になる付値の集合は、$D_a$ が $a$ でだけ偽なので、ちょうど $A$ である。同値な 2 つの完全連言標準形は偽になる付値の集合が同じなので、同じ $A$ をもち、節の集合が一致する。これが $\varphi$ と同値なら $A=\{a\mid f_\varphi(a)=\mathrm F\}$ である。完全選言標準形も同様に、真になる付値の集合が節の集合を決める。
4：連言標準形は、恒真式でなければ 1 により、恒真式なら選言節 1 個の $p_1\lor\lnot p_1$ で得られる。選言標準形は、充足可能なら 2 により、充足不能なら連言節 1 個の $p_1\land\lnot p_1$ で得られる。$\square$
2 は 命題論理 の記事の定理「選言標準形による関数的完全性」の証明の形そのもので、1 はその双対である。完全な標準形の存在は Gal15 の問題 3.3.13（p. 56）でも扱われている。
- 選言標準形の論理式が充足可能であるのは、相補なリテラルの組を含まない連言節があるときに限る。
- 連言標準形の論理式が恒真式であるのは、すべての選言節が相補なリテラルの組を含むときに限る。
1：連言節が真になる付値があるのは、節の中に $p$ と $\lnot p$ の組がないとき（そのとき各リテラルを真にする付値をとれる）に限る。選言標準形は、どれかの連言節が真になる付値で真になる。2：選言節が偽になる付値があるのは、相補な組がないときに限り（各リテラルを偽にする付値をとる）、連言標準形が恒真なのは、どの選言節も偽にならないときである。$\square$
逆向きの問い、すなわち連言標準形の充足可能性は、NP完全 の記事の定義「連言標準形と充足可能性」の SAT であり、NP 完全問題の代表である。選言標準形の否定は De Morgan の法則で同じ大きさの連言標準形になるので、選言標準形の恒真性の判定は連言標準形の充足可能性の判定に移る。2 つの標準形は「易しく判定できる性質」が逆になっている。
分配律による変形
真理値表を使わずに、式の変形で標準形を得ることもできる。まず 論理的同値 の記事の定理「否定標準形の存在」で、$\to$ を消し否定を変数の直前に押し込んだ否定標準形 $N(\varphi)$ に移す。そのあと次の手順を使う。
否定標準形の論理式 $\varphi$ に対し、選言標準形 $\mathrm{DNF}(\varphi)$ を、リテラル $\ell$ では $\mathrm{DNF}(\ell):=\ell$、
$$
\mathrm{DNF}(\varphi\lor\psi):=\mathrm{DNF}(\varphi)\lor\mathrm{DNF}(\psi),\qquad
\mathrm{DNF}(\varphi\land\psi):=\bigvee_{i,j}(C_i\land C'_j)
$$
（$\mathrm{DNF}(\varphi)=\bigvee_iC_i$、$\mathrm{DNF}(\psi)=\bigvee_jC'_j$）で定める。このとき $\mathrm{DNF}(\varphi)\equiv\varphi$ であり、項数 $t$ は $t(\varphi\lor\psi)=t(\varphi)+t(\psi)$、$t(\varphi\land\psi)=t(\varphi)\,t(\psi)$ を満たす（同じ節が重複して現れるときは重複も数える）。$\land$ と $\lor$ の役割を入れ替えると連言標準形 $\mathrm{CNF}(\varphi)$ が同様に得られる。
$\varphi$ の組み立てについての帰納法で示す。リテラルと $\lor$ の場合は帰納法の仮定と合同性（論理的同値 の記事の定理「代入と論理的同値」の後の段落）による。$\land$ の場合、帰納法の仮定により $\varphi\land\psi\equiv(\bigvee_iC_i)\land(\bigvee_jC'_j)$ である。分配律 $\chi\land(\theta_1\lor\theta_2)\equiv(\chi\land\theta_1)\lor(\chi\land\theta_2)$ を、選言の項の個数についての帰納法で繰り返し使うと、$\chi\land\bigvee_j\theta_j\equiv\bigvee_j(\chi\land\theta_j)$ である。これを $\chi:=C_i$ について使い、さらに $\land$ の可換性で左右を入れ替えて同じことを $\bigvee_iC_i$ にも使うと、$\bigvee_{i,j}(C_i\land C'_j)$ を得る。$C_i\land C'_j$ はリテラルの連言なので連言節である。項数の式は定義から明らかである。$\square$
項数の式から分かるとおり、$\land$ の下に $\lor$ が重なるごとに項数が掛け算で増える。Gal15 Lemma 3.4.5（p. 73）は、同じ手順を連言標準形について述べている。
例
$\varphi:=p\to(q\land r)$ の否定標準形は $\lnot p\lor(q\land r)$ で、これはすでに選言標準形である。prop-nf-distribution の双対の手順で連言標準形にすると $(\lnot p\lor q)\land(\lnot p\lor r)$ である。$\varphi$ が偽になるのは $p$ が真で $q,r$ の少なくとも一方が偽の 3 通りなので、完全連言標準形は
$$
(\lnot p\lor q\lor r)\land(\lnot p\lor q\lor\lnot r)\land(\lnot p\lor\lnot q\lor r)
$$
である。$p,q,r$ がすべて真の付値では $\varphi$ は真なので、その付値の節 $\lnot p\lor\lnot q\lor\lnot r$ は入らない。真になる付値は 5 通りなので、完全選言標準形は 5 項である。
3 変数のうち 2 個以上が真のとき真になる関数 $\mathrm{maj}(p,q,r)$ は、選言標準形 $(p\land q)\lor(q\land r)\lor(r\land p)$ でも、連言標準形 $(p\lor q)\land(q\lor r)\land(r\lor p)$ でも表せる。後者が正しいことは、2 個以上が偽なら偽になる選言節が残り、偽が 1 個以下ならどの選言節も真になることから分かる。完全選言標準形は真になる 4 通りの付値に対応する 4 項になる。
標準形の大きさの下界
分配律による展開で項数が増えるのは手順のせいではなく、避けられない場合がある。以下、節の中に相補なリテラルの組があるものを 自明な節 という。自明な連言節はどの付値でも偽、自明な選言節はどの付値でも真なので、標準形から取り除いても論理的同値は変わらない。
$n\ge1$ とし、$p_1,\dots,p_n,q_1,\dots,q_n$ を相異なる命題変数とする。
$$
\varphi_n:=(p_1\lor q_1)\land(p_2\lor q_2)\land\cdots\land(p_n\lor q_n)
$$
は項数 $n$ の連言標準形であるが、$\varphi_n$ と論理的に同値な選言標準形の項数は $2^n$ 以上である。双対に、$\psi_n:=(p_1\land q_1)\lor\cdots\lor(p_n\land q_n)$ と同値な連言標準形の項数は $2^n$ 以上である。
$\bigvee_{k}C_k$ を $\varphi_n$ と同値な選言標準形とし、自明な連言節は取り除いておく（取り除いても項数は増えず、同値も保たれる）。
段 1：各 $C_k$ はどの $i$ についても $p_i$ か $q_i$ をリテラルとして含む。 ある $i$ でどちらも含まないとする。$C_k$ は自明でないので、$C_k$ のリテラルをすべて真にし、さらに $p_i,q_i$ を偽にする付値 $v$ がとれる（$C_k$ が含みうるのは $\lnot p_i,\lnot q_i$ だけなので、これと矛盾しない）。$v$ で $C_k$ は真、$p_i\lor q_i$ は偽なので、選言標準形は真、$\varphi_n$ は偽となり、同値に反する。
段 2：項数は $2^n$ 以上である。 写像 $c\colon\{1,\dots,n\}\to\{p,q\}$ ごとに、$c(i)$ が $p$ なら $p_i$、$q$ なら $q_i$ だけを真にし、残りの変数（選言標準形に現れるほかの変数も含む）をすべて偽にする付値 $v_c$ をとる。$v_c$ で $\varphi_n$ は真なので、ある $C_k$ が $v_c$ で真である。$C_k$ の否定のないリテラルは $v_c$ で真なので、選ばれた $n$ 個の変数の中にある。段 1 と合わせると、$C_k$ の否定のないリテラルの集合は、選ばれた $n$ 個の変数（$c(i)$ に対応するもの）にちょうど一致する。したがって $c\ne c'$ なら対応する $C_k$ は異なり、$c$ は $2^n$ 通りあるので項数は $2^n$ 以上である。
後半：$\lnot\psi_n$ は De Morgan の法則で $\bigwedge_i(\lnot p_i\lor\lnot q_i)$ と同値である。$\psi_n$ と同値な連言標準形 $\bigwedge_kD_k$ があれば、その否定は De Morgan の法則で同じ項数の選言標準形になり、$\bigwedge_i(\lnot p_i\lor\lnot q_i)$ と同値である。この選言標準形のリテラルをすべて相補なリテラルに取り替えると、付値 $v$ での値は、取り替える前の式の、すべての変数の値を反転した付値での値に等しい。$\bigwedge_i(\lnot p_i\lor\lnot q_i)$ に同じ取り替えをすると $\varphi_n$ になるので、同じ項数の選言標準形で $\varphi_n$ と同値なものが得られ、前半により項数は $2^n$ 以上である。$\square$
$\varphi_n$ を分配律で展開すると、各 $i$ から $p_i$ か $q_i$ を 1 つずつ選んだ $2^n$ 個の連言節が現れる（論理的同値 の記事の否定標準形の節の例）。thm-nf-lower-bound はこの展開が最小であることを示す。次の例では、どちらの標準形も大きくなる。
$\pi_n$ を、$p_1,\dots,p_n$ のうち真であるものの個数が奇数のときに真となる真理関数を表す論理式とする。$\pi_n$ と同値な選言標準形の項数と連言標準形の項数は、どちらも $2^{n-1}$ 以上である。また、$\pi_n$ の完全選言標準形・完全連言標準形の項数はちょうど $2^{n-1}$ である。
同値な選言標準形から自明な連言節を除き、その連言節 $C$ を 1 つとる。$C$ がある $p_i$ を（肯定でも否定でも）含まないとすると、$C$ を真にする付値 $v$ をとり、$p_i$ の値だけを反転した付値 $v'$ でも $C$ は真である。$v$ と $v'$ では $p_1,\dots,p_n$ のうち真のものの個数の偶奇が異なるので、一方で $\pi_n$ は偽だが $C$ は真で、同値に反する。よって $C$ は $p_1,\dots,p_n$ をすべて含み、$C$ を真にする付値では $p_1,\dots,p_n$ の値がただ 1 通りに決まる。$\pi_n$ を真にする $p_1,\dots,p_n$ の値の組は $2^{n-1}$ 個（$p_1,\dots,p_{n-1}$ を任意に決めると $p_n$ の値がただ 1 つ決まる）あり、どの組もそれを含む付値でどれかの連言節を真にするので、項数は $2^{n-1}$ 以上である。連言標準形では、自明でない選言節が同様に $p_1,\dots,p_n$ をすべて含み、それを偽にする付値では $p_1,\dots,p_n$ の値がただ 1 通りに決まることと、$\pi_n$ を偽にする値の組が $2^{n-1}$ 個あることから従う。最後の主張は thm-nf-existence の 1・2 の形による。$\square$
充足可能性だけを保つ短い連言標準形
thm-nf-lower-bound により、同値な連言標準形は長くなりうる。充足可能性を調べるだけなら、新しい変数を使って、元の式の長さに比例する長さの連言標準形に移せる。
$\varphi$ を $\lnot,\land,\lor$ だけから作られた論理式とし、その部分論理式の出現 $\chi$ ごとに、$\varphi$ に現れない相異なる新しい命題変数 $r_\chi$ を用意する（$\chi$ が命題変数 $p$ なら $r_\chi:=p$ とする）。結合子の出現ごとに次の選言節を作る。
$$
\begin{aligned}
\chi=\lnot\alpha&:\ (\lnot r_\chi\lor\lnot r_\alpha),\ (r_\chi\lor r_\alpha),\\
\chi=\alpha\land\beta&:\ (\lnot r_\chi\lor r_\alpha),\ (\lnot r_\chi\lor r_\beta),\ (r_\chi\lor\lnot r_\alpha\lor\lnot r_\beta),\\
\chi=\alpha\lor\beta&:\ (\lnot r_\chi\lor r_\alpha\lor r_\beta),\ (r_\chi\lor\lnot r_\alpha),\ (r_\chi\lor\lnot r_\beta).
\end{aligned}
$$
これらすべてと選言節 $r_\varphi$ の連言を $T(\varphi)$ とする。$T(\varphi)$ の項数は結合子の個数の 3 倍に 1 を足した数以下であり、$\varphi$ が充足可能であるのは $T(\varphi)$ が充足可能であるときに限る。
各結合子の選言節の組は、それぞれ $r_\chi\leftrightarrow\lnot r_\alpha$、$r_\chi\leftrightarrow(r_\alpha\land r_\beta)$、$r_\chi\leftrightarrow(r_\alpha\lor r_\beta)$ と論理的に同値である（$r_\chi$ の 2 つの値に分けて確かめられる）。$\varphi$ を真にする付値 $v$ があれば、新しい変数に $w(r_\chi):=v(\chi)$ と値を与えて $v$ を延ばした付値 $w$ は、真理値の定義によりすべての同値を満たし、$w(r_\varphi)=\mathrm T$ なので $T(\varphi)$ を真にする。逆に $T(\varphi)$ を真にする付値 $w$ があれば、部分論理式の組み立てについての帰納法で $w(r_\chi)=w(\chi)$ が分かる（命題変数では定義、結合子では上の同値と帰納法の仮定による）。とくに $w(\varphi)=w(r_\varphi)=\mathrm T$ である。項数は結合子 1 個につき 3 個以下と $r_\varphi$ の 1 個である。$\square$
$T(\varphi)$ は $\varphi$ と同値ではない（新しい変数を含む）。この変換は Gal15 の問題 4.2.4（p. 121）にも演習としてある。これにより、任意の論理式の充足可能性の問題は、連言標準形の充足可能性の問題（NP完全 の記事の SAT）に、長さを比例の範囲に保って移せる。
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 完全であること（thm-nf-existence の 3） | $p$ と $p\lor(p\land q)$（変数 $p,q$） | 同値な標準形が節の並べ方を除いて 1 つであること |
| 選言標準形であること（thm-nf-lower-bound） | $\varphi_n$ 自身（論理式として長さは $n$ に比例） | 同値な論理式の大きさが $2^n$ 以上であること |
| 論理的同値（prop-nf-parity を充足同値に弱める） | 新しい変数 $s_1,\dots,s_n$ を使う下の 3 の連言標準形（$n\ge6$） | 連言標準形の項数が $2^{n-1}$ 以上であること |
1 行目：$p$ と $p\lor(p\land q)$ はどちらも選言標準形で、吸収律により同値だが、節の集合 $\{p\}$ と $\{p,\ p\land q\}$ は異なる。どちらも完全でない（$p$ は $q$ を含まない）。完全選言標準形はどちらも $(p\land q)\lor(p\land\lnot q)$ になる。2 行目：$\varphi_n$ は $2n-1$ 個の結合子で書けており、選言標準形に限らなければ指数的な大きさは要らない。3 行目：$\pi_{k+1}$ を $(\pi_k\land\lnot p_{k+1})\lor(\lnot\pi_k\land p_{k+1})$ と書くと $\pi_k$ が 2 回現れて長さが倍々になる。そこで新しい変数 $s_k$ を「$p_1,\dots,p_k$ の真の個数が奇数」の代わりに使い、選言節 $\lnot s_1\lor p_1$、$s_1\lor\lnot p_1$ と、$k=1,\dots,n-1$ についての 4 個の選言節 $\lnot s_{k+1}\lor s_k\lor p_{k+1}$、$\lnot s_{k+1}\lor\lnot s_k\lor\lnot p_{k+1}$、$s_{k+1}\lor\lnot s_k\lor p_{k+1}$、$s_{k+1}\lor s_k\lor\lnot p_{k+1}$（これらで $s_{k+1}\leftrightarrow(s_k$ と $p_{k+1}$ のちょうど一方が真$)$ と同値）と、$s_n$ の連言をとる。項数は $4n-1$ で、$n\ge6$ では $2^{n-1}$ より小さい。これを真にする付値は $p$ の値が $\pi_n$ を真にするものだけであり、$\pi_n$ と充足同値になる。しかし新しい変数を含むので $\pi_n$ と同値ではない。
補足：Boole 代数との関係
論理式の同値類は Boole代数 をなす（命題論理 の記事の定理「論理式の同値類のなすBoole代数」）。変数を $p_1,\dots,p_n$ に限ると、完全な連言節 $C_a$ の類はこの Boole 代数の原子（$0$ でない最小の元）である。実際、$\psi\to C_a$ が恒真で $\psi$ が充足可能なら、$\psi$ が真になる付値は $a$ だけで、$\psi\equiv C_a$ となる。thm-nf-existence の 2・3 は、この Boole 代数の $0$ でないどの元も原子の結びにただ 1 通りに書けることを、論理式の言葉で述べたものである。選言標準形と連言標準形の双対性は、Boole 代数の結びと交わりの双対性（De Morgan の法則）に対応している。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
