主加法標準形・主乗法標準形

先日の投稿（ANDアレイ - jinyux’s diary）で説明したことについて少し勉強が進んだのでまたまとめてみる。内容的には単なる言い換えになってしまっているが、自分的に言葉の整理をしたいと思ったのである。

論理式に関する用語の説明

・最小項
論理関数への入力すべてを含む論理積のこと。例えば3変数 $A, B, C$ の関数に対して $A\bar{B}\bar{C}$ は最小項となるが $A\bar{C}$ は最小項ではない。

・最大項
入力すべてを含む論理和のこと。 $A+\bar{B}+\bar{C}$ は3変数 $A, B, C$ の関数の最大項である。

・主加法標準形
ある論理関数を最小項の論理和で表したものを主加法標準形という。これはまさに前述したすでに投稿した記事で説明したことの言い換えである。
例えば以下のような真理値表を考える時、2入力なので $2^2$ 行あるわけだが、この各行には入力のとり得るパターンが記入される。

A	B	E
0	0	1
1	0	0
0	1	0
1	1	0

この各行にTrueとなる最小項を記入すると以下のようになる。

A	B	E	Trueとなる最小項
0	0	1	$\bar{A}\bar{B}$
1	0	0	$A\bar{B}$
0	1	0	$\bar{A}B$
1	1	0	$AB$

この論理関数の主加法標準形は出力がTrueとなる行の最小項を論理和でつなげたものだから
$E=\bar{A}\bar{B}$
となる。

・主乗法標準形
ある論理関数を最大項の論理積で表したものを主乗法標準形という。真理値表でいえば各行の入力に対してFalseとなる最大項を考えることである。

A	B	E	Falseとなる最大項
0	0	1	$A+B$
1	0	0	$\bar{A}+B$
0	1	0	$A+\bar{B}$
1	1	0	$\bar{A}+\bar{B}$

主乗法標準形は出力がFalseになる行の最大項の論理積をとるので
$E=(\bar{A}+B)(A+\bar{B})(\bar{A}+\bar{B})$
となる。当然だがこれを展開すると主加法標準形と同じ形になる。
出力がTrueとなっている行が少なければ主加法標準形のほうが式が簡単であり、Falseとなる行が少なければ主乗法標準形のほうが簡単になる。