デジタル回路/論理代数

Last-modified: 2010-12-03 (金) 17:02:01

論理と命題

  • 命題(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　　　
  2. 入力の組み合わせを考慮して、真理値を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)