Bài giảng Toán rời rạc - Chương 5: Đại số boole

ChươngChương 55 ĐĐẠẠII SSỐỐ BOOLEBOOLE George Boole (1815 - 1864) ĐẠI SỐ BOOLE I Nguyên lý qui nạp toán học II Công thức truy hồi 5.1 MỞ ĐẦU Đại số Boole được xây dựng trên tập hợp {0; 1} Các phép toán giữa các phần tử 0 và 1: + Phép phủ định: 0 1;1  0 + Phép cộng: ký hiệu là + hoặc OR 11  1; 1 0  0 1 1; 0  0  0 + Phép nhân: ký hiệu là . hoặc AND 1.1 1; 1.0  0.1  0; 0.00 Thứ tự thực hiện các phép toán trên đại số Boole: 1. Phép phủ định 2. Phép nhân 3. Phép cộng Ví dụ Tìm giá trị của các biểu thức sau: a. 1(1 1)  0(11) b. 1.0 11.0  0 5.1 HÀM BOOLE VÀ BIỂU THỨC BOOLE a. Hàm Boole Cho B = {0; 1} Một hàm Boole n biến số là một ánh xạ: f : Bn  B (x1; x 2 ;...; x n )  f(x1;x 2 ;...;x n ) Với xi (i = 1..n)  B Chú ý: + Các hàm Boole còn được gọi là hàm lôgic hay hàm nhị phân + Biến chỉ nhận các giá trị trong B còn được gọi là biến Boole + Một bảng liệt kê hết các giá trị của một hàm Boole được gọi là bảng giá trị của hàm Boole Ví dụ Xét hàm boole: f: B2  B 1 khi x 1, y  0 Với f (x, y)   0 Các trường hợp còn lại của x, y Có bảng giá trị: x y f(x,y) 0 0 0 0 1 0 1 0 1 Định lý: 1 1 0 2n Số hàm Boole bậc n là 2 b. Biểu thức Boole Một biểu thức Boole gồm các số 0, 1 và các biến Boole liên kết với nhau bằng các phép toán trong đại số Boole. Các hàm Boole có thể biểu diễn bởi các biểu thức Boole. Ví dụ 1. Cho biểu thức Boole: f (x, y, z)  xyz  xy  yz Giá trị của f(1, 0, 1) là: 2. Cho hàm Boole f(x,y) có bảng giá trị như sau: x y f(x,y) Hỏi hàm Boole f(x,y) có biểu thức là: 0 0 0 0 1 0 A. xy B. xy 1 0 1 C . xy D. xy 1 1 0 5.3 DẠNG CHUẨN CỦA HÀM BOOLE Một biến Boole hoặc phủ định của nó gọi là một tục biến. Cho n biến Boole x1, x2,, xn. Ta gọi tích: y1.y2yn với yi bằng xi hoặc bằng xi là một tiểu hạng. Một hàm Boole gọi là ở dạng chuẩn nếu biểu thức Boole biểu diễn nó là tổng các tiểu hạng. Ví dụ Các hàm Boole sau đây là có dạng chuẩn tắc f (x, y)  xy  x y g(x, y, z)  xyz  xyz  xyz 5.4 TỐI THIỂU HÓA HÀM BOOLE Phương pháp biến đổi đại số: Ví dụ Tối thiểu hóa các hàm Boole sau: a. xy  xy  xy  xy b. xyz xyz  xyz