ブール代数とカルノー図

1　ブール代数

　ブール代数（boolean algebra）は、イギリスの数学者ブール（George Boole）が19世紀の中ごろに提唱した代数系の1つです。ブール代数は束（そく、ｌａｔｔｉｃｅ）の理論が築かれる契機となったものです。ブール代数は1または0の2値のみを持つ変数を用いる論理です。そのため2値代数、2値論理数学、デジタル数学、スイッチング代数などとも呼ばれます。スイッチング回路では、スイッチがONかOFFの2値を取りますので、ブール代数でスイッチング回路を表すことができます。

1．1　ブール代数の公理

　公理2、3、4はブール代数の基本である論理和、論理積、否定について述べたものです。

■　否定（NOT演算）
　変数Aの否定は、NOT演算とも呼ばれます。Aの否定はAの上に横棒（¯）を書いて表します。読み方は「ノットA」、「Aバー」、「Aの否定」、「Aの反転」などです。ただこれをここに表記するのは難しいので￢Aと書くことにします。NOT演算は次の通りです。

　NOT演算の真理値表は次の通りです。

　論理回路ではNOT演算を行う回路は次の回路記号であらわされます。

　この図は左側が入力で右側が出力を表します。三角形（▷）はバッファ（入力と出力が同じ処理で、論理演算としては意味はありませんが、電子回路の入出力ゲートとして記述されることがあります）を表す記号で、否定を意味するのは三角形の前についている小さな○です。他の論理ゲートの入出力にも小さな○が付いていることがありますが、これらは全て否定（値の反転）を意味します。

■　OR演算
　変数A、BのOR演算はA＋Ｂで表され、「AオアB」、「AまたはB」などと読みます。論理演算はA、Bのいずれかでも１なら、出力は1、両方とも1でも1、入力が何れも0の場合に、出力が0となります。真理値表は次の通りです。

　（A、B）＝（0、0）、（1、0）、（0、1）の場合は、公理3のbから導くことができます。（A、B）＝（1、0)、（0、1）、（1、1）の場合は、公理2のbから導くことができます。

　OR演算の論理回路記号は次の通りです。

■　AND演算
　変数A、BのAND演算はA・Bまたは演算記号を省略してABと表し、「AアンドB」、「AかつB」などと読みます。AND演算は2つの入力がともに1の場合だけ、出力が1になります。入力に1つでも0が入れば、結果は0となります。

　（A、B）＝（0、0）、（1、0）、（0、1）の場合は、公理2のａから導くことができます。（A、B）＝（1、0）、（0、1）、（1、1）の場合は、公理3のaから導くことができます。

　AND演算の回路記号は次の通りです。

1．2　ブール代数の基本的な性質－定理

　ブール代数の演算において基本となる定理及び法則をまとめたものを次に示します。これらはNOT演算、OR演算、AND演算の公理から導くことができます。

　以上の定理は変数に全ての値の組み合わせを代入することで証明することができます。例としてドモルガンの定理のaについて真理値表を作成して証明してみたいと思います。

　式の変形で証明することももちろんできます。分配律aは次のように証明できます。

　A＋BC＝A（1＋C）＋BC＝A＋AC＋BC＝A（1＋B）＋AC＋BC＝AA＋AB＋AC＋BC＝A（A＋B）＋C（A＋B）＝（A＋B）（A＋C）

　共有項律も見た目が少しわかりにくいと思いますので、上のように式の変形をしてみたいと思います。

共有項律a）　A＋（￢A）B＝A（1＋B）＋（￢A)B＝A＋AB＋（￢A)B＝A＋（A＋￢A）B＝A＋B
※1＝1＋B、A＋￢A＝1より

共有項律b）　A（￢A＋B）＝A（￢A）＋AB＝AB
※A（￢A）＝0より

共有項律c）　AB＋BC＋（￢A）C＝AB＋BC（A＋￢A）＋（￢A)C＝AB（1＋C）＋（￢A）C（B＋1）＝AB＋（￢A）C
※A＋￢A＝1、1＋C＝1、1＋B＝1より

共通項律d）　（A＋B）（B＋C）（￢A＋C）＝（￢AA＋AC＋￢AB＋BC）（B＋C）＝（AC＋￢AB＋BC）（B＋C）＝ABC＋ACC＋￢ABB＋￢ABC＋BBC＋BCC＝（A＋￢A）BC＋AC＋￢AB＋BC＋BC＝BC＋￢AB＋AC＝B（￢A＋C）＋AC＋￢AA＝B（￢A＋C）＋A（￢A＋C）＝（A＋B）（￢A＋C）
※￢AA＝0、A＋￢A＝1より

1．3　論理演算と論理回路

　論理回路ではNOT、OR、AND回路が基本ですが、実際によく利用されるのはNAND（NOT-AND、否定論理積）や、XOR（eXclusive-OR、排他的論理和）です。

　NANDの真理値表は次のようになります。

　AND回路とNOT回路を組み合わせるとNAND回路となります。ドモルガンの定理を使うと、￢（AB）＝￢A＋￢Bとなりますので、OR回路とNOT回路の組み合わせでも実現できます。

　XORは入力がいずれかが1で、もう一方が0の場合のみ出力が1となり、入力が、ともに1、ともに0の場合は、何れも出力が0となります。記号は⊕が使用されます。真理値表は次のようになります。

　A⊕B＝￢A・B＋A（￢B）＝￢A・B＋￢A・A＋A（￢B）＋￢B・B＝￢A（A＋B）＋￢B（A＋B）＝（A＋B）（￢A＋￢B）＝（A＋B）（￢（A・B））
となりますので、排他的論理和はOR回路と、NAND回路の組み合わせで実現できます。

　否定、論理積、論理和、否定論理積、排他的論理和などいろいろあると、回路が複雑になり、工業的には効率的ではありません。一種類の回路で作ると、生産過程がシンプルになるだけでなく、面積当たりの回路数という意味でも、効率的にICの設計ができます。実は、NANDを使うと、NOT回路、AND回路、OR回路の何れも設計することが可能です。従って、実際ICでは、NOT回路も、AND回路も、OR回路もNANDで設計されています。

　NANDでNOTを作る場合は、￢（A・A）＝￢Aとなります。これを回路記号を使って表すと、次のようになります。

　NANDでOR回路を作る場合は、￢[￢（A・A）・｛￢（B・B）｝]＝￢｛￢A・（￢B）｝＝A＋B　となります（ドモルガンの定理bより）。これを回路記号を使って表すと、次のようになります。

　NAND回路でAND回路を作る場合は、￢[￢（A・B）｛￢（A・B）｝]＝A・B＋A・B＝A・B（ドモルガンの定理とべき等律）となります。これを回路記号を使って示すと、次のようになります。

1．4　半加算器の設計

　ブール代数に少し慣れたと思いますので、半加算回路について考えてみたいと思います。

　半加算器の真理値表は次のようになります。入力はA、Bで和はS₀、桁上りはC₀です。

　これを論理式に表すと、S₀＝A（￢B）＋￢A（B）＝A⊕B、C₀＝ABとなります。これを回路記号を使って表現すると次のようになります。

　排他的論理和の回路記号を使って、S₀＝A⊕B、C₀＝ABで回路図を書くと次のようになります。

　S₀＝A（￢B）＋￢A（B）、C₀＝ABで回路を作ると、次のようになります。

　AND回路をNAND回路に置き換えると次のようになります。

S₀＝A⊕B＝￢A・B＋A（￢B）＝￢A・B＋￢A・A＋A（￢B）＋￢B・B＝A（￢A＋￢B）＋B（￢A＋￢B）＝￢（A・B）A＋￢（A・B）B＝￢[￢｛￢（A・B）・A｝][￢｛￢（A・B）・B｝]

C0＝A・B＝￢（￢（A・B））

となりますので、NAND回路（とNOT回路）だけで構成すると、次のようになります。

　半加算器は下位ビットからの桁上りを取り入れることができません。下位ビットからの桁上りをCn-1とすると、真理値表は次のようになります。

　この真理値表から論理式を導き出すのは少し難しいようです。このような場合に役に立つのがカルノー図です。

2　カルノー図

		F
		0	1
E	0
	1

3　順序回路

3．1　RS-FF（リセットフリップフロップ）

Tweet

ネットワーク超入門講座 セキュリティ編【電子書籍】[ 久米原 栄 ] 価格:2,268円 (2018/1/21 11:07時点) 感想(0件)

更新履歴