Bài giảng Chương II: Đại số boole

Chương II. ĐẠI SỐ BOOLE2.1 Các phần tử logic cơ bảnCác phần tử logic được chế tạo ở dạng vi mạch .Có hai loại logic : * Logic dương : mức điện thế cao tương ứng logic 1, mức điện thế thấp tương ứng logic 0. * Logic âm : mức điện thế cao tương ứng logic 0, mức điện thế thấp tương ứng logic 1.Nếu đổi cách sử dụng từ logic dương sang âm hay ngược lại thì hàm chức năng của mạch logic có thể thay đổi .Cổng NOT x y 0 1 x t 1 0 y t y = x x y Cổng AND x1 t x1 x2 y 0 0 0 x2 t 0 1 0 1 0 0 y t 1 1 1 x1 y = x1x2 x2 Cổng OR x1 x2 y x1 t 0 0 0 0 1 1 x2 t 1 0 1 1 1 1 y t x1 y = x1 + x2 x2Cổng NAND x1 x2 y x1 t 0 0 1 0 1 1 x2 t 1 0 1 1 1 0 y t x1 y = x1. x2 x2Cổng NOR x1 x2 y 0 0 1 x1 t 0 1 0 1 0 0 x2 t 1 1 0 y t x1 y = x1 + x2 x2Cổng EX.ORx1 x2 y 0 0 0 0 1 1 1 0 1 1 1 0 x1 y = x1  x2 x2Cổng EX.NORx1 x2 y 0 0 1 0 1 0 1 0 0 1 1 1 x1 y = x1  x2 x22.2 Các tiên đềCho tập hợp B = {x,y,z,} . Trang bị cho B hai phép toán logic “+” và “.” .Với mọi phần tử thuộc B thỏa mãn các tiên đề :Tiên đề 1: Tính giao hoán Tiên đề 2 : Tính phân bố x + y = y + x x(y + z) = xy + xz xy = yx x + yz = (x + y)(x + z)Tiên đề 3 : Tồn tại các hằng Tiên đề 4 : Tồn tại phần tử số 0 và 1 sao cho : bù sao cho : x + 0 = x x + x = 1 x.1 = x x.x = 0Tiên đề 5 : Kết quả các phép toán giữa hai phần tử bất kỳ là duy nhất .Định nghĩa :đối ngẫu của một biểu thức là biểu thức nhận được bằng cách đổi 0  1 , 1 0 , . + và + . F x x 0 1 . +  F’ x x 1 0 + .Định lý : một định lý hoặc tiên đề đúng với biểu thức chính thì cũng đúng với biểu thức đối ngẫu của nó hoặc ngược lại .2.3 Các định lýĐịnh lý 1: Luật phủ định Định lý 2 : Luật đồng nhất của hai lần phép cộng và nhân logic x = x x + x = x x.x = xĐịnh lý 3 : Quy tắc tính Định lý 4 : Quy tắc tính đối với giữa biến và hằng hằng x + 1 = 1 0 = 1 x.0 = 0 1 = 0 Định lý 5 : Luật nuốt Định lý 6 : Luật dán x(x + y) = x x( x + y) = xy x + xy = x x + xy = x + yĐịnh lý 7 : Quy tắc Định lý 8 : Luật kết hợp De Morgan x + (y + z) = (x + y) + z x + y = xy x(yz) = (xy)z xy = x + y2.3 Các phương pháp biểu diễn hàmBảng giá trị (hay bảng chân lý) liệt kê tất cả các giá trị của các tổ hợp biến và giá trị tương ứng của hàm. Hàm n biến có 2n tổ hợp biến khác nhau.Bìa Karnaugh là ô vuông hay chữ nhật chia thành 2n ô nhỏ.Dọc theo hai cạnh ghi các tổ hợp trị của các biến và phân bố sao cho hai tổ hợp liên tiếp nhau chỉ khác trị của một biến.Trong mỗi ô nhỏ ghi trị tương ứng của hàm.Hàm đa số x1x2x3 f10 0 0 0 0 Hàm có trị bằng 1 nếu số lượng 1 0 0 1 0 biến bằng 1 nhiều hơn số lượng2 0 1 0 0 biến bằng 0.3 0 1 1 14 1 0 0 0 f1 x1x25 1 0 1 1 x3 00 01 11 106 1 1 0 1 0 17 1 1 1 1 1 1 1 1 f2 x1x2 x3x4 00 01 11 10 x1x2x3x4 f2 x1x2x3x4 f2 00 1 1 0 0 0 0 0 1 8 1 0 0 0 0 01 1 1 1 0 0 0 1 0 9 1 0 0 1 1 11 1 1 2 0 0 1 0 0 10 1 0 1 0 1 10 1 1 3 0 0 1 1 1 11 1 0 1 1 0 4 0 1 0 0 0 12 1 1 0 0 1 5 0 1 0 1 1 13 1 1 0 1 0 6 0 1 1 0 1 14 1 1 1 0 0 7 0 1 1 1 0 15 1 1 1 1 1 x1x2x3 f30 0 0 0 0 Hàm f3 chọn các số lớn hơn 2 với1 0 0 1 0 điều kiện x1x2x3 = 0, nếu không2 0 1 0 0 thỏa điều kiện thì hàm có trị X .3 0 1 1 14 1 0 0 1 f3 x1x25 1 0 1 1 x3 00 01 11 106 1 1 0 1 0 1 17 1 1 1 X 1 1 X 1Biểu thức đại sốDạng chính tắc thứ nhất (tuyển chuẩn toàn phần)là dạng tổng các tích cơ bản :Dạng chính tắc thứ nhất liệt kê các tổ hợp biến hàm có trị bằng 1,trong đó biến bằng 1 viết dạng thực và biến bằng 0 viết dạng bù .Mỗi số hạng được gọi là một mintec Dạng chính tắc thứ hai (hội chuẩn toàn phần) là dạng tích của các tổng cơ bản :Dạng chính tắc thứ hai liệt kê các tổ hợp biến hàm có trị bằng 0,trong đó biến bằng 0 viết dạng thực và biến bằng 1 viết dạng bù .Mỗi thừa số được gọi là một maxtec x1x2x3 f40 0 0 0 1 1 0 0 1 0 f4 = x1x2x3 + x1x2x3 + x1x2x3 +2 0 1 0 1 (0) (2) (3)3 0 1 1 1 + x1x2x3 + x1x2x34 1 0 0 0 (5) (7)5 1 0 1 1 f4 = (x1 + x2 + x3) (x1 + x2 + x3)x6 1 1 0 0 (1) (4)7 1 1 1 1 x (x1 + x2 + x3) (6) Các mintec và maxtec của hàm ba biến N x1x2x3 mintec maxtec 0 000 m0 = x1x2x3 M0 = x1 + x2 + x3 1 001 m1 = x1x2x3 M1 = x1 + x2 + x3 2 010 m2 = x1x2x3 M2 = x1 + x2 + x3 3 011 m3 = x1x2x3 M3 = x1 + x2 + x3 4 100 m4 = x1x2x3 M4 = x1 + x2 + x3 5 101 m5 = x1x2x3 M5 = x1 + x2 + x3 6 110 m6 = x1x2x3 M6 = x1 + x2 + x3 7 111 m7 = x1x2x3 M7 = x1 + x2 + x3Phương pháp hình học Bieåu dieãn hình hoïc f4(x1,x2,x3) = (0,2,3,5,7) x3 011 X11 101 1X1 01X 111 000 x2 0X0 010 x1 2.5 Các phương pháp rút gọn hàmCác chỉ tiêu rút gọn : - Biểu thức cuối cùng chứa tối thiểu số biến. - Biểu thức cuối cùng chứa tối thiểu số số hạng hay thừa số. - Biểu thức cuối cùng đòi hỏi số vi mạch ít nhất để thực hiện .Phương pháp đại sốf1 = AB + ABC + ABC + AC = AB(1 + C) + AC(1 + B) = AB.1 + AC.1 = AB + AC = A(B + C) A B f1 Cf2 = ABC + ABC + ABC + AC = AC(B + B) + A(C + BC) = AC + AC + AB = C(A + A) + AB = C + AB A B f2 C 1 2 4 3 5 1 2 5 3 4f = ABC + ABC + ABC + ABC + ABC 1. ABC + ABC = AC(B + B) = AC2. ABC + ABC = BC3. ABC + ABC = BC4. ABC + ABC = AB 5. ABC + ABC = AB A f 1’.BC + BC = B2’.AB + AB = B Cf = AC + B + Bf = AC + B BPhương pháp bìa Karnaugh ABCD ABCD AB CD 00 01 11 10 00 ABCD 01 ABCD 11 ABCD 10 ABCDHai ô bất kỳ kế cận nhau chỉ khác nhau một biến .Các ô thuộc hai cạnh rìa song song cũng thỏa mãn tính kế cận theo từng cặp . Quy tắc chung : kết hợp 2n ô kế cận thì loại được n biến, trong đó biến có trị thay đổi bị loại .Nếu kết hợp các ô hàm bằng 1 thì biểu thức có dạng tổng các tích, trong đó biến bằng 1 viết dạng thực và bằng 0 viết dạng bù .Nếu kết hợp các ô hàm bằng 0 thì biểu thức có dạng tích các tổng, trong đó biến bằng 0 viết dạng thực và bằng 1 viết dạng bù.Đối với các hàm xác định bộ phận, tại các ô hàm bằng X có thể gán trị cụ thể, sao hàm được rút gọn tối ưu nhất . y1 AB C 00 01 11 10 0 1 1 1 y1 = B + AC 1 1 1 A y1 C B y1 = B + AC = B + AC = B AC = B AC NOT A B y1 C y2 AB CD 00 01 11 10 y2 = CD + BD 00 01 1 1 11 1 1 1 1 10 B y2 D C y2 = CD + BD = CD + BD = CD BD NOT B D y2 Cy1 AB C 00 01 11 10 y1 = (A + B) (C + B) 0 0 1 0 0 A B y1 C y1 = (A + B) (C + B) = (A + B) (C + B) y1 = A + B + C + B A B y1 C NOT y3 AB CD 00 01 11 10 00 0 01 0 0 0 11 0 0 0 0 10 0 0 0 y3 = (A + B)(B + C)(A + D) y4 AB CD 00 01 11 10 00 1 1 01 X X X X y4 = B + AC 11 1 1 1 10 1 1 1 B y4 A C y4 = B + AC = B + AC = B AC A B y4 C y5 AB CD 00 01 11 10 00 0 0 y5 = (A + B)(B + D) 01 X X X X 11 0 10 0 X A y5 B D y5 = (A + B)(B + D) = (A + B)(B + D) y5 = (A + B) +(B + D) A y5 B DBÀI TẬPBài 1 Hãy chứng minh các đẳng thức sau bằng phương pháp đại số :a) xyz + xyz = xy + yz + xzb) xy ( x  y  z ) = xyzc) AB + BC + AC = AB + BC + ACBài 2 Hãy vẽ dạng tín hiệu f ABCfABCtttBài 3 Hãy vẽ dạng tín hiệu fACBfCBAtttBài 4 Dùng bìa Karnaugh rút gọn các hàm sau :F1(A,B,C,D) = (0,4,5,7,8,12,14,15)F2(A,B,C,D) = (15,14,10,9,6,4,2)F3(A,B,C,D) = (2,5,6,9,13,14)+d(0,7,8,10,15)F4(A,B,C,D) = (1,4,6,8,11,12)+d(2,5,13,15)Bài 5Viết biểu thức chính tắc 1 & 2 của các hàm sau :yxxzf1(x,y,z)f2(x,y,z)yxf3(x,y,z)xyzf4 (x,y,z)yxf3(x,y,z)xyzf4 (x,y,z)