情報理論 - 主加法標準形

📢 Webサイト閉鎖と移転のお知らせ

このWebサイトは2026年9月に閉鎖いたします。

移転先はhttps://mochiu.net/index.php?title=情報理論 - 主加法標準形です。

新しい記事は移転先で追加しております。（旧サイトでは記事を追加しておりません）

概要

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

任意のブール関数は、その関数の値が1となる全ての入力の組み合わせに対応する最小項を論理和 (OR) で結合することによって、一意に表現できる。
この表現は Σ記法を用いて構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum m(\ldots)} と記述される。

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

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

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

主加法標準形の特徴
項目	内容
正式名称	主加法標準形 (Principal Disjunctive Normal Form)
略称	PDNF
別名	SOP canonical form (Sum of Products)
構成要素	最小項 (minterm)
結合演算	論理和 (OR, +)
記号表記	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum m(\ldots)}
真理値表から	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = 1} の行を使用
展開に利用	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x + \overline{x} = 1}
簡単化手法	カルノー図、クワイン・マクラスキー法

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

基本用語

リテラル

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

肯定リテラル
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A} のように、論理変数そのままの形
否定リテラル
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A}} のように、論理変数の否定の形

n個の変数が存在する場合、リテラルの総数は構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 2n} 個となる。

基本積

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

例: 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot \overline{B} \cdot C}

最小項 (minterm)

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

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

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

例: $A=0,B=1,C=0$ の場合、10進数値は $010_{(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},\ldots ,x_{n})=\sum m(i_{1},i_{2},\ldots ,i_{k})$

ここで、 $i_{1},i_{2},\ldots ,i_{k}$ は構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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

導出過程を以下に示す。

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = 1} となる行の特定
入力 001 (行1), 010 (行2), 100 (行4), 111 (行7) の4行で構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = 1} となる
対応する最小項
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_1 = \overline{A} \cdot \overline{B} \cdot C} , 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_2 = \overline{A} \cdot B \cdot \overline{C}} , 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_4 = A \cdot \overline{B} \cdot \overline{C}} , 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_7 = A \cdot B \cdot C}
主加法標準形
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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}
Σ記法
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = \sum m(1, 2, 4, 7)}

論理式からの導出

既存の論理式から主加法標準形を導出するには、恒等式構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x + \overline{x} = 1} を利用した展開を行う。

手順を以下に示す。

論理式を積和形に展開する。(分配法則を適用)
各項に含まれない変数構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x} について、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (x + \overline{x})} を乗じる。(構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x + \overline{x} = 1} なので値は変わらない)
分配法則で展開し、全ての項を最小項の形にする。
重複する最小項を除去する。(構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_i + m_i = m_i} )

具体例として、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = A \cdot B + \overline{A} \cdot C} の主加法標準形を求める。

第1項構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot B} の変換
Cが含まれないため、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot B \cdot (C + \overline{C})} に展開する。

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot B \cdot C + A \cdot B \cdot \overline{C} = m_7 + m_6}
第2項構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A} \cdot C} の変換
Bが含まれないため、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A} \cdot (B + \overline{B}) \cdot C} に展開する。

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A} \cdot B \cdot C + \overline{A} \cdot \overline{B} \cdot C = m_3 + m_1}
結果
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot 1 = A}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + 0 = A}
支配法則 (Domination Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot 0 = 0}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + 1 = 1}
冪等法則 (Idempotent Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot A = A}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + A = A}
補元法則 (Complement Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot \overline{A} = 0}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + \overline{A} = 1}
二重否定法則 (Involution Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{\overline{A}} = A}

構造法則

ブール代数の構造法則
法則名	AND形式	OR形式
交換法則 (Commutative Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot B = B \cdot A}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + B = B + A}
結合法則 (Associative Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (A \cdot B) \cdot C = A \cdot (B \cdot C)}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (A + B) + C = A + (B + C)}
分配法則 (Distributive Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot (B + C) = A \cdot B + A \cdot C}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + B \cdot C = (A + B) \cdot (A + C)}

簡単化法則

ブール代数の簡単化法則
法則名	AND形式	OR形式
吸収法則 (Absorption Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot (A + B) = A}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + A \cdot B = A}
ド・モルガンの法則 (De Morgan's Law)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A \cdot B} = \overline{A} + \overline{B}}	${\overline {A+B}}={\overline {A}}\cdot {\overline {B}}$
コンセンサス定理 (Consensus Theorem)	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (A + B) \cdot (\overline{A} + C) \cdot (B + C) = (A + B) \cdot (\overline{A} + C)}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot B + \overline{A} \cdot C + B \cdot C = A \cdot B + \overline{A} \cdot C}

吸収法則の証明

吸収法則構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A + A \cdot B = A} の成立を以下のように証明できる。

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{align} A + A \cdot B &= A \cdot 1 + A \cdot B && \text{(恒等法則: } A = A \cdot 1 \text{)} \\ &= A \cdot (1 + B) && \text{(分配法則)} \\ &= A \cdot 1 && \text{(支配法則: } 1 + B = 1 \text{)} \\ &= A && \text{(恒等法則)} \end{align} }

コンセンサス定理の証明

コンセンサス定理構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A \cdot B + \overline{A} \cdot C + B \cdot C = A \cdot B + \overline{A} \cdot C} の成立を以下のように証明できる。

第3項構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B \cdot C} が冗長であることを示す。

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{align} A \cdot B + \overline{A} \cdot C + B \cdot C &= A \cdot B + \overline{A} \cdot C + B \cdot C \cdot (A + \overline{A}) && \text{(補元法則: } A + \overline{A} = 1 \text{)} \\ &= A \cdot B + \overline{A} \cdot C + A \cdot B \cdot C + \overline{A} \cdot B \cdot C && \text{(分配法則)} \\ &= A \cdot B \cdot (1 + C) + \overline{A} \cdot C \cdot (1 + B) && \text{(分配法則)} \\ &= A \cdot B + \overline{A} \cdot C && \text{(支配法則: } 1 + C = 1 \text{, } 1 + B = 1 \text{)} \end{align} }

簡単化の適用例

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

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{align} 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 && \text{(分配法則)} \\ &= A \cdot B \cdot 1 + \overline{A} \cdot B \cdot C && \text{(補元法則: } C + \overline{C} = 1 \text{)} \\ &= A \cdot B + \overline{A} \cdot B \cdot C && \text{(恒等法則)} \\ &= B \cdot (A + \overline{A} \cdot C) && \text{(分配法則)} \\ &= B \cdot (A + \overline{A}) \cdot (A + C) && \text{(分配法則 (OR形式))} \\ &= B \cdot 1 \cdot (A + C) && \text{(補元法則: } A + \overline{A} = 1 \text{)} \\ &= B \cdot (A + C) && \text{(恒等法則)} \\ &= A \cdot B + B \cdot C && \text{(分配法則)} \end{align} }

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

概要

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

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

手順

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

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

具体例

例として構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = \sum m(0, 1, 2, 3, 7)} を簡単化する。

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

ステップ1 : グループ分け
グループ (1のビット数)	最小項	2進数
0	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_0}	000
1	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_1}	001
1	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_2}	010
2	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_3}	011
3	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_7}	111

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

ステップ2 : 第1回の組み合わせ
組み合わせ	結果	カバーする最小項
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_0} (000) と構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_1} (001)	00-	{0, 1}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_0} (000) と構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_2} (010)	0-0	{0, 2}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_1} (001) と構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_3} (011)	0-1	{1, 3}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_2} (010) と構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_3} (011)	01-	{2, 3}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_3} (011) と構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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-- -> 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A}} (m0, m1, m2, m3をカバー)
-11 -> 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B \cdot C} (m3, m7をカバー)

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

ステップ4 : 主項表
主項	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_0}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_1}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_2}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_3}	構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_7}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A}} (0--)	○	○	○	○
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B \cdot C} (-11)				○	○

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

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_0} , 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_1} , 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_2} は構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A}} のみがカバーするため、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{A}} は必須主項
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_7} は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B \cdot C} のみがカバーするため、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B \cdot C} は必須主項
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m_3} は両方がカバーするが、両主項が既に必須として選択されているため問題なし。

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

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = \overline{A} + B \cdot C}

主乗法標準形との関係

補集合による変換

n変数の関数では、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0} から構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 2^{n} - 1} までの全ての番号のうち、最小項番号の補集合が最大項番号となる。

例: 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum m(1, 2, 4, 7)} の場合
全体集合構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {0,\, 1,\, \cdots, \, 7}} から構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {1, \, 2, \, 4, \, 7}} を除いた構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {0, \, 3, \, 5, \, 6}} が最大項番号となる。

よって構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = \prod M(0, 3, 5, 6)} と表現される。

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

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

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

手順を以下に示す。

関数構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f} の補関数構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{f}} を求める (fの値が0の行の最小項の和)
ド・モルガンの定理で構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{f}} の否定を取る
整理すると主乗法標準形が得られる

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

補関数の導出
f の値が0となる行の最小項番号は {0, 3, 5, 6} であるため

構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{f} = \sum m(0, 3, 5, 6) = m_0 + m_3 + m_5 + m_6}
否定を取る
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = \overline{\overline{f}} = \overline{m_0 + m_3 + m_5 + m_6}}
ド・モルガンの定理を適用
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = \overline{m_0} \cdot \overline{m_3} \cdot \overline{m_5} \cdot \overline{m_6}}
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{m_i} = M_i} の関係を利用
構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f = M_0 \cdot M_3 \cdot M_5 \cdot M_6 = \prod M(0, 3, 5, 6)}