









Preview text:
  lOMoAR cPSD| 59994889  Ôn tập Toán rời rạc  Nguyễn Hoàng Minh Tâm  Ngày 17 tháng 12 năm 2024  Giới thiệu 
Đây là một file tổng hợp ngắn gọn các khái niệm và kiến trúc trọng tâm có thể ra trong thi, đồng thời 
cung cấp thuật toán để giải quyết các yêu cầu của đề bài. Lưu ý rằng tác giả không tóm tắt toàn bộ 
các tính chất hoặc chi tiết vốn có trong bài giảng, vậy nên bạn đọc vẫn nên kết hợp với bài 
giảng/slide/giáo trình được giảng viên cung cấp để có được kiến thức vững chắc nhất cũng như nắm 
được cách trình bày cho phù hợp.  1 Hệ thức đệ quy 
1.1 Định nghĩa và giải hệ thức đệ quy 
• Cho dãy panqněr thỏa mãn: 
ar “ α1,ar`1 “ α2,...ar`k´1 “ αk (˚) 
@n ě r ` k,an “ fpn,an´1,an´2,...an´kq (˚˚) 
Ta nói dãy panqněr có hệ thức truy hồi cấp k (˚˚) với điều kiện ban đầu (˚). 
• Kết quả khi chỉ giải (˚˚) thường sẽ là vô số dãy thỏa mãn nên ta gọi chúng là nghiệm tổng quát 
của (˚˚). Còn khi kết hợp với điều kiện ban đầu (˚) thì có thể chỉ có một ( hoặc không có) dãy 
thỏa cả (˚) lẫn (˚˚). Ta gọi kết quả này là nghiệm riêng của (˚˚) ứng với  (˚). 
1.2 Hệ thức đệ quy tuyến tính hệ số hằng  1.2.1  Định nghĩa 
• Dãy panqněr có một hệ thức đệ quy tuyến tính hệ số hằng bậc k nếu: 
ar “ α1,ar`1 “ α2,...ar`k´1 “ αk (˚) 
@n ě r ` k,an “ c1 ¨ an´1 ` c2 ¨ an´2 ` ¨¨¨ ` ck ¨ an´k ` fpnq (˚˚) 
@1 ď i ď k,ci “ const 
• Nếu fpnq “ 0 thì (˚˚) ở dạng thuần nhất, còn nếu fpnq ‰ 0 thì (˚˚) ở dạng không thuần nhất.  1.2.2  Cách giải 
Sử dụng dãy panqněr được địng nghĩa ở trên, ta có các bước tìm giải quyết như sau ( Trong phạm vi ôn tập, 
ta chỉ xét các hệ thức đệ quy có bậc 1 và 2): 
1. Tìm nghiệm tổng quát a1n ứng với dạng thuần nhất của hệ thức đệ quy (˚˚): xét dạng thuần 
nhất của hệ thức đệ quy (cần chỉ ra cụ thể) và xét đa thức đặc trưng:      lOMoAR cPSD| 59994889 
fpλq “ λk ´ c1λk´1 ´ c2λk´2 ´ ¨¨¨ ´ ck 
rồi chỉ ra tất cả các nghiệm của phương trình đặc trưng fpλq “ 0, gồm có λ1,λ2,...λm cùng số lần xuất 
hiện của nó để rút ra nghiệm tổng quát cần tìm. Cụ thể: 
• Với k “ 1, ta luôn có nghiệm λ “ c1 nên ta có nghiệm tổng quát là . 
• Với k “ 2, ta có 3 trường hợp phụ có thể xảy ra: 
– Nếu có hai nghiệm thực phân biệt λ1,λ2 thì nghiệm tổng quát là . – Nếu 
có nghiệm thực và kép λ1 thì nghiệm tổng quát là . 
– Nếu có 2 nghiệm phức thì viết chúng dưới dạng λ1,2 “ d ¨ pcospφq ˘ i ¨ sinpφqq, khi đó 
nghiệm tổng quát là a1n “ dn ¨ pp ¨ cospnφq ˘ q ¨ sinpnφqq. 
Ở tất cả các trường hợp, ta đều có p,q P R và công thức nghiệm áp dụng với mọi n ě r. 
2. Trong trường hợp hệ thức đệ quy không thuần nhất thì ta cần tìm nghiệm cụ thể a2n ứng với 
(˚˚). Trong phạm vi môn học, ta chỉ xét các hàm fpnq thỏa fpxq “ αnPpnq với Ppnq là một đa 
thức hệ số thực theo n và m “ degpPpxqq ě 0. Tương tự lúc tìm nghiệm tổng quát, ta cũng 
chia ra các trường hợp như sau:  • Với k “ 1: 
– Nếu α ‰ c1 thì nghiệm riêng a2n “ αnQpnq. – Ngược lại thì nghiệm riêng a2n “ αnnQpnq.  • Với k “ 2: 
– Nếu α không là nghiệm của fpλq thì nghiệm riêng a2n “ αnQpnq. 
– Nếu α là nghiệm đơn fpλq thì nghiệm riêng a2n “ αnnQpnq. 
– Nếu α là nghiệm kép fpλq thì nghiệm riêng a2n “ αnn2Qpnq. 
Ở tất cả các trường hợp, ta đều có Qpnq là một đa thức hệ số thực theo n thỏa degpQpxqq “ 
degpPpxqq “ m và công thức nghiệm áp dụng với mọi n ě r. 
3. Kết luận nghiệm tổng quát: 
• Nếu hệ thức đệ quy là thuần nhất thì ta kết luận nghiệm tổng quát an “ an1,@n ě r. • Còn nếu 
hệ thức đệ quy là không thuần nhất thì ta kết luận nghiệm tổng quát an “ a1n ` a2n,@n ě r. 
4. Tìm nghiệm riêng cuối cùng: Nếu bài toán có cung cấp điều kiện ban đầu (˚) thì ta lập hệ 
phương trình tuyến tính k biến bằng cách thay lần lượt giá trị của ar,ar`1,...ar`k´1 vào công thức 
nghiệm tổng quát an, rồi từ đó tìm ra nghiệm riêng an của (˚˚) ứng với điều kiện ban đầu (˚).  2 Tập hợp số nguyên  2.1 Ước chung lớn nhất  2.1.1 
Một số mệnh đề quan trọng 
• d là UCLN của a và b ðñ d dương và chia hết cho mọi ước chung của a và b 
• d là UCLN của a và b thì tồn tại u,v P Z thỏa d “ ua ` vb 
• pka,kbq “ k ¨ pa,bq 
• Nếu a “ bq ` r là phép chia Euclid thì pa,bq “ pb,rq        lOMoAR cPSD| 59994889  2.1.2 
Thuật toán Euclid để tìm UCLN và biểu diễn tổ hợp nguyên 
Cho a,b P Z thỏa |a| ą |b|. Để tìm d “ gcdpa,bq và 1 bộ u,v P Z thỏa d “ ua ` vb, ta áp dụng thuật toán  Euclid như sau: 
• Tìm d: Để thuận tiện cho bước sau, gán r0 “ a,r1 “ b. Áp dụng thuật chia Euclid, tuần tự thực  hiện:     (1) 
rn´1 “ rn ¨ qn´1 ` 0 
Lúc này ta kết luận d “ pa,bq “ pr0,r1q “ ... “ prn´2,rn´1q “ prn´1,rnq “ rn. 
• Tìm một bộ u,v P Z thỏa mãn: Lần lượt đi ngược lại từ kết quả tính ở bước trên, sử dụng kết 
quả tính được ở bước trước để tính cho bước sau: Giả sử ta có các bộ pui,viqp0 ď i ă nq thỏa: 
r0 ¨ u0 ` r1 ¨ v0 “ d r1 ¨ 
u1 ` r2 ¨ v1 “ d 
r2 ¨ u2 ` r3 ¨ v2 “ d   (2)  ... 
rn´2 ¨ un´2 ` rn´1 ¨ vn´2 “ d rn´1 ¨ un´1 ` 
rn ¨ vn´1 “ d 
Vì rn “ d nên ta có thể chọn pun´1,vn´1q “ p0,1q là một nghiệm thỏa mãn. Từ pui,viq (1 ď i ă n) 
đã tính, ta tính được pui´1,vi´1q “ pvi,ui ´ vi ¨ qi´1q. Tính tuần tự từ pun´1,vn´1q về pu0,v0q, ta sẽ 
tính được pu0,v0q “ pu,vq là một nghiệm cần tìm. Bài toán đến đây là hoàn tất. 
2.2 Bội chung dương nhỏ nhất  2.2.1 
Một số mệnh đề quan trọng 
• e là BCDNN của a và b ðñ e là ước dương của mọi bội chung của a và b 
• e là UCLN của a và b thì tồn tại u1,v1 P Z thỏa   
• rka,kbs “ k ¨ ra,bs 
• Đặt d “ pa,bq thì de “ |ab| và vì tồn tại u,v P Z thỏa d “ ua ` vb nên ta có được  “ 
1 d “ ua`vb “ v¨sgnpbq ` u¨sgnpaq “ v¨sgnpabq ` u¨sgnpabq e |ab| |ab| |a| |b|  a b   
Như vậy thì ta chọn được pu1,v1q “ pv ¨ sgnpabq,u ¨ sgnpabqq thỏa  . 
2.3 Sự nguyên tố cùng nhau  2.3.1 
Tìm dạng tối giản của một số hữu tỉ Để tìm  dạng tối giản của  ), ta cần: 
• Tính UCLN d “ pa,bq  • Tính   2      lOMoAR cPSD| 59994889 
Lúc này pa1,b1q “ 1 nên ta có và ´ a
´ b11 là hai dạng tối giản của . 
2.4 Sự phân tích số nguyên tố  2.4.1 
Định lý phân tích số nguyên tố 
Cho n P Z và n ‰ 0. Khi đó n phân tích được một cách duy nhất dưới dạng   
Trong đó p1 ă p2 ă ...pm là các số nguyên tố và k1,k2,...km P N. (m là số ước 
nguyên tố phân biệt của n, khi n “ ˘1 thì m “ 0). 
Như vậy ta có được một phép phân tích số nguyên tố của n, và để tìm ra cách phân tích như vậy ta có  thuật toán sau: 
1. Xác định tùy ý một ước nguyên tố p1 tùy ý của n. 
2. Với p1 vừa tìm được, xác định k1 P N lớn nhất có thể mà
. Như vậy trong cách phân tích số 
nguyên tố của n sẽ có ước nguyên tố p1 ứng với số mũ k1.  3. Tính
| ă |n| và n1 là ước của n nên ta có thể nhân dạng phân tích của  để 
có được dạng phân tích của n. 
4. Nếu |n1| ą 1 thì quay lại bước 1 và thay n bằng n1. 
5. Còn nếu không thì sau m bước, ta có được các bộ ppi,kiq (1 ď i ď m) là tất cả các ước nguyên tố của 
n. Sắp xếp các bộ đó theo thứ tự tăng dần của pi, ta có được   
là dạng phân tích thừa số nguyên tố của n (n1 “ ˘1 là giá trị n1 cuối cùng tính được).  2.4.2 
Một số kết quả quan trọng từ định lý phân tích số nguyên tố Cho a,b P Z. Phân  tích nguyên tố: 
a “ ˘pk11pk22 ...pkmm  l1 l2  lm  (3) 
b “ ˘q1 q2 ...qm1 1 
Rồi đặt P “ tp1,p2,...pmu Y tq1,q2,...qm1u “ tP1,P2,...Pnu (với n “ |P|), và viết lại  a 
“ ˘P1k11 P2k21  ...Pkn1  1  1  n1   (4)  b 
“ ˘P1l1P2l2 ...Pnln 
Thì ta có những kết quả sau:  1.  q  2.  q 
3. pa,bq “ 1 khi và chỉ khi P “ tp1,p2,...pmu X tq1,q2,...qm1u “ H (hay tức là minpki1,li1q “ 0 với 1 ď i ď n, 
dựa trên kết quả ở trên). 
4. a|b khi và chỉ khi ki1 ď li1 với 1 ď i ď n.        lOMoAR cPSD| 59994889 
Dựa vào tính chất cuối cùng ở trên, ta có thể chỉ ra tập các ước số nguyên dương của n P Z với   là:  u 
Áp dụng quy tắc nhân, ta tính được số ước dương của n là 
|D| “ p1 ` k1qp1 ` k2q...p1 ` kmq  3 Quan hệ trên tập hợp  3.1 Quan hệ hai ngôi  3.1.1  Định nghĩa 
Một quan hệ hai ngôi trên tập S ‰ H là một tập hợp R “ tpx,yq P S2 | xRyu Ď S2.  3.1.2 
Các tính chất của quan hệ hai ngôi 
Cho R “ tpx,yq P S2 | xRyu Ď S2 là 1 quan hệ trên S ‰ H. Ta có: 
• R có tính phản xạ nếu @x P S,xRx. 
• R có tính đối xứng nếu @x,y P S,xRy ÑÝ yRx. 
• R có tính phản xứng nếu @x,y P S,pxRy ^ yRxq ÑÝ px “ yq. 
• R có tính bắc cầu (truyền) nếu @x,y,z P S,pxRy ^ yRzq ÑÝ xRz  3.2 Quan hệ thứ tự  3.2.1  Định nghĩa 
Tập R là 1 quan hệ thứ tự trên S ‰ H khi R có tính phản xạ, tính phản xứng và tính bắc cầu. Khi đó, 
ta có thể kí hiệu ă để thể hiện quan hệ thứ tự thay cho R và kí hiệu pS,ăq là tập hợp S có quan hệ  thứ tự ă.  3.2.2 
Thứ tự toàn phần - Thứ tự bán phần  Xét pS,ăq: 
• Nếu @x,y P S,px ă yq_py ă xq (tức là mọi phần tử trong S đều có thể so sánh được với nhau) thì ă 
là một thứ tự toàn phần trong S. 
• Ngược lại, nếu có ít nhất 1 cặp px,yq P S2 mà giữa x và y không so sánh được thì ă là một thứ tự  bán phần.  3.2.3 
Tính kề nhau và biểu đồ Hasse 
Cho pS,ăq và x,y P S,x ‰ y. Nếu x ă y và không tồn tại z P S,z ‰ x,z ‰ y thỏa x ă z ă y thì ta nói x kề 
y và ta vẽ một mũi tên định hướng từ x đến y. Xét tất cả mọi cặp px,yq P S2 và vẽ mũi tên với những 
cặp thỏa mãn tính chất trên, ta thu được biểu đồ Hasse cho pS,ăq.  4      lOMoAR cPSD| 59994889  3.2.4 
Phần tử cực tiểu(tối tiểu) và phần tử cực đại (tối đại) Cho pS,ăq và 
một phần tử a P S. Ta nói rằng: 
• a “ minpS,ăq là phần tử cực tiểu nếu @x P S,a ă x. 
• a “ maxpS,ăq là phần tử cực đại nếu @x P S,x ă a. 
• a là phần tử tối tiểu nếu Ex P Sztau,x ă a. 
• a là phần tử tối đại nếu Ex P Sztau,a ă x. 
Dựa trên biểu đồ Hasse ứng với pS,ăq, tương ứng với từng ý trên, ta thấy rằng: 
• a “ minpS,ăq là phần tử cực tiểu nếu a là điểm xuất phát chung của mọi nhánh. 
• a “ maxpS,ăq là phần tử cực đại nếu a là điểm kết thúc chung của mọi nhánh. 
• a là phần tử tối tiểu nếu a là điểm xuất phát của ít nhất một nhánh. 
• a là phần tử tối đại nếu a là điểm kết thúc của ít nhất một nhánh. 
Trong một tập hợp sẽ luôn có một (hoặc nhiều) phần tử tối tiểu và một (hoặc nhiều) phần tử tối đại, 
nhưng sẽ chỉ có một (hoặc không tồn tại) phần tử cực tiểu và chỉ có một (hoặc không tồn tại) phần 
tử cực đại. Ngoài ra, mọi phần tử cô lập đều được tính là phần tử tối tiểu lẫn phần tử tối đại. 
3.3 Quan hệ tương đương  3.3.1  Định nghĩa 
Tập R là 1 quan hệ tương đương trên S ‰ H khi R có tính phản xạ, tính đối xứng và tính bắc cầu. Khi 
đó, ta có thể kí hiệu „ để thể hiện quan hệ thứ tự thay cho R và kí hiệu pS,„q là tập hợp S có quan  hệ tương đương „.  3.3.2 
Lớp tương đương của một phần tử, sự phân hoạch thành các lớp tương đương và tập hợp 
thương được xác định bởi quan hệ tương đương Cho pS,„q. 
• Xét a P S, ras “ tx P S | x „ au được gọi là lớp tương đương của a trên S. 
• Do tính chất quan hệ tương đương nên hai phần tử bất kỳ hoặc là có quan hệ (thì cùng chung lớp 
tương đương) hoặc không có quan hệ (thì có lớp tương đương khác nhau và không giao nhau) nên 
„ sẽ phân hoạch S thành các lớp tương đương rời nhau từng đôi một: 
S “ ra1s Y ra2s Y ...raks 
với k ě 1 là số lớp tương đương phân biệt tối đa, rais lần lượt là các lớp tương đương ứng với ai  P S thỏa 
rais X rajs “ H,@1 ď i ă j ď k 
• Sau khi phân hoạch S thành các lớp tương đương, ta sẽ có được 
pS{ „q “ tras | a P Su 
là tập hợp thương của S xác định bởi quan hệ tương đương „.        lOMoAR cPSD| 59994889 
3.4 Quan hệ đồng dư trên Z  3.4.1  Định nghĩa 
• Quan hệ đồng dư modulo n trên Z là a „ b ðñ a ” b (mod n). 
• Kí hiệu Zn “ pZ{ „q “ t0,1,...,n ´ 1u.    3.4.2 
Các phép toán trên Zn 
• Các phép toán cơ bản cộng, trừ và nhân trên Zn có thể được định nghĩa giống các phép toán 
bình thường (tuy nhiên phải lấy số dư của kết quả). 
• Tuy nhiên, kết quả của phép chia có thể không tồn tại. Cụ thể, x{y chỉ tồn tại khi 1{y tồn tại, 
tức là tồn tại y1 thỏa y ¨y1 “ 1. Dựa theo định nghĩa về quan hệ đồng dư modulo n, điều này có 
nghĩa là phương trình yX `nY “ 1 có cặp nghiệm nguyên pX,Y q nào đó, mà như vậy thì điều 
kiện py,nq “ 1 phải được thỏa mãn.     
• Do đó, chỉ có các phần tử y thuộc tập hợp UpZnq “ tk P Zn | pk,nq “ 1u thì mới tồn tại phần tử 
khả nghịch tương ứng và duy nhất, ký hiệu y´1, và ta có thể dùng phương trình ở phía trên để 
tính giá trị của y´1. 
• Khi n là một số nguyên tố p thì pk,nq ‰ 1 ðñ n | k, nên ngoại trừ 0, còn lại mọi phần tử trong 
Zn đều sẽ có phần tử khả nghịch.    3.4.3 
Giải phương trình trên Zn 
Cho a,b P Zn, cần tìm x P Zn thỏa a¨x “ b p˚q. Để giải phương trình này, ta làm các bước sau: 
1. Nếu a “ 0 thì tùy theo b “ 0 hay không mà phương trình có thể vô nghiệm (b ‰ 0) hoặc n  nghiệm (b “ 0). 
2. Ngược lại, tính d “ pa,nq và kiểm tra b có chia hết cho d hay không. 
• Nếu d | b thì ta kết luận p˚q không có nghiệm (nên lập luận giải thích tại sao lại không  có nghiệm).   
• Ngược lại, đặt a1 “ a{d, b1 “ b{d, n1 “ n{d và xét phương trình a1 ¨ x “ b1 p˚˚q trong 
Zn1. Lúc này ta có a1 ‰ 0 và pa1,n1q “ 1 nên tồn tại a1´1 thỏa a1 ¨a1´1 “ 1 trong Zn1. Tính a1´1, rồi 
từ đây ta tìm được x “ b1 ¨a1´1 là nghiệm duy nhất của p˚˚q trong Zn1.      6      lOMoAR cPSD| 59994889 
Đặt b1 ¨ a1´1 “ c P Zn thì ta kết luận (˚) có d nghiệm là x “ c ` kn1 (0 ď k ă dq.  4 Hàm Boolean 
4.1 Định nghĩa đại số Boolean nhị phân 
Cho B “ t0,1u và các phép toán trên B như sau:  @x,y P B : 
x„^xy ““ 1xy ´ x 
(5) x _ y “ x ` y ´ xy 
thì ta có cấu trúc đại số Boolean pB,„,^,_q trong đó các phép bù Boolean („), tích Boolean (^) và tổng 
Boolean (_) tương ứng với các phép NOT, AND và OR trong các mệnh đề logic. Do đó, ta có thể biến 
đổi 1 biểu thức trên đại số Boolean thành một mệnh đề logic và ngược lại. (Một cách không chính 
thức, có thể coi phép tích Boolean và tổng Boolean giống như phép tích và phép tổng thông thường)  4.2 Hàm Boolean 
Một hàm Boolean là một ánh xạ 
f : Bn ÑÝ B “ t0,1u  (6) 
X “ px1,x2,...,xn´1,xnq ÑÝ fpXq “ fpx1,x2,...,xn´1,xnq 
với X “ px1,x2,...,xn´1,xnq là 1 vector Boolean. Vì có 2n vector đầu vào có thể nên mỗi hàm Boolean n 
biến được mô tả bằng một bảng giá trị có 2n cột là các vector Boolean và giá trị của hàm ứng với 
vector đó. Một ví dụ với hàm Boolean 2 biến như sau:  p  0  1  0  1            q  0 0 1 1  fpp,q  0 1 1 0 
Xét Fn là tập hợp các hàm Boolean 
n biến thì |Fn| “ 22n và luôn có 2 hàm  q 
đặc biệt là hàm hằng 0 và hàm hằng 
1. Trên tập Fn, ta cũng có thể định 
nghĩa các phép toán tương tự như trên đại số Boolean như sau: 
@f,g P Fn,@X “ px1,x2,...,xn´1,xnq P Bn : 
„ fpXq “ 1pXq ´ fpXq  (7) 
pf ^ gqpXq “ fpXqgpXq 
pf _ gqpXq “ fpXq ` gpXq ´ fpXqgpXq 
Cấu trúc đại số pFn,„,^,_q được gọi là đại số Boolean của các hàm n biến, và nó cũng tương tự như đại  số Boolean vậy. 
4.3 Các dạng biểu diễn của hàm Boolean 
Xét các hàm Boolean fpx1,x2,...,xn´1,xnq P Fn: 
1. Từ đơn: Có 2n hàm cơ bản (từ đơn), mỗi từ đơn ứng với xi hoặc „ xi với 1 ď i ď n 
2. Đơn thức: Là tích của một số từ đơn thỏa không đồng thời chứa xi và „ xi và không viết lặp lại 
từ đơn. Bậc (degpq) của một đơn thức lúc này là số từ đơn xuất hiện trong đơn thức, và khi 
bậc của đơn thức đúng bằng n thì đây là một đơn thức tối tiểu, và khi đấy đơn thức có dạng 
tổng quát: m “ y1y2 ...yn trong đó yi “ xi hoặc yi “„ xi 
3. Đa thức: Là tổng Boolean của một số đơn thức trong Fn.        lOMoAR cPSD| 59994889 
4. Dạng nối rời chính tắc: Là 1 đa thức mà mọi thành phần đơn thức đều là đơn thức tối tiểu 
Một hàm f thỏa mãn dạng này sẽ có dạng: f “ m1 _ m2 _ ... _ mk với các mi đều là đơn thức tối 
tiểu (hoán vị của các đơn thức không ảnh hưởng đến kết quả của hàm). 
Từ các định nghĩa trên, ta có một cách đơn giản để xác định dạng nối rời chính tắc như sau: 
1. Xác định tất cả các vector Boolean X “ px1,x2,...,xn´1,xnq thỏa fpXq “ 1. 
2. Lập dang sách các đơn thức mi “ x1x2 ...xnp1 ď i ď kq với k là số vector thỏa mãn. 
3. Lập hàm f “ m1 _ m2 _ ... _ mk. Đây là dạng nối rời chính tắc cần tìm. 
4.4 So sánh các dạng đa thức 
Xét f P Fn và f không phải hàm hằng. Giả sử f có 2 dạng biểu diễn 
f “ u1 _ u2 _ ... _ up (1) và f “ v1 _ v2 _ ... _ vq (2) 
thì có 3 trường hợp xảy ra: 
• Đơn giản như nhau: khi p “ q và degpuiq “ degpviq,1 ď i ď n (có cùng số đơn thức và các đơn thức 
có bậc tương ứng bằng nhau) 
• Đơn giản hơn (không mất tính tổng quát, chỉ xét trường hợp (1) đơn giản hơn (2)) như sau: khi p 
ď q, degpuiq ď degpviq,1 ď i ď n và D1 ď i ď n : degpuiq ă degpviq ((1) có ít đơn thức hơn (2), mọi 
đơn thức của (1) đều có bậc không lớn hơn đơn thức thức tương ứng của (2) và tồn tại 1 đơn 
thức có bậc nhỏ hơn hẳn). 
• Không so sánh được: khi 2 trường hợp trên không xảy ra. 
Vì f có nhiều dạng đa thức khác nhau nên ta so sánh cách dạng đa thức và tứ đó chọn ra các dạng đa thức 
đơn giản nhất có thể, được gọi là các công thức đa thức tối tiểu của f.  4.5 Biểu đồ Karnaugh  4.5.1 
Một số định nghĩa cần thiết 
Xét f P Fn (n ď 4) và bảng giá trị của f, ta có thể xây dựng biểu đồ Karnaugh tương ứng với tập các 
vector Boolean thỏa fpXq “ 1, kí hiệu tập các ô được đánh dấu là S “ Karpfq. Một số tính chất: 
• Karp„ fq “ p„ Karpfqq 
• Karpf ^ gq “ Karpfq ^ Karpgq và Karpf _ gq “ Karpfq _ Karpgq 
• f ď g ðñ Karpfq Ď Karpgq 
• Với m P Fn là một đơn thức bậc p thì Karpmq là một hình chữ nhật (mở rộng) có kích  thước 2n´p. 
Một tế bào trong S là một hình chữ nhật (mở rộng) có số ô là 2kp0 ď k ď 4q 
Một tế bào lớn T trong S là một tế bào mà không tế bào nào khác chứa nó ngoài chính nó). 
Một phép phủ trên tập S là tập T “ tT1,T2,...,Tku thỏa S là giao của các Ti trong T và nếu không thể 
loại bỏ bớt Ti khỏi T mà kết quả của phép giao vẫn là S thì đây là một phép phủ tối thiểu.  8      lOMoAR cPSD| 59994889  4.5.2 
Thuật toán để tìm các công thức đa thức tối tiểu cho hàm Boolean 
• Xác định tất cả các tế bào lớn của S. Cụ thể, cần đi từ số ô lớn nhất (16 ô) đến số ô nhỏ nhất (1 ô), 
rồi chọn thêm tất cả các tế bào lớn có cùng số ô như vậy, và chỉ phải chọn tiếp nếu như các tế bào 
lớn đã chọn được vẫn chưa phủ hết biểu đồ. 
• Sau đó, xét tất cả các ô mà chỉ có 1 tế bào lớn phủ lên nó, và chọn luôn tế bào lớn mà đang phủ  những ô này. 
• Với những ô còn lại, tùy ý chọn một ô chưa được phủ lẫn một tế bào lớn đang phủ lên nó. Cứ như 
vậy cho đến khi tất cả các ô đều đã được phủ. 
• Từ định nghĩa, chỉ giữ lại các phép phủ tối tiểu của S. 
• Viết công thức đa thức cho từng phép phủ được giữ lại và chỉ chọn ra các công thức đơn giản nhất 
có thể. Đây là các công thức đa thức tối tiểu của f.  4.5.3  Thiết kế mạch điện 
Tốt nhất, ta nên xác định một công thức đa thức tối tiểu của hàm Boolean f đại diện cho mạng (gồm các 
cổng AND, OR, NOT và các dây dẫn) trước khi mua sắm các cổng và thiết kế.