情報理論 - 主加法標準形

概要

主加法標準形 (PDNF: Principal Disjunctive Normal Form) は、論理関数を最小項の論理和として一意に表現した標準形である。
SOP canonical form (Sum of Products) とも呼ばれる。

任意のブール関数は、その関数の値が1となる全ての入力の組み合わせに対応する最小項を論理和 (OR) で結合することによって、一意に表現できる。
この表現は Σ記法を用いて $\sum m (\dots)$ と記述される。

主加法標準形は以下の領域で広く活用される。

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

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

主加法標準形の特徴
項目	内容
正式名称	主加法標準形 (Principal Disjunctive Normal Form)
略称	PDNF
別名	SOP canonical form (Sum of Products)
構成要素	最小項 (minterm)
結合演算	論理和 (OR, +)
記号表記	$\sum m (\dots)$
真理値表から	$f = 1$ の行を使用
展開に利用	$x + \overline{x} = 1$
簡単化手法	カルノー図、クワイン・マクラスキー法

対となる標準形として、情報理論 - 主乗法標準形が存在する。
主乗法標準形は最大項の論理積として論理関数を表現するものであり、主加法標準形と双対の関係にある。

基本用語

リテラル

リテラルとは、論理変数またはその否定のことである。

肯定リテラル
$A$ のように、論理変数そのままの形
否定リテラル
$\overline{A}$ のように、論理変数の否定の形

n個の変数が存在する場合、リテラルの総数は $2 n$ 個となる。

基本積

基本積とは、リテラルの論理積 (AND結合) のことである。
積項とも呼ばれる。

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

最小項 (minterm)

最小項とは、n個の変数全てが1回ずつ現れる基本積のことである。
記号 $m_{i}$ で表され、添字iは対応する入力の10進数値である。

命名ルールは以下の通りである。

入力値が1の変数は肯定リテラルとして記述する。
入力値が0の変数は否定リテラルとして記述する。

例: $A = 0, B = 1, C = 0$ の場合、10進数値は $01 0_{(2)} = 2_{(10)}$ であるため、 $m_{2} = \overline{A} \cdot B \cdot \overline{C}$ となる。

最小項の重要な性質として、ある最小項 $m_{i}$ は、対応する入力の組み合わせのときのみ値1となり、他の全ての入力の組み合わせでは値0となる。

最小項の一覧

3変数 (A, B, C) の場合、最小項は $2^{3} = 8$ 個存在する。

下表に、3変数の最小項の一覧を示す。

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

主加法標準形の定義

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

一般式を以下に示す。
$f (x_{1}, x_{2}, \dots, x_{n}) = \sum m (i_{1}, i_{2}, \dots, i_{k})$

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

任意のブール関数は一意の主加法標準形を持つ。
すなわち、2つの論理関数が同一の主加法標準形を持つならば、それらの関数は等価である。

真理値表からの導出

導出手順

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

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

具体例

以下の真理値表を持つ論理関数fを例として、主加法標準形を導出する。

真理値表
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 = 1$ となる行の特定
入力 001 (行1), 010 (行2), 100 (行4), 111 (行7) の4行で $f = 1$ となる
対応する最小項
$m_{1} = \overline{A} \cdot \overline{B} \cdot C$ , $m_{2} = \overline{A} \cdot B \cdot \overline{C}$ , $m_{4} = A \cdot \overline{B} \cdot \overline{C}$ , $m_{7} = A \cdot B \cdot C$
主加法標準形
$f = \overline{A} \cdot \overline{B} \cdot C + \overline{A} \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot \overline{C} + A \cdot B \cdot C$
Σ記法
$f = \sum m (1, 2, 4, 7)$

論理式からの導出

既存の論理式から主加法標準形を導出するには、恒等式 $x + \overline{x} = 1$ を利用した展開を行う。

手順を以下に示す。

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

具体例として、 $f = A \cdot B + \overline{A} \cdot C$ の主加法標準形を求める。

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

$A \cdot B \cdot C + A \cdot B \cdot \overline{C} = m_{7} + m_{6}$
第2項 $\overline{A} \cdot C$ の変換
Bが含まれないため、 $\overline{A} \cdot (B + \overline{B}) \cdot C$ に展開する。

$\overline{A} \cdot B \cdot C + \overline{A} \cdot \overline{B} \cdot C = m_{3} + m_{1}$
結果
$f = m_{1} + m_{3} + m_{6} + m_{7} = \sum m (1, 3, 6, 7)$

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

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

ブール代数には双対性原理 (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 + A \cdot B = A$ の成立を以下のように証明できる。

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

コンセンサス定理の証明

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

第3項 $B \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}$

簡単化の適用例

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

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

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

概要

クワイン・マクラスキー法 (QM法) は、主加法標準形を体系的に簡単化するためのアルゴリズムである。

カルノー図と異なり、変数が多い場合 (5個以上) でも適用可能
コンピュータによる自動化に適しており、最簡形であることを保証する。
全ての主項を列挙し、必要最小限の主項の集合を求める。

手順

クワイン・マクラスキー法の手順を以下に示す。

主加法標準形の全最小項を2進数で表し、1のビット数でグループ分けする。
隣接グループ (1のビット数が1だけ異なる) 間で、正確に1ビットだけ異なる項を組み合わせる。
(異なるビットをダッシュ「-」で置換)
組み合わせ可能な項がなくなるまで繰り返す。
組み合わせできなかった項が主項 (prime implicant) となる。
主項表を作成する。
(行: 主項、列: 元の最小項)
必須主項 (essential prime implicant) を特定する。
(ある最小項をカバーする主項が1つだけの場合、その主項は必須)
必須主項で全最小項がカバーされるか確認し、不足があれば追加の主項を選択する。
選択した主項の論理和が簡単化された論理式となる。

具体例

例として $f = \sum m (0, 1, 2, 3, 7)$ を簡単化する。

ステップ 1 : 最小項を1のビット数でグループ分け

ステップ1 : グループ分け
グループ (1のビット数)	最小項	2進数
0	$m_{0}$	000
1	$m_{1}$	001
1	$m_{2}$	010
2	$m_{3}$	011
3	$m_{7}$	111

ステップ 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_{3}$ (011)	0-1	{1, 3}
$m_{2}$ (010) と $m_{3}$ (011)	01-	{2, 3}
$m_{3}$ (011) と $m_{7}$ (111)	-11	{3, 7}

ステップ 3 : 第2回の組み合わせ

00- (0, 1) と 01- (2, 3)
ダッシュ位置が同じ (ビット0)、非ダッシュ部分が1ビット異なる → 0-- (カバー: {0,1,2,3})
0-0 (0, 2) と 0-1 (1, 3)
ダッシュ位置が同じ (ビット1)、非ダッシュ部分が1ビット異なる → 0-- (カバー: {0,1,2,3})
これ以上の組み合わせは不可能

主項の一覧を以下に示す。

0-- → $\overline{A}$ (m0, m1, m2, m3をカバー)
-11 → $B \cdot C$ (m3, m7をカバー)

ステップ 4 : 主項表を作成

ステップ4 : 主項表
主項	$m_{0}$	$m_{1}$	$m_{2}$	$m_{3}$	$m_{7}$
$\overline{A}$ (0--)	○	○	○	○
$B \cdot C$ (-11)				○	○

ステップ 5 : 必須主項を特定する

$m_{0}$ , $m_{1}$ , $m_{2}$ は $\overline{A}$ のみがカバーするため、 $\overline{A}$ は必須主項
$m_{7}$ は、 $B \cdot C$ のみがカバーするため、 $B \cdot C$ は必須主項
$m_{3}$ は両方がカバーするが、両主項が既に必須として選択されているため問題なし。

全最小項がカバーされたため、簡単化結果は以下の通りである。

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

主乗法標準形との関係

補集合による変換

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

例: $\sum m (1, 2, 4, 7)$ の場合
全体集合 $0, 1, \dots, 7$ から $1, 2, 4, 7$ を除いた $0, 3, 5, 6$ が最大項番号となる。

よって $f = \prod M (0, 3, 5, 6)$ と表現される。

逆に、最大項番号の補集合が最小項番号となる。

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

補関数を求めて展開することにより、主加法標準形から情報理論 - 主乗法標準形へ変換できる。

手順を以下に示す。

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

例: $f = \sum m (1, 2, 4, 7)$ からの変換を以下に示す。

補関数の導出
f の値が0となる行の最小項番号は {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}}$
$\overline{m_{i}} = M_{i}$ の関係を利用
$f = M_{0} \cdot M_{3} \cdot M_{5} \cdot M_{6} = \prod M (0, 3, 5, 6)$