›
›

Bài giảng Luận lý toán học - Chương 1: Tổng quan (Phần 2)

ppt 45 trang hapham 350
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Luận lý toán học - Chương 1: Tổng quan (Phần 2)", để 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:

  • pptbai_giang_luan_ly_toan_hoc_chuong_1_tong_quan_tiep_theo.ppt

Nội dung text: Bài giảng Luận lý toán học - Chương 1: Tổng quan (Phần 2)

  1. II. Suy luận tự nhiên trong luận lý mệnh đề ntsơn
  2. Chứng minh Thí dụ : Tam giác ABC có các cạnh là AB = 3, BC = 4, CA = 5. Chứng minh ABC vuông. Chứng minh : (1) cạnh AB = 3. (2) cạnh BC = 4. (3) cạnh CA = 5. (4) CA2 = BC2 + AB2. (5) Từ định lý Pythagore, tam giác ABC vuông. Chương 2 ntsơn
  3. Chứng minh • Chuỗi 5 phát biểu : (1) cạnh AB = 3 (2) cạnh BC = 4 (3) cạnh CA = 5 (4) CA2 = BC2 + AB2 (5) Từ đlý Pythagore, tam giác ABC vuông được gọi là một “chứng minh” theo nghĩa thông thường trong toán học. Chương 2 ntsơn
  4. Chứng minh Hệ thồng : Mã hóa {cạnh AB = 3, {F1, cạnh BC = 4, F2, cạnh CA = 5}. F3} Chứng minh : {tam giác ABC vuông}. H Chương 2 ntsơn
  5. Chứng minh • Công thức H được gọi là “được chứng minh” từ hệ thống F nếu viết ra được một “chứng minh” mà công thức cuối cùng trong chứng minh là H. • Chứng minh là chuỗi các công thức được viết ra dựa vào hệ thống và các qui tắc suy luận. • Qui tắc suy luận gồm : các qui tắc suy luận tự nhiên và các suy luận đã được chứng minh. Chương 2 ntsơn
  6. Qui tắc viết chuỗi công thức • Viết ra một công thức (trong chuỗi công thức) trên 1 dòng bằng cách : lấy một công thức từ hệ thống hoặc áp dụng các qui tắc suy luận. Với 2 cách trên, khi viết được dòng có nội dung là công thức cần chứng minh thì dừng. Chương 2 ntsơn
  7. Chứng minh • H được chứng minh từ F được ký hiệu là : (F ├─ H). • Ký hiệu (F ├─ H) được gọi là một sequent. F được gọi là tiền đề và H là kết luận. • Nếu sequent không có tiền đề thì kết luận H được gọi là định lý (├─ H). • Nếu F├─ G và F ─┤G thì ký hiệu là F ─┤├─ G hay F ≡ G Chương 2 ntsơn
  8. Suy luận tự nhiên[3] • Qui tắc giao i (i) dòng m : F dòng k : G dòng p : F  G Nếu có dòng m với nội dung F và dòng k với nội dung G thì có thể viết ra dòng mới p có nội dung là (F  G). Ghi chú : Ký hiệu i có nghĩa là introduction. Chương 2 ntsơn
  9. Suy luận tự nhiên[3] • Qui tắc giao e (e) dòng m : F  G dòng k : F dòng p : G Nếu đã có một dòng là (F  G) thì có thể viết ra dòng mới là F (hoặc G). Ghi chú : Ký hiệu e có nghĩa là elimination. Chương 2 ntsơn
  10. Suy luận tự nhiên[3] • Qui tắc điều kiện e (Modus ponens) (→e) dòng m : F → G dòng k : F dòng p : G Nếu có dòng F và dòng F → G thì viết được dòng mới G. * Từ modus ponens (MP) có nghĩa là affirming method. Chương 2 ntsơn
  11. Suy luận Chứng minh : P, Q, (P  Q) → (R  S) ├─ S. 1 P tiền đề 2 Q tiền đề 3 P  Q i 1, 2 4 P  Q → R  S tiền đề 5 R  S →e 3, 4 6 S e 5 Chương 2 ntsơn
  12. Suy luận tự nhiên[3] • Qui tắc điều kiện i (→i) dòng m : if F dòng m+k : nif G dòng m+k+1 : F→G Dòng m có nội dung là F (được chọn tùy ý), và thêm từ khóa ‘if’ trước công thức F. (dòng này có nghĩa là giả sử có F). Các dòng kế (m+1, , m+k) có thể sử dụng hay không sử dụng dòng m đều được coi như phụ thuộc vào sự hiện diện của giả thiết F. Chương 2 ntsơn
  13. Suy luận tự nhiên[3] • Qui tắc điều kiện i (tt) Để chấm dứt ảnh hưởng của giả thiết F ở dòng k thêm từ khóa ‘nif’ trước nội dung của dòng này. Việc đặt từ khoá nif trước dòng nào là tùy thuộc người chứng minh. Các dòng trong cấu trúc ‘if-nif’ có thể được xây dựng nhờ cả các dòng trên dòng m. Chương 2 ntsơn
  14. Suy luận tự nhiên[3] • Qui tắc điều kiện i (tt) Các dòng trong cấu trúc ‘if-nif’ không được sử dụng để xây dựng cho các dòng ngoài cấu trúc ‘if-nif’. Công thức trên dòng “nif” (ngay sau từ khóa nif) được qui ước là thuộc cấu trúc “if nif”. Sau cấu trúc ‘if-nif’ viết dòng kết hợp dòng ‘if’ và dòng ‘nif’ : F → G. Cấu trúc ‘if-nif’ có thể lồng vào nhau. Chương 2 ntsơn
  15. Suy luận[3] Chứng minh : F├─ G → F 1 if G 2 nif F tiền đề 3 G → F →i 1, 2 Chương 2 ntsơn
  16. Suy luận tự nhiên[3] • Qui tắc bản sao (id) dòng m : F dòng k : F chép lại công thức đã xuất hiện, nếu dòng k nằm trong phạm vi ảnh hưởng của dòng m. Chương 2 ntsơn
  17. Suy luận[3] Chứng minh ├─ F → F 1 if F 2 nif F bản sao của 1 3 F → F →i 1-2 Chương 2 ntsơn
  18. Suy luận[3] Chứng minh : ├─ (F → (G → F) 1 if F 2 if G 3 nif F bản sao 1 4 nif G → F →i 2, 3 5 F → (G → F) →i 1, 4 Chương 2 ntsơn
  19. Suy luận tự nhiên[3] • Qui tắc hội i (i) dòng m : F dòng k : F  G Nếu có dòng F thì viết được dòng mới F  G với G là công thức bất kỳ. Chương 2 ntsơn
  20. Suy luận tự nhiên[3] • Qui tắc hội e (e) dòng m : F  G dòng n : if F dòng n+p : nif H dòng k : if G dòng k+q : nif H dòng k+q+1 : H Nếu F sinh ra H và G cũng sinh ra H thì F  G cũng sinh ra H. Chương 2 ntsơn
  21. Suy luận[3] Chứng minh (G → H) ├─ (F  G) → (F  H) 1 G → H tiền đề 2 if F  G 3 if F 4 nif F  H i 3 5 if G 6 H →e 1, 5 7 nif F  H i 6 8 nif F  H e 2, 3, 5 9 (F  G) → (F  H) →i 2-8 Chương 2 ntsơn
  22. Suy luận tự nhiên[3] • Qui tắc phủ định (e) dòng m : F  F dòng k : ⊥ Dạng (FF) được gọi là công thức mâu thuẫn. Công thức mâu thuẫn được biểu diễn bằng ký hiệu ⊥. Đây là công thức “mạnh” nhất. • Dạng (F  F) được ký hiệu Ť. Đây là công thức “yếu” nhất. Chương 2 ntsơn
  23. Suy luận tự nhiên[3] • Qui tắc phủ định (i) dòng m : if F dòng k : nif ⊥ dòng k+1 : F Giả sử có dòng F và dẫn ra mâu thuẫn thì có thể viết ra dòng F. Chương 2 ntsơn
  24. Suy luận • Qui tắc mâu thuẫn (⊥e) dòng k : ⊥ dòng m : F Nếu có dòng (k) ⊥ thì có thể viết ra dòng (m) F với F là bất kỳ công thức nào. Nhận xét : Mọi công thức có thể được dẫn xuất từ công thức mâu thuẫn. Nói cách khác, công thức mâu thuẫn chứng minh được mọi công thức. Chương 2 ntsơn
  25. Suy luận Chứng minh : F  G ├─ F → G 1 F  G tiền đề 2 if F 3 if F 4 ⊥ e 2, 3 5 nif G ⊥e 4 6 nif F → G →i 3, 5 7 if G 8 if F 9 nif G bản sao 7 10 nif F → G →i 8, 9 11 F → G e 1, 2-10 Chương 2 ntsơn
  26. Suy luận[3] Chứng minh F→G, F→G├─ F 1 F→G tiền đề 2 F→G tiền đề 3 if F 4 G →e 1, 3 5 G →e 2, 3 6 nif ⊥ e 4, 5 7 F i 3, 6 Chương 2 ntsơn
  27. Suy luận[3] Chứng minh F ├─ F 1 F tiền đề 2 if F 3 nif ⊥ e 1, 2 4 F i 2, 3 Chương 2 ntsơn
  28. Suy luận[3] Chứng minh Modus tolens F→G, G├─ F 1 F→G tiền đề 2 G tiền đề 3 if F 4 G →e 1, 3 5 nif ⊥ e 2, 4 6 F i 3, 5 • Từ modus tolens (MT) có nghĩa là denying method. Chương 2 ntsơn
  29. Suy luận[3] Chứng minh F → (G→H), F, H├─ G 1 F → (G→H) tiền đề 2 F tiền đề 3 G→H →e 1, 2 4 H tiền đề 5 G MT 3, 4 Chương 2 ntsơn
  30. Suy luận[3] Chứng minh F→G├─ G→F 1 F→G tiền đề 2 if G 3 nif F MT 1, 2 4 G → F (→i) Chương 2 ntsơn
  31. Suy luận tự nhiên[3] • Qui tắc phủ định kép e (e) dòng m : F dòng k : F Nếu có dòng F thì có thể viết được dòng F. Chương 2 ntsơn
  32. Suy luận[3] Chứng minh Reductio ad absurrdum (RAA) : F → ⊥ ├─ F 1 F → ⊥ tiền đề 2 if F 3 nif ⊥ e 1, 2 4 F i 2, 3 5 F e 4 Chương 2 ntsơn
  33. Suy luận[3] Nhận xét : RAA còn gọi là Proof by contradiction (PBC), được viết dưới dạng qui tắc như sau : • Qui tắc PBC dòng m : if  F dòng k : nif ⊥ dòng k+1 : F Nếu giả sử có dòng F và dẫn ra mâu thuẫn thì có thể viết ra dòng F. Chương 2 ntsơn
  34. Suy luận[3] Chứng minh LEM (the law of the excluded middle) : ├─ F  F 1 if (F  F) 2 if F 3 F  F i 2 4 nif ⊥ e 1, 3 5 F i 2-4 6 F  F i 5 7 nif ⊥ e 1, 6 8 (F  F) i 1-7 9 F  F e 8 Chương 2 ntsơn
  35. Suy luận[3] Chứng minh F → G├─ F  G 1 F  F LEM 2 if F 3 nif F  G i 2 4 if F 5 F → G tiền đề 6 G →e 4, 5 7 nif F  G i 6 8 F  G e 1, 2, 4 Chương 2 ntsơn
  36. Suy luận[3] Chứng minh F  G├─ (F  G) 1 if F  G 2 F e 1 3 G e 1 4 F  G tiền đề 5 if F 6 nif ⊥ e 2,5 7 if G 8 nif ⊥ e 3,7 9 nif ⊥ e 4-8 10 (F  G) i 1-9 Chương 2 ntsơn
  37. Ứng dụng của chứng minh[7] • Có các phản ứng hóa học sau : HCl + NaOH → NaCl + H2O C + O2 → CO2 CO2 + H2O → H2CO3 Chỉ rằng có thể có H2CO3 khi có HCl, NaOH, O2 và C. Chương 2 ntsơn
  38. Ứng dụng của chứng minh[7] • Các phân tử HCl, NaOH, O2 và C được hình thức hóa như là một hệ thống và chứng minh rằng H2CO3 được chứng minh từ hệ thống này. • Các phản ứng hóa học được hình thức hóa như sau : HCl  NaOH → NaCl  H2O C  O2 → CO2 CO2  H2O → H2CO3. Chương 2 ntsơn
  39. Ứng dụng của chứng minh Bài toán trở thành chứng minh : HCl  NaOH → NaCl  H2O, C  O2 → CO2, CO2  H2O → H2CO3, HCl, ├─ H2CO3. NaOH, O2, C Chương 2 ntsơn
  40. Ứng dụng của chứng minh Chứng minh : 1 HCl tiền đề 2 NaOH tiền đề 3 HCl  NaOH i 1, 2 4 HCl  NaOH → NaCl  H2O tiền đề 5 NaCl  H2O →e 3, 4 6 H2O e 5 7 C tiền đề 8 O2 tiền đề 9 C  O2 i 7, 8 10 C  O2 → CO2 tiền đề 11 CO2 →e 9, 10 12 CO2  H2O i 6, 11 13 CO2  H2O → H2CO3 tiền đề 14 H2CO3 →e 12, 13 Chương 2 ntsơn
  41. Chứng minh bằng phản chứng • Một số công thức khó chứng minh được bằng cách trực tiếp. • Logic cổ điển chấp nhận cách chứng minh gián tiếp - chứng minh F để dẫn đến mâu thuẫn. • Nhưng logic trực giác (intuitionistic logic) không đồng ý hai qui tắc : ├─ F  F (LEM) và ├─ F → F (e) Chương 2 ntsơn
  42. Bài tập Chương 2 : Luận lý mệnh đề ntsơn
  43. Suy luận Chứng minh 1. G → F├─ F → G 2. ├─ (G→H) → ((G→ F) → (F→H)) 3. (F  G) → H├─ F → (G → H) 4. F → (G → H) ├─ (F  G) → H 5. F → G ├─ (F  H) → (G  H) Chương 2 ntsơn
  44. Suy luận 6. (F  G)  H ├─ F  (G  H) 7. F  (G  H) ├─ (F  G)  (F  H) 8. F→F├─ F 9. F→(G→H), F, H├─ G (không dùng luật MT) 10. (F  G) → H, H, F├─ G. Chương 2 ntsơn
  45. Hết slide Chương 2 ntsơn