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

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

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

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

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

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

例として, $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$ について展開すると,

$$\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}$$

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

$$\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 つの形式が決められており, その形式への変形を標準化, また正規化という. 以下, $n$ 変数ブール関数 $f(x_1,x_2,\cdots,x_n)$ において, $x_1,x_2,\cdots,x_n$ を入力変数, また入力変数およびその否定をリテラルという. さらに $n$ 個の入力変数に対し, $k$ 番目のリテラル $x_k^{e_k}\ (1\leq k\leq n)$ を次のように表す.

$$\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(x_1,x_2,\cdots,x_n)$ を $x_1,x_2$ についてシャノン展開すると,

$$\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}$$

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

$$\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}$$

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

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

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

$$f(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_\mid(x_1,x_2)$ で表すこととする. あとは真理値表 2 の $\mid$ の列のとおりに $f_\mid(x_1,x_2)$ の値を決めてやればよいので

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

$$\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 で表せるということである³.

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

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

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

$$\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(x_1,x_2)_{\rm P D N F}=x_1\land x_2\lor x_1'\land x_2$$ となる. 例としてもう 1 つ, $f(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 は

$$\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(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(x_1,x_2,\cdots,x_n)$ を $x_1,x_2$ についてシャノン双対展開すると,

$$\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}$$

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

$$\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}$$

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

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

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

$$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_{\mid}(x_1,x_2)$ は, 真理値表 2 の $\mid$ の列のとおりに $f_{\mid}(x_1,x_2)$ の値を決めてやればよいので

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

$$\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 で表せるということである⁵. 次に, 任意の論理式から PCNF に変換することを考える. 結論からいうと, 次の手順に従えば PCNF へ機械的に変換できることが知られている.

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

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

$$\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}$$