TOÁN HỌC RỜI RẠC PHẦN 1
DISCRETE MATHEMATICS PART ONE
NỘI DUNG ÔN TẬP
PHẦN 1 1. CƠ SỞ LOGIC
a. Phép tính mệnh đề & vị từ b. Quy tắc suy luận. Quy nạp
2. ĐẠI SỐ BOOL
a. Quan hệ thứ tự & tập hợp được sắp b. Dàn và đại số bool c. Hàm bool d. Phương trình bool & hệ phủ tối tiểu e. Công thức tối tiểu của hàm bool
PHẦN 2 1. PHÉP ĐẾM
a. Nguyên lý cộng, nhân & bù trừ b. Giải tích tổ hợp c. Nguyên lý Dirichlet d. Công thức đệ quy
2
NỘI DUNG ÔN TẬP (cont.)
2. LÝ THUYẾT ĐỒ THỊ
a. Đại cương b. Đồ thị liên thông c. Đường đi ngắn nhất d. Cây khung trọng lượng tối tiểu e.
Luồng cực đại
2. SỐ HỌC
a. b.
Lý thuyết chia hết Lý thuyết đồng dư
3
CƠ SỞ LOGIC (1)
A. PHÉP TÍNH MỆNH ĐỀ & VỊ TỪ
– Mệnh đề
)
• • • • • • •
Phép phủ định (NOT, ¬, …) Phép hội (AND, (cid:217) ) Phép tuyển: (OR, (cid:218) ) Phép tuyển loại trừ (XOR, ¯ Phép toán trên bit Phép kéo theo: fi Phép tương đương: «
– – Chân trị của mệnh đề: đúng, sai (true, false) Các phép toán mệnh đề
Q hằng đúng
• • • •
Hằng đúng (tautology), hằng sai Tiếp liên Mệnh đề hệ quả: P fi Tương đương logic: P «
Q hằng đúng
4
– – Biểu thức mệnh đề Mệnh đề hệ quả & mệnh đề tương đương
CƠ SỞ LOGIC (2)
Các tương đương thường dùng (T=hằng đúng, F=hằng sai)
Domination laws Associative laws
P (cid:218) T = T P (cid:217) F = F (P (cid:218) Q) (cid:218) R=P (cid:218) (Q (cid:218) R) = P (cid:218) Q (cid:218) R (P (cid:217) Q) (cid:217) R = P (cid:217) (Q (cid:217) R) = P (cid:217) Q (cid:217) R
Identity laws Distributive laws
P (cid:218) F = P P (cid:217) T = P P (cid:218) (Q (cid:217) R)=(P(cid:218) Q) (cid:217) (P(cid:217) R) P (cid:217) (Q (cid:218) R)=(P(cid:217) Q) (cid:218) (P(cid:217) R)
P (cid:218) P = P Idempotent laws ¬(P (cid:218) Q) = ¬P (cid:217) ¬Q
De Morgan’s laws
P (cid:217) P = P
¬(¬P)=P ¬(P (cid:217) Q) = ¬P (cid:218) ¬Q P (cid:218) (P (cid:217) Q) = P Double negation laws Absortion laws
P (cid:218) ¬P = T P (cid:217) (P (cid:218) Q) = P Comlement laws
P fi Q = ¬P (cid:218) Q
P (cid:217) ¬P = F P (cid:218) Q = Q (cid:218) P Commutative laws
5
P (cid:217) Q = Q (cid:217) P
CƠ SỞ LOGIC (3)
–
Vị từ
• {0, 1}
•
, (cid:217) , (cid:218) , …
• • •
X: P(X)) = $ X: P(X)) = "
X: ¬P(X) X: ¬P(X)
6
Vị từ P: E fi Không gian của một vị từ: E = E1xE2x…xEn Trọng lượng của một vị từ: n Các phép toán vị từ: (cid:216) Các lượng tử ¬ (" – ¬ ($ –
CƠ SỞ LOGIC (4)
–
B. QUY TẮC SUY LUẬN Các quy tắc suy luận:
H ng đúng Tên Quy t cắ
ằ (P (cid:218) Q) P fi C ngộ
(cid:218)
P QP QP (cid:217) P
P (cid:217) Q fi P Rút g nọ
,
QPP Q
fi (P (cid:217) (P fi Q)) fi Q Modus ponens
,
fi (cid:216) (¬Q (cid:217) (P fi Q)) fi ¬P Modus tollens
QPQ P
(cid:216)
R
,
fi fi ((P fi Q) (cid:217) (Q fi R)) fi (P fi R) Tam đo n lu n gi ạ ậ ả
fi đ nhị
,
QQP P R QPP (cid:218) Q
7
(cid:216) (¬P (cid:217) (P (cid:218) Q)) fi Q Tam đo n lu n tuy n ể ạ ậ
CƠ SỞ LOGIC (5)
–
Các phương pháp chứng minh: P fi
Q
¬P đúng)
False)
8
• • • • • • Chứng minh rỗng (P = false) Chứng minh tầm thường (Q = true) Chứng minh trực tiếp (P = true kéo theo Q = true) Chứng minh gián tiếp (Chứng minh ¬Q fi Chứng minh phản chứng (Chứng minh ¬Q (cid:217) P fi Chứng minh quy nạp
ĐẠI SỐ BOOL (1)
A. QUAN HỆ
– Quan hệ tương đương
– Quan hệ thứ tự
• • • Def: (phản xạ, đối xứng, bắc cầu) Lớp tương đương Tập thương
)
x=M
E, " x ˛ A: M £ E, " x ˛ A: x £
x=M
• • • •
x (cid:222) m (cid:222) E, " x ˛ A: x £ E, " x ˛ A: m £
M x
9
Def: (phản xạ, phản xứng, bắc cầu) (E, £ Trội, trội trực tiếp, sơ đồ Hasse Quan hệ thứ tự toàn phần, bộ phận Phần tử – tối đại: M˛ A ˝ – tối tiểu: m ˛ A ˝ – phần tử lớn nhất: M˛ A ˝ – phần tử nhỏ nhất: m˛ A ˝
ĐẠI SỐ BOOL (2)
B. DÀN (LATTICE)
–
z, y £
), x, y ˛
E, A={z| x £
z}, nếu A có phần tử nhỏ
–
E, A={z| z £
), x, y ˛
x, z £
–
sup(x, y) = x(cid:218) y, inf(x, y)=x(cid:217) y
), " x, y ˛
Cận trên: (E, £ nhất thì phần tử nhỏ nhất đó được gọi là cận trên (đúng), ký hiệu sup(x, y) / x(cid:218) y cận dưới: (E, £ y}, nếu A có phần tử lớn nhất thì phần tử lớn nhất đó được gọi là cận dưới (đúng), ký hiệu inf(x, y) / x(cid:217) y / xy Dàn: (E, £
E, $ Các tính chất (giao hoán, kết hợp, phân phối) Phần tử bù: (E, £ hiệu 0, x ˛
• • )dàn có phần tử lớn nhất ký hiệu 1, phần tử nhỏ nhất ký
E phần tử bù của x (trong E) là phần tử, ký hiệu sao cho
x
=
(cid:236) (cid:218) (cid:239)
x
x
1
=
(cid:237) (cid:239) (cid:217) (cid:238)
x
x
0
10
• Dàn mà mọi phần tử đều có phần tử bù được gọi là dàn bị bù
ĐẠI SỐ BOOL (3)
• ĐẠI SỐ BOOL – Def1: dàn (E, £
) có nhiều hơn một phần tử , là dàn phân phối và
bị bù Def2: (E, (cid:218) , (cid:217) ) kết hợp, giao hoán, phân phối, có phần tử trung hòa và phần tử bù
– Định lý Stone
• Atom: phần tử trội trực tiếp của phần tử nhỏ nhất • (E, £ " x „
) là một đại số bool hữu hạn với phần tử nhỏ nhất ký hiệu là 0, 0˛
E, a1, a2, …, ak là tất cả các atom bị trội bởi x khi đó: x=a1 (cid:218) a2 (cid:218) … (cid:218) ak
cách viết này là duy nhất nếu không kể đến thự tự của các atom
• Số phần tử của một đại số bool là lũy thừa của 2 • Đại số bool gồm 2n phần tử có n atom
11
HÀM BOOL (1)
A. HÀM BOOL
– –
B=({0, 1}, (cid:218) , (cid:217) ) là một đại số bool f : Bn fi (
,...,
b
x
B , xx 1
n )
2
–
–
Bn : f(X) ≤ g(X)
f tương ứng với một dãy nhị phân độ dài 2n (dãy các giá trị của f trên các bộ biến 0…00, 0…01, 0…10, …) đánh chỉ số cho f bởi dãy nhị phân các giá trị của hàm f Fn = tập tất cả các hàm bool n biến f, g ˛ Fn , f ≤ g khi và chi khi " X ˛ (Fn, ≤) là một đại số bool
12
HÀM BOOL (2)
B. DẠNG CHUẨN TẮC TUYỂN
–
–
–
–
=
˛ "
,...,
)
)
,
Fn tập các hàm bool n biến Từ tối tiểu (nguyên tửAtom): 00..010..0 f là hàm bool, m1, m2, …, mk là tất cả các từ tối tiểu bị trội hơn (cid:218) m2 bởi f, ta có: f=m1 = xx i , ( i i Literal: ,..., bb ( , 1 2
(cid:218) …(cid:218) mk n ,...,2,1 ) n b : B n
( bbx 1 2
b n
b i
i
=
,
,...,
)
( bbx 1 2
i
b n
b i
–
Dạng chuẩn tắc tuyển của hàm bool f (n biến): •
•
Lập bảng giá trị hàm f Phân tích f thành tổng của các từ tối tiểu: f=m1
(cid:218) m2 (cid:218) … (cid:218) mk
=
(cid:236)
1
bx i i
=
(cid:237)
...
y;
• mi(b1, b2, …, bn) = 1, = yym 21
i
y n
i
=
i
x
0
(cid:238)
b i
13
HÀM BOOL (3)
C. DẠNG CHUẨN TẮC HỘI
Từ tối đại: 11…101…1
– – M là từ tối đại, M(b1, b2, …, bn)=0
=
(cid:236)
0
bx i i
=
(cid:218) (cid:218) (cid:218) (cid:237)
...
y;
= yM 1
y 2
y n
i
=
i
x
1
(cid:238)
b i
–
Dạng chuẩn tắc hội của hàm f (n biến): •
•
Lập bảng giá trị của f Phân tích f thành tích các từ tối đại: f=M1M2…Mk
• Mi(b1, b2, …, bn)=0
=
(cid:236)
0
bx i i
=
(cid:218) (cid:218) (cid:218) (cid:237)
...
y;
= yM 1 i
y 2
y n
i
=
i
x
1
(cid:238)
b i
14
HÀM BOOL (4)
• HỆ PHƯƠNG TRÌNH BOOL & PHỦ TỐI TIỂU
–
HỆ PHƯƠNG TRÌNH BOOL:
•
=
•
,...
,...
x
x
)
)
,
xxG ( 1
2
xxD ( 1
1
n
n
2
1 ...
(cid:236) G1, G2, …, Gk, D1, D2, …, Dk là 2n hàm bool n biến x1, x2, …, xn Hệ phương trình bool , (cid:239) (cid:237)
=
xxG (
,
,...
x
)
,
,...
x
)
1
k
2
n
xxD ( 1
k
2
n
(cid:239) (cid:238)
Phương pháp giải 1. 2.
1=GD(cid:218) ¬G¬D, biến đổi hệ về dạng
=
(cid:216) (cid:216) (cid:218) (cid:236)
1
Biến đổi mỗi phương trình về dạng tổng của các tích Áp dụng biến đổi tương đương G=D @ DG 1 1
DG 1 1
(cid:239) (cid:237)
(cid:239)
... =
(cid:216) (cid:216) (cid:218)
1
(cid:238)
DG k k
DG k k
3.
Hệ tương đương với: 1=(G1D1
(cid:218) ¬G1¬D1)…(GkDk(cid:218) ¬Gk¬Dk)
15
HÀM BOOL (5)
4.
5.
Ø
Œ
Œ
=
1
Œ º
Biến đổi phương trình về dạng tổng của các tích: 1=h1 (cid:218) h2 (cid:218) … (cid:218) hm (hi là tích của các biến hoặc phủ định của biến Phương trình tương đương với tuyển = h 11 ... mh
6.
Do mỗi hi là tích các biến hoặc phủ định của biến, ta suy ra các nghiệm của hệ phương trình
–
PHỦ TỐI TIỂU
•
{ Ai | i=1,…, p} ˚ {e1, e2, …, en}. Tìm họ con của họ {Ai} (phủ
–
Cho tập hợp E, e1, e2, …, en là các phần tử của E, A1, A2, …, Ap là các tập con của E, ¨ tối tiểu) sao cho: –
Hợp các tập của họ con này chứa {e1, e2, …, en} Bỏ đi một tập bất kỳ của họ con thì hợp của các tập còn lại không còn chứa {e1, e2, …, en} Phương pháp giải: –
•
xi = 1
–
16
–
Đặt xi là biến sao cho nếu Ai được chọn (cid:219) " ej / Aj1, Aj2, …, Ajq là tất cả các tập của họ chứa ej, ta xây dựng được phương trình: xj1 (cid:218) xj2 (cid:218) … (cid:218) xjq = 1 Giải hệ phương trình ta tìm được phủ tối tiểu
ĐƠN GIẢN CÔNG THỨC (1)
• CÔNG THỨC TỐI TIỂU
–
Đơn thức:
tồn tại x bù của x trong đơn thức
• • •
–
Ước
• tích của các literals khác 0 (nhân tử nguyên tố) Đơn thức = 0 (cid:219) Tồn tại duy nhất một cách viết đơn thức (sai khác thứ tự của các literals) Tập Fn có 3n đơn thức
•
M ≤ m
–
Công thức dạng đa thức:
• • Đơn thức m là ước của đơn thức M (M chia hết cho m) nếu mỗi nhân tử nguyên tố của m đều là nhân tử nguyên tố của M Đơn thức m là ước của M (cid:219) m là ước của M (cid:219) m (cid:218) M = m
=
...
km
–
=
Fn , cách viết f dưới dạng tổng ( (cid:218) ) của các đơn thức được gọi là dạng (cid:218) (cid:218) (cid:218)
...
mmf 1 2
km & "
17
(cid:218) (cid:218) (cid:218) f ˛ mmf đa thức của f: , mk là các đơn thức 1 2 Công thức dạng đa thức tối giản: i „ j, mi không là ước của mj
ĐƠN GIẢN CÔNG THỨC (2)
– Quan hệ đơn giản hơn: hai công thức tối giản của f:
(1)
(2)
(1)
p < q
f=m1 (cid:218) m2 (cid:218) … (cid:218) mp f=M1 (cid:218) M2 (cid:218) … (cid:218) Mq được gọi là đơn giản hơn (2) khi và chỉ khi: •
•
i: mi là ước của ít nhất một Mj
–
"
18
Mỗi hàm bool f có một tập hợp hữu hạn công thức tối giản dạng đa thức và quan hệ đơn giản hơn là một quan hệ thứ tự bộ phận trên tập đó Công thức dạng tối tiểu dạng đa thức: Công thức tối tiểu dạng đa thức của một hàm bool f là phần tử tối tiểu của tập các công thức tối giản dạng đa thức của f
ĐƠN GIẢN CÔNG THỨC (3)
•
PHƯƠNG PHÁP KARNAUGH –
Bảng Karnaugh
a
a
a
a
a
a
a
a
c
c
d
1010 1110 0110 0010 101 111 011 001
c
d
c
1011 1111 0111 0011 100 110 010 000
c
d
b
b
b
b
1001 1101 0101 0001
c
d
ầ ử
b
ế 3 vào b ng ả
b
b
b
S p x p các ph n t ắ c a Bủ karnaugh
ầ ử
ế 4 vào b ng ả
S p x p các ph n t ắ c a Bủ karnaugh
19
1000 1100 0100 0000
ĐƠN GIẢN CÔNG THỨC (4)
–
Sơ đồ karnaugh của hàm 3 hoặc 4 biến
B4
f
B3
f
0000
0
000
0
0001
1
001
0
0010
0
1010 1110 0110 0010
010
1
101
111
011
001
0011
0
011
1
1011 1111 0111 0011
100
110
010
000
0100
1
100
0
1001 1101 0101 0001
0101
1
101
1
0110
0
1000 1100 0100 0000
110
1
0111
1
111
0
1000
0
1001
0
1010
0
ế
Hàm bool 4 bi n f ế =0100110100000011
hàm bool 3 bi n f = 00110110
1011
0
1100
0
1101
0
1110
1
1111
1
20
ĐƠN GIẢN CÔNG THỨC (5)
–
Định lý:
•
hàm đồng nhất 0 là bảng rỗng hàm đồng nhất 1 là bảng có tất cả các ô dược « tô »
Sơ đồ karnaugh của – –
• •
f
•
•
–
yzx
• f ≤ g tương đương với sơ đồ karnaugh của g phủ sơ đồ karnaugh của f Sơ đồ karnaugh của tích fg là giao của sơ đồ karnaugh của f và sơ đồ karnaugh của g Sơ đồ karnaugh của tổng f(cid:218) g là hợp của sơ đồ karnaugh của f và sơ đồ karnaugh của g Sơ đồ karnaugh của là sơ đồ « bù » của sơ đồ karnaugh của f (trong sơ đồ karnaugh của f: xoá các ô được tô, tô các ô không được tô) Sơ đồ karnaugh của mỗi từ tối tiểu chỉ có một ô được tô
(cid:222)
001
011
Sơ đồ karnaugh và dạng chuẩn tắc của hàm tương ứng zyx 111 101
ng ng là:
ươ
ứ
100
110
010
000
ạ =
D ng chu n t c c a hàm t ẩ ắ f yzx zyx
ủ zxy
zyx
zyx
zxy
21
(cid:218) (cid:218) (cid:218)
ĐƠN GIẢN CÔNG THỨC (6)
–
Sơ đồ karnaugh và đơn thức
•
•
–
Tìm công thức tối tiểu bằng phương pháp karnaugh 1. 2. 3.
4. 5.
Lập bảng giá trị và sơ đồ karnaugh của f Xác định các cell lớn (các cell không bị chứa trong cell khác) Chọn các cell lớn chứa ít nhất một ô chỉ thuộc riêng cell đó, « chồng » các cell được chọn (nhận được sơ đồ phụ). Nếu nhận được sơ đồ trùng sơ đồ karnaugh của f thực hiện 6. Nếu không thực hiện 5. Chọn trong các cell lớn còn lại cell lớn chứa nhiều ô chưa được tô nhất (trong sơ đồ « chồng »). Nếu có nhiều cell lớn như vậy, chọn cell lớn nhất. Nếu tồn tại nhiều cell cùng thoả mãn, chọn một trong số đó. Chồng lên sơ đồ phụ. Thực hiện 4. Xây dựng công thức tối tiểu của f : là tổng của các công thức của các cell lớn được chọn So sánh các công thức xây dựng được để xác định công thức tôt nhất (ít phép toán nhất)
6. 7.
22
Định lý: trong Fn, một đơn thức do p nhân tử nguyên tố tạo thành, sơ đồ karnaugh của nó có 2np ô được tô. Sơ đồ karnaugh có hình chữ nhật gồm 2np ô được tô là sơ đồ karnaugh của một đơn thức là tích của p literals (được gọi là cell) Cell của một đơn thức được chứa trọn vẹn trong các dòng và các cột thì công thức của đơn thức là tích của các dòng, cột đó
ĐƠN GIẢN CÔNG THỨC (7)
1010 1110 0110 0010
1011 1111 0111 0011
1001 1101 0101 0001
1000 1100 0100 0000
Các cell l nớ
x
tzy
2.
3.
tyx
1. xyz
x
x
23
4.
5.
zyx
tzx
ĐƠN GIẢN CÔNG THỨC (7)
Ch ng các cell có ô ch thu c mình nó, ta đ
ồ
ộ
ỉ
ượ
c s đ ph : ụ
ơ ồ
ơ ồ
ụ
ớ
ọ
ố
ộ
S đ ph còn khác s đ Karnaugh g c, ch n m t trong hai cell l n 2. ho c 3, ch ng lên s đ ph , ta đ
c:
ơ ồ ặ
ơ ồ
ượ
ụ
ồ
24
ĐƠN GIẢN CÔNG THỨC (7)
i ti u d ng
ớ ơ ồ
ố
ứ ố ể
ạ
ng ng là:
S đ ph bây gi trùng v i s đ Karnaugh g c. Công th c t ờ ụ đa th c c a hàm t ươ ủ
ơ ồ ứ
ứ
=
(cid:218) (cid:218) (cid:218) (cid:218) (cid:218) (cid:218)
f
xyz
tzx
zyx
xzt
(1.
4.
5.
2)
=
(cid:218) (cid:218) (cid:218) (cid:218) (cid:218) (cid:218)
f
xyz
tzx
zyx
tyx
(1.
4.
5.
3.)
C hai công th c « t
ứ
ả
ố
t » nh nhau ư
25
ĐƠN GIẢN CÔNG THỨC (8)
•
PHƯƠNG PHÁP CONSENSUS –
Cơ sở phương pháp:
• i: mi ≤ f
•
• • •
•
Nếu f = m1 (cid:218) m2 (cid:218) … (cid:218) mp là công thức dạng đa thức của f, thì " Nếu m là đơn thúc, m ≤ f thì tồn tại các đơn thức m1, …, mk sao cho f = m (cid:218) m1 (cid:218) … (cid:218) mk Nguyên nhân: đơn thức m ≤ f được gọi là một nguyên nhân của f Nguyên nhân nguyên tố: đơn thức m bị trội trực tiếp bởi f Tổng các nguyên nhân nguyên tố của f là một công thức tối giản dạng đa thức của f Trong công thức tối tiểu dạng đa thức của f, mỗi đơn thức là một nguyên nhân nguyên tố của f
– –
Tìm tập các nguyên nhân nguyên tố của f Xác định tập nhỏ nhất các nguyên nhân nguyên tố tìm được có tổng là f (phủ tối tiểu)
(cid:222) • phương pháp tìm công thức tối tiểu dạng đa thức của f:
xm
2
•
__ x
__ 1 , mx Consensus: hai đơn thức , trong đó m1, m2 là các đơn thức không chứa x và , khi đó m1m2 đươc gọi là consensus của hai đơn thức
26
•
•
ĐƠN GIẢN CÔNG THỨC (9) Consensus(m1, m2) ≤ m1 (cid:218) m2 Tìm nguyên nhân nguyên tố: 1.
2.
Xác định một công thức tối giản dạng đa thức của f. Lập danh sách L các đơn thức nguyên nhân For each variable x a)
x
b)
Chia L thành ba danh sách con: A gồm các đơn thức chứa x, B gồm các đơn thức chứa , C gồm các đơn thức còn lại Nếu A hoặc B rỗng chuyển sang bước tiếp theo, nếu không ,tính các consensus của mỗi đơn thức của A với mỗi đơn thức của B thêm chúng vào L c) Xoá bỏ khỏi L các đơn thức là bội của các đơn thức khác Kết quả thu được: L là danh sách các nguyên nhân nguyên tố của f
3. Tìm phủ tối tiểu các nguyên nhân nguyên tố:
•
Lập và giải hệ phương trình bool cho phủ tối tiểu »
Đơn thức C phủ đơn thức m (cid:219)
C là ước của m
27
(cid:222)
ĐƠN GIẢN CÔNG THỨC (10)
•
PHƯƠNG PHÁP QUINEMC CLUSKEY – Giai đoạn 1: Tìm công thức tối giản dạng đa thức
• •
Lập bảng giá trị của f Lập bảng gồm nhiều cột để ghi kết quả của các bước sau: 1.
2.
BxA
3.
28
Viết vào cột thứ nhất các dãy bit làm f = 1, gom thành từng nhóm theo số bit 1 (sắp các nhóm theo thứ tự tăng của số bit 1) Với mỗi dãy bit của nhóm i viết dưới dạng AxB tổng với dãy bit viết dưới dạng của nhóm i+1. kết quả (A_B) được ghi vào cột kế bên, đánh dấu dãy bit tham gia vào tổng (A hoặc B có thể là rỗng) Lặp lại với cột kế tiếp đến khi không tạo ra cột mới , khi đó dãy bít không bị đánh dấu cho các đơn thức trong công thức tối giản dạng đa thức của f
ĐƠN GIẢN CÔNG THỨC (11)
– Giai Đoạn 2: tìm công thức tối tiểu dạng đa thức
•
Lập bảng phủ: các cột tương ứng với các đơn thức mi trong dạng tuyển chuẩn tắc của f, dòng tương ứng với các đơn thức trong công thức tối giản dạng đa thức, tô ô giao của dòng và cột nếu đơn thức dòng tương ứng là ước của đơn thức cột tương ứng 1.
2. 3.
4.
29
Phát hiện các đơn thức cốt yếu: tìm các cột chỉ một ô được tô, ô được tô nằm trên dòng nào, đơn thức dòng đó là đơn thức cốt yếu Xóa các cột được phủ bởi các đơn thức cốt yếu Xóa các dòng không chứa ô được tô, xóa bớt các cột giống nhau (nếu có) Trong các dòng còn lại, tìm tập ít nhất các đơn thức phủ các cột còn lại
30
