ブール代数

  • 2019/05/29 09:00
この記事は, 旧ブログから移植された記事です. よって, その内容として, 旧ブログに依存した文脈が含まれている可能性があります. 予めご了承下さい.

ブール代数は古典論理における命題論理と密接に関連している. 結論からいえば, 両者の違いは歴史的な背景ぐらいであり, 殆どの場合は同等の理論であるということができる1. ブール代数はその応用として論理回路の構築に直接役立つことから, 計算機科学, とくにハードウェアの分野において重宝される代数系の 1 つである.

ブール代数の公理とその定理

次に示すのはブール代数の公理系である. 公理系に関する詳細は証明理論 (TODO) の冒頭を参照のこと.

ブール代数

半順序集合 (B,,,,0,1)(B,\lor,\land,',0,1) が可補分配ならば, (B,,,,0,1)(B,\lor,\land,',0,1) はブール代数である. すなわち, x,y,zBx,y,z\in B に対して, 次のすべての公理を満たした (B,,,,0,1)(B,\lor,\land,',0,1) はブール代数である.

  1. 可換律\htmlId{boolean_algebra1}{\rm 可換律}: xy=yx,xy=yxx\land y=y\land x,x\lor y=y\lor x
  2. 分配律\htmlId{boolean_algebra2}{\rm 分配律}: (xy)z=(xz)(yz),(xy)z=(xz)(yz)(x\lor y)\land z=(x\land z)\lor(y\land z),(x\land y)\lor z=(x\lor z)\land(y\lor z)
  3. 同一律\htmlId{boolean_algebra3}{\rm 同一律}: xL^\forall x\in L に対して x1=x,x0=xx\land 1=x,x\lor 0=x. ここで 11 は最大限, 単位元である. 00 は最小限, 零元である.
  4. 補元律\htmlId{boolean_algebra4}{\rm 補元律}: xL s.t. xL,xx=1,xx=0^\exists x'\in L\ {\rm s.t.}\ ^\forall x\in L, x\lor x'=1, x\land x'=0

また, この 1,01,0 からのみ成る集合をブール領域, ブール代数の下に書かれた式をブール式, nNn\in\mathbb{N} 個のブール領域の引数をとり, 1 個のブール領域の値となる関数 f:BnBf:B^n\to B をブール関数という. 例えば, 2 変数ブール関数 f(x1,x2)f(x_1,x_2) では x1,x2x_1,x_2 がそれぞれ 1,01,0 のいずれかとなるので, 24=162^4=16 通りの 2 変数ブール式が存在することとなる. 以下, 演算の優先順序は左結合性で ,,',\land,\lor の順とする. ただし, 括弧内の演算はより優先される.

さてブール代数の公理における乗法 \land と加法 \lor, および 1,01, 0 をそれぞれ入れ替えると, 再びブール代数の公理である. これは双対の原理という公理である.

双対の原理

ブール代数で成立する文/式は, そこに現れるすべての ,,0,1\lor ,\land,0,1 をそれぞれ ,,1,0\land,\lor ,1,0 で置き換えても成立する.

これらの公理から補元の一意性, べき等律, 有界律, 吸収律, 結合律, 対合律, ド・モルガンの法則, シャノンの展開定理が導出可能である. 以下 x,y,zBx,y,z\in B とする.

補元の一意性

xx に対する補元は一意である.

補元の一意性

2 つの xx の補元 x1,x2x'_1,x'_2 を仮定する. x1=x11(公理3:同一律)=x1(xx2)(公理4:補元律)=(x1x)(x1x2)(公理2:分配律)=0(x1x2)(公理4:補元律)=(xx2)(x1x2)(公理4:補元律)=x2(xx1)(公理2:分配律)=x21(公理4:補元律)=x2(公理3:同一律)\begin{aligned} x'_1&=&x'_1\land1&(\because {\rm \href{#boolean_algebra3}{公理 3}:同一律})\\ &=&x'_1\land(x\lor x'_2)&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&(x'_1\land x)\lor (x'_1\land x'_2)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&0\lor (x'_1\land x'_2)&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&(x\land x'_2)\lor (x'_1\land x'_2)&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&x'_2\land(x\lor x'_1)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&x'_2\land1&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&x'_2&(\because {\rm \href{#boolean_algebra3}{公理 3}:同一律}) \end{aligned} より xx の補元が一意であることは明らか.

べき等律

以下が成り立つ.

  1. xxxx\land x\Leftrightarrow x
  2. xxxx\lor x\Leftrightarrow x

べき等律

束の定理による.

有界律

以下が成り立つ.

  1. x1=1x\lor 1=1
  2. x0=0x\land 0=0

有界律

x1=(x1)1(公理3:同一律)=(x1)(xx)(公理4:補元律)=x(1x)(公理2:分配律)=xx(公理1,公理3:可換律,同一律)=1x0=xxx(公理4:補元律)=xx(定理:べき等律)=0(公理4:補元律)\begin{aligned} x\lor 1&=&(x\lor 1)\land1&(\because {\rm \href{#boolean_algebra3}{公理 3}:同一律})\\ &=&(x\lor 1)(x\lor x')&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&x\lor (1\land x')&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&x\lor x'&(\because {\rm \href{#boolean_algebra1}{公理1}, \href{#boolean_algebra3}{公理3}:可換律, 同一律})\\ &=&1\\ x\land0&=&x\land x\land x'&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&x\land x'&(\because {\rm 定理:\href{#idempotence}{べき等律}})\\ &=&0&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律}) \end{aligned}

吸収律

以下が成り立つ.

xxy=x(xy)=xx\lor x\land y=x\land(x\lor y)=x

吸収律

xxy=(x1)(xy)(公理3:同一律)=x(1y)(公理2:分配律)=x1(公理1:可換律,定理:有界律)=x(公理3:同一律)x(xy)=(x0)(xy)(公理3:同一律)=(0y)x(公理2:分配律)=x0(公理1:可換律,定理:有界律)=x(公理3:同一律)\begin{aligned} x\lor x\land y&=&(x\land1)\lor (x\land y)&(\because {\rm \href{#boolean_algebra3}{公理3}: 同一律})\\ &=&x\land(1\lor y)&(\because {\rm \href{#boolean_algebra2}{公理2}:分配律})\\ &=&x\land1&(\because {\rm \href{#boolean_algebra1}{公理 1}: 可換律, 定理: \href{#bounded}{有界律}} )\\ &=&x&(\because {\rm\href{#boolean_algebra3}{公理 3}: 同一律})\\ x\land(x\lor y)&=&(x\lor 0)(x\lor y)&(\because {\rm \href{#boolean_algebra3}{公理3}: 同一律})\\ &=&(0\land y)\lor x&(\because {\rm \href{#boolean_algebra2}{公理2}: 分配律})\\ &=&x\lor 0&(\because \rm{\href{#boolean_algebra1}{公理1}: 可換律,定理: \href{#bounded}{有界律}})\\ &=&x&(\because \rm{\href{#boolean_algebra3}{公理3}: 同一律}) \end{aligned}

結合律

以下が成り立つ.

x(yz)=(xy)zx\lor(y\lor z)=(x\lor y)\lor z

結合律

A=x(yz),B=(xy)zA=x\lor (y\lor z), B=(x\lor y)\lor z とおく. このとき,

xA=x(x(yz))=x(定理:吸収律)xB=x((xy)z)=x(xy)xz(公理2:分配律)=xxz(定理:吸収律)=x(定理:吸収律)\begin{aligned} x\land A&=&x\land(x\lor (y\lor z))\\ &=&x&(\because {\rm 定理: \href{#absorption}{吸収律}})\\ x\land B&=&x\land((x\lor y)\lor z)\\ &=&x\land(x\lor y)\lor x\land z&(\because {\rm \href{#boolean_algebra2}{公理2}: 分配律})\\ &=&x\lor x\land z&(\because {\rm 定理: \href{#absorption}{吸収律}})\\ &=&x&(\because {\rm 定理: \href{#absorption}{吸収律}}) \end{aligned}

ゆえに xA=xB=x(L1)x\land A=x\land B=x\tag{L1} また,

xA=x(x(yz))=xxx(yz)(公理2:分配律)=x(yz)0(公理1,公理4:可換律,補元律)=x(yz)(公理3:同一律)xB=x((xy)z)=x(xy)xz(公理2:分配律)=(xxxy)xz(公理2:分配律)=(0xy)xz(公理4:補元律)=xyxz(公理3:同一律)=x(yz)(公理2:分配律)\begin{aligned} x'\land A&=&x'\land(x\lor (y\lor z))\\ &=&x'\land x\lor x'\land(y\lor z)&(\because {\rm \href{#boolean_algebra2}{公理2}: 分配律})\\ &=&x'\land(y\lor z)\lor 0&(\because {\rm \href{#boolean_algebra1}{公理1}, \href{#boolean_algebra4}{公理 4}: 可換律, 補元律})\\ &=&x'\land(y\lor z)&(\because {\rm \href{#boolean_algebra3}{公理3}: 同一律})\\ x'\land B&=&x'\land((x\lor y)\lor z)\\ &=&x'\land(x\lor y)\lor x'\land z&(\because {\rm \href{#boolean_algebra2}{公理2}: 分配律})\\ &=&(x'\land x\lor x'\land y)\lor x'\land z&(\because {\rm \href{#boolean_algebra2}{公理2}: 分配律})\\ &=&(0\lor x'\land y)\lor x'\land z&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&x'\land y\lor x'\land z&(\because {\rm \href{#boolean_algebra3}{公理3}: 同一律})\\ &=&x'\land(y\lor z)&(\because {\rm \href{#boolean_algebra2}{公理2}: 分配律}) \end{aligned}

ゆえに xA=xB=x(yz)(L2)x'\land A=x'\land B=x'\land(y\lor z)\tag{L2} 従って,

A=A1(公理3:同一律)=A(xx)(公理4:補元律)=AxAx(公理2:分配律)=xAxA(公理1:可換律)=xBxB(, より)=B(xx)(公理2:分配律)=B1(公理4:補元律)=B(公理3:同一律)\begin{aligned} A&=&A\land1&(\because {\rm \href{#boolean_algebra3}{公理3}: 同一律})\\ &=&A\land(x\lor x')&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&A\land x\lor A\land x'&(\because {\rm \href{#boolean_algebra2}{公理2}: 分配律})\\ &=&x\land A\lor x'\land A&(\because {\rm \href{#boolean_algebra1}{公理1}: 可換律})\\ &=&x\land B\lor x'\land B&(\because,\ {\rm より})\\ &=&B(x\lor x')&(\because {\rm \href{#boolean_algebra2}{公理2}: 分配律})\\ &=&B\land1&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&B&(\because {\rm \href{#boolean_algebra3}{公理3}: 同一律}) \end{aligned}

また, 双対の原理より x(yz)=(xy)zx(y\land z)=(x\land y)\land z.

対合律

以下が成り立つ.

(x)=x(x')'=x

対合律

(x)=(x)0(公理3:同一律)=(x)xx(公理4:補元律)=((x)x)((x)x)(公理2:分配律)=(x(x))1(公理1,公理4:可換律,補元律)=(x(x))(xx)(公理4:補元律)=x((x)x)(公理2:分配律)=x0(公理4:補元律)=x(公理3:同一律)\begin{aligned} (x')'&=&(x')'\lor 0&(\because \rm{\href{#boolean_algebra3}{公理3}: 同一律})\\ &=&(x')'\lor x\land x'&(\because {\href{#boolean_algebra4}{公理 4}:補元律})\\ &=&((x')'\lor x)((x')'\lor x')&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&(x\lor (x')')\land1&(\because {\rm \href{#boolean_algebra1}{公理1}, \href{#boolean_algebra4}{公理 4}:可換律, 補元律})\\ &=&(x\lor (x')')(x\lor x')&(\because {\rm \href{#boolean_algebra4}{公理 4}: 補元律})\\ &=&x\lor ((x')'\land x')&(\because {\rm \href{#boolean_algebra2}{公理2}:分配律})\\ &=&x\lor 0&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&x&(\because {\rm \href{#boolean_algebra3}{公理3}: 同一律}) \end{aligned}

ド・モルガンの法則

以下が成り立つ. (xy)=xy(x\lor y)'=x'\land y'

ド・モルガンの法則

xyx'\land y'(xy)(x\lor y) の補元でなければならない. すなわち, 公理4: 補元律より (xy)(xy)=1(x\lor y)\lor (x'\land y')=1 および (xy)(xy)=0(x\lor y)\land(x'\land y')=0 が同時に成り立つことを示せばよい.

(xy)(xy)=((xy)x)((xy)y)(公理2:分配律)=(y(xx))(x(yy))(公理1:可換律,定理:結合律)=(y1)(x1)(公理4:補元律)=11(定理:有界律)=1(定理:べき等律)(xy)(xy)=(xy)(xy)(公理1:可換律)=((xy)x)((xy)y)(公理2:分配律)=(y(xx))(x(yy))(公理1:可換律,定理:結合律)=(y0)(x1)(公理4:補元律)=00(定理:有界律)=0(定理:べき等律)\begin{aligned} (x\lor y)\lor (x'\land y')&=&((x\lor y)\lor x')((x\lor y)\lor y')&(\because {\rm \href{#boolean_algebra2}{公理2}:分配律})\\ &=&(y\lor (x\lor x'))(x\lor (y\lor y'))&(\because {\rm \href{#boolean_algebra1}{公理1}: 可換律, 定理: \href{#associative}{結合律}})\\ &=&(y\lor 1)(x\lor 1)&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&1\land1&(\because {\rm 定理: \href{#bounded}{有界律}} )\\ &=&1&(\because {\rm 定理:\href{#idempotence}{べき等律}})\\ (x\lor y)\land(x'\land y')&=&(x'\land y')\land(x\lor y)&(\because {\rm \href{#boolean_algebra1}{公理1}: 可換律})\\ &=&((x'\land y')\land x)\lor ((x'\land y')\land y)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&(y'\land(x\land x'))\lor (x'\land(y\land y'))&(\because {\rm \href{#boolean_algebra1}{公理1}: 可換律, 定理: \href{#associative}{結合律}})\\ &=&(y'\lor 0)\lor (x'\land1)&(\because {\rm \href{#boolean_algebra4}{公理 4}: 補元律})\\ &=&0\lor 0&(\because {\rm 定理: \href{#bounded}{有界律}} )\\ &=&0&(\because {\rm 定理:\href{#idempotence}{べき等律}}) \end{aligned}

また, 双対の原理より (xy)=xy(x\land y)'=x'\lor y'.

シャノン展開

任意の nn 変数ブール関数 f(x1,x2,,xn)f(x_1,x_2,\cdots,x_n)x1x_1 について, 次のように展開できる.

f(x1,x2,,xn)=(x1x1)f(x1,x2,,xn)(公理4,公理3:補元律,同一律)=x1f(x1,x2,,xn)x1f(x1,x2,,xn)(公理2:分配律)=x1f(0,x2,,xn)x1f(1,x2,,xn)(以下に証明)\begin{aligned} f(x_1,x_2,\cdots,x_n)&=&(x'_1\lor x_1)\land f(x_1,x_2,\cdots,x_n)&(\because {\rm \href{#boolean_algebra4}{公理 4}, \href{#boolean_algebra3}{公理 3} :補元律, 同一律})\\ &=&x'_1\land f(x_1,x_2,\cdots,x_n)\lor x_1\land f(x_1,x_2,\cdots,x_n)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&x'_1\land f(0,x_2,\cdots,x_n)\lor x_1\land f(1,x_2,\cdots,x_n)&(\because \href{#chanon_theorem_proof}{以下に証明}) \end{aligned}

シャノン展開

x1=0x_1=0 のとき, f(0,x2,,xn)=1f(0,x2,,xn)0f(1,x2,,xn)=f(0,x2,,xn)f(0,x_2,\cdots,x_n)=1\land f(0,x_2,\cdots,x_n)\lor 0\land f(1,x_2,\cdots,x_n)=f(0,x_2,\cdots,x_n) x1=1x_1=1 のとき, f(1,x2,,xn)=0f(0,x2,,xn)1f(1,x2,,xn)=f(1,x2,,xn)f(1,x_2,\cdots,x_n)=0\land f(0,x_2,\cdots,x_n)\lor 1\land f(1,x_2,\cdots,x_n)=f(1,x_2,\cdots,x_n)

例として, f(x1,x2,x3)=x1x2x2x3x1x3f(x_1,x_2,x_3)=x_1\land x_2\lor x_2\land x_3\lor x_1\land x_3x1x_1 について展開すると,

f(x1,x2,x3)=x1x2x2x3x1x3=(x1x1)f(x1,x2,x3)(公理4,公理3:補元律,同一律)=x1f(x1,x2,x3)x1f(x1,x2,x3)(公理2:分配律)=x1f(0,x2,x3)x1f(1,x2,x3)(定理:シャノンの展開定理)=x1x2x3x1x2x2x3x3(公理3:同一律)=x1x2x3x1x2x3(公理1:可換律,定理:吸収律)\begin{aligned} f(x_1,x_2,x_3)&=&x_1\land x_2\lor x_2\land x_3\lor x_1\land x_3\\ &=&(x'_1\lor x_1)\land f(x_1,x_2,x_3)&(\because {\rm \href{#boolean_algebra4}{公理 4}, \href{#boolean_algebra3}{公理 3} :補元律, 同一律})\\ &=&x'_1\land f(x_1,x_2,x_3)\lor x_1\land f(x_1,x_2,x_3)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&x'_1\land f(0,x_2,x_3)\lor x_1\land f(1,x_2,x_3)&(\because {\rm 定理: \href{#chanon_theorem}{シャノンの展開定理}})\\ &=&x'_1\land x_2\land x_3\lor x_1\land x_2\lor x_2\land x_3\lor x_3&(\because {\rm \href{#boolean_algebra3}{公理 3}:同一律})\\ &=&x'_1\land x_2\land x_3\lor x_1\land x_2\lor x_3&(\because {\rm \href{#boolean_algebra1}{公理1}: 可換律, 定理: \href{#absorption}{吸収律}})\\ \end{aligned}

となる. また双対の原理より,

f(x1,x2,,xn)=(x1x1)f(x1,x2,,xn)(公理4,公理3:補元律,同一律)=(x1f(x1,x2,,xn))(x1f(x1,x2,,xn))(公理2:分配律)=(x1f(0,x2,,xn))(x1f(1,x2,,xn))(上記証明の双対)\begin{aligned} f(x_1,x_2,\cdots,x_n)&=&(x_1\land x'_1)\lor f(x_1,x_2,\cdots,x_n)&(\because {\rm \href{#boolean_algebra4}{公理 4}, \href{#boolean_algebra3}{公理 3} :補元律, 同一律})\\ &=&(x_1\lor f(x_1,x_2,\cdots,x_n))\land(x'_1\lor f(x_1,x_2,\cdots,x_n))&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&(x_1\lor f(0,x_2,\cdots,x_n))\land(x'_1\lor f(1,x_2,\cdots,x_n))&(\because {\rm \href{#chanon_theorem_proof}{上記証明}の\href{#dual_def}{双対}}) \end{aligned}

この展開をシャノン双対展開という.

標準形

異なる表現のなされたブール式が同値であるかを即座に断定することは, 一般的に困難であることが多い2. ここで, ブール式を一意に表す方法が決まっていれば, 即座に同値であるか判断がしやすく, 便利である. ブール代数では主に 2 つの形式が決められており, その形式への変形を標準化, また正規化という. 以下, nn 変数ブール関数 f(x1,x2,,xn)f(x_1,x_2,\cdots,x_n) において, x1,x2,,xnx_1,x_2,\cdots,x_n を入力変数, また入力変数およびその否定をリテラルという. さらに nn 個の入力変数に対し, kk 番目のリテラル xkek (1kn)x_k^{e_k}\ (1\leq k\leq n) を次のように表す.

xkek={xk(=xk1)ek=1 のときxk(=xk0)ek=0 のとき\begin{aligned} x^{e_k}_k=\begin{cases} x_k&(=x^1_k)&e_k=1{\rm\ のとき}\\ x'_k&(=x^0_k)&e_k=0{\rm\ のとき} \end{cases} \end{aligned}

加法標準形, 主加法標準形

f(x1,x2,,xn)f(x_1,x_2,\cdots,x_n)x1,x2x_1,x_2 についてシャノン展開すると,

f(x1,x2,,xn)=x1x2f(0,0,,xn)x1x2f(0,1,,xn)x1x2f(1,0,,xn)x1x2f(1,1,,xn)\begin{aligned} f(x_1,x_2,\cdots,x_n)&=&x'_1\land x'_2\land f(0,0,\cdots,x_n)\\ &&\lor x'_1\land x_2\land f(0,1,\cdots,x_n)\\ &&\lor x_1\land x'_2\land f(1,0,\cdots,x_n)\\ &&\lor x_1\land x_2\land f(1,1,\cdots,x_n) \end{aligned}

となる. 従って, 全入力変数 x1,x2,,xnx_1,x_2,\cdots,x_n についてシャノン展開すると,

f(x1,x2,,xn)=x1x2xnf(0,0,,0)x1x2xnf(0,0,,1)x1x2xnf(1,1,,0)x1x2xnf(1,1,,1)\begin{aligned} f(x_1,x_2,\cdots,x_n)&=&x'_1\land x'_2\land\cdots\land x'_n\land f(0,0,\cdots,0)\\ &&\lor x'_1\land x'_2\land\cdots\land x_n\land f(0,0,\cdots, 1)\\ &&\lor\cdots\\ &&\lor x_1\land x_2\land\cdots\land x'_n\land f(1,1,\cdots,0)\\ &&\lor x_1\land x_2\land\cdots\land x_n\land f(1,1,\cdots,1) \end{aligned}

となる (シャノンの定理より数学的帰納法により証明できるが, 省略). これを以下のように定義する.

最小項展開

nn 変数ブール関数 f(x1,x2,,xn)f(x_1,x_2,\cdots,x_n) のすべての入力変数 x1,x2,,xnx_1,x_2,\cdots,x_n について, シャノン展開した形式 f(x1,x2,,xn)=(e1,e2,,en)Bnf(e1,e2,,en)i=1nxiei(1)f(x_1,x_2,\cdots,x_n)= \bigvee_{(e_1,e_2,\cdots,e_n)\in B^n}f(e_1,e_2,\cdots,e_n)\land\bigwedge_{i=1}^{n}x_i^{e_i}\tag{1}f(x1,x2,,xn)f(x_1,x_2,\cdots,x_n) の最小項展開である. なお, このときの項数は 2n2^n となる.

これを踏まえ, 加法標準形および主加法標準形を導入する.

加法標準形, 主加法標準形

  • 加法標準形 (disjunctive normal form: DNF) は, ブール式のリテラル, または 2 つ以上のリテラルの積の和のことをいう. ここで, 2 つ以上のリテラルの積で同じ入力変数を 2 度以上含まない論理式を基本積, また標準項という. 基本積のうち, すべての入力変数を含むブール式を最小項という. すなわち, 上記最小項展開i=1nxiei\displaystyle\bigwedge_{i=1}^nx^{e_i}_i は最小項である.
  • 主加法標準形 (principal disjunctive normal form: PDNF) は, ブール関数を最小項展開した形式, すなわち最小項展開の形式である.

例えば, 否定論理積 \mid を PDNF で表すとしよう. 否定論理和は 2 項演算子なので, その PDNF は 2 変数ブール関数を最小項展開した形となる.

f(x1,x2)=f(0,0)x1x2f(0,1)x1x2f(1,0)x1x2f(1,1)x1x2f(x_1,x_2)=f(0,0)\land x'_1\land x'_2\lor f(0,1)x'_1\land x_2\lor f(1,0)\land x_1\land x'_2\lor f(1,1)\land x_1\land x_2

便宜上, 2 項演算子 \mid を最小項展開した形を f(x1,x2)f_\mid(x_1,x_2) で表すこととする. あとは真理値表 2\mid の列のとおりに f(x1,x2)f_\mid(x_1,x_2) の値を決めてやればよいので

f(x1,x2)=1x1x21x1x21x1x20x1x2=x1x2x1x2x1x2 \begin{aligned} f_\mid(x_1,x_2)&=&1\land x'_1\land x'_2\lor 1\land x'_1\land x_2\lor 1\land x_1\land x'_2\lor 0\land x_1\land x_2\\ &=&x'_1\land x'_2\lor x'_1\land x_2\lor x_1\land x'_2 \end{aligned}

従って, 否定論理積の PDNF は x1x2x1x2x1x2x'_1\land x'_2\lor x'_1\land x_2\lor x_1\land x'_2 となる. この操作を振り返ると, 真理値表から PDNF を書くためには, 結果が 11 となっている入力変数の全パターンに対して, 元の入力変数の値が 11 ならそのまま, 00 ならその補元をとり, それらすべての和を取ればよいことがわかる. 何故ならば, 結果が 00 となる部分は, シャノンの展開定理の証明でも示したように消えてしまうからである. 同じようにして, 否定論理和, 排他的論理和も真理値表 2,\downarrow,\oplus の列をみると, 11 となる入力のパターンから

f(x1,x2)=x1x2f(x1,x2)=x1x2x1x2 \begin{aligned} f_{\downarrow}(x_1,x_2)&=&x'_1\land x'_2\\ f_{\oplus}(x_1,x_2)&=&x_1\land x'_2\lor x'_1\land x_2\\ \end{aligned}

となる. すなわち, 真理値表で表現できるブール式は PDNF で表せるということである3.

次に, 任意の論理式から PDNF に変換することを考える. 結論からいうと, 次の手順に従えば PDNF へ機械的に変換できることが知られている.

  1. ブール式全体を基本項による積の和の形にする (分配律等を利用)
  2. 最小項でない基本項に対し, その基本項に含まれないすべてのリテラル xix_i について (xixi)(x_i\land x'_i) を乗ずる
  3. 分配律等に従い展開して, 冗長な項を除去する

以下, PDNF で表されたブール式を f(x1,x2,,xn)PDNFf(x_1,x_2,\cdots,x_n)_{\rm P D N F} と書くこととする. 例えば, ブール式 f(x1,x2)=x1x2x1x2f(x_1,x_2)=x_1\land x_2\land x_1\lor x_2 を PDNF で表すとすると,

f(x1,x2)=x1x2x1x2=x1x1x2x2(公理1:可換律)=x1x2x2(定理:べき等律)=x1x21x2(公理3:同一律)=x1x2(x1x1)x2(公理4:補元律)=x1x2x1x2x1x2(公理2:分配律)=x1x2x1x2(定理:べき等律) \begin{aligned} f(x_1,x_2)&=&x_1\land x_2\land x_1\lor x_2\\ &=&x_1\land x_1\land x_2\lor x_2&(\because {\rm\href{#boolean_algebra1}{公理1}: 可換律})\\ &=&x_1\land x_2\lor x_2&(\because {\rm 定理:\href{#idempotence}{べき等律}})\\ &=&x_1\land x_2\lor 1\land x_2&(\because {\rm \href{#boolean_algebra3}{公理 3}:同一律})\\ &=&x_1\land x_2\lor (x_1\lor x_1')\land x_2&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&x_1\land x_2\lor x_1\land x_2\lor x_1'\land x_2&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&x_1\land x_2\lor x_1'\land x_2&(\because {\rm 定理:\href{#idempotence}{べき等律}}) \end{aligned}

従って f(x1,x2)PDNF=x1x2x1x2f(x_1,x_2)_{\rm P D N F}=x_1\land x_2\lor x_1'\land x_2 となる. 例としてもう 1 つ, f(x1,x2,x3)=x1x2x3x1x3x2x3f(x_1,x_2,x_3)=x_1\land x_2'\land x_3\lor x_1\land x'_3\lor x_2\land x'_3 としたときの PDNF は

f(x1,x2,x3)=x1x2x3xx3x2x3=x1x2x3x1(x2x2)x3(x1x1)x2x3(公理3,公理4:同一律,補元律)=x1x2x3x1x2x3x1x2x3x1x2x3x1x2x3(公理2:分配律)=x1x2x3x1x2x3x1x2x3x1x2x3(定理:べき等律) \begin{aligned} f(x_1,x_2,x_3)&=&x_1\land x'_2\land x_3\lor x\land x'_3\lor x_2\land x'_3\\ &=&x_1\land x'_2\land x_3\lor x_1\land(x_2\lor x'_2)\land x'_3\lor (x_1\lor x_1')\land x_2\land x'_3&(\because {\rm \href{#boolean_algebra3}{公理 3}, \href{#boolean_algebra4}{公理 4}: 同一律, 補元律} )\\ &=&x_1\land x'_2\land x_3\lor x_1\land x_2\land x'_3\lor x_1\land x'_2\land x'_3\lor x_1\land x_2\land x'_3\lor x'_1\land x_2\land x'_3&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&x_1\land x'_2\land x_3\lor x_1\land x_2\land x'_3\lor x_1\land x'_2\land x'_3\lor x'_1\land x_2\land x'_3&(\because {\rm 定理: \href{#idempotence}{べき等律}}) \end{aligned}

従って f(x1,x2,x3)PDNF=x1x2x3x1x2x3x1x2x3x1x2x3f(x_1,x_2,x_3)_{\rm P D N F}=x_1\land x'_2\land x_3\lor x_1\land x_2\land x'_3\lor x_1\land x'_2\land x'_3\lor x'_1\land x_2\land x'_3 となる.

乗法標準形, 主乗法標準形

f(x1,x2,,xn)f(x_1,x_2,\cdots,x_n)x1,x2x_1,x_2 についてシャノン双対展開すると,

f(x1,x2,,xn)=(x1x2f(0,0,,xn))(x1x2f(0,1,,xn))(x1x2f(1,0,,xn))(x1x2f(1,1,,xn)) \begin{aligned} f(x_1,x_2,\cdots,x_n)&=&(x_1\lor x_2\lor f(0,0,\cdots,x_n))\\ &&\land (x_1\lor x'_2\lor f(0,1,\cdots,x_n))\\ &&\land (x'_1\lor x_2\lor f(1,0,\cdots,x_n))\\ &&\land (x'_1\lor x'_2\lor f(1,1,\cdots,x_n)) \end{aligned}

となる. 従って, 全入力変数 x1,x2,,xnx_1,x_2,\cdots,x_n についてシャノン双対展開すると,

f(x1,x2,,xn)=(x1x2xnf(0,0,,0))(x1x2xnf(1,0,,0))(x1x2xnf(1,1,,0))(x1x2xnf(1,1,,1)) \begin{aligned} f(x_1,x_2,\cdots,x_n)&=&(x_1\lor x_2\lor\cdots\lor x_n\lor f(0,0,\cdots,0))\\ &&\land(x_1\lor x_2\lor\cdots\lor x'_n\lor f(1,0,\cdots,0))\\ &&\land\cdots\\ &&\land(x'_1\lor x'_2\lor\cdots x_n\lor f(1,1,\cdots,0))\\ &&\land(x'_1\lor x'_2\lor\cdots x'_n\lor f(1,1,\cdots,1)) \end{aligned}

となる (シャノンの定理より数学的帰納法により証明できるが, 省略). これを以下のように定義する.

最大項展開

nn 変数ブール関数 f(x1,x2,,xn)f(x_1,x_2,\cdots,x_n) のすべての入力変数 x1,x2,,xnx_1,x_2,\cdots,x_n について, シャノン双対展開した形式 f(x1,x2,,xn)=(e1,e2,,en)Bn(f(e1,e2,,en)i=1nxiei)(2)f(x_1,x_2,\cdots,x_n)= \bigwedge_{(e_1,e_2,\cdots,e_n)\in B^n}(f(e_1,e_2,\cdots,e_n)\lor\bigvee_{i=1}^{n}x_i^{e'_i})\tag{2}f(x1,x2,,xn)f(x_1,x_2,\cdots,x_n) の最大項展開である. なお, このときの項数は 2n2^n となる.

これを踏まえ, 乗法標準形, 主乗法標準形を導入する.

乗法標準形, 主乗法標準形

  • 乗法標準形 (CNF: conjunctive normal form) は, ブール式のリテラル, または 2 つ以上のリテラルの和の積のことをいう. ここで, 2 つ以上のリテラルの和で同じ入力変数を 2 度以上含まないブール式を基本和, また標準項という. 基本和のうち, すべての入力変数を含むブール式を最大項という. すなわち, 上記最大項展開i=1nxiei\displaystyle\bigvee_{i=1}^{n}x_i^{e'_i} は最大項である.
  • 主乗法標準形 (principal conjunctive normal form: PCNF) は, ブール関数を最大項展開した形式, すなわち最大項展開の形式である.

例えば, 否定論理積 \mid を PCNF で表すとしよう. 否定論理積は 2 項演算子なので, その PCNF は 2 変数ブール関数を最大項展開した形となる.

f(x1,x2)=(x1x2f(0,0))(x1x2f(0,1))(x1x2f(1,0))(x1x2f(1,1)) f(x_1,x_2)= (x_1\lor x_2\lor f(0,0))\land (x_1\lor x'_2\lor f(0,1))\land(x'_1\lor x_2\lor f(1,0))\land(x'_1\lor x'_2\lor f(1,1))

2 項演算子 \mid を最大項展開した式 f(x1,x2)f_{\mid}(x_1,x_2) は, 真理値表 2\mid の列のとおりに f(x1,x2)f_{\mid}(x_1,x_2) の値を決めてやればよいので

f(x1,x2)=(x1x21)(x1x21)(x1x21)(x1x20)=x1x2 \begin{aligned} f_{\mid}(x_1,x_2)&=&(x_1\lor x_2\lor 1)\land (x_1\lor x'_2\lor 1)\land(x'_1\lor x_2\lor 1)\land(x'_1\lor x'_2\lor 0)\\ &=&x'_1\lor x'_2 \end{aligned}

従って, 否定論理積の PCNF は x1x2x'_1\lor x'_2 となる. この操作を振り返ると, 真理値表から PCNF を書くためには, 結果が 00 となっている入力変数の全パターンに対して, 元の入力変数の値が 11 なら補元をとり, 00 ならそのままで和を取り, それらすべての積を取ればよいことがわかる. 何故ならば, 結果が 11 となる部分は, 和の性質, すなわち公理 2: 同一律より消えてしまうからである. 同じようにして, 否定論理和, 排他的論理和も真理値表 2,\downarrow,\oplus の列をみると, 00 となる入力のパターンから

f(x1,x2)=(x1x2)(x1x2)(x1x2)f(x1,x2)=(x1x2)(x1y1) \begin{aligned} f_{\downarrow}(x_1,x_2)&=&(x'_1\lor x'_2)\land(x'_1\lor x_2)\land(x_1\lor x'_2)\\ f_{\oplus}(x_1,x_2)&=&(x'_1\lor x'_2)\land(x_1\lor y_1) \end{aligned}

となる. すなわち, 真理値表で表現できるブール式は, PCNF で表せるということである5. 次に, 任意の論理式から PCNF に変換することを考える. 結論からいうと, 次の手順に従えば PCNF へ機械的に変換できることが知られている.

  1. ブール式全体を基本項による和の積の形にする (分配律等を利用)
  2. 最大項でない基本項に対し, その基本項に含まれないすべてのリテラル xix_i について xixix_i\land x'_i を乗ずる
  3. 分配律等に従い展開して, 冗長な項を除去する

以下, PCNF で表されたブール式を f(x1,x2,,xn)PCNFf(x_1,x_2,\cdots,x_n)_{\rm P C N F} と書くこととする. 例えば, ブール式 f(x1,x2,x3)=x1(x2x3)f(x_1,x_2,x_3)=x_1\land(x'_2\land x_3)' を PCNF で表すとすると,

f(x1,x2,x3)=x1(x2x3)=x1(x2x3)(定理:ド・モルガンの法則)=(x1x2x2)(x2x3)(公理3:同一律)=(x1x2)(x1x2)(x2x3)(公理2:分配律)=(x1x2x3x3)(x1x2x3x3)(x1x1x2x3)(公理3:同一律)=(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(公理2:分配律)=(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(定理:べき等律) \begin{aligned} f(x_1,x_2,x_3)&=&x_1\land(x'_2\land x_3)'\\ &=&x_1\land(x_2\lor x'_3)&(\because {\rm 定理: \href{#de_morgan}{ド・モルガンの法則}})\\ &=&(x_1\lor x_2\land x'_2)\land(x_2\lor x'_3)&(\because {\rm \href{#boolean_algebra3}{公理 3}:同一律})\\ &=&(x_1\lor x_2)\land(x_1\lor x'_2)\land(x_2\lor x'_3)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&(x_1\lor x_2\lor x_3\land x'_3)\land(x_1\lor x'_2\lor x_3\land x'_3)\land(x_1\land x'_1\lor x_2\land x'_3)&(\because {\rm \href{#boolean_algebra3}{公理 3}:同一律})\\ &=&(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor x'_3)\land(x_1\lor x'_2\lor x_3)\\ &&\land(x_1\lor x'_2\lor x'_3)\land(x_1\lor x_2\lor x'_3)\land(x'_1\lor x_2\lor x'_3)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor x'_3)\land(x_1\lor x'_2\lor x_3)\\ &&\land(x_1\lor x'_2\lor x'_3)\land(x'_1\lor x_2\lor x'_3)&(\because {\rm 定理:\href{#idempotence}{べき等律}}) \end{aligned}

従って f(x1,x2,x3)PCNF=(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)f(x_1,x_2,x_3)_{\rm P C N F}=(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor x'_3)\land(x_1\lor x'_2\lor x_3)\land(x_1\lor x'_2\lor x'_3)\land(x'_1\lor x_2\lor x'_3)

となる. 例としてもう 1 つ, f(x1,x2,x3)=x1x2x2x3f(x_1,x_2,x_3)=x_1\land x'_2\lor x_2\land x_3 としたときの PCNF は

f(x1,x2,x3)=x1x2x2x3=(x1x2x2)(x1x2x3)(公理2:分配律)=(x1x2)(x1x3)(x2x3)(公理4:補元律)=(x1x2x3x3)(x1x2x2x3)(x1x1x2x3)(公理4:補元律)=(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(公理2:分配律) \begin{aligned} f(x_1,x_2,x_3)&=&x_1\land x'_2\lor x_2\land x_3\\ &=&(x_1\land x'_2\lor x_2)\land(x_1\land x'_2\lor x_3)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律})\\ &=&(x_1\lor x_2)\land(x_1\lor x_3)\land(x'_2\lor x_3)&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&(x_1\lor x_2\lor x_3\land x'_3)\land(x_1\lor x_2\land x'_2\lor x_3)\land(x_1\land x'_1\lor x'_2\lor x_3)&(\because {\rm \href{#boolean_algebra4}{公理 4}:補元律})\\ &=&(x_1\lor x_2\lor x_3)\land(x_1\lor x_2\lor x'_3)\land(x_1\lor x'_2\lor x_3)\land(x'_1\lor x'_2\lor x_3)&(\because {\rm \href{#boolean_algebra2}{公理 2}:分配律}) \end{aligned}