第３回 論理式と論理代数 本講義のホームページ： http://www.ee.tcu.ac.jp/lectures/digital/index.html ユーザ名： tcu　　　パスワード： seto

ディジタル回路の回路図作成の注意 回路記号はテンプレートを使用し、丁寧に書くこと 必ず入力名 a b c 出力 0 0 0 0 0 1 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 a b c 必ず出力名 交点に 黒丸を 付ける 順番 昇順 f はみ出さない 線は定規で書く

論理否定の良く使われる省略記法 論理否定(NOTゲート): 下の二つはどちらも同じ意味 NOTゲートは、小さな白丸（○）の省略表現可能 ゲートの前後にくっつける ２重否定により，以下の２つの白丸は削除可能 x x x x こちらのほうがよく使われる

関数とは? （復習） 函数とも書く （「 はこ 」の数） 例えば， 関数とは?　（復習） 函数とも書く　（「 はこ 」の数） 入力を与えると，出力が１つ決まる 例えば， y = f(x) = 2x (1変数， 1次関数): x=1 なら y=2 w = g(x,y,z) = 3x2+y+2z3 (2変数， 3次関数) 変数 x, y, z, y, w は，通常， 　実数 　 の範囲 x=0.1243, y=-3.333.., ... 函数 （はこ） 入力 x 出力 y=f(x)

論理 関数(式)： 組合せ回路の機能を表す C Y B A Y = A･B･C + A･B･C 論理　関数(式)：　組合せ回路の機能を表す 組合せ回路の入出力関係（ 真理値 表） ＝ “関数”そのもの 入力が決まると、出力が１つに決まる 信号の状態： 変数A,B,C,...で表現(0: 低い電圧，1: 高い電圧) 論理関数と呼ぶ 変数の値は ０ か １ どちらかだけ（２値変数） 対応する 真理値表 C B A Y 1 C 組合せ 回路 Y B A 本日学習する 対応する 論理関数（式) Y = A･B･C + A･B･C

基本論理演算の記号 （復習） 通常の関数で，四則演算 (＋, －, ×, ÷)に対応 論理積 (AND) A∙B 論理和 (OR) A+B 基本論理演算の記号　（復習） 通常の関数で，四則演算 (＋, －, ×, ÷)に対応 論理積 (AND) A∙B 論理和 (OR) A+B 論理否定 (NOT) A B A Y 1 B A Y 1 A Y 1 B B Y= A+B Y= A∙B A Y= A A A 通常の足し算と 異なるので注意

XORも比較的よく出現します XOR (eXclusive OR, 排他的論理和) A B XOR 1 B Y= A+B A

A∙B+C A∙(B+C) f(A,B,C)= A∙B+C 論理式と論理関数 論理式 括弧()，論理積・, 論理和＋, 論理否定　 , を組合せて作った式　 論理関数 (＝ 論理式) 論理式中の２値変数 に値を代入すると、式の値 (0, 1)が決まる 論理式で表される関数。　変数の値は，0または1 A∙B+C 論理式の例1 括弧と使うと，式の中の 計算順序を変更可能 A∙(B+C) 論理式の例2 f(A,B,C)= A∙B+C 論理関数

３入力ANDゲートを，2入力ANDゲート２個で実現可能 論理和，論理積 の　 結合　法則 加算（＋）や，乗算（×）で成立　（小学校で学習） (A＋B)＋C = A＋(B＋C)= A＋B＋C (A×B)×C = A×(B×C)= A×B×C 論理和（＋）や，論理積（・）でも，同様に成立 (A・B)・C = A・(B・C)= A・B・C A A A Y ＝ ＝ B Y B Y B C C C ３入力ANDゲートを，2入力ANDゲート２個で実現可能

≠ A・B A・B 論理否定の注意点 論理否定の付け方は，要注意！ 例えば，A=0, B=1のとき， A・B = 0 A・B = 1 A A

論理式について，少々用語説明を リテラル (literal) 二値変数 A に対して、その肯定形か否定形 例： A または A のこと 積項(product term) ２つ以上のリテラルの論理積 例： 積和形 複数の 積項 の論理和で表現された論理式 A・B + A・B・C A・B

積和形 ⇔ 組合せ回路 （AND・OR二段回路） 積和形は，組合せ回路を表す AND ・ OR 二段回路 とよぶ 積和形： Y = A・B・C + A・B・C + A・B・C 積項の数 ＝ AND ゲートの数 ＝ OR ゲートの入力数 A B C A・B・C A・B・C Y A・B・C

組合せ回路、真理値表、論理式の関係 組合せ回路 論理式 真理値表 互いに，変換可能

論理積の記号は省略できます 例： Y = A・B・C + A・B・C + A・B・C Y = ABC + ABC + ABC 注意：　ただし，２進表現と，論理積を，間違えるな！ 二進数：　A1 A0 A1 =0, A0=1のとき， 1 A1 =1, A0=1のとき， 3 論理積：　A1 A0 A1 =0, A0=1のとき， 0 A1 =1, A0=1のとき， 1 また，A B ≠ A B　であることにも注意 Y = A・B・C + A・B・C + A・B・C Y = ABC + ABC + ABC

論理式の簡単化による組合せ回路の最適化 y =((a・b)+c)+(c・b)・d a b ６個 実は　y　は、y’ =(a・b)+cと等しい(　等価　) 一つの論理式は、様々な論理式に変形できる 簡単な論理式を使えば、 ゲート数が削減可能 ⇒小面積（低コスト）、 ⇒省電力 ⇒高性能 a・b a (a・b)+c b y ６個 (c・b) c d (c・b)・d a 式簡単化の基礎 「論理（ブール）代数」 を学ぶ ２個 b y’ c

ブール代数の公式 （１） （回路変形に利用可能, x,yは任意の論理式） (1) 交換則 x・y = y・x x+y = y+x (2) 結合則 x・(y・z)=(x・y)・z x+(y+z)=(x+y)+z (3) 分配則 x・(y+z)=x・y+x・z 　x+(y・z)=(x+y)・(x+z) (4) 零元0、単位元1 x・0 = 0, x+1 = 1 (5) 補元 x 　x・x = 0, 　　x+x = 1　 実数の＋，×で 当たり前の法則 ブール代数（＋，・） 特有の性質

ブール代数の公式 （２） （式変形，回路変形に利用可能） ブール代数の公式　（２） （式変形，回路変形に利用可能） 二重否定 　x = x ドモルガンの定理 (x+y)= x・y (x・y)= x+y 吸収律 x+x・y = x x・(x+y)= x ブール代数 独特の性質 重要な注意：　論理式には，”2xy”とかは出てこない

公式による，ディジタル回路の変形 交換則 x x x・y = y・x y y 結合則 x・(y・z)=(x・y)・z x x 分配則 y y x・(y+z)=x・y+x・z x x y y x x y y z z x x y y z z

公式とゲート回路との対応 (ANDゲート版) 　x・x = x 　x・0 = 0 　x・1 = x 　x・x = 0 　x = x 配線 x x x x x 配線 x x x x 1 x 配線 x x x x

ドモルガンの定理 （復習） ドモルガン(Augustus De Morgan, 1806-1871，英) 以下の回路変形が可能 ドモルガンの定理　（復習） ドモルガン(Augustus De Morgan, 1806-1871，英) 数学的帰納法の名付け親 以下の回路変形が可能 ANDゲートを，ORゲートに ORゲートを，ANDゲートに (x+y) x・y (x・y) x+y

完全性とは？ {AND, OR, NOT} 「完全性」 を持つ ⇔ AND, OR, NOTゲートで， 任意 の組合せ回路を実現 C B A Y 1 Y

{NOR}, {AND, NOT}, {OR, NOT}, {AND, XOR} も完全 NANDゲートの完全性 NANDゲートだけで，任意の組合せ回路を実現可能 f = x∙x = x NANDゲート x x x x NOTゲート f y f = x∙y x x∙y ANDゲート y f = x∙y ド・モルガン x x∙y = x+y = x+y y ORゲート {NOR},　{AND, NOT},　{OR, NOT}, {AND, XOR}　も完全

論理式なので，部分式の値は，0または１しかないことに注意 公式による，論理式変形の例 (a+b)・(a+c)を展開する (a+b)・(a+c)= a・(a+c)+b・(a+c) (分配法則) = a・a+a・c+b・a+b・c (分配法則) = a+a・c+b・a+b・c (x・x=x) = a +b・a+b・c (x+x・y=x) = a +a・b+b・c (交換法則) = a +b・c (x+x・y=x) 論理式なので，部分式の値は，0または１しかないことに注意 （２とか３が出てきたら，間違い！）

まとめ 論理関数，論理式 完全系 任意の組合せ回路が実現可能なゲートの集まり 括弧()，論理積・, 論理和＋, 論理否定　 を使った式 変数は，２値 (0, 1)，関数（式）の値も，２値(0, 1) 組合せ回路の機能を表す 公式を紹介 完全系 任意の組合せ回路が実現可能なゲートの集まり {NAND},{NOR},{AND, NOT},{OR,NOT},{XOR,AND}