Bài giảng Toán rời rạc - Cơ sở logic - Trần Nguyễn Minh Thư

Nội dung text: Bài giảng Toán rời rạc - Cơ sở logic - Trần Nguyễn Minh Thư

1. 1 TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT & TRUYỀN THễNG BỘ MễN KHOA HỌC MÁY TÍNH TOÁN RỜI RẠC (DISCRETE MATHEMATICS) 08/2013 GV: Trần Nguyễn Minh Thư (tnmthu@ctu.edu.vn)
2. 2 CƠ SỞ LOGIC
3. 3 PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ tnmthu@cit.ctu.edu.vn 7/17/2016
4. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Định nghĩa: Mệnh đề là một cõu khẳng định cú giỏ trị chõn lý xỏc định đỳng (True) hoặc sai (False). Vớ dụ: True  2+3=5  Tam giỏc đều cú 3 cạnh bằng nhau True  Toronto là thủ đụ của Canada False  3*4=10 False 4
5. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ 5  P, Q, R, S, : cỏc ký hiệu mệnh đề  Ký hiệu giỏ trị chõn lý của mệnh đề:  T: Đỳng  F: Sai  Bảng chõn trị: biểu diễn mối quan hệ giữa những giỏ trị chõn lý của cỏc mệnh đề
6. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ Cỏc phộp tớnh mệnh đề  Phộp phủ định: Cho P là một mệnh đề, cõu “khụng phải là P” là một mệnh đề được gọi là phủ định của mệnh đề P. Kớ hiệu: ơP hay P  Bảng chõn trị P ơP TTF FFT 6
7. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ 7  Phộp hội (conjunction): Cho hai mệnh đề P, Q. “P và Q” là một mệnh đề được gọi là hội của 2 mệnh đề P và Q.  Kớ hiệu: PQ  Bảng chõn trị: PQPQ TTTT TFF FTF FFF
8. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ 8  Phộp tuyển (disjunction): “P hay Q” là một mệnh đề được gọi là tuyển của 2 mệnh đề P và Q. Kớ hiệu: P  Q  Bảng chõn trị: PQPQ TTT TFT FTT FFF
9. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ 9  Phộp XOR: “loại trừ P hoặc loại trừ Q”, nghĩa là “hoặc là P đỳng hoặc Q đỳng”.  Bảng chõn trị PQPQ PQ = (P  Q)  ơ(P  Q) TTF TFT FTT FFF
10. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ 10  Phộp kộo theo: “Nếu P thỡ Q” là một mệnh đề kộo theo của hai mệnh đề P, Q.  Bảng chõn trị: PQPđQ P đ Q = ơP  Q TTT TFF FTT FFT
11. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Mệnh đề đảo và mệnh đề phản đảo  Cỏc mệnh đề kộo theo khỏc của mệnh đề P đ Q:  Q đ P: mệnh đề đảo  ơQ đ ơP: mệnh đề phản đảo 11
12. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ 12  Phộp tương đương: “P nếu và chỉ nếu Q” là một mệnh đề được gọi là P tương đương Q.  Bảng chõn trị: PQPQ P  Q = (P đ Q)  (Q đ P) TTT TFF FTF FFT
13. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Cho P, Q, R, là cỏc mệnh đề. Nếu cỏc mệnh đề này liờn kết với nhau bằng cỏc phộp toỏn thỡ ta được một biểu thức mệnh đề. Chỳ ý: - Một mệnh đề cũng là một biểu thức mệnh đề. - Nếu P là một biểu thức mệnh đề thỡ ơP cũng là biểu thức mệnh đề - Chõn trị của biểu thức mệnh đề là kết quả nhận được từ sự kết hợp giữa cỏc phộp toỏn và chõn trị của cỏc biến mệnh đề. 13
14. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ 14  Hằng đỳng: là một mệnh đề luụn cú chõn trị là đỳng Vớ dụ: ơP  P P ơP ơP P T F T F T T  Hằng sai: là một mệnh đề luụn cú chõn trị là sai Vớ dụ: ơP  P P ơP ơP  P T F F F T F
15. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Tiếp liờn: là một mệnh đề khụng phải là hằng đỳng và khụng phải là hằng sai. Vớ dụ: (P  Q )  (ơQ) PQ ơQ P Q (P  Q )  (ơQ) TTFTT TFTFT FTFFF FFTFT 15
16. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Mệnh đề hệ quả: Cho F và G là 2 biểu thức mệnh đề. G là mệnh đề hệ quả của F hay G được suy ra từ F nếu F đ G là hằng đỳng. Kớ hiệu: FG  Tương đương logic:  Định nghĩa 1: Mệnh đề P và Q được gọi là tương đương logic nếu phộp tương đương của P và Q là hằng đỳng.  Định nghĩa 2: Hai mệnh đề P và Q được gọi là tương đương logic nếu và chỉ nếu chỳng cú cựng chõn trị. 16
17. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Cỏc quy tắc tương đương logic: Đặt T= hằng đỳng, F = hằng sai PTT = Luật thống trị PFF = PTP = Luật trung hũa PFP = PPP = Luật lũy đẳng PPP = P = P Luật phủ định của phủ định 17
18. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Cỏc quy tắc tương đương logic: Đặt T= hằng đỳng,F = hằng sai PPT = Luật về phần tử bự PPF = PQQP =  Luật giao hoỏn PQQP =  ()()PQRPQR  =   Luật kết hợp ()()PQRPQR  =   P (Q  R) = (P  Q)  (P  R) Luật phõn phối P (Q  R) = (P  Q)  (P  R) 18
19. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Cỏc quy tắc tương đương logic: Đặt T= hằng đỳng, F = hằng sai PQPQ =  Luật De Morgan PQPQ =  P(PQ)P  = Luật hấp thụ P(PQ)P  = PQPQđ =  Luật về phộp kộo theo 19
20. PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Vị 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 A, B, cho trước, sao cho:  Bản thõn P(x,y, ) khụng phải là mệnh đề.  Nếu thay x, y, bằng những giỏ trị cụ thể thuộc tập hợp A, B, cho trước ta sẽ được một mệnh đề P(x, y, ). Cỏc biến x, y, được gọi là cỏc biến tự do của vị từ.  Vớ dụ: P(n) = {n là chẵn}  n = 2: {2 là chẵn}: True  n = 5: {5 là chẵn}: False 20
21. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Khụng gian của vị từ: cú thể xem vị từ như là một ỏnh xạ P,  x E ta được một ảnh P(x) {0, 1}. Tập hợp E này được gọi là khụng gian của vị từ.  Trọng lượng của vị từ: số biến của vị từ  Vớ dụ:  P(a,b) = {cặp số nguyờn tương ứng thỏa a + b = 5}  Khụng gian của vị từ: Số nguyờn  Trọng lượng: 2 21
22. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Cho trước cỏc vị từ P(x), Q(x) theo một biến x A. Ta cú cỏc phộp toỏn vị từ tương ứng như trờn phộp tớnh mệnh đề.  Phủ định ơP(x)  Phộp hội P(x)  Q(x)  Phộp tuyển P(x)  Q(x)  Phộp XOR P(x)  Q(x)  Phộp kộo theo P(x) đ Q(x)  Phộp tương đương P(x)  Q(x) 22
23. 1.Mệnh đề 2.Vị từ PHẫP TÍNH MỆNH ĐỀ & VỊ TỪ  Định nghĩa: Cho P(x) là một vị từ cú khụng gian là A. Cỏc mệnh đề lượng tử húa (quantified statement) của P(x) như sau:  Mệnh đề “Với mọi x thuộc A, P(x) ”, kớ hiệu bởi “ x A, P(x)”, là mệnh đề đỳng  P(a) luụn đỳng với mọi giỏ trị a A.  Mệnh đề “Tồn tại một x thuộc A, P(x))” kớ hiệu bởi : “ x A, P(x)”, là mệnh đề đỳng khi và chỉ khi cú một giỏ trị x = a nào đú sao cho mệnh đề P(a) đỳng. 23
24. BÀI TẬP 24  Khụng lập bảng chõn trị, sử dụng cỏc tương đương logic để chứng minh rằng : (P  Q) đ Q là hằng đỳng. (P Q) đ Q = P  Q  Q = (P  Q)  Q = P  (Q  Q) = P  T = T
25. BÀI TẬP 25  Bằng biến đổi tương đương, chứng minh cỏc biểu thức mệnh đề sau là hằng đỳng  (PQ)đP (PQ)đP = ơ (PQ) v P = (ơP v ơQ) v P = ơP v P v ơQ = T v ơQ = T  Pđ(ơPđP) P đ (PvP) = P đ P = ơP v P = T
26. BÀI TẬP 26  Bằng biến đổi tương đương, chứng minh cỏc biểu thức mệnh đề sau là hằng đỳng  Pđ(Qđ(PQ)) Pđ(ơQ v (P ^ Q) = Pđ((ơQvP)^( ơQvQ) = Pđ((ơQvP)^T = Pđ((ơQvP) = ơPv (ơQvP) = ơP v ơQ v P = ơP v P v ơQ = T v ơQ = T (hằng đỳng)
27. BÀI TẬP 27  Chứng minh biểu thức mệnh đề (((r  q)  q)  p) ((p  q) đ (p  q  r)) là hằng sai ((r  q)  q)  p ≡ q  p ≡ (p  q) (p  q) đ (p  q  r)  (p  q)  (p  q  r)  (p  q)  (p  q  r)  p  q (((r  q)  q)  p) ((p  q) đ (p  q  r))  (p  q)(p  q)  F
28. BÀI TẬP 28  Chứng minh biểu thức mệnh đề sau là hằng sai p  (p  q)  (p  r)  (((q đ r)  (q  (r  s)  (r  s)))  p) p  (p  q)  (p  r)  (p  (p  q)  (p  r)) ≡ p ((q đ r)  (q  (r  s)  (r  s)))  p ≡ ((q  r)  (q  (r  (s  s))))  p ≡ ((q  r)  (q  r))  p  p (p  (p  q)  (p  r))  (p  ((q đ r)  (q  (r  s)  (r  s))))  pp  F
29. BÀI TẬP 29  Chứng minh biểu thức mệnh đề sau là hằng sai (((p  q)  (p  q))  q  (r  q))  ((p đ q)  (q  (r  q))) ((p  q)  (p  q))  q  (r  q)  (p  (q  q))  q  p  q (p đ q)  (q  (r  q)) ≡ (p  q)  q ≡ (p  q)  (q  q) ≡ p  q  (p  q) (((p  q)  (p  q))  q)  ((p đ q)  (q  (r  q)))  (p  q)  (p  q)  F
30. BÀI TẬP 30 Chứng minh biểu thức mệnh đề (p  q)  (p  q)  q tương đương với biểu thức (p đ q)  (q  (r  q)) (p  q)  (p  q)  q ≡ (p  q)  (p  q)  q ≡ (p  (q  q))  q ≡ p  q (1) (p đ q)  (q  (r  q)) ≡ (p  q)  q ≡ (p  q)  (q  q) ≡ (p  q)  F ≡ p  q (2) (1) & (2) (p  q)  (p  q)  q tương đương (p đ q)  (q  (r  q))
31. BÀI TẬP 31 Chứng minh biểu thức mệnh đề (((r  q)  q)  p) tương đương với biểu thức (p  q) đ (p  q  r) (((r  q)  q)  p) ≡ (q  p) ≡ p  q (1) (p  q) đ (p  q  r)  (p  q)  (p  q  r)  (p  q)  (p  q  r)  p  q (2) (1)& (2) (((r  q)  q)  p) tương đương (p  q) đ (p  q  r)
32. BÀI TẬP 32 Chứng minh biểu thức mệnh đề p  ((p  q)  (p  r)) tương đương với biểu thức mệnh đề p  ((q đ r)  (q  (r  s)  (r  s))) p  ((p  q)  (p  r)) ≡ p  (p  (q  r)) ≡ p (1) p  ((q đ r)  (q  (r  s)  (r  s))) ≡ p  ((q  r)  (q  (r  (s  s))))  p  ((q  r)  (q  r))  p (2) (1) & (2) hai mệnh đề là tương đương
33. QUY TẮC SUY LUẬN 33  Cỏc quy tắc suy luận: Quy tắc Hằng đỳng Tờn P P đ (P  Q) Cộng PQ PQ P  Q đ P Rỳt gọn P PPQ, đ (P  (P đ Q)) đ Q Modus ponens Q QPQ, đ (ơQ  (P đQ)) đ ơP Modus tollens P PQQRđ , đ ((P đQ) (Q đ R)) đ (P đ R) Tam đoạn luận giả P đ R định PPQ,  Q (ơP  (P  Q)) đ Q Tam đoạn luận tuyển
34. QUY TẮC SUY LUẬN  Vớ dụ : Dựng cỏc quy tắc suy luận chứng minh rằng : (Pđ (Q đ R))  (Q  P)  P R  Giải: 1.P đ (Q đ R) 2.Q P P.3 4.Qđ R : Modus Ponens của 1 và 3 Q.5 : Tam đoạn luận tuyển của 2 và 3 R.6 : Modus Ponens của 4 và 5 34
35. BÀI TẬP 35 Dựng quy tắc suy luận chứng minh rằng (p đ (q đ r))  (t  r)  (s đ (p  q))  (p đ t)  (s  u) u (p đ (q đ r))  (t  r)  (s đ (p  q))  (p đ t)  (s  u) ≡ (p đ (q đ r))  t  r  (s đ p)  (s đ q)  (p đ t)  (s  u) 1. p đ (q đ r) 2. t 3. r 4. s đ p 5. s đ q 6. p đ t 7. s  u
36. BÀI TẬP 36 1. p đ (q đ r) 2. t 3. r 4. s đ p 5. s đ q 6. p đ t 7. s  u 8. p modus tollens của 2. & 6. 9. q đ r modus ponens của 8. & 1. 10. q modus tollens của 9. & 3. 11. s modus tollens của 10. & 5 12. u tam đoạn luận tuyển 11. & 7.
37. BÀI TẬP 37 Dựng quy tắc suy luận chứng minh rằng ((p  q) đ r)  s  t  p  (p đ (u đ q))  (s đ (r  t)) u 1. (p  q) đ r 2. s 3. t 4. p 5. p đ (u đ q) 6. s đ (r  t)
38. BÀI TẬP 38 1. (p  q) đ r 2. s 7. u đ q modus ponens của 4. & 5. 3. T 8. r  t modus ponens của 2. & 6. 4. p 9. r tam đoạn luận tuyển của 8. & 3. 5. p đ (u đ q) 10. (p  q) modus tollens của 9. & 1. 6. s đ (r  t) 11. p  q de Morgan của 10. 12. q tam đoạn luận tuyển của 4. & 11. 13. u modus tollens của 12. & 7.
39. Chứng minh quy nạp 39
40. Chứng minh quy nạp  Phương phỏp chứng minh:  n, n0 là số tự nhiờn. 1. Kiểm chứng P(n) đỳng với n=n0 40
41. Chứng minh quy nạp  Phương phỏp chứng minh:  n, n0 là số tự nhiờn. 1. Kiểm chứng P(n) đỳng với n=n0 2. Giả sử P(n) đỳng với n: n0 ≤ n ≤ k 3. Chứng minh P(n) đỳng với n=k+1 41
42. Chứng minh quy nạp  Phương phỏp chứng minh  n, n0 là số tự nhiờn. 1. Kiểm chứng P(n) đỳng với n=n0 2. Giả sử P(n) đỳng với n: n0 ≤ n ≤ k 3. Chứng minh P(n) đỳng với n=k+1 4. Kết luận n ≥ n0 P(n) là đỳng 42
43. Chứng minh quy nạp  Vớ dụ 1: n ≥ 1 là số nguyờn. CMR: n n(n 1) P(n) :  i= 1 2 3 n = i= 1 2 43
44. Chứng minh quy nạp 1- Kiểm chứng với n=1 n( n 1) 1(1 1) VT = 1 VP = = =1 Vậy P(n) đỳng với n = 1 2 2 2- Giả sử P(n) đỳng với n = k > 1 k( k 1) 1 2 3 k = 2 3- CM P(n) đỳng với n = k + 1 k( k 1) 1 2 3 k ( k 1) = (k 1) 2 k( k 1) 2( k 1) 1 2 3 k ( k 1) = 2 (k 1)( k 2) 1 2 3 k ( k 1) = 2 =>P(k+1) đỳng 44
45. Chứng minh quy nạp  Vớ dụ 2: n ≥ 1 là số nguyờn. Tỡm cụng thức tớnh tổng n số lẻ đầu tiờn và chứng minh cụng thức đú. n (2i 1) = 1 3 5 (2 n 1) = n2 i=1 45
46. Chứng minh quy nạp 46 1- Kiểm chứng với n=1 VT = 1 VP = n2 = 12 = 1 Vậy P(n) đỳng với n = 1 2- Giả sử P(n) đỳng với n = k > 1 1 3 5 (2k 1) = k 2 3- CM đỳng với n = k + 1 1 3 5 (2k 1) (2 k 1) = k2 (2 k 1) 1 3 5 (2k 1) (2 k 1) = ( k 1)2 => P(k+1) đỳng
47. Bài tập 47 Bằng phương phỏp chứng minh quy nạp, chứng minh rằng : với mọi số nguyờn dương n, 7n + 3n – 1 chia hết cho 9 n = 1: 7 + 3 – 1 = 9 chia hết cho 9 giả sử với n = k > 1: 7k + 3k – 1 chia hết cho 9 phải CM: 7k+1 + 3(k+1) – 1 chia hết cho 9 thật vậy: 7k+1 + 3(k+1) – 1 = 7(7k + 3k – 1) – 18k + 9 chia hết cho 9
48. Bài tập 48 Bằng phương phỏp chứng minh quy nạp, chứng minh rằng : với mọi số nguyờn dương n, 7n + 3n – 1 chia hết cho 9 n = 1: 7 + 3 – 1 = 9 chia hết cho 9 giả sử với n = k 1: 7k + 3k – 1 chia hết cho 9 phải CM: 7k+1 + 3(k+1) – 1 chia hết cho 9 thật vậy: 7k+1 + 3(k+1) – 1 = 7(7k + 3k – 1) – 18k + 9 chia hết cho 9