Xem mẫu
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
CHƯƠNG VIII
ð IS BOOLE
Các m ch ñi n trong máy tính và các d ng c ñi n t khác ñ u có các ñ u vào,
m i ñ u vào là s 0 ho c s 1, và t o ra các ñ u ra cũng là các s 0 và 1. Các m ch ñi n
ñó ñ u có th ñư c xây d ng b ng cách dùng b t kỳ m t ph n t cơ b n nào có hai tr ng
thái khác nhau. Chúng bao g m các chuy n m ch có th hai v trí m ho c ñóng và
các d ng c quang h c có th là sáng ho c t i. Năm 1938 Claude Shannon ch ng t
r ng có th dùng các quy t c cơ b n c a lôgic do George Boole ñưa ra vào năm 1854
trong cu n “Các quy lu t c a tư duy” c a ông ñ thi t k các m ch ñi n. Các quy t c
này ñã t o nên cơ s c a ñ i s Boole. S ho t ñ ng c a m t m ch ñi n ñư c xác ñ nh
b i m t hàm Boole ch rõ giá tr c a ñ u ra ñ i v i m i t p ñ u vào. Bư c ñ u tiên trong
vi c xây d ng m t m ch ñi n là bi u di n hàm Boole c a nó b ng m t bi u th c ñư c
l p b ng cách dùng các phép toán cơ b n c a ñ i s Boole. Bi u th c mà ta s nh n
ñư c có th ch a nhi u phép toán hơn m c c n thi t ñ bi u di n hàm ñó. cu i
chương này, ta s có các phương pháp tìm m t bi u th c v i s t i thi u các phép t ng
và tích ñư c dùng ñ bi u di n m t hàm Boole. Các th t c ñư c mô t là b n ñ
Karnaugh và phương pháp Quine-McCluskey, chúng ñóng vai trò quan tr ng trong vi c
thi t k các m ch ñi n có hi u qu cao.
8.1. KHÁI NI M ð I S BOOLE.
8.1.1. ð nh nghĩa: T p h p khác r ng S cùng v i các phép toán ký hi u nhân (.), c ng
(+), l y bù (’) ñư c g i là m t ñ i s Boole n u các tiên ñ sau ñây ñư c tho mãn v i
m i a, b, c ∈ S.
1. Tính giao hoán: a) a.b = b.a,
b) a+b = b+a.
2. Tính k t h p: a) (a.b).c = a.(b.c),
b) (a+b)+c = a+(b+c).
3. Tính phân ph i: a) a.(b+c) = (a.b)+(a.c),
b) a+(b.c) = (a+b).(a+c).
4. T n t i ph n t trung hoà: T n t i hai ph n t khác nhau c a S, ký hi u là 1 và 0
sao cho: a) a.1 = 1.a = a,
b) a+0 = 0+a = a.
1 g i là ph n t trung hoà c a phép . và 0 g i là ph n t trung hoà c a phép +.
5. T n t i ph n t bù: V i m i a ∈ S, t n t i duy nh t ph n t a’∈ S sao cho:
a) a.a’ = a’.a = 0,
b) a+a’ = a’+a = 1.
114
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
a’ g i là ph n t bù c a a.
Thí d 1:
1) ð i s lôgic là m t ñ i s Boole, trong ñó S là t p h p các m nh ñ , các phép toán ∧
(h i), ∨ (tuy n), − (ph ñ nh) tương ng v i . , +, ’, các h ng ñ (ñúng), s (sai) tương
ng v i các ph n t trung hoà 1, 0.
2) ð i s t p h p là m t ñ i s Boole, trong ñó S là t p h p P(X) g m các t p con c a
t p khác r ng X, các phép toán ∩ (giao), ∪ (h p), − (bù) tương ng v i . , +, ’, các t p
X, Ø tương ng v i các ph n t trung hoà 1, 0.
3) Cho B = {0,1}, các phép toán . , +, ’ trên B ñư c ñ nh nghĩa như sau:
1.1 = 1, 1+1 = 1, 1’ = 0,
1.0 = 0, 1+0 = 1, 0’ = 1. (1)
0.1 = 0, 0+1 = 1,
0.0 = 0, 0+0 = 0,
Khi ñó B là m t ñ i s Boole. ðây cũng chính là ñ i s lôgic, trong ñó 1, 0 tương ng
v i ñ (ñúng), s (sai). M i ph n t 0,1 c a B g i là m t bit. Ta thư ng vi t x thay cho x’.
n
T ng quát, g i B là t p h p các xâu n bit (xâu nh phân ñ dài n). Ta ñ nh nghĩa
tích, t ng c a hai chu i và bù c a m t chu i theo t ng bit m t như trong B ng 1, mà
n
thư ng ñư c g i là các phép toán AND-bit, OR-bit, NOT-bit. B v i các phép toán này
t o thành m t ñ i s Boole.
4) Cho M là t p h p các s th c có c n trên p, c n dư i q và tâm ñ i x ng O. Các phép
toán . , +, ’ trên M ñư c ñ nh nghĩa như sau:
a.b = min(a, b), a+b = max(a, b), a’ là ñi m ñ i x ng c a a qua O.
Khi ñó M là m t ñ i s Boole, trong ñó q, p tương ng v i các ph n t trung hoà 1, 0.
8.1.2. Chú ý: Trư c h t c n lưu ý ñi u quan tr ng sau ñây: các tiên ñ c a ñ i s Boole
ñư c x p theo t ng c p a) và b). T m i tiên ñ a), n u ta thay . b i +, thay + b i ., thay
1 b i 0 và thay 0 b i 1 thì ta ñư c tiên ñ b) tương ng.
Ta g i c p tiên ñ a), b) là ñ i ng u c a nhau. Do ñó n u ta ch ng minh ñư c
m t ñ nh lý trong ñ i s Boole thì ta có ngay m t ñ nh lý khác, ñ i ng u c a nó, b ng
cách thay . và 1 tương ng b i + và 0 (và ngư c l i). Ta có:
Quy t c ñ i ng u: ð i ng u c a m t ñ nh lý là m t ñ nh lý.
8.1.3. ð nh lý:
6. (Tính nu t)
a) a.0 = 0,
b) a+1 = 1
7. (Tính lu ñ ng)
a) a.a = a,
b) a+a = a.
115
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
8. (H th c De Morgan)
a) (a.b)’ = a’+b’,
b) (a+b)’ = a’.b’.
9. (H th c bù kép)
(a’)’ = a.
10. a) 1’ = 0,
b) 0’ = 1.
11. (Tính hút)
a) a.(a+b) = a,
b) a+(a.b) = a.
Ch ng minh:
6. 0 = a.a (tiên ñ 5a))
= a.(a’+0) (tiên ñ 4b))
= (a.a’)+(a.0) (tiên ñ 3a))
= 0+(a.0) (tiên ñ 5a))
= a.0 (tiên ñ 4b)).
7. a = a.1 (tiên ñ 4a))
= a.(a+a’) (tiên ñ 5b))
= (a.a)+(a.a’) (tiên ñ 3a))
= (a.a)+0 (tiên ñ 5a))
= a.a (tiên ñ 4b))
8. Ta ch ng minh r ng a’+b’ là bù c a a.b b ng cách ch ng minh r ng:
(a.b).(a’+b’) = 0 (theo 5a)) và (a.b)+(a’+b’) = 1 (theo 5b)).
Th t v y, (a.b).(a’+b’) = (a.b.a’)+(a.b.b’) = (a.a’.b)+(a.b.b’) = (0.b)+(a.0) = 0+0 = 0,
(a.b)+(a’+b’) = (a’+b’)+(a.b) = (a’+b’+a).(a’+b’+b) = (1+b’).(a’+1) = 1.1 = 1.
Vì a.b ch có m t ph n t bù duy nh t nên (a.b)’ = a’+b’.
9. Có ngay t tiên ñ 5.
10. Có t các h th c 1.0 = 0 và 1+0 = 1.
11. a.(a+b) = (a+0).(a+b) = a+(0.b) = a+0 = a.
8.1.4. Chú ý: H tiên ñ c a ñ i s Boole nêu ra ñây không ph i là m t h t i thi u.
Ch ng h n, các tiên ñ v tính k t h p có th suy ra t các tiên ñ khác. Th t v y, v i
A=(a.b).c và B=a.(b.c), ta có: a+A = a+((a.b).c) = (a+(a.b)).(a+c) = a.(a+c) = a, a+B =
a+(a.(b.c)) = (a+a).(a+(b.c)) = a.(a+(b.c)) = a, a’+A = a’+((a.b).c) = (a’+(a.b)).(a’+c) =
((a’+a).(a’+b)).(a’+c) = (1.(a’+b)).(a’+c) = (a’+b).(a’+c) = a’+(b.c), a’+B = a’+(a.(b.c))
= (a’+a).(a’+(b.c)) = 1.(a’+(b.c)) = a’+(b.c).
Do ñó a+A = a+B và a’+A = a’+B. T ñó suy ra r ng:
116
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
A = A+0 = A+(a.a’) = (A+a).(A+a’) = (a+A).(a’+A) = (a+B).(a’+B)=(a.a’)+B=0+B= B
hay ta có 2a) và ñ i ng u ta có 2b). Ngoài ra, tính duy nh t c a ph n t bù cũng ñư c
suy ra t các tiên ñ khác.
Tương t trong ñ i s lôgic, trong ñ i s Boole ta cũng xét các công th c, ñư c
thành l p t các bi n a, b, c, … nh các phép toán . , +, ’. Trong công th c, ta quy ư c
th c hi n các phép toán theo th t : ’, ., +; a.b ñư c vi t là ab, g i là tích c a a và b còn
a+b g i là t ng c a a và b. Ta có th bi n ñ i công th c, rút g n công th c tương t
trong ñ i s lôgic. Ta cũng xét các tích sơ c p và t ng sơ c p tương t “h i sơ c p” và
“tuy n sơ c p”. M i công th c ñ u có th ñưa v d ng tích chu n t c hoàn toàn ho c v
d ng t ng chu n t c hoàn toàn tương t d ng “h i và tuy n chu n t c hoàn toàn”. M i
công th c trong ñ i s Boole cũng ñư c g i là bi u di n m t hàm Boole.
8.2. HÀM BOOLE.
8.2.1. ð nh nghĩa: Ký hi u B = {0, 1} và Bn = {(x1, x2, …, xn) | xi∈ B, 1≤ i ≤ n}, ñây
n
B và B là các ñ i s Boole (xem 2) và 3) c a Thí d 1). Bi n x ñư c g i là m t bi n
Boole n u nó nh n các giá tr ch t B. M t hàm t Bn vào B ñư c g i là m t hàm Boole
(hay hàm ñ i s lôgic) b c n.
Các hàm Boole cũng có th ñư c bi u di n b ng cách dùng các bi u th c ñư c
t o b i các bi n và các phép toán Boole (xem B ng 1 trong Thí d 1). Các bi u th c
Boole v i các bi n x1, x2, …, xn ñư c ñ nh nghĩa b ng ñ quy như sau:
- 0, 1, x1, x2, …, xn là các bi u th c Boole.
- N u P và Q là các bi u th c Boole thì P , PQ và P+Q cũng là các bi u th c Boole.
M i m t bi u th c Boole bi u di n m t hàm Boole. Các giá tr c a hàm này nh n
ñư c b ng cách thay 0 và 1 cho các bi n trong bi u th c ñó.
Hai hàm n bi n F và G ñư c g i là b ng nhau n u F(a1, a2, …, an)=G(a1, a2, …,an)
v i m i a1, a2, …, an∈ B. Hai bi u th c Boole khác nhau bi u di n cùng m t hàm Boole
ñư c g i là tương ñương. Ph n bù c a hàm Boole F là hàm F v i F (x1, x2, …, xn) =
F ( x1 , x2 ,..., xn ) . Gi s F và G là các hàm Boole b c n. T ng Boole F+G và tích Boole
FG ñư c ñ nh nghĩa b i:
(F+G)(x1, x2, …, xn) = F(x1, x2, …, xn)+G(x1, x2, …, xn),
(FG)(x1, x2, …, xn) = F(x1, x2, …, xn)G(x1, x2, …, xn).
Thí d 2:
B c S các hàm Boole
Theo quy t c nhân c a phép ñ m ta suy 1 4
n
ra r ng có 2 b n ph n t khác nhau g m 2 16
các s 0 và 1. Vì hàm Boole là vi c gán 0 3 256
ho c 1 cho m i b trong s 2 b n ph n n 4 65.536
5 4.294.967.296
t ñó, nên l i theo quy t c nhân s có
n 6 18.446.744.073.709.551.616
2 2 các hàm Boole khác nhau.
117
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
B ng sau cho giá tr c a 16 hàm Boole b c 2 phân bi t:
x y F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16
0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0
0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1
1 0 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0
1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0
trong ñó có m t s hàm thông d ng như sau:
- Hàm F1 là hàm h ng 0,
- Hàm F2 là hàm h ng 1,
- Hàm F3 là hàm h i, F3(x,y) ñư c vi t là xy (hay x ∧ y),
- Hàm F4 là hàm tuy n, F4(x,y) ñư c vi t là x+y (hay x ∨ y),
- Hàm F5 là hàm tuy n lo i, F5(x,y) ñư c vi t là x ⊕ y,
- Hàm F6 là hàm kéo theo, F6(x,y) ñư c vi t là x ⇒ y,
- Hàm F7 là hàm tương ñương, F7(x,y) ñư c vi t là x ⇔ y,
- Hàm F8 là hàm Vebb, F8(x,y) ñư c vi t là x ↓ y,
- Hàm F9 là hàm Sheffer, F9(x,y) ñư c vi t là x ↑ y.
Thí d 3: Các giá tr c a hàm Boole b c 3 F(x, y, z) = xy+ z ñư c cho b i b ng sau:
x y z xy z F(x, y, z) = xy+ z
0 0 0 0 1 1
0 0 1 0 0 0
0 1 0 0 1 1
0 1 1 0 0 0
1 0 0 0 1 1
1 0 1 0 0 0
1 1 0 1 1 1
1 1 1 1 0 1
8.2.2. ð nh nghĩa: Cho x là m t bi n Boole và σ ∈ B. Ký hi u:
σ x khi σ = 1,
x =
x khi σ = 0.
D th y r ng xσ = 1 ⇔ x = σ . V i m i hàm Boole F b c n, ký hi u:
TF = {(x1, x2, …, xn)∈ B | F(x1, x2, …, xn)=1}
n
Và g i nó là t p ñ c trưng c a hàm F. Khi ñó ta có:
TF = TF , TF+G = TF ∪ TG, TFG = TF ∩ TG.
Cho n bi n Boole x1, x2, …, xn. M t bi u th c d ng:
σ σ2 σk
xi 1 xi K xi
1 2 k
118
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
trong ñó σ 1 ,σ 2 ,K,σ k ∈ B, 1 ≤ i1 < i2 < L < ik ≤ n ñư c g i là m t h i sơ c p c a n
bi n x1, x2, …, xn. S các bi n xu t hi n trong m t h i sơ c p ñ oc g i là h ng c a c a
h i sơ c p ñó.
Cho F là m t hàm Boole b c n. N u F ñư c bi u di n dư i d ng t ng (tuy n) c a
m t s h i sơ c p khác nhau c a n bi n thì bi u di n ñó ñư c g i là d ng t ng (tuy n)
chu n t c c a F. D ng t ng (tuy n) chu n t c hoàn toàn là d ng chu n t c duy nh t c a
F mà trong ñó các h i sơ c p ñ u có h ng n.
Thí d 4: x y + x y là m t d ng t ng chu n t c c a hàm x ⊕ y.
x + y và x y + x y + x y là các d ng t ng chu n t c c a hàm Sheffer x ↑ y.
8.2.3. M nh ñ : M i hàm Boole F b c n ñ u có th bi u di n dư i d ng:
F ( x1 , x2 ,K, xn ) = ∑ x1 1 K xiσ i F (σ 1,K,σ i , xi +1,K, xn )
σ
i
(1),
(σ 1 ,K,σ n )∈B
trong ñó i là s t nhiên b t kỳ, 1 ≤ i ≤ n.
Ch ng minh: G i G là hàm Boole v ph i c a (1). Cho (x1, x2, …, xn)∈ TF. Khi ñó s
h ng ng v i b giá tr σ 1= x1, …, σ i= xi trong t ng v ph i c a (1) b ng 1, do ñó
(x1, x2, …, xn)∈ TG. ð o l i, n u (x1, x2, …, xn)∈TG t c là v ph i b ng 1 thì ph i x y ra
b ng 1 t i m t s h ng nào ñó, ch ng h n t i s h ng ng v i b giá tr ( σ 1, …, σ i),
khi ñó x1= σ 1, …, xi= σ i và f( σ 1,…, σ i, xi+1,…, xn)=1 hay (x1, x2, …, xn)∈TF. V y
TF=TG hay F=G.
Cho i=1 trong m nh ñ trên và nh n xét r ng vai trò c a các bi n xi là như nhau,
ta ñư c h qu sau.
8.2.4. H qu : M i hàm Boole F b c n ñ u có th ñư c khai tri n theo m t bi n xi:
F ( x1 ,K, xn ) = xi F ( x1 ,K, xi −1 ,0, xi +1 ,K, xn ) + xi F ( x1 ,K, xi −1 ,1, xi +1 ,K, xn ) .
Cho i=n trong m nh ñ trên và b ñi các nhân t b ng 1 trong tích, các s h ng
b ng 0 trong t ng, ta ñư c h qu sau.
8.2.5. H qu : M i hàm Boole F b c n ñ u có th ñư c khai tri n dư i d ng:
σ
F ( x1 ,K, xn ) = ∑ x1 1 K xσ n .
n
(σ 1 ,K,σ n )∈TF
8.2.6. Chú ý: T H qu 8.2.5, ta suy ra r ng m i hàm Boole ñ u có th bi u di n dư i
d ng t ng (tuy n) chu n t c hoàn toàn. Như v y m i hàm Boole ñ u có th bi u di n
b ng m t bi u th c Boole ch ch a ba phép tích (h i), t ng (tuy n), bù (ph ñ nh). Ta
nói r ng h {tích, t ng, bù} là ñ y ñ .
B ng ñ i ng u, ta có th ch ng minh m t k t qu tương t b ng vi c thay tích
b i t ng và ngư c l i, t ñó d n t i vi c bi u di n F qua m t tích các t ng. Bi u di n
này ñư c g i là d ng tích (h i) chu n t c hoàn toàn c a F:
119
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
σ
F ( x1 ,K, xn ) = ∏ ( x1 1 + K + xσ n )
n
(σ 1 ,K,σ n )∈TF
Thí d 5: D ng t ng chu n t c hoàn toàn c a hàm F cho trong Thí d 3 là:
F ( x, y, z ) = x y z + x y z + x y z + xy z + xyz ,
và d ng tích chu n t c hoàn toàn c a nó là:
F ( x, y, z ) = ( x + y + z )( x + y + z )( x + y + z ) .
8.3. M CH LÔGIC.
8.3.1. C ng lôgic:
x1
x2
M
xn-1 F(x1, x2, …, xn)
xn
Xét m t thi t b như hình trên, có m t s ñư ng vào (d n tín hi u vào) và ch có
m t ñư ng ra (phát tín hi u ra). Gi s các tín hi u vào x1, x2, …, xn (ta g i là ñ u vào
hay input) cũng như tín hi u ra F (ñ u ra hay output) ñ u ch có hai tr ng thái khác
nhau, t c là mang m t bit thông tin, mà ta ký hi u là 0 và 1.
Ta g i m t thi t b v i các ñ u vào và ñ u ra mang giá tr 0, 1 như v y là m t
m ch lôgic.
ð u ra c a m t m ch lôgic là m t hàm Boole F c a các ñ u vào x1, x2, …, xn. Ta
nói m ch lôgic trong hình trên th c hi n hàm F.
Các m ch lôgic ñư c t o thành t m t s m ch cơ s , g i là c ng lôgic. Các c ng
lôgic sau ñây th c hi n các hàm ph ñ nh, h i và tuy n.
1. C ng NOT: C ng NOT th c hi n hàm ph ñ nh. C ng ch có m t ñ u vào. ð u ra
F(x) là ph ñ nh c a ñ u vào x.
0 khi = 1, F(x)= x
F ( x) = x = x
1 khi x = 0.
Ch ng h n, xâu bit 100101011 qua c ng NOT cho xâu bit 011010100.
2. C ng AND: C ng AND th c hi n hàm h i. ð u ra F(x,y) là h i (tích) c a các ñ u
vào.
1 khi x = y = 1,
F ( x, y ) = xy =
0 trong các trư ng h p khác.
x F(x,y)=xy x F(x,y,z)=xyz
y
y z
Ch ng h n, hai xâu bit 101001101 và 111010110 qua c ng AND cho 101000100.
120
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
3. C ng OR: C ng OR th c hi n hàm tuy n (t ng). ð u ra F(x,y) là tuy n (t ng) c a
các ñ u vào.
1 khi x = 1 hay y = 1,
F ( x, y ) = x + y =
0 khi x = y = 0.
x F(x,y)=x+y x F=x+y+z+t
y
z
y t
Ch ng h n, hai xâu bit 101001101 và 111010100 qua c ng OR cho 111011101.
8.3.2. M ch lôgic:
1. T h p các c ng: Các c ng lôgic có th l p ghép ñ ñư c nh ng m ch lôgic th c
hi n các hàm Boole ph c t p hơn. Như ta ñã bi t r ng m t hàm Boole b t kỳ có th bi u
di n b ng m t bi u th c ch ch a các phép −, ., +. T ñó suy ra r ng có th l p ghép
thích h p các c ng NOT, AND, OR ñ ñư c m t m ch lôgic th c hi n m t hàm Boole
b t kỳ.
Thí d 6: Xây d ng m t m ch lôgic th c hi n hàm Boole cho b i b ng sau.
x y z F(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
Theo b ng này, hàm F có d ng t ng (tuy n) chu n t c hoàn toàn là:
F ( x, y, z ) = xyz + xy z + x yz .
Hình dư i ñây v m ch lôgic th c hi n hàm F ñã cho.
x
y
z
F = xyz + xy z + x yz
121
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Bi u th c c a F(x, y, z) có th rút g n:
xyz + xy z + x yz = xy ( z + z ) + x yz = xy + x yz .
Hình dư i ñây cho ta m ch lôgic th c hi n hàm xy + x yz .
x •
y •
F = xy + x yz
z
Hai m ch lôgic trong hai hình trên th c hi n cùng m t hàm Boole, ta nói ñó là
hai m ch lôgic tương ñương, nhưng m ch lôgic th hai ñơn gi n hơn.
V n ñ tìm m ch lôgic ñơn gi n th c hi n m t hàm Boole F cho trư c g n li n
v i v n ñ tìm bi u th c ñơn gi n nh t bi u di n hàm y. ðây là v n ñ khó và lý thú,
tuy ý nghĩa th c ti n c a nó không còn như m y ch c năm v trư c.
Ta v a xét vi c th c hi n m t hàm Boole b t kỳ b ng m t m ch lôgic ch g m
các c ng NOT, AND, OR.
D a vào ñ ng th c x + y = x. y cũng như xy = x + y , cho ta bi t h {., −} và h
{+, −} cũng là các h ñ y ñ . Do ñó có th th c hi n m t hàm Boole b t kỳ b ng m t
m ch lôgic ch g m có các c ng NOT, AND ho c NOT, OR.
0 khi x = y = 1,
Xét hàm Sheffer F ( x, y ) = x ↑ y = M ch lôgic th c hi n
1 khi x = 0 hay y = 0.
hàm ↑ g i là c ng NAND, ñư c v như hình dư i ñây.
x x↑ y
O
y
D a vào các ñ ng th c x = x ↑ x, xy = ( x ↑ y ) ↑ ( x ↑ y ), x + y = ( x ↑ x) ↑ ( y ↑ y ) ,
cho ta bi t h { ↑ } là ñ y ñ , nên b t kỳ m t hàm Boole nào cũng có th th c hi n ñư c
b ng m t m ch lôgic ch g m có c ng NAND.
0 khi x = 1 hay y = 1,
Xét hàm Vebb F ( x, y ) = x ↓ y = M ch lôgic th c hi n hàm
1 khi x = y = 0.
↓ g i là c ng NOR, ñư c v như hình dư i ñây.
x x↓ y
y O
Tương t h { ↓ } là ñ y ñ nên b t kỳ hàm Boole nào cũng có th th c hi n ñư c
b ng m t m ch lôgic ch g m có c ng NOR.
M t phép toán lôgic quan tr ng khác là phép tuy n lo i:
122
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
0 khi x = y,
F ( x, y ) = x ⊕ y =
1 khi x ≠ y.
M ch lôgic này là m t c ng lôgic, g i là c ng XOR, ñư c v như hình dư i ñây.
x x⊕ y
y
2. M ch c ng: Nhi u bài toán ñòi h i ph i xây d ng nh ng m ch lôgic có nhi u ñư ng
ra, cho các ñ u ra F1, F2, …, Fk là các hàm Boole c a các ñ u vào x1, x2, …, xn.
x1
F1(x1, x2, …, xn)
x2
M F2(x1, x2, …, xn)
xn-1 M
Fk(x1, x2, …, xn)
xn
Ch ng h n, ta xét phép c ng hai s t nhiên t các khai tri n nh phân c a chúng.
Trư c h t, ta s xây d ng m t m ch có th du c dùng ñ tìm x+y v i x, y là hai s 1-bit.
ð u vào m ch này s là x và y. ð u ra s là m t s 2-bit cs , trong ñó s là bit t ng và c
là bit nh .
0+0 = 00 x y c s
0+1 = 01 0 0 0 0
0 1 0 1
1+0 = 01
1 0 0 1
1+1 = 10 1 1 1 0
T b ng trên, ta th y ngay s = x ⊕ y , c = xy . Ta v ñư c m ch th c hi n hai hàm
s = x ⊕ y và c = xy như hình dư i ñây. M ch này g i là m ch c ng hai s 1-bit hay
m ch c ng bán ph n, ký hi u là DA.
s = x⊕ y
x s
DA
y c
x • c = xy
y •
Xét phép c ng hai s 2-bit a 2 a1 và b2 b1 ,
a 2 a1
b2 b1
Th c hi n phép c ng theo t ng c t, c t th nh t (t ph i sang trái) ta tính a1 + b1 ñư c
bit t ng s1 và bit nh c1; c t th hai, ta tính a 2 + b2 + c1 , t c là ph i c ng ba s 1-bit.
123
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Cho x, y, z là ba s 1-bit. T ng x+y+z là m t s 2-bit cs , trong ñó s là bit t ng
c a x+y+z và c là bit nh c a x+y+z. Các hàm Boole s và c theo các bi n x, y, z ñư c
xác ñ nh b ng b ng sau:
x y z 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
1 1 1 1 1
T b ng này, d dàng th y r ng:
s = x⊕ y⊕z.
Hàm c có th vi t dư i d ng t ng chu n t c hoàn toàn là:
c = x yz + x yz + xy z + xyz .
Công th c c a c có th rút g n:
c = z ( x y + x y ) + xy ( z + z ) = z ( x ⊕ y ) + xy .
Ta v ñư c m ch th c hi n hai hàm Boole s = x ⊕ y ⊕ z và c = z ( x ⊕ y ) + xy
như hình dư i ñây, m ch này là ghép n i c a hai m ch c ng bán ph n (DA) và m t
c ng OR. ðây là m ch c ng ba s 1-bit hay m ch c ng toàn ph n, ký hi u là AD.
z
• s
•
x •
y • c
z
x s x
s
DA DA y AD
y c
z
c
124
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Tr l i phép c ng hai s 2-bit a 2 a1 và b2 b1 . T ng a 2 a1 + b2 b1 là m t s 3-bit
c2 s 2 s1 , trong ñó s1 là bit t ng c a a1+b1: s1 = a1 ⊕ b1 , s2 là bit t ng c a a2+b2+c1, v i c1
là bit nh c a a1+b1: s 2 = a2 ⊕ b2 ⊕ c1 và c2 là bit nh c a a2+b2+c1.
Ta có ñư c m ch th c hi n ba hàm Boole s1, s2, c2 như hình dư i ñây.
b2 a2 b1 a1
AD DA
c1
c2 s2 s1
D dàng suy ra m ch c ng hai s n-bit, v i n là m t s nguyên dương b t kỳ.
Hình sau cho m t m ch c ng hai s 4-bit.
b4 a4 b3 a3 b2 a 2 b1 a1
AD AD AD DA
c3 c2 c1
c4 s4 s3 s2 s1
8.4. C C TI U HOÁ CÁC M CH LÔGIC.
Hi u qu c a m t m ch t h p ph thu c vào s các c ng và s b trí các c ng
ñó. Quá trình thi t k m t m ch t h p ñư c b t ñ u b ng m t b ng ch rõ các giá tr
ñ u ra ñ i v i m i m t t h p các giá tr ñ u vào. Ta luôn luôn có th s d ng khai tri n
t ng các tích c a m ch ñ tìm t p các c ng lôgic th c hi n m ch ñó. Tuy nhiên,khai
tri n t ng các tích có th ch a các s h ng nhi u hơn m c c n thi t. Các s h ng trong
khai tri n t ng các tích ch khác nhau m t bi n, sao cho trong s h ng này xu t hi n
bi n ñó và trong s h ng kia xu t hi n ph n bù c a nó, ñ u có th ñư c t h p l i.
Ch ng h n, xét m ch có ñ u ra b ng 1 khi và ch khi x = y = z = 1 ho c x = z = 1 và y =
0. Khai tri n t ng các tích c a m ch này là xyz + x yz . Hai tích trong khai tri n này ch
khác nhau m t bi n, ñó là bi n y. Ta có th t h p l i như sau:
xyz + x yz = ( y + y ) xz = 1xz = xz .
125
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Do ñó xz là bi u th c v i ít phép toán hơn bi u di n m ch ñã cho. M ch th hai ch
dùng m t c ng, trong khi m ch th nh t ph i dùng ba c ng và m t b ñ o (c ng NOT).
8.4.1. B n ñ Karnaugh:
ð làm gi m s các s h ng trong m t bi u th c Boole bi u di n m t m ch, ta
c n ph i tìm các s h ng ñ t h p l i. Có m t phương pháp ñ th , g i là b n ñ
Karnaugh, ñư c dùng ñ tìm các s h ng t h p ñư c ñ i v i các hàm Boole có s bi n
tương ñ i nh . Phương pháp mà ta mô t dư i ñây ñã ñư c Maurice Karnaugh ñưa ra
vào năm 1953. Phương pháp này d a trên m t công trình trư c ñó c a E.W. Veitch. Các
b n ñ Karnaugh cho ta m t phương pháp tr c quan ñ rút g n các khai tri n t ng các
tích, nhưng chúng không thích h p v i vi c cơ khí hoá quá trình này. Trư c h t, ta s
minh ho cách dùng các b n ñ Karnaugh ñ rút g n bi u th c c a các hàm Boole hai
bi n.
Có b n h i sơ c p khác nhau trong khai tri n t ng các tích c a m t hàm Boole có
hai bi n x và y. M t b n ñ Karnaugh ñ i v i m t hàm y y
Boole hai bi n này g m b n ô vuông, trong ñó hình vuông
x xy xy
bi u di n h i sơ c p có m t trong khai tri n ñư c ghi s 1.
Các hình ô ñư c g i là k nhau n u các h i sơ c p mà chúng x xy xy
bi u di n ch khác nhau m t bi n.
Thí d 7: Tìm các b n ñ Karnaugh cho các bi u th c:
a) xy + x y b) x y + x y c) x y + x y + x y
và rút g n chúng.
Ta ghi s 1 vào ô vuông khi h i sơ c p ñư c bi u di n b i ô ñó có m t trong khai
tri n t ng các tích. Ba b n ñ Karnaugh ñư c cho trên hình sau.
y y y
x 1 1 x 1
x 1 1 x 1 1
Vi c nhóm các h i sơ c p ñư c ch ra trong hình trên b ng cách s d ng b n ñ
Karnaugh cho các khai tri n ñó. Khai tri n c c ti u c a t ng các tích này tương ng là:
a) y, b) x y + x y , c) x + y .
B n ñ Karnaugh ba bi n là m t hình ch nh t ñư c chia thành tám ô. Các ô ñó
bi u di n tám h i sơ c p có ñư c. Hai ô ñư c yz yz yz yz
g i là k nhau n u các h i sơ c p mà chúng
bi u di n ch khác nhau m t bi n. M t trong x xyz xy z xyz x yz
các cách ñ l p b n ñ Karnaugh ba bi n ñư c
x x yz xy z xyz x yz
cho trong hình bên.
126
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
ð rút g n khai tri n t ng các tích ba bi n, ta s dùng b n ñ Karnaugh ñ nh n
d ng các h i sơ c p có th t h p l i. Các kh i g m hai ô k nhau bi u di n c p các h i
sơ c p có th ñư c t h p l i thành m t tích c a hai bi n; các kh i 2 x 2 và 4 x 1 bi u
di n các h i sơ c p có th t h p l i thành m t bi n duy nh t; còn kh i g m t t c tám ô
bi u di n m t tích không có m t bi n nào, c th ñây là bi u th c 1.
Thí d 8: Dùng các b n ñ Karnaugh ba bi n ñ rút g n các khai tri n t ng các tích sau:
a) xy z + x y z + x yz + x y z ,
b) x yz + x y z + x yz + x yz + x y z ,
c) xyz + xy z + x yz + x y z + x yz + x yz + x y z .
B n ñ Karnaugh cho nh ng khai tri n t ng các tích này ñư c cho trong hình
sau:
yz yz yz yz yz yz yz yz
x 1 1 x 1 1
x 1 1 x 1 1 1
yz yz yz yz
x 1 1 1 1
1 1 1
x
Vi c nhóm thành các kh i cho th y r ng các khai tri n c c ti u thành các t ng Boole
c a các tích Boole là:
a) x z + y z + x yz , b) y + xz , c) x + y + z .
B n ñ Karnaugh b n bi n là m t hình vuông ñư c chia làm 16 ô. Các ô này bi u
di n 16 h i sơ c p có ñư c. M t trong nh ng cách l p b n ñ Karnaugh b n bi n ñư c
cho trong hình dư i ñây.
yz yz yz yz
wx wxyz wxy z wx y z wx yz
w x w x yz wxy z wx y z wx yz
w x w x yz wxy z wx y z w x yz
wx wxyz wxy z wx y z wx yz
Hai ô ñư c g i là k nhau n u các h i sơ c p mà chúng bi u di n ch khác nhau
m t bi n. Do ñó, m i m t ô k v i b n ô khác. S rút g n m t khai tri n t ng các tích
b n bi n ñư c th c hi n b ng cách nh n d ng các kh i g m 2, 4, 8 ho c 16 ô bi u di n
các h i sơ c p có th t h p l i ñư c. M i ô bi u di n m t h i sơ c p ho c ñư c dùng ñ
l p m t tích có ít bi n hơn ho c ñư c ñưa vào trong khai tri n. Cũng như trong trư ng
127
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
h p b n ñ Karnaugh hai và ba bi n, m c tiêu là c n ph i nh n d ng các kh i l n nh t
có ch a các s 1 b ng cách dùng m t s ít nh t các kh i, mà trư c h t là các kh i l n
nh t.
8.4.2. Phương pháp Quine-McCluskey:
8.4.2.1. M ñ u: Ta ñã th y r ng các b n ñ Karnaugh có th ñư c dùng ñ t o bi u
th c c c ti u c a các hàm Boole như t ng c a các tích Boole. Tuy nhiên, các b n ñ
Karnaugh s r t khó dùng khi s bi n l n hơn b n. Hơn n a, vi c dùng các b n ñ
Karnaugh l i d a trên vi c rà soát tr c quan ñ nh n d ng các s h ng c n ñư c nhóm
l i. Vì nh ng nguyên nhân ñó, c n ph i có m t th t c rút g n nh ng khai tri n t ng các
tích có th cơ khí hoá ñư c. Phương pháp Quine-McCluskey là m t th t c như v y. Nó
có th ñư c dùng cho các hàm Boole có s bi n b t kỳ. Phương pháp này ñư c W.V.
Quine và E.J. McCluskey phát tri n vào nh ng năm 1950. V cơ b n, phương pháp
Quine-McCluskey có hai ph n. Ph n ñ u là tìm các s h ng là ng viên ñ ñưa vào khai
tri n c c ti u như m t t ng các tích Boole mà ta g i là các nguyên nhân nguyên t . Ph n
th hai là xác ñ nh xem trong s các ng viên ñó, các s h ng nào là th c s dùng ñư c.
8.4.2.2. ð nh nghĩa: Cho hai hàm Boole F và G b c n. Ta nói G là m t nguyên nhân
c a F n u TG ⊂ TF, nghĩa là G ⇒ F là m t h ng ñúng.
D th y r ng m i h i sơ c p trong m t d ng t ng chu n t c c a F là m t nguyên
nhân c a F. H i sơ c p A c a F ñư c g i là m t nguyên nhân nguyên t c a F n u trong
A xoá ñi m t bi n thì h i nh n ñu c không còn là nguyên nhân c a F.
N u F1, …, Fk là các nguyên nhân c a F thì TFi ⊂ TF , 1 ≤ i ≤ k . Khi ñó
k k
Tk = U TFi ⊂ TF . Do ñó ∑ Fi là m t nguyên nhân c a F.
∑ Fi i =1 i =1
i =1
Cho S là m t h các nguyên nhân c a F. Ta nói r ng h S là ñ y ñ ñ i v i F n u
F= ∑ G , nghĩa là TF = U
TG .
G∈S G∈S
8.4.2.3. M nh ñ : H các nguyên nhân nguyên t c a hàm F là m t h ñ y ñ .
Ch ng minh: G i S là h các nguyên nhân nguyên t c a F. Ta có TG ⊂ TF , ∀g ∈ S ,
Nên T G =
∑ U
TG ⊂ TF . Gi s d ng t ng chu n t c hoàn toàn c a F là F = G'∑
G∈S G∈S G '∈S '
nên TF = UTG' .
G '∈S '
Xét G '∈ S ' , n u G’ không ph i là nguyên nhân nguyên t c a F thì b ng cách
xoá b t m t s bi n trong G’ ta thu ñư c nguyên nhân nguyên t G c a F. Khi ñó
TG ' ⊂ TG và U
TG ' ⊂ U
TG hay TF ⊂ U
TG . Vì v y TF = U
TG hay F = ∑
G.
G '∈S ' G∈S G∈S G∈S G∈S
128
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
D ng t ng chu n t c F = ∑ G ñư c g i là d ng t ng chu n t c thu g n c a F.
G∈S
8.4.2.4. Phương pháp Quine-McCluskey tìm d ng t ng chu n t c thu g n:
Gi s F là m t hàm Boole n bi n x1, x2, …, xn. M i h i sơ c p c a n bi n ñó
ñư c bi u di n b ng m t dãy n ký hi u trong b ng {0, 1, −} theo quy ư c: ký t th i là
1 hay 0 n u xi có m t trong h i sơ c p là bình thư ng hay v i d u ph ñ nh, còn n u xi
không có m t thì ký t này là −. Ch ng h n, h i sơ c p c a 6 bi n x1, …, x6 là x1 x3 x4 x6
ñư c bi u di n b i 0−11−0. Hai h i sơ c p ñư c g i là k nhau n u các bi u di n nói
trên c a chúng ch khác nhau m t v trí 0, 1. Rõ ràng các h i sơ c p ch có th dán
ñư c v i nhau b ng phép dán Ax + A x = A n u chúng là k nhau.
Thu t toán ñư c ti n hành như sau: L p m t b ng g m nhi u c t ñ ghi các k t
qu dán. Sau ñó l n lư t th c hi n các bư c sau:
Bư c 1: Vi t vào c t th nh t các bi u di n c a các nguyên nhân h ng n c a hàm Boole
F. Các bi u di n ñư c chia thành t ng nhóm, các bi u di n trong m i nhóm có s các ký
hi u 1 b ng nhau và các nhóm x p theo th t s các ký hi u 1 tăng d n.
Bư c 2: L n lư t th c hi n t t c các phép dán các bi u di n trong nhóm i v i các bi u
di n trong nhóm i+1 (i=1, 2, …). Bi u di n nào tham gia ít nh t m t phép dán s ñư c
ghi nh n m t d u * bên c nh. K t qu dán ñư c ghi vào c t ti p theo.
Bư c 3: L p l i Bư c 2 cho c t k ti p cho ñ n khi không thu thêm ñư c c t nào m i.
Khi ñó t t c các bi u di n không có d u * s cho ta t t c các nguyên nhân nguyên t
c a F.
Thí d 9: Tìm d ng t ng chu n t c thu g n c a các hàm Boole:
F1 = w x yz + wx yz + w x yz + w x yz + w x yz + wxyz + wxyz ,
F2 = w x y z + w x yz + w x yz + wx y z + wx yz + wxy z + wxyz .
0001* 0−01* 0−−1 0010* 001− 11−−
0101* 00−1* −0−1 0011* −011
0011* −001* −−11 1100* 110−*
1001* −011* 1011* 11−0*
1011* 10−1* 1101* 1−11
0111* 01−1* 1110* 11−1*
1111* 0−11* 1111* 111−*
1−11*
−111*
T các b ng trên ta có d ng t ng chu n t c thu g n c a F1 và F2 là:
F1 = wz + xz + yz ,
F2 = w x y + x yz + wyz + wx.
129
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
8.4.2.5. Phương pháp Quine-McCluskey tìm d ng t ng chu n t c t i thi u:
Sau khi tìm ñư c d ng t ng chu n t c thu g n c a hàm Boole F, nghĩa là tìm
ñư c t t c các nguyên nhân nguyên t c a nó, ta ti p t c phương pháp Quine-
McCluskey tìm d ng t ng chu n t c t i thi u (c c ti u) c a F như sau.
L p m t b ng ch nh t, m i c t ng v i m t c u t o ñơn v c a F (m i c u t o
ñơn v là m t h i sơ c p h ng n trong d ng t ng chu n t c hoàn toàn c a F) và m i dòng
ng v i m t nguyên nhân nguyên t c a F. T i ô (i, j), ta ñánh d u c ng (+) n u nguyên
nhân nguyên t dòng i là m t ph n con c a c u t o ñơn v c t j. Ta cũng nói r ng
khi ñó nguyên nhân nguyên t i là ph c u t o ñơn v j. M t h S các nguyên nhân
nguyên t c a F ñư c g i là ph hàm F n u m i c u t o ñơn v c a F ñ u ñư c ph ít
nh t b i m t thành viên c a h . D th y r ng n u h S là ph hàm F thì nó là ñ y ñ ,
nghĩa là t ng c a các thành viên trong S là b ng F.
M t nguyên nhân nguyên t ñư c g i là c t y u n u thi u nó thì m t h các
nguyên nhân nguyên t không th ph hàm F. Các nguyên nhân nguyên t c t y u ñư c
tìm như sau: t i nh ng c t ch có duy nh t m t d u +, xem d u + ñó thu c dòng nào thì
dòng ñó ng v i m t nguyên nhân nguyên t c t y u.
Vi c l a ch n các nguyên nhân nguyên t trên b ng ñã ñánh d u, ñ ñư c m t
d ng t ng chu n t c t i thi u, có th ti n hành theo các bư c sau.
Bư c 1: Phát hi n t t c các nguyên nhân nguyên t c t y u.
Bư c 2: Xoá t t c các c t ñư c ph b i các nguyên nhân nguyên t c t y u.
Bư c 3: Trong b ng còn l i, xoá n t nh ng dòng không còn d u + và sau ñó n u có hai
c t gi ng nhau thì xoá b t m t c t.
Bư c 4: Sau các bư c trên, tìm m t h S các nguyên nhân nguyên t v i s bi n ít nh t
ph các c t còn l i.
T ng c a các nguyên nhân nguyên t c t y u và các nguyên nhân nguyên t
trong h S s là d ng t ng chu n t c t i thi u c a hàm F.
Các bư c 1, 2, 3 có tác d ng rút g n b ng trư c khi l a ch n. ð ph c t p ch
y u n m Bư c 4. Tình hu ng t t nh t là m i nguyên nhân nguyên t ñ u là c t y u.
Trư ng h p này không ph i l a ch n gì và hàm F có duy nh t m t d ng t ng chu n t c
t i thi u cũng chính là d ng t ng chu n t c thu g n. Tình hu ng x u nh t là không có
nguyên nhân nguyên t nào là c t y u. Trư ng h p này ta ph i l a ch n toàn b b ng.
Thí d 10: Tìm d ng t ng chu n t c t i thi u c a các hàm Boole cho trong Thí d 9.
w x yz wx yz w x yz w x yz w x yz wxyz wxyz
wz + + +
xz + + + +
yz + + + +
130
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Các nguyên nhân nguyên t ñ u là c t y u nên d ng t ng chu n t c t i thi u c a F1 là:
F1 = wz + xz + yz
wxy z w x yz w x yz wx y z wx yz wxy z wxyz
wx + + + +
wxy + +
x yz + +
wyz + +
Các nguyên nhân nguyên t c t y u n m dòng 1 và 2. Sau khi rút g n, b ng
còn dòng 3, 4 và m t c t 3. Vi c ch n S khá ñơn gi n: có th ch n m t trong hai nguyên
nhân nguyên t còn l i. Vì v y ta ñư c hai d ng t ng chu n t c t i thi u là:
F2 = wx + w x y + x yz ,
F2 = wx + w x y + wyz .
131
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
BÀI T P CHƯƠNG VIII:
1. Cho S là t p h p các ư c nguyên dương c a 70, v i các phép toán •, + và ’ ñư c ñ nh
nghĩa trên S như sau:
a • b = UCLN(a, b), a + b = BCNN(a, b), a’ = 70/a.
Ch ng t r ng S cùng v i các phép toán •, + và ’ l p thành m t ñ i s Boole.
2. Ch ng minh tr c ti p các ñ nh lý 6b, 7b, 8b (không dùng ñ i ng u ñ suy ra t 6a,
7a, 8a).
3. Ch ng minh r ng:
a) (a+b).(a+b’) = a;
b) (a.b)+(a’.c) = (a+c).(a’+b).
4. Cho các hàm Boole F1, F2, F3 xác ñ nh b i b ng sau:
x y z F1 F2 F3
0 0 0 1 1 0
0 0 1 1 0 1
0 1 0 0 1 1
0 1 1 1 1 0
1 0 0 1 0 1
1 0 1 0 0 1
1 1 0 0 1 1
1 1 1 1 1 1
V m ch th c hi n các hàm Boole này.
5. Hãy dùng các c ng NAND ñ xây d ng các m ch v i các ñ u ra như sau:
a) x b) xy c) x+y d) x ⊕ y.
6. Hãy dùng các c ng NOR ñ xây d ng các m ch v i các ñ u ra ñư c cho trong Bài
t p 5.
7. Hãy dùng các c ng NAND ñ d ng m ch c ng bán ph n.
8. Hãy dùng các c ng NOR ñ d ng m ch c ng bán ph n.
9. Dùng các b n ñ Karnaugh, tìm d ng t ng chu n t c t i thi u (khai tri n c c ti u) c a
các hàm Boole ba bi n sau:
a) F = x yz + x yz .
b) F = xyz + xy z + + x yz + x y z .
c) F = xy z + + x yz + x y z + x yz + x yz .
d) F = xyz + x yz + x y z + x yz + x y z + x y z .
132
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
10. Dùng các b n ñ Karnaugh, tìm d ng t ng chu n t c t i thi u c a các hàm Boole
b n bi n sau:
a) F = wxyz + wx yz + wx y z + w x y z + w x yz .
b) F = wxy z + wx yz + w x yz + wx yz + w x y z + w x yz .
c) F = wxyz + wxy z + wx yz + w x yz + w x y z + wx yz + w x y z + w x yz .
d) F = wxyz + wxy z + wx yz + w x yz + w x y z + wxyz + w x yz + w x y z + w x yz .
11. Dùng phương pháp Quine-McCluskey, tìm d ng t ng chu n t c t i thi u c a các
hàm Boole ba bi n cho trong Bài t p 9 và hãy v m ch th c hi n các d ng t i thi u tìm
ñư c.
12. Dùng phương pháp Quine-McCluskey, tìm d ng t ng chu n t c t i thi u c a các
hàm Boole b n bi n cho trong Bài t p 9 và hãy v m ch th c hi n các d ng t i thi u tìm
ñư c.
13. Hãy gi i thích làm th nào có th dùng các b n ñ Karnaugh ñ rút g n d ng tích
chu n t c (tích các t ng) hoàn toàn c a m t hàm Boole ba bi n. (G i ý: ðánh d u b ng
s 0 t t c các tuy n sơ c p trong bi u di n và t h p các kh i c a các tuy n sơ c p.)
14. Dùng phương pháp Bài t p 13, hãy rút g n d ng tích chu n t c hoàn toàn:
F = ( x + y + z )( x + y + z )( x + y + z )( x + y + z ) .
133
nguon tai.lieu . vn
