mẹo hay

3 bài toán tối tiểu hóa đa thức bool năm 2024

1. 4: ĐẠI SỐ BOOLE TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
2. số logic B Đại số Boole Hàm Boole Công thức đa thức tối thiểu Biểu đồ Karnaugh của hàm Boole Phương pháp Quine – McCluskey Các cổng logic 12/31/2015 Đại Số Boole Trang 2
3. B Trên tập logic B =0, 1 xét các phép toán logic  [tích Boole] x  y  [tổng Boole] x  y  [phép bù] x trong đó x, y B gọi là các biến logic hoặc biến Boole. 12/31/2015 Đại Số Boole Trang 3
4. Boole Trang 4
5. thức logic 1] Giao hoán 6] Luỹ đẳng 2] Kết hợp 7] Phần tử trung hoà 3] Phân phối 8] Phần tử bù 4] Luật bù kép 9] Luật thống trị 5] De Morgan 10] Luật hấp thu 12/31/2015 Đại Số Boole Trang 5
6. toán 2 – ngôi khác trên đại số logic B 1] Tổng modulo 2, x + y 2] Kéo theo x  y 3] Tương đương x  y 4] Vebb [NOR] x  y 5] Sheffer [NAND] x  y 12/31/2015 Đại Số Boole Trang 6
7. Boole Trang 7
8. nghĩa: Cho tập A có ít nhất 2 phần tử, trong đó có 2 phần tử đặc biệt được ký hiệu là 0 và 1. Trên A xét các phép toán 2 – ngôi  và , và phép toán 1 – ngôi / Ký hiệu là [A, , , /, 0, 1] 12/31/2015 Đại Số Boole Trang 8
9. phối Phần tử trung hoà Phần tử bù Tập A cùng với các phép toán này được gọi là một đại số Boole nếu các phép toán này có tính chất: ∀ 𝑎, 𝑏 ∈ 𝐴: 𝑎 ∨ 𝑏 = 𝑏 ∨ 𝑎. 𝑎 ∧ 𝑏 = 𝑏 ∧ 𝑎. ∀ 𝑎, 𝑏, 𝑐 ∈ 𝐴: 𝑎 ∨ 𝑏 ∨ 𝑐 = 𝑎 ∨ [𝑏 ∨ 𝑐]. [𝑎 ∧ 𝑏] ∧ 𝑐 = 𝑎 ∧ [𝑏 ∧ 𝑐]. 1 ∀ 𝑎, 𝑏, 𝑐 ∈ 𝐴: 𝑎 ∨ [𝑏 ∧ 𝑐] = [𝑎 ∨ 𝑏] ∧ [𝑎 ∨ 𝑐]. 𝑎 ∧ [𝑏 ∨ 𝑐] = [𝑎 ∧ 𝑏] ∨ [𝑎 ∧ 𝑐].Trong A tồn tại phần tử 0 và 1: ∀ 𝑎 ∈ 𝐴 𝑎 ∧ 1 = 1 ∧ 𝑎 = 𝑎. 𝑎 ∨ 0 = 0 ∨ 𝑎 = 𝑎. ∀ 𝑎 ∈ 𝐴 , tồn tại duy nhất phần tử bù 𝑎 sao cho: 𝑎 ∧ 𝑎 = 0. 𝑎 ∨ 𝑎 = 1. 2 3 4 5 12/31/2015 Đại Số Boole Trang 9
10. là tập bất kỳ, trên A = P[U] [tập các tập con của U] xét phép  là phép , phép  là phép , phép / là phép lấy phần bù, phần tử 0 là tập rỗng  còn phần tử 1 là tập U. Khi đó P[U] là một đại số Boole. 12/31/2015 Đại Số Boole Trang 10
11. AB của các đại số Boole A, B là một đại số Boole, trong đó: [a1,b1]  [a2,b2] = [a1  b1, a2  b2], [a1,b1]  [a2,b2] = [a1  b1, a2  b2], [a, b]/ = [a/, b/], [0,0] là phần tử 0 trong AB, [1,1] là phần tử 1 trong AB. Đặc biệt, Bn là một đại số Boole. 12/31/2015 Đại Số Boole Trang 11
12. gì thêm, tất cả các tập được nói đến trong chương này đều là tập hữu hạn. Nhắc lại: Một tập hữu hạn sắp thứ tự luôn luôn có phần tử tối tiểu/tối đại. Trên một đại số Boole tổng quát chúng ta cũng có các hằng đẳng thức giống như các hằng đẳng thức đã xét trên đại số logic B. 12/31/2015 Đại Số Boole Trang 12
13. Boole Trang 13
14. xạ f: BnB gọi là một hàm Boole n biến. Hàm đồng nhất bằng 1 ký hiệu là 1, hàm đồng nhất bằng 0 ký hiệu là 0. Tập tất cả các hàm Boole n – biến ký hiệu là Fn. 12/31/2015 Đại Số Boole Trang 14
15. g là hai hàm Boole n biến. Chúng ta có các định nghĩa như sau: 1] [f  g][x1, …, xn] = f[x1, …, xn]  g[x1, …, xn] 2] [f  g][x1, …, xn] = f[x1, …, xn]  g[x1, …, xn] 3] f/ [x1, …, xn] = [f[x1, …, xn]]/ với mọi x1, …, xn. 12/31/2015 Đại Số Boole Trang 15
16. cùng các phép toán này lập thành một đại số Boole. Ngoài ra còn có: f  g  f  g = g  f  g = f trong đó f  g nếu f[x1, …, xn]  g[x1, …, xn]. 12/31/2015 Đại Số Boole Trang 16
17. nhất để xác định một hàm Boole là dùng bảng giá trị. Hàm Boole 2 biến 12/31/2015 Đại Số Boole Trang 17
18. phiếu chỉ lấy một trong hai giá trị: 1 [tán thành] hoặc 0 [bác bỏ]. 2. Kết quả f là 1 [thông qua quyết định] nếu được đa số phiếu tán thành. là 0 [không thông qua quyết định] nếu đa số phiếu bác bỏ. Xét kết quả f trong việc thông qua một quyết định dựa vào 3 phiếu bầu x, y, z 12/31/2015 Đại Số Boole Trang 18
19. là hàm Bool theo 3 biến x,y,x có bảng chân trị như sau: x y z f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 12/31/2015 Đại Số Boole Trang 19
20. có thể xác định hàm Boole bằng một biểu thức Boole. Đó là một biểu thức gồm các biến Boole và các phép toán  [hội],  [tuyển], / [phép lấy bù]. Mỗi biểu thức Boole cũng được xem như một hàm Boole. 12/31/2015 Đại Số Boole Trang 20
21. x gọi là biến Boole nếu x chỉ nhận một trong hai giá trị 0/1. Giả sử x là một biến Boole. Khi đó ký hiệu x1 = x, x0 = x. 12/31/2015 Đại Số Boole Trang 21
22. trên hàm Boole: • Phép cộng Boole ∨: Với f, g ∈Fn, ta định nghĩa tổng Boole của f và g: 𝒇 ∨ 𝒈 = 𝒇 + 𝒈 − 𝒇𝒈 ∀ 𝑥 = 𝑥1, 𝑥2, … 𝑥 𝑛 ∈ 𝐵 𝑛,  [f ∨ g][x] = f[x] + g[x] – f[x]g[x] 12/31/2015 Đại Số Boole Trang 22
23. Boole ∧: Với f,g ∈Fn, ta định nghĩa tích Boole của f và g: 𝒇 ∧ 𝒈 = 𝒇𝒈 ∀ 𝑥 = 𝑥1, 𝑥2, … 𝑥 𝑛 ∈ 𝐵 𝑛,  [f ∧ g][x] = f[x]g[x] • Phép lấy phần bù: 𝒇 = 𝟏 − 𝒇 12/31/2015 Đại Số Boole Trang 23
24. một biểu thức được tạo bởi các biến và các phép toán Boole. VD: E= [x ∧ y ∧ z] ∨ [z ∧ 𝑦] Để dễ đọc hơn, người ta có thể viết: E = xyz + z 𝑦 12/31/2015 Đại Số Boole Trang 24
25. chính tắc của hàm Boole: Xét tập hợp các hàm Boole n biến Fn theo n biến x1, x2, …,xn. • Mỗi hàm Boole xi hay 𝑥i được gọi là một từ đơn. • Đơn thức là tích khác không của một số hữu hạn từ đơn. • Từ tối tiểu [đơn thức tối tiểu] là tích khác không của đúng n từ đơn. • Công thức đa thức là công thức biểu diễn hàm Boole thành tổng của các đơn thức. • Dạng nối rời chính tắc là công thức biểu diễn hàm Boole thành tổng của các từ tối tiểu. 12/31/2015 Đại Số Boole Trang 25
26. boole, với 3 biến: x, y, z x, y, z, 𝑥, 𝑦, 𝑧 là các từ đơn. xy, yz là đơn thức xy 𝑧 là từ tối tiểu E= xy + yz là một công thức đa thức Và F=xyz + 𝑥 𝑦 𝑧 là một dạng nối rời chính tắc 12/31/2015 Đại Số Boole Trang 26
27. F 𝑛, 𝑓 có thể viết dưới dạng sau: [*] Với 𝒖𝒊 là các đơn thức tối tiểu bậc 𝑛 [𝑖 = 1, … , 𝑛]. [*] được gọi là dạng nối rời chính tắc của 𝑓. Ví dụ: Trong F4 có dạng biểu diễn sau đây: 𝑓 𝑥, 𝑦, 𝑧, 𝑡 = 𝑥 𝑦 𝑧𝑡 ∨ 𝑥𝑦𝑧𝑡 ∨ 𝑥𝑦 𝑧 𝑡 ⇒ 𝑓 có dạng nối rời chính tắc của hàm Bool. 𝒇 = 𝒖 𝟏 ∨ 𝒖 𝟐 ∨ 𝒖 𝟑∨…∨ 𝒖𝒊 12/31/2015 Đại Số Boole Trang 27
28. để xác định dạng nối rời chính tắc một hàm Bool:  Cách 1: Bổ sung từ đơn còn thiếu vào các đơn thức. Bước 1: Khai triển hàm Bool thành tổng của các đơn thức. Bước 2: Với mỗi đơn thức thu được ở bước 1, ta nhân đơn thức đó với các tổng dạng với xi là những từ đơn bị thiếu trong đơn thức đó. Bước 3: Tiếp tục khai triển hàm thu được ở bước 2 và loại bỏ những đơn thức bị trùng. Công thức đa thức thu được chính là dạng nối rời chính tắc của hàm Bool ban đầu. Vídụ: Trong 𝐅𝟑 tìm dạng nối rời chính tắc 𝒇 𝒙, 𝒚, 𝒛 = 𝒙 ∨ 𝒚𝒛 ∨ 𝒙𝒚 𝒛 = 𝒙 𝒚 ∨ 𝒚 . 𝒛 ∨ 𝒛 ∨ 𝒙 ∨ 𝒙 𝒚𝒛 ∨ 𝒙𝒚 𝒛 = 𝒙𝒚𝒛 ∨ 𝒙𝒚 𝒛 ∨ 𝒙 𝒚𝒛 ∨ 𝒙 𝒚 𝒛 ∨ 𝒙 𝒚𝒛 ∨ 𝒙 𝒚𝒛 ∨ 𝒙𝒚 𝒛  𝒇 có dạng nối rời chính tắc của hàm Bool. 12/31/2015 Đại Số Boole Trang 28
29. chân trị. Để ý đến các vector boole trong bảng chân trị mà tại đó 𝑓 = 1 Tại đó Vector bool thứ 𝑛 là 𝑢1, 𝑢2,…,𝑢 𝑛và 𝑓[𝑢1, 𝑢2,…,𝑢 𝑛] = 1 Ví dụ: Cho 𝑓 𝑥, 𝑦 = 𝑥 ∨ 𝑦. Tìm biểu thức dạng nối rời chính tắc của 𝑓 Lập bảng chân trị của 𝑓 Các thể hiện làm cho 𝒇 = 𝟏 là 𝟎𝟎, 𝟏𝟎, 𝟏𝟏  lập được các từ tối tiểu tương ứng. Vậy dạng nối rời chính tắc của 𝑓 là 𝑓 𝑥, 𝑦 = 𝑥 𝑦 ∨ 𝑥 𝑦 ∨ 𝑥𝑦 x y 𝐱 ∨ 𝒚 0 0 1 0 1 0 1 0 1 1 1 1 12/31/2015 Đại Số Boole Trang 29
30. thức tối tiểu: 1. Đơn giản hơn: Cho hai công thức đa thức của một hàm Boole: F = m1∨ m2∨ m3 ∨ ........ mk G = M1∨ M2∨ M3 ∨ ........ Ml Ta nói rằng công thức F đơn giản hơn công thức G nếu tồn tại đơn ánh h: 1,2, … , 𝑘 → {1,2, … , 𝑙} sao cho với mọi 𝑖 ∈ {1,2, … , 𝑘} thì số từ đơn của 𝑚𝑖 không nhiều hơn số từ đơn của 𝑀ℎ[𝑖] 12/31/2015 Đại Số Boole Trang 30
31. như nhau Nếu F đơn giản hơn G và G đơn giản hơn F thì ta nói F và G đơn giản như nhau. Ví dụ: 12/31/2015 Đại Số Boole Trang 31
32. có 3 dạng đa thức f[x,y,z,t]: f1 = x 𝑦 𝑡 V 𝑥yz V x 𝑧 𝑡 V xyz [1] : f2 = x 𝑦 𝑡 V 𝑥yz V xy 𝑧 V yzt [2] : f3 = x 𝑦 𝑡 V 𝑥yzt V 𝑥yz 𝑡 V xy 𝑧 V yzt [3] [1] và [2] đơn giản như nhau Vì 𝑝 = 𝑞 = 4 deg 𝑢𝑗 = deg 𝑣𝑗 = 3 [2] đơn giản hơn [3] hay [3] phức tạp hơn [2] Vì 𝑝 = 4 < 𝑞 = 5 deg 𝑢𝑗 ≤ deg 𝑣𝑗 12/31/2015 Đại Số Boole Trang 32
33. Boole Trang 33
34. đa thức tối tiểu: Công thức F của hàm Boole f được gọi là Công thức đa thức tối tiểu nếu với bất kỳ công thức G của f mà đơn giản hơn F thì F và G đơn giản như nhau. 12/31/2015 Đại Số Boole Trang 34
35. Sử dụng bảng Karnaugh là phương pháp xác định công thức đa thức tối tiểu. • Quy tắc gom nhóm: - Gom các tiểu hạng mang biểu diễn là số 1. - Khi gom 2 𝑛 Ô kế cận sẽ loại được n biến. Những biến bị loại là những biến khi ta đi vòng qua các ô kế cận mà giá trị của chúng thay đổi. - Các vòng phải được gom sao cho số ô có thể vào trong vòng là lớn nhất và để đạt được điều đó, thường ta phải gom cả những ô đã gom vào trong các vòng khác. - Vòng gom phải là 1 hình chữ nhật. 12/31/2015 Đại Số Boole Trang 35
36. Đối với hàm Boole 2 biến x, y : • Bảng karnaugh 2 biến có 4 ô vuông, trong đó:  Ô được đánh số 1 để biểu diễn tiểu hạng có mặt trong hàm.  Các ô được cho là liền nhau nếu các tiểu hạng mà chúng biểu diễn chỉ khác nhau 1 biến. y x 12/31/2015 Đại Số Boole Trang 36
37. Tìm bảng Karnaugh cho F = 𝑥𝑦 + 𝑥 𝑦 F y 𝑦 x 1 1 𝑥 12/31/2015 Đại Số Boole Trang 37
38. Karnaugh cho: A = 𝑥𝑦 + 𝑥𝑦 + 𝑥 𝑦 A y 𝒚 x 1 𝒙 1 1 12/31/2015 Đại Số Boole Trang 38
39. F = 𝑥𝑦 + 𝑥 𝑦 F y 𝑦 x 1 1 𝑥 • Từ bảng Karnaugh  Tổ hợp các tiểu hạng mang biểu diễn là số 1. • Các tổ hợp được gom phải là khối khả dĩ lớn nhất và số ô là 2 𝑛 , với n = 1, 2. 12/31/2015 Đại Số Boole Trang 39
40. = 𝑥𝑦 + 𝑥𝑦 + 𝑥 𝑦 B y 𝑦 x 1 𝑥 1 1  B = 𝑦 + 𝑥 12/31/2015 Đại Số Boole Trang 40
41. Bảng karnaugh 3 biến là 1 hình chữ nhật chia thành 8 ô. • Sau khi có bảng Karnaugh, ta bắt đầu gom nhóm các tiểu hạng. • Quy tắc tương tự Bảng Karnaugh 2 biến. 12/31/2015 Đại Số Boole Trang 41
42. 𝑦 𝑧 𝑦𝑧 𝑥 1 1 𝑥 1 1 1  𝑧 + 𝑥𝑦 VD: Dùng bảng Karnaugh 3 biến để rút gọn tổng các tích sau 𝑥𝑦 𝑧 + 𝑥 𝑦 𝑧 + 𝑥𝑦𝑧 + 𝑥𝑦 𝑧 + 𝑥 𝑦 𝑧 12/31/2015 Đại Số Boole Trang 42
43. Bảng gồm 16 ô vuông như sau: 12/31/2015 Đại Số Boole Trang 43
44. Karnaugh 4 biến để rút gọn hàm sau: D = 𝝎𝒙𝒚𝒛 + 𝝎𝒙𝒚 𝒛 + 𝝎𝒙 𝒚𝒛 + 𝝎 𝒙𝒚 𝒛 + 𝝎 𝒙 𝒚𝒛 + 𝝎 𝒙𝒚𝒛 + 𝝎 𝒙 𝒚𝒛 + 𝝎𝒙 𝒚𝒛 D 𝑦𝑧 𝑦 𝑧 𝑦 𝑧 𝑦𝑧 𝜔𝑥 1 1 1 𝜔 𝑥 1 1 𝜔 𝑥 1 1 𝜔𝑥 1 D = 𝜔𝑥𝑦 + 𝜔𝑥𝑧 + 𝜔𝑦 𝑧 + 𝜔 𝑥𝑧 + 𝑦𝑧 12/31/2015 Đại Số Boole Trang 44
45. của một tập  Việc tìm tất cả các tổng chuẩn tắc không dư thừa của hàm Boole f, từ các tsc tối đại của f, là một vấn đề khá phức tạp.  Trước hết, chúng ta xét bài toán tìm phủ tối tiểu của một tập như sau. 12/31/2015 Đại Số Boole Trang 45
46. X Cho S = X1, …, Xn là họ các tập con của X. S gọi là phủ của X nếu X = Xi. Phủ tối tiểu của X Giả sử S là một phủ của X. S gọi là phủ tối tiểu của X nếu với mọi i, SXi không phủ X. 12/31/2015 Đại Số Boole Trang 46
47. a, b, c, d A = a,b B = c,d C = a,d D = b,c A, B, C, D phủ không tối tiểu. A, B, C, D là các phủ tối tiểu. A, C, D phủ không tối tiểu. B, D không phủ. 12/31/2015 Đại Số Boole Trang 47
48. 1: Vẽ biểu đồ karnaugh của f. Bước 2: Xác định tất cả các tế bào lớn của kar[f]. Bước 3: Xác định các tế bào lớn nhất thiết phải chọn. Ta nhất thiết phải chọn tế bào lớn T khi tồn tại một ô của kar[f] mà ô này chỉ nằm trong tế bào lớn T và không nằm trong bất kỳ tế bào lớn nào khác. Thuật toán tìm công thức đa thức tối tiểu 12/31/2015 Đại Số Boole Trang 48
49. định các phủ tối tiểu gồm các tế bào lớn: • Nếu các tế bào lớn chọn được ở bước 3 đã phủ được kar[f] thì ta có duy nhất một phủ tối tiểu gồm các tế bào lớn của kar[f]. • Nếu các tế bào lớn chọn được ở bước 3 chưa phủ được kar[f] thì: o Xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn chứa ô này, ta chọn một trong các tế bào lớn này. Cứ tiếp tục như thế ta sẽ tìm được tất cả các phủ gồm các tế bào lớn của kar[f]. o Loại bỏ các phủ không tối tiểu, ta tìm được tất cả các phủ tối tiểu gồm các tế bào lớn của kar[f]. 12/31/2015 Đại Số Boole Trang 49
50. định các công thức đa thức tối tiểu của f. • Từ các phủ tối tiểu gồm các tế bào lớn của kar[f] tìm được ở bước 4 ta xác định được các công thức đa thức tương ứng của f. • Loại bỏ các công thức đa thức mà có một công thức đa thức nào đó thực sự đơn giản hơn chúng. • Các công thức đa thức còn lại chính là các công thức đa thức tối tiểu của f. 12/31/2015 Đại Số Boole Trang 50
51. các công thức đa thức tối tiểu của hàm 𝑓: 𝑓 [x,y,z,t] = xyzt ∨ x 𝑦 ∨ x 𝑧 ∨ yz ∨ xy 𝑧 ∨ xy 𝑡 B1: Bảng Kar[𝑓] 𝑓 [x,y,z,t] = xyzt ∨ x 𝑦 ∨ x 𝑧 ∨ yz ∨ xy 𝑧 ∨ xy 𝑡 𝑥 𝑦 𝑥𝑦 𝑥𝑦 𝑥 𝑦 𝑧 𝑡 1 1 1 𝑧𝑡 1 1 1 𝑧𝑡 1 1 𝑧 𝑡 1 1 12/31/2015 Đại Số Boole Trang 51
52. 𝑥𝑦 𝑥 𝑦 𝑧 𝑡 1 1 1 𝑧𝑡 1 1 1 𝑧𝑡 1 1 𝑧 𝑡 1 1 B3: Chọn tế bào lớn nhất thiết phải chọn: [Vì chúng chứa các các ô không nằm trong tế bào nào khác – minh hoạ với ô vàng] + chọn tế bào lớn thứ 1: x + chọn tế bào lớn thứ 2: yz B2: Xác định tất cả các tế bào lớn của f. 12/31/2015 Đại Số Boole Trang 52
53. họ phủ của các tế bào lớn: Ta thấy các tế bào chọn ở bước 3 đã phủ hết bảng đây là họ phủ tối thiểu gồm các tế bào Kar[𝑓]: x ∨ yz B5: Ứng với họ phủ tối thiểu của tế bào lớn tìm được ta được duy nhất 1 công thức đa thức tối tiểu của f:  f = x ∨ yz 𝑥 𝑦 𝑥𝑦 𝑥𝑦 𝑥 𝑦 𝑧 𝑡 1 1 1 𝑧𝑡 1 1 1 𝑧𝑡 1 1 𝑧 𝑡 1 1 12/31/2015 Đại Số Boole Trang 53
54. các công thức đa thức tối thiểu của hàm 𝑓: 𝑓 𝑥, 𝑦, 𝑧, 𝑡 = 𝑦𝑧𝑡 ∨ 𝑦𝑧𝑡 ∨ 𝑦 𝑧 𝑡 ∨ 𝑥𝑦𝑧𝑡 ∨ 𝑥z 𝑡 B1: Bảng Kar[𝑓] 𝑓 𝑥, 𝑦, 𝑧, 𝑡 = 𝑦𝑧𝑡 ∨ 𝑦𝑧𝑡 ∨ 𝑦 𝑧 𝑡 ∨ 𝑥𝑦𝑧𝑡 ∨ 𝑥z 𝑡 x 𝑦 𝑥𝑦 𝑥y 𝑥 𝑦 z 𝑡 1 1 𝑧𝑡 1 1 1 𝑧t 𝑧 𝑡 1 1 1 1 12/31/2015 Đại Số Boole Trang 54
55. các tế bào lớn + Tế bào lớn thứ 1: 𝑥 𝑡 + Tbào lớn thứ 2: 𝑥 𝑦z + Tế bào lớn thứ 3: 𝑦zt + Tế bào lớn thú 4: xzt + Tế bào lớn thứ 5: 𝑧 𝑡 x 𝑦 𝑥𝑦 𝑥y 𝑥 𝑦 z 𝑡 1 1 𝑧𝑡 1 1 1 𝑧t 𝑧 𝑡 1 1 1 1 12/31/2015 Đại Số Boole Trang 55
56. 𝑥y 𝑥 𝑦 z 𝑡 1 1 𝑧𝑡 1 1 1 𝑧t 𝑧 𝑡 1 1 1 1 B3: Xác định các tế bào lớn nhất thiết phải chọn Có 3 ô chỉ nằm trong 1 tế bào lớn Các tế bào lớn nhất thiết phải chọn là 𝑥 𝑡 + xzt + 𝑧 𝑡 12/31/2015 Đại Số Boole Trang 56
57. họ phủ tối thiểu của các tế bào lớn: Ta có họ phủ : 𝑧𝑡 ∨ 𝑥 𝑡 ∨ xzt Ta thấy còn một ô chưa được phủ và ô đó nằm ở 1 trong 2 tế bào lớn. Ta có 2 cách chọn: • Cách chọn thứ 1: 𝑧𝑡 ∨ 𝑥 𝑡 ∨ xzt ∨ 𝑥 𝑦z • Cách chọn thứ 2: 𝑧𝑡 ∨ 𝑥 𝑡 ∨ xzt ∨ 𝑦zt x 𝑦 𝑥𝑦 𝑥y 𝑥 𝑦 z 𝑡 1 1 𝑧𝑡 1 1 1 𝑧t 𝑧 𝑡 1 1 1 1 12/31/2015 Đại Số Boole Trang 57
58. công thức đa thức cực tiểu: Ta thấy 2 công thức đơn giản như nhau cho nên công thức đa thức tối thiểu của hàm 𝑓 là: 𝑧𝑡 ∨ 𝑥 𝑡 ∨ xzt ∨ 𝑥𝑦z 𝑧𝑡 ∨ 𝑥 𝑡 ∨ xzt ∨ 𝑦zt 12/31/2015 Đại Số Boole Trang 58
59. 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 của hàm Boole như dưới dạng chuẩn tắc tuyển. 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. Phương pháp Quine-McCluskey 12/31/2015 Đại Số Boole Trang 59
60. tìm dạng tổng chuẩn tắc thu gọn: Bước 1: Viết vào cột thứ nhất các biểu diễn của các nguyên nhân hạng n củ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. 12/31/2015 Đại Số Boole Trang 60
61. 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ố của F. 12/31/2015 Đại Số Boole Trang 61
62. Boole Trang 62
63. tìm dạng tổng chuẩn tắc tối thiểu: 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. 12/31/2015 Đại Số Boole Trang 63
64. + + + + + + + + + 12/31/2015 Đại Số Boole Trang 64
65. Các phép toán ở đại số boole  Phép cộng thể hiện qua hàm OR  Phép nhân thể hiện qua hàm AND  Phép phủ định thể hiện qua hàm NOT Các phép tính trên khi áp dụng cho logic 0 và 1 12/31/2015 Đại Số Boole Trang 65
66. bản Cổng AND Cổng OR Cổng NOT Đầu ra = 1 khi có 1 ngõ vào =1 Đầu ra chỉ =1 khi tất cả ngõ vào =1 Bù của giá trị đầu vàoA 𝐴 12/31/2015 Đại Số Boole Trang 66
67. XOR Chỉ = 0 khi tất cả ngõ vào =1 Chỉ = 1 khi tất cả ngõ vào =0 2 ngõ khác nhau thì =1 Cổng X-NOR 2 ngõ giống nhau thì =1 12/31/2015 Đại Số Boole Trang 67
68. giữa các cổng cơ bản sang cổng NAND 12/31/2015 Đại Số Boole Trang 68
69. giữa các cổng cơ bản sang cổng NOR 12/31/2015 Đại Số Boole Trang 69
70. biểu thức logic sau từ mạch logic: Kết quả: Y = [ 𝐴 + 𝐵][𝐴 + 𝐵 + 𝐶] 𝐶 12/31/2015 Đại Số Boole Trang 70
71. kế logic tổng hợp:  Bước 1: Đặt các biến cho ngõ vào và các hàm của ngõ ra tương ứng.  Bước 2: Thiết lập bảng chân trị cho ngõ ra và ngõ vào  Bước 3: Viết biểu thức logic liên hệ giữa ngõ ra và các ngõ vào.  Bước 4: Tìm công thức đa thức tối tiểu của biểu thức logic vừa tìm được.  Bước 5: Từ biểu thức logic rút gọn chuyển sang mạch logic tương ứng 12/31/2015 Đại Số Boole Trang 71
72. nhà có 3 công tắc, người chủ nhà muốn bóng đèn sáng khi cả 3 công tắc đều hở, hoặc khi công tắc 1 và 2 đóng còn công tắc thứ 3 hở. Hãy thiết kế mạch logic thực hiện sao cho số cổng là ít nhất. Giải:  Bước 1: Gọi 3 công tắc lần lượt là A, B, C. Bóng đèn là Y. Trạng thái công tắc đóng là logic 1, hở là 0. Trạng thái đèn sáng là logic 1 và tắt là 0. 12/31/2015 Đại Số Boole Trang 72
73. yêu cầu bài toán ta có bảng chân trị: 12/31/2015 Đại Số Boole Trang 73
74. Bước 3: Từ bảng chân trị ta có biểu thức logic ngõ ra 𝑌 = 𝐴 𝐵 𝐶 + 𝐴𝐵 𝐶  Bước 4: Rút gọn biểu thức logic: 𝑌 = 𝐴 𝐵 𝐶 + 𝐴𝐵 𝐶  Bước 5: Mạch logic tương ứng của biểu thức 12/31/2015 Đại Số Boole Trang 74
75. ta cũng có thể sử dụng cổng XOR cho bài toán như sau: 12/31/2015 Đại Số Boole Trang 75
76. ƠN CÔ VÀ CÁC BẠN ĐÃ LẮNG NGHE VÀ THEO DÕI