Chương 5 Đại số Boole

Chương 5 ĐẠI SỐ BOOLE George Boole (1815 - 1864) Nguyên lý qui nạp toán học Công thức truy hồi ĐẠI SỐ BOOLE I II 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: 01;10  + Phép cộng: ký hiệu là + hoặc OR 000;11001;111  + Phép nhân: ký hiệu là . hoặc AND 00.0;01.00.1;11.1  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: )11(0)11(1.a  00.110.1.b  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ạ: )x;...;x;f(x)x;...;x;(x BB:f n21n21 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 Với      0 0y,1xkhi1 )y,x(f Các trường hợp còn lại của x, y Có bảng giá trị: 0 0 1 0 0 1 0 1 0 0 1 1 f(x,y)yx Định lý: Số hàm Boole bậc n là n22 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ụ zyxyzyxzyxf ),,( 1. Cho biểu thức Boole: Giá trị của f(1, 0, 1) là: 2. Cho hàm Boole f(x,y) có bảng giá trị như sau: 0 0 1 0 0 1 0 1 0 0 1 1 f(x,y)yx Hỏi hàm Boole f(x,y) có biểu thức là: yx.A yx.B xy.C yx.D 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.y2…yn với yi bằng xi hoặc bằng ix 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. Các hàm Boole sau đây là có dạng chuẩn tắc yxyxyxf ),( zyxzyxxyzzyxg ),,( Ví dụ 5.4 TỐI THIỂU HÓA HÀM BOOLE Phương pháp biến đổi đại số: yxyxyxxy.a  Ví dụ Tối thiểu hóa các hàm Boole sau: zyxzxyxyz.b 