論理回路 ( 基礎 ) 法政大学 情報科学部 大森健児
参考書
論理演算 () AND,OR,NOT,XOR AND OR NOT XOR
論理演算 (2) NAND,NOR NAND NOR
前提 結論 If A then B は A が真のとき B が真であるならば この文は真であり A が偽のときは B が真であろうとなかろうとこの文は真である A が真のとき B が偽であればこの文は偽である すなわち A +B である
論理ゲート
半加算器 A B 和 桁上り
全加算器 A B 繰上り 和 桁上り
半加算器より全加算器を A B 半加算器 繰上り 半加算器 OR 桁上り C
論理式の変形 () Constant X+=X, X+=, X*=X, X*= Idempotent X+X=X, X*X=X Involution (X ) =X Complementary X+X =, X*X = Commutative X+Y=Y+X, X*Y=Y*X
論理式の変形 (2) Associative (X+Y)+Z=X+(Y+Z), (X*Y)*Z=X*(Y*Z) Distributive X*(Y+Z)=X*Y+X*Z, X+(Y*Z)=(X+Y)*(X+Z) Simplification X*Y+X*Y =X, (X+Y)*(X+Y )=X X+X*Y=X, X*(X+Y)=X (X+Y )*Y=X*Y, (X*Y )+Y=X+Y
論理式の変形 (3) DeMorgan s (X+Y+Z+ ) =X *Y *Z * (X*Y*Z* ) =X +Y +Z + Multiplying & Factoring (X+Y)*(X +Z)=X*Z+X *Y X*Y+X *Z=(X+Z)*(X +Y)
例 Theorem (Idempotent): (a) a + a = a (b) aa = a Theorem 2 (Constant): (a) a + = (b) a = Theorem 3 (Involution) a = a Properties of and elements: OR AND Complement a + = a = ' = a + = a = a ' =
例 2 Theorem 4 (Absorption) (a) a + ab = a (b) a(a + b) = a Examples: (X + Y) + (X + Y)Z = X + Y [T4(a)] AB'(AB' + B'C) = AB' [T4(b)] Theorem 5 (a) a + a'b = a + b (b) a(a' + b) = ab Examples: B + AB'C'D = B + AC'D [T5(a)] (X + Y)((X + Y)' + Z) = (X + Y)Z [T5(b)]
例 3 Theorem 6 (a) ab + ab' = a Examples: ABC + AB'C = AC [T6(a)] (b) (a + b)(a + b') = a (W' + X' + Y' + Z')(W' + X' + Y' + Z)(W' + X' + Y + Z')(W' + X' + Y + Z) = (W' + X' + Y')(W' + X' + Y + Z')(W' + X' + Y + Z) [T6(b)] = (W' + X' + Y')(W' + X' + Y) [T6(b)] = (W' + X') [T6(b)]
例 4 Theorem 7 (a) ab + ab'c = ab + ac (b) (a + b)(a + b' + c) = (a + b)(a + c) Examples: wy' + wx'y + wxyz + wxz' = wy' + wx'y + wxy + wxz' [T7(a)] = wy' + wy + wxz' [T7(a)] = w + wxz' [T7(a)] = w [T7(a)] (x'y' + z)(w + x'y' + z') = (x'y' + z)(w + x'y') [T7(b)]
例 5 Theorem 8 (DeMorgan's Theorem) (a) (a + b)' = a'b' (b) (ab)' = a' + b' Generalized DeMorgan's Theorem (a) (a + b + z)' = a'b' z' (b) (ab z)' = a' + b' + z' Examples: (a + bc)' = (a + (bc))' = a'(bc)' [T8(a)] = a'(b' + c') [T8(b)] = a'b' + a'c' Note: (a + bc)' a'b' + c'
例 6 More Examples for DeMorgan's Theorem (a(b + z(x + a')))' = a' + (b + z(x + a'))' [T8(b)] = a' + b' (z(x + a'))' [T8(a)] = a' + b' (z' + (x + a')') [T8(b)] = a' + b' (z' + x'(a')') [T8(a)] = a' + b' (z' + x'a) [T3] = a' + b' (z' + x') [T5(a)]
例 7 More Examples for DeMorgan's Theorem (a(b + c) + a'b)' = (ab + ac + a'b)' = (b + ac)' [T6(a)] = b'(ac)' [T8(a)] = b'(a' + c') [T8(b)]
例 8 Theorem 9 (Consensus) (a) ab + a'c + bc = ab + a'c (b) (a + b)(a' + c)(b + c) = (a + b)(a' + c) Examples: AB + A'CD + BCD = AB + A'CD [T9(a)] (a + b')(a' + c)(b' + c) = (a + b')(a' + c) [T9(b)] ABC + A'D + B'D + CD = ABC + (A' + B')D + CD [P5(b)] = ABC + (AB)'D + CD [T8(b)] = ABC + (AB)'D [T9(a)] = ABC + (A' + B')D [T8(b)] = ABC + A'D + B'D
標準形 積和標準形 (Sum of Products) 例 ABC+BC D+A CD 和積標準形 (Product of Sums) 例 (A+B+C)(B+C +D)(A +C+D) 項という 項という
スイッチング関数 スイッチング代数 : 要素 K = {, } の集合を持つブール代数 2 n 変数では 2n の関数が存在する AB f f f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f f f 2 f 3 f 4 f 5 スイッチング関数は上の表で または下の論理式で表わす ( インデックスの 2 進数が関数の値に対応 ) f (A,B)=, f 6 (A,B) = AB' + A'B, f (A,B) = AB + A'B + A'B' = A' + B,...
真理表 () ab f(a,b)=a+b ab f(a,b)=ab a f(a)=a'
真理表 (2) f(a,b,c) = AB + A'C + AC' ABC f(a,b,c) ABC f(a,b,c) FFF F FFT T FTF F FTT T TFF T TFT F TTF T TTT T
最小項 最大項 積の項が全ての変数をそれぞれひとつだけ含んでいるとき その項を最小項という 和の項が全ての変数をそれぞれひとつだけ含んでいるとき その項を最大項という 最小項だけからなる積和標準形を主加法標準形という 最大項だけからなる和積標準形を主乗法標準形という
最小項と最小項のコード 主加法標準形 : 最小項の和として表す. 例 : f (A,B,C) = A'BC' + ABC' + A'BC + ABC 3 変数での最小項 Minterm Minterm Code Minterm Number A'B'C' m A'B'C m A'BC' m 2 A'BC m 3 AB'C' m 4 AB'C m 5 ABC' m 6 ABC m 7
主加法標準形 Shannon's expansion theorem (a). f(x, x 2,, x n ) = x f(, x 2,, x n ) + (x )' f(, x 2,, x n ) (b). f(x, x 2,, x n ) = [x + f(, x 2,, x n )] [(x )' + f(, x 2,, x n )] 例 f(a,b,c) = AB + AC' + A'C = A f(,b,c) + A' f(,b,c) = A( B + C' + ' C) + A'( B + C' + ' C) = A(B + C') + A'C = B[A(+C') + A'C] + B'[A( + C') + A'C] = B[A + A'C] + B'[AC' + A'C] = AB + A'BC + AB'C' + A'B'C = C[AB + A'B + AB' ' + A'B' ] + C'[AB + A'B + AB' ' + A'B' ] = ABC + A'BC + A'B'C + ABC' + AB'C インデックスは最小項の値を2 進数 = Σm(, 3, 4, 6, 7) = f + f 3 + f 4 + f 6 + f 7 で表わしたもの
最大項と最大項のコード 主乗法標準形 : 最大項の積として表す 例 : f 2 (A,B,C) = (A+B+C)(A+B+C')(A'+B+C)(A'+B+C') 3 変数での最大項 最小項と逆であることに注意 Maxterm Maxterm Code Maxterm Number A+B+C M A+B+C' M A+B'+C M 2 A+B'+C' M 3 A'+B+C M 4 A'+B+C' M 5 A'+B'+C M 6 A'+B'+C' M 7
ゲート回路 (TTL) NAND 74(2 入力 ),74(3 入力 ),742(4 入力 ),743(8 入力 ) NOT 744 AND 748(2 入力 ) OR 7432(2 入力 ) XOR 7486(2 入力 )
電気信号と論理値 正論理 負論理 論理値 に設定されている信号はアクティブ 真などといわれる 正論理では信号がハイのとき真である 負論理では信号がローのとき真である
ゲート回路の表記 a AND f(a, b) = ab b a OR f(a, b) = a + b b NOT a f(a) = a a NAND f(a, b) = ab b a NOR f(a, b) = a + b b EXCLUSIVE a f(a, b) = a b OR b Symbol set AND OR NOT a b a b a b a NAND b NOR a b EXCLUSIVE a OR b Symbol set 2 (ANSI/IEEE Standard 9-984) & ³ & ³ = f(a, b) = ab f(a, b) = a + b f(a) = a f(a, b) = ab f(a, b) = a + b f(a, b) = a b
ゲート回路 (IC) Vcc 4B 4A 4Y 3B 3A 3Y 4 3 2 9 8 Vcc 4Y 4B 4A 3Y 3B 3A 4 3 2 9 8 2 3 4 5 A B Y 2A 2B 6 2Y 7 GND 74: Y = AB Quadruple two-input NAND gates 2 3 4 5 Y A B 2Y 2A 6 2B 742: Y = A + B Quadruple two-input NOR gates 7 GND Vcc 6A 6Y 5A 5Y 4A 4Y 4 3 2 9 8 Vcc 4B 4A 4Y 3B 3A 3Y 4 3 2 9 8 2 3 4 5 A Y 2A 2Y 3A 744: Y = A Hex inverters 6 3Y 7 GND 2 3 4 5 A B Y 2A 2B 6 2Y 748: Y = AB Quadruple two-input AND gates 7 GND
ゲート回路 (IC) Vcc C Y 3C 3B 3A 3Y 4 3 2 9 8 Vcc 2D 2C NC 2B 2A 2Y 4 3 2 9 8 2 3 A B 2A 2B 2C 4 5 6 2Y 74: Y = ABC Triple three-input NAND gates 7 GND 2 3 A B NC C D 4 5 6 Y 742: Y = ABCD Dual four-input NAND gates 7 GND
ゲート回路 (IC) Vcc NC H G NC NC Y 4 3 2 9 8 Vcc 4B 4A 4Y 3B 3A 3Y 4 3 2 9 8 2 3 A B C D E 4 5 743: Y = ABCDEFGH 8-input NAND gate 6 F 7 GND 2 3 A B Y 2A 2B 4 5 6 2Y 7432: Y = A + B Quadruple two-input OR gates 7 GND Vcc 4B 4A 4Y 3B 3A 3Y 4 3 2 9 8 2 3 A B Y 2A 2B 4 5 6 2Y 7 GND 7486: Y = A Å B Quadruple two-input exclusive-or gates
AND AND a b f AND (a, b) =ab A B Y L L H H L H L H L L L H A B A B (c) & Y Y (a) (b) (d) (a) AND logic function. (b) Electronic AND gate. (c) Standard symbol. (d) IEEE block symbol.
OR OR a b f OR (a, b) =a + b A B Y L L H H L H L H L H H H A B A B (c) Y Y (a) (b) (a) OR logic function. (b) Electronic OR gate. (c) Standard symbol. (d) IEEE block symbol. (d)
NOT NOT A Y a fnot(a) =a A Y (c) L H H L A Y (a) (b) (d) (a) NOT logic function. (b) Electronic NOT gate. (c) Standard symbol. (d) IEEE block symbol.
負論理 () 負論理での ANDゲートの利用 A B Y (a) A B (b) Y a b a b (c) (d) y = a + b y = ab a b= a+ b = f OR ( a, b ) y= ( a) + ( b ) = a+ b= for( a, b)
負論理 (2) 負論理での ORゲートの利用 A B Y (a) A B (b) Y a b a b (c) (d) y = ab y = a + b y= a+ b= a+ b= a b = f AND y= ( a) ( b ) = a b= fand( a, b) ( a, b )
煙検知器 例 : 煙検知器 部品 : 2 個の煙検知器 スプリンクラー 警報機 動作 : いずれかの検知器が煙を検知したときはスプリンクラーが作動 両方のときは警報機がなる Signals: : 検知器の出力はローのときアクティブ : スプリンクラーの入力はローのときアクティブ : 警報機の入力はローのときアクティブ SPK = D+ D2 DIAL= D D2 D, D2 SPK DIAL
煙検知器 Logic diagram of the smoke alarm system Smoke detectors D D2 G D + D2 Sprinkler SPK G2 D D2 Telephone dialer DIAL
NAND NAND a b fnand(a, b) =ab (a) A B Y L L L H H L H H (b) H H H L A B Y A B Y A B & Y (c) (d) (e) (a) NAND logic function (b) Electronic NAND gate (c) Standard symbol (d) IEEE block symbol
NAND AND, OR, NOT は NAND から合成可 a b ab f(a, b) = ab = ab a f(a, a) = a a = a AND gate NOT gate a b a b OR gate f(a, b) =a + b = a + b
NOR NOR a b f NOR (a, b) =a + b (a) A B Y L L L H H L H H (b) H L L L A B Y A B Y A B ³ Y (c) (d) (e) (a) NAND logic function (b) Electronic NAND gate (c) Standard symbol (d) IEEE block symbol
NOR AND, OR, NOT は NOR から合成可 a b a + b f(a, b) =a + b a f(a, a) =a + a = a OR gate NOT gate a b a b AND gate f(a, b) =ab = ab
XOR Exclusive-OR (XOR) a b a b+ ab f XOR (a, b) = a b A B Y L L L L H H H L H H H L A B Y (a) XOR logic function A B = Y (b) Electronic XOR gate (c) Standard symbol (d) IEEE block symbol
パリティー回路 または を取る信号を並列に 4 つ入力し の数が奇数であるとき を そうでないとき を出力する回路の論理式を積和標準形で示しなさい また NAND だけを使った論理式も示しなさい なお 入力は A,B,C,D とし 出力は X とする
エンコーダ つだけが をとり 他は をとる 4 つの信号を並列に入力し これを 2 進数に変える回路を考えなさい なお 入力は A,B,C,D とし ビットはこの順に並んでおり A は最下位とする また 出力は X,Y とし X を最下位とする さらに A が のとき YX=, B が のとき YX=, C が のとき YX=, D が のとき YX= とする また が つでないときは Valid Bit が になるものとし そうでないときは になるものとする