06/05/2010
1
Chương III
ðI S BOOL
HÀM BOOL
06/05/2010
2
1. ði S Bool
Mt ñi s Bool (A,+,.) là mt tp hp A ≠ ∅
vi hai phép toán (+), (.), tha 5 tính ch"t sau:
• Tính giao hoán:
∀
x,y
∈
A
x.y = y.x;
x+y = y+x;
06/05/2010
3
Tính phân b:
∀
x,y,z
∈
A
x.(y+z) = (x.y)+(x.z);
x+(y.z) = (x+y).(x+z).
1. ði S Bool
Tính kt hp:
∀
x,y,z
∈
A
(x.y).z = x.(y.z);
(x+y)+z = x+(y+z).
06/05/2010
4
• Có các ph/n t0 trung hòa 1 và 0: ∀x∈A
x.1 = 1.x = x;
x + 0 = 0 ∨x = x.
M6i ph/n t0 ñ7u có ph/n t0 bù:∀x∈A,∃ ∈A,
x. = .x = 0;
X+ = + x = 1.
1. ði S Bool
x
x
x
x
x
06/05/2010
2
06/05/2010
5
1. ði S Bool
Ví d:
Xét F là tp hp t"t c< các dng m>nh ñ7 theo n bi@n
p1, p2,…,pnvi hai phép toán ni li7n ∧, phép toán ni
rCi ∨, trong ñó ta ñDng nh"t các dng m>nh ñ7 tương
ñương. Khi ñó F là mt ñi s Bool vi ph/n t0 1 là
hHng ñúng 1, ph/n t0 0 là hHng sai 0, ph/n t0 bù cJa
dng m>nh ñ7 E là dng m>nh ñ7 bù
06/05/2010
6
1. ði S Bool
Xét tp hp B = {0, 1}. Trên B ta ñOnh nghĩa hai
phép toán +,. như sau:
Khi ñó, B trQ thành mt ñi s Bool
. 0 1
00 0
10 1
+ 0 1
00 0
10 1
06/05/2010
7
1. ði S Bool
Cho ñi s Bool (A,+,.). Khi ñó vi m6i x,y∈A, ta có:
1. x.x = x; x+x = x.
2. x.0 = 0.x =0; x+1 =1+ x = 1.
3. Ph/n t0 bù cJa x là duy nh"t và = x;
4. Công thVc De Morgan:
5. Tính h"p thX:
x(x+y) = x; x+(xy) = x.
= +
+ =
= =
06/05/2010
8
2. Hàm Bool
ðnh nghĩa
Mt hàm Bool n bi@n là mt ánh x
f : Bn→B , trong ñó B = {0, 1}.
Mt hàm Bool n bi@n là mt hàm s có dng:
f = f(x1,x2,…,xn), trong ñó mZi bi@n trong x1, x2,…, xn
ch[ nhn hai giá trO 0,1 và f nhn giá trO trong B = {0,1}.
Ký hi>u Fnñ] ch[ tp các hàm Bool n bi@n.
06/05/2010
3
06/05/2010
9
Bng chân tr
Xét hàm Bool n bi@n f(x1,x2,…,xn). Vì mZi bi@n xich[
nhn hai giá trO 0, 1 nên ch[ có 2ntrưCng hp cJa b
bi@n (x1,x2,…,xn).
Do ñó, ñ] mô t< f, ta có th] lp b<ng gDm 2nhàng ghi
t"t c< các giá trO cJa f tùy theo 2ntrưCng hp cJa bi@n.
Ta g6i ñây là b(ng chân tr- c.a f.
2. Hàm Bool
06/05/2010
10
Xét k@t qu< f trong vi>c thông qua mt Quy@t ñOnh dda
vào 3 phi@u b/u x, y, z.
1. MZi phi@u ch[ l"y mt trong hai giá trO: 1 (tán thành)
hoec 0 (bác b).
2. K@t qu< f là 1 (thông qua Quy@t ñOnh) n@u ñưc ña
s phi@u tán thành, là 0 (không thông qua Quy@t
ñOnh) n@u ña s phi@u bác b.
Khi ñó f là hàm Bool theo 3 bi@n x, y, z có b<ng chân
trO như sau:
2. Hàm Bool
Ví d:
06/05/2010
11
2. Hàm Bool
x y z f
1 1 1 1
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 0
06/05/2010
12
Các phép toán trên hàm Bool
Các phép toán trên Fnñưc ñOnh nghĩa như sau:
1. Phép cng Bool +:
Vi f, g ∈Fnta ñOnh nghĩa tfng Bool cJa f và g:
2. Hàm Bool
∀x = (x1,x2,…,xn)∈Bn,
(f +g)(x) = f(x) + g(x) – f(x)g(x)
f +g ∈Fnvà (f+g)(x) = max{f(x),g(x)}
D5 th6y
06/05/2010
4
06/05/2010
13
2. Phép nhân Bool .:
Vi f, g ∈Fnta ñOnh nghĩa tích Bool cJa f và g
2. Hàm Bool
Các phép toán trên hàm Bool
∀x=(x1,x2,…,xn)∈Bn,
(f.g)(x) = f(x)g(x)
D5 th6y:
f.g ∈Fnvà (f.g)(x) = min{f(x),g(x)}
06/05/2010
14
3. Phép l"y hàm bù:
Vi f ∈Fnta ñOnh nghĩa hàm bù cJa f như sau:
1
f f
= −
2. Hàm Bool
Các phép toán trên hàm Bool
06/05/2010
15
Dng ni r i chính t!c c"a hàm Bool
• Xét tp hp các hàm Bool cJa n bi@n Fntheo n bi@n
x1,x2,…,xn.
• MZi hàm bool xihay ñưc g6i là th ñơn.
• ðơn thVc là tích khác không cJa mt s hju hn th
ñơn.
• Th ti ti]u là tích khác không cJa ñúng n th ñơn.
•Công th)c ña th)c là công th)c bi+u di.n hàm Bool
thành t/ng c0a các ñơn th)c.
• Dng ni rCi chính tkc là công thVc bi]u diln hàm
Bool thành tfng cJa các th ti ti]u.
i
x
2. Hàm Bool
06/05/2010
16
Công th$c ña th$c ti ti&u
•ðơn gi3n hơn
Cho hai công thVc ña thVc cJa mt hàm Bool:
f = m1+ m2 +…. +mk(F)
f =M1 + M2 +… + Ml (G)
Ta nói rHngcông thVc F ñơn gi<n hơn công thVc
G n@u tn ti ñơn ánh h: {1,2,..,k} → { 1,2,…,
l} sao cho vi m6i i∈{1,2,..,k} thì s th ñơn cJa
mikhông nhi7u hơn s th ñơn cJa Mh(i)
2. Hàm Bool
06/05/2010
5
06/05/2010
17
•ðơn gi3n như nhau:
N@u F ñơn gi<n hơn G và G ñơn gi<n hơn F thì
ta nói F và G ñơn gi<n như nhau.
Công th$c ña th$c ti ti&u:
Công thVc F cJa hàm Bool f ñưc g6i là ti ti]u
n@u vi b"t kỳ công thVc G cJa f mà ñơn gi<n
hơn F thì F và G ñơn gi<n như nhau
2. Hàm Bool
Công th$c ña th$c ti ti&u
06/05/2010
18
2. Hàm Bool
Phương pháp bi&u ñ, Karnaugh
Xét f là mt hàm Bool theo n bi@n x1,x2,…,xnvi n = 3 hoec 4.
Trư7ng hp n = 3: f là hàm Bool theo 3 bi@n x, y, z. Khi ñó
b<ng chân trO cJa f gDm 8 hàng. Thay cho b<ng chân trO cJa f
ta vr mt b<ng chj nht gDm 8 ô, tương Vng vi 8 hàng cJa
b<ng chân trO, ñưc ñánh d"u như sau:
x x
z101 111 011 001
100 110 010 000
y y
x
x
z
y
y
06/05/2010
19
2. Hàm Bool
Phương pháp bi&u ñ, Karnaugh
V:i qui ư:c: Khi mt ô nHm trong dãy ñưc ñánh d"u
bQi x thì ti ñó x =1, bQi thì ti ñó x =0, tương td cho
y, z.
Các ô ti ñó f bHng 1 sr ñưc ñánh d"u (tô ñm hoec
gch chéo). Tp các ô ñưc ñánh d"u ñưc g6i là bi]u
ñD Karnaugh cJa f, ký hi>u là kar(f).
x
06/05/2010
20
2. Hàm Bool
Trư7ng hp n = 4: f là hàm Bool theo 4 bi@n x, y, z, t. Khi ñó
b<ng chân trO cJa f gDm 16 hàng. Thay cho b<ng chân trO cJa f ta
vr mt b<ng chj nht gDm 16 ô, tương Vng vi 16 hàng cJa b<ng
chân trO, ñưc ñánh d"u như sau:
x x
z1010 1110 0110 0010
z1011 1111 0111 0011 t
1001 1101 0101 0001 t
1000 1100 0100 0000
y y
Phương pháp bi&u ñ, Karnaugh
x
x
z
y
y
z
t
t