コンピュータアーキテクチャI #3 二変数論理関数 本日の講義内容 主な

本日の講義内容

ブール代数

二変数論理関数
– 土・モルガンの法則の証明(真理値表を使って)
コンピュータアーキテクチャI #3
二変数論理関数
– 二変数論理関数の種類
– 完全系
– ブール代数による項の整理
平成27年4月24日
教科書p.17~p.40
主なブール代数の定理(4)

2変数論理関数とは
任意の元 , に対し,次のド・モルガンの定理が成
立する
̅⋅
2つの論理変数A,Bから組み立てられる関数
̅
⋅
○
⋅
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
0
0
1
0
1
1
1
0
0
0
0
⋅
⋅
1
1
1
1



0
0
0
0
1
0
1
1
0
1
1
0
0
1
0
1
1
1
1
1
0
0
0
0
2変数論理関数のパターン
1
1
0
0
A
1
1
0
#0:
B
1
0
1
0
B
1
0
1
0
0
0
0
0
#8
1
0
0
0
#1
0
0
0
1
#9
1
0
0
1
#2
0
0
1
0
#10
1
0
1
0
#3
0
0
1
1
#11
1
0
1
1
#4
0
1
0
0
#12
1
1
0
0
#5
0
1
0
1
#13
1
1
0
1
#6
0
1
1
0
#14
1
1
1
0
#7
0
1
1
1
#15
1
1
1
1
,
1,0 のときのみ
1となる2変数関数
,
–
–
0
#0
Ex) #4は
A,Bはそれぞれ0,1の値をとりうるので,4通りの
入力パターンがある
ある入力パターンに対して,出力は0,1の2通り
24=16通りの「2変数論理関数」があると共に,そ
れ以上は存在しない
2変数論理関数

A
,
–
–
0,0
–
1
0,1
1
⋅
#3:

0
ORの否定に等しい.“NOR” (Not-OR)と呼ばれる
#2:

のいろいろ(1)
,
入力に関わらず出力が0
定数0
#1:

○には何か論理演算子が入る
0,1
0,0
1
が0のときのみ1なので, の否定に等しい
を表す
1
2変数論理関数

#4:
1,0
のいろいろ(2)
,
1
2変数論理関数

#5:
–

1,0
0,0
1

#6:
1,0
0,1
#7:
1,0
1

0,1
0,0
#9:
1
1,1
–
が0のときのみ1なので, の否定に等しい
–
– 排他的論理和(XOR, EOR)と言われ, ⨁ で表す

1,1
– AND( ⋅ )
–

#8:
のいろいろ(3)
,
#10:
–

1
0,0
⋅
1
⊕
1,1
0,1
1
に関わらず, の値に等しいので,単に
#11:
1,1
0,1
0,0
1
–
– , 共に1以外は1なので,ANDの否定に等しい
– NANDと呼ばれる
2変数論理関数

#12:
–

1,1
のいろいろ(4)
,
1,0
1

に関わらず出力は に等しいので,単に
#13:
1,1
1,0
0,0
#14:

1,1
1,0
0,1
#15:
1,1
1,0
0,1
0,0
他に完全系を成す演算(素演算)はあるか?
– NAND, NORは単独で完全系をなす
– NOTとAND, NOTとORも完全系をなす
1
– か のどちらか一方でも1ならば出力は1
– 論理和(OR)である

2変数論理関数16種類
– AND, OR, NOTがあればすべて表現できる
– 上記3演算をもって「完全系」をなす,という
1
–

完全系
1
– 入力に関わらず出力が1
– 定数1
単一演算子による完全系:NOR


NOR:
⋅
NORを使った論理演算
– NOT:
NAND: ⋅
NANDを使った論理演算
– NOT:
‖
⋅


‖
– OR:
– AND :
‖
単一演算子による完全系:NAND
‖
‖
‖
‖
‖
– AND:
– OR:
|
⋅
|
1|
|
|
|
|
|
2
最小項と最大項

加法標準形と乗法標準形
最小項

– すべての論理変数が真,または偽の形で含まれている論
理積項

–
–
–
–
ex)
(論理)積を各項に,それを(論理)和で結んだ形
「加法標準形」という
真理値が0となる項も含めて書くと「主加法標準形」と
呼ばれる
– (論理)和項を(論理)積で結んだ形は「乗法標準形」と呼
ばれる
最大項
– すべての論理変数が真,または偽の形で含まれている論
理和項
多変数論理関数の表現

論理関数の簡単化とは
主加法標準形

個の論理変数を持つ論理変数 について,
–
, ,⋯,
0,0, ⋯ , 0,0
0,0, ⋯ , 0,1
0,0, ⋯ , 1,0
⋯
⋯
⋯
⋯
論理式の項数を少なくすること
– ド・モルガンの定理や各種ブール代数の公理・定理を駆使
して項数を減らす
論理最小項
今まで書いてきた論理式

論理式で使われている演算子を統一すること
– 完全系を成すNANDやNORのみで論理式を記述し,必要
な部品の種類を減らす
⋯
1,1, ⋯ , 1,1
– 論理積の和,と言う形で表現する.
– すべての入出力の組合せを列挙する.
論理式の簡単化の例(1)

与えられた論理式:
–
論理式の簡単化の例(2)

与えられた論理式:
–
–
–
–

–
–
3
簡単化の練習

本日のまとめと来週の予定
次の論理式を簡単化しなさい
–

–
–
–
–

–
⋅
ブール代数の基礎
ブール代数と定理
二変数論理関数
完全系
ブール代数を利用した項の整理
来週の予定(5月1日)
– ブール代数演習
– 単元テスト
4