学ぶ › トピック 3

真理値表と標準形：Σm と ΠM

読了時間：約 8 分 · bitGateLab チーム

デジタル設計の問題はほとんどの場合、言葉で書かれた仕様（「次の場合に警報が鳴る…」）から始まり、それを真理値表に直します。次のステップは、その表から、ゲートで作れる式を取り出すことです。この記事では、そのための体系的な方法を学びます。最小項と最大項、積和標準形と和積標準形、そして教科書やシミュレータ、カルノー図で使われる簡潔な記法 Σm と ΠM です。

真理値表の並べ方

変数が n 個あれば、行は 2ⁿ 行になります。行は 2 進数の昇順に並べ、最初の変数を最上位ビットとします。こうすると、各行を 10 進数の番号で特定できます。A、B、C の表では、A = 1、B = 0、C = 1 の行は 101₂ = 5 です。この番号を最小項や最大項の添字として使うので、変数の順序が重要になります。順序を変えると番号も変わってしまいます。

最小項と積和形

まず、最小項とは、すべての変数を、否定つきまたは否定なしで、それぞれ一度ずつ含む積（AND）のことです。作り方はこうです。その行で 1 になる変数はバーなしで、0 になる変数はバーつきで書きます。最小項は自分の行でだけ 1 になり、ほかのすべての行では 0 になります。m_i と書き、i は行の番号です。

行	A	B	C	最小項	最大項
0	0	0	0	m₀ = ABC	M₀ = A + B + C
1	0	0	1	m₁ = ABC	M₁ = A + B + C
2	0	1	0	m₂ = ABC	M₂ = A + B + C
3	0	1	1	m₃ = ABC	M₃ = A + B + C
4	1	0	0	m₄ = ABC	M₄ = A + B + C
5	1	0	1	m₅ = ABC	M₅ = A + B + C
6	1	1	0	m₆ = ABC	M₆ = A + B + C
7	1	1	1	m₇ = ABC	M₇ = A + B + C

関数が 1 になるすべての行の最小項を足し合わせる（OR をとる）と、ちょうどそれらの行で 1 になる式が得られます。これが積和標準形（英語の sum of products を略して SOP）で、加法標準形とも呼ばれます。簡潔な記法では F = Σm(1 になる行の番号) と書きます。

最大項と和積形

一方、最大項とは、すべての変数を含む和（OR）のことです。規則は逆になります。その行で 0 になる変数はバーなしで、1 になる変数はバーつきで書きます。最大項は自分の行でだけ 0 になります。M_i（大文字の M）と書きます。

関数が 0 になるすべての行の最大項を掛け合わせる（AND をとる）と、ちょうどそれらの行で 0、残りの行で 1 になる式が得られます。これが和積標準形（POS）で、乗法標準形とも呼ばれます。F = ΠM(0 になる行の番号) と書きます。

同じ行の最小項と最大項は、互いに否定の関係にあります。m_i = M_i です。そのため、ある関数の Σm の一覧がわかっていれば、ΠM の一覧は、そこに現れないすべての番号でできています。

例 1：真理値表から二つの形へ。 ある 3 変数の関数が、行 1、3、6、7 で 1 になるとします。

#	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

簡潔な記法：F = Σm(1, 3, 6, 7) = ΠM(0, 2, 4, 5)。
積和標準形：F = ABC + ABC + ABC + ABC。
和積標準形：F = (A + B + C)(A + B + C)(A + B + C)(A + B + C)。
SOP を簡単化します。ABC + ABC = AC、ABC + ABC = AB です。したがって F = AC + AB。

行 5（A = 1、B = 0、C = 1）で検算します。AC = 0、AB = 0 なので F = 0 となり、表と一致します。

どちらの形を使うべきか

二つの形は同じ関数を表しますが、大きさは同じではありません。項の少ないほうを使いましょう。関数に 1 が少なければ Σm のほうが短く、0 が少なければ ΠM のほうが短くなります。8 行の表で 1 が 2 個の関数なら、SOP は 2 項、POS は 6 項です。

実装のしかたも関係します。積和形は、複数の AND ゲートの出力を一つの OR に入れる形で作られ、この二段構成はそのまま NAND-NAND に変換できます。和積形は、複数の OR の出力を一つの AND に入れる形で作られ、NOR-NOR に変換できます。

例 2：問題文から式へ。 あるタンクに、水位センサが三つ付いています。A（低）、B（中）、C（高）です。各センサは、水がその高さに達すると 1 を出力します。「水位異常」ランプは、物理的にありえない組み合わせのとき、つまり上のセンサが作動しているのに、それより下のセンサが作動していないときに点灯させます。

有効な組み合わせ（ABC）：000、100、110、111。つまり行 0、4、6、7 です。
ランプはそれ以外の行で点灯します。F = Σm(1, 2, 3, 5)。
等価な表現：F = ΠM(0, 4, 6, 7)。
簡単化します。m₁ + m₃ = AC、m₁ + m₅ = BC、m₂ + m₃ = AB です。m₁ と m₃ を二回ずつ使うと（べき等則）、F = BC + AB となります。

確認しましょう。行 1（001）では BC = 1、行 2（010）では AB = 1、行 3（011）では AB = 1、行 5（101）では BC = 1 です。000、100、110、111 では両方の項が 0 になります。この式は「B が作動していないのに C が作動している」または「A が作動していないのに B が作動している」と読めます。

関数の否定

F = Σm(1, 3, 6, 7) のとき、その否定は F が 0 になるところで 1 になります。F = Σm(0, 2, 4, 5) です。これは、簡単化した POS が欲しいときに役立ちます。F を積和形として簡単化し、そのあとでド・モルガンの定理を適用するのです。たとえば F = AC + AB で（行 0、2、4、5 で確かめてみてください）、否定をとると F = (A + C)(A + B) になります。展開すると AB + AC + BC で、コンセンサスの定理により AB + AC となり、例 1 と同じ結果です。

こうした式変形をさらに深く学ぶにはブール代数を復習してください。図を使って簡単化する方法は、カルノー図に進みましょう。

よくある間違い

バーの規則を逆にする。最小項では 0 の変数にバーが付き、最大項では 1 の変数にバーが付きます。
関数が 1 になる行を ΠM に入れる。ΠM は 0 の行、Σm は 1 の行の一覧です。
表と式とで変数の順序を変える。C、B、A の順にすると、行「5」はもう同じ行ではありません。
標準形の項で変数を一つ書き忘れる。4 変数の最小項には、必ずリテラルが四つあります。それより少なければ、すでに簡単化されていて、標準形ではありません。

シミュレータで試してみよう

真理値表モジュールでは、関数を一行ずつ入力すると、その標準形と簡単化した式がすぐに表示されます。手で行った各ステップの確認に使えます。

入力が三つ、出力が一つの表を作ります。
例 1 の行 1、3、6、7 を 1 にし、残りは 0 のままにします。
生成された Σm と ΠM の式を見て、自分の式と比べます。
表を回路に変換し、入力を切り替えて、出力が表どおりになることを確かめます。
タンクの問題でも同じことを行い、ありえない組み合わせのときだけランプが点灯することを確かめます。

練習問題

4 変数 A、B、C、D の関数について、最小項 m₉ と最大項 M₉ を書いてください。
解答
9 = 1001 です。m₉ = ABCD、M₉ = A + B + C + D となります。
F(A, B, C) = Σm(0, 1, 5) のとき、F を ΠM 記法で書いてください。
解答
F = ΠM(2, 3, 4, 6, 7)。
A と B が等しいときだけ 1 になる 2 変数関数の積和標準形を求め、可能なら簡単化してください。
解答
F = Σm(0, 3) = AB + AB。これ以上は簡単になりません。XNOR です。
F(A, B, C) = Σm(1, 2, 3, 4, 5, 6, 7) の和積標準形を書いてください。
解答
0 になるのは行 0 だけなので、F = ΠM(0) = A + B + C です。3 入力 OR 一つで済みます。