Download presentation
Presentation is loading. Please wait.
1
第３回 論理式と論理代数 本講義のホームページ：
ユーザ名： tcu パスワード： seto
2
ディジタル回路の回路図作成の注意 回路記号はテンプレートを使用し、丁寧に書くこと 必ず入力名 a b c 出力 0 0 0 0 0 1
1 a b c 必ず出力名 交点に 黒丸を 付ける 順番 昇順 f はみ出さない 線は定規で書く
3
論理否定の良く使われる省略記法 論理否定(NOTゲート): 下の二つはどちらも同じ意味 NOTゲートは、小さな白丸（○）の省略表現可能
ゲートの前後にくっつける ２重否定により，以下の２つの白丸は削除可能 x x x x こちらのほうがよく使われる
4
関数とは? （復習） 函数とも書く （「 はこ 」の数） 例えば，
関数とは? （復習） 函数とも書く （「 はこ 」の数） 入力を与えると，出力が１つ決まる 例えば， 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= , ... 函数 （はこ） 入力 x 出力 y=f(x)
5
論理 関数(式)： 組合せ回路の機能を表す 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
6
基本論理演算の記号 （復習） 通常の関数で，四則演算 (＋, －, ×, ÷)に対応 論理積 (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 通常の足し算と 異なるので注意
7
XORも比較的よく出現します XOR (eXclusive OR, 排他的論理和) A B XOR 1 B Y= A+B A
8
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 論理関数
9
３入力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ゲート２個で実現可能
10
≠ A・B A・B 論理否定の注意点 論理否定の付け方は，要注意！ 例えば，A=0, B=1のとき， A・B = 0 A・B = 1 A A
11
論理式について，少々用語説明を リテラル (literal) 二値変数 A に対して、その肯定形か否定形 例： A または A のこと
積項(product term) ２つ以上のリテラルの論理積 例： 積和形 複数の 積項 の論理和で表現された論理式 A・B + A・B・C A・B
12
積和形 ⇔ 組合せ回路 （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
13
組合せ回路、真理値表、論理式の関係 組合せ回路 論理式 真理値表 互いに，変換可能
14
論理積の記号は省略できます 例： 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
15
論理式の簡単化による組合せ回路の最適化 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
16
ブール代数の公式 （１） （回路変形に利用可能, 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 実数の＋，×で 当たり前の法則 ブール代数（＋，・） 特有の性質
17
ブール代数の公式 （２） （式変形，回路変形に利用可能）
ブール代数の公式 （２） （式変形，回路変形に利用可能） 二重否定 x = x ドモルガンの定理 (x+y)= x・y (x・y)= x+y 吸収律 x+x・y = x x・(x+y)= x ブール代数 独特の性質 重要な注意： 論理式には，”2xy”とかは出てこない
18
公式による，ディジタル回路の変形 交換則 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
19
公式とゲート回路との対応 (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
20
ドモルガンの定理 （復習） ドモルガン(Augustus De Morgan, 1806-1871，英) 以下の回路変形が可能
ドモルガンの定理 （復習） ドモルガン(Augustus De Morgan, ，英) 数学的帰納法の名付け親 以下の回路変形が可能 ANDゲートを，ORゲートに ORゲートを，ANDゲートに (x+y) x・y (x・y) x+y
21
完全性とは？ {AND, OR, NOT} 「完全性」 を持つ ⇔ AND, OR, NOTゲートで， 任意 の組合せ回路を実現 C B A
Y 1 Y
22
{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} も完全
23
論理式なので，部分式の値は，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または１しかないことに注意 （２とか３が出てきたら，間違い！）
24
まとめ 論理関数，論理式 完全系 任意の組合せ回路が実現可能なゲートの集まり
括弧()，論理積・, 論理和＋, 論理否定 を使った式 変数は，２値 (0, 1)，関数（式）の値も，２値(0, 1) 組合せ回路の機能を表す 公式を紹介 完全系 任意の組合せ回路が実現可能なゲートの集まり {NAND},{NOR},{AND, NOT},{OR,NOT},{XOR,AND}
Similar presentations
