主加法標準形・主乗法標準形・リードマラー標準形の求め方

こんにちは！　ももやまです！
たまには数学系じゃなくて情報系のまとめをしたくなったのでたまには情報系でいきます。

前回の記事　論理回路の基礎編

www.momoyama-usagi.com

 

ということで、今回は主加法標準形、主乗法標準形、リードマラー標準形の3つについてまとめてみたいと思います。

論理式の基本法則についてはこちらの記事でまとめているので、もし論理式についてわからないことがあればこちらをご覧ください。

www.momoyama-usagi.com

なお、今回は論理和を \( A + B \) 、論理積を \( AB \)、否定を \( \bar{A} \) と書くことにします。ほかの記事では、論理和を \( A \lor B \) 、論理積を \( A \land B \) 、否定を \( \lnot A \) と書いているのもあるのでご注意ください。

 

スポンサードリンク

１．主加法標準形（論理和標準形）

主加法標準形とは、最小項（論理積で表されている）同士の和の形になっているような論理式、具体的に1つ例を挙げてみると \[ X= \bar{A} \bar{B} C + \bar{A} B  C + ABC \] のような形になっている論理式を表します。数学界では「選言標準形」、「DNF」と呼ばれます。

例えば2変数 \( A,B \) の次の論理式を考えてみましょう。
\[ X = A + \bar{A}B \]

まずは、この式の真理値表と最小項を求めてみましょう。

最小項とは、それぞれの入力（今回は \( A \) と \( B \) ）を論理式の積で表したものを表します。例えば、\( A = 0, B = 0 \) のときの最小項は2変数の否定の積、つまり \( \bar{A}\bar{B} \) となります。

A	B	X	最小項
0	0	0	\( \bar{A}\bar{B} \)
0	1	1	\( \bar{A}B \)
1	0	1	\( A\bar{B} \)
1	1	1	\( AB \)

真理値表が \( X \) が1になっている部分の最小項に注目してください。（ピンク色の部分）
\( X \) が1の部分の最小項の和を全部取ると主加法標準形が完成します。この場合だと、

\[ X = \bar{A}B + A \bar{B} + AB \]

となります。

スポンサードリンク

２．主乗法標準形（論理積標準形）

主乗標準形とは、最大項（論理和で表されている）同士の積の形になっているような論理式、具体的に1つ例を挙げてみると \[X= (\bar{A} + \bar{B}  + C)(A + \bar{B}  + C)(\bar{A} + B  + C)\] のような形になっている論理式を表します。数学界では「連言標準形」、「CNF」と呼ばれます。

１と同じように \[ X = A + \bar{A}B \] で考えてみましょう。
今度は最小項ではなく、最大項をもとめます。
最大項は、それぞれの入力（今回は \( A \) と \( B \) ）の場合のみ満たさないように論理式の和で表したものとなります。
例えば、\( A = 0 \), \( B = 0 \) の最大項を求めてみます。例えば、\( A = 1 \) と \( B = 1 \) の和、つまり \( A + B \) であれば、\( A = 0 \), \( B = 0 \) のときだけが0、つまり偽になりますね。なので\( A=0,B=0 \) の最大項は \( A + B \) となります。*1
同じように該当する入力だけを満たさないような和を下のように求めていきます。

A	B	X	最大項
0	0	0	\( A+B \)
0	1	1	\( A + \bar{B} \)
1	0	1	\( \bar{A}+B \)
1	1	1	\( \bar{A}+\bar{B} \)

今度は真理値表の \( X \) が 0 になっている部分の最大項に注目してください。
0の部分の最大項の and をすべて取ると主乗法標準形が完成します。この場合だと、

\[ X = A+B \]

となります。

スポンサードリンク

３．リードマラー標準形（展開）

リードマラー標準形とは、論理積で表されたもの同士を排他的論理和で表したもの、例えば \[X= A \oplus BC \oplus AC \oplus ABC\] のようなものを表します。not も使用できないことに注意してください。

求め方は、まず変数のうちの一部を0に固定、残りを固定しなかったときに、\( X \) が真の数をすべて数えます。\( X \) の真の数が奇数個であるパターンの場合のみ、固定しなかった変数（複数固定しなかった場合は変数同士の積）を追加していきます。

調べ終わったときに追加した変数同士すべての排他的論理和がリードマラー標準形となります。*2

試しに１と同じ \[ X = A + \bar{A}B \] のリードマラー標準形を求めてみましょう。

今回は2変数なので次の4パターンを調べます。

1. \( A \), \( B \) ともに0に固定
2. \( A \) だけを0に固定
3. \( B \) だけを0に固定
4. \( A \), \( B \) ともに固定しない

(1) \( A \), \( B \) ともに0に固定

\( A,B \) がともに0のときの真理値表に注目してください。このときは0になっていますよね。なので、真の数の合計は0個です。0は偶数なのでNG、追加はしない。
（仮にもしここがOKの場合、追加されるのは1（恒真）です）

(2) \( A \) だけを0に固定

\( A \) を0とします。このとき、

• \( B \) が0のとき、\( X \) は0
• \( B \) が1のとき、\( X \) は1

この2パターンの中で \( X \) が真なのは1パターンですね。
1は奇数なのでOKです。なので固定しなかった \( B \) を追加。 

(3) \( B \) だけを0に固定

\( B \) を0とします。このとき、

• \( A \) が0のとき、\( X \) は0
• \( A \) が1のとき、\( X \) は1

この2パターンの中で \( X \) が真なのは1パターンですね。
1は奇数なのでOKです。なので固定しなかった \( A \) を追加。 

(4) \( A \), \( B \) ともに固定しない

この場合は真理値表すべてのパターンに注目してください。4パターン中真に該当するのは3パターンですよね。
3は奇数なのでOKです。なので固定しなかった \( AB \) を追加。
（2変数以上固定しなかった場合は追加するのは変数同士の積です） 

よって、(2),(3),(4)のパターンのすべての排他的論理和を取ればよいので、リードマラー標準形は、

\[ X = A \oplus B \oplus AB \]

となります。

 

では1問練習してみましょう。

 

４．練習

練習　

つぎの真理値表 \( A,B,C \) の入力に対して、以下の出力となる論理式を考える。

\( A \)	\( B \)	\( C \)	\( X \)
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

このとき、論理式 \( X \) の

(a) 主加法標準形
(b) 主乗法標準形
(c) リードマラー標準形

をもとめなさい。

 

解答

まずは、最小項と最大項を求める。

\( A \)	\( B \)	\( C \)	\( X \)	最小項	最大項
0	0	0	0	\( \bar{A}\bar{B}\bar{C} \)	\( A+B+C \)
0	0	1	1	\( \bar{A}\bar{B}C \)	\( A+B+\bar{C} \)
0	1	0	1	\( \bar{A}B\bar{C} \)	\( A+\bar{B}+C \)
0	1	1	0	\( \bar{A}BC \)	\( A+\bar{B}+\bar{C} \)
1	0	0	1	\( A\bar{B}\bar{C} \)	\( \bar{A}+B+C \)
1	0	1	0	\( A\bar{B}C \)	\( \bar{A}+B+\bar{C} \)
1	1	0	0	\( AB\bar{C} \)	\( \bar{A}+\bar{B}+C \)
1	1	1	1	\( ABC \)	\( \bar{A}+\bar{B}+\bar{C} \)

(a) 主加法標準形は \( X \) が1のときの最小項のすべての和

\[ X = \bar{A}\bar{B} C + \bar{A}B\bar{C} + A\bar{B}\bar{C} + ABC\]

(b) 主乗法標準形は \( X \) が0のときの最大項のすべての積

\[ X = (A+B+C)(A+\bar{B}+\bar{C})(\bar{A}+B+\bar{C})(\bar{A}+\bar{B}+C)\] 

(c) リードマラー標準形は0を固定していく。固定のしかたを8パターン（3変数なので \( 2^3 \) 通り）変えて \( X \) が真の数が合計が奇数のパターンのすべての排他的論理和を取ればOK。

(1) \( A,B,C \) すべて0に固定

このときの \( X \) は0、\( X \) の真の数の合計数は0 → NG。

(2) \( A,B \) を0で固定（\( C \) を固定しない）

固定させたところは緑で表しています（下も同じく）。

\( A \)	\( B \)	\( C \)	\( X \)
0	0	0	0
0	0	1	1

表より、\( X \) の真の数の合計は1つ → OK、固定しなかった \( C \) を追加

(3) \( A,C \) を0で固定（\( B \) を固定しない）

\( A \)	\( B \)	\( C \)	\( X \)
0	0	0	0
0	1	0	1

表より、\( X \) の真の数の合計は1つ → OK、固定しなかった \( B \) を追加

(4) \( B,C \) を0で固定（\( A \) を固定しない）

\( A \)	\( B \)	\( C \)	\( X \)
0	0	0	0
1	0	0	1

表より、\( X \) の真の数の合計は1つ → OK、固定しなかった \( A \) を追加

(5) \( A \) だけを0で固定（\( B,C \) を固定しない）

\( A \)	\( B \)	\( C \)	\( X \)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0

表より \( X \) の真の数の合計は2つ→NG。

(6) \( B \) だけを0で固定（\( A,C \) を固定しない）

\( A \)	\( B \)	\( C \)	\( X \)
0	0	0	0
0	0	1	1
1	0	0	1
1	0	1	0

表より \( X \) の真の数の合計は2つ→NG。

(7) \( C \) だけを0で固定（\( A,B \) を固定しない）

\( A \)	\( B \)	\( C \)	\( X \)
0	0	0	0
0	1	0	1
1	0	0	1
1	1	0	0

表より \( X \) の真の数の合計は2つ→NG。

(8) すべて固定しない

上の真理値表より \( X \) の真の数は合計4つ→NG。

よって、(2),(3),(4)のパターンの排他的論理和同士をとればよい。よって、

\[ X = A \oplus B \oplus C \]

となる。

５．さいごに

今回は主加法標準形、主乗法標準形、リードマラー標準形の出し方についてまとめてみました。

主加法標準形、主乗法標準形、リードマラー標準形は、論理式を変形して求めることもできるのですが、変形の際にミスしてしまうことがあるので「真理値表書かずに解け」と指示されたとき以外は真理値表を書いて解くことをおすすめします。

 

Next　論理式の簡略化（カルノー図編）

www.momoyama-usagi.com