Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 3: Đại số Bool - Võ Tấn Dũng

LOGO
Chương 3. Đại số Bool
TOÁN RỜI RẠC
1
GV: Võ Tấn Dũng
Trường Cao đẳng CNTT TPHCM
Nội dung
Đại Số Bool
Hàm Bool
Mạch logic
Bản đồ Karnaugh
2
Xét mạch điện như hình vẽ
Tùy theo các trạng thái cầu dao A, B, C mà ta sẽ có dòng 
điện đi qua MN. Như vậy ta sẽ có bảng giá trị sau
Mở đầu
3
Mở đầu
A B C MN
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
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 biến được xem như là một cầu 
dao
5Xét tập hợp B = {0, 1}.
I. Đại Số Bool
Khi đó, B trở 
thành một đại số 
Bool
6II. Hàm Bool
Hàm Bool n biến là ánh xạ 
f : Bn B , trong đó B = {0, 1}. 
Như vậy hàm Bool 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}.
Ký hiệu Fn để chỉ tập các hàm Bool n biến. 
7Xét hàm Bool 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ó 2
n 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 
Bảng chân trị
Ví dụ:
 Cho hàm bool bậc 3, f(x,y,z) = xy + xz. Ta có thể lập bảng giá 
trị của f như sau:
8
9Ví 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ỏ. 
10
Hàm Bool
Khi đó f là hàm Bool theo 3 biến x, y, z có bảng chân trị như 
sau:
x y z f
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
11
Dạng chính tắc tuyển (d.n.f) của Hàm Bool
Xét tập hợp các hàm Bool của n biến Fn theo n biến x1, 
x2,,xn
Mỗi hàm bool xi hay được gọi là từ đơn.
 Đơn thức là tích khác không của một số hữu hạn từ
đơn.
 Từ tối tiểu là tích khác không của đúng n từ đơn.
 Công thức đa thức là công thức biểu diễn hàm Bool
thành tổng của các đơn thức.
 Dạng chính tắc tuyển là công thức biểu diễn hàm Bool
thành tổng của các từ tối tiểu.
disjunctive normal form (d.n.f) = chính tắc tuyển
ix
là từ tối tiểu
12
Ví dụ:
Mệnh đề: Mọi hàm Bool f khác 0 đều có thể viết một cách duy 
nhất (không kể sai khác về thứ tự trước sau của các tích cơ bản) 
dưới dạng d.n.f.
13
III. Mạch các cổng
Ta nói mạch logic trên tổng hợp (hay còn gọi là biểu diễn) hàm Bool f
14
Cổng NOT
Kí hiệu cổng
( )F x x 
X not X
0 1
1 0
Input Output
Bảng chân trị
15
Cổng AND
a b a.b
0 0 0
0 1 0
1 0 0
1 1 1
Bảng chân trị
16
Cổng OR
a b a + b
0 0 0
0 1 1
1 0 1
1 1 1
Bảng chân trị:
17
Cổng NAND
18
Cổng NOR
19
Ví dụ f x z y z x t y t x y z    
20
Ví dụ
21
Viết biểu thức f  ( , , ) ( )f x y z x y z x y z
Cho sơ đồ
. Thiết kế một mạch điều khiển bởi 2 công tắc
Mỗi công tắc được xem như là biến x, y : 1 là bật 0 là tắt 
Cho F(x, y) =1 khi đèn sáng và 0 khi đèn tắt
Giả sử F(x, y) =1 khi cả hai công tắc đều cùng bật hoặc 
đều cùng tắt
x y F(x, y)
1 1 1
1 0 0
0 1 0
0 0 1
Tại bảng chân trị, chỉ quan tâm các dòng 
có F(x,y)=1.
- Khi x hay y bằng 1, ghi lại x, y
- Khi x hay y bằng không, ghi phủ định x hay phủ định y
Kết quả hàm số dạng dnf là:
23
x
x
x
y
y
x y
yxy
24
Giả sử F(x,y,z) =1 khi 1 hoặc 3 
cái đều bật
x y z F(x,y,z)
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 1
0 0 0 0
. Thiết kế một mạch điều khiển bởi 3 công tắc
Mỗi công tắc xem như là biến x, y,z : 1 là bật 0 là tắt 
Cho F(x, y) =1 khi đèn sáng và 0 khi đèn tắt
Chỉ quan tâm các dòng có F(x,y,z)=1. Tại 
các dòng đó, biến nào bằng 1 thì giữ 
nguyên, biến nào bằng 0 thì ghi phủ định.
Kết quả hàm số dạng dnf là:
25
xz
x
y
z
x y z
zyxy
z
y
x
y
zyxz
z
x
zyx
z
y
x
x
y
Mạch
26
CÁC BƯỚC THIẾT KỀ SƠ ĐỒ MẠCH
Bước 1: Từ yêu cầu thực tế, lập ra bảng 
giá trị cho hàm Bool.
Bước 2: Từ bảng giá trị, rút ra hàm Bool ở 
dạng chuẩn tắc tuyển.
Bước 3: Rút gọn hàm Bool (Tìm dạng công 
thức đa thức tối tiểu của hàm Bool).
Bước 4: Vẽ sơ đồ mạch ứng với công thức 
đa thức tối tiểu đã tìm được.
27
Bản đồ Karnaugh
(xem trong bản viết tay của thầy)
 https://sites.google.com/site/votandungsg/noi-dung-trr-ltdht
28