Ôn Tập cuối kỳ môn Toán rời rạc 1A | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

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ế.