Bài giảng Toán rời rạc - Chương 2: Đại số boole
TOÁN RỜI RẠC
Chương 2: ĐẠI SỐ BOOLE
GV: NGUYỄN LÊ MINH
Bộ môn Công nghệ thông tin
Nội dung
Hàm Boole và biểu thức Boole
Khai triển hàm Boole
Mạch Logic
Tối thiểu hóa hàm Boole
2
Đại số Boole
Định nghĩa: Đại số Boole đưa ra các phép
toán và quy tắc làm việc với tập {0,1}. Trong
các mạch điện của máy tính, các dụng cụ
điện tử và quang học được nghiên cứu bằng
cách dùng tập này và các quy tắc của đại số
Boole.
3
Đại số Boole
Các phép toán thường dùng trong đại số
Boole
• Phần bù của một phần tử
và
0 1
1 0
• Phép lấy tổng Bool (Ký hiệu + hoặc OR)
1+1=1, 1+0=1, 0+1=1, 0+0=0
• Phép lấy tích Bool (Kí hiệu . hoặc AND)
1.1=1, 1.0=0, 0.1=0, 0.0=0
3
Đại số Boole
Thứ tự thực hiện các pháp toán Boole
• Lấy phần bù
• Phép lấy tích
• Phép lấy tổng
• Ví dụ: Tìm giá trị của phép tính sau
(1.0) (0 1)
3
Hàm Boole
Định nghĩa: Hàm Boole thường được biểu
diễn bằng cách dùng các biểu thức được tạo
bởi các biến và các phép toán Boole
Cho B = {0,1}. Một ánh xạ
f: 퐵푛 → 퐵
(푥1, 푥2, … , 푥푛) → 푓(푥1, 푥2, … , 푥푛)
Gọi là hàm Boole bậc n theo n biến 푥1,푥2, … , 푥푛
3
Hàm Boole
Ví dụ: Hàm Boole 2 biến f(x,y) với giá trị
bằng 1 khi x=1, y=0 và bằng 0 với mọi khả
năng còn lại của x và y có thể được cho
trong bảng sau
x
0
0
1
1
y
0
1
0
1
f(x,y)
0
0
1
0
3
Hàm Boole
Ví dụ: Cử tri 푨ퟏ, 푨ퟐ, 푨ퟑtham gia bỏ phiếu
trong cuộc bầu cử có ứng cử viên D. Các
biến Boole tương ứng là 풙ퟏ, 풙ퟐ, 풙ퟑ
ퟏ 풏ế풖 푨풋 풃ầ풖 풑풉풊ế풖 풄풉풐 푫
Với 풙풋 =
ퟎ 풏ế풖 푨풋 풌풉ô풏품 풃ầ풖 풑풉풊ế풖 풄풉풐 푫
(ퟏ ≤ 풋 ≤ ퟑ)
3
Hàm Boole
풙ퟏ
0
풙ퟐ
0
풙ퟑ
0
풇(풙ퟏ, 풙ퟐ, 풙ퟑ)
0
0
0
1
0
1
1
1
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
3
Các hằng đằng thức đại số Boole
Tính đối ngẫu đại số Boole
Định nghĩa: Đối ngẫu của một biểu thức Boole
là một biểu thức Boole nhận được bằng cách
các tổng và tích Boole đổi chỗ cho nhau, các số
0 và 1 đổi chỗ cho nhau.
Ví dụ:
• Đối ngẫu của 푥. 푦 + 푧 là 푥 + 푦 . 푧
• Đối ngẫu của 푥. 1+ 푦 + 푧 là (푥 + 0)(푦. 푧)
1
1
Nguyên lý đối ngẫu
Định nghĩa: Một hằng đẳng thức giữa các hàm
được biểu diễn bởi các biểu thức Boole vẫn còn
đúng nếu ta lấy đối ngẫu 2 vế của nó
Ví dụ: Lấy đối ngẫu 2 vế của hằng đẳng thức
x(x+y) = x
ta được x+ xy = x
1
2
Khai triển hàm Boole
2 vấn đề trong đại số Boole:
• Cho các giá trị của một hàm Boole n biến
푥1, 푥2, … , 푥푛. Làm thế nào để tìm được biểu
thức Boole biểu diễn hàm đó ?
• Có biểu thức nào đơn giản hơn để biểu diễn
cùng một hàm Boole hay không ?
1
3
Khai triển tổng các tích
Khái niệm:
• Đơn tử: Là một biến Boole hoặc phần bù của
nó
• Tiểu hạng: Là tích các đơn tử
• Tổng các tiểu hạng biểu diễn hàm Boole
được gọi là khai triển tổng các tích hay dạng
tuyển chuẩn tắc hàm Boole
1
4
Khai triển tổng các tích
1
5
Khai triển tổng các tích
1
6
Khai triển tổng các tích
Tìm dạng chuẩn tắc đầy đủ hàm Boole
푓 푥, 푦, 푧 = 푥. 푦. 푧 + 푦. 푧
= 푥. 푦. 푧 + 푦. 푧. 푥 + 푥
= 푥. 푦. 푧 + 푥. 푦. 푧 + 푥. 푦. 푧
Bài tập: 푓 푥, 푦, 푧 = 푥푦 + 푥푧 + 푦푧
1
7
Mạch Logic
Một máy tính cũng như một dụng cụ điện tử
được tạo bởi nhiều mạch, mỗi một mạch có thể
được thiết kế bằng cách dùng các phép toán
của đại số Boole. Các mạch logic được tạo
thành từ các mạch cơ sở, gọi là cổng logic.
1
8
Cổng NOT
Cổng NOT thực hiện hàm phủ định, chỉ có 1
đầu vào, đầu ra F(x) là phủ định của đầu vào x
9
Cổng AND
Cổng AND thực hiện hàm hội, đầu ra F(x,y) là
tích (hội) các đầu vào
2
0
Tải về để xem bản đầy đủ
38 trang
12/01/2024
20120
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Chương 2: Đại số boole", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_chuong_2_dai_so_boole.pdf
