Bài giảng Toán rời rạc - Chương III: Ðại số Bool. Hàm Bool

, B trở thành một ñại số Bool
. 0 1
0 0 0
1 0 1
+ 0 1
0 0 0
1 0 1
06/05/2010 7
1. ðại Số Bool
Cho ñại số Bool (A,+,.). Khi ñó với mọi x,y∈A, ta có:
1. x.x = x; x+x = x.
2. x.0 = 0.x =0; x+1 =1+ x = 1.
3. Phần tử bù của x là duy nhất và = x;
4. Công thức De Morgan:
5. Tính hấp thụ:
x(x+y) = x; x+(xy) = x.
= +
+ =
xy x y;
x y xy.
x
= =1 0; 0 1.
06/05/2010 8
2. Hàm Bool
ðịnh nghĩa
Một hàm Bool n biến là một ánh xạ
f : Bn→ B , trong ñó B = {0, 1}. 
Một 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.
06/05/2010
3
06/05/2010 9
Bảng chân trị
Xé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ó 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.
2. Hàm Bool
06/05/2010 10
Xét kết quả f trong việc thông qua một Quyết ñịnh dựa
vào 3 phiếu bầu x, y, z.
1. Mỗi phiếu chỉ lấy một trong hai giá trị: 1 (tán thành)
hoặc 0 (bác bỏ).
2. Kết quả 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ỏ.
Khi ñó f là hàm Bool theo 3 biến x, y, z có bảng chân
trị như sau:
2. Hàm Bool
Ví dụ:
06/05/2010 11
2. Hàm Bool
x y z f
1 1 1 1
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 0
06/05/2010 12
Các phép toán trên hàm Bool
Các phép toán trên Fn ñược ñịnh nghĩa như sau:
1. Phép cộng Bool +:
Với f, g ∈ Fn ta ñịnh nghĩa tổng Bool của f và g:
2. Hàm Bool
∀x = (x1,x2,,xn)∈ Bn,
(f +g)(x) = f(x) + g(x) – f(x)g(x) 
f +g ∈ Fn và (f+g)(x) = max{f(x),g(x)}
Dễ thấy
06/05/2010
4
06/05/2010 13
2. Phép nhân Bool .:
Với f, g ∈Fn ta ñịnh nghĩa tích Bool của f và g 
2. Hàm Bool
Các phép toán trên hàm Bool
∀x=(x1,x2,,xn)∈Bn,
(f.g)(x) = f(x)g(x)
Dễ thấy: 
f.g ∈Fn và (f.g)(x) = min{f(x),g(x)}
06/05/2010 14
3. Phép lấy hàm bù:
Với f ∈ Fn ta ñịnh nghĩa hàm bù của f như sau:
1f f= −
2. Hàm Bool
Các phép toán trên hàm Bool
06/05/2010 15
Dạng nối rời chính tắc 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 nối rời chính tắc 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.
ix
2. Hàm Bool
06/05/2010 16
Công thức ña thức tối tiểu
• ðơn giản hơn
Cho hai công thức ña thức của một hàm Bool:
f = m1+ m2 +. +mk (F)
f =M1 + M2 + + Ml (G)
Ta nói rằngcông thức F ñơn giản hơn công thức
G nếu tốn tại ñơn ánh h: {1,2,..,k} → { 1,2,,
l} sao cho với mọi i∈ {1,2,..,k} thì số từ ñơn của
mi không nhiều hơn số từ ñơn của Mh(i)
2. Hàm Bool
06/05/2010
5
06/05/2010 17
• ðơn giản như nhau:
Nếu F ñơn giản hơn G và G ñơn giản hơn F thì
ta nói F và G ñơn giản như nhau.
Công thức ña thức tối tiểu:
Công thức F của hàm Bool f ñược gọi là tối tiểu
nếu với bất kỳ công thức G của f mà ñơn giản
hơn F thì F và G ñơn giản như nhau
2. Hàm Bool
Công thức ña thức tối tiểu
06/05/2010 18
2. Hàm Bool
Phương pháp biểu ñồ Karnaugh
Xét f là một hàm Bool theo n biến x1,x2,,xn với n = 3 hoặc 4.
Trường hợp n = 3: f là hàm Bool theo 3 biến x, y, z. Khi ñó
bảng chân trị của f gồm 8 hàng. Thay cho bảng chân trị của f
ta vẽ một bảng chữ nhật gồm 8 ô, tương ứng với 8 hàng của
bảng chân trị, ñược ñánh dấu như sau:
x x
z 101 111 011 001
100 110 010 000
y y
x x
z
y y
06/05/2010 19
2. Hàm Bool
Phương pháp biểu ñồ Karnaugh
Với qui ước: Khi một ô nằm trong dãy ñược ñánh dấu
bởi x thì tại ñó x =1, bởi thì tại ñó x =0, tương tự cho
y, z.
Các ô tại ñó f bằng 1 sẽ ñược ñánh dấu (tô ñậm hoặc
gạch chéo). Tập các ô ñược ñánh dấu ñược gọi là biểu
ñồ Karnaugh của f, ký hiệu là kar(f).
x
06/05/2010 20
2. Hàm Bool
Trường hợp n = 4: f là hàm Bool theo 4 biến x, y, z, t. Khi ñó
bảng chân trị của f gồm 16 hàng. Thay cho bảng chân trị của f ta
vẽ một bảng chữ nhật gồm 16 ô, tương ứng với 16 hàng của bảng
chân trị, ñược ñánh dấu như sau:
x x
z 1010 1110 0110 0010
z 1011 1111 0111 0011 t
1001 1101 0101 0001 t
1000 1100 0100 0000
y y
Phương pháp biểu ñồ Karnaugh
x x
z
y y
z
t
t
06/05/2010
6
06/05/2010 21
2. Hàm Bool
Trong cả hai trường hợp, hai ô ñược gọi là kề
nhau (theo nghĩa rộng), nếu chúng là hai ô liền
nhau hoặc chúng là ô ñầu, ô cuối của cùng một
hàng (cột) nào ñó. Nhận xét rằng, do cách ñánh
dấu như trên, hai ô kề nhau chỉ lệch nhau ở một
biến duy nhất.
Phương pháp biểu ñồ Karnaugh
06/05/2010 22
2. Hàm Bool
Tế bào
Xét các hàm Bool theo n biến x1,x2,,xn. Khi ñó, nếu f
là một ñơn thức có dạng tích của k từ ñơn phân biệt thì
kar(f) là một hình chữ nhật gồm 2n-k ô kề nhau. Những
hình chữ nhật gồm một lũy thừa của 2 những ô kề nhau
ñược gọi là các tế bào. Như vậy, biểu ñồ Karnaugh của
một ñơn thức là một tế bào. Ngược lại, nếu T là một tế
bào thì T là biểu ñồ Karnaugh của một ñơn thức duy
nhất m, cách xác ñịnh m như sau: lần lượt chiếu T lên
các cạnh, nếu toàn bộ hình chiếu nằm trọn trong một từ
ñơn nào thì từ ñơn ñó mới xuất hiện trong m.
06/05/2010 23
2. Hàm Bool
Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t.
Biểu ñồ Karnaugh của ñơn thức xyzt
x x
z
z t
t
y y
x x
z
y y
z
t
t
06/05/2010 24
2. Hàm Bool
Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t.
Biểu ñồ Karnaugh của ñơn thức 
x x
z
z t
t
y y
x x
z
y y
z
t
t
yzt
06/05/2010
7
06/05/2010 25
2. Hàm Bool
Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t.
Biểu ñồ Karnaugh của ñơn thức 
x x
z
z t
t
y y
x x
z
y y
z
t
t
yt
06/05/2010 26
2. Hàm Bool
Ví dụ: Xét các hàm Bool theo 4 biến x, y, z, t.
Biểu ñồ Karnaugh của ñơn thức 
x x
z
z t
t
y y
x x
z
y y
z
t
t
t
06/05/2010 27
2. Hàm Bool
Tế bào lớn
Cho hàm Bool f. Ta nói T là một tế bào lớn của
kar(f) nếu T thoả hai tính chất sau:
a. T là một tế bào và T ⊆ kar(f).
b. Không tồn tại tế bào T’ nào thỏa T’ ≠ T và T
⊆ T’⊆ kar(f).
06/05/2010 28
2. Hàm Bool
Ví dụ:
Xét hàm Bool f theo 4 biến x, y, z, t có biểu ñồ
Karnaugh như sau:
x x
z
z t
t
y y
x x
z
y y
z
t
t
06/05/2010
8
06/05/2010 29
2. Hàm Bool
Kar(f) có 6 tế bào lớn như sau:
x x
z
z t
t
y y
x x
z
y y
z
t
t
x x
z
z t
t
y y
x x
z
y y
z
t
t
xz yz
06/05/2010 30
2. Hàm Bool
x x
z
z t
t
y y
x x
z
y y
z
t
t
x x
z
z t
t
y y
x x
z
y y
z
t
t
xt xy
06/05/2010 31
2. Hàm Bool
x x
z
z t
t
y y
x x
z
y y
z
t
t
x x
z
z t
t
y y
x x
z
y y
z
t
t
yzt yt
06/05/2010 32
2. Hàm Bool
Thuật toán xác ñịnh tất cả các công thức ña thức
tối tiểu của hàm Bool f
Bước 1: Vẽ biểu ñồ Karnaugh của f.
Bước 2: Xác ñịnh tất cả các tế bào lớn của kar(f).
Bước 3: Xác ñịnh các tế bào lớn nhất thiết phải chọn.
Ta nhất thiết phải chọn tế bào lớn T khi tồn tại
một ô của kar(f) mà ô này chỉ nằm trong tế bào lớn T
và không nằm trong bất kỳ tế bào lớn nào khác.
06/05/2010
9
06/05/2010 33
2. Hàm Bool
Bước 4: Xác ñịnh các phủ tối tiểu gồm các tế bào lớn.
Nếu các tế bào lớn chọn ñược ở bước 3 ñã phủ ñược
kar(f) thì ta có duy nhất một phủ tối tiểu gồm các tế bào
lớn của kar(f).
Nếu các tế bào lớn chọn ñược ở bước 3 chưa phủ
ñược kar(f) thì xét một ô chưa bị phủ, sẽ có ít nhất hai
tế bào lớn chứa ô này, ta chọn một trong các tế bào lớn
này. Cứ tiếp tục như thế ta sẽ tìm ñược tất cả các phủ
gồm các tế bào lớn của kar(f). Loại bỏ các phủ không
tối tiểu, ta tìm ñược tất cả các phủ tối tiểu gồm các tế
bào lớn của kar(f).
06/05/2010 34
2. Hàm Bool
Bước 5: Xác ñịnh các công thức ña thức tối tiểu của f.
Từ các phủ tối tiểu gồm các tế bào lớn của kar(f) tìm
ñược ở bước 4 ta xác ñịnh ñược các công thức ña thức
tương ứng của f.
So sánh các công thức trên: Loại bỏ các công thức ña
thức mà có một công thức ña thức nào ñó thực sự ñơn
giản hơn chúng. Các công thức ña thức còn lại chính là
các công thức ña thức tối tiểu của f.
06/05/2010 35
2. Hàm Bool
Ví dụ 1: Tìm tất cả các công thức ña thức tối tiểu của
hàm Bool
Ta có:
Bước 1:Vẽ kar(f):
( , , , ) ( )f x y z t xyzt x y xz yz xy z t= + + + + +
f xyzt x y xz yz xyz xyt= + + + + +
x x
z 1 2 3
z 4 5 6 t
7 8 t
9 10
y y
x x
z
y y
z
t
t
06/05/2010 36
2. Hàm Bool
Bước 2: Kar(f) có các tế bào lớn như sau:
x x
z 1 2
z 4 5 t
7 8 t
9 10
y y
x x
z
y y
z
t
t
x x
z 2 3
z 5 6 t
t
y y
x x
z
y y
z
t
t
x yt
06/05/2010
10
06/05/2010 37
2. Hàm Bool
Bước 3: Xác ñịnh các tế bào lớn nhất thiết phải
chọn.
– Ô 1 nằm trong một tế bào lớn duy nhất x. Ta
chọn x.
– Ô 3 nằm trong một tế bào lớn duy nhất yz. Ta
chọn yz.
06/05/2010 38
2. Hàm Bool
Bước 4: Xác ñịnh các phủ tối tiểu gồm các tế bào lớn.
Các ô ñược các tế bào lớn ñã chọn ở bước 3 phủ như
sau:
Ta ñược duy nhất một phủ tối tiểu gồm các tế bào lớn của kar(f): x; yz.
x x
z 1 2 3
z 4 5 6 t
7 8 t
9 10
y y
x x
z
y y
z
t
t
06/05/2010 39
2. Hàm Bool
Bước 5: Xác ñịnh các công thức ña thức tối tiểu của f.
Ứng với phủ tối tiểu gồm các tế bào lớn tìm ñược ở
bước 4 ta tìm ñược duy nhất một công thức ña thức tối
tiểu của f:
f x yz= +
06/05/2010 40
3. Mạng logic (Mạng các cổng)
ðịnh nghĩa
Một mạng logic hay một mạng các cổng là một
hệ thống có dạng:
x1
x2
xn
f(x1,x2,..., xn)
06/05/2010
11
06/05/2010 41
3. Mạng logic (Mạng các cổng)
trong ñó:
- Input: x1, x2,..., xn là các biến Bool.
- Output: f(x1, x2,..., xn) là hàm Bool.
Ta nói mạng logic trên tổng hợp hay biểu diễn
hàm Bool f.
Một mạng logic bất kỳ luôn luôn ñược cấu tạo
từ một số mạng sơ cấp mà ta gọi là các cổng
06/05/2010 42
3. Mạng logic (Mạng các cổng)
Cổng NOT 
Cổng AND 
Cổng OR 
06/05/2010 43
3. Mạng logic (Mạng các cổng)
x
x
y
OR
y
x y
yx
yxxy +
x
x
y
x y
yx
yxxy +
x