YOMEDIA
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
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ế.
AMBIENT/
Chủ đề:
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
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.98:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.98:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
