Bài giảng Toán rời rạc - Chương 2: Đại số Boole - Nguyễn Lê Minh

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à
• 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
0 1 1 0 
Đạ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
3
(1.0) (0 1) 
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
3
x y f(x,y)
0 0 0
0 1 0
1 0 1
1 1 0
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
3
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒇(𝒙𝟏, 𝒙𝟐, 𝒙𝟑)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Các hằng đằng thức đại số Boole
1
0
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
1
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
Cổng OR
Cổng OR thực hiện hàm tuyển, đầu ra F(x,y) là
tổng (tuyển) các đầu vào
2
1
Mạch Logic
Thiết kế mạch tổ hợp có đầu ra là biểu thức 𝑥𝑦
+ 𝑥𝑦
2
2
Mạch Logic
Thiết kế mạch tổ hợp có đầu ra là biểu thức
𝑓 𝑥, 𝑦, 𝑧 = 𝑥𝑦𝑧 + 𝑥𝑦 𝑧 + 𝑥 𝑦𝑧
2
3
Tối thiểu hóa hàm Boole
Tối thiểu hóa hàm Boole là tìm dạng biểu thức
Boole đơn giản nhất của hàm Boole đó
• Phương pháp biển đổi đại số
• Phương pháp bảng Karnaugh
2
4
Phương pháp biến đổi đại số
Phương pháp này dựa các luật, hay các hằng
đẳng thức của đại số Boole để tối thiểu hóa các
biến và các phép toán trên biểu thức Boole
Ví dụ: Tối thiểu hóa hàm Boole
𝑓 𝑥, 𝑦, 𝑧 = 𝑥𝑦𝑧 + 𝑥 𝑦𝑧
Thiết kế mạch tổ hợp của f(x,y,z) và mạch tổ
hợp tối thiểu của nó.
2
5
Phương pháp biến đổi đại số
𝑓 𝑥, 𝑦, 𝑧 = 𝑥𝑦𝑧 + 𝑥 𝑦𝑧
= 𝑦 + 𝑦 𝑥𝑧
= 1. 𝑥𝑧
= 𝑥𝑧
2
6
Phương pháp biến đổi đại số
Ví dụ: Tối thiểu hóa hàm Boole
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 𝑦 + 𝑥𝑦 + 𝑥𝑦
Thiết kế mạch tổ hợp của f(x,y,z) và mạch tổ
hợp tối thiểu của nó.
2
7
Phương pháp biến đổi đại số
Ví dụ: Tối thiểu hóa hàm Boole
𝑓 𝑥, 𝑦, 𝑧 = 𝑥 𝑦 + 𝑥𝑦 + 𝑥𝑦
Thiết kế mạch tổ hợp của f(x,y,z) và mạch tổ
hợp tối thiểu của nó.
2
8
Phương pháp bảng Karnaugh
• Do Karnaugh đề xuất năm 1953, được dùng để tìm
các số hạng có thể tổ hợp được của hàm Boole.
• Có bốn hội sơ cấp khác nhau trong khai triển tổng
các tích của một hàm Boole có hai biến x và y. Một
bản đồ Karnaugh đối với một hàm Boole hai biến này
gồm bốn ô vuông, trong đó hình vuông biểu diễn hội
sơ cấp có mặt trong khai triển được ghi số 1. Các
hình ô được gọi là kề nhau nếu các hội sơ cấp mà
chúng biểu diễn chỉ khác nhau một biến
2
9
Phương pháp bảng Karnaugh
3
0
Phương pháp bảng Karnaugh
• Ví dụ: 𝑥𝑦 + 𝑥𝑦
• Dạng tối thiểu hóa
𝑓 x, y = y
3
1
Phương pháp bảng Karnaugh
• Ví dụ: 𝑥 𝑦 + 𝑥𝑦 + 𝑥𝑦
3
2
Phương pháp bảng Karnaugh
Bảng Karnaugh ba biến là một hình chữ nhật được chia
thành 8 ô
3
3
Phương pháp bảng Karnaugh
• Các khối 2 ô kề nhau có thể được tổ hợp lại thành
tích của 2 biến
• Các khối 4 ô kề nhau có thể tổ hợp lại thành một biến
duy nhất
• Khối các 8 ô biểu diễn một tích không có biến nào
3
4
Phương pháp bảng Karnaugh
• Ví dụ: 𝑥𝑦 𝑧 + 𝑥𝑦𝑧 + 𝑥𝑦𝑧 + 𝑥𝑦𝑧
• 𝑥 𝑧 + 𝑦𝑧 + 𝑥𝑦𝑧
3
5
Bài tập
Bài 1: Tìm đối ngẫu các biểu thức sau
• 𝑥. 𝑦. 𝑧 + 𝑥. 𝑦. 𝑧
• 𝑥. 𝑧 + 𝑥. 0 + 𝑥. 1
Bài 2: Khai triển tổng các tích (tìm dạng chuẩn tắc đầy
đủ) các hàm Boole sau
• 𝑓 𝑥, 𝑦, 𝑧 = 𝑥𝑦 𝑧 + 𝑦𝑧
• 𝑓 𝑥, 𝑦, 𝑧 = 𝑥𝑦 + 𝑥𝑧 + 𝑦𝑧
• 𝑓 𝑥, 𝑦, 𝑧, 𝑡 = 𝑥𝑦𝑡 + 𝑥𝑧 + 𝑦𝑧𝑡
3
6
Bài tập
Bài 3: Dùng phương pháp Karnaugh, tối thiểu hóa các
hàm Boole sau, vẽ mạch Logic trước và sau khi tối thiểu
3
7
Bài tập
Bài 4: Tìm đầu ra các mạch tổ hợp sau
3
8