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

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

288
lượt xem 42
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ế.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Chương 5 ĐẠI SỐ BOOLE ĐẠI SỐ BOOLE 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 )  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 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.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ể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 )  x y  x y g ( x, y, z )  xyz  x yz  x y z
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  x y  x y b. xyz  xyz  x yz