ブール関数の簡略化
代数関数を使用した簡略化
このアプローチでは、ブールIDを適用することにより、1つのブール式が最小化されて同等の式になります。
問題1
ブールIDを使用して次のブール式を最小化します-
$$ F(A、B、C)= A'B + BC '+ BC + AB'C' $$
解決
与えられた場合、$ F(A、B、C)= A'B + BC '+ BC + AB'C' $
または、$ F(A、B、C)= A'B +(BC '+ BC')+ BC + AB'C '$
[べき等法により、BC '= BC' + BC ']
または、$ F(A、B、C)= A'B +(BC '+ BC)+(BC' + AB'C ')$
または、$ F(A、B、C)= A'B + B(C '+ C)+ C'(B + AB ')$
[分配法則による]
または、$ F(A、B、C)= A'B + B.1 + C '(B + A)$
[(C '+ C)= 1および吸収法則(B + AB')=(B + A)]
または、$ F(A、B、C)= A'B + B + C '(B + A)$
[B.1 = B]
または、$ F(A、B、C)= B(A '+ 1)+ C'(B + A)$
または、$ F(A、B、C)= B.1 + C '(B + A)$
[(A '+ 1)= 1]
または、$ F(A、B、C)= B + C '(B + A)$
[As、B.1 = B]
または、$ F(A、B、C)= B + BC '+ AC' $
または、$ F(A、B、C)= B(1 + C ')+ AC' $
または、$ F(A、B、C)= B.1 + AC '$
[As、(1 + C ')= 1]
または、$ F(A、B、C)= B + AC '$
[As、B.1 = B]
したがって、$ F(A、B、C)= B + AC '$は最小化された形式です。
問題2
ブールIDを使用して次のブール式を最小化します-
$$ F(A、B、C)=(A + B)(A + C)$$
解決
与えられた、$ F(A、B、C)=(A + B)(A + C)$
または、$ F(A、B、C)= AA + AC + BA + BC $ [分配規則の適用]
または、$ F(A、B、C)= A + AC + BA + BC $ [べき等法の適用]
または、$ F(A、B、C)= A(1 + C)+ BA + BC $ [分配法則の適用]
または、$ F(A、B、C)= A + BA + BC $ [優勢法の適用]
または、$ F(A、B、C)=(A + 1).A + BC $ [分配法則の適用]
または、$ F(A、B、C)= 1.A + BC $ [優勢法の適用]
または、$ F(A、B、C)= A + BC $ [優勢法の適用]
したがって、$ F(A、B、C)= A + BC $が最小化された形式です。
カルノー図
1953年にMauriceKarnaughinによって導入されたKarnaughマップ(K-map)は、ブール代数式を単純化するために使用される真理値表のグリッドのような表現です。カルノー図には、異なる位置に0個と1個のエントリがあります。ブール式を共通の要素でグループ化し、式から不要な変数を排除します。Kマップでは、垂直または水平のセル境界を越えることは、常に1つの変数のみの変更です。
例1
以下に任意の真理値表を取ります−
A | B | 操作B |
---|---|---|
0 | 0 | w |
0 | 1 | バツ |
1 | 0 | y |
1 | 1 | z |
次に、上記の真理値表のkマップを作成します-
例2
次に、式のKマップを作成します-AB + A'B '
Kマップを使用した簡略化
K-mapは、隣接するセルを1つの項に結合することにより、ブール式を単純化するためのいくつかのルールを使用します。ルールは以下のとおりです-
Rule 1 −ゼロを含むセルはグループ化できません。
間違ったグループ化
Rule 2 −グループには2n個のセルが含まれている必要があります(nは1から始まります)。
間違ったグループ化
Rule 3 −グループ化は水平または垂直である必要がありますが、斜めであってはなりません。
間違った斜めのグループ化
適切な垂直グループ化
適切な水平方向のグループ化
Rule 4 −グループは可能な限り広範囲にカバーする必要があります。
不十分なグループ化
適切なグループ化
Rule 5 −いずれかのセルを他のセルとグループ化できない場合、そのセルはそれ自体がグループとして機能します。
適切なグループ化
Rule 6 −グループは重複する場合がありますが、グループはできるだけ少なくする必要があります。
適切なグループ化
Rule 7 −左端のセル/セルは右端のセル/セルとグループ化でき、最上部のセル/セルは最下部のセル/セルとグループ化できます。
適切なグループ化
問題
K-mapを使用して次のブール式を最小化します-
$$ F(A、B、C)= A'BC + A'BC '+ AB'C' + AB'C $$
解決
各項はk-mapに入れられ、次のようになります。
FのKマップ(A、B、C)
ここで、上記のルールに従って1のセルをグループ化します-
FのKマップ(A、B、C)
$ A'B $と$ AB '$と呼ばれる2つのグループがあります。したがって、$ F(A、B、C)= A'B + AB '= A \ oplus B $です。最小化された形式です。