Bài giảng Toán rời rạc - Chương 3: Đại số Bool, hàm Bool
Công thức đa thức tối tiểu
n 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 thức F của hàm Bool f được gọi là tối tiểu
nếu với bất kỳ công thức G của f mà đơn giản
hơn F thì F và G đơn giản như nhau
2. Hàm Bool
Phương pháp biểu đồ Karnaugh
Với qui ước: Khi một ô nằm trong dãy được đánh dấu
bởi x thì tại đó x =1, bởi thì tại đó x =0, tương tự cho
y, z.
Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm hoặc
gạch chéo). Tập các ô được đánh dấ
Bạn đang xem nội dung tài liệu Bài giảng Toán rời rạc - Chương 3: Đại số Bool, hàm Bool, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
06/05/2010
Chương III 1. ð i S Bool
M t ñ i s Bool (A,+,.) là m t t p h p A ≠ ∅
ð I S BOOL v i hai phép toán (+), (.), th a 5 tính ch t sau:
HÀM BOOL • Tính giao hoán: ∀x,y ∈ A
x.y = y.x;
x+y = y+x;
06/05/2010 2
1. ð i S Bool 1. ð i S Bool
• Tính k t h p: ∀x,y,z ∈ A • Có các ph n t trung hòa 1 và 0: ∀x ∈A
(x.y).z = x.(y.z);
x.1 = 1.x = x;
(x+y)+z = x+(y+z).
x + 0 = 0 ∨ x = x.
• Tính phân b : ∀x,y,z ∈ A
x.(y+z) = (x.y)+(x.z); • M i ph n t ñ u có ph n t bù:∀x∈A, ∃x ∈A,
x+(y.z) = (x+y).(x+z). x. x = x .x = 0;
X+x = x + x = 1.
06/05/2010 3 06/05/2010 4
1
06/05/2010
1. ð i S Bool 1. ð i S Bool
Ví d :
Xét t p h p B = {0, 1}. Trên B ta ñ nh nghĩa hai
Xét F là t p h p t t c các d ng m nh ñ theo n bi n phép toán +,. như sau:
p1, p2,,p n v i hai phép toán n i li n ∧, phép toán n i
. 0 1
r i ∨, trong ñó ta ñ ng nh t các d ng m nh ñ tương + 0 1
0 0 0 0 0 0
ñương. Khi ñó F là m t ñ i s Bool v i ph n t 1 là
1 0 1 1 0 1
h ng ñúng 1, ph n t 0 là h ng sai 0, ph n t bù c a
d ng m nh ñ E là d ng m nh ñ bù E Khi ñó, B tr thành m t ñ i s Bool
06/05/2010 5 06/05/2010 6
1. ð i S Bool 2. Hàm Bool
Cho ñ i s Bool (A,+,.). Khi ñó v i m i x,y ∈A, ta có: ð nh nghĩa
1. x.x=x;x+x=x.
M t hàm Bool n bi n là m t ánh x
2. x.0=0.x=0;x+1=1+x=1.
3. Ph nt bùc axlàduynh tvàx =x; f : B n → B , trong ñó B = {0, 1}.
1= 0; 0 = 1. M t hàm Booln bi n là m t hàm s có d ng:
4. Công th c De Morgan:
f = f(x ,x ,,x ), trong ñó m i bi n trong x , x ,, x
xy= x + y; 1 2 n 1 2 n
ch nh n hai giá tr 0,1 và f nh n giá tr trong B = {0,1}.
x+ y = xy.
5. Tínhh pth :
Ký hi u Fn ñ ch t p các hàm Bool n bi n.
x(x+y) = x; x+(xy) = x.
06/05/2010 7 06/05/2010 8
2
06/05/2010
2. Hàm Bool 2. Hàm Bool
B ng chân tr Ví d :
Xét hàm Bool n bi n f(x 1,x 2,,x n). Vì m i bi n xi ch Xét k t qu f trong vi c thông qua m t Quy t ñ nh d a
nh n hai giá tr 0, 1 nên ch có 2n trư ng h p c a b vào3 phi ub u x, y, z.
bi n (x ,x ,,x ). 1. M i phi u ch l y m t trong hai giá tr : 1 (tán thành)
1 2 n ho c 0 (bác b ).
Do ñó, ñ mô t f, ta có th l p b ng g m 2n hàng ghi
2. K t qu f là 1 (thông qua Quy t ñ nh) n u ñư c ña
t t c các giá tr c a f tùy theo 2n trư ng h p c a bi n. s phi u tán thành, là 0 (không thông qua Quy t
ñ nh) n u ña s phi u bác b .
Ta g i ñây là b ng chân tr c a f.
Khi ñó f là hàm Bool theo 3 bi n x, y, z có b ng chân
tr như sau:
06/05/2010 9 06/05/2010 10
2. Hàm Bool 2. Hàm Bool
x y z f Các phép toán trên hàm Bool
1 1 1 1 Các phép toán trên Fn ñư c ñ nh nghĩa như sau:
1 1 0 1
1. Phép c ng Bool +:
1 0 1 1
∈
1 0 0 0 V i f, g Fn ta ñ nh nghĩa t ng Bool c a f và g:
n
0 1 1 1 ∀x = (x 1,x 2,,x n)∈ B ,
0 1 0 0 (f +g)(x) = f(x) + g(x) – f(x)g(x)
0 0 1 0 D th y
0 0 0 0 f +g ∈ Fn và (f+g)(x) = max{f(x),g(x)}
06/05/2010 11 06/05/2010 12
3
06/05/2010
2. Hàm Bool 2. Hàm Bool
Các phép toán trên hàm Bool Các phép toán trên hàm Bool
2. Phép nhân Bool .: 3. Phép l y hàm bù:
V i f, g ∈Fn ta ñ nh nghĩa tích Bool c a f và g V i f ∈ Fn ta ñ nh nghĩa hàm bù c a f như sau:
n
∀x=(x 1,x 2,,x n)∈B , f=1 − f
(f.g)(x) = f(x)g(x)
D th y:
f.g ∈Fn và (f.g)(x) = min{f(x),g(x)}
06/05/2010 13 06/05/2010 14
2. Hàm Bool 2. Hàm Bool
D ng n i r i chính t c c a hàm Bool Công th c ña th c t i ti u
•Xét t p h p các hàm Bool c a n bi n Fn theo n bi n • ðơn gi n hơn
x1 ,x 2,,x n. Cho hai công th c ña th c c a m t hàm Bool:
• M ihàmboolx hayx ñư cg ilàt ñơn.
i i f = m + m +. +m (F)
• ðơn th c là tích khác không c a m t s h u h n t 1 2 k
ñơn. f =M 1 + M 2 + + M l (G)
• T t i ti u là tích khác khôngc a ñúngn t ñơn. Ta nói r ngcông th c F ñơn gi n hơn công th c
• Công th c ña th c là công th c bi u di n hàm Bool G n u t n t i ñơn ánh h: {1,2,..,k} → { 1,2,,
thành t ng c a các ñơn th c. l} sao cho v i m i i∈ {1,2,..,k} thì s t ñơn c a
• D ng n i r i chính t c là công th c bi u di n hàm mi không nhi u hơn s t ñơn c a Mh(i)
Bool thành t ng c a các t t i ti u.
06/05/2010 15 06/05/2010 16
4
06/05/2010
2. Hàm Bool 2. Hàm Bool
Công th c ña th c t i ti u Phương pháp bi u ñ Karnaugh
• ðơn gi n như nhau:
Xétf là m t hàm Booltheo n bi n x1,x 2,,x n v in=3ho c4.
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. Trư ng h p n = 3: f là hàm Bool theo 3 bi n x, y, z. Khi ñó
b ng chân tr c a f g m 8 hàng. Thay cho b ng chân tr c a f
Công th c ña th c t i ti u: ta v m t b ng ch nh t g m 8 ô, tương ng v i 8 hàng c a
Công th c F c a hàm Bool f ñư c g i là t i ti u b ng chân tr , ñư c ñánh d u như sau:
n u v i b t kỳ công th c G c a f mà ñơn gi n x x x x
hơn F thì F và G ñơn gi n như nhau z 101 111 011 001
z 100 110 010 000
y y y y
06/05/2010 17 06/05/2010 18
2. Hàm Bool 2. Hàm Bool
Phương pháp bi u ñ Karnaugh Phương pháp bi u ñ Karnaugh
Trư ng h p n = 4: f là hàm Bool theo 4 bi n x, y, z, t. Khi ñó
V i qui ư c: Khi m t ô n m trong dãy ñư c ñánh d u b ng chân tr c a f g m 16 hàng. Thay cho b ng chân tr c a f ta
b i x thì t i ñó x =1, b ix thì t i ñó x =0, tương t cho v m t b ng ch nh t g m 16 ô, tương ng v i 16 hàng c a b ng
y, z. chân tr , ñư c ñánh d u như sau:
x x x x
Các ô t i ñó f b ng 1 s ñư c ñánh d u (tô ñ m ho c
z 1010 1110 0110 0010 t
g ch chéo). T p các ô ñư c ñánh d u ñư c g i là bi u
z 1011 1111 0111 0011 t
ñ Karnaugh c a f, ký hi u là kar(f).
z 1001 1101 0101 0001 t
z 1000 1100 0100 0000 t
y y y y
06/05/2010 19 06/05/2010 20
5
06/05/2010
2. Hàm Bool 2. Hàm Bool
Phương pháp bi u ñ Karnaugh T bào
Trong c hai trư ng h p, hai ô ñư c g i là k Xét các hàm Bool theo n bi n x1,x 2,,x n. Khi ñó, n u f
là m t ñơn th c có d ng tích c a k t ñơn phân bi t thì
nhau (theo nghĩa r ng), n u chúng là hai ô li n kar(f) là m t hình ch nh t g m 2n k ô k nhau. Nh ng
hình ch nh t g m m t lũy th a c a 2 nh ng ô k nhau
nhau ho c chúng là ô ñ u, ô cu i c a cùng m t ñư c g i là các t bào . Như v y, bi u ñ Karnaugh c a
hàng (c t) nào ñó. Nh n xét r ng, do cách ñánh m t ñơn th c là m t t bào. Ngư c l i, n u T là m t t
bào thì T là bi u ñ Karnaugh c a m t ñơn th c duy
d u như trên, hai ô k nhau ch l ch nhau m t nh t m, cách xác ñ nh m như sau: l n lư t chi u T lên
các c nh, n u toàn b hình chi u n m tr n trong m t t
bi n duy nh t. ñơn nào thì t ñơn ñó m i xu thi n trong m.
06/05/2010 21 06/05/2010 22
2. Hàm Bool 2. Hàm Bool
Ví d : Xét các hàm Bool theo 4 bi n x, y, z, t. Ví d : Xét các hàm Bool theo 4 bi n x, y, z, t.
Bi u ñ Karnaugh c a ñơn th c xyzt Bi u ñ Karnaugh c a ñơn th c yzt
x x x x x x x x
z t z t
z t z t
z t z t
z t z t
y y y y y y y y
06/05/2010 23 06/05/2010 24
6
06/05/2010
2. Hàm Bool 2. Hàm Bool
Ví d : Xét các hàm Bool theo 4 bi n x, y, z, t. Ví d : Xét các hàm Bool theo 4 bi n x, y, z, t.
Bi u ñ Karnaugh c a ñơn th c yt Bi u ñ Karnaugh c a ñơn th c t
x x x x x x x x
z t z t
z t z t
z t z t
z t z t
y y y y y y y y
06/05/2010 25 06/05/2010 26
2. Hàm Bool 2. Hàm Bool
T bào l n Ví d :
Xét hàm Bool f theo 4 bi n x, y, z, t có bi u ñ
Cho hàm Bool f. Ta nói T là m t t bào l n c a Karnaugh như sau:
kar(f) n u T tho hai tính ch t sau:
x x x x
a. T là m t t bào và T ⊆ kar(f).
z t
b. Không t n t i t bào T’ nào th a T’ ≠ T và T z t
z t
⊆ T’ ⊆ kar(f). z t
y y y y
06/05/2010 27 06/05/2010 28
7
06/05/2010
2. Hàm Bool 2. Hàm Bool
Kar(f) có 6 t bào l n như sau:
x x x x x x x x x x x x x x x x
z t z t z t z t
z t z t z t z t
z t z t z t z t
z t z t z t z t
y y y y y y y y y y y y y y y y
xz yz xt xy
06/05/2010 29 06/05/2010 30
2. Hàm Bool 2. Hàm Bool
Thu t toán xác ñ nh t t c các công th c ña th c
x x x x x x x x t i ti u c a hàm Bool f
z t z t
Bư c 1: V bi u ñ Karnaugh c a f.
z t z t
z t z t Bư c 2: Xác ñ nh t t c các t bào l n c a kar(f).
z t z t Bư c 3: Xác ñ nh các t bào l n nh t thi t ph i ch n.
y y y y y y y y
Ta nh t thi t ph i ch n t bào l n T khi t n t i
yzt yt m t ô c a kar(f) mà ô này ch n m trong t bào l n T
và không n m trong b t kỳ t bào l n nào khác.
06/05/2010 31 06/05/2010 32
8
06/05/2010
2. Hàm Bool 2. Hàm Bool
Bư c 4: Xác ñ nh các ph t i ti u g m các t bào l n.
Bư c 5: Xác ñ nh các công th c ña th c t i ti u c a f.
N u các t bào l n ch n ñư c bư c 3 ñã ph ñư c
T các ph t i ti u g m các t bào l n c a kar(f) tìm
kar(f) thì ta có duy nh t m t ph t i ti u g m các t bào
ñư c bư c 4 ta xác ñ nh ñư c các công th c ña th c
l n c a kar(f).
tương ng c a f.
N u các t bào l n ch n ñư c bư c 3 chưa ph
So sánh các công th c trên: Lo i b các công th c ña
ñư c kar(f) thì xét m t ô chưa b ph , s có ít nh t hai
th c mà có m t công th c ña th c nào ñó th c s ñơn
t bào l n ch a ô này, ta ch n m t trong các t bào l n
gi n hơn chúng. Các công th c ña th c còn l i chính là
này. C ti p t c như th ta s tìm ñư c t t c các ph
các công th c ña th c t i ti u c a f.
g m các t bào l n c a kar(f). Lo i b các ph không
t i ti u, ta tìm ñư c t t c các ph t i ti u g m các t
bào l n c a kar(f).
06/05/2010 33 06/05/2010 34
2. Hàm Bool 2. Hàm Bool
Ví d 1: Tìm t t c các công th c ña th c t i ti u c a Bư c 2: Kar(f) có các t bào l n như sau:
hàm Bool
x x x x x x x x
fxyzt(,,,)= xyzt ++++ xy xz yz xyz () + t
z 1 2 t z 2 3 t
Ta có: f= xyzt ++++ x y xz yz xyz + xyt z 4 5 t z 5 6 t
z 7 8 t z t
Bư c 1:V kar(f):
x x x x z 9 10 t z t
z 1 2 3 t y y y y y y y y
z 4 5 6 t
z 7 8 t x yt
z 9 10 t
y y y y
06/05/2010 35 06/05/2010 36
9
06/05/2010
2. Hàm Bool 2. Hàm Bool
Bư c 3: Xác ñ nh các t bào l n nh t thi t ph i
Bư c 4: Xác ñ nh các ph t i ti u g m các t bào l n.
ch n. Các ô ñư c các t bào l n ñã ch n bư c 3 ph như
sau:
– Ô 1 n m trong m t t bào l n duy nh t x. Ta x x x x
z 1 2 3 t
ch n x. z 4 5 6 t
z 7 8 t
– Ô 3 n m trong m t t bào l n duy nh t yz. Ta
z 9 10 t
ch n yz. y y y y
Ta ñư c duy nh t m t ph t i ti u g m các t bào l n c a kar(f): x; yz.
06/05/2010 37 06/05/2010 38
2. Hàm Bool 3. M ng logic (M ng các c ng)
Bư c 5: Xác ñ nh các công th c ña th c t i ti u c a f. ð nh nghĩa
ng v i ph t i ti u g m các t bào l n tìm ñư c M t m ng logic hay m t m ng các c ng là m t
bư c 4 ta tìm ñư c duy nh t m t công th c ña th c t i h th ng có d ng:
ti u c a f:
x1
x f(x 1,x 2,..., x n)
f= x + yz 2
xn
06/05/2010 39 06/05/2010 40
10
06/05/2010
3. M ng logic (M ng các c ng) 3. M ng logic (M ng các c ng)
trong ñó: C ng NOT
Input: x1, x2,..., xn là các bi n Bool.
C ng AND
Output: f(x 1, x2,..., xn) là hàm Bool.
Ta nói m ng logic trên t ng h p hay bi u di n
hàm Bool f.
C ng OR
M t m ng logic b t kỳ luôn luôn ñư c c u t o
t m t s m ng sơ c p mà ta g i là các c ng
06/05/2010 41 06/05/2010 42
3. M ng logic (M ng các c ng)
x y
x
y
xy + xy
x
x
y xy
OR
x x y
y xy + xy
x
xy
06/05/2010 43
11
Các file đính kèm theo tài liệu này:
bai_giang_toan_roi_rac_chuong_3_dai_so_bool_ham_bool.pdf
