2 論理関数と真理値表

論理関数とは、以前の授業で論理式と言っていたものです。ブール関数とかス イッチング関数と呼ばれることもあります。変数は$(0,1)$のみで、演算子は $\{+,\;\cdot\;,\;\bar{}\;\}$の3個しかありません。要するに論理関数と いうものは、変数$A$, $B$, $C$, $\cdots$があるとき、

$$Z=F(A, B, C, \cdots)$$ (1)

のようになっているものを言います。論理式のことです。当然、この関数の演 算の結果は、$(0,1)$のいずれかになります。

変数の0のことを偽(false)、$1$のことを真(true)と言ったりすることがありま す。その場合、$+$のことをOR(又は)、$\cdot$のことをAND(かつ)、$\bar{}$ を否定(NOT)といいます。この場合、変数$A$, $B$, $C$, $\cdots$は命題を表 します。1年生の時に学習したFORTRANの論理式です。あの時も、.OR.とか. AND.とか.NOT.の論理演算子を使ったと思います。命題とは、FORTRANのA.GT.B とかに対応します。命題の話はこれくらいにしておきます。

もうひとつ、真理値表のことを述べておきます。変数がとりうる全ての値と $Z$の関係を表したものを真理値表と呼びます。変数が少ない場合は、真理値 表は簡単ですが、変数の数が増えると大変です。変数の数を$N$とすると、 $2^N$行必要になります。

2.1 真理値表から論理式を導く

ここで、興味のある問題は、「任意の真理値表はOR($+$)とAND($\;\cdot\;$)、 NOT( $\;\bar{}\;$)で書き表すことができるか?」ということです。この問いに対す る答えは、「YES」です。このことを、「OR($+$)とAND($\;\cdot$)、 NOT( $\;\bar{}\;$)は完全系をなす」といいます。この証明は非常に大変でこの講 義のレベルを超えます。講義ではなくて、私の頭のレベルを超えるのか $\cdots$。従って、完全な証明をしません(できません)が、任意の真理値表か ら論理関数を導く方法を示すことにより、そのことを理解してもらいたいと思 います。これなら理解できる。

ここでは、真理値表から論理式を導く方法として、主加法標準展開と主乗法標 準展開という方法を示します。教科書は非常に分かりづらいので、以降の議論 は松本光功著「論理回路」を参考にしました。

2.1.1 主加法標準形

3変数(入力)$A,B,C$を含む論理関数で、その出力を$Z$とします。例えば、表 1のようなものです。各変数を一つずつ含む式を標準項 (canonical term)といいます。例えば、 $A\cdot B \cdot C$や $\bar{A}\cdot \bar{B} \cdot C$、 $A+B \cdot C$、 $A \cdot \bar{B}+C$、$A+B+C$、 $A+\bar{B}+\bar{C}$などがそうです。このうち最も項が少ないもの、例えば $A\cdot B \cdot C$や $\bar{A}\cdot \bar{B} \cdot C$を最小項(minterm)と いいます。項というのは数学が学習したものと同じで、乗算のかたまりを1つ の項として数えます。要するに最小項の標準項が乗算のみで構成されており、 その項数は1となります。一方、$A+B+C$、 $A+\bar{B}+\bar{C}$のように最も 項数の多いものを最大項(maxterm)といいます。最大項の項数は、変数の数と 同じになります。 $A+B \cdot C$や $A \cdot \bar{B}+C$は、項数2で最小項で も最大項でもありません。

準備ができたので、表1で示されている真理値表 から、論理式を導き出します。まずは、主加法標準形で最小項を利用した方法を 示します。

表1を見てください。入力変数が$A=1$の場合$A$、$A=0$の 場合$\bar{A}$と表します。$B$や$C$も同様です。そして、それらを乗算して 最小項を書き出します。つまり、表1の最小項ようにしま す。入力が8種類あるので8個の最小項を得ることができます。おのおのの最小 項は、それに応じた入力の時のみ$1$になります。例えば、$(A,B,C)$の入力が $(0,0,0)$の場合、その出力が1になる論理関数は、表から分かるように $\bar{A}\cdot\bar{B}\cdot\bar{C}$のみです。$(1,0,1)$の場合は $A \cdot \bar{B} \cdot C$のみという具合です。

そうして、今度は出力$Z$を注目します。出力$Z$のうち、$Z=1$となる最小項 を次のように加算します。

$$Z=\bar{A} \cdot B \cdot C + A \cdot \bar{B} \cdot C + A \cdot B \cdot \bar{C} + A \cdot B \cdot C$$ (2)

これが、元の真理値表を表す論理式になっています。式(2) は4つの最小項を含み、それぞれが1になる場合を加算しているので、元の真理 値表を表すのはあたりまえですよね。

このように最小項の和で表すことを主加法標準形、あるいは主加法標準展開 (principal disjunctive canonical expansion)といいます。もう一度の手順 をまとめると以下のようになります。

1. 真理値表に従い、入力が$A=0$のとき$\bar{A}$、$A=1$のとき$A$と表 す。$B$、$C$、$\cdots$と入力変数の数だけ同じように表す。
2. そうして、それらを乗算して、最小項を作る。これを全ての入力の組み合わせにつ いて行う。
3. 次に、出力$Z=1$の場合の最小項を加算する。これで主加法標準形が完 成します。

表 1: 3入力の真理値表と最小項

入力			出力	最小項
$A$	$B$	$C$	$Z$
0	0	0	0	$\bar{A} \cdot \bar{B} \cdot \bar{C}$
0	0	1	0	$\bar{A} \cdot \bar{B} \cdot C$
0	1	0	0	$\bar{A} \cdot B \cdot \bar{C}$
0	1	1	1	$\bar{A} \cdot B \cdot C$
1	0	0	0	$A \cdot \bar{B} \cdot \bar{C}$
1	0	1	1	$A \cdot \bar{B} \cdot C$
1	1	0	1	$A \cdot B \cdot \bar{C}$
1	1	1	1	$A \cdot B \cdot C$

2.1.2 主乗法標準形

主加法標準形では出力$Z$の値が1になるものに着目しましたが、主乗法標準形 では$Z$が0になるものに着目します。今度は主加法標準形とは逆に、入力変数 が$A=1$の場合$\bar{A}$、$A=0$の場合$A$と表します。$B$や$C$も同様です。 そして、それらを加算して最大項を書き出します。つまり、表 2のようにします。おのおのの最大項は、それに応じた入 力の時のみ0になります。例えば、$(A,B,C)$の入力が$(0,0,0)$の場合、そ の出力が0になる論理関数は、表から分かるように$A+B+C$のみです。 $(1,0,1)$の場合は $\bar{A}+B+\bar{C}$のみという具合です。

そうして、今度は出力$Z$を注目します。出力$Z$のうち、$Z=0$となる最大項 を次のように乗算します。

$$Z=(A+B+C)\cdot (A+B+\bar{C})\cdot (A+\bar{B}+C)\cdot (\bar{A}+B+C)$$ (3)

これが、元の真理値表を表す論理式になっています。式(3) は4つの最大項を含み、それぞれが0になる場合を乗算しているので、元の真理 値表を表すのはあたりまえですよね。

このように最大項の積で表すことを主乗法標準形、あるいは主乗法標準展開 (principal conjunctive canonical expansion)といいます。もう一度の手順 をまとめると以下のようになります。

1. 真理値表に従い、入力が$A=0$のとき$A$、$A=1$のとき$\bar{A}$と表 す。$B$、$C$、$\cdots$と入力変数の数だけ同じように表す。
2. そうして、それらを加算して、最大項を作る。これを全ての入力の組み合わせにつ いて行う。
3. 次に、出力$Z=0$の場合の最大項を乗算する。これで主乗法標準形が完 成します。

表 2: 3入力の真理値表と最大項

入力			出力	最大項
$A$	$B$	$C$	$Z$
0	0	0	0	$A+B+C$
0	0	1	0	$A+B+\bar{C}$
0	1	0	0	$A+\bar{B}+C$
0	1	1	1	$A+\bar{B}+\bar{C}$
1	0	0	0	$\bar{A}+B+C$
1	0	1	1	$\bar{A}+B+\bar{C}$
1	1	0	1	$\bar{A}+\bar{B}+C$
1	1	1	1	$\bar{A}+\bar{B}+\bar{C}$

ホームページ: Yamamoto's laboratory
著者: 山本昌志