Bài giảng Luận lý toán học - Chương 3: Luận lý vị từ - Nguyễn Thanh Sơn (Phần 2)

Nội dung text: Bài giảng Luận lý toán học - Chương 3: Luận lý vị từ - Nguyễn Thanh Sơn (Phần 2)

1. II. Suy luận tự nhiên trong luận lý vị từ ntsơn
2. Cây phân tích[3’] • Công thức ∀x ((p(x) → q(x)) ∧ r(x, y)) có cây phân tích : ∀x ∧ → r p q x y x x Chương 3 ntsơn
3. Hiện hữu[3’] • Hiện hữu là ràng buộc nếu có một lượng từ cùng tên ở trên con đường từ nó hướng về gốc. Ngược lại là tự do. Thí dụ : (∀x (p(x) ∧ q(x))) → (¬p(x) ∨ q(y)) → ∀x ∨ ∧ ¬ q p q p y tự do x x x ràng buộc ràng buộc tự do Chương 3 ntsơn
4. Thay thế • Chỉ những hiện hữu tự do mới được thay thế • Biến là nguyên từ phải được thay bởi một nguyên từ. → ∀x ∨ ∧ ¬ q p q p y tự do x x x tự do ràng buộc ràng buộc 2 hiện hữu này có thể được thay thế Chương 3 ntsơn
5. Thay thế • Ký hiệu F[t/x] nghĩa là tất cả hiện hữu tự do của x trong F được thay bởi t. → ∀y ∨ ∧ ¬ q p q p y tự do x y x tự do tự do ràng buộc 2 hiện hữu của x thay bởi t với F[t/x] Chương 3 ntsơn
6. Thay thế Thí dụ : → ∀x ∨ ∧ ¬ q p q p y x z x ràng buộc thay z bằng t ?  thay z bằng x ?  thay z bằng f(t, y) ?  thay z bằng g(x, t) ?  Chương 3 ntsơn
7. Điều kiện thay thế[3’] • Nguyên từ t tự do đối với biến x trong công thức F nếu không có hiện hữu tự do của x xuất hiện trong phạm vi của ∀y hoặc ∃y với mọi biến y có trong t. Nói các khác, hiện hữu của các biến trong t không trở thành ràng buộc khi thế t vào tất cả những hiện hữu tự do của x. Chương 3 ntsơn
8. Điều kiện thay thế • Thí dụ : ∧ ràng buộc r ∀y t2 = g(x, x) t1 = f(y, z) x → t3 = h(x, z) tự do p q x y tự do t1 = f(y, z) không tự do đối với x vì y trở thành ràng buộc. t2 = g(x, x) tự do đối với x. t3 = h(x, z) tự do đối với x. Chương 3 ntsơn
9. Thay thế Nhận xét : – Một số biến cần được đổi tên để thoả mãn điều kiện thay thế. – Để F[t/x] luôn luôn được thực hiện, trước tiên đổi tên tất cả các biến có hiện hữu ràng buộc trong F xuất hiện trong t. Lúc này t tự do đối với x. Chương 3 ntsơn
10. Thay thế Thí dụ : ∧ r ∀y ∀t f(y, z) không tự do đối với x. Nếu thay biến y bằng t thì x → f(y, z) tự do đối với x. tự do p q x y t tự do Chương 3 ntsơn
11. Suy luận tự nhiên • Suy luận tự nhiên trong LLVT cũng tương tự như trong LLMĐ, ngoại trừ các qui tắc liên quan đến lượng từ. • Ký hiệu bằng nhau t = s với t và s là nguyên từ là vị từ eq(t, s). • eq(t, s) có giá trị đúng khi t và s : - cùng là một ký hiệu hằng - là biểu thức hàm cùng giá trị trên miền đối tượng. Chương 3 ntsơn
12. Suy luận tự nhiên[3’] • Qui tắc bằng nhau i (=i) dòng m : eq(t, t), với t là nguyên từ. Đương nhiên viết được dòng m. Chú thích : qui tắc (=i) còn được viết là t = t. Chương 3 ntsơn
13. Suy luận tự nhiên[3’] • Qui tắc bằng nhau e (=e) dòng m : eq(t1, t2) với t1,t2 là nguyên từ dòng k : F[t1/x] dòng k+1 : F[t2/x] với t1, t2 tự do đối với x trong F. Nếu có dòng m và k thì viết được dòng k+1. Chú thích : qui tắc (=e) còn được viết là t1 = t2. Chương 3 ntsơn
14. Suy luận tự nhiên[3’] • Chứng minh : t1 = t2 ├─ t2 = t1. Viết lại : eq(t1, t2)├─ eq(t2, t1). Đặt F = eq(x, t1). 1 eq(t1, t2) tiền đề 2 eq(t1, t1) (=i) (= F[t1/x]) 3 eq(t2, t1) (=e) 1, 2 (= F[t2/x]) Chương 3 ntsơn
15. Suy luận tự nhiên[3’] • Chứng minh : t1 = t2 , t2 = t3 ├─ t1 = t3 F = eq(x, t3). 1 t2 = t3 tiền đề (F[t2/x]) 2 t1 = t2 tiền đề 3 t1 = t3 =e 1, 2 (F[t1/x]) Chương 3 ntsơn
16. Suy luận tự nhiên[3’] • Qui tắc lượng từ phổ dụng e (∀e) dòng m : ∀x F dòng k : F[t/x] với nguyên từ t tự do đối với x trong F(*). Nếu có dòng m thì viết được dòng k. (*)Nhận xét : t tự do đối với x trong F, không phải trong (∀xF), nghĩa là công thức đã được “gỡ bỏ” lượng từ. Chương 3 ntsơn
17. Suy luận tự nhiên[3’] • Thí dụ : p(t), ∀x (p(x)→¬q(x)) ├─ ¬q(t) với mọi t (tự do đối với x) 1 ∀x (p(x)→¬q(x)) tiền đề 2 p(t)→¬q(t) ∀e 1 3 p(t) tiền đề 4 ¬q(t) →e 2, 3 Chương 3 ntsơn
18. Suy luận tự nhiên[3’] • Từ ∀x F tới F[y/x] không thể thiếu điều kiện “tự do đối với biến“. Thí dụ : F = (∃y (x < y)) với x, y là số nguyên và quan hệ nhỏ hơn (<) thông thường. ∀x F có nghĩa là mọi số nguyên x có số nguyên y lớn hơn. Nhưng, F[y/x] là (∃y (y <y)), nghĩa là có số y lớn hơn chính nó. Kết quả sai này là do điều kiện “tự do đối với biến” bị vi phạm. Chương 3 ntsơn
19. Suy luận tự nhiên[3’] • Qui tắc lượng từ phổ dụng i (∀i) dòng m : if x0 dòng : dòng k : nif F[x0/x] dòng k+1 : ∀x F với biến x0 là bất kỳ và không xuất hiện ở ngoài cấu trúc if nif. khi đó viết được dòng k+1. Cấu trúc if nif chỉ là qui định phạm vi của x0. Chương 3 ntsơn
20. Suy luận tự nhiên[3’] • Thí dụ : ∀x (p(x)→q(x)), ∀x p(x)├─ ∀x q(x) 1 ∀x (p(x)→q(x)) tiền đề 2 ∀x p(x) tiền đề 3 if x0 (x0 không xuất hiện ở 1,2,6) p(x0)→q(x0) ∀e 1 4 p(x0) ∀e 2 5 nif q(x0) →e 3, 4 6 ∀x q(x) ∀i 3-5 Chương 3 ntsơn
21. Suy luận tự nhiên[3’] • Qui tắc ∀i dẫn từ F[x0/x] đến ∀x F “có vẻ” như từ một trường hợp đặc biệt tổng quát hóa lên. Điều kiện biến x0 chưa xuất hiện ở ngoài cấu trúc if nif cho phép khái quát được trường hợp tổng quát. Vì x0 là “bất kỳ”, không phải là phần tử đã được “chuẩn bi sẵn”. Nhắc lại : Tất cả các dòng - từ dòng có từ khóa if đến dòng có từ khóa nif - đều thuộc cấu trúc if nif Chương 3 ntsơn
22. Suy luận tự nhiên[3’] • Qui tắc lượng từ hiện hữu i (∃i) dòng m : F[t/x] dòng k : ∃x F Nếu có dòng m thì viết được dòng k. Nhận xét : qui tắc này là đối ngẫu của ∀e. Chương 3 ntsơn
23. Suy luận tự nhiên[3’] • Thí dụ : ∀x F ├─ ∃x F 1 ∀x F tiền đề 2 F[x/x] ∀e 1 3 ∃x F ∃i 2 Chương 3 ntsơn
24. Suy luận tự nhiên[3’] • Qui tắc lượng từ hiện hữu e (∃e) dòng m : ∃x F dòng m+1 : if x0 F[x0/x] (thế x0 vào dòng m) dòng k : nif G dòng k+1 : G với x0 là bất kỳ và không xuất hiện ở ngoài cấu trúc if nif. Nếu có dòng m và cấu trúc if nif thì viết được dòng k+1. Chương 3 ntsơn
25. Suy luận tự nhiên[3’] • Qui tắc lượng từ hiện hữu e (∃e) (tt) Khi có ∃x F thì “có ít nhất một” giá trị của x để bảo đảm sự hiện hữu của ∃x F, x0 là đại diện cho tất cả các giá trị này của x. Chương 3 ntsơn
26. Suy luận tự nhiên[3’] • Thí dụ : ∀x (p(x)→q(x)), ∃x p(x)├─ ∃x q(x) 1 ∀x (p(x)→q(x)) tiền đề 2 ∃x p(x) tiền đề (*) 3 if x0 p(x0) 2 [x0/x] 4 p(x0)→ q(x0) ∀e 1 5 q(x0) →e 3,4 6 nif ∃x q(x) ∃i 5 7 ∃x q(x) ∃e 2, 3-6 ((*) Lý do để có dòng 3 là do qui định của qui tắc lượng từ hiện hữu ∃e) Chương 3 ntsơn
27. Suy luận tự nhiên[3’] • Thí dụ : ∀x (p(x)→q(x)), ∃x p(x)├─ ∃x q(x) 1 ∀x (p(x)→q(x)) tiền đề 2 ∃x p(x) tiền đề 3 if x0 p(x0) 2 [x0/x] 4 p(x0)→ q(x0) ∀e 1 5 nif q(x0) →e 3,4 6 q(x0) ∃e 2, 3-5 7 ∃x q(x) ∃i 6 * Dòng 6 không hợp lệ vì x0 thoát ra ngoài cấu trúc if nif. Chương 3 ntsơn
28. Suy luận tự nhiên[3’] • Thí dụ : ∀x (q(x)→r(x)), ∃x (p(x) ∧ q(x))├─ ∃x (p(x) ∧ r(x)) 1 ∀x (q(x)→r(x)) tiền đề 2 ∃x (p(x) ∧ q(x)) tiền đề 3 if x0 p(x0) ∧ q(x0) 2[x0/x] 4 p(x0) ∧e 3 5 q(x0) ∧e 3 6 q(x0) → r(x0) ∀e 1 7 r(x0) →e 5,6 8 p(x0) ∧ r(x0) ∧i 4,7 9 nif ∃x (p(x) ∧ r(x)) ∃i 8 10 ∃x (p(x) ∧ r(x)) ∃e 2, 3-9 Chương 3 ntsơn
29. Suy luận tự nhiên[3’] • Thí dụ : ∃x p(x), ∀x∀y (p(x)→q(y))├─ ∀y q(y) 1 ∀x∀y (p(x)→q(y)) tiền đề 2 ∃x p(x) tiền đề 3 if y0 4 if x0 p(x0) 2 [x0/x] 5 p(x0)→ q(y0) ∀x ∀y e 1 6 nif q(y0) →e 4,5 7 nif q(y0) ∃x e 2,4-6 8 ∀y q(y) ∀y i 3-7 Chương 3 ntsơn
30. Suy luận tự nhiên[3’] • Định lý : (a) ¬∀x F ≡ ∃x ¬F (b) ¬∃x F ≡ ∀x ¬F Chương 3 ntsơn
31. Suy luận tự nhiên • Hiện hữu tự do (của 1 biến) đối với 1 công thức. Thí dụ : G = p(x) ∧ (∃x)q(x)), x (trong p(x)) là hiện hữu tự do (đối với G) của biến x. F = (∀x)(r(x) ∨ G), không có hiện hữu tự do (đối với F) của biến x. Chương 3 ntsơn
32. Suy luận tự nhiên[3’] • Định lý : G không chứa hiện hữu tự do của x (trong G). (a) ∀x F ∧ G ≡ ∀x (F ∧ G) (b) ∀x F ∨ G ≡ ∀x (F ∨ G) (c) ∃x F ∧ G ≡ ∃x (F ∧ G) (d) ∃x F ∨ G ≡ ∃x (F ∨ G) Chương 3 ntsơn
33. Suy luận tự nhiên[3’] • Định lý : G không chứa hiện hữu tự do của x (trong G). (e) ∀x (G → F) ≡ G →∀x F (f) ∃x (F → G) ≡ ∀x F → G (g) ∀x (F → G) ≡ ∃x F → G (h) ∃x (G → F) ≡ G → ∃x F Chương 3 ntsơn
34. Suy luận tự nhiên[3’] • Định lý : (a) ∀x F ∧ ∀x G ≡ ∀x (F ∧ G) (b) ∃x F ∨ ∃x G ≡ ∃x (F ∨ G) (c) ∀x∀y F ≡ ∀y∀x F (d) ∃x∃y F ≡ ∃y∃x F Chương 3 ntsơn
35. Bài tập Chương 3 : Luận lý vị từ ntsơn
36. Suy luận tự nhiên[3’] 0. Chứng minh các định lý trong phần giáo khoa. 1. Chứng minh : a. (y = 0) ∧ (y = x) ├─ 0 = x b. t1 = t2 ├─ (t + t2) = (t + t1) c. (x = 0) ∨ ((x + x) > 0) ├─ (y = (x + x)) → ((y > 0) ∨ (y = (0 +x))) 2. Dịch ∃x ∃y (¬(x = y) ∧ ∀z ((z = x) ∨ (z = y)))) ra ngôn ngữ tự nhiên. Chương 3 ntsơn
37. Suy luận tự nhiên[3’] 3. Dịch ra LLVT : a. Có đúng 3 phần tử phân biệt. b. Có nhiều nhất 3 phần tử phân biệt. c. Chỉ một số hữu hạn các phần tử phân biệt. 4. Chứng minh : F → (q1∧q2) ├─ (F→q1) ∧ (F→q2) (trong LLMĐ) F → ∀x q(x) ├─ ∀x (F → q(x)) (trong LLVT) với x không tự do trong F. ∀x (p(x) → q(x)) ├─ ∀x p(x) → ∀x q(x). Chương 3 ntsơn
38. Suy luận tự nhiên[3’] 5. Chứng minh : a. ∀x p(x)├─ ∀y p(y) b. ∀x (p(x) → q(x)) ├─ (∀x ¬q(x)) → (∀x ¬p(x)) c. ∀x (p(x) → ¬q(x)) ├─ ¬(∃x (p(x) ∧ q(x)) Chương 3 ntsơn
39. Hết slide Chương 3 ntsơn