Tin Tức

Công Thức Toán Rời Rạc 1 – (Pdf) Một Số Kiến Thức Cơ Bản Toán Rời Rạc 1

Tài liệu Tóm tắt bài giảng môn Toán rời rạc do Nguyễn Ngọc Trung biên soạn có cấu trúc gồm 4 chương cung cấp cho người đọc các kiến thức: Mệnh đề, phép đếm, quan hệ, đại số Boole. Mời các bạn cùng tham khảo nội dung chi tiết.

Đang xem: Công thức toán rời rạc

*

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ônTOÁN RỜI RẠC Giảng viên biên soạn: Nguyễn Ngọc Trung TP.HCM 9.2006 MỤC LỤCChươ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……………………………………………………………….. 14Chươ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) …………………. 23Chươ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 ……………………………………………… 26Chươ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 …………… 44TÀI LIỆU THAM KHẢO……………………………………………………………….. 51Tó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ất1.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 P  Q (đọc là “P và Q”. Chân trị của P  Q 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 P  Q 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à: P  Q = “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 3Tó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 P Q 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 P  Q (đọc là “P hay Q”. Chân trị của P  Q 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 P  Q 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à P  Q = “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ì P  Q sẽ sai. Bảng chân trị của phép nối rời: P Q PQ 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 4Tó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 11.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ácbiế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 chobiế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 5Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCMVí 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ộthằ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ếuE  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áctươ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 6Tó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  pVí 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  11.1.3 Các quy tắc suy diễnTrong 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ạngmệnh đề  p1  p2    pn   q là một hằng đúng, trong đó p1 , p2 ,…, pn , q là cácdạng mệnh đề theo một số biến logic nào đó. Trang 7Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCMVí 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ốnvậ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 đichơ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  rTa phải chứng minh dạng mệnh đề sau là một hằng đúng:  p  r    q  p   r   qTa 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òngcủ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áctiề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 qSau đây là một số quy tắc suy diễn thường dùng mà chân lý của nó có thể đượckiể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 8Tó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 9Tó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ợpf(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ếtcho 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ễnhay 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 đượctrả 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 10Tó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 pSuy 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 DeMorgan) 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ếnx,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 11Tó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óacủ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  .

Xem thêm: Thu Em Can, Pt – Thứ Em Cần (Part 2)

Xem thêm: Hãy Nói Lời Yêu Tập 19 Vtv3: Ông Tín Đòi Dắt 2 Con 'Bỏ Trốn'

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 12Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCMCâ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óicá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ừ theonhiề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ằngcá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ởilượ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 13Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM1.3 Nguyên lý quy nạpNguyê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ácbướ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ằnggiá 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 minhp(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ó: 0  1  …  n  (n  1)  n(n  1)  (n  1)   n  1 (n  1)  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 14Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM 2 Chương 2. Phép đếm2.1 Tập hợp – Tính chấtTrong 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ộtsố 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óirõ 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 quacá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ợpA, 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ệubở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. A  x   x 2  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ạnnhư 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 Achứ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ántrê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 ) A  B   x  U ( x  A)  ( x  B) A   x  U x  A Trang 15Tó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  B =B  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 A U  A vi. Phần bù: A A U A A   vii. Tính thống trị: A U  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  AChứ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 A  A A i 1 i 1 2  …  An nvà A  A A i 1 i 1 2  …  An Trang 16Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCM2.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ộtphần tử x  A sao cho f(x)=y. Như thế, tương ứng y  x là một ánh xạ từ B vào Amà 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ợph là ánh xạ từ A vào C được xác định bởi: Trang 17Tó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ủaA, 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 ) iii. f 1 ( F1  F2 )  f 1 ( F1 )  f ( F2 ) iv. f 1 ( F1  F2 )  f 1 ( F1 )  f ( F2 )2.3 Giải tích tổ hợpPhé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ộttậ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ó. Địnhnghĩ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áchloạ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: đibằ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: đibằ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 18Tóm tắt bài giảng Toán rời rạc Trường ĐHSP TP.HCMNguyê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ó: A1  A2  …  An  N1  N 2  …  (1) n1 N ntrong đó 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 CNguyê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ếpnhau: k1, k2, …, kn. Mỗi giai đoạn ki có ti cách để thực hiện. Như vậy sẽ có t1.t2…tncá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 đôigià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àylự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à A  B là tập hợp tất cả cáccặ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ằngnhau 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ì A  B cũng là tập hợp hữu hạn và tacó: A B  A . B2.3.2 Giải tích tổ hợpHoá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ếpchú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ôngviệ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ácbướ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 19Tó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ánvị 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, 5là 5! = 120 cách.Hoán vị lặpHoá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ị. Tuynhiê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ánvị 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ựcchấ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áchchọ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à: Ank  (n  k )!Chứng minh. Dùng nguyên lý nhân. Trang 20

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Back to top button