情報理論 - 主乗法標準形

概要

主乗法標準形 (PCNF: Principal Conjunctive Normal Form) は、論理関数を最大項 (maxterm) の論理積として一意に表現する標準形である。
POS canonical form (Product of Sums) とも呼ばれ、Π記法 $\prod M (\dots)$ を用いて表記する。

任意のブール関数は一意の主乗法標準形を持ち、論理回路の設計や検証において重要な役割を担う。

主な応用領域を以下に示す。

デジタル論理回路の設計
論理式の等価性判定
論理式の簡単化 (カルノー図、クワイン・マクラスキー法)
ブール関数の解析

下表に、主乗法標準形の特徴を示す。

主乗法標準形の特徴
項目	内容
正式名称	主乗法標準形 (Principal Conjunctive Normal Form)
略称	PCNF
別名	POS canonical form (Product of Sums)
構成要素	最大項 (maxterm)
結合演算	論理積 (AND, ・)
記号表記	$\prod M (\dots)$
真理値表から	f = 0 の行を使用
展開に利用	$x + \overline{x} = 1$
簡単化手法	カルノー図、クワイン・マクラスキー法

対となる標準形として、情報理論 - 主加法標準形が存在し、最小項の論理和で関数を表現する。

基本用語

リテラル

論理変数またはその否定のことをリテラルという。

肯定リテラル
変数そのもの

例: $A$
否定リテラル
変数の否定

例: $\overline{A}$

n個の変数があるとき、リテラルは合計 $2 n$ 個存在する。

基本和

リテラルの論理和 (OR結合) を基本和という。和項とも呼ぶ。

例: $A + \overline{B} + C$

最大項 (maxterm)

n個の変数が全て1回ずつ現れる基本和を最大項という。記号 $M_{i}$ で表す。

命名ルールは最小項と逆であり、以下の規則に従う。

変数の値が0の場合 → 肯定リテラルとして含める
変数の値が1の場合 → 否定リテラルとして含める

例: A=0, B=1, C=0 のとき、10進数で 2 (010) となる。
このとき最大項は $M_{2} = A + \overline{B} + C$ である。

最大項の重要な性質として、対応する入力の組み合わせのときのみ値が0となり、その他の全ての入力では値が1となる。

最小項と最大項の補数関係

最小項 $m_{i}$ と最大項 $M_{i}$ の間には以下の補数関係が成立する。

$m_{i} = \overline{M_{i}}$

ド・モルガンの定理による導出例を以下に示す。( $m_{2}$ と $M_{2}$ の場合)

最小項 $m_{2}$ の定義
$m_{2} = \overline{A} \cdot B \cdot \overline{C}$
ド・モルガンの定理を適用
$\overline{m_{2}} = \overline{\overline{A} \cdot B \cdot \overline{C}} = A + \overline{B} + C$
最大項 $M_{2}$ との一致を確認
$M_{2} = A + \overline{B} + C$
結論
したがって $m_{2} = \overline{M_{2}}$ が成立する。

最大項の一覧

3変数 (A, B, C) の最大項8個を以下の表に示す。

3変数の最大項一覧
A	B	C	最大項	記号
0	0	0	$A + B + C$	$M_{0}$
0	0	1	$A + B + \overline{C}$	$M_{1}$
0	1	0	$A + \overline{B} + C$	$M_{2}$
0	1	1	$A + \overline{B} + \overline{C}$	$M_{3}$
1	0	0	$\overline{A} + B + C$	$M_{4}$
1	0	1	$\overline{A} + B + \overline{C}$	$M_{5}$
1	1	0	$\overline{A} + \overline{B} + C$	$M_{6}$
1	1	1	$\overline{A} + \overline{B} + \overline{C}$	$M_{7}$

主乗法標準形の定義

論理関数 $f$ の主乗法標準形とは、 $f$ の値が0となる全ての入力の組み合わせに対応する最大項の論理積として表した形式である。

一般式を以下に示す。

$f (x_{1}, x_{2}, \dots, x_{n}) = \prod M (j_{1}, j_{2}, \dots, j_{l})$

ここで $j_{1}, j_{2}, \dots, j_{l}$ は、 $f$ の値が0となる入力の組み合わせに対応する10進番号である。

任意のブール関数は一意の主乗法標準形を持つ。
これは、真理値表から関数の値が0となる行が一意に決まるためである。

真理値表からの導出

導出手順

真理値表から主乗法標準形を導出する手順を以下に示す。

真理値表から、関数の値が0となる行を全て特定する。
各行に対応する最大項を書き出す。(値が0の変数は肯定リテラル、値が1の変数は否定リテラル)
全ての最大項の論理積 (AND) を取る。
最大項番号のリスト表記 (Π記法) に変換する。

具体例

真理値表から主乗法標準形を導出する。

真理値表
A	B	C	f(A,B,C)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

導出過程を以下に示す。

f = 0 となる行の特定
入力 000 (行0), 011 (行3), 101 (行5), 110 (行6) の4行
対応する最大項
$M_{0} = A + B + C$ , $M_{3} = A + \overline{B} + \overline{C}$ , $M_{5} = \overline{A} + B + \overline{C}$ , $M_{6} = \overline{A} + \overline{B} + C$
主乗法標準形
$f = (A + B + C) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C}) \cdot (\overline{A} + \overline{B} + C)$
Π記法
$f = \prod M (0, 3, 5, 6)$

論理式からの導出

一般の論理式から主乗法標準形を導出するには、 $x + \overline{x} = 1$ および $x \cdot \overline{x} = 0$ を利用した展開を行う。

手順を以下に示す。

論理式を和積形に展開する。(分配法則を適用)
各因子に含まれない変数 $x$ について、 $(x + \overline{x})$ を因子にOR演算で加える。( $x + \overline{x} = 1$ なので値は変わらない)
分配法則で展開し、全ての因子を最大項の形にする。
重複する最大項を除去する。( $M_{i} \cdot M_{i} = M_{i}$ )

具体例として $f = A \cdot B + \overline{A} \cdot C$ を主乗法標準形に変換する。

和積形への変換
分配法則 $x \cdot y + z = (x + z) \cdot (y + z)$ を使用する。

$f = A \cdot B + \overline{A} \cdot C = (A + \overline{A} \cdot C) \cdot (B + \overline{A} \cdot C)$

さらに展開すると、 $f = (A + \overline{A}) (A + C) (\overline{A} + B) (B + C)$

$(A + \overline{A}) = 1$ なので $f = (A + C) \cdot (\overline{A} + B) \cdot (B + C)$
第1因子 $(A + C)$ の変換
B が含まれないため、 $(A + B + C) \cdot (A + \overline{B} + C)$ に展開する。

10進番号 0 (000), 2 (010) に対応し、 $M_{0} \cdot M_{2}$
第2因子 $(\overline{A} + B)$ の変換
C が含まれないため、 $(\overline{A} + B + C) \cdot (\overline{A} + B + \overline{C})$ に展開する。

10進番号 4 (100), 5 (101) に対応し、 $M_{4} \cdot M_{5}$
第3因子 $(B + C)$ の変換
Aが含まれないため、 $(A + B + C) \cdot (\overline{A} + B + C)$ に展開する。

10進番号 0 (000), 4 (100) に対応し、 $M_{0} \cdot M_{4}$
重複を除去した結果
$f = M_{0} \cdot M_{2} \cdot M_{4} \cdot M_{5} = \prod M (0, 2, 4, 5)$

論理式の簡単化に用いる変換法則

ブール代数の論理式を簡単化する際に使用される主要な変換法則を以下に示す。
これらの法則は、主乗法標準形から得られた論理式を、より簡潔な等価式に変換するために用いられる。

ブール代数には双対性原理 (Duality Principle) が成立する。
AND演算とOR演算、および定数0と定数1を互いに交換することで、ある法則からその双対の法則が導出される。

基本法則

下表に、各法則をAND形式とOR形式の双対の組を示す。

ブール代数の基本法則
法則名	AND形式	OR形式
恒等法則 (Identity Law)	$A \cdot 1 = A$	$A + 0 = A$
支配法則 (Domination Law)	$A \cdot 0 = 0$	$A + 1 = 1$
冪等法則 (Idempotent Law)	$A \cdot A = A$	$A + A = A$
補元法則 (Complement Law)	$A \cdot \overline{A} = 0$	$A + \overline{A} = 1$
二重否定法則 (Involution Law)	$\overline{\overline{A}} = A$

構造法則

ブール代数の構造法則
法則名	AND形式	OR形式
交換法則 (Commutative Law)	$A \cdot B = B \cdot A$	$A + B = B + A$
結合法則 (Associative Law)	$(A \cdot B) \cdot C = A \cdot (B \cdot C)$	$(A + B) + C = A + (B + C)$
分配法則 (Distributive Law)	$A \cdot (B + C) = A \cdot B + A \cdot C$	$A + B \cdot C = (A + B) \cdot (A + C)$

簡単化法則

ブール代数の簡単化法則
法則名	AND形式	OR形式
吸収法則 (Absorption Law)	$A \cdot (A + B) = A$	$A + A \cdot B = A$
ド・モルガンの法則 (De Morgan's Law)	$\overline{A \cdot B} = \overline{A} + \overline{B}$	$\overline{A + B} = \overline{A} \cdot \overline{B}$
コンセンサス定理 (Consensus Theorem)	$(A + B) \cdot (\overline{A} + C) \cdot (B + C) = (A + B) \cdot (\overline{A} + C)$	$A \cdot B + \overline{A} \cdot C + B \cdot C = A \cdot B + \overline{A} \cdot C$

吸収法則の証明

吸収法則 $A \cdot (A + B) = A$ の成立を以下のように証明できる。

$\begin{aligned} A \cdot (A + B) & = A \cdot A + A \cdot B & (分配法則) \\ = A + A \cdot B & (冪等法則: A \cdot A = A) \\ = A \cdot 1 + A \cdot B & (恒等法則: A = A \cdot 1) \\ = A \cdot (1 + B) & (分配法則) \\ = A \cdot 1 & (支配法則: 1 + B = 1) \\ = A & (恒等法則) \end{aligned}$

コンセンサス定理の証明

コンセンサス定理 $(A + B) \cdot (\overline{A} + C) \cdot (B + C) = (A + B) \cdot (\overline{A} + C)$ の成立を以下のように証明できる。

第3因子 $(B + C)$ が冗長であることを示す。
双対の定理 $A \cdot B + \overline{A} \cdot C + B \cdot C = A \cdot B + \overline{A} \cdot C$ を証明し、双対性原理により成立を確認する。

$\begin{aligned} A \cdot B + \overline{A} \cdot C + B \cdot C & = A \cdot B + \overline{A} \cdot C + B \cdot C \cdot (A + \overline{A}) & (補元法則: A + \overline{A} = 1) \\ = A \cdot B + \overline{A} \cdot C + A \cdot B \cdot C + \overline{A} \cdot B \cdot C & (分配法則) \\ = A \cdot B \cdot (1 + C) + \overline{A} \cdot C \cdot (1 + B) & (分配法則) \\ = A \cdot B + \overline{A} \cdot C & (支配法則: 1 + C = 1, 1 + B = 1) \end{aligned}$
双対性原理により、AND形式のコンセンサス定理も成立する。

簡単化の適用例

以下の和積形の論理式を変換法則を用いて簡単化する。

まず、第1因子と第2因子を統合する。
ここで $X = A + B$ とおく。

$\begin{aligned} f & = (A + B + C) \cdot (A + B + \overline{C}) \cdot (\overline{A} + B + C) \\ = (X + C) \cdot (X + \overline{C}) \cdot (\overline{A} + B + C) & (X = A + B とおく) \\ = (X + C \cdot \overline{C}) \cdot (\overline{A} + B + C) & (分配法則 (OR形式)) \\ = (X + 0) \cdot (\overline{A} + B + C) & (補元法則: C \cdot \overline{C} = 0) \\ = (A + B) \cdot (\overline{A} + B + C) & (恒等法則) \end{aligned}$

次に、結果と第3因子を統合する。
ここで、 $X = B$ とおく。

$\begin{aligned} f & = (X + A) \cdot (X + \overline{A} + C) & (交換法則) \\ = B + A \cdot (\overline{A} + C) & (分配法則 (OR形式)) \\ = B + A \cdot \overline{A} + A \cdot C & (分配法則) \\ = B + 0 + A \cdot C & (補元法則: A \cdot \overline{A} = 0) \\ = A \cdot C + B & (恒等法則) \end{aligned}$

クワイン・マクラスキー法による簡単化

概要

クワイン・マクラスキー法 (QM法) は最大項にも適用可能であり、主乗法標準形を体系的に簡単化できる。
最小項ベースと同じアルゴリズムを使用するが、ビットの解釈が異なる点に注意が必要である。

ビット解釈の違い
最大項では 0 → 肯定リテラル、1 → 否定リテラルとなる。(最小項と逆)
グループ化
グループ化は最小項と同様に「1のビット数」で行う。

手順

クワイン・マクラスキー法による主乗法標準形の簡単化手順を以下に示す。

主乗法標準形の全最大項を2進数で表し、1のビット数でグループ分けする。
隣接グループ間で、正確に1ビットだけ異なる項を組み合わせる。(ダッシュ「-」で置換)
組み合わせ不可の項が主項 (prime implicant) となる。
主項表を作成する。(行: 主項、列: 元の最大項)
必須主項 (essential prime implicant) を特定する。(その最大項をカバーする主項が1つだけのもの)
必須主項で全最大項がカバーされるか確認し、不足があれば追加の主項を選択する。
選択した主項の論理積が簡単化された論理式となる。
ビット解釈に注意: ダッシュ以外の 0 → 肯定リテラル、1 → 否定リテラルとして和項 (sum term) を構成する。

具体例

例として $f = \prod M (0, 1, 2, 5)$ を簡単化する。

ステップ1として、1のビット数でグループ分けする。

ステップ1 : グループ分け
グループ (1のビット数)	最大項	2進数
0	$M_{0}$	000
1	$M_{1}$	001
1	$M_{2}$	010
2	$M_{5}$	101

ステップ2として、隣接グループ間で1ビットだけ異なる項を組み合わせる。

ステップ2 : 第1回の組み合わせ
組み合わせ	結果	カバーする最大項
$M_{0}$ (000) と $M_{1}$ (001)	00-	{0, 1}
$M_{0}$ (000) と $M_{2}$ (010)	0-0	{0, 2}
$M_{1}$ (001) と $M_{5}$ (101)	-01	{1, 5}

$M_{2}$ (010) と $M_{5}$ (101) は2ビット以上異なるため組み合わせ不可である。

ステップ3として、第2回の組み合わせを試みる。全ての主項のダッシュ位置が異なるため、これ以上の組み合わせは不可能である。

主項の一覧とそれぞれの和項への変換を以下に示す。

00- → $(A + B)$
ビット解釈: A=0 → 肯定(A), B=0 → 肯定(B), C=ダッシュ → 除去
0-0 → $(A + C)$
ビット解釈: A=0 → 肯定(A), B=ダッシュ → 除去, C=0 → 肯定(C)
-01 → $(B + \overline{C})$
ビット解釈: A=ダッシュ → 除去, B=0 → 肯定(B), C=1 → 否定( $\overline{C}$ )

ステップ4として、主項表を作成する。

ステップ4 : 主項表
主項	$M_{0}$	$M_{1}$	$M_{2}$	$M_{5}$
$(A + B)$ (00-)	○	○
$(A + C)$ (0-0)	○		○
$(B + \overline{C})$ (-01)		○		○

ステップ5として、必須主項を特定する。

$M_{2}$ は、 $(A + C)$ のみがカバーするため、 $(A + C)$ は必須主項である
$M_{5}$ は、 $(B + \overline{C})$ のみがカバーするため、 $(B + \overline{C})$ は必須主項である
$(A + C)$ は $M_{0}$ もカバーし、 $(B + \overline{C})$ は $M_{1}$ もカバーするため、全最大項がカバーされる

簡単化の結果を以下に示す。

$f = (A + C) \cdot (B + \overline{C})$

主加法標準形との関係

補集合による変換

n変数の関数では、 $0$ から $2^{n} - 1$ までの全ての番号のうち、最大項番号の補集合が最小項番号となる。

例: $\prod M (0, 3, 5, 6)$ の場合、全体集合 {0, 1, ..., 7} から {0, 3, 5, 6} を除いた {1, 2, 4, 7} が最小項番号となる。
したがって、 $\sum m (1, 2, 4, 7)$ と等価である。

逆に、最小項番号の補集合が最大項番号となる。
この対称性から、一方の標準形が分かれば他方を直ちに求めることができる。

ド・モルガンの定理による変換

補関数を求めて展開する方法によっても変換が可能である。

手順を以下に示す。

関数 $f$ の補関数 $\overline{f}$ を求める。(fの値が1の行の最大項の積)
ド・モルガンの定理で $\overline{f}$ の否定を取る。
整理すると主加法標準形が得られる。

例として、 $f = \prod M (0, 3, 5, 6)$ からの変換を示す。

補関数の導出
fの値が1となる行の最小項番号の補集合を考える。

fの値が0となる行は {0, 3, 5, 6} であるため、 $\overline{f}$ の値が1となる行は {0, 3, 5, 6} である。

$\overline{f} = \sum m (0, 3, 5, 6) = m_{0} + m_{3} + m_{5} + m_{6}$
否定を取る。
$f = \overline{\overline{f}} = \overline{m_{0} + m_{3} + m_{5} + m_{6}}$
ド・モルガンの定理を適用
$f = \overline{m_{0}} \cdot \overline{m_{3}} \cdot \overline{m_{5}} \cdot \overline{m_{6}}$
主加法標準形への変換
fが1となる行の最小項番号は {1, 2, 4, 7} であるため

$f = \sum m (1, 2, 4, 7)$

主加法標準形との詳細な比較については、情報理論 - 主加法標準形のページを参照すること。