Bài giảng Toán rời rạc - Khương Thị Quỳnh

ầu bằng một bảng chỉ rõ 
các giá trị đầu ra đối với mỗi một tổ hợp các giá trị đầu vào. Ta luôn luôn có thể 
sử dụng khai triển tổng các tích của mạch để tìm tập các cổng lôgic thực hiện 
mạch đó. Tuy nhiên, khai triển tổng các tích có thể chứa các số hạng nhiều hơn 
mức cần thiết. Các số hạng trong khai triển tổng các tích chỉ khác nhau ở một 
biến, sao cho trong số hạng này xuất hiện biến đó và trong số hạng kia xuất hiện 
phần bù của nó, đều có thể đƣợc tổ hợp lại. Chẳng hạn, xét mạch có đầu ra bằng 
1 khi và chỉ khi x = y = z = 1 hoặc x = z = 1 và y = 0. Khai triển tổng các tích 
của mạch này là xyz xyz . Hai tích trong khai triển này chỉ khác nhau ở một 
biến, đó là biến y. Ta có thể tổ hợp lại nhƣ sau: 
 146 
 xyz xyz (y y)xz 1xz xz 
 Do đó, xz là biểu thức với ít phép toán hơn biểu diễn mạch đã cho. Mạch 
thứ hai chỉ dùng một cổng, trong khi mạch thứ nhất phải dùng ba cổng và một 
bộ đảo (cổng NOT). 
8.4.1. Bản đồ Karnaugh 
 Để làm giảm số các số hạng trong một biểu thức Boole biểu diễn một 
mạch, ta cần phải tìm các số hạng để tổ hợp lại. Có một phƣơng pháp đồ thị, gọi 
là bản đồ Karnaugh, đƣợc dùng để tìm các số hạng tổ hợp đƣợc đối với các hàm 
Boole có số biến tƣơng đối nhỏ. Phƣơng pháp mà ta mô tả dƣới đây đã đƣợc 
Maurice Karnaugh đƣa ra vào năm 1953. Phƣơng pháp này dựa trên một công 
trình trƣớc đó của E. W. Veitch. Các bản đồ Karnaugh cho ta một phƣơng pháp 
trực quan để rút gọn các khai triển tổng các tích, nhƣng chúng không thích hợp 
với việc cơ khí hoá quá trình này. Trƣớc hết, ta sẽ minh hoạ cách dùng các bản 
đồ Karnaugh để rút gọn biểu thức của các hàm Boole hai biến. 
 Có bốn hội sơ cấp khác nhau trong khai triển tổng các tích của một hàm 
Boole có hai biến x và y. Một bản đồ Karnaugh đối với một hàm Boole hai biến 
này gồm bốn ô vuông, trong đó hình vuông biểu diễn hội sơ cấp có mặt trong 
khai triển đƣợc ghi số 1. Các hình ô đƣợc gọi là kề nhau nếu các hội sơ cấp mà 
chúng biểu diễn chỉ khác nhau một biến. 
 y y 
 x xy x y 
 x xy x y 
 Thí dụ 8.7: Tìm các bản đồ Karnaugh cho các biểu thức và rút gọn chúng: 
 a) xy xy b) xy xy c) xy xy xy 
 Ta ghi số 1 vào ô vuông khi hội sơ cấp đƣợc biểu diễn bởi ô đó có mặt 
trong khai triển tổng các tích. Ba bản đồ Karnaugh đƣợc cho trên hình sau. 
 Việc nhóm các hội sơ cấp đƣợc chỉ ra trong hình trên bằng cách sử dụng 
bản đồ Karnaugh cho các khai triển đó. Khai triển cực tiểu của tổng các tích này 
tƣơng ứng là: 
 147 
 a) y, b) xy xy , c) x y . 
 Bản đồ Karnaugh ba biến là một hình chữ nhật đƣợc chia thành tám ô. Các 
ô đó biểu diễn tám hội sơ cấp có đƣợc. Hai ô đƣợc gọi là kề nhau nếu các hội sơ 
cấp mà chúng biểu diễn chỉ khác nhau một biến. Một trong các cách để lập bản 
đồ Karnaugh ba biến đƣợc cho trong hình bên. 
 yz yz yz yz 
 x xyz xyz xyz xyz 
 x xyz xyz xyz xyz 
 Để rút gọn khai triển tổng các tích ba biến, ta sẽ dùng bản đồ Karnaugh để 
nhận dạng các hội sơ cấp có thể tổ hợp lại. Các khối gồm hai ô kề nhau biểu 
diễn cặp các hội sơ cấp có thể đƣợc tổ hợp lại thành một tích của hai biến; các 
khối 2 x 2 và 4 x 1 biểu diễn các hội sơ cấp có thể tổ hợp lại thành một biến duy 
nhất; còn khối gồm tất cả tám ô biểu diễn một tích không có một biến nào, cụ 
thể đây là biểu thức 1. 
 Thí dụ 8.8: 
 Dùng các bản đồ Karnaugh ba biến để rút gọn các khai triển tổng các 
tích sau: 
 a) xyz xyz xyz xyz; 
 b) xyz xyz xyz xyz xyz ; 
 c) xyz xyz xyz xyz xyz xyz xyz . 
 Bản đồ Karnaugh cho những khai triển tổng các tích này đƣợc cho trong 
hình sau: 
 148 
 Việc nhóm thành các khối cho thấy rằng các khai triển cực tiểu thành các 
tổng Boole của các tích Boole là: 
 a) xz yz xyz , b) y xz , c) x y z . 
 Bản đồ Karnaugh bốn biến là một hình vuông đƣợc chia làm 16 ô. Các ô 
này biểu diễn 16 hội sơ cấp có đƣợc. Một trong những cách lập bản đồ 
Karnaugh bốn biến đƣợc cho trong hình dƣới đây. 
 yz yz yz yz 
 wx 
 wxyz wxyz wxyz wxyz 
 wx wxyz wxyz wxyz wxyz 
 wx wxyz wxyz wxyz wxyz 
 wxyz wxyz wxyz wxyz 
 wx 
 Hai ô đƣợc gọi là kề nhau nếu các hội sơ cấp mà chúng biểu diễn chỉ khác 
nhau một biến. Do đó, mỗi một ô kề với bốn ô khác. Sự rút gọn một khai triển 
tổng các tích bốn biến đƣợc thực hiện bằng cách nhận dạng các khối gồm 2, 4, 8 
hoặc 16 ô biểu diễn các hội sơ cấp có thể tổ hợp lại đƣợc. Mỗi ô biểu diễn một 
hội sơ cấp hoặc đƣợc dùng để lập một tích có ít biến hơn hoặc đƣợc đƣa vào 
trong khai triển. Cũng nhƣ trong trƣờng hợp bản đồ Karnaugh hai và ba biến, 
mục tiêu là cần phải nhận dạng các khối lớn nhất có chứa các số 1 bằng cách 
dùng một số ít nhất các khối, mà trƣớc hết là các khối lớn nhất. 
8.4.2. Phương pháp Quine-McCluskey 
8.4.2.1. Mở đầu 
 Ta đã thấy rằng các bản đồ Karnaugh có thể đƣợc dùng để tạo biểu thức 
cực tiểu của các hàm Boole nhƣ tổng của các tích Boole. Tuy nhiên, các bản đồ 
Karnaugh sẽ rất khó dùng khi số biến lớn hơn bốn. Hơn nữa, việc dùng các bản 
đồ Karnaugh lại dựa trên việc rà soát trực quan để nhận dạng các số hạng cần 
đƣợc nhóm lại. Vì những nguyên nhân đó, cần phải có một thủ tục rút gọn 
những khai triển tổng các tích có thể cơ khí hoá đƣợc. Phƣơng pháp Quine-
McCluskey là một thủ tục nhƣ vậy. Nó có thể đƣợc dùng cho các hàm Boole có 
 149 
số biến bất kỳ. Phƣơng pháp này đƣợc W. V. Quine và E. J. McCluskey phát 
triển vào những năm 1950. Về cơ bản, phƣơng pháp Quine-McCluskey có hai 
phần. Phần đầu là tìm các số hạng là ứng viên để đƣa vào khai triển cực tiểu nhƣ 
một tổng các tích Boole mà ta gọi là các nguyên nhân nguyên tố. Phần thứ hai là 
xác định xem trong số các ứng viên đó, các số hạng nào là thực sự dùng đƣợc. 
8.4.2.2. Định nghĩa 
 Cho hai hàm Boole F và G bậc n. Ta nói G là một nguyên nhân của F nếu 
TG  TF, nghĩa là G F là một hằng đúng. 
 Dễ thấy rằng mỗi hội sơ cấp trong một dạng tổng chuẩn tắc của F là một 
nguyên nhân của F. Hội sơ cấp A của F đƣợc gọi là một nguyên nhân nguyên tố 
của F nếu trong A xoá đi một biến thì hội nhận đuợc không còn là nguyên nhân 
của F. 
 Nếu F , , F là các nguyên nhân của F thì T  T , 1 i k . 
 1 k Fi F
 k k
 Khi đó: T T  T . Do đó, F là một nguyên nhân của F. 
 k  Fi F  i
  Fi i 1 i 1
 i 1
 Cho S là một hệ các nguyên nhân của F. Ta nói rằng hệ S là đầy đủ đối với 
F nếu F G , nghĩa là TF TG . 
 G S G S
8.4.2.3. Mệnh đề 
 Hệ các nguyên nhân nguyên tố của hàm F là một hệ đầy đủ. 
 Chứng minh: Gọi S là hệ các nguyên nhân nguyên tố của F. 
 Ta có TG  TF , g S . 
 Nên T G TG  TF . Giả sử dạng tổng chuẩn tắc hoàn toàn của F là 
 G S G S
F G' nên TF TG' . 
 G' S' G' S'
 Xét G' S', nếu G’ không phải là nguyên nhân nguyên tố của F thì bằng 
cách xoá bớt một số biến trong G’ ta thu đƣợc nguyên nhân nguyên tố G của F. 
 Khi đó TG'  TG và TG'  TG hay TF  TG . 
 G' S' G S G S
 Vì vậy hay . 
 Dạng tổng chuẩn tắc đƣợc gọi là dạng tổng chuẩn tắc thu gọn của F. 
 150 
8.4.2.4. Phương pháp Quine-McCluskey tìm dạng tổng chuẩn tắc thu gọn 
 Giả sử F là một hàm Boole n biến x1, x2, , xn. Mỗi hội sơ cấp của n biến 
đó đƣợc biểu diễn bằng một dãy n ký hiệu trong bảng {0, 1, −} theo quy ƣớc: ký 
tự thứ i là 1 hay 0 nếu xi có mặt trong hội sơ cấp là bình thƣờng hay với dấu phủ 
định, còn nếu xi không có mặt thì ký tự này là −. Chẳng hạn, hội sơ cấp của 6 
biến x1, , x6 là x1x3x4 x6 đƣợc biểu diễn bởi 0−11−0. Hai hội sơ cấp đƣợc gọi 
là kề nhau nếu các biểu diễn nói trên của chúng chỉ khác nhau ở một vị trí 0, 1. 
Rõ ràng các hội sơ cấp chỉ có thể dán đƣợc với nhau bằng phép dán Ax Ax A 
nếu chúng là kề nhau. 
 Thuật toán đƣợc tiến hành nhƣ sau: Lập một bảng gồm nhiều cột để ghi 
các kết quả dán. Sau đó lần lƣợt thực hiện các bƣớc sau: 
 - Bƣớc 1: Viết vào cột thứ nhất các biểu diễn của các nguyên nhân hạng n 
của hàm Boole F. Các biểu diễn đƣợc chia thành từng nhóm, các biểu diễn trong 
mỗi nhóm có số các ký hiệu 1 bằng nhau và các nhóm xếp theo thứ tự số các ký 
hiệu 1 tăng dần; 
 - Bƣớc 2: Lần lƣợt thực hiện tất cả các phép dán các biểu diễn trong nhóm 
i với các biểu diễn trong nhóm i + 1 (i = 1, 2 ). Biểu diễn nào tham gia ít nhất 
một phép dán sẽ đƣợc ghi nhận một dấu * bên cạnh. Kết quả dán đƣợc ghi vào 
cột tiếp theo; 
 - Bƣớc 3: Lặp lại Bƣớc 2 cho cột kế tiếp cho đến khi không thu thêm đƣợc 
cột nào mới. Khi đó tất cả các biểu diễn không có dấu * sẽ cho ta tất cả các 
nguyên nhân nguyên tố của F. 
 Thí dụ 8.9: Tìm dạng tổng chuẩn tắc thu gọn của các hàm Boole: 
 F1 wxyz wxyz wxyz wxyz wxyz wxyz wxyz 
 F2 wxyz wxyz wxyz wxyz wxyz wxyz wxyz 
 0 0 0 1 * 0 − 0 1 * 0 − − 1 0 0 1 0 * 0 0 1 − 1 1 − − 
 0 1 0 1 * 0 0 − 1 * − 0 − 1 0 0 1 1 * − 0 1 1 
 0 0 1 1 * − 0 0 1 * − − 1 1 1 1 0 0 * 1 1 0 − * 
 1 0 0 1 * − 0 1 1 * 1 0 1 1 * 1 1 − 0 * 
 1 0 1 1 * 1 0 − 1 * 1 1 0 1 * 1 − 1 1 
 0 1 1 1 * 0 1 − 1 * 1 1 1 0 * 1 1 − 1 * 
 1 1 1 1 * 0 − 1 1 * 1 1 1 1 * 1 1 1 − * 
 1 − 1 1 * 
 − 1 1 1 * 
 151 
 Từ các bảng trên ta có dạng tổng chuẩn tắc thu gọn của F1 và F2 là: 
 F1 wz xz yz 
 F2 wxy xyz wyz wx. 
8.4.2.5. Phương pháp Quine-McCluskey tìm dạng tổng chuẩn tắc tối thiểu 
 Sau khi tìm đƣợc dạng tổng chuẩn tắc thu gọn của hàm Boole F, nghĩa là 
tìm đƣợc tất cả các nguyên nhân nguyên tố của nó, ta tiếp tục phƣơng pháp 
Quine-McCluskey tìm dạng tổng chuẩn tắc tối thiểu (cực tiểu) của F nhƣ sau: 
 Lập một bảng chữ nhật, mỗi cột ứng với một cấu tạo đơn vị của F (mỗi cấu 
tạo đơn vị là một hội sơ cấp hạng n trong dạng tổng chuẩn tắc hoàn toàn của F) 
và mỗi dòng ứng với một nguyên nhân nguyên tố của F. Tại ô (i, j), ta đánh dấu 
cộng (+) nếu nguyên nhân nguyên tố ở dòng i là một phần con của cấu tạo đơn 
vị ở cột j. Ta cũng nói rằng khi đó nguyên nhân nguyên tố i là phủ cấu tạo đơn 
vị j. Một hệ S các nguyên nhân nguyên tố của F đƣợc gọi là phủ hàm F nếu mọi 
cấu tạo đơn vị của F đều đƣợc phủ ít nhất bởi một thành viên của hệ. Dễ thấy 
rằng nếu hệ S là phủ hàm F thì nó là đầy đủ, nghĩa là tổng của các thành viên 
trong S là bằng F. 
 Một nguyên nhân nguyên tố đƣợc gọi là cốt yếu nếu thiếu nó thì một hệ các 
nguyên nhân nguyên tố không thể phủ hàm F. Các nguyên nhân nguyên tố cốt 
yếu đƣợc tìm nhƣ sau: tại những cột chỉ có duy nhất một dấu +, xem dấu + đó 
thuộc dòng nào thì dòng đó ứng với một nguyên nhân nguyên tố cốt yếu. 
 Việc lựa chọn các nguyên nhân nguyên tố trên bảng đã đánh dấu, để đƣợc 
một dạng tổng chuẩn tắc tối thiểu, có thể tiến hành theo các bƣớc sau: 
 - Bƣớc 1: Phát hiện tất cả các nguyên nhân nguyên tố cốt yếu; 
 - Bƣớc 2: Xoá tất cả các cột đƣợc phủ bởi các nguyên nhân nguyên tố cốt yếu; 
 - Bƣớc 3: Trong bảng còn lại, xoá nốt những dòng không còn dấu + và sau 
đó nếu có hai cột giống nhau thì xoá bớt một cột; 
 - Bƣớc 4: Sau các bƣớc trên, tìm một hệ S các nguyên nhân nguyên tố với 
số biến ít nhất phủ các cột còn lại. 
 Tổng của các nguyên nhân nguyên tố cốt yếu và các nguyên nhân nguyên 
tố trong hệ S sẽ là dạng tổng chuẩn tắc tối thiểu của hàm F. 
 Các bƣớc 1, 2, 3 có tác dụng rút gọn bảng trƣớc khi lựa chọn. Độ phức tạp 
chủ yếu nằm ở Bƣớc 4. Tình huống tốt nhất là mọi nguyên nhân nguyên tố đều 
là cốt yếu. Trƣờng hợp này không phải lựa chọn gì và hàm F có duy nhất một 
 152 
dạng tổng chuẩn tắc tối thiểu cũng chính là dạng tổng chuẩn tắc thu gọn. Tình 
huống xấu nhất là không có nguyên nhân nguyên tố nào là cốt yếu. Trƣờng hợp 
này ta phải lựa chọn toàn bộ bảng. 
 Thí dụ 8.10: Tìm dạng tổng chuẩn tắc tối thiểu của các hàm Boole cho 
trong Thí dụ 9. 
 wxyz wxyz wxyz wxyz wxyz wxyz wxyz 
 wz + + + 
 xz + + + + 
 yz + + + + 
 Các nguyên nhân nguyên tố đều là cốt yếu nên dạng tổng chuẩn tắc tối 
thiểu của F1 là: 
 F1 wz xz yz 
 wxyz wxyz wxyz wxyz 
 wx + + + + 
 wxy + + 
 xyz + + 
 wyz + + 
 Các nguyên nhân nguyên tố cốt yếu nằm ở dòng 1 và 2. Sau khi rút gọn, 
bảng còn dòng 3, 4 và một cột 3. Việc chọn S khá đơn giản: có thể chọn một 
trong hai nguyên nhân nguyên tố còn lại. Vì vậy ta đƣợc hai dạng tổng chuẩn tắc 
tối thiểu là: 
 F2 wx wxy xyz 
 F2 wx wxy wyz 
 153 
 BÀI TẬP CHƢƠNG 8 
 1. Cho S là tập hợp các ƣớc nguyên dƣơng của 70, với các phép toán •, + và 
’ đƣợc định nghĩa trên S nhƣ sau: 
 a • b = UCLN(a, b), a + b = BCNN(a, b), a’ = 70/a. 
 Chứng tỏ rằng S cùng với các phép toán •, + và ’ lập thành một đại số Boole. 
 2. Chứng minh trực tiếp các định lý 6b, 7b, 8b (không dùng đối ngẫu để 
suy ra từ 6a, 7a, 8a). 
 3. Chứng minh rằng: 
 a) (a + b).(a + b’) = a; 
 b) (a.b) + (a’.c) = (a + c).(a’ + b). 
 4. Cho các hàm Boole F1, F2, F3 xác định bởi bảng sau: 
 x y z F1 F2 F3 
 0 0 0 1 1 0 
 0 0 1 1 0 1 
 0 1 0 0 1 1 
 0 1 1 1 1 0 
 1 0 0 1 0 1 
 1 0 1 0 0 1 
 1 1 0 0 1 1 
 1 1 1 1 1 1 
 Vẽ mạch thực hiện các hàm Boole này. 
 5. Hãy dùng các cổng NAND để xây dựng các mạch với các đầu ra nhƣ sau: 
 a) x b) xy c) x+y d) x y. 
 6. Hãy dùng các cổng NOR để xây dựng các mạch với các đầu ra đƣợc cho 
trong Bài tập 5. 
 7. Hãy dùng các cổng NAND để dựng mạch cộng bán phần. 
 8. Hãy dùng các cổng NOR để dựng mạch cộng bán phần. 
 9. Dùng các bản đồ Karnaugh, tìm dạng tổng chuẩn tắc tối thiểu (khai triển 
cực tiểu) của các hàm Boole ba biến sau: 
 a) F xyz xyz ; 
 b) F xyz xyz xyz xyz ; 
 154 
 c) F xyz xyz xyz xyz xyz ; 
 d) F xyz xyz xyz xyz xyz xyz . 
 10. Dùng các bản đồ Karnaugh, tìm dạng tổng chuẩn tắc tối thiểu của các 
hàm Boole bốn biến sau: 
 a) F wxyz wxyz wxyz wxyz wxyz ; 
 b) F wxyz wxyz wxyz wxyz wxyz wxyz ; 
 c) F wxyz wxyz wxyz wxyz wxyz wxyz wxyz wxyz ; 
 d) F wxyz wxyz wxyz wxyz wxyz wxyz wxyz wxyz wxyz . 
 11. Dùng phƣơng pháp Quine-McCluskey, tìm dạng tổng chuẩn tắc tối 
thiểu của các hàm Boole ba biến cho trong Bài tập 9 và hãy vẽ mạch thực hiện 
các dạng tối thiểu tìm đƣợc. 
 12. Dùng phƣơng pháp Quine-McCluskey, tìm dạng tổng chuẩn tắc tối 
thiểu của các hàm Boole bốn biến cho trong Bài tập 9 và hãy vẽ mạch thực hiện 
các dạng tối thiểu tìm đƣợc. 
 13. Hãy giải thích làm thế nào có thể dùng các bản đồ Karnaugh để rút gọn 
dạng tích chuẩn tắc (tích các tổng) hoàn toàn của một hàm Boole ba biến (Gợi ý: 
Đánh dấu bằng số 0 tất cả các tuyển sơ cấp trong biểu diễn và tổ hợp các khối 
của các tuyển sơ cấp). 
 14. Dùng phƣơng pháp ở Bài tập 13, hãy rút gọn dạng tích chuẩn tắc 
hoàn toàn: 
 F (x y z)(x y z)(x y z)(x y z) 
 155 
 TÀI LIỆU THAM KHẢO 
1. Nguyễn Cam, Chu Đức Khánh (1999). Lý thuyết đồ thị. Nxb Thành phố Hồ 
Chí Minh. 
2. Hoàng Chúng (1997). Đại cương về toán học hữu hạn. Nxb Giáo dục. 
3. Phan Đình Diệu (1977). Lý thuyết Ô-tô-mat và thuật toán. Nxb Đại học và 
Trung học chuyên nghiệp. 
4. Đỗ Đức Giáo (2000). Toán rời rạc. Nxb Đại học Quốc Gia, Hà Nội. 
5. Nguyễn Xuân Quỳnh (1995). Cơ sở toán rời rạc và ứng dụng. Nxb Giáo dục. 
6. Đặng Huy Ruận (2000). Lý thuyết đồ thị và ứng dụng. Nxb Khoa học và 
Kỹ thuật. 
7. Nguyễn Tô Thành, Nguyễn Đức Nghĩa (1997). Toán rời rạc. Nxb Giáo dục. 
8. Claude Berge (1963). Théorie des graphes et ses applications. Dunod, Paris. 
9. Richard Johnsonbaugh (1992). Discrete Mathematics. Macmillan Publishing 
Company, New york. 
 156