主加法標準形と主乗法標準形について

最初に

間違いがありましたら編集リクエストもしくは下記のツイッターまで連絡お願いします。
また、「￢」の記号が出た場合はnotと読んでください。
「￢A」は「notA」すなわちAの否定を指しています。
また、「~」や「not」と書いたりしますが、ここでは「￢」で統一します。

ブール代数の基本法則

ブール代数の説明は省きますが簡単に言うと集合論における和集合(∪)や積集合(∩)などを+,*と置き換えた式群のことを言います。
例えばA∪BはA+Bと同じことを意味します。
気になる人は調べてみてください。

ここでは、簡略化するときに使うブール代数を基本法則を書きます。
(ここでの名前はあくまで一例です。資料によっては呼び方が変わる可能性があります。)

則
べき等則	A + A = A
	A * A = A
交換則	A + B = B + A
	A * B = B * A
分配則	A * (B + C)= A * B + A * C
	A + (B * C) = A + B * A + C
結合則	(A + B) + C= A + (B + C)
	(A * B) * C = A * (B * C)
吸収則	A + (A * B = A
	A * (A + B) = A
復元則	￢￢A = A
帰無則	A + 1 = 1
	A * 0 = 0
恒等則	A + 0 = A
	A * 1 = A
相補則	A + ￢A = 1
	A * ￢A = 0

こんな感じです。
特にべき等則、その他3あたりは覚えておいて損はないです。

ド・モルガンの法則

ド・モルガンの法則は
①AND演算からOR演算へ変換
￢(A+B) =￢A*￢B
②OR演算からAND演算へ変換
￢(A*B) = ￢A+￢B
です。

最小項と最大項

主加法標準形と主乗法標準形を学ぶ前に最小項と最大項を知っておきましょう。

最小項はどれか１つだけ１となる関数で、任意の入力を１回ずつ含む論理積のことを言います。
例　A*B*C, A*(￢B)*(￢C)　

最大項はどれか１つだけ0になる関数で、任意の入力を1回ずつ含む論理和のことを言います。
例　A+B+C, A+(￢B)+(￢C)

また注意が必要なのですが、0と1の関係が最小項と最大項で逆になっています。以下に例を示します。
例

A	B	X	最小項	最大項
0	0	0	￢A*(￢B)	A+B
0	1	1	￢A*B	A+(￢B)
1	0	1	A*(￢B)	￢A+B
1	1	0	A*B	￢A+(￢B)

主加法標準形について

主加法標準形(加法標準形とも言います。今回は主加法標準形で統一します)は真理値から読み取れる出力が「1」の最小項の論理和のこと。

また、主加法標準形を簡略化した論理式を加法形と言います。

例　X = AB + ￢AB

主加法標準形を用いた論理式の求め方

例えば以下の真理値表があると考えます。

真理値表

A	B	X
0	0	1
0	1	0
1	0	1
1	1	1

今回はXが「1」のところの最小項を抜き出すと

X = ￢A￢B + A￢B + AB

となります。

よって主加法標準形で算出した真理値表になる論理式はX=￢A￢B+A￢B+ABで実現可能となります。

以上が主加法標準形を用いた論理式の求め方となります。

主乗法標準形について

主乗法標準形(乗法標準形とも言います。ここでは主乗法標準形で統一します)は真理値から読み取れる出力が「0」の最大項の論理積のこと。

また、主乗法標準形を簡略化した論理式を乗法形と言います。
例　X=(A+B) * (￢A+B)

主乗法標準形を用いた論理式の求め方

以下の真理値表があったとします

真理値表

A	B	X
0	0	1
0	1	0
1	0	1
1	1	1

今回はXが「0」のところの最大項を抜き出すと

X = A+￢B

よって真理値表になる論理式はX=￢A+Bで実現可能となります。

以上が主乗法標準形を用いた論理式の求め方となります。

主加法標準形と主乗法標準形で求める論理式は同じである

先程求めた論理式は

	論理式
主加法標準形	X=￢A￢B + A￢B + AB
主乗法標準形	X=A+￢B

となっています。

(証明)
主加法標準形で求めた論理式
=￢A￢B + A￢B + AB
=A(B+￢B) + ￢B(A+￢A)
=A+￢B =主乗法標準形で求めた論理式

よって主加法標準形を用いた論理式と主乗法標準形で用いた論理式は同じである。
(証明終)

カルノー図を使っても証明できます。

(証明)
Xをレ点とし、カルノー図に主加法標準形で求めた論理式の最小項
と該当する箇所にXを当てはめていく。

a\b	0	1
0	X
1	X	X

まとめるとA, ￢Bがでてくる
以上より
X = A+￢Bが求まる。
(証明終)

最後に

今回の真理値表はAとBの2入力でしたが、これは3,4入力でもやり方は変わりません。
僕の学校ではちゃんとした説明を受けなかったのでまだ僕自信も完全に理解していませんができるだけ初めてみてもわかりやすいようにまとめてみました。
お役に立てたら光栄です。

なにか質問がありましたら、コメントもしくはTwitter(@PotyaExe)に、修正がありましたら、編集リクエストで修正お願いします。

それでは失礼します。

2018/12/27追記

主加法標準形と主乗法標準形の説明に間違いがありましたので修正いたしました。お詫び申し上げます。
もし、まだ間違いがありましたら編集リクエストもしくは下記のツイッターまでご連絡ください。