デジタル回路/論理代数 - nkym_memo @ ウィキ

論理と命題

• 命題(proposition) １つの判断を述べた文章があって、それが正しいか正しくないかを考える対象

• 真(true)/偽(false) 命題が正しい/正しくないことの表現

• 複合命題(compound proposition) ２つ以上の命題が結合された命題

ブール代数

• ２値論理(binary logic) ２つの集合のいずれか属するかのみで真/偽の判断を行う論理

  例)
  「彼は20歳以上である」という命題において、彼の年齢は9,10,11,…69,70…と幾通りも存在する。
   だが、この命題において彼の年齢には興味がない(彼が9歳の男の娘だろうが39歳のｵｻｰﾝだろうが)
   20歳以上かということのみが問題となっていることを、２値論理という。
  

• ２値論理演算(binary logical operation) ２値論理による命題の処理を行う方法

• ブール代数(Boolean algebra) 論理和、論理積、論理否定の３つによる代数。George Boole(1815-1864,享年49,英)による。微分方程式と差分についてすごいみたい。

論理積(logical product,AND)

複合命題を構成する各命題がすべて真のとき複合命題が真になり、それ以外では偽となる。 論理記号：「・」

Y = A・B

論理和(OR)

複合命題を構成する各命題が１つでも真のとき複合命題が真になり、それ以外のとき、つまり各命題がすべて偽の時だけ偽となる。 論理記号「＋」

Y = A＋B

論理否定(NOT)

真ならば偽と判断し、偽ならば真と判断する。 論理記号「¬」

¬A(Aバーと読む)

基本法則

• 交換則

  A・B = B・A
  A＋B = B＋A
  

• 吸収則

  A・1 = A
  A・0 = 0
  A＋1 = 1
  A＋0 = A
  

• 結合則

  (A・B)・C = A・(B・C)
  (A＋B)＋C = A＋(B＋C)
  

• 分配則

  A・(B＋C) = A・B＋A・C
  A＋B・C = (A＋B)・(A＋C)
  

• 対合則

  ¬¬A = A
  

• 補元則

  A・¬A = 0
  A＋¬A = 1
  

• 同一則

  A・A = A
  A＋A = A
  

de Morgan(ド・モルガン）の定理

¬(A＋B) = ¬A・¬B

¬(A・B) = ¬A＋¬B

論理式の算出

1. 回路の動作を表す真理値表を作成
2. 真理値表から論理式を算出
3. 論理式を簡単化(加法標準形,乗法標準形)

真理値と真理値表

• 真理値(true value) 真/偽に対応する1/0

• 真理値表(truth table) 命題を表現した表

真理値表の作成手順

• 例として、入力変数を３個、出力が１個の多数決判定

1. 入力変数A,B,Cに対してその組み合わせ８通りの行をつくる 左端Cは表の半分が0/1 中央Bはその半分が0/1 右側Aはその半分が0/1(交互に0/1ともいえる)

C	B	A		Y
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

1. 入力の組み合わせを考慮して、真理値をYに入力する（ここでは1が２つ以上)

C	B	A		Y
0	0	0		0
0	0	1		0
0	1	0		0
0	1	1		1
1	0	0		0
1	0	1		1
1	1	0		1
1	1	1		1

加法標準形(disjunctive canonical form)

1. 出力が'1'の時の入力の組み合わせをすべて選び出す 上の多数決回路のとき

   A='0', B='1', C='1'
   A='1', B='0', C='1'
   A='1', B='1', C='0'
   A='1', B='1', C='1'
   

2. (1)の組み合わせにおいて、各入力の値が'1'のときはそのまま、'0'のときはNOTをしてANDで結合する

   A¬・B・C
   A・B¬・C
   A・B・C¬
   A・B・C
   

3. (2)の各AND項をORで結合します

   Y＝A¬・B・C＋A・B¬・C＋A・B・C¬＋A・B・C
   

乗法標準形(conjunctive canonical form)

1. 出力が'0'の時の入力の組み合わせをすべて選び出す 上の多数決回路のとき

   A='0', B='0', C='0'
   A='0', B='0', C='1'
   A='0', B='1', C='0'
   A='1', B='0', C='0'
   

2. (1)の組み合わせにおいて、各入力の値が'0'のときはそのまま、'1'のときはNOTをしてORで結合する

   A＋B＋C
   A＋B＋C¬
   A＋B¬＋C
   A¬＋B＋C
   

3. (2)の各AND項をANDで結合します

   Y＝(A＋B＋C)・(A＋B＋C¬)・(A＋B¬＋C)・(A¬＋B＋C)
   

論理式の簡単化

真理値表から加法標準形、乗法標準形による論理式には無駄が含まれる。 デジタル回路の動作速度向上および部品点数の削減のため、簡単化(simplification)を行う

基本法則による簡単化

前述のブール代数の基本法則によって簡単化する

• カット・アンド・トライ(cut and try)法
• トライアル・アンド・エラー(trial and error)法

と呼ばれる。

カルノー図による簡単化

実際の設計における論理式の簡単化はカルノー図(karnaugh map)で行うことが多い http://www.page.sannet.ne.jp/je3nqy/degital/losic5.htm

---

参考文献

• VHDLによるディジタル回路入門(並木秀明,永井亘道,技術評論社,2006)