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

Tham khảo "Bài giảng Toán rời rạc - Chương 5: Đại số Boole" để nghiên cứu và ứng dụng nguyên lý qui nạp toán học, công thức truy hồi để giải các bài toán kinh tế.

Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc - Chương 5: Đại số BooleChương 5 ĐẠI SỐ BOOLE ĐẠI SỐ BOOLE George Boole (1815 - 1864) ĐẠI SỐ BOOLEI Nguyên lý qui nạp toán họcII 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  0Thứ 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 BOOLEa. 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àmnhị 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  0Với f ( x , y)   0 Các trường hợp còn lại của x, yCó 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à 2b. 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 )  x yz  xy  y z Giá trị của f(1, 0, 1) là: 2. Cho hàm Boole f(x,y) có bảng giá trị như sau: Hỏi hàm Boole f(x,y) có biểu x y f(x,y) thức là: 0 0 0 A. xy B. xy 0 1 0 1 0 1 C. xy D. x y 1 1 05.3 DẠNG CHUẨN CỦA HÀM BOOLEMột biến Boole hoặc phủ định của nó gọi là mộttụ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 xi là một tiểu hạng.Một hàm Boole gọi là ở dạng chuẩn nếu biểuthứ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 )  x y  x y g ( x, y, z )  xyz  x yz  x y z 5.4 TỐI THIỂU HÓA HÀM BOOLEPhươ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  x y  x y b. xyz  xyz  x yz