例えば、下のような3入力(A,B,C)の真理値表を満たす論理式を作るにはどうすればよいでしょうか？ここでは分かりやすい方法として、主加法標準形、主乗法標準形、リードマラー標準形の3つを紹介します。
| 入力 (input) | 出力 (output) | 論理式 | |||
|---|---|---|---|---|---|
| A | B | C | X | 最小項 | 最大項 |
| 0 | 0 | 0 | 1 | A B C | A+B+C |
| 0 | 0 | 1 | 1 | A B C | A+B+C |
| 0 | 1 | 0 | 0 | A B C | A+B+C |
| 0 | 1 | 1 | 0 | A B C | A+B+C |
| 1 | 0 | 0 | 1 | A B C | A+B+C |
| 1 | 0 | 1 | 0 | A B C | A+B+C |
| 1 | 1 | 0 | 0 | A B C | A+B+C |
| 1 | 1 | 1 | 1 | A B C | A+B+C |
1. 主加法標準形
例えば、A,B,Cすべてが0の場合、A,B,Cの論理積を使って出力を1にしたいとき、A B Cとすると1になります。A,B,Cどれかが1だと0になるため、A B Cを1にするには0,0,0のパターンしかありません。
同様に、例えば、(A, B, C) = (0, 1, 1)の場合のみ出力を1にしたいときは、A B Cとすればよいことになります。上表で各行のパターンのときだけ論理積が1になる式が最小項に記載されています。
つまり、上表のような出力パターンを得るためには出力が1となっている行の最小項を論理和(+)で繋げればよいことになります。
結果として X ＝ A B C + A B C + A B C + A B C の式ができあがり、これが主加法標準形となります。
ちなみに0になる方の論理和を取ると、出力の0と1が逆になるので、X = A B C + A B C + A B C + A B C も成り立ちます。
2. 主乗法標準形
次に、論理和は全部の項が0のときのみ0となるため、この性質を利用します。
例えば、(A,B,C) = (0,1,0)のときのみ論理和で0にするには、A+B+Cとすれば0になります。0,1,0以外のパターンでは必ず1になってしまいます。
なので真理値表で出力が0の行について、上表の最大項を取り出し論理積で繋げれば、出力が0になる行は(最大項が0になるので)、論理積の結果も0になります。逆に出力が1になる行はすべての論理和部分が必ず1になる(0になる最大項を含まない)ので式が成り立つことになります。
結果として、X ＝ (A+B+C)(A+B+C)(A+B+C)(A+B+C)の式ができあがり、これが主乗法標準形となります。
ちなみに1になる方の論理積を取ると、出力が逆になるので、X = (A+B+C)(A+B+C)(A+B+C)(A+B+C) も成り立ちます。
3. リードマラー標準形
リードマラー標準形は、「B⊕C⊕AB⊕AC⊕ABC」のように否定のない論理積の項を排他的論理和でつないだ形で表現するものです (このとき計算順位は論理積が高い(先計算))。
作り方は、まず以下のようにA,B,Cのそれぞれを0~1回使ったパターンを出します。
-,-,-: (1の項)
A,-,-: (A項)
-,B,-: (B項)
-,-,C: (C項)
A,B,-: (AB項)
A,-,C: (AC項)
-,B,C: (BC項)
A,B,C: (ABC項)
上記の8通りがあります。ここで”-“の部分は0で固定して、文字が入った部分は0と1の両方を持つ行を真理値表から抽出します。例えば、”-,-,-“は0,0,0の行のみ、”A,-,-“は0,0,0と1,0,0の2行を抽出します。”A,-,C”なら、0,0,0、1,0,0、0,0,1、1,0,1の4行といった具合です。”A,B,C”は真理値表を丸ごと抽出することになります。
次に抽出した行について、出力が1になっている行数を数えます。1になっている行の数が奇数ならその項を残して排他的論理和でつなげば完成です。
上表の真理値表で具体的に説明すると、まず0,0,0の出力は1となっているので、1の項を書きます(1⊕)。次にA項ですが、0,0,0は1で、1,0,0も1で出力の1は2個で偶数なので、A項は加えません。同様にB項は1が1個で追加(1⊕B)、C項は2個なので追加しません。AB項は0,0,0が1、1,0,0が1、0,1,0が0、1,1,0が0で1は2個となるので追加しません。同様にAC項は3個で奇数なので追加(1⊕B⊕AC)、BC項は2個なので追加なし、ABC項は4個なので追加なしとなります。
結果として、X = 1⊕B⊕AC という論理式が導かれます。
さて、なぜこの方法で式が導けるかです。
排他的論理和の性質として、1の項の数が奇数の場合出力が1、偶数の場合出力が0となります。例えば、0⊕0⊕1⊕1⊕0⊕1なら1は3個で奇数なので計算結果は1となります(0を数値の1、1を数値の-1と見立てて算術的な掛け算をしたときと似ています→1 × 1 × (-1) × (-1) × 1 × (-1) = -1)。
また例えば、A,B,Cの3入力を例とすると、すべての項を足した一番長い式は、1⊕A⊕B⊕C⊕AB⊕AC⊕BC⊕ABC の8項の式となります(4入力なら2^4=16項になる)。
このうち最初の”1″の項を使うかどうかは、真理値表の0,0,0の行の出力が0か1かで決まります。なぜなら、”1″以外の項(A、B、C、AB、AC、BC、ABCの項)は、すべて0になるからです。つまりA⊕B⊕C⊕AB⊕AC⊕BC⊕ABCが0であるため、出力に合わせるためには、0,0,0の行の出力が1の場合は “1”の項が必ず必要になり、0の場合はこの項は入れられない(または0を入れても良い)ということになります。
次にA項を使うかどうかを考えます。Aの入力以外が「0」(0,0,0または1,0,0)のときは、”1″と”A”以外の項、つまり、B⊕C⊕AB⊕AC⊕BC⊕ABCは必ず0になるため、0,0,0と1,0,0の行の出力のパターン(のみ)でAを使うかどうか決める必要があります。
具体的なパターンを考えると、
1の項がある(0,0,0の出力が1の)とき、1,0,0が0の場合Aの項は(0,1を逆転させる必要があるため)必要で、1,0,0が1の場合Aの項は不要となり、
1の項がない(0,0,0の出力が0の)とき、1,0,0が0の場合Aの項は不要で、1,0,0が1の場合Aの項は必要(0,1を逆転させる必要があるため)となります。
結局、0,0,0と1,0,0の出力の1の数が0個か2個の場合、Aの項を除くことになります (またはAの代わりに0を入れてもよい)。
Bの項もCの項もAの項と同じ考え方で入れるか入れないかを決めることができます。
以下同様なのですが、ABの項を残すかどうかは、AまたはB以外の入力(ここではC)が「0」のとき、それより後ろの項、つまりC、AC、BC、ABCの項は必ず0になるため、0,0,0と1,0,0と0,1,0と1,1,0の出力のパターンで消すか残すか決める必要があります。
ここまでに0,0,0と1,0,0と0,1,0のパターンは既に成立しているので、結局、1,1,0のパターンのとき成り立つように、AB項を残すかどうか決めればよいことになります。
ここまでで0,0,0と1,0,0と0,1,0とパターンについては、1,A,Bの項の排他的論理和の演算の結果となっているため、つまり、この3パターンの出力の1の数が奇数(=ここまでの排他的論理和が1)のとき、1,1,0の出力が0の場合反転させるためAB項を残し、1の場合除けばよいことになります。
逆に出力の1の数が偶数(=ここまでの排他的論理和が0)の場合は、1,1,0の出力が0の場合、そのままにするためAB項を除き、1の場合(反転させるため)残せばよいことになります。
同様にAC項、BC項も決まり、以下同様です。
今回は、真理値表から簡単に論理式を導く方法を紹介しましたが、さらにブール代数などで演算を行い変形して式を単純化する(=回路を単純にする)こともできるでしょう。次回は単純化の一つの方法としてカルノー図を使う方法を紹介したいと思いましたが、以下のページが参考になりこれで良い気がしてきました。
※この記事は、以下のサイトを参考とさせていただきました。