intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

[Giáo trình Toán rời rạc] - Chương8 - Đại số Boole

Chia sẻ: Trần Bá Trung5 | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST
Báo xấu
205
lượt xem 77
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu " [Giáo trình Toán rời rạc] - Chương8 - Đại số Boole " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: [Giáo trình Toán rời rạc] - Chương8 - Đại số Boole

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2