Document

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

Download Report