Bài giảng Đại số Boole

Nội dung text: Bài giảng Đại số Boole

1. ĐẠI SỐ BOOLE
2. Đi s Boole Nguy n Th Vinh-ĐHKH CH ƯƠ NG VI ĐẠI S Ố BOOLE Trong máy tính điện t ử và các d ụng c ụ điện t ử khác các m ạch điện t ử đề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. Các chuy ển m ạch điện t ử quang h ọc có th ể nghiên c ứu bằng cách dùng t ập {0,1} và các qui t ắc c ủa đại s ố Boole. 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. Trong ch ươ ng này chúng ta sẽ tìm hi ểu 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ính t ổng và tích được dùng để bi ểu di ễn m ột hàm Boole. 6.1. KHÁI NI ỆM ĐẠ I S Ố BOOLE Tr ước h ết ta làm quen v ới các phép toán và qui t ắc làm vi ệc trên t ập {0,1}. Phép toán được dùng nhi ều nh ất là phép l ấy ph ần bù, phép l ấy t ổng và phép l ấy tích. Ph ần bù c ủa m ột ph ần t ử được kí hi ệu b ởi ¬ ho ặc NOT ¬0=1 và ¬1=0 Tổng Boole được kí hi ệu và + ho ặc OR có các giá tr ị sau 1 + 1=1; 1 + 0=1; 0 + 1=1; 0 + 0=0; Tích Boole được kí hi ệu là . ho ặc AND có các giá tr ị sau 1 . 1 =1; 1 . 0=0; 0 . 1 =0; 0 . 0=0; 137
3. Đi s Boole Nguy n Th Vinh-ĐHKH Ví d ụ: Tìm giá tr ị c ủa 1.0 + ¬(1+0) 1.0 + ¬(1+0)= 1.0 + ¬1= 1.0 + 0= 0+0=0 Đại s ố Boole là các phép toán và quy t ắc làm vi ệc v ới t ập {0,1} được áp dụng trong các nghiên c ứu v ề máy tính, d ụng c ụ điện t ử quang h ọc và ba phép toán ph ần bù, t ổng boole và tích boole ở trên. 6.1.1. Biến Boole và hàm Boole n Định ngh ĩa: Cho B={0,1}. Khi đó B ={(x 1,x 2,x 3, x n) | x i ∈B} là t ập t ất cả các b ộ n giá tr ị 0 và 1. Bi ến x được g ọi là m ột bi ến Boole n ếu nó nh ận ch ỉ nh ận các giá tr ị t ừ B. M ột hàm t ừ B n tới B được g ọi là hàm Boole b ậc n Ví d ụ: Hàm F(x,y)= x + ¬ y t ừ t ập các c ặp có th ứ t ự là hàm Boole b ậc 2 với F(1,1)=1; F(1,0)=1; F(0,1)=0; F(0,0)=1; 6.1.2. Các h ằng đẳ ng th ức c ủa đạ i s ố Boole Trong quá trình thi ết k ế m ạch m ột trong nh ững vi ệc c ần làm là đơ n gi ản hóa các m ạch đó hay t ạm g ọi đó là t ối ưu hóa các m ạch, th ường được d ựa trên một s ố h ằng đẳ ng th ức Boole còn được g ọi là các lu ật. 1. Lu ật giao hoán a) a.b = b .a b) a+b = b+a 2. Lu ật kết h ợp a) (a .b) .c = a .(b .c) b) (a+b)+c = a+(b+c) 3. Lu ật phân ph ối a) a.(b+c) = (a .b)+(a .c) b) a+(b .c) = (a+b) .(a+c) 4. Lu ật đồ ng nh ất a) a.1 = a b) a+0 = a 5. Lu ật tr ội a+1=1 a.0=0 6. Lu ật t ồn t ại ph ần t ử bù: 138
4. Đi s Boole Nguy n Th Vinh-ĐHKH a) a.¬a = 0 (tính ch ất 0) b) a+¬a =1.(tính ch ất đơn v ị) 7. Lu ật lu ỹ đẳ ng a) a.a = a, b) a+a = a. 8. Lu ật De Morgan a) ¬(a .b) = ¬a + ¬b b) ¬(a+b) = ¬a .¬b 9. Lu ật bù kép ¬¬(a) = a. 10. Lu ật hút a) a.(a+b) = a b) a+(a .b) = a. Vi ệc ch ứng minh các lu ật trên có dựa vào vi ệc l ập b ảng chân tr ị ch ẳng hạn ch ứng minh lu ật hút d ựa vào b ảng sau Giá tr ị a b a + b a. (a+b) 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 Nhìn vào c ột 1 và c ột 4 ta th ấy các giá tr ị hoàn toàn phù h ợp v ới nhau do v ậy a. (a+b) = a; t ươ ng t ự v ới ý b Ngoài ra ta có th ể ch ứng minh b ằng cách dùng các h ằng đẳ ng th ức c ủa đại s ố Boole. a(a+b)= (a+0)(a+b) theo lu ật đồ ng nh ất = a +0. b theo lu ật phân ph ối = a+ b.0 theo lu ật giao hoán = a + 0 theo lu ật tr ội 139
5. Đi s Boole Nguy n Th Vinh-ĐHKH = a theo lu ật đồ ng nh ất 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. 6.1.3 Bi ểu di ễn các hàm boolean 6.1.3.1. Khai tri ển t ổng các tích Tìm các bi ểu th ức Boole bi ểu di ễn các hàm có các giá tr ị t ươ ng ứng trong b ảng sau Giá tr ị x y z F(x,y,z) G(x,y,z) 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 Với hàm F(x,y,z) ta th ấy ch ỉ nh ận giá tr ị 1 khi x=z=1 và y=0 còn l ại có giá tr ị 0 trong m ọi tr ường h ợp còn l ại. Ta l ại th ấy y=0 thì ¬y=1. V ậy ta có th ể lập bi ểu th ức b ằng cách l ấy tích c ủa x,¬y,z có f(x,y,z)= x.¬y.z 140
6. Đi s Boole Nguy n Th Vinh-ĐHKH Với hàm G(x,y,z) nh ận giá tr ị 1 khi x=z=0 và y=1 ho ặc x=y=1 và z=0. Tươ ng t ự nh ư ở trên tích x.y.¬z=1 ho ặc tích ¬x.y.¬z=1 sau đó xét t ổng c ủa chúng. V ậy hàm G(x,y,z) s ẽ là t ổng c ủa 2 tích này G(x,y,z)=x.y.¬z + ¬x.y.¬z Nh ư v ậy vi ệc tìm m ột bi ểu th ức boole bi ểu di ễn m ột hàm Boole có giá tr ị đã cho ta d ựa trên các giá tr ị 1 t ừ đó s ẽ d ẫn t ới tích c ủa các bi ến ho ặc các ph ần bù c ủa nó. 6.1.3.2. Định ngh ĩa: Một bi ến boole ho ặc ph ần bù c ủa nó được g ọi là một tục bi ến. Tích c ủa n tục bi ến đó được g ọi là m ột ti ểu h ạng . Ví d ụ: Tìm ti ểu h ạng có giá tr ị là 1 nếu x 1=x 3=1 và x2=0 Ti ểu h ạng x 1. ¬x2. x 3 có các t ập giá tr ị đáp ứng được yêu c ầu Bằng cách l ấy t ổng Boole c ủa các ti ểu h ạng phân bi ệt ta l ập được bi ểu th ức Boole v ới t ập giá tr ị đã được xác đị nh. K ết qu ả c ủa t ổng b ằng 1 khi và ch ỉ khi t ồn t ại ít nh ất 1 ti ểu h ạng nh ận giá tr ị là 1, k ết qu ả c ủa t ổng b ằng 0 khi mọi ti ểu h ạng đề u b ằng 0. T ổng các ti ểu h ạng để bi ểu di ễn hàm được g ọi là tri ển khai t ổng các tích c ủa hàm Boole. Ví d ụ: Tìm tri ển khai t ổng các tích c ủa hàm sau: F(x,y,z)= ¬x.(y+z) Ta có th ể tri ển khai t ổng này d ựa vào hai ph ươ ng pháp c ơ b ản sau Ph ươ ng pháp 1: Lập b ảng chân tr ị Giá tr ị x y z ¬x y+z ¬x.(y+z) 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 Dựa vào b ảng ta có F(x,y,z) = ¬x.¬y.z +¬x.¬z.y+ ¬x.z.y 141
7. Đi s Boole Nguy n Th Vinh-ĐHKH Ph ươ ng pháp 2: Sử d ụng các lu ật = ¬x.(y+z) = ¬x.y + ¬x.z theo lu ật phân ph ối = ¬x.1.y + ¬x.1.z theo lu ật đồ ng nh ất = ¬x.(z+¬z).y + ¬x.(y+¬y).z theo lu ật phần t ử bù =¬x.z.y + ¬x.¬z.y + ¬x.y.z + ¬x.¬y.z theo lu ật phân ph ối = ¬ x.z.y + ¬x.¬z.y + ¬x.¬y.z theo lu ật l ũy đẳ ng 6.2. M ẠCH LÔGIC. 6.2.1. Cổng lôgic: x1 x2 M x n-1 F(x 1, x 2, , x n) 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 x 1, x 2, , x n (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 x 1, x 2, , x n. 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. F(x )= 0 khi x = ,1 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. 142
8. Đi s Boole Nguy n Th Vinh-ĐHKH 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. 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 F(x,y )= x+y x F=x+y+z+t x y z y t Ch ẳng h ạn, hai xâu bit 101001101 và 111010100 qua c ổng OR cho 111011101. 6.2.2. M ạch lôgic 6.2.2.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 ỳ. Ví d ụ: Xây d ựng m ột m ạch lôgic th ực hi ện hàm Boole cho b ởi b ảng sau. 143
9. Đi s Boole Nguy n Th Vinh-ĐHKH 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 zy . 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 zy Bi ểu th ức c ủa F(x, y, z) có th ể rút g ọn: xyz + xy z + x zy = xy (z + z) + x zy = xy + x zy . Hình d ưới đây cho ta m ạch lôgic th ực hi ện hàm xy + x zy . 144
10. Đi s Boole Nguy n Th Vinh-ĐHKH x • y • F = xy + x zy 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 1 khi x = 0 hay y = .0 hi ện 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. 145
11. Đi s Boole Nguy n Th Vinh-ĐHKH 0 khi x = 1 hay y = ,1 Xét hàm Vebb F(x, y) = x ↓ y =  Mạch lôgic th ực 1 khi x = y = .0 hi ện hàm ↓ gọi là c ổng NOR, được v ẽ nh ư hình d ưới đây. x x ↓ y O y 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: 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 6.2.2.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, F 2, , F k là các hàm Boole c ủa các đầu vào x 1, x 2, , x n. x1 F1(x1, x 2, , x n) x2 M F2(x 1, x 2, , x n) xn-1 M F (x , x , , x ) x k 1 2 n n 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 146
12. Đi s Boole Nguy n Th Vinh-ĐHKH 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 a2a1 và b2b1 , a2 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 a2 + b2 + c1, t ức là ph ải c ộng ba s ố 1-bit. 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 = xyz + x zy + xy z + xyz . 147
13. Đi s Boole Nguy n Th Vinh-ĐHKH Công th ức c ủa c có th ể rút g ọn: c = z( yx + 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 Tr ở l ại phép c ộng hai s ố 2-bit a2a1 và b2b1 . T ổng a2a1 +b2b1 là m ột s ố 3-bit c2s2s1 , trong đó s1 là bit t ổng c ủa a1+b 1: s1 = a1 ⊕ b1, s2 là bit t ổng c ủa a2+b2+c1, v ới c1 là bit nh ớ c ủa a1+b 1: s2 = a2 ⊕ b2 ⊕ c1 và c2 là bit nh ớ c ủa a2+b2+c1. 148
14. Đi s Boole Nguy n Th Vinh-ĐHKH 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 a2 b1 a1 AD AD AD DA c3 c2 c1 c4 s4 s3 s2 s1 6.3. 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 149
15. Đi s Boole Nguy n Th Vinh-ĐHKH 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 zy . 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 zy = (y + y)xz =1xz = xz . 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). 6.3.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 Boole hai bi ến này g ồm b ốn ô vuông, trong đó hình vuông bi ểu di ễn h ội s ơ c ấp có m ặt trong khai tri ển được ghi s ố 1. y y x xy x y x yx x y Các hình ô đượ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. 150
16. Đi s Boole Nguy n Th Vinh-ĐHKH Ví d ụ: Tìm các b ản đồ Karnaugh cho các bi ểu th ức: a) xy + yx b) x y + yx c) x y + yx + xy 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 1 1 1 x 1 x 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 + yx , 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 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 các cách để lập b ản đồ Karnaugh ba bi ến được cho trong bảng sau: yz zy zy zy xyz x xy z x zy x zy xyz zyx x zy x zy x Để 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). Ví d ụ: 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: 151
17. Đi s Boole Nguy n Th Vinh-ĐHKH a) xy z + x zy + xyz + x zy , b) x zy + x zy + xyz + x zy + x zy , c) xyz + xy z + x zy + x zy + xyz + x zy + x zy . Bản đồ Karnaugh cho nh ững khai tri ển t ổng các tích này được cho trong hình sau: yz zy zy zy yz zy zy zy x 1 1 x 1 1 x 1 1 x 1 1 1 yz zy zy zy 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) zx + zy + xyz , b) y + zx , 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 zy zy zy wx wxyz wxy z wx zy wx zy wx wxyz w zyx wx zy wx zy wxyz w zyx wx zy wx zy wx wxyz wxy z wx zy wx zy wx 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 152
18. Đi s Boole Nguy n Th Vinh-ĐHKH 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 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. 6.3.2. Ph ươ ng pháp Quine-McCluskey 6.3.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. 6.3.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 T G ⊂ 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 F , , F là các nguyên nhân c ủa F thì T ⊂ T , 1 ≤ i ≤ k . Khi đó 1 k Fi F k k T = T ⊂ T . Do đó F là m ột nguyên nhân c ủa F. k U Fi F ∑ i ∑ 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 UTG . G∈S G∈S 153
19. Đi s Boole Nguy n Th Vinh-ĐHKH 6.3.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 UTG TF . G∈S G∈S Gi ả s ử d ạng t ổng chu ẩn t ắc hoàn toàn c ủa F là F = ∑G' nên G'∈S' = 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à UTG' UTG hay TF UTG . G'∈S' G∈S G∈S = Vì v ậy TF UTG G∈S hay F = ∑G . G∈S 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 6.3.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à x1x3x4 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 ở 154
20. Đi s Boole Nguy n Th Vinh-ĐHKH 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 + Ax = 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. Ví d ụ 9: Tìm d ạng t ổng chu ẩn t ắc thu g ọn c ủa các hàm Boole: F1 = wx zy + wx zy + wxyz + wx zy + wxyz + wxyz + wxyz , F2 = w zyx + wxyz + wxyz + wx zy + wx zy + wxy z + wxyz . 0 0 0 1 * 0 − 0 1 * 0 − − 1 0 0 1 0 * 0 0 1 − 1 1 − − 0 0 − 1 * − 0 − 1 − 0 1 1 0 1 0 1 * 0 0 1 1 * 0 0 1 1 * − 0 0 1 * − − 1 1 1 1 0 0 * 1 1 0 − * 1 0 0 1 * − 0 1 1 * 1 0 1 1 * 1 1 − 0 * 1 0 1 1 * 1 0 − 1 * 1 1 0 1 * 1 − 1 1 0 1 1 1 * 0 1 − 1 * 1 1 1 0 * 1 1 − 1 * 1 1 1 1 * 0 − 1 1 * 1 1 1 1 * 1 1 1 − * 1 − 1 1 * − 1 1 1 * 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 + zx + yz F2 = w yx + xyz + wyz + wx . 155
21. Đi s Boole Nguy n Th Vinh-ĐHKH 6.32.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. 156
22. Đi s Boole Nguy n Th Vinh-ĐHKH 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. Ví 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 Ví d ụ 9. wx zy wx zy wxyz wx zy wxyz wxyz wxyz wz + + + xz + + + + yz + + + + 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 + zx + yz w zyx wxyz wxyz wx zy wx zy wxy z wxyz wx + + + + w yx + + xyz + + 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 yx + xyz , F2 = wx + w yx + wyz . 157
23. Đi s Boole Nguy n Th Vinh-ĐHKH BÀI T ẬP CH ƯƠ NG VI Bài t ập tính toán 6.1.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. 6.1.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). 6.1.3. Ch ứng minh r ằng: a) (a+b) .(a+b¬) = a; b) (a .b)+(a¬.c) = (a+c) .(a¬+b). 6.1.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. 6.1.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.1.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. 6.1.7. Hãy dùng các c ổng NAND để d ựng m ạch c ộng bán ph ần. 6.1.8. Hãy dùng các c ổng NOR để d ựng m ạch c ộng bán ph ần. 158
24. Đi s Boole Nguy n Th Vinh-ĐHKH 6.1.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 = xyz + x zy . b) F = xyz + xy z + xyz + zyx . c) F = xy z + x zy + x zy + xyz + x zy . d) F = xyz + x zy + x zy + xyz + zyx + x zy . 6.1.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 zy + wx zy + w zyx + wx zy . b) F = wxy z + wx zy + wxyz + wx zy + w zyx + wx zy . c) F = wxyz + wxy z + wx zy + wx zy + wx zy + wx zy + w zyx + wx zy . d) F = wxyz + wxy z + wx zy + wxyz + w zyx + wxyz + wxyz + w zyx + wx zy . Bài tâp trên máy tính 6.2.1. Xác định đầ u ra c ủa hàm s ố F(x,y) b ất kì khi đi qua các c ổng AND; OR; NOR. 6.2.2. Cho giá tr ị c ủa hàm Boole n bi ến, v ới n là s ố nguyên d ươ ng. Tìm tri ển khai t ổng các tích c ủa hàm này 6.2.3. Cho b ảng giá tr ị c ủa m ột hàm Boole. Hãy bi ểu di ễn hàm này b ằng cách ch ỉ dùng các phép toán + và – 6.2.4. Đư a ra d ạng t ổng c ủa chu ẩn t ắc thu g ọn c ủa hàm Boole 6.2.5 . Lập b ản đồ Karnaugh n bi ến (<3n<10). Vi ết ti ểu lu ận 6.3.1. Mô t ả m ột s ố máy tính ở giai đoạn đầ u được ch ế t ạo để gi ải m ột bài toán v ề logic, ch ẳng h ạn nh ư máy ch ứng minh Stanhope, máy logic c ủa Jevon và máy Marquand 6.3.2. Hãy nêu cách dùng các c ổng logic để d ựng các b ộ nhân 6.3.3. Tìm hi ểu c ấu trúc v ật lí c ủa các c ổng NAND và NOR có được dùng để xây d ựng các m ạch không. 6.3.4 . Thi ết k ế m ạch đèn được điều khi ển b ởi hai công t ắc. 6.3.5. Tìm hi ểu v ề thi ết k ế các m ạch điện t ử 159
25. Đi s Boole Nguy n Th Vinh-ĐHKH TÀI LI ỆU THAM KH ẢO [1] Kenneth H.Rosen - Toán h ọc r ời r ạc ứng d ụng trong tin h ọc, NXB Giáo d ục, 2007. [2] Robert Sedgewick , C ẩm nang thu ật toán, NXB Khoa h ọc và K ĩ thu ật, 2004 [3] Đỗ Đứ c Giáo , Toán r ời r ạc, NXB Đạ i h ọc Qu ốc Gia Hà N ội, 2000. [4] Đặng Huy Ru ận, Lý thuy ết đồ th ị và ứng d ụng, NXB Khoa h ọc và K ĩ thu ật, 2000. [5] Nguy ễn Đứ c Ngh ĩa-Nguy ễn Tô Thành , Toán r ời r ạc, NXB Giáo dục, 1999. 160