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

TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016
Chương 6
ĐẠI SỐ BOOLE
lvluyen@hcmus.edu.vn
∼luyen/trr
FB: fb.com/trr2015
Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 1/45
Mở đầu
Xét sơ đồ mạch điện như hình vẽ
Tùy theo cách trạng thái cầu dao A,B,C mà ta sẽ có dòng điện đi qua
MN hay không?
Như vậy ta sẽ có bảng giá trị sau
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 2/45
Bảng giá trị
Câu hỏi. Khi mạch điện gồm nhiều
cầu dao, làm sao ta có thể kiểm soát
được.
Giải pháp là đưa ra công thức, với mỗi
cầu dao ta xem như là một biến.
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 3/45
Nội dung
Chương 6. ĐẠI SỐ BOOLE
1. Đại số Boole
2. Mạng logic
3. Biểu đồ Karnaugh
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 4/45
6.1.1. Đại số Boole
Ví dụ. Xét tập hợp B = {0; 1}. Với mọi x, y ∈ B, ta định nghĩa:
x ∧ y = xy,
x ∨ y = x + y − xy,
x = 1− x.
Các phép toán vừa định nghĩa có bảng chân trị là:
x y x ∧ y x ∨ y x
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 0
Khi đó, tập hợp B với các phép toán trên là một đại số Boole ;
1 ∧ được gọi là tích Boole ;
2 ∨ là tổng Boole ;
3 x là phần bù của x.
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 5/45
Nhận xét. Do x ∧ y = xy nên ta dùng ký hiệu xy thay cho x ∧ y.
Nhận xét. Cho x và y là các phần tử thuộc B. Khi đó
1 xy = yx; x ∨ y = y ∨ x
2 xx = x; x ∨ x = x
3 xx = 0; x ∨ x = 1
4 x(y ∨ z) = xy ∨ xz;
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 6/45
6.1.2. Hàm Boole
Định nghĩa. Hàm Boole n biến là ánh xạ
f : Bn → B,
trong đó B = {0, 1}.
Như vậy hàm Boole n biến là một hàm số có dạng :
f = f(x1, x2, . . . , xn),
trong đó mỗi biến trong x1, x2, . . . , xn chỉ nhận hai giá trị 0, 1 và f
nhận giá trị trong B = {0, 1} và B = {(x1, x2, . . . , xn) |xi ∈ B}.
Ký hiệu Fn để chỉ tập các hàm Boole n biến.
Ví dụ.
f(x, y, z, t) = (x ∨ z)t ∨ (x y ∨ y t)z ∨ (y z ∨ x y z)t
là hàm Boole 4 biến.
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 7/45
Bảng chân trị
Định nghĩa. Xét hàm Boole n biến f(x1, x2, . . . , xn). Vì mỗi biến xi
chỉ nhận hai giá trị 0, 1 nên chỉ có 2n trường hợp của bộ biến
(x1, x2, . . . , xn).
Do đó, để mô tả f, ta có thể lập bảng gồm 2n hàng ghi tất cả các giá
trị của f tùy theo 2n trường hợp của biến. Ta gọi đây là bảng chân
trị của f.
Ví dụ. Xét kết qủa f trong việc thông qua một quyết định dựa vào 3
phiếu bầu x, y, z. Mỗi phiếu chỉ lấy một trong hai giá trị: 1 (tán thành)
hoặc 0 (bác bỏ).
Kết qủa f là 1 (thông qua quyết định) nếu được đa số phiếu tán thành,
là 0 (không thông qua quyết định) nếu đa số phiếu bác bỏ.
Hãy lập bảng chân trị của f.
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 8/45
Giải. Bảng chân trị của hàm Boole f là:
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 9/45
6.1.3. Dạng nối rời chính tắc
Từ đơn, từ tối tiểu
Định nghĩa. Xét tập hợp các hàm Boole của n biến Fn theo n biến
x1, x2, . . . , xn. Khi đó:
i) Mỗi hàm Boole xi hay xi được gọi là từ đơn.
ii) Từ tối tiểu là tích khác không của đúng n từ đơn.
Ví dụ. Xét tập hợp các hàm Boole theo 3 biến x, y, z. Ta có
Các từ đơn là x, y, z, x, y, z.
Các từ tối tiểu là x y z, x y z, x y z, x y z, x y z, x y z, x y z, x y z.
Nhận xét. Tập hợp các hàm Boole n biến chứa đúng 2n từ đơn và 2n
từ tối tiểu.
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 10/45
Định lý. Cho f là hàm Boole n biến x1, x2, . . . xn. Khi đó:
i) Nếu f là từ tối tiểu thì bảng chân trị của f có đúng một vị trí bằng
1.
ii) Ngược lại, nếu f chỉ nhận giá trị 1 tại vị trí u = (a1, a2, . . . , an)
thì f là từ tối tiểu có dạng f = b1 b2 . . . bn, trong đó
bi =
{
xi nếu ai = 1;
xi nếu ai = 0.
Ví dụ.
1 Nếu f(x, y, z) chỉ nhận giá trị 1 tại vị trí (1, 0, 1) thì f = x y z.
2 Nếu f(x, y, z, t) chỉ nhận giá trị 1 tại vị trí (0, 1, 1, 0) thì
f = x y z t.
3 Nếu f(x, y, z, t) = x y z t thì f chỉ nhận giá trị 1 tại vị trí (1, 1, 0, 0).
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 11/45
Định nghĩa. Xét tập hợp các hàm Boole của n biến Fn theo n biến
x1, x2, . . . , xn. Khi đó:
i) Đơn thức là tích khác không của một số hữu hạn từ đơn.
ii) Công thức đa thức là công thức biểu diễn hàm Boole thành
tổng của các đơn thức.
Ví dụ. Xét tập hợp các hàm Boole theo 3 biến x, y, z. Ta có
Các hàm Boole y, x z, y z, x y z, y z, z là các đơn thức.
Công thức f = x y ∨ y z ∨ x y z là một công thức đa thức.
Ví dụ. Xét hàm Boole f(x, y, z) = x (y ∨ z) ∨ x z (1). Ta có (1) không
là công thức đa thức của f. Tuy nhiên,
(1)⇔ f = x y ∨ x z ∨ x z, (2)
Khi đó (2) là công thức đa thức của f.
lvluyen@hcmus.edu.vn Chương 6. HÀM BOOLE 3/1/2016 12/45
Nhận xét. Mọi hàm Boole đều có thể biểu diễn dưới dạng đa thức.
Định nghĩa. Dạng nối rời chính tắc là công thức biểu diễn hàm
Boole thành tổng của các từ tối tiểu.
Ví dụ. Xét hàm Boole
f(x, y, z) = x(y ∨ z) ∨ xz. (1)
Ta có (1) không là công thức đa thức của f.
Ta có
(1)⇔ f = x y ∨ x z ∨ x z. (2)
Khi đó (2) là công thức đa thức của f nhưng không phải là