真理値表による証明
● 真理値表によってド・モルガン則を確かめてみよ う。
x y x y x·y x+y x·y x+y x·y x+y
0 0 1 1 0 0 1 1 1 1
0 1 1 0 0 1 1 0 0 1
1 0 0 1 0 1 1 0 0 1
1 1 0 0 1 1 0 0 0 0
基本論理演算と論理関数
●
AND, OR, NOT
演算の組み合わせだけでどんな 論理関数でも作ることができる。● 証明：引数の数に関する数学的帰納法
–
引数１つの時● 引数１つの論理関数は前述の通り４種類しかない。
f
0( x )= 0 = x ⋅̄ x f
1( x )= x
f ( x )=̄ x 成立
基本論理演算と論理関数
–
引数n
個のとき、引数n-1
個では成立を仮定● 任意の
n
変数論理関数– 次のn-1変数論理関数を考える
– ここで次の式を考える：「x=0ならa、x=1ならb」
f ( x
1, x
2, … , x
n)
g
0( x
1, x
2, … , x
n−1)= f ( x
1, … , x
n−1, 0 ) g
1( x
1, x
2, … , x
n−1)= f ( x
1, … , x
n−1, 1 )
̄ x a + x b
x a b xa xb xa+ab
1 0 0 0 0 0
1 0 1 0 1 1
1 1 0 0 0 0
x a b xa xb xa+ab
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 1 0 1
基本論理演算と論理関数
●
x
nの値によって関数を切り替える– x
n=0 ⇒
– x
n=1 ⇒
● 前ページの考察により、
● 仮定より
g
0とg
1はAND,OR,NOT
のみで表せるのf ( x
1, … , x
n−1, x
n)= g
0( x
1, … , x
n−1) f ( x
1, … , x
n−1, x
n)= g
1( x
1, … , x
n−1)
f ( x
1, … , x
n−1, x
n)= x
ng
0( x
1, … , x
n−1)+
x
ng
1( x
1, … , x
n−1)
演習
● 分配律が成立していることを真理値表で確かめ よ。
x ⋅( y + z )=( x ⋅ y )+ ( x ⋅ z ) x + ( y ⋅ z )=( x + y )⋅( x + z )
x y z xy xz y+z x(y+z) xy+xz
0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0
論理演算と論理素子
● ある論理演算を実現するための電子回路
（論理ゲート）
AND
ゲートOR
ゲートNOT
ゲートMIL 記号
論理演算と論理素子
● ゲートの端にある○が「反転」を表す
NAND
ゲートNOR
ゲートNOT
ゲート等価な論理ゲート
● ド・モルガン律などによる
＝
AB B
NAND ゲートは万能
●
NAND
ゲートですべてのゲートの代用ができる＝
＝
＝
x ⋅ x =̄ x
x ⋅ y = x ⋅ y
̄ x ⋅̄ y = x + y
NAND ゲートの実現例
●
Diode-Transistor Logic (DTL)
–
簡略化した回路図（実際はもう少し複雑）– DTL
は遅くて消費電力が大きいので、実際にはあまり 使われないV+ V+
V+ V+
V+ V+
H L
L
H
IN1 IN2 OUT
半導体でなくても論理ゲートは作れる
● リレーで作る論理ゲート
コイルに電流を流すと隣にある スイッチが
ON/OFF
S1 S2
S1とS2の両方がONの ときだけOFFになる
論理演算と論理回路
● 論理式⇔論理回路
● 例
Z = AB BC CA
A B
C Z
演習
● 次の論理式に基づく論理回路を描け。
S = X ⋅ Y X ⋅ Y
C = X ⋅ Y
X ?
Y
C
S
半加算器
● さっきの論理式の真理値表
X Y C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
X, Y
を１桁の２進数、CS
を２桁の２進数と見C: Carry （桁上げ）
S: Sum （和）
桁の多い加算
● ２桁以上の２進数の加算をするにはどうする？
–
桁上げを考慮⇒３つの２進数の和を計算しなければな らない–
３つの１桁の２進数a,b,c
を加算→２桁の２進数CS
a b c C S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
全加算器 (full adder)
● 半加算器の組み合わせで作れる
発展
● 前ページの回路の入出力関係がその前の真理値 表と同じになっていることを確かめよう
● ２ページ前の真理値表を直接表現する論理式を考 えてみよう
C = f ( a , b , c )
S = g ( a ,b , c )
桁の多い加算器
● 筆算と同じ要領（下から順に桁上げ）
1111
+1111
---10000
1 1 1 1論理関数の設計
● これまでは論理式から論理回路を描いていた
● 本当にやりたいこと
–
要求仕様（欲しい入出力関係）を実現する論理回路● やるべきこと
–
要求仕様（真理値表）→論理式（関数）→論理回路● 問題点
–
どうやって真理値表を満たす論理式を作るか–
真理値表を満たす論理式は１つではない● どういう論理式を作ればいいか
真理値表から論理関数へ
● 次の真理値表で表される論理式（論理関数）は？
x y z f(x,y,z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
真理値表から論理関数へ
● 次の真理値表で表される論理式（論理関数）は？
x y z f(x,y,z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
答えは唯一ではない
f =̄ x y ̄ z + x ̄ y z + x y ̄ z
f = ( x + y + z )( x + y + ̄ z ) ( x + ̄ y + ̄ z )(̄ x + y + z ) (̄ x + ̄ y + ̄ z )
f = y ̄ z + x ̄ y z
真理値表から論理関数へ
● 論理関数への変換の考え方
–
できるだけ機械的に変換できたほうがいい● 真理値表から標準形論理式への変換
–
できるだけ論理演算が少ないほうがいい● 論理回路として実現した時の素子数が少ない
– 低コスト、高速
● 演算数が最小の論理式：最簡形論理式
● 最簡形論理式の導出
– カルノー図
– クワイン・マクラスキ法
基礎的な概念
● 基本的に積和形（論理積の論理和）で考える
● リテラル：変数または変数の否定
̄ y z + x y ̄ z
リテラル
̄ y z + x y ̄ z
リテラル リテラル
項（積項）
標準形論理式
● 積和標準形（主加法標準形）
Sum-of-product
–
リテラルの論理積の論理和–
すべての項がすべての変数を含む–
同じ項は１回しか出てこない–
積和標準形の例–
積和標準形でない例f ( x , y , z )=̄ x ̄ y z + x ̄ y z + x y ̄ z
f ( x , y , z )=̄ y z + x y ̄ z
標準形論理式
● 和積標準形（主乗法標準形）
Product-of-sum
–
リテラルの論理和の論理積–
すべての論理和がすべての変数を含む–
同じ論理和は１回しか出てこない–
和積標準形の例–
和積標準形でない例f ( x , y , z )=( x + y + z )( x + y + ̄ z )(̄ x + y + z ) f ( x , y , z )=( x + z )(̄ x + y + z )
f ( x , y , z )=( x + z )(̄ x y + z )
f ( x , y , z )=( x + y + z )( x + y + ̄ z )( x + y + z )
2 つの標準形の関係
● どんな論理式でも、積和標準形と和積標準形の両 表で表現できる。
–
証明（変数の数による数学的帰納法）●
1
変数の場合は自明●
k
変数の場合に成立を仮定。任意の
k+1
変数論理関数を考える 次のk
変数関数を考えるf ( x
1, x
2, … , x
k+ 1)
g
0( x
1, … , x
k)= f ( x
1, x
2, … , x
k, 0 )
g
1( x , … , x )= f ( x , x , … , x , 1 )
2 つの標準形の関係
●
g
をそれぞれ積和と和積標準形で表した論理式● 以前と同じ議論により、
g
0( x
1, … , x
k)→ g
SOP0( x
1, … , x
k) , g
0POS( x
1, … , x
k) g
1( x
1, … , x
k)→ g
1SOP( x
1, … , x
k) , g
1POS( x
1, … , x
k)
f ( x
1, x
2, … , x
k, x
k+1)= x
k+1g
0( x
1, … , x
k)+ x
k+1g
1( x
1, … , x
k)
= x
k+1g
0SOP( x
1, … , x
k)+ x
k+1g
1SOP( x
1, … , x
k)
これを分配律によって展開すれば、f
も積和標準形で表せる。
2 つの標準形の関係
● 和積標準形の場合、まず次の関係を考える
x=0
ならa
、x=1
ならb
となる論理式● したがって
( x + a )(̄ x + b )
x = 0 →( x + a )(̄ x + b )=( 0 + a )( 1 + b )= a ⋅ 1 = a x = 1 →( x + a )(̄ x + b )=( 1 + a )( 0 + b )= 1 ⋅ b = b
f ( x
1, x
2, … , x
k, x
k+1)=( x
k+1+ g
0( x
1, … , x
k))( x
k+1+ g
1( x
1, … , x
k))
=( x
k+1+ g
0POS( x
1, … , x
k))( x
k+1+ g
1POS( x
1, … , x
k))
これを分配律によって展開すれば、f
も和積標準形で表せる。
標準形論理式と論理回路設計
● ある標準形は、１つの仕様（真理値表）に対して基 本的に
1
つしか存在しない真理値表 一対一 標準形
論理式 一対一 論理回路
x y f(x,y)
0 0 0
0 1 1
1 0 1
1 1 0
̄ x y + x ̄ y
真理値表から積和標準形へ
x y x・y x・y x・y x・y
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1
● 最小項：すべての変数のリテラルを含む積項
● ある入力の組み合わせの時だけ１になり、それ以外の組み合わせでは0になる。
x y f(x,y)
0 0 0
0 1 1
1 0 1
1 1 0
実現したい真理値表のうち、１になる組み合わせの最小項だけを OR で つなぐと積和標準形になる。
f ( x , y )=̄ x y + x ̄ y
真理値表から和積標準形へ
x y x+y x+y x+y x+y
0 0 0 1 1 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
● 最大項：すべての変数のリテラルを含む論理和
● ある入力の組み合わせの時だけ0になり、それ以外の組み合わせでは1になる。
x y f(x,y)
0 0 0
0 1 1
1 0 1
1 1 0
実現したい真理値表のうち、0になる組み合わせの最大項だけを AND でつなぐと和積標準形になる。
f ( x , y )=( x + y )(̄ x + ̄ y )
演習
● 次の真理値表による論理関数を積和標準形と和 積標準形で表せ。
x y z f(x,y,z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
論理式の簡単化
● 標準形で表現した論理式は一般に冗長
x y f(x,y)
0 0 0
0 1 1
1 0 1
1 1 1
̄ x y + x ̄ y + x y
x y
̄ x y + x ̄ y + x y =̄ x y + x ̄ y + x y + x y
=(̄ x + x ) y + x ( y + ̄ y )= 1 ⋅ y + x ⋅ 1 = x + y
x y
同じ
どうすれば同じ関数を表現するときの論理演算の
基礎的な概念
● 論理関数の順序
–
値の順序：0≤0, 0≤1, 1≤1
–
論理関数の順序：f(x),g(x)
について、∀ x(f(x)≤g(x))↔f≤g
–
例：確かめてみよう●
xy ≤ x ≤ x+y
– （真理値表を書き、左辺が１のところが右辺でも必ず
1
になっているな らば≤
が成立）基礎的な概念
● 系
–
論理関数a,b,c,d
について●
a ≤ c , b ≤ d
ならばa+b ≤ c+d
●
a ≤ c, a ≤ d
ならばa ≤ c+d
●
a ≤ c, b ≤ c
ならばa+b ≤ c
基礎的な概念
● 論理式
f
の主項とは–
リテラルの論理積t
のうち、次の条件を満たすもの●
t ≤ f
であり、●
tからそれ以上リテラルを取り除くと t ≤ f
でなくなる● 例 x y z f x・y・z x・y x
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 1 0 0 0
1 0 0 1 1 1 1
f ≤ x ̄ y ̄ z f ≤ x ̄ y f ≤ x
これが主項
主項と論理式
● ある論理式
f
の主項を全部列挙し、その論理和を とれば、それはf
と一致する。–
ただし一般には冗長x y z f x・y x・z y・z
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 1 0 0 1
1 0 0 1 0 1 0
1 0 1 0 0 0 0
1 1 0 1 1 1 0
1 1 1 1 1 0 1
f = x y + x ̄ z + y z = x ̄ z + y z
必須主項
● ある論理式を構成するために必ず必要な主項
x y z f x・y x・z y・z
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 1 0 0 1
1 0 0 1 0 1 0
1 0 1 0 0 0 0
f = x y + x ̄ z + y z = x ̄ z + y z
必須 主項
最簡形論理式とは
● 次の条件を満たす論理式：
–
ある論理関数を実現する論理式のうち、–
積項の数が最小で、–
かつ式全体のリテラルの数が最小のもの● 論理式を簡単化するときの目標
● 論理関数の仕様（真理値表）に対して最簡形が一 意に決まるとは限らない
最簡形を求めるには
● 次のような手順を踏む
1. 与えられた論理関数の主項をすべて求める 2. 求まった主項のなかの必須主項を調べる
3. すべての必須主項と、それ以外の主項のうちできるだ けリテラルの少ない主項を組み合わせて元の論理関数 を表現する
● これらの求め方でいくつかの方法がある
● カルノー図
● クワイン・マクラスキ―法
最簡形を求める方法
● カルノー図
(Karnaugh map)
–
真理値表に似た表と四角形でできた図を使う–
人間向き–
変数の数はふつう4
個ぐらいまで● クワイン・マクラスキ―法
(Quine-McClusky alg.)
–
文字列処理–
計算機向き（人間にはつらい）–
変数の数は多くてもよいが、変数が多いと時間がかか るカルノー図
●
2
次元の真理値表をもとに主項を発見する●
3
変数(x,y,z)
、４変数(x,y,z,w)
の表の例– 0,1
の並びに注意xy\zw 00 01 11 10
00 01 11
xy\z 0 1
00
01
11
カルノー図
● カルノー図では積項は長方形になる
xy\zw 00 01 11 10
00 01 11 10
z y
x
カルノー図
● カルノー図は表の上下左右がつながっている
xy\zw 00 01 11 10
00 01 11
y
w
カルノー図
● リテラルの多い積項の例
xy\zw 00 01 11 10
00 01 11 10
x ・ z
z ・ w x ・ y ・ z ・ w
x ・ y ・ w
カルノー図による論理式の簡単化
●カルノー図の表を描き、目標となる論理式が１となる マス目に“１”を記入
●“１”を囲む、できるだけ大きい長方形（＝主項）を探 す
● 辺の長さは２の
n
乗のみ● 上下左右が連続していることを忘れずに
●すべての“１”をカバーする、できるだけ少ない数の、
できるだけ大きい長方形の組み合わせを探す
カルノー図の例
カルノー図の表を描き、目標となる論理式が１となる マス目に“１”を記入
xy\zw 00 01 11 10
00 1 1 1
01 1 1
11 1 1
10 1 1
カルノー図の例
“１”を囲む、できるだけ大きい長方形（＝主項）を探す
–
辺の長さは２のn
乗のみ–
上下左右が連続していることを忘れずにxy\zw 00 01 11 10
00 1 1 1
01 1 1
11 1 1
1 1
カルノー図の例
すべての“１”をカバーする、できるだけ少ない数の、
できるだけ大きい長方形の組み合わせを探す
xy\zw 00 01 11 10
00 1 1 1
01 1 1
11 1 1
10 1 1
ある“１”を１つの四角だけが囲んでいるなら、その四
この２つは必須 ではない→大き いほうを選ぶ
カルノー図の例
その長方形の組み合わせに対応する論理式が最簡 形になっている
xy\zw 00 01 11 10
00 1 1 1
01 1 1
11 1 1
1 1
使わない
x w + y w + z w + ̄ x ̄ y w ̄
演習
● 次のカルノー図を使って最簡形論理式を求めよ。
xy\z 0 1
00 1
01 1
11 1 1
10 1
xy\zw 00 01 11 10
00
01 1 1 1
11 1 1 1
10 1 1 1
部分論理関数とカルノー図
● 入力のすべてのパターンを考えなくてよい場合
–
例：7
セグメントLED
に0
～4
の数字を表示0 1 2 3 4
5 6
LED エンコーダ
x
1x
2x
3b
0b
6部分論理関数とカルノー図
●
b1
～b6
の真理値表–
下3
行の入力は想定しなくてよい→部分論理関数0 1 2 3 4
5 6
x1 x2 x3 b0 b1 b2 b3 b4 b5 b6
0 0 0 1 1 1 1 1 1 0
0 0 1 0 1 1 0 0 0 0
0 1 0 1 1 0 1 1 0 1
0 1 1 1 1 1 1 0 0 1
1 0 0 0 1 1 0 0 1 1
1 0 1 N/A
1 1 0 N/A
1 1 1 N/A
部分論理関数とカルノー図
●
b0
の論理関数の設計x1x2\x3 0 1
0 0 1
0 1 1 1
1 1 1 0
x1x2\x3 0 1
0 0 1
0 1 1 1
1 1 * *
1 0 *
想定外の入力に対し
て０を出力 想定外の入力に対し て何を出力してもよい