Lập trình hướng đối tượng - Chương 5: Đại số Boole

Chương 5: Đại số BooleLà phép toán đại số liên quan đến hệ thống số nhị phânDo nhà toán học người Anh đưa ra năm 1815-1864 nhằm Đơn giản hóa việc trình bàyThao tác với logic mệnh đề1938 Claude đề xuất sử dụng đại số Boole trong thiết kế mạchCung cấp cách tiếp cận tiết kiệm và đơn giảnĐược sử dụng rộng rãi trong thiết kế mạch điện tử trong máy tínhĐại số boole là gì?Các phép toán trong đại số Boole thực hiện trên các biến có 2 giá trị 0 và 1, gồmCộng logic: ‘+’ hay ORNhân logic: ‘ . ‘ hay ANDPhép bù: ‘-’ hay NOTKhái niệm cơ bản về Đại số BooleKhái niệm cơ bản về Đại số BooleBảng chân trị:ABA AND BA OR BNOT A00001010111001011110Độ ưu tiên của các toán tửToán tử có độ ưu tiên cao nhất được định trị đầu tiên.Biểu thức được tính từ trái sang phảiĐộ ưu tiênToán tử1( ) Biểu thức trong ngoặc2_ (NOT)3. (AND)4+ (OR)Độ ưu tiên của các toán tửCác tiên đề của đại số BooleTiên đề 1:A = 0 khi và chỉ khi A không bằng 1A = 1 khi và chỉ khi A không bằng 0Tiên đề 2: Phần tử đồng nhấtX + 0 = XX . 1 = XTiên đề 3: Tính giao hoánX + Y = Y + XX . Y = Y . X Các tiên đề của đại số BooleTiên đề 4: Tính kết hợpx + (y + z) = (x + y) + zx . (y . z) = (x . y) . zTiên đề 5: Tính phân phốix . (y +z) = x . y + x . zx + y . z = (x + y) . (x + z)Tiên đề 6: Tính bù  Nguyên lý đối ngẫuCó sự đối ngẫu giữa toán tử AND, OR và bit 0, 1Các định lý của đại số BooleĐịnh lí 1 (Luật lũy đẳng)X + X = XX . X = XĐịnh lí 2 (Luật nuốt)X + 1 = 1X . 0 = 0Định lí 3 (Luật hấp thu)X + X . Y = XX .(X + Y) = XCác định lý của đại số BooleĐịnh lí 4 (Luật bù kép) Định lí 5  Định lí 6(De Morgan)   Hàm BooleMột hàm Boole là một biểu thức được thực hiện với:Các biến nhị phânCác toán tử AND, OR, NOTCác dấu ngoặc và đấu =Giá trị của hàm Boole có thể là 0 hoặc 1Một hàm Boole có thể được biểu diễn dạng:Một biểu thức đại số Một bảng chân trịHàm BooleHàm Boole biểu diễn dưới dạng biểu thức đại số:Với: X, Y và Z được gọi là các biến của hàm. HoặcHàm BooleHàm Boole biểu diễn dưới dạng bảng chân trịSố hàng của bảng là 2n, n là số các biến nhị phân được sử dụng trong hàm. XYZW00000011010001101001101111011111Sự dư thừaKhái niệm:Literal: là các biến trong hàm BooleTerm của n biến là sự kết hợp của các biến mà mỗi biến chỉ xuất hiện một lần duy nhất. Ví dụ: term của 3 biến A, B, C là A.B.CMột biểu thức là dư thừa nếu nó có chứaLiteral lặp: XX hay X+XBiến và bù của biến: XX’ hay X+X’Hằng: 0 hay 1Tối thiểu hóa hàm BooleTối thiểu hàm Boolean:Giảm số phần tử (Term)Giảm số biến (Literal)Phương pháp: Sử dụng phương pháp đại sốÁp dụng các định lý, tiên đề, các luật nhiều lần để tối thiểu hàm Boolean tới mức thấp nhất. Tối thiểu hóa hàm Boole Phần bù của hàm Boole Phần bù của hàm BooleVí dụ: tính phần bù của hàm sau:Bước 1: Chuyển toán tử AND thành OR và ngược lại.Bước 2: tính phần bù của các biếnDạng chính tắc của hàm BooleMột hàm n biến luôn được biểu diễn dưới 2 dạng:Dạng tổng các tích (sum-of-product SOP): biểu thức được biểu diễn dưới dạng tổng (sum) các toán hạng (term), mỗi toán hạng là tích (product) của các literalDạng tích các tổng (product-of-sum POS): biểu thức được biểu diễn dưới dạng tích các toán hạng, mỗi toán hạng là tổng của các literal Dạng chính tắc: biểu thức n biến dạng SOP hay POS ở dạng chính tắc nếu mỗi toán hạng của nó có đủ n literal và không chứa các literal thừa.Một biểu thức SOP hoặc POS không chính tắc luôn được chuyển thành dạng chính tắcVd: E = xy’ + x’y + xz + yz = xy’(z + z’) + x’y(z + z’) + xz(y + y’) + yz(x + x’) = xy’z + xy’z’ + x’yz + x’yz’ + xyz + xy’z + xyz + x’yz = xy’z + xy’z’ + x’yz + x’yz’ + xyzDạng chính tắc của hàm BooleDạng chính tắc của hàm BooleMinterm: Thực hiện phép toán AND giữa các literal tạo thành một TermMaxterm: Thực hiện phép toán OR giữa các literal tạo thành một TermDạng chính tắc của hàm BooleBiểu diễn hàm Boole dưới dạng SOPCác bước để biểu diễn hàm Boole dưới dạng SOPBước 1: Xây dựng bảng chân trị của hàm BooleBước 2: Xây dựng một minterm cho mỗi sự kết hợp của các biến mà làm cho hàm có giá trị là 1Bước 3: Biểu thức kết quả là tổng (OR) các minterm thu được ở bước 2Ví dụ: bảng chân trị của hàm F1Có 3 kết hợp của các biến cho giá trị của hàm là 1001, 100, 111Biểu diễn hàm Boole dưới dạng SOPBiểu diễn hàm Boole dưới dạng SOP Biểu diễn hàm Boole dưới dạng POSCác bước để biểu diễn hàm Boole dưới dạng tích của các tổng (POS):1. Xây dựng bảng chân trị của hàm Boole.2. Xây dựng một maxterm cho mỗi sự kết hợp của các biến mà làm cho hàm có giá trị là 03. Biểu thức kết quả là AND tất cả các maxterm thu được từ bước 2Biểu diễn hàm Boole dưới dạng POSVí dụ: bảng chân trị của hàm F1:Có 5 sự kết hợp làm cho giá trị của hàm là 0:000, 010, 011, 101, 110Biểu diễn hàm Boole dưới dạng POSCác maxterm tương ứng làThực hiện phép AND tất cả các maxterm ta được biểu thức POS củs hàm F1.Chuyển đổi giữa các dạng chính tắcĐể chuyển đổi từ một dạng chính tắc này sang một dạng chính tắc khác:Đổi các kí hiệu Liệt kê danh sách các tham số không có mặt từ hàm ban đầu.Chuyển đổi giữa các dạng chính tắcVí dụ: F (A, B, C) = ∑(1, 4, 5, 6, 7) = m1 + m4 + m5 + m6 + m7Phần bù đó có thể được biểu diễn như sau: F (A, B, C) = п(0, 2, 3) = m0 + m2 + m3Áp dụng định lý De Morgan’s chúng ta thu được F dưới một dạng khác : F = M0 . M2 . M3 = π (0, 2, 3) Bài tập