›
›

Tóm tắt bài giảng Toán rời rạc - Nguyễn Ngọc Trung

pdf 51 trang ngocly 3240
Download
Bạn đang xem 20 trang mẫu của tài liệu "Tóm tắt bài giảng Toán rời rạc - Nguyễn Ngọc Trung", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdftom_tat_bai_giang_toan_roi_rac_nguyen_ngoc_trung.pdf

Nội dung text: Tóm tắt bài giảng Toán rời rạc - Nguyễn Ngọc Trung

  1. TRƯỜNG ĐẠI HỌC SƯ PHẠM TP.HCM KHOA TOÁN – TIN HỌC TÓM TẮT BÀI GIẢNG Môn TOÁN RỜIRẠC Giảng viên biên soạn: Nguyễn Ngọc Trung TP.HCM 9.2006
  2. MỤC LỤC Chương 1. Mệnh đề 3 1.1 Mệnh đề - Tính chất 3 1.1.1 Mệnh đề và các phép toán mệnh đề 3 1.1.2 Dạng mệnh đề 5 1.1.3 Các quy tắc suy diễn 7 1.2 Vị từ - Lượng từ 11 1.3 Nguyên lý quy nạp 14 Chương 2. Phép đếm 15 2.1 Tập hợp – Tính chất 15 2.2 Ánh xạ 17 2.3 Giải tích tổ hợp 18 2.3.1 Các nguyên lý cơ bản của phép đếm: 18 2.3.2 Giải tích tổ hợp 19 2.3.3 Nguyên lý Dirichlet. (nguyên lý chuồng bồ câu) 23 Chương 3. Quan hệ 24 3.1 Quan hệ 24 3.2 Quan hệ tương đương 25 3.3 Quan hệ thứ tự - Biểu đồ Hasse 26 Chương 4. Đại số Boole 30 4.1 Đại số Boole: Định nghĩa – Tính chất 30 4.2 Hàm Boole – Dạng nối rời chính tắc 36 4.3 Bài toán mạch điện –Mạng các cổng 42 4.4 Tìm công thức đa thức tối tiểu – Phương pháp Karnaugh 44 TÀI LIỆU THAM KHẢO 51
  3. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 1 Chương 1. Mệnh đề 1.1 Mệnh đề - Tính chất 1.1.1 Mệnh đề và các phép toán mệnh đề Định nghĩa. Mệnh đề là các khẳng định có giá trị chân lý xác định (đúng hoặc sai, nhưng không thể vừa đúng, vừa sai). Các mệnh đề đúng được nói là có chân trị đúng, các mệnh đề sai được nói là có chân trị sai. Ví dụ: - Các khẳng định sau là mệnh đề: . “1 + 2 = 5” là mệnh đề sai. . “10 là số chẵn” là mệnh đề đúng. - Các khẳng định sau không phải là mệnh đề: . “Tôi đi học” . “n là số nguyên tố” Ký hiệu: Ta thường ký hiệu các mệnh đề bằng các chữ cái in hoa: P, Q, R, và chân trị đúng (sai) được ký hiệu bởi 1 (0). Các phép toán mệnh đề: Phép phủ định: phủ định của mệnh đề P được ý hiệu bởi P (đọc là “không P” hoặc “phủ định của P”. Chân trị của P là 0 nếu chân trị của P là một và ngược lại. VD. P = “3 là số nguyên tố” là mệnh đề đúng. Do đó mệnh đề P = “3 không là số nguyên tố là mệnh đề sai. Bảng sau gọi là bảng chân trị của phép phủ định: P P 0 1 1 0 Phép nối liền: Mệnh đề nối liến của hai mệnh đề P và Q được ký hiệu bởi PQ (đọc là “P và Q”. Chân trị của PQ là 1 nếu cả P lẫn Q đều có chân trị là 1, trong các trường hợp khác PQ có chân trị là 0. VD. P = “Hôm nay trời đẹp” và Q = “Trận bóng đá hấp dẫn”. Khi đó ta có mệnh đề nối liền của P và Q là: PQ = “Hôm nay trời đẹp và trận bóng đá hấp dẫn”. Mệnh đề nối liền này sẽ đúng nếu như cả hai mệnh đề P và Q đều Trang 3
  4. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM đúng. Ngược lại nếu có một trong hai mệnh đề trên sai hoặc cả hai cùng sai thì mệnh đề nồi liền sẽ là sai. Bảng chân trị của phép nối liền: P Q PQ 0 0 0 0 1 0 1 0 0 1 1 1 Phép nối rời: Mệnh đề nối rời của hai mệnh đề P và Q được ký hiệu bởi PQ (đọc là “P hay Q”. Chân trị của PQ là 0 nếu cả P lẫn Q đều có chân trị là 0, trong các trường hợp khác PQ có chân trị là 0. VD. P = “An là ca sĩ”, P = “An là giáo viên”. Khi đó ta có mệnh đề nối rời của P và Q là PQ = “An là ca sĩ hay An là giáo viên”. Mệnh đề nối liền này sẽ đúng nếu như một trong hai mệnh đề trên là đúng hoặc cả hai mệnh đề trên đều đúng. Nếu cả hai mệnh đề P và Q đều sai thì PQ sẽ sai. Bảng chân trị của phép nối rời: P Q PQ 0 0 0 0 1 1 1 0 1 1 1 1 Phép kéo theo: Mệnh đề P kéo theo Q được ký hiệu là P Q . Để xác định chân trị của mệnh đề P kéo theo Q ta xét ví dụ sau: P = “An trúng số”, Q = “An mua xe máy”, khi đó mệnh đề P kép theo Q sẽ là “Nếu An trúng số thì An sẽ mua xe máy”. Ta có các trường hợp sau đây: . An đã trúng số và anh ta mua xe máy: hiển nhiên mệnh đề P Q là đúng. . An đã trúng số nhưng anh ta không mua xe máy: rõ ràng mệnh đề P Q là sai. . An không trúng số nhưng anh ta vẫn mua xe máy: mệnh đề P Q vẫn đúng. . An không trúng số và anh ta không mua xe máy: mệnh đề P Q đúng. Trang 4
  5. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Bảng chân trị của phép kéo theo: P Q P Q 0 0 1 0 1 1 1 0 0 1 1 1 Phép kéo theo hai chiều: Mệnh đề P kéo theo Q và ngược lại được ký hiệu bởi P  Q là mệnh đề có chân trị đúng khi P và Q có chân trị giống nhau (cùng đúng hoặc cùng sai) và có chân trị sai khi P và Q có chân trị khác nhau. VD. P = “An học giỏi”, Q = “An được điểm cao”. Khi đó mệnh đề P  Q = “Nếu An học giỏi thì An sẽ được điểm cao và ngược lại”. Bảng chân trị của phép kéo theo hai chiều như sau: P Q P  Q 0 0 1 0 1 0 1 0 0 1 1 1 1.1.2 Dạng mệnh đề Định nghĩa. Dạng mệnh đề được xây dựng từ: - Các mệnh đề (là các hằng mệnh đề) - Các biến mệnh đề p, q, r, có thể lấy giá trị là các mệnh đề nào đó. - Các phép toán trên mệnh đề, và các dấu ngoặc ( ). Ví dụ. E(,,) p q r p q  r p là một dạng mệnh đề trong đó p, q, r là các biến mệnh đề. Để ý rằng ta có thể xây dựng nhiều dạng mệnh đề phức tạp từ các dạng mệnh đề đơn giản hơn bằng cách sử dụng các phép toán mệnh đề để kết hợp chúng lại. Chẳng hạn như dạng mệnh đề E(p,q,r) ở trên được kết nối từ hai dạng mệnh đề E1(,,) p q r p q và E2 (,,) p q r r p bằng phép toán nối rời (  ). Mỗi dạng mệnh đề sẽ được sẽ có một bảng chân trị xác định trong đó mỗi dòng cho biết chân trị của dạng mệnh đề đó theo các chân trị cụ thể của các biến. Trang 5
  6. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Ví dụ. E(,,) p q r p q  r p có bảng chân trị như sau: p q r r p q r p E(p,q,r) 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 Định nghĩa. Hai dạng mệnh đề E và F được nói là tương đương logic nếu chúng có cùng bảng chân trị. Khi ấy ta viết E F . Chú ý rằng nếu E và F tương đương logic thì dạng mệnh đề P  Q luôn lấy giá trị là 1 dù các biến có lấy bất cứ giá trị nào. Định nghĩa. i. Một dạng mệnh đề được gọi là một hằng đúng nếu nó luôn luôn lấy chân trị 1 ii. Một dạng mệnh đề được gọi là một hằng sai nếu nó luôn lấy chân trị 0. Mệnh đề. Hai dạng mệnh đề E và F tương đương logic khi và chỉ khi P  Q là một hằng đúng. Định nghĩa. Dạng mệnh đề F được nói là hệ quả logic của dạng mệnh đề E nếu E F là một hằng đúng. Khi ấy ta viết E F . Các quy luật logic: Định lý. Với p, q, r là các biến mệnh đề, 1 là hằng đúng, 0 là hằng sai, ta có các tương đương logic: i. Phủ định của phủ định: p p ii. Quy tắc De Morgan:  p q p  q và  p q p  q iii. Luật kéo theo: p q p  q iv. Luật giao hoán: p q q  p Trang 6
  7. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM và p q q  p v. Luật phân phối: p  q r p q  p r và p  q r p q  p r vi. Luật kết hợp: p  q r p q  r và p  q r p q  r vii. Luật lũy đẳng: p  p p và p  p p viii. Luật trung hòa: p 1 p và p 0 p ix. Phần tử bù: p  p 0 và p  p 1 x. Luật thống trị: p 0 0 và p 1 1 xi. Luật hấp thụ: p  p q p và p  p q p Ví dụ. sử dụng các quy luật logic chứng minh rằng dạng mệnh đề E(,) p q p  p q q là hằng đúng. Giải. E(p,q) p  p  q q p  p  p q 0  p q q p q q p  q  q p 1 1 1.1.3 Các quy tắc suy diễn Trong chứng minh toán học, xuất phát từ một số khẳng định đúng (mệnh đề đúng) gọi là tiền đề, ta sẽ áp dụng các quy tắc suy diễn để suy ra chân lý của một khẳng định q mà ta gọi là kết luận. Nói cách khác, ta sẽ phải tìm cách chứng minh dạng mệnh đề p1  p2  pn q là một hằng đúng, trong đó p1, p2 , , pn , q là các dạng mệnh đề theo một số biến logic nào đó. Trang 7
  8. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Ví dụ. Giả sử ta có các tiền đề: p1: “Nếu An học chăm thì An đạt điểm cao” p2: “Nêu An không hay đi chơi thì An học chăm” p3: “An không được điểm cao” Ta muốn dùng các quy tắc suy diễn để suy ra kết luận: q = “An hay đi chơi”. Muốn vậy, ta phải trừu tượng hóa các mệnh đề nguyên thủy: “An học chăm”, “An hay đi chơi” và “An được điểm cao” thành các biến mệnh đề p, q, r. Như vậy các tiền đề bây giờ trở thành các dạng mệnh đề: p1 p r p2 q p p3 r Ta phải chứng minh dạng mệnh đề sau là một hằng đúng: p r  q p  r q Ta có thể chứng minh điều này bằng cách lập bảng chân trị của dạng mệnh đề trên. Tuy nhiên cách này sẽ gặp rất nhiều khó khăn khi các biến mệnh đề lớn (số dòng của bảng chân trị bằng 2n, với n là số biến mệnh đề). Một phương pháp khác là sử dụng các quy tắc suy diễn để chia bài toán ra thành nhiều bước nhỏ, nghĩa là từ các tiền đề ta suy ra một số kết luận trung gian trước khi áp dụng các quy tắc suy diễn để suy ra kết luận. Để tiện ta mô hình hóa phép suy diễn thành sơ đồ như sau: p1 p2  pn q Sau đây là một số quy tắc suy diễn thường dùng mà chân lý của nó có thể được kiểm tra dễ dàng bằng cách lập bảng chân trị.  Quy tắc Modus Ponens (Phương pháp khẳng định): Quy tắc này được thể hiện bởi hằng đúng: p q  p q hoặc dưới dạng sơ đồ: p q p q Ví dụ. Nếu An học chăm thì An sẽ được điểm cao, mà An học chăm. Suy ra An được điểm cao. Trang 8
  9. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM  Tam đoạn luận (Syllogism). Quy tắc này được thể hiện bằng hằng đúng: p q  q r p r hay dưới dạng mô hình: p q q r p r Ví dụ. Nếu An không hay đi chơi thì An học chăm và nếu An học chăm thì An sẽ được điểm cao. Suy ra nếu An không hay đi chơi thì An sẽ được điểm cao.  Quy tắc Modus Tollens (phương pháp phủ định) Quy tắc này được thể hiện bởi hằng đúng: p q  q p hay dưới dạng mô hình: p q q p Ví dụ. Nếu trời mưa thì đường ướt mà đường không ướt. Suy ra trời không mưa.  Quy tắc mâu thuẫn (chứng minh bằng phản chứng) Quy tắc này dựa trên tương đương logic sau: p1  p2  pn q p1  p2  pn  q 0 Ví dụ. Hãy sử dụng phương pháp phản chứng cho chứng minh sau: p r p q q s r s - Trước hết, ta lấy phủ định của kết luận:  r s  r  s r  s - Sau đó ta sẽ thêm vào các tiền đề hai giả thiết phụ r và s tìm cách chứng minh suy luận sau là đúng: Trang 9
  10. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM p r p q q s r s 0 Các bước suy luận sẽ được thực hiện như sau: p q q s p s (Tam đoạn luận) mà s p (PP phủ định) mà p r r (PP khẳng định) Kết luận r cùng với giả thiết phụ r cho ta r  r 0 . Do đó theo phương pháp phản chứng, chứng minh ban đầu là đúng.  Quy tắc chứng minh theo trường hợp: Quy tắc này được thể hiện bằng hằng đúng sau: p r  q r p q r Ý nghĩa của quy tắc này là nếu một giả thiết có thể tác ra thành hai trường hợp p đúng hay q đúng, và ta đã chứng minh được riêng rẽ cho từng trường hợp là kết luận r đúng, khi ấy r cũng đúng trong cả hai trường hợp. Ví dụ. Để chứng minh rằng f(n) = n(n+1) luôn chia hết cho 2 với mọi số tự nhiên n, ta xét hai trường hợp là n chẵn, n lẻ và thấy rằng trong cả hai trường hợp f(n) luôn chia hết cho 2. Vậy ta rút ra kết luận cần chứng minh là f(n) luôn chia hết cho 2 với mọi số tự nhiên n. Trên đây là một số quy tắc suy diễn ta thường dùng trong các quá trình suy luận. Sau đây ta sẽ xét một ví dụ cụ thể có sử dụng kết hợp nhiều quy tắc suy diễn: Ví dụ. Kiểm tra suy luận sau đúng hay sai: “Nếu nghệ sĩ Văn Ba không trình diễn hay số vé bán ra ít hơn 50 vé thì đêm diễn sẽ bị hủy bỏ và Ông bầu sẽ rất buồn. Nếu đêm diễn bị hủy bỏ thì phải trả lại vé cho người xem. Nhưng tiền vé đã không được trả lại cho người xem. Vậy nghệ sĩ Văn Ba đã trình diễn”. Để kiểm tra suy luận trên, ta thay các mệnh đề nguyên thủy bằng các biến mệnh đề: p: “nghệ sĩ Văn Ba đã trình diễn” Trang 10
  11. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM q: “số vé bán ra ít hơn 50 vé” r: “đêm diễn bị hủy bỏ” s: “ông Bầu rất buồn” t: “trả tiền vé lại cho người xem” Từ đó, suy luận ban đầu có thể mô hình như sau: p  q r  s r t t  p Suy luận trên có thể được thực hiện theo các bước sau: p  q r  s ( tiền đề) r  s r (hằng đúng) r t (tiền đề)  p  q t (tam đoạn luận mở rộng) mà t (tiền đề) p  q (phương pháp phủ định và luật De Morgan) mà p  q p (hằng đúng)  p (phương pháp khẳng định) Vậy suy luận ban đầu là chính xác. 1.2 Vị từ - Lượng từ Định nghĩa. Một vị từ là một khẳng định p(x,y, ) trong đó có chứa một số biến x,y, lấy giá trị trong những tập hợp cho trước A, B, sao cho: i. Bản thân p(x,y, ) không phải là mệnh đề ii. Nếu thay x, y, bằng những a A , b B , ta sẽ được một mệnh đề p(a,b, ) nghĩa là chân trị của nó hoàn toàn xác định. Các biến x, y, được nói là biến tự do của vị từ. Ví dụ. a. p(n) = “n là số nguyên tố” là một vị từ theo biến tự do n , với n = 2, 11, 13 ta được các mệnh đề đúng p(2), p(11), p(13) còn với n = 4, 10, 20 ta được các mệnh đề sai p(4), p(10), p(20). b. q(x,y) = “x + y là số lẻ” là vị từ theo 2 biến tự do x, y , chẳng hạn q(2,5) là một mệnh đề đúng, q(-3, -7) là một mệnh đề sai, Trang 11
  12. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Định nghĩa. Cho trước các vị từ p(x), q(x) theo một biến x A. Khi đó: i. Phủ định của p, ký hiệu là p là vị từ theo biến x mà khi thay x bằng một phần tử a cố định của A thì ta được mệnh đề  p a . ii. Phéo nối liền (tương ứng nối rời, kéo theo, ) của p và q, ký hiệu bởi p q ( p q , p q , ) là vị từ theo biến x mà khi thay x bằng một phần tử a cố định của A thì ta được mệnh đề p a  q a p() a  q( a ), p ( a ) q( a ), Ví dụ: p(x) = “x là số nguyên tố”, q(x) = “x là số chẵn”. Khi đó ta có: . Phủ định của p: p() x = “x không là số nguyên tố” . Phép nối liền của p và q: p q() x = “x là số nguyên tố va x là số chẵn” . . . . Định nghĩa. Các mệnh đề “ x A,() p x ” và “ x A,() p x ” được gọi là lượng từ hóa của vị từ p(x) bởi lượng từ phổ dụng ( ) và lượng từ tồn tại (  ). Chú ý: a. Trong các mệnh đề lượng từ hóa, biến x không còn là biến tự do nữa, ta nói nó bị buộc bởi các lượng từ  hay  . b. Mệnh đề x A,() p x sẽ đúng nếu thay x bằng giá trị a bất kỳ nhưng cố định trong A, p(a) luôn là mệnh đề đúng. c. Mệnh đề x A,() p x sẽ đúng nếu có một giá trị a trong A sao cho p(a) là mệnh đề đúng. Xét một vị từ p(x,y) theo hai biến x A, y B . Khi ấy nếu thay x bằng một phần tử cố định nhưng tùy ý a A , ta sẽ được một vị từ p(a,y) theo biến y. Khi đó ta có thể lượng từ hóa nó theo biến y và được hai mệnh đề sau: “ y B,(,) p a y ” và “ y B,(,) p a y ”. Do x được thay bằng một phần tử cố định nhưng tùy ý a của A, nên ta có hai vị từ sau đây là hai vị từ theo biến x A: “ y B,(,) p x y ” và “ y B,(,) p x y ”. Tiếp tục lượng từ hóa hai vị từ trên theo biến x, ta được 4 mệnh đề sau đây: x A, y B, p(,) x y x A, y B, p(,) x y x A, y B, p(,) x y x A, y B, p(,) x y Tương tự ta cũng có thể lượng từ hóa p(x,y) theo biến x trước rồi biến y sau để được 4 mệnh đề nữa: y B, x A, p(,) x y y B, x A, p(,) x y y B, x A, p(,) x y y B, x A, p(,) x y Trang 12
  13. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Câu hỏi đặt ra lúc này là liệu thứ tự lượng từ hóa có quan trọng hay không? Nói cách khác, các mệnh đề tương ứng có tương đương logic với nhau không? Định lý sau sẽ đề cập đến vấn đề này Định lý. Nếu p(x,y) là một vị từ theo 2 biến x, y thì ta có các điều sau: i. x A, y B, p(,) x y y B, x A, p(,) x y ii. x A, y B, p(,) x y y B, x A, p(,) x y iii. x A, y B, p(,) x y y B, x A, p(,) x y Chứng minh. Xem tài liệu tham khảo [1]. Cũng tương tự cách làm như trên, ta có thể mở rộng dễ dàng cho các vị từ theo nhiều biến tự do. Đặc biệt, ta có: Mệnh đề. Trong một mệnh đề lượng từ hóa từ một vị từ theo nhiều biến độc lập, nếu ta hoán vị hai lượng từ đứng cạnh nhau thì: i. Mệnh đề mới vẫn còn tương đương logic với mệnh đề cũ nếu hai lượng từ này cùng loại. ii. Mệnh đề mới sẽ là hệ quả logic của mệnh đề cũ nếu hai lượng từ trước khi hoán vị có dạng  Định lý sau sẽ cho chúng ta biết cách lấy phủ định của một mệnh đề lượng từ hóa: Định lý. Phủ định của một mệnh đề lượng từ hóa từ vị từ p(x,y, ) có được bằng cách thay lượng từ  bởi lượng từ  , thay lượng từ  bằng lượng từ  và thay vị từ p(x,y, ) bằng phủ định  p(x,y, ). Ví dụ. Phủ định của mệnh đề “x ,y , x + y là số chẵn” là mệnh đề “ x ,y , x+y không là số chẵn”. Quy tắc đặc biệt hóa phổ dụng: “Nếu một mệnh đề đúng có dạng lượng từ hóa, trong đó một biến x A bị buộc bởi lượng từ phổ dụng  , khi đó nếu thay x bằng a A ta sẽ được một mệnh đề đúng”. Ví dụ. Ta có mệnh đề đúng sau: “n ,(n n 1) 2 ”, khi đó nếu thay n bằng số tự nhiên bất kỳ, chẳng hạn n = 5, không cần kiểm tra lại, ta cũng chắc chắn rằng mệnh đề “5*(5+1)2” là mệnh đề đúng. Trang 13
  14. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 1.3 Nguyên lý quy nạp Nguyên lý quy nạp: Mệnh đề “ n ,()p n ” là hệ quả logic của “ p(0)  n ,()p n p( n 1)” Nguyên lý quy nạp được cụ thể hóa thành phương pháp chứng minh quy nạp như sau: Giả sử ta phải chứng minh mệnh đề: n ,()p n , khi đó ta sẽ thực hiện các bước sau: Bước 1. Kiểm tra p(0) là mệnh đề đúng (trong thực tế, ta có thể bắt đầu bằng giá trị nhỏ nhất có thể được của n, không nhất thiết phải bắt đầu từ 0) Bước 2. Với n bất kỳ, giả sử p(n) là mệnh đề đúng, ta sẽ phải chứng minh p(n+1) cũng là mệnh đề đúng. n( n 1) Ví dụ. Để chứng minh n , 0 1 n ,ta xét vị từ p(n) = 2 n( n 1) “ 0 1 n ”. Ta có: 2 0.1 . p(0) = “ 0 ”, đây rõ ràng là một mệnh đề đúng. 2 . Xét n là số tự nhiên bất kỳ, giả sử p(n) là mệnh đề đúng, nghĩa là ta có: n( n 1) 0 1 n 2 ta sẽ chứng minh p(n+1) cũng đúng. Thật vậy, ta có: n( n 1) n 1  (n 1) 1 0 1 n (n 1) (n 1) 2 2 suy ra p(n+1) là mệnh đề đúng. Theo nguyên lý quy nạp ta có điều phải chứng minh. Trang 14
  15. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 2 Chương 2. Phép đếm 2.1 Tập hợp – Tính chất Trong chương trước, chúng ta đã một vài lần sử dụng khái niệm tập hợp trong một số ví dụ, đặc biệt là trong định nghĩa của các lượng từ. Trong chương này ta sẽ nói rõ hơn về khái niệm này. Trong toán học, tập hợp là một khái niệm cơ bản, không thể định nghĩa thông qua các đối tượng khác được. Một cách trực quan, tập hợp là một khái niệm để chỉ các đối tượng được nhóm lại theo một tính chất nào đó. Nếu a là đối tượng của tập hợp A, ta viết a A , nếu không, ta viết a A . Để ý rằng từ “tính chất” được hiểu theo một nghĩa rộng rãi. Thông thường nó sẽ được biểu hiện bởi một vị từ p(x) theo một biến x U . Khi ấy tập hợp được ký hiệu bởi: A x U p() x  U được gọi là tập vũ trụ. Ví dụ. 1. A x x 2 , đây là tập hợp các số tự nhiên chẵn. 2 2. A x x 5 , đây là tập hợp các số nguyên có bình phương nhỏ hơn 5. Tập hợp còn có thể được biểu diễn bằng cách liệt kê các phần tử của nó. Chẳng hạn như tập hợp trong mục 2 của ví dụ trên có thể được viết là: A = {-2,-1,0,1,2}. Tập hợp không chứa bất cứ phần tử nào gọi là tập hợp rỗng và được ký hiệu là  . Xét hai tập hợp A và B trong tập vũ trụ U. Ta nói A là tập hợp con của B (hay A chứa trong B) nếu: x U, x A x B . Ta có thể hiểu đơn giản là bất cứ phần tử nào nằm trong A cũng nằm trong B. Ta có thể sử dụng các phép toán trên mệnh đề và vị từ để định nghĩa các phép toán trên tập hợp như phép hợp (  ), phép giao ( ) và phần bù theo định nghĩa sau đây: Định nghĩa. Giả sử A, B là hai tập hợp con của tập hợp vũ trụ U. Khi ấy: A B x U( x A)( x B) AB x U( x A)( x B) A x U x A Trang 15
  16. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Định lý sau sẽ giới thiệu các tính chất của các phép toán trên tập hợp: Định lý. A, B, C là các tập con tùy ý của U, ta có: i. Tính giao hoán: A BB=  A A B B  A ii. Tính kết hợp: A B C A B C A B C A B C iii. Luật De Morgan: A B A  B A B A  B iv. Tính phân phối: A B C A B  AC A B C A B  AC v. Phần tử trung hòa: A A AU A vi. Phần bù: A AU A A  vii. Tính thống trị: AU U A  viii. Tính lũy đẳng: A A A A A A ix. Luật hấp thụ: A A B A A A B A Chứng minh. Các tính chất trên được suy ra từ định nghĩa và các quy luật logic. Chú ý. Ta có thể lấy hợp hoặc giao của nhiều tập hợp và ký hiệu như sau: n Ai A1  A2   An i 1 n và Ai A1  A2   An i 1 Trang 16
  17. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 2.2 Ánh xạ Định nghĩa. i. Một ánh xạ f từ tập hợp A vào tập hợp B là phép tương ứng liên kết mỗi phần tử x của A với một phần tử duy nhất y của B mà ta ký kiệu là f(x) và gọi là ảnh của x bởi f. Ta viết: f: A B x f() x ii. Hai ánh xạ f và g từ A vào B được nói là bằng nhau nếu: x A,() f x g() x Định nghĩa. i. Nếu E là một tập hợp con của A thì ảnh của E bởi f là tập hợp: f() E y B x A, y f() x  f() x x E ii. Nếu F là một tập hợp con của B thì ảnh ngược của F qua ánh xạ f là tập hợp: f 1()F x A f() x F Chú ý: 1. Nếu y B ta viết f 1 y f 1()y 2. Nếu f 1()y  thì y không nằm trong ảnh f(A) của A. 3. Nếu f 1(y ) {x} thì x là phần tử duy nhất có ảnh là y. Định nghĩa. Gọi f là một ánh xạ từ tập A và tập B. Khi ấy ta nói: i. f là toàn ánh nếu f(A)=B ii. f là đơn ánh nếu hai phần tử khác nhau bất kỳ của A có ảnh khác nhau, nghĩa là: x,' x A, x x ' f() x f( x ') iii. f là song ánh nếu nó vừa đơn ánh vừa toán ánh. Xét f là một song ánh từ A lên B, khi đó với mỗi y B tùy ý, sẽ có duy nhất một phần tử x Asao cho f(x)=y. Như thế, tương ứng y x là một ánh xạ từ B vào A mà ta ký hiệu là f 1 và gọi là ánh xạ ngược của ánh xạ f. Ta có: f 1()y x f() x y . Ta có tính chất của ánh xạ ngược như sau: f( f 1(y )) y, y B f 1(f ( x )) x, x A Định nghĩa. Cho hai ánh xạ: f: A B và g:' B C , trong đó B  B ' . Ánh xạ hợp h là ánh xạ từ A vào C được xác định bởi: Trang 17
  18. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM h: A C x h() x g( f ( x )) Ta ký hiệu: h f g . Các tính chất của ánh xạ: Định lý. Cho f là một ánh xạ từ tập A vào tập B, E1 và E2 là hai tập con tùy ý của A, F1 và F2 là hai tập con tùy ý của B. Ta có: i. f( E1  E2 ) f() E1  f( E2 ) ii. f( E1  E2 )  f() E1  f( E2 ) 1 1 iii. f (F1  F2 ) f ()F1  f() F2 1 1 iv. f (F1  F2 ) f ()F1  f() F2 2.3 Giải tích tổ hợp Phép đếm các phần tử của một tập hợp A chính là tìm một song ánh giữa A và một tập con {1,2, ,n} của N. Nếu A hữu hạn thì n chính là số phần tử của nó. Định nghĩa sau đây sẽ đề cập đến vấn đề này: Định nghĩa. i. Một tập hợp A được nói là hữu hạn và có n phần tử nếu tồn tại một song ánh giữa A và tập hợp con {1,2, ,n} của N. Khi đó ta viết A n . ii. Nếu A không hữu hạn, ta nói A vô hạn. 2.3.1 Các nguyên lý cơ bản của phép đếm: Nguyên lý cộng: Nếu một công việc có thể được thực hiện bằng một trong n cách loại trừ lẫn nhau: k1, k2, , kn. Trong đó để thực hiện theo cách ki lại có ti phương án khác nhau (i=1 n). Khi đó tổng số phương án để thực hiện công việc ban đầu là: t1 + t2 + + tn. Ví dụ: Để đi từ Tp.HCM ra Hà Nội có 3 cách: đi ôtô, đi tàu hỏa hoặc đi máy bay. Đi bằng ôtô có 3 cách: đi taxi, đi xe đò, thuê xe riêng. Đi bằng tàu hỏa có 2 cách: đi bằng tàu nhanh và đi bằng tàu bình thường. Đi bằng máy bay cũng có hai cách: đi bằng Vietnam airline hoặc đi bằng Pacific airline. Như vậy tổng cộng có 3 + 2 + 2 = 7 cách đi từ Tp.HCM ra Hà Nội. Trang 18
  19. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Nguyên lý cộng mở rộng: i. Cho A và B là hai tập hợp bất kỳ, khi đó ta có: A B A B A B ii. Cho A1, A2, , An là n tập hợp bất kỳ. Ta có: n 1 A1  A2   An N1 N2 ( 1) Nn trong đó Nk là tổng số phần tử của các tất cả các phần giao của k tập bất kỳ trong số n tập ban đầu. Ví dụ. Với 3 tập A, B, C (n=3) theo nguyên lý cộng tổng quát ta có công thức sau: AB C A B C A B B C C  A AB C Nguyên lý nhân: Nếu một công việc phải thực hiện được theo n giai đoạn liên tiếp nhau: k1, k2, , kn. Mỗi giai đoạn ki có ti cách để thực hiện. Như vậy sẽ có t1.t2 tn cách khác nhau để thực hiện công việc ban đầu. Ví dụ. Một người có 3 cái áo sơ-mi khác nhau, 2 cái quần dài khác nhau và 4 đôi giày khác nhau. Như vậy có tất cả 3.2.4 = 24 bộ trang phục khác nhau để người này lựa chọn khi mặc. Định nghĩa. Tích Đề-các của 2 tập hợp A, B ký hiệu là AB là tập hợp tất cả các cặp thứ tự (a,b) với a A và b B trong đó hai cặp (a,b) và (a’,b’) được nói là bằng nhau nếu và chỉ nếu a=a’ và b=b’. Định lý. Nếu A và B là hai tập hợp hữu hạn thì AB cũng là tập hợp hữu hạn và ta có: AB AB. 2.3.2 Giải tích tổ hợp Hoán vị. Định nghĩa. Cho n vật khác nhau. Một hoán vị của n vật này là một cách sắp xếp chúng theo một cách nào đó. Mệnh đề. Số các hoán vị của n vật khác nhau là: Pn n! 1.2.3 n . Chứng minh. Ta chứng minh công thức này dựa trên nguyên lý nhân. Xét công việc xây dựng một hoán vị của n vật ban đầu. Công việc này được chia thành các bước sau: - Bước 1: Chọn vật đứng đầu: có n cách chọn (n vật đều có thể đứng đầu) - Bước 2: Chọn vật đứng thứ hai: có n-1 cách chọn (do đã chọn vật đứng đầu nên bây giờ ta chỉ còn n-1 vật ) - Trang 19
  20. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM - Bước n: Chọn vật còn lại cuối cùng: chỉ có 1 cách duy nhất. Như vậy theo nguyên lý nhân, số cách xây dựng hoán vị, cũng chính là số các hoán vị của n vật ban đầu là n.(n-1) 2.1 = n!. Ví dụ. Số các số tự nhiên có 5 chữ số khác nhau được tạo từ các chữ số 1, 2, 3, 4, 5 là 5! = 120 cách. Hoán vị lặp Hoán vị lặp cũng mang ý nghĩa như hoán vị, điều khác biệt ở đây là trong n vật ban đầu có nhiều vật giống nhau. Mệnh đề sau đây sẽ cho chúng ta biết công thức để tính hoán vị lặp. Mệnh đề. Cho n vật, trong đó có t1 vật loại 1 giống nhau, t2 vật loại 2 giống nhau, , tk vật loại k giống nhau. Khi đó, số các hoán vị khác nhau của n vật ban đầu là n! . t1 ! t2 ! tk ! Chứng minh. Đầu tiên, nếu xem như n vật là khác nhau, ta có n! hoán vị. Tuy nhiên do có t1 vật loại 1 giống nhau, nên ứng với một hoán vị ban đầu, nếu ta hoán vị t1 phần tử này (có t1! hoán vị như vậy) ta vẫn được hoán vị đó. Chính vì vậy thực chất t1! hoán vị kiểu này chỉ là một hoán vị. Do đó, số hoán vị thực sự khác nhau n! nếu có t1 vật loại 1 giống nhau chỉ còn là: . Tiếp theo ta lại có t2 phần tử loại 2 t1 ! n! giống nhau, nên số hoán vị thực sự khác nhau bây giờ sẽ là . Cứ tiếp tục như t1 !! t2 vậy cho đến khi kết thúc, ta sẽ được công thức cần chứng minh trong mệnh đề. Ví dụ: Số các số tự nhiên có 6 chữ số, trong đó bắt buộc phải có 3 chữ số 1, 2 chữ 6! số 2 và 1 chữ số 3 là: 60 . 3!2!1! Chỉnh hợp Định nghĩa. Cho n vật khác nhau. Một chỉnh hợp chập k của n vật này là một cách chọn k vật khác nhau có kể đến thứ tự trong số n vật đó. n! Mệnh đề. Số chỉnh hợp chập k của n vật khác nhau là: Ak n (n k)! Chứng minh. Dùng nguyên lý nhân. Trang 20
  21. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Ví dụ. Trong một lớp học có 20 thành viên. Số cách chọn ra một ban cán sự lớp gồm 3 người, trong đó có một lớp trưởng, một lớp phó và một thủ quỹ là: 20! A3 6840. 20 (20 3)! Chỉnh hợp lặp Trong phần trên, ta đã xét số cách chọn k vật từ n vật khác nhau ban đầu. Nếu ta được phép chọn trong số k phần tử đó, có nhiều phần tử giống nhau (nghĩa là một vật có thể được chọn nhiều lần) thì kết quả sẽ thay đổi như thế nào? Mệnh đề sau đây sẽ đề cập đến yếu tố này. Mệnh đề. Số cách chọn k vật từ n vật khác nhau ban đầu trong đó một vật có thể được chọn nhiều lần (lặp) là: nk. Chứng minh. Sử dụng nguyên lý nhân. Ví dụ. Có bao nhiêu số tự nhiên có 5 chứ số được xây dựng từ 3 chữ số 1, 2, 3, trong đó các chữ số có thể xuất hiện nhiều lần trong cùng một số? Câu trả lời trong trường hợp này là 35 = 243 số tự nhiên như vậy. Tổ hợp Định nghĩa. Cho n vật khác nhau. Một tổ hợp chập k của n vật này là một cách chọn k vật khác nhau không kể đến thứ tự trong số n vật đó. n! Mệnh đề. Số tổ hợp chập k của n vật khác nhau là: C k n k!( n k)! Chứng minh. Dễ thấy rằng sự khác nhau giữa tổ hợp và chỉnh hợp chỉ là vấn đề có xét đến hay không thứ tự của k vật được chọn. Đối với tổ hợp, ta không xét đến yếu tố thứ tự, điều đó có nghĩa là nếu hoán vị k vật được chọn một cách tùy ý, tổ hợp Ak của chúng ta ban đầu cũng không thay đổi. Do đó, ta có công thức: C k n . Và ta n k! dễ dàng có được công thức của số tổ hợp. Ví dụ. Trong một lớp học có 20 học sinh. Có bao nhiêu cách chọn ra một đội văn 20! nghệ gồm 5 người? Câu trả lời là: C 5 15504 . 20 5!15! Tổ hợp lặp Xét bài toán sau đây: “Có bao nhiêu cách cho 4 cái bánh giống nhau vào trong 3 cái hộp khác nhau mà không có ràng buộc nào”. Trang 21
  22. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Đối với bài toán này, điều gây cho chúng ta khó khăn chính là việc những cái bánh giống nhau. Nó làm cho công việc đếm của chúng ta sẽ phức tạp nếu ta đếm theo kiểu thông thường vì sẽ có rất nhiều trường hợp trùng nhau. Để giải bài toán này, chúng ta sẽ làm như sau: - Biểu diễn mỗi cái bánh là 1 dấu +, và dùng dấu | để thể hiện vách ngăn giữa các hộp. Có 3 cái hộp thì chỉ cần 2 vách ngăn là đủ. Khi đó ta sẽ có một dãy ký hiệu gồm 4 dấu + và 2 dấu | như sau: + + + + | | . - Bây giờ ta sẽ hoán vị dãy ký hiệu này bất kỳ, một hoán vị nhận được sẽ tương ứng 1-1 với một cách cho bánh vào hộp. Số dấu + đứng trước dấu | đầu tiên sẽ là số bánh nằm trong hộp thứ nhất, số dấu + đứng giữa hai dấu | sẽ là số bánh trong hộp thứ hai và số dấu + nằm sau dấu | thứ hai sẽ là số bánh trong hộp thứ ba. Chẳng hạn như hoán vị: + + | | + + sẽ tương ứng với cách cho 2 bánh vào hộp thứ nhất, 0 bánh vào hộp thứ hai và 2 bánh vào hộp thứ ba. - Như vậy số cách chia 4 cái bánh giống nhau vào trong 3 cái hộp khác nhau chính là số hoán vị của một dãy gồm 4 dấu + và 2 dấu |. Theo công thức của (2 4)! hoán vị lặp, số hoán vị này là: . Để ý một chút thì công thức này cũng 4!2! 4 2 chính là công thức của tổ hợp C4 2 C4 2 . Tổng quát, ta có mệnh đề sau: n k 1 Mệnh đề. Số cách cho n vật giống nhau vào trong k hộp khác nhau là: Cn k 1 Cn k 1 Dạng tổ hợp lặp có rất nhiều ứng dụng, mỗi ứng dụng đòi hỏi những cách vận dụng khác nhau của công thức. Chính vì thế khi giải, chúng ta phải rất linh hoạt để đưa về bài toán gốc “chia bánh” mà chúng ta đã có công thức. Ví dụ. a. “Tìm số nghiệm nguyên không âm của phương trình sau: x1 + x2 + x3 = 10”. Đối với bài toán này, nếu đặt x1 là số bánh được cho vào hộp 1, x2 là số bánh được cho vào hộp 2 và x3 là số bánh được cho vào hộp 3 thì bài toán trên trở thành “có bao nhiêu cách cho 10 cái bánh giống nhau vào trong 3 cái hộp 10 10 khác nhau” và kết quả cần tìm là: C10 3 1 C12 . b. “Một người Mẹ có 4 đứa con. Một ngày nọ, người Mẹ có 20 cái kẹo và muốn chia cho 4 đứa con sao cho mỗi đứa được ít nhất 2 cái kẹo. Hỏi có bao nhiêu cách chia như vậy?”. Rõ ràng là cách đặt vấn đề ở đây cũng giống như việc ta cho 20 cái bánh giống nhau vào trong 4 cái hộp khác nhau sao cho mỗi cái hộp có ít nhất 2 cái bánh. Rõ ràng là ta không thể áp dụng ngay công thức đã biết vì nếu như vậy thì sẽ có rất nhiều trường hợp sẽ có hộp có ít hơn 2 bánh (thậm chí là có thể không có cái bánh nào). Để giải quyết trường hợp này, ta sẽ cho vào mỗi hộp hai cái bánh trước, sau đó mới chia 12 cái bánh còn lại Trang 22
  23. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM một cách tự do vao 4 cái hộp, như vậy số cách chia thỏa mãn yêu cầu ban 12 12 đầu là: C12 4 1 C15 . 2.3.3 Nguyên lý Dirichlet. (nguyên lý chuồng bồ câu) Nguyên lý. Nếu chuồng bồ câu có ít cửa hơn số bồ câu thì có ít nhất hai con chim bồ câu ở chung trong một cửa. Ví dụ. a. Trong một lớp có 50 người sẽ có ít nhất 2 người có ngày sinh nhật trong cùng một tháng. b. Trong 5 số tự nhiên bất kỳ luôn tìm được 2 số sao cho hiệu của chúng chia hết cho 4. Nhận thấy rằng trong phần a. của ví dụ trên, việc chắc chắn là có 2 người có cùng ngày sinh nhật trong một tháng nào đó là chính xác nhưng dường như vẫn chưa làm chúng ta thỏa mãn. Điều này cũng dễ hiểu vì thật ra chúng ta còn có thể có được kết quả mạnh hơn. Sau đây là nguyên lý Dirichlet tổng quát. Nguyên lý Dirichlet tổng quát. Nếu nhốt n con chim bồ câu vào trong một chuồng có k cửa thì chắc chắn sẽ có một n cửa chứa không ít hơn con chim bồ câu. k Ví dụ: Trong một lớp có 50 người thì chắc chắn sẽ có ít nhất 5 người có ngày sinh nhật trong cùng một tháng. Trang 23
  24. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 3 Chương 3. Quan hệ 3.1 Quan hệ Định nghĩa. Một quan hệ giữa tập hợp A và tập hợp B là một tập con  của AB . Nếu (,)a b  , ta viết a b . Đặc biệt, một quan hệ giữa A và A được gọi là một quan hệ hai ngôi trên A. Ví dụ. 1. A = {1, 2, 3, 4}, B = {4, 5},  ={(1,4),(1,5),(3,5)(4,4)} là một quan hệ giữa A và B. Quan hệ  có thể được biểu diễn bởi sơ đồ sau: 1 2 3 4 2. Quan hệ “=” trên một tập hợp A bất kỳ: a b a b 3. Quan hệ “ ” trên N, Z hay R: a b a b 4. Quan hệ đồng dư trên Z: a b a  b(mod7) Các tính chất của quan hệ: Định nghĩa. Cho là quan hệ hai ngôi trên tập hợp A. Ta nói: i.  có tính phản xạ nếu x A, x x ii.  có tính đối xứng nếu x, y A, x y y  x iii.  có tính phản xứng nếu x, y A, x y y  x x y iv.  có tính bắc cầu nếu x,, y z A, x y y  z x  z Nhận xét. 1. Một quan hệ hai ngôi  trên tập A có tính chất phản xạ nếu mọi phần tử của A đều quan hệ với chính nó. Trong trường hợp này, nếu ta biểu diễn quan hệ  trên hệ trục thì nó sẽ chứa các điểm nằm trên đường chéo chính. 2. Nếu  có tính chất đối xứng thì khi biểu diễn nó trên đồ thị, ta sẽ thấy các điểm được xác định sẽ đối xứng qua đường chéo chính. Trang 24
  25. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 3. Hai tính chất đối xứng và phản xứng không phải là ngược nhau. Một quan hệ không có tính chất đối xứng không có nghĩa là nó có tính chất phản xứng và ngược lại. Sẽ có những quan hệ vừa đối xứng vừa phản xứng và cũng sẽ có những quan hệ không đối xứng và cũng không phản xứng. Ví dụ. Xét A = {1,2,3,4}, và  ={(1,1),(3,3),(4,4)}, khi đó  là quan hệ vừa đối xứng vừa phản xứng. Còn nếu xét  ’ = {(1,2),(2,1),(3,2)} thì  ’ không đối xứng (vì (3,2)  nhưng (2,3)  ) cũng không phản xứng (vì (1,2) ' và (2,1) ' nhưng 1 2 ). Ví dụ. Xét quan hệ hai ngôi  trên tập Z được định nghĩa như sau: a,b Z, ab a 2 b 2 Chứng minh rằng  có các tính chất phản xạ, đối xứng và bắc cầu. Giải. .  phản xạ. a Z , ta có a2 = a2, do đó, theo định nghĩa, ta có a a hay  có tính phản xạ .  đối xứng. Xét a, b bất kỳ thuộc Z, giả sử a b , ta sẽ chứng minh b a . Thật vậy: a b a2 b2 b2 a2 b  a , suy ra  có tính đối xứng. .  bắc cầu. Xét a, b, c bất kỳ thuộc Z, giả sử a b và b c ta sẽ chứng minh a c . Thật vậy: a b  b  c a2 b2  b2 c2 a2 c2 a  c , suy ra  có tính bắc cầu. 3.2 Quan hệ tương đương Định nghĩa. Một quan hệ hai ngôi  trên tập hợp A được gọi là quan hệ tương đương nếu nó có các tính chất phản xạ, đối xứng và bắc cầu. Ví dụ. 1. Quan hệ  như đã định nghĩa trong phần trước, a,b Z, ab a 2 b 2 , chính là một quan hệ tương đương. 2. Cho trước một ánh xạ f: A B , ta định nghĩa quan hệ  trên A như sau: x, y A, x y f() x f() y khi đó, ta có thể kiểm chứng được đây là một quan hệ tương đương. 3. Cho trước một số tự nhiên n. Xét quan hệ  trên Z được định nghĩa như sau: a,b Z, ab a b(mod n) Đây cũng là một quan hệ tương đương trên Z. Định nghĩa. Cho  là một quan hệ tương đương trên A và x A. Khi ấy lớp tương đương chứa x, ký hiệu là x hay [x], là tập hợp con của A sau đây: x y A y x Ví dụ. Xét A = {1,2,3, 10}. Xét quan hệ  trên A: a b a  b(mod 3) . Đây là một quan hệ tương đương trên A. Và ta có: - Lớp tương đương chứa 1: 1 1,4,7,10 Trang 25
  26. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM - Lớp tương đương chứa 5: 5 2,5,8 - Để ý rằng: 1 4 7 10 , 2 5 8 và 3 6 9 Định lý. Cho là một quan hệ tương đương trên tập hợp A. Khi ấy: i. x A, x x ii. x, y A, x y x y iii. Hai lớp tương đương x và y sao cho x  y  thì trùng nhau. Chứng minh. i. Do có tính chất phản xạ nên ta có x A, x x . Theo định nghĩa của lớp tương đương, ta suy ra x x . ii. Xét x và y là hai phần tử bất kỳ của A. Giả sử x y , ta sẽ chứng minh x y . Xét z là một phần tử bất kỳ trong x . Từ định nghĩa của lớp tương đương, ta suy ra z x . Mặt khác, do  có tính chất bắc cầu nên kết hợp với giả thiết ban đầu là x y , ta suy ra z y . Điều này cũng có nghĩa là z y . Từ đó, ta có x  y . Bằng cách tương tự ta cũng chứng minh được y  x . iii. Giả sử x  y  . Khi đó tồn tại phần tử z x  y , nghĩa là z x và z y . Từ đó ta suy ra z x và z y , do có tinh đối xứng và bắc cầu nên ta suy ra x y . Theo phần ii) ta có x y . Từ các tính chất trên của các lớp tương đương, ta có thể nói rằng các lớp tương đương tạo thành một phân hoạch của tập A. Nghĩa là hợp của các lớp tương đương sẽ chính bằng A và các lớp tương đương hoặc trùng nhau, hoặc tách rời hẳn nhau. Ví dụ. 1. Xét quan hệ  trên Z: m n m2 n2 . Ta đã kiểm chứng được đây là một quan hệ tương đương. Các lớp tương đương tạo thành phân hoạch của là: {0}, {1,-1}, {2,-2}, , {k,-k}, và ta nói Z được phân hoạch thành vô số lớp tương đương hữu hạn. 2. Xét quan hệ đồng dư theo modulo n trên tập Z. Đây cũng là một quan hệ tương đương và ta có Z sẽ được phân hoạch thành n lớp tương đương: 0, 1, ,n 1 mỗi lớp tương đương là một tập con vô hạn của Z, chẳng hạn như 0 là tập hợp tất cả các số nguyên chia hết cho n. 3.3 Quan hệ thứ tự - Biểu đồ Hasse Trang 26
  27. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Định nghĩa. Một quan hệ hai ngôi trên tập hợp A được nói là một quan hệ thứ tự nếu nó có tính chất phản xạ, phản xứng và bắc cầu. Khi ấy ta nói A là tập hợp có thứ tự hay A là tập hợp được sắp. Ký hiệu. Thông thường, ta sẽ ký hiệu một quan hệ thứ tự là và ký hiệu cặp A, là cặp có thứ tự. Ví dụ. 1. Z, là một tập hợp có thứ tự. 2. Trên tập hợp P(E) ta có quan hệ: A B A  B . Khi đó là một quan hệ thứ tự trên P(E). 3. Xét n là một số nguyên dương. Đặt U n a Z a | n ký hiệu a| n để chỉ a là ước số của n (hay n chia hết cho a). U n chính là tập hợp các ước số của n. Trên U n ta định nghĩa một quan hệ: x y x| y Ta sẽ kiểm chứng rằng Un , là một tập hợp có thứ tự. Thật vậy dễ thấy rằng có tính phản xạ và bắc cầu. Mặt khác giả sử a b và b a , nghĩa là a là ước của b và b là ước của a. Điều này chỉ có thể xảy ra khi và chỉ khi a = b. Vậy có tính phản xứng. Suy ra là quan hệ thứ tự và tập Un , là một tập hợp có thứ tự. Để biểu diễn quan hệ thứ tự, chúng ta có thể sử dụng hai phương pháp là liệt kê hoặc dùng đồ thị. Tuy nhiên cả hai phương pháp này đều không thể hiện được một cách trực quan về quan hệ thứ tự. Chính vì thế, chúng ta sẽ phải dùng một cách khác để biểu diễn: đó là biểu đồ Hasse. Trước hết, ta xét định nghĩa sau: Định nghĩa. Cho A, là tập có thứ tự và x, y là hai phần tử bất kỳ trong A. a. Nếu x y, ta nói y là trội của x hay x được trội bởi y. b. y là trội trực tiếp của x nếu y là trội của x và không tồn tại một phần tử z A nào sao cho x z y và x y z . Ví dụ. Xét tập U12 , , dễ dàng nhận thấy rằng: - Trội của 2 là 4, 6, 12 - Trội trực tiếp của 2 là 4, 6. Định nghĩa. Cho A, là tập có thứ tự hữu hạn. Biểu đồ Hasse của A, bao gồm: Trang 27
  28. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM a. Một tập hợp các điểm trong mặt phẳng tương ứng 1 – 1 với A, gọi là các đỉnh b. Một tập hợp các cung có hướng nối một số cặp đỉnh: hai đỉnh x và y được nối bằng một cung có hướng (từ x sang y) nếu và chỉ nếu y là trội trực tiếp của x. Ví dụ. Xét U12 1,2,3,4,6,12 a. Biểu đồ Hasse của U12 , là: 1 2 3 4 6 12 b. Biểu đồ Hasse của U12 ,| là: 12 4 6 2 3 1 c. Cho tập E = {1,2,3}. Xét tập P(E) – tập tất cả các tập con của E. Trên P(E) ta định nghĩa quan hệ như sau: AB, (EA ), B A  B Khi đó biểu đồ Hasse của PE( ), như sau: {1,3} {1,2,3} {1} {1,2} {3} {2,3}  {2} Định nghĩa. Tập A, được nói là có thứ tự toàn phần nếu và chỉ nếu hai phần tử bất kỳ đều so sánh được, nghĩa là mệnh đề sau là đúng: Trang 28
  29. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM x, y A, x y  y x Ví dụ. Tập N, Z, Q, R với thứ tự , thông thường là các tập có thứ tự toàn phần. Mệnh đề. Biểu đồ Hasse của A, là một dây chuyền khi và chỉ khi A, là tập có thứ tự toàn phần. Định nghĩa. Cho A, là một tập có thứ tự. Khi đó ta nói: a. Một phần tử m của A được nói là tối tiểu (tương ứng là tối đại) nếu m không là trội thực sự của bất cứ phần tử nào (m không được trội thực sự bởi bất cứ phần tử nào) của A. b. Một phần tử M của A được nói là cực tiểu (tương ứng là cực đại) nếu M được trội bởi mọi phần tử của A (M là trội của mọi phần tử trong A). Ví dụ. a. Xét tập U12 , , ta có: - Phần tử tối tiểu là 1 – đây cũng là phần tử cực tiểu - Phần tử tối đại là 12 – đây cũng là phần tử cực đại b. Xét tập {1,2,3,4,5,6},| , ta có: - Phần tử tối tiểu là 1 – đây cũng là phần tử cực tiểu - Phần tử tối đại là: 4, 5, 6 – không có phần tử cực đại Trang 29
  30. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 4 Chương 4. Đại số Boole 4.1 Đại số Boole: Định nghĩa – Tính chất Định nghĩa. Một đại số Boole là tập hợp A  cùng với hai phép tính hai ngôi  và  thỏa mãn các tính chất sau: i. Tính kết hợp: với mọi x,, y z A : x (y  z) (x  y)  z và x (y  z) (x  y)  z ii. Tính giao hoán: với mọi x, y A : x y y  x và x y y  x iii. Tính phân phối: với mọi x,, y z A : x (y  z) (x  y)( x  z) và x (y  z) (x  y)( x  z) iv. Phần tử trung hòa: tồn tại hai phần tử trung hòa 1, 0 đối với hai phép toán ,  sao cho với mọi x A, ta có: x  0 x và x 1 x v. Phần tử bù: với mọi x A, tồn tại x A sao cho: x  x 1 và x x 0 Ví dụ. a. Xét tập hợp B {0,1} . Trên B ta định nghĩa hai phép toán sau: x, y B, x y x. y x y x y x. y Bây giờ ta sẽ kiểm chứng rằng tập hợp B với hai phép toán trên sẽ là một đại số Boole. Thật vậy, với mọi x, y, z B ta có: - Tính kết hợp: x  (y  z) = x  (y z yz) = x (y z yz) x( y z yz) = x y z xy yz xz xyz = (x y xy) z (x y xy) z = (x y xy)  z = (x  y)  z x  (y  z) = x( yz) (xy) z (x  y)  z Vậy tính chất kết hợp được thỏa Trang 30
  31. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM - Tính giao hoán: Tính chất này hiển nhiên được thỏa vì trong định nghĩa của các phép toán, vai trò của x và y là như nhau. - Tính phân phối: Ta có: o x  (y  z) = x  (yz) x yz xyz (1) Mặt khác ta có: (x  y)( x  z) = (x y xy)( x z xz) = x2 xz x2 z xy yz xyz x2 y xyz x2 yz Để ý rằng x B {0,1}, do đó ta có x2 = x. Từ đó, ta suy ra: (x  y)( x  z) = x yz xyz (2) Từ (1), (2) ta suy ra x  (y  z) = (x  y)( x  z) . o x  (y  z) = x( y z yz) = xy xz xyz (3) Mặt khác, ta có: (x  y)( x  z) = xy  yz xy yz x2 yz xy yz xyz( do x2 x) (4) Từ (3), (4), ta suy ra x (y  z) (x  y)( x  z) Vậy tính chất phân phối được thỏa. - Phần tử trung hòa: x 0 x 0 x.0 x Ta có: với mọi x B , . Do đó, 1=1 là phần tử trung x 1 x.1 x hòa của phép  và 0 =0 là phần tử trung hòa của phép  . - Phần tử bù: Với mọi x B , ta có phần tử bù của x là x 1 x . Thật vậy, ta có: x x x(1 x) x x2 0 0 x  x x (1 x) x(1 x) 1 1 Vậy B={0,1} với hai phép toán định nghĩa ở trên là một đại số Boole. b. Xét tập U30 1,2,3,5,6,10,15,30 là tập các ước số của 30. Trên tập này, ta định nghĩa hai phép toán như sau: x, y B, x y UCLN(,) x y x y BCNN(,) x y Dễ dàng nhận thấy rằng do các tính chất của phép lấy ước chung lớn nhất và bội chung nhỏ nhất nên hai phép toán ,  này thỏa mãn các tính chất kết hợp, giao hoán và phân phối. Bây giờ ta xét xem liệu có tồn tại 2 phần tử trung hòa cho 2 phép toán và có tồn tại phần tử bù cho mỗi phần tử của U30 hay không. Trước hết, ta nhận thấy rằng UCLN(30,x) = x và BCNN(1,x) = x với mọi x U30 . Do đó, 30 và 1 lần lượt chính là hai phần tử trung hòa của phép  và phép  . Ta có: 1 30, 0 1. Xét một phần tử x bất kỳ trong U30. Ta sẽ chứng minh phần tử bù của x chính 30 là x : x Trang 31
  32. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 30 - Nhận thấy rằng nếu x là một ước số của 30 thì cũng là một ước số của x 30 30, nghĩa là x U . x 30 - Ta nhận thấy rằng: 30 = 2.3.5. Điều đó có nghĩa là nếu một số nguyên tố 2, 30 3, hoặc 5 là ước số của x thì nó không thể nào là ước số của x . Suy x ra, giữa x và x không có chung một ước số nguyên tố nào. Suy ra: 30 x x UCLN(, x ) 1 0 x 30 - Tương tự ta cũng có: x  x BCNN x, 30 1 x Vậy U30 là một đại số Boole với hai phép toán kể trên. Chú ý. U12 với 2 phép toán kể trên không thể là một đại số Boole vì phần tử x = 2 không có phần tử bù thỏa mãn các tính chất như trong định nghĩa (phần kiểm chứng xem như bài tập). Định lý. Cho đại số Boole A. Trên A, ta định nghĩa: x, y A, x y x y x khi đó, sẽ là một quan hệ thứ tự trên A. Hơn nữa, 1 chính là phần tử cực đại và O chính là phần tử cực tiểu trong A, . Chứng minh. là một quan hệ thứ tự trên A. o Phản xạ: x A, ta có: x x = 0  (x x) (t/c phần tử trung hòa) = (x  x)( x  x) (t/c phần tử bù) = x  (x  x) (t/c phân phối) = x  1 (t/c phần tử bù) = x (t/c phần tử trung hòa) Suy ra x x hay có tính chất phản xạ o Phản xứng: x y x y x x, y A, x y (do  có tính chất giao hoán) y x y x y Vậy, có tính chất phản xứng. o Bắc cầu: x y x y x x,, y z A, . Xét x z , ta có: y z y z z x  z = (x  y)  z Trang 32
  33. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM = x  (y  z) = x  y = x Suy ra x z hay có tính chất bắc cầu. Vậy là quan hệ thứ tự trên A 1 là cực đại, 0 là cực tiểu trong A, Với mọi x A, ta có x 1 x x 1. Suy ra 1 là phần tử cực đại trong A, . Mặt khác, ta có: 0 x (0  x)  0 (0  x)( x  x)( 0  x) x x x 0 suy ra 0 x,x A, hay 0 là phần tử cực tiểu trong A, . Như vậy, trên đại số Boole luôn luôn tồn tại một quan hệ để đại số Boole trở thành tập được sắp. Để làm rõ hơn khía cạnh này, chúng ta xét các ví dụ sau đây: Ví dụ. a. Xét đại số Boole B 1,0 , theo định lý trên, trên B chúng ta có quan hệ thứ tự được định nghĩa như sau: x, y B, x y x  y x x.y x (*) Để ý rằng do, x, y chỉ có thể nhận giá trị 0 hay 1 nên ta chỉ có 4 trường hợp khác nhau của x và y. Trong 4 trường hợp đó, để thỏa (*), có 3 trường hợp: TH1: x = 1, y = 1. TH2: x = 0, y = 0. TH3: x = 0, y = 1. Trường hợp còn lại (x=1, y=0) thì không thỏa (*). Nhìn lại 3 trường hợp trên, chúng ta thấy rằng: chúng đều có một đặc điểm chung là x y . Vì vậy, ta có thể viết: x, y B, x y x  y x x.y x (*) x y Và như vậy thì chúng ta nhận thấy rằng: mặc dù quan hệ thứ tự được định nghĩa bằng các phép toán trong đại số Boole tưởng như xa lạ lại chính là quan hệ mà ta rất quen thuộc. Hơn nữa, theo quan hệ này, 0=0 chính là phần tử cực tiểu và 1=1 chính là phần tử cực đại, đúng theo định lý trên. b. Xét đại số Boole U30, theo định lý trên, trên U20 chúng ta có quan hệ thứ tự được định nghĩa như sau: Trang 33
  34. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM x, y B, x y x  y x UCLN (x, y) x ( ) Nhận thấy rằng, điều kiện ( ) chỉ thỏa khi và chỉ khi x là ước số của y. Vì vậy, ta có thể viết: x, y B, x y x  y x UCLN(x, y) x ( ) x | y Và như vậy thì chúng ta nhận thấy rằng: mặc dù quan hệ thứ tự được định nghĩa bằng các phép toán trong đại số Boole lại chính là quan hệ “là ước số của” mà ta rất quen thuộc. Hơn nữa, theo biểu đồ Hasse của (U30,|) dưới đây, 0=1 chính là phần tử cực tiểu và 1=30 chính là phần tử cực đại, đúng theo định lý trên. 15 30 3 6 5 10 1 2 c. Cho tập E = {1,2,3}. Xét tập P(E) – tập tất cả các tập con của E. Trên P(E) ta có quan hệ như sau: A, B P(E), A B A  B A  B A ( ) Nhận thấy rằng điều kiện ( ) được thỏa khi và chỉ khi A  B . Và như vậy ta có thể viết: A, B P(E), A B A  B A  B A ( ) A  B Quan hệ được định nghĩa trong định lý trên chính là quan hệ “là tập con của” mà ta đã khảo sát trong các phần trước. {1,3} {1,2,3} {1} {1,2} {3} {2,3}  {2} Theo biểu đồ Hasse trên, dễ dàng nhận thấy 0= là phần tử cực tiểu và 1={1,2,3} là phần tử cực đại trong đại số Boole P(E). Trang 34
  35. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Chú ý: trên một đại số Boole có thể có rất nhiều quan hệ thứ tự khác. Mặc dầu vậy, từ đây trở về sau khi ta nói đến quan hệ thứ tự trong đại số Boole mà không nói gì thêm thì ta hiểu rằng đấy là quan hệ thứ tự như đã định nghĩa trong định lý trên. Định nghĩa. Cho đại số Boole A. Một trội trực tiếp của phần tử 0 trong A được gọi là một nguyên tử của A. Ví dụ. a. Trong đại số Boole U30, 2, 3 và 5 chính là các nguyên tử vì chúng là trội trực tiếp của 0=1. b. Trong đại số Boole P(E), với E là tập {1,2,3}, các tập hợp {1}, {2}, {3} chính là các nguyên tử. Khi nói đến nguyên tử, chúng ta hiểu rằng đó là những đối tượng không thể chia nhỏ được nữa và chúng thường được dùng để cấu thành nên những đối tượng khác. Ở đây, trong đại số Boole, khái niệm nguyên tử vẫn được giữ nguyên vẹn ý nghĩa như vậy. Mệnh đề sau đây đề cập đến ý nghĩa này. Mệnh đề. Trong đại số Boole A, mọi phần tử x khác 0 đều có thể được biểu diễn dưới dạng: x m1  m2   mk với m1, m2, , mk là các nguyên tử nào đó của A Mệnh đề trên có ý nghĩa rất lớn. Nó khẳng định rằng tập hợp các nguyên tử của một đại số Boole A có thể được dùng để biểu diễn tất cả các phần tử khác 0 trong đại số Boole đó. Ví dụ. a. Xét đại số Boole U30. Nhắc lại rằng, 2 phép toán được định nghĩa trên đại số Boole này là 2 phép toán UCLN và BCNN, và các nguyên tử của đại số Boole này chính là: 2, 3, và 5. Theo mệnh đề trên, bất kỳ một phần tử nào khác 0(=1) của U30 cũng đều có thể biểu diễn bằng một phép  một số nguyên tử nào đó của nó. Chẳng hạn như: 6 2  3 BCNN )3,2( hay 15 5  3 BCNN )3,5( hay 30 2  3  5 BCNN )5,3,2( b. Xét đại số Boole P(E), với E là tập {1,2,3}. Nhắc lại rằng, 2 phép toán được định nghĩa trên đại số Boole này là 2 phép toán  và  , và các nguyên tử của đại số Boole này chính là các tập hợp: {1}, {2}, {3}. Theo mệnh đề trên, bất kỳ một phần tử nào khác 0(=) của P(E) cũng đều có thể biểu diễn bằng một phép  một số nguyên tử nào đó của nó. Chẳng hạn như: }2,1{ }1{  }2{ }1{  }2{ hay }3,2{ }2{  }3{ }2{  }3{ Trang 35
  36. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM hay }3,2,1{ }1{  }2{  }3{ }1{  }2{  }3{ 4.2 Hàm Boole – Dạng nối rời chính tắc Định nghĩa. Một hàm Boole f theo n biến là một ánh xạ: f : B n B (x1 , , xn ) f (x1 , , xn ) Nhận xét. a. Nếu đồng nhất tập B={0,1} với tập các mệnh đề {Đúng, Sai} thì hàm Boole cũng không phải là một khái niệm quá xa lạ: một hàm Boole chính là một dạng mệnh đề (công thức logic – xem lại chương 1). Nó nhận các biến x1, x2, ,xn chính là các biến mệnh đề và kết quả thu được cũng là cũng là một mệnh đề (đúng hoặc sai). b. Tổng quát, một hàm Boole theo n biến sẽ là một hàm số theo n biến số, mỗi biến số sẽ nhận giá trị 0 hoặc 1 và kết quả của hàm số cũng là giá trị 0 hoặc 1. Mặc dù không nói ra nhưng ta vẫn phải hiểu rằng các phép toán biểu diễn trong công thức của hàm Boole vẫn chính là các phép toán trong đại số Boole B={0,1}. Ví dụ. a. f (x, y) x  y là một hàm Boole theo 2 biến: f(0,0) = 1, f(0,1)=0, b. f (x, y, z) (x  y)  z là một hàm Boole theo 3 biến: f(0,0,1)=0, f(1,0,1)=1,  Bảng chân trị của hàm Boole. Tương tự như một dạng mệnh đề, chúng ta có thể lập bảng chân trị của hàm Boole để xác định giá trị của hàm Boole khi giá trị của các biến thay đổi. Ví dụ. Xét hàm Boole: f (x, y, z) (x  y)  z . Bảng chân trị của hàm Boole này được xác định như sau: x y z y x  y z f(x,y,z) 0 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 Như vậy, mỗi hàm Boole sẽ tương ứng với một và chỉ một bảng chân trị. Nói cách khác, hai hàm Boole có cùng bảng chân trị sẽ là hai hàm Boole bằng nhau (thực chất chỉ được coi như là một hàm Boole duy nhất). Trang 36
  37. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Nhận thấy rằng, việc xây dựng bảng chân trị của một hàm Boole hoàn toàn giống như xây dựng bảng chân trị của một dạng mệnh đề (xem lại chương 1). Câu hỏi đặt ra là: “Từ một bảng chân trị, làm thể nào ta xây dựng lại được công thức tường minh của hàm Boole?”. Đây là một câu hỏi được đặt ra rất thực tế, chúng ta phải thường xuyên xây dựng công thức của hàm Boole khi biết bảng chân trị của nó. Để thực hiện được điều này, chúng ta phải quay lại kiến thức của đại số Boole đã học trong phần trước. Xét Fn là tập hợp tất cả các hàm Boole theo n biến. Trên Fn, ta định nghĩa 2 phép toán , như sau: Với mọi f , g Fn , f  g và f  g được xác định bởi: x B n (, f  g)(x) f (x).g(x) ( f  g)(x) f (x) g(x) f (x).g(x) Rõ ràng với f  g và f  g được xác định như trên thì f  g và f  g đều là những hàm Boole theo n biến, do đó 2 phép toán , là 2 phép toán trên Fn. Bây giờ, ta sẽ kiểm tra xem nó có thỏa mãn các tính chất của đại số Boole hay không. Dễ thấy rằng các phép toán trên được định nghĩa tương tự như trong đại số Boole B={0,1} (xem lại VD trong mục 4.1). Chính vì thế, không khó để có thể kiểm tra hai phép toán này thỏa mãn các tính chất giao hoán, kết hợp và phân phối. Kế tiếp, chúng ta sẽ xác định 2 phần tử trong Fn đóng vai trò là 0 và 1. Thực chất đây là 2 hàm Boole theo n biến. Giả sử t Fn là hàm đóng vai trò phần tử 1. Khi đó, ta có: f Fn , f  t f n f Fn , x B (, f  t)(x) f (x) n f Fn , x B , f (x).t(x) f (x) (*) Theo đó, do (*) phải thỏa với f và x được lấy bất kỳ, điều này chỉ có thể xảy ra khi t(x)=1 với mọi x B n . Như vậy hàm Boole đóng vai trò là phần tử trung hòa của phép  chính là một hàm hằng: hàm này luôn nhận giá trị là 1 với mọi giá trị của các biến. Nói cách khác, bảng chân trị của hàm này bằng 1 ở tất cả các dòng. Tương tự, hàm đóng vai trò là phần tử 0 trong Fn, phần tử trung hòa của phép  , chính là hàm mà giá trị của nó luôn bằng 0 với bất kỳ giá trị của các biến. Bây giờ với hàm f Fn bất kỳ, liệu có luôn tồn tại một hàm f Fn thỏa mãn điều kiện: f  f 0 và f  f 1? Câu trả lời là có, thật vậy, với f Fn bất kỳ, ta đặt f (x) 1 f (x),x B n . Khi đó ta có: x B n (, f  f )(x) f (x). f (x) f (x).(1 f (x)) 0 (do f (x) B }1,0{ ) ( f  f )(x) f (x) f (x) f (x). f (x) f (x) 1( f (x)) f (x).(1 f (x)) 1 f (x)(1 f (x)) .1 Trang 37
  38. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Như vậy hàm f chính là phần tử bù của hàm f. Từ những điều đã khảo sát ở trên, ta thấy rằng Fn với hai phép toán định nghĩa như trên sẽ là một đại số Boole. Đây là một điều cũng hết sức thú vị khi các hàm Boole được định nghĩa thông qua đại số Boole B={0,1} và bây giờ, tập hợp những hàm Boole theo n biến cũng sẽ lại là một đại số Boole. Cũng trong mục 4.1, chúng ta thấy rằng mọi đại số Boole đều là tập hợp có thứ tự theo một quan hệ thứ tự nào đó. Và Fn cũng không phải ngoại lệ, trên Fn, ta có quan hệ thứ tự sau: f , g Fn , f g f  g g x B n , f (x)  g(x) f (x) x B n , f (x).g(x) f (x) x B n , f (x) g(x) Để ý rằng, thông qua định nghĩa trên, một hàm Boole f được nói là “bé hơn” một hàm Boole g nếu và chỉ nếu tại cùng một dòng trên bảng chân trị, giá trị của f(x) luôn bé hơn hay bằng giá trị của g(x). Ví dụ. Cho 2 hàm Boole f và g được xác định trong bảng chân trị sau: x y z f g 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 Khi đó, ta thấy rằng trên một dòng bất kỳ, giá trị của f luôn nhỏ hơn hay bằng giá trị của g. Do đó, ta có: f g . Bây giờ, ta sẽ khảo sát các nguyên tử của Fn. Theo định nghĩa, nguyên tử của một đại số Boole sẽ là các trội trực tiếp của phần tử 0 theo quan hệ đã được xác định. Như vậy những nguyên tử của đại số Boole chính là những hàm Boole mà bảng chân trị của nó chỉ khác 0 tại một dòng duy nhất (vì nếu có 2 dòng khác 0 thì đây không còn là trội trực tiếp của 0 nữa). Bảng chân trị của một hàm Boole theo n biến n n sẽ có 2 dòng, chính vì vậy, Fn sẽ có tất cả là 2 nguyên tử. Trên đây, ta đã xác định được các nguyên tử của Fn theo bảng chân trị, tuy nhiên chúng ta cũng cần biết công thức tường minh của các nguyên tử này. Mệnh đề sau đây sẽ cho chúng ta rõ hơn về điều này. Trang 38
  39. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Mệnh đề. Mọi nguyên tử của Fn đều có dạng: b1  b2   bn trong đó bi sẽ là xi hoặc xi (i=1 n, xi là các biến của trong các hàm Boole). Việc chứng minh mệnh đề trên không khó. Tuy nhiên chúng ta sẽ tập trung hơn vào việc xác định công thức cho từng nguyên tử cụ thể. Để ý rằng các hàm Boole được xác định theo công thức trên chỉ khác 0 tại một dòng duy nhất. Dòng duy nhất này được xác định bởi các thành phần bi trong công thức. Tại dòng duy nhất đó, nếu xi = 1 thì bi = xi, còn nếu xi=0 thì bi = xi . Để cụ thể hơn, ra xét ví dụ sau đây: Ví dụ. Xét đại số Boole F3. Ta có 8 nguyên tử (gọi là f0, ,f7) và bảng chân trị của chúng được xác định như sau: x y z f0 f1 f2 f3 f4 f5 f6 f7 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 Để xác định công thức của f0, ta thấy rằng f0 chỉ khác 0 tại một dòng duy nhất ứng với x = 0, y = 0, và z = 0. Như vậy theo mệnh đề trên, ta có f 0 x  y  z . Tương tự, ta có công thức của 7 nguyên tử còn lại như sau: f1 x  y  z f 2 x  y  z f3 x  y  z f 4 x  y  z f5 x  y  z f 6 x  y  z f 7 x  y  z Chú ý. Để cho tiện, từ đây về sau, ta sẽ sử dụng dấu chấm (.) thay cho ký hiệu  , nghĩa là ta sẽ viết x.y thay cho x  y . Đến đây ta đã xác định được cụ thể các nguyên tử của Fn. Ta quay trở lại câu hỏi đặt ra ban đầu: “Làm thể nào xác định được công thức tường minh của một hàm Trang 39
  40. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Boole khi biết bảng chân trị của nó?”. Phần sau đây sẽ giới thiệu cụ thể các xác định này.  Công thức dạng nối rời chính tắc của hàm Boole: Cần nhắc lại rằng chúng ta có một mệnh đề rằng mọi phần tử khác 0 trong đại số Boole đều có thể biểu diễn được dưới dạng tổ hợp một số nguyên tử được nối với nhau bởi phép hợp (  ). Cụ thể, một hàm Boole f 0 bất kỳ đều có thể được biểu diễn dưới dạng: f m1  m2   mk với m1, m2, , mk là một số nguyên tử nào đó của Fn. Vấn đề ở đây là những nguyên tử nào được chọn để thiết lập công thức của hàm f. Để ý rằng các nguyên tử của Fn đều không đồng thời bằng 1 với một bộ giá trị nào của các biến. Nói cách khác với nếu một nguyên tử nào đó có giá trị 1 với một bộ giá trị đó của các biến thì các nguyên tử còn lại đều có giá trị bằng 0 với chính bộ giá trị của các biến đó. Tận dụng tính chất này, ta có thể thiết lập công thức của một hàm Boole từ bảng chân trị của nó theo các bước sau đây: - Chọn tất cả các nguyên tử của Fn ứng với các dòng bằng 1 trong bảng chân trị của f. - Nối tất cả các nguyên tử đã được chọn ở trên bằng phép toán hợp (  ) ta được công thức biểu diễn của hàm f. Ví dụ. Cho hàm Boole f(x,y) có bảng chân trị như sau: x y f 0 0 1 0 1 1 1 0 0 1 1 0 Hãy thiết lập công thức biểu diễn của hàm f. Giải. Để thiết lập công thức này, ta tuân thủ 2 bước như đã nêu ở trên. Trang 40
  41. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Đầu tiên ta xác định các nguyên tử tương ứng với các dòng mà tại đó giá trị của f bằng 1. Do f có giá trị bằng 1 tại 2 dòng đầu tiên nên ta chọn 2 nguyên tử tương ứng với 2 dòng đó: f 0 x.y và f1 x.y . Kế tiếp, nối chúng lại bằng phép hợp, ta được công thức của hàm f . Ta có : f (x, y) x.y  x.y Đó là công thức cần tìm. Ví dụ. Cho hàm Boole f(x,y,z) có bảng chân trị như sau: x y z f 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 Hãy thiết lập công thức biểu diễn của hàm f. Giải. Đầu tiên ta xác định các nguyên tử tương ứng với các dòng mà tại đó giá trị của f bằng 1. Do f có giá trị bằng 1 tại 4 dòng nên ta chọn 4 nguyên tử tương ứng với 4 dòng đó: f 0 x.y.z , f1 x.y.z , f5 x.y.z , và f 7 x.y.z Kế tiếp, nối chúng lại bằng phép hợp, ta được công thức của hàm f . Ta có : f (x, y, z) x.y.z  x.y.z  x.y.z  x.y.z Đó là công thức cần tìm. Công thức biểu diễn hàm Boole được xác định theo quy tắc trên được gọi là dạng nối rời chính tắc của nó. Sở dĩ ta nói đây là dạng nối rời vì nó được nối bởi phép nối rời – phép hợp và ta nói là chính tắc vì trong tất cả các số hạng (các nguyên tử) đều luôn có sự xuất hiện của tất cả các biến. Chú ý: Trang 41
  42. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM - Dạng nối rời chính tắc đôi khi còn được gọi là dạng tổng các tích vì trong công thức này ta lấy tổng (phép  ) của các số hạng là tích (phép  ) của các biến. - Dạng nối rời chính tắc có ưu điểm là dễ thiết lập, mặc dù vậy công thức này thường sẽ rất dài. 4.3 Bài toán mạch điện –Mạng các cổng Các hàm Boole có một sự tương ứng rất chặt chẽ với các mạch điện tử. Các hàm Boole nhận có các biến nhận giá trị 0 hoặc 1, và kết quả của hàm Boole cũng là giá trị 0 hoặc 1. Trong khi đó, cũng tương tự, mạch điện tử thường được thiết kế với nhiều đầu vào và một hoặc nhiều đầu ra, các đầu vào là các đường truyền tín hiệu chỉ nhận các giá trị nhị phân (0 hoặc 1), các đầu ra cũng là các đường tín hiệu nhị phân là tổ hợp các đầu vào theo một quy tắc nào đó. Như vậy, ta vậy ta có thể coi mỗi đầu ra của mạch điện tử tương ứng với một hàm Boole và các đầu vào chính là các biến của hàm Boole đó. f1 (x1,x2, ,xn) x1 f (x ,x x x2 . MẠCH ĐIỆN TỬ . 2 1 2, , n) . . . . xn fk(x1,x2, ,xn ) ĐẦU VÀO ĐẦU RA  Các cổng điện tử cơ bản. Trong hàm Boole, chúng ta sử dụng các phép toán trên đại số Boole B={0,1} để biểu diễn. Như đã nói ở trên, ở các mạch điện, các đầu ra sẽ là một tổ hợp các đầu vào. Cũng tương tự như hàm Boole – các biến được nối với nhau bằng các phép toán – các đầu vào cũng được liên kết với nhau thông qua các cổng cơ bản. Và hơn nữa, các cổng cơ bản này cũng hoàn toàn tương ứng với các phép toán trên đại số Boole B={0,1}. x x y x  y y x  y Cổng AND Cổng OR x x x Cổng NOT Trang 42
  43. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Dễ thấy rằng cổng AND sẽ tương ứng với phép toán  , cổng OR sẽ tương ứng với phép toán  , còn cổng NOT sẽ tương ứng với phép lầy phần tử bù. Từ những sự tương ứng giữa mạch điện tử với hàm Boole ở trên, ta thấy rằng việc thiết kế các mạch điện tử cũng sẽ tương ứng với việc xây dựng các hàm Boole. Chẳng hạn, xét ví dụ sau: Ví dụ. Xây dựng mạch cộng 2 bit. Mạch cộng 2 bit sẽ thực hiện phép cộng 2 bit x và y, kết quả thu được sẽ là 2 giá trị nhị phân S (tổng) và C (nhớ). Sở dĩ ta phải dùng thêm giá trị C vì trong trường hợp x=1, y=1 thì S không đủ để biểu diễn kết quả (1+1 bằng 0, nhớ 1). Như vậy mạch cộng 2 bit sẽ có 2 đầu vào x, y và 2 đầu ra là S và C. Bảng chân trị mô tả yêu cầu và quan hệ giữa đầu ra với các đầu vào như sau: x y S C 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Hai đầu ra S và C sẽ được biểu diễn bằng 2 hàm Boole theo 2 biến x và y. Áp dụng quy tắc tìm dạng nối rời chính tắc của hàm Boole, ta có công thức của 2 hàm Boole biểu diễn S và C là: S f (x, y) x.y  x.y C g(x, y) x.y Từ đó, mô hình mạch cộng 2 bit sẽ như sau: x C y x.y S x.y Ví dụ. Trong một trận thi đấu võ thuật có 3 trọng tài sẽ cho điểm các đòn đánh được thực hiện trong một trận đấu. Mỗi trọng tài sẽ có một nút bấm để chấm điểm các đòn đánh. Mỗi đòn đánh sẽ được tính điểm nếu có từ 2 trọng tài bấm nút trở lên. Mạch điện dùng cho việc chấm điểm này sẽ gồm có 3 đầu vào tương ứng với 3 nút bấm của các trọng tài. Nếu trọng tài nào bấm nút thì tín hiệu 1 từ đường dây đó sẽ được truyền vào mạch, nếu không bấm thì tín hiệu trên đường dây vẫn là 0. Đầu ra của mạch sẽ là một tín hiệu nhị phân (0/1) thể hiện việc đòng đánh đó có được tính điểm hay không. (0 – không tính điểm, 1 – tính điểm). Gọi f là hàm Boole thể hiện tín hiệu đầu ra, bảng chân trị của f theo mô tả trên sẽ như sau: x y z f Trang 43
  44. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Theo quy tắc xây dựng dạng nối rời chính tắc của hàm Boole, ta có công thức của hàm Boole f là: f (x, y, z) x.y.z  x.y.z  x.y.z  x y z Từ đó, mạch điện được thiết kế như sau: x y x.y.z z x.y.z f x.y.z x.y.z Thông qua các ví dụ trên, chúng ta thấy rằng việc xây dựng công thức của hàm Boole liên quan mật thiết đến việc xây dựng các mạch điện tử. Với việc xây dựng được công thức dạng nối rời chính tắc của các hàm Boole, ta đã có một cơ sở lý thuyết và một công cụ hữu dụng cho việc thiết kế các mạch điện. 4.4 Tìm công thức đa thức tối tiểu – Phương pháp Karnaugh Như ta đã thấy ở trên mô hình các mạch điện được thiết kế dựa theo công thức của hàm Boole (các cổng đều tương ứng với các phép toán). Mặt khác, cũng cần để ý rằng, đối với một hàm Boole, có thể có nhiều dạng công thức biểu diễn khác nhau. Công thức dạng nối rời chính tắc của một hàm Boole, như phân tích ở trên, rất dễ thiết lập, tuy vậy trong thực tế, công thức dạng nối rời chính tắc không phải là công thức dạng ngắn nhất của một hàm Boole. Trang 44
  45. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Đối với mục đích thiết kế mạch điện, công thức hàm Boole càng ngắn thì mạch điện thiết kế sẽ có chi phí càng thấp (do sử dụng ít cổng điện tử). Chính vì thế, ta cần phải tìm công thức hàm Boole dưới dạng ngắn nhất có thể. Có nhiều phương pháp khác nhau nhằm rút gọn công thức của hàm Boole như: sử dụng các tính chất của đại số Boole biến đổi, rút gọn mỗi phương pháp có những ưu khuyết riêng và sẽ hữu dụng cho một số trường hợp nào đó. Trong phần này chúng ta sẽ giới thiệu phương pháp Karnaugh, một phương pháp hữu hiệu cho việc tìm công thức dạng đơn giản nhất của hàm Boole có 3 hoặc 4 biến. Trước hết, ta tìm hiểu khái niệm biểu đồ Karnaugh của một hàm Boole f. Định nghĩa. Cho hàm Boole f theo n biến. Biểu đồ Karnaugh của hàm f là một hình chữ nhật gồm 2n ô sao cho: - Mỗi ô sẽ tương ứng với một dòng trong bảng của f. - Một ô sẽ được đánh dấu nếu và chỉ nếu tại dòng tương ứng với nó trong bảng chân trị, giá trị của f bằng 1. - Các ô được cho tương ứng với các dòng sao cho hai dòng tương ứng với hai ô cạnh nhau luôn sai khác nhau về giá trị của chỉ một biến duy nhất. Cụ thể, hình vẽ sau đây là cách tổ chức biểu đồ Karnaugh cho một hàm Boole theo 3 biến. x x z (1) (2) z y y y Các ô được xác định tương ứng với các dòng dựa vào cách đánh địa chỉ của các biến như trong hình vẽ. Chẳng hạn như ô (1) có địa chỉ là x.y.z , do đó, nó sẽ tương ứng với dòng {x=0,y=0,z=0} trong bảng chân trị. Hoặc, ô (2) có địa chỉ là x.y.z và nó tương ứng với dòng {x=0,y=1,z=0}. Rõ ràng ô (1) và (2) là hai ô cạnh nhau và nó cũng tương ứng với hai dòng trong bảng chân trị chỉ sai khác nhau giá trị của biến y. Chú ý: - Có nhiều cách bố trí vị trí của các biến khác nhau, miễn sao phải đảm bảo được những yêu cầu của một biểu đồ Karnaugh. - Hai ô nằm biên vẫn được coi là hai ô cạnh nhau (tưởng tượng rằng biểu đồ Karnaugh được cuốn lại). Chẳng hạn như trong biểu đồ trên, ô (1) và ô có địa chỉ x.y.z (góc trên bên phải) vẫn được coi là hai ô nằm cạnh nhau. Ví dụ. Hàm Boole f theo 3 biến có bảng chân trị: Trang 45
  46. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM x y z f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Khi đó, biểu đồ Karnaugh của hàm Boole f này như sau: x x z z y y y Rõ ràng, chúng ta thấy rằng, trong bảng chân trị có bao nhiêu dòng bằng 1 thì biểu đồ Karnaugh có bấy nhiêu ô được đánh dấu, và ngược lại. Hơn thế nữa, bảng chân trị và biểu đồ Karnaugh thực ra là “bản sao” của nhau. Nếu ta có bảng chân trị thì ta dễ dàng xây dựng được biểu đồ Karnaugh và tương tự nếu ta đã có biểu đồ Karnaugh thì hoàn toàn có thể xây dựng lại bảng chân trị. Định nghĩa. Cho biểu đồ Karnaugh của một hàm Boole f theo n biến. Ta định nghĩa: a. Một tế bào là một hình chữ nhật gồm 2k ( 0 k n ) ô được đánh dấu liền nhau. b. Một tế bào lớn là một tế bào mà không bị phủ bởi bất cứ tế bào nào khác. Ví dụ. Xét biểu đồ Karnaugh trong ví dụ trên, ta thấy: - Các tế bào: x.y.z , x.y.z , x.y.z , x.y.z (tế bào 1 ô), xy, yz, xz (tế bào 2 ô) - Các tế bào lớn: xy, yz, xz. Như đã nói ở phần đầu của mục này, mục đích của chúng ta là tìm công thức đa thức tối tiểu (công thức đa thức dạng đơn giản nhất) của hàm Boole. Sau đây chúng ta sẽ khảo sát phương pháp Karnaugh để thực hiện điều này.  Phương pháp Karnaugh tìm công thức đa thức tối tiểu của hàm Boole. Trang 46
  47. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Cho hàm Boole f (dưới dạng công thức hoặc bảng chân trị), để tìm công thức đa thức tối tiểu của f , ta thực hiện theo các bước sau: Bước 1. Xây dựng biểu đồ Karnaugh của f Bước 2. Xác định tất cả các tế bào lớn trong biểu đồ Karnaugh vừa xây dựng Bước 3. Tìm một số lượng ít nhất các tế bào lớn để phủ kín các ô đã đánh dấu trong biểu đồ Karnaugh, ghép chúng lại với nhau bằng phép  , ta sẽ được công thức đa thức tổi tiểu cần tìm. Ví dụ: Cho hàm Boole f có bảng chân trị dưới đây. Hãy tìm công thức đa thức tối tiểu của f. x y z f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Bước 1. Xây dựng biểu đồ Karnaugh của hàm f: x x z y y y Bước 2. Xác định tất cả các tế bào lớn: xy, yz, xz Bước 3. Tìm một số lượng ít nhất các tế bào lớn để phủ các ô đã được đánh dấu. Tưởng tượng rằng chúng ta có thể tách riêng các tế bào lớn, khi đó hình ảnh về các tế bào lớn như sau: x x x x x x z z z z z z y y y y y y y y y Tế bào lớn xy Tế bào lớn yz Tế bào lớn xz Trang 47
  48. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Như vậy thực chất việc chọn các tế bào lớn để phủ kín các ô được đánh dấu trong biểu đồ Karnaugh chính là việc chọn các tế bào lớn rồi xếp chồng chúng lên nhau sao cho hình thu được giống biểu đồ Karnaugh ban đầu. Trong ví dụ trên, rõ ràng là trong trường hợp này, ta phải chọn cả 3 tế bào lớn. Như vậy, công thức đa thức tối tiểu của hàm f này sẽ là: f xy  yz  xz Ví dụ: Cho hàm Boole f (x, y, z) x.y.z  x.y  x y z . Hãy tìm công thức đa thức tối tiểu của f. Bước 1. Xây dựng biểu đồ Karnaugh của hàm f. Trong trường hợp này, ta được cung cấp bảng chân trị của hàm f. Chúng ta có thể lập bảng chân trị của f rồi thực hiện như đã làm ở ví dụ trước. Mặc dù vậy, một cách nhanh chóng hơn, ta có thể xây dựng biểu đồ Karnaugh trực tiếp từ công thức trên. Dễ thấy rằng, các thành phần của công thức trên tương ứng với 3 tế bào: x x x x x x z z z z z z y y y y y y y y y Tế bào x.y.z Tế bào x.y Tế bào x.y.z Đặt chồng các tế bào này lên nhau, ta sẽ được biểu đồ Karnaugh của hàm f ban đầu: x x z z y y y Bước 2. Xác định tất cả các tế bào lớn: x.z, x.y, y.z Bước 3. Tìm một số lượng ít nhất các tế bào lớn để phủ các ô đã được đánh dấu. Tương tự như ví dụ trước, để dễ hình dung, ta tách riêng các tế bào lớn: x x x x x x z z z z z z y y y y y y y y y Tế bào lớn x.z Tế bào lớn x.y Tế bào lớn y.z Trang 48
  49. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Mặc dù có 3 tế bào lớn, nhưng trong trường hợp này, để phủ kín các ô đã đánh dấu trong bản đồ Karnaugh, ta chỉ cần chọn 2 tế bào lớn: x.z và y.z . Như vậy, công thức đa thức tối tiểu của hàm f này sẽ là: f x.z  y.z Đối với hàm Boole theo 4 biến, biểu đồ Karnaugh sẽ bao gồm 16 ô được sắp xếp như dưới đây: x x t z t z t y y y và phương pháp tiến hành tìm công thức đa thức tối tiểu cũng tương tự như đối với hàm 3 biến. Chú ý: Đối với biểu đồ Karnaugh của hàm Boole 4 biến, hai ô ở trên cùng và dưới cùng (của cùng một cột) vẫn được coi là cạnh nhau, 4 ô ở 4 góc vẫn được coi là cạnh nhau. Điều này là bởi vì biểu đồ Karnaugh có thể được gấp lại theo cả 2 chiều ngang và dọc. Ví dụ: Tìm công thức đa thức tối tiểu của hàm Boole sau: f (x, y, z,t) x.y tz  x y tz  x.y tz  x.y tz  x y tz  x y tz  x.y tz Bước 1. Tương tự như hàm Boole với 3 biến, ta có biểu đồ Karnaugh của hàm Boole trên như sau: x x t z t z t Bước 2. Xác định các tế bào ylớn: cóy 3 tếy bào lớn: x x x x x x t t t z z z t t t z z z t t t y y y y y y y y y Tế bào lớn x.z Tế bào lớn y.z Tế bào lớn x.y.t Trang 49
  50. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM Bước 3. Tìm một số lượng ít nhất các tế bào lớn để phủ các ô đã được đánh dấu. Ở đây, dễ thấy là ta không thể bỏ tế bào lớn nào. Như vậy, công thức đa thức tối tiểu của hàm Boole ban đầu là: f (x, y, z,t) x.z  y.z  x. .ty Đến đây, chúng ta đã biết cách xây dựng công thức đa thức tối tiểu dựa trên phương pháp biểu đồ Karnaugh. Đây là một phương pháp cực kỳ hữu hiệu đối với các hàm Boole 3 hoặc 4 biến. Đối với các hàm nhiều biến hơn, phương pháp này khó thực hiện vì khi đó biểu đồ Karnaugh phải mở rộng ra không gian và điều này sẽ làm cho ta khó nhận biết các tế bào và tế bào lớn. Khi áp dụng phương pháp biểu đồ Karnaugh, cần lưu ý các điểm sau: - Vẽ biểu đồ Karnaugh phải tuyệt đối chính xác. Chỉ nhầm lẫn việc đánh dấu 1 ô sẽ dẫn tới kết quả hoàn toàn sai lệch trong những bước tiếp theo. - Việc xác định các tế bào lớn phải thận trọng, nếu xác định không chính xác các tế bào lớn thì công thức thu được cuối cùng có thể không phải là công thức dạng đơn giản nhất. (Do các tế bào lớn có nhiều ô hơn, nhưng số biến biểu diễn lại ít hơn). - Khi chọn các tế bào lớn để phủ các ô được đánh dấu cần ưu tiên chọn những tế bào lớn bắt buộc (không thể không chọn) trước. Với những ô được đánh dấu chỉ thuộc một tế bào lớn duy nhất thì tế bào lớn này bắt buộc phải được chọn. Bên cạnh đó khi có hai tế bào lớn cùng phủ qua một ô thì ta ưu tiên chọn tế bào lớn có nhiều ô hơn để phủ. Trang 50
  51. Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM TÀI LIỆU THAM KHẢO [1]. Nguyễn Đức Nghĩa – Nguyễn Tô Thành, Toán rời rạc, NXB Đại học Quốc Gia Hà Nội, 2003. [2]. Kenneth H.Rosen – Toán rời rạc ứng dụng trong Tin học (Bản dịch), NXB Khoa học và Kỹ thuật, 2000. [3]. Nguyễn Hữu Anh, Toán rời rạc, NXB Giáo dục, 2000. [4]. Hoàng Chúng , Đại cương về Toán học hữu hạn, NXB Giáo Dục, 1999. Trang 51