Bài giảng Toán rời rạc - Tối thiểu hóa hàm bool - Nguyễn Ngọc Phụng

LOGO
Tối tiểu hố hàm bool
1
Đơ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)
∨ ∨ ∨
Cơng thức đa thức tối tiểu
f =M1 M2  Ml (G)
Ta nĩi rằng cơ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
3Cơng thức đa thức tối tiểu
Đơ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
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.
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 
Trường hợp n = 3:
đánh dấu như sau:
4
Với qui ước:
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).
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.x
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:
Trường hợp n = 4:
6
Với qui ước:
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).
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, t.x
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.
Định lý
Cho f, g là các hàm Bool theo n biến x1,x2,,xn. 
Khi đĩ:
a) kar(fg) = kar(f)∩kar(g).
b) kar(f∨g) = kar(f)∪kar(g).
c) kar(f) gồm đúng một ơ khi và chỉ khi f là một từ 
tối tiểu
8
Tế bào là hình chữ nhật (theo nghĩa rộng) gồm 2n-k ơ
Tế bào 
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 tồ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.
9
Ví dụ 1. Xét các hàm Bool theo 4 biến x, y, z, t.
10
Ví dụ 2. Xét các hàm Bool theo 4 biến x, y, z, t.
11
Ví dụ 3.
Xét các hàm Bool theo 4 biến x, y, z, t.
12
Ví dụ 4.
Xét các hàm Bool theo 4 biến x, y, z, t.
13
Ví dụ 5. Xét các hàm Bool theo 4 biến x, y, z, t.
Tế bào sau: 
Là biểu đồ Karnaugh của đơn thức nào?
14
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:
Tế bào lớn.
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).
15
Ví dụ. Xét hàm Bool f theo 4 biến x, y, z, t cĩ biểu đồ karnaugh 
như sau:
16
Kar(f) cĩ 6 tế bào lớn như sau:
17
18
19
Thuật tốn.
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 m 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.
20
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).
21

 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 
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.
22
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:
( , , , ) ( )f x y z t xyzt xy xz yz xy z t= ∨ ∨ ∨ ∨ ∨
xyzt xy xz yz xyz xyt= ∨ ∨ ∨ ∨ ∨
23
( , , , )f x y z t xy xzx yyzt z xyz xyt= ∨ ∨ ∨ ∨ ∨
24
( , , , ) xf x y z t xyzt xz yz z x ty xy y= ∨ ∨ ∨ ∨ ∨
25
( , , , )f x y z t xyzt xy yz x zz y xytx= ∨ ∨ ∨ ∨ ∨
26
( , , , )f x y z t xyzt x yzy xz xyz xyt= ∨ ∨ ∨ ∨ ∨
27
( , , , )f x y z t xyzt xy xz yz xyz xyt= ∨ ∨ ∨ ∨ ∨
28
( , , , )f x y z t xyzt xy xz yz xyz xyt= ∨ ∨ ∨ ∨ ∨
29
Bước 1:Vẽ kar(f):
( , , , )f x y z t xyzt xy xz yz xyz xyt= ∨ ∨ ∨ ∨ ∨
30
Bước 2: Kar(f) cĩ các tế bào lớn như sau:
x
( , , , )f x y z t xyzt xy xz yz xyz xyt= ∨ ∨ ∨ ∨ ∨
yz
31
1 2 3
1 2
4 5
7 8
Bước 3: Xác định các tế bào lớn nhất thiết phải chọn:
x
- Ơ 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.
( , , , )f x y z t xyzt xy xz yz xyz xyt= ∨ ∨ ∨ ∨ ∨
4 5 6
7 8
9 10
9 10
2 3
5 6
yz
32
1 2 3
4 5 6
7 8
Bước 4: Xác định các phủ tối tiểu gồm các tế bào lớn
x
1 2 3
4 5 6
7 8
9 10
9 10
yz
1 2 3
4 5 6
7 8
9 10
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.
33

 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 y z t xyzt xy xz yz xyz xyt= ∨ ∨ ∨ ∨ ∨
x ∨ yz
34
1 2
3 4 5
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
6 7 8 9
B1: Vẽ Kar(f)
35
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
B2: Xác định tế bào lớn
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
36
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
B3: Xác định các tế bào lớn nhất thiết phải chọn
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
37

 Bước 3: Xác định các tế bào lớn nhất thiết 
phải chọn
 Ơ 6 nằm trong một tế bào lớn duy nhất . Ta 
chọn 
 Ơ 1 nằm trong một tế bào lớn duy nhất . 
zt
zt
xt
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
Ta chọn 
 Ơ 4 nằm trong một tế bào lớn duy nhất xzt . 
Ta chọn xzt
xt
38
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
1 2
3 4 5
6 7 8 9
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
1 2
3 4 5
6 7 8 9
zt xt xzt∨ ∨
B4: Xác định các phủ tối tiểu gồm các tế bào lớn
39
1 2
3 4 5
6 7 8 9
1 2 1 2
Cịn lại ơ 5 chưa bị phủ
Ơ 5 nằm trong 2 tế bào lớn: 2 cách chọn
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
B4: Xác định các phủ tối tiểu gồm các tế bào lớn
3 4 5
6 7 8 9
3 4 5
6 7 8 9
zt xt xzt∨ ∨
40
1 2
3 4 5
6 7 8 9
1 2
3 4 5
Cịn lại ơ 5 chưa bị phủ
Ơ 5 nằm trong 2 tế bào lớn: 2 cách chọn
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
B4: Xác định các phủ tối tiểu gồm các tế bào lớn
6 7 8 9
zt xt xzt xyz∨ ∨ ∨
41
1 2
3 4 5
6 7 8 9
1 2
3 4 5
Cịn lại ơ 5 chưa bị phủ
Ơ 5 nằm trong 2 tế bào lớn: 2 cách chọn
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
B4: Xác định các phủ tối tiểu gồm các tế bào lớn
6 7 8 9
zt xt xzt yzt∨ ∨ ∨
42

 Bước 5: Xác định các cơng thức đa thức tối 
tiểu của f
f yzt yzt yzt xyzt xzt= ∨ ∨ ∨ ∨
zt xt xzt xyz∨ ∨ ∨
z t x t xzt yzt∨ ∨ ∨
43

Hãy xác định các công thức đa thức tối tiểu của 
hàm Bool: 
)()( yxytztzxtyzxf ∨∨∨∨=
44

Biểu đồ Karnaugh:
45

Các tế bào lớn:
tyxtzxztzyxz ,,,,

Các tế bào lớn bắt buộc phải chọn là

Còn lại ô (1,4) có thể nằm trong 2 tế bào lớn
tzxztxz ,,
tyxzy ,
46

Do đó có 2 công thức đa thức tương ứng với phủ tối
tiểu:

Trong đó chỉ có công thức thứ hai là tối tiểu
zytzxztxzf
tyxtzxztxzf
∨∨∨=
∨∨∨=
47