ブール代数(Boolean algebra)

2種類の値(0,1)を使った代数体系です。ブール代数を使って論理関数を表現することができ、各種演算規則により論理の変換や圧縮を行うことができます。

  • 交換則 a+b = b+a
  • 結合則    a+(b+c) = (a+b)+c
  • 吸収則    a・b+a = a
  • 分配則    a・(b+c) = a・b+a・c
  • ド・モルガンの定理  ab = a + b 

演習1  結合則

下記の結合則を確認する回路を作成し、判定方法も説明しなさい。

 (a・b)・c = a・(b・c)

 

解説

3つの入力a,b,cとして、それぞれスイッチS1,スイッチS2、近接センサを割り当てます。左辺の2つのANDからなる回路をブロックで実装してLEDの緑入力に接続します。また右辺の2つのANDからなる回路もブロックで実装しこちらはLEDの赤入力に接続します。

2つのスイッチと近接センサによって2^3=8通りの状態を作りLEDの緑と赤が同じように発光することを確認します。

 

回路図は以下のとおりです。

ブール代数の結合則(AND)を確認するための回路図
ブール代数の結合則(AND)を確認するための回路のブロック実装図

 

以下は補足ですが、OR演算による結合則

 (a+b)+c = a+(b+c)

は、先の回路においてANDをORに置き換えるだけで確認ができます。

ブール代数の結合則(OR)を確認するための回路図
ブール代数の結合則(OR)を確認するための回路のブロック実装図

演習2 多入力AND演算

5入力AND回路を2入力ANDで作成し、出力の妥当性を確認する回路も併せて作りなさい。

 

解説

カウンタの出力の下位5bitを4つの2入力ANDゲートに入力し、最終出力はLEDに接続します。カウンタ下位5bitが全てHレベルの場合、つまりカウンタ値が1Fh,3Fh,5Fh,7Fh,9Fh,BFh,DFh,FFhの場合にLEDが点灯することを確認します。※通常の回路では8ビットカウンタ出力を直接ANDゲートに入力可能ですが、Cube-Dでは各ビットを分離するためにデコーダブロックが必要になります(シリアル通信でバス情報を送っているため)。

5入力ANDを2入力ANDで構成できることを確認する回路のブロック実装図
5入力ANDを2入力ANDで構成する回路例

上記回路のANDをORに置き換えると、20h,40h,60h,80h,a0h,c0h,e0hでLEDが消灯する回路になります。併せて確認してみてください。

演習3 ド・モルガンの定理①

下記のド・モルガンの定理を確認する回路を作成、その確認方法も説明しなさい。

                    ab = a + b

解説

2つの入力a,bとして、それぞれスイッチS1,スイッチS2を割り当てます。左辺の回路をブロックで実装してLEDの赤入力に接続します。また右辺の回路もブロックで実装しこちらはLEDの緑入力に接続します。NORブロックを使わずにORブロックとNOTブロックを使っているのは、ANDブロックとORブロックを入れ替えるだけでもう一つの式の確認もできるからです。

 2つのスイッチより2^2=4通りの状態を作りLEDの緑と赤が同じタイミングで発光することを確認します。

 

回路図は以下のとおりです。

ド・モルガンの定理①を確認するための回路図
ド・モルガンの定理①を確認するための回路のブロック実装図

演習4 ド・モルガンの定理②

下記のド・モルガンの定理を確認する回路を作成、その確認方法も説明しなさい。

                 ab = a・b

解説

演習3の回路においてANDブロックとORブロックのみを入れ替えてあります。確認方法等は同じです。

 

回路図は以下のとおりです。

ド・モルガンの定理②を確認するための回路図
ド・モルガンの定理②を確認するための回路のブロック実装図

演習5 完備性

N入力M出力の論理関数は、{AND,OR,NOT}の3基本関数の組み合わせで表現できる(完備性がある)が、NANDは完備性があることを示せ。

 

解説

NANDだけでAND,OR,NOTの3つと等価な論理が作り出せることを示します。

 

まずはNOTから。2入力を1つに束ねたものは、NANDの真理値表の入力00と11だけの表となり、NOTに一致することは明らかです。

 

 

NANDだけで構成したNOT回路

NOT


続いてANDを作ってみます。

NANDの出力に先ほど確認したNOTを接続した回路なので明らかにANDになることが分かります。

 

 

 

NANDだけで構成したAND回路

AND


最後はORです。

NANDの入力にNOTがそれぞれ接続されています。ド・モルガンの定理を使って変形します。 

 y = not(  ab ) = a+b  

ORになることが確認できました。以上でNANDは完備性があることが証明されました。

 

 

NANDだけで構成したOR回路

OR


XORをNANDだけで作成したらどのような回路になるでしょうか? 

 

 y = a・b+a・b

 

なので、先に求めたNOT, AND, ORを当てはめて変形すると5つのNANDで作ることができます。 

 

 

5つのNANDで構成したXOR


 

実はXORは4つのNANDで作ることができます。代数で変形するよりもCube-Dで回路を組んで真理値を確認したほうが早いので下のような回路を使って確認します。

 

NANDだけで構成したXOR回路

4つのNANDで構成したXOR


NANDだけで構成したXOR回路のブロック実装図

完備集合はその他に、{NOR},{AND,NOT},{OR,NOT}などがあります。