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 1)

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 1)

1. Chương 3. Luận lý vị từ ntsơn
2. Nội dung I. Cấu trúc của luận lý vị từ II. Suy luận tự nhiên trong luận lý vị từ III. Ngữ nghĩa của luận lý vị từ IV. Phân giải Chương 3 ntsơn
3. I. Cấu trúc của luận lý vị từ ntsơn
4. Hạn chế của LLMĐ • Tam đoạn luận Nếu là người thì phải chết. (P) Socrates là người. (Q) Vậy Socrates phải chết. (R) • Biểu diễn bằng LLMĐ không giữ được mối quan hệ ((P ∧ Q) → R) của 3 phát biểu trên.  Thêm khái niệm quan hệ để duy trì được sự liên kết. Chương 3 ntsơn
5. Biểu diễn bằng quan hệ • Chọn các quan hệ từ các mệnh đề P, Q, R : * qhệ người(x) (ie, x là người). * qhệ chết(x) (ie, x chết). • Khi đó các mệnh đề P, Q, R trở thành : P = nếu người(x) thì chết(x). Q = người(Socrates). R = chết(Socrates). {người(x) → chết(x), người(Socrates)} hệ thống kết luận được : chết(Socrates). Chương 3 ntsơn
6. Hạn chế của LLMĐ • Một phỏng đoán của Goldbach : P = “ Mọi số nguyên chẵn ≥ 4 là tổng của hai số nguyên tố”. • Đặt Pn = “n chẵn là tổng của hai số nguyên tố”. Mệnh đề P có thể được phân rã thành vô hạn các mệnh đề : P = P4 và P6 và P8 và • Luận lý mệnh đề không chấp nhận dạng giao vô hạn P4 ∧ P6 ∧ P8 ∧ .  Khái niệm quan hệ biểu diễn được giao vô hạn. Chương 3 ntsơn
7. Lượng từ • Logic “phục vụ” cho toán học. Thí dụ : (G, *) là một nhóm. Luật giao hoán được diễn tả bằng công thức x * y = y * x, với mọi phần tử x, y. Luật phần tử đơn vị được diễn tả có phần tử i, x * i = x, với mọi phần tử x.  Lý do xuất hiện khái niệm ∀, ∃. Chương 3 ntsơn
8. Lượng từ • Xây dựng các quan hệ : nhân (mp), bằng (eq) - Luật giao hoán được diễn tả : ∀x,∀y eq(mp(x, y), mp(y, x)). - Luật phần tử đơn vị ∃i,∀x eq(mp(x, i), x).  Phân loại quan hệ : hàm, vị từ. Chương 3 ntsơn
9. Cấu trúc của luận lý vị từ • Bảng ký tự : Tập hợp hữu hạn các ký tự. Thí dụ : a, b, c, d, , z • Ký hiệu : Chuỗi hữu hạn ký tự được dùng để đặt tên cho các khái niệm trong FOL. Thí dụ : tên biến : x, y, tên hàm : cong, nhan, chia, • Miền đối tượng D : là một tập hợp “trừu tượng”. Chương 3 ntsơn
10. Cấu trúc của luận lý vị từ • Tập hợp các ký hiệu biến. • Lượng từ có 2 loại : Phổ dụng ∀ (universal quantifier) Hiện hữu ∃ (existential quantifier). Hình thức sử dụng : (∀x), (∃x) : với x là biến. Chương 3 ntsơn
11. Cấu trúc của luận lý vị từ Chương 3 ntsơn
12. Cấu trúc của luận lý vị từ • Vị từ là quan hệ trên tập Dn, nghĩa là tập con của tập Dn. Thí dụ : D = {táo, đường, cam, bắpcải, chuối, mướp, ớt, tiêusọ, khổhoa, muối} p = {táo, cam, chuối} ⊆ D. p là quan hệ “trái cây tráng miệng”. q = {đường, ớt, tiêusọ, muối} ⊆ D. q là quan hệ “gia vị”. Chương 3 ntsơn
13. Cấu trúc của luận lý vị từ Thí dụ : D = {2, 3, 4, 5, 6, 7, 8, 9, 10} r = {2, 3, 5, 7} (⊆ D) là quan hệ “nguyên tố” s = {(2, 2), (2, 4), (2, 6), (2, 8), (2, 10), (3, 6), (3, 9), (4, 8), (5, 10)} ⊆ D×D là quan hệ “chia chẵn”. t = {4, 9} (⊆ D) là quan hệ chính phương. Chương 3 ntsơn
14. Cấu trúc của luận lý vị từ • Một cách định nghĩa khác. Hàm là vị từ nếu - Chỉ kết hợp với nhau qua các toán tử logic : ¬, ∧, ∨, →. - Khi sử dụng không được làm thông số của hàm khác. Chương 3 ntsơn
15. Cấu trúc của luận lý vị từ • Vị từ được biểu diễn bằng hàm Dn → {1, 0} Thí dụ : p = {táo, cam, chuối} ⊆ D p : D → {1, 0}, p(táo) = p(cam) = p(chuối) = 1, p(đường) = p(bắpcải) = p(mướp) = p(ớt) = p(tiêusọ) = p(khổhoa) = p(muối ) =0. Chương 3 ntsơn
16. Cấu trúc của luận lý vị từ Thí dụ : s = {(2, 2), (2, 4), (2, 6), (2, 8), (2, 10), (3, 6), (3, 9), (4, 8), (5, 10)} ⊆ D×D là quan hệ “chia chẵn”. s(2, 2) = s(2, 4) = s(2, 6) = s(2, 8) = s(2, 10) = s (3, 6) = s(3, 9) = s(4, 8) = s(5, 10) = 1, s(x, y) = 0 với (x, y) ∉ s. Chương 3 ntsơn
17. Cấu trúc của luận lý vị từ • Ảnh của vị từ được gọi là biểu thức vị từ. Thí dụ : mẹ(x, y) là ảnh của vị từ mẹ, bạn(y, z) là ảnh của vị từ bạn. cha(Minh, Vũ) không phải là biểu thức vị từ vì Minh, Vũ là 2 giá trị trong thế giới thực, không phải là giá trị của miền D trừu tượng. Chương 3 ntsơn
18. Các vị từ đặc biệt • Trường hợp đặc biệt : card(D0) = card({f | f : ∅ → D}) = 1. 0 f • • Hàm f : D → D được gọi là hằng. • • • • D0 D 0 Có 2 vị từ từ : D → {1, 0} là p1 (luôn lấy giá trị đúng) và p0 (luôn lấy giá trị sai). p1 0 p • • 0 0 1 1 D0 D0 {0, 1} {0, 1} Chương 3 ntsơn
19. Nguyên từ • Nguyên từ (term) : (i) Ký hiệu hằng (constant) là nguyên từ. (ii) Ký hiệu biến (variable) là nguyên từ. (iii) Nếu t1, , tn là nguyên từ thì biểu thức hàm f(t1, , tn) là nguyên từ. (với hàm f không là vị từ). * Điều kiện (i) không cần thiết vì đã được bao hàm trong điều kiện (iii). Chương 3 ntsơn
20. Nguyên từ Thí dụ : Hằng a, b, c là nguyên từ. Biến x, y, z là nguyên từ. Biểu thức hàm f(a,x) là nguyên từ. Biểu thức hàm h(g(y),a,x) là nguyên từ. Biểu thức hàm g(f(h(x, y, z), c)) là nguyên từ. Bởi các hàm f(_,_), g(_), và h(_,_,_). Chương 3 ntsơn
21. Công thức nguyên • Nếu p là vị từ và t1, , tn là nguyên từ thì p(t1, , tn) là công thức nguyên. • Biểu thức vị từ là công thức nguyên. Thí dụ : Vị từ : mẹcủa(_, _), nhỏhơn(_, _), cònsống(_). mẹ_của(x, f(y)), nhỏhơn(cộng(x, a), y), còn_sống(z) là các công thức nguyên. Chương 3 ntsơn
22. Công thức nguyên Thí dụ : Các nhà thơ : Văn Cao, Xuân Diệu, Hoàng Cầm, Phạm Thiên Thư. Sử gia : Lê Văn Hưu. Vua : QuangTrung. Đặt D = {xDiệu, hCầm, vCao, pTThư, lVHưu, qTrung}. Đặt vị từ nt(x) = x là nhà thơ, với x ∈ D.  nt(x) là công thức nguyên  nt(xDiệu), nt(pTThư) không là CT nguyên. Chương 3 ntsơn
23. Công thức nguyên Công thức nguyên nt(x) với x ∈ D tương đương với 6 câu khai báo : nt(xDiệu) : Xuân Diệu là nhà thơ. nt(hCầm) : Hoàng Cầm là nhà thơ. nt(vCao) : Văn Cao là nhà thơ. nt(pTThư) : Phạm Thiên Thư là nhà thơ. nt(lVHưu) : Lê Văn Hưu là nhà thơ. nt(qTrung) : QuangTrung là nhà thơ. Chương 3 ntsơn
24. Công thức nguyên Nhận xét : • Một công thức nguyên của LLVT tương ứng với một tập công thức nguyên của LLMĐ. • LLMĐ là một trường hợp đặt biệt của LLVT. Chương 3 ntsơn
25. Công thức hoàn hảo • Công thức hoàn hảo được gọi tắt là công thức. • Công thức : (i) Công thức nguyên là CT. (ii) ⊥, Ť là CT. (iii) CT kết hợp với ¬, ∧, ∨, → cũng là CT. (vi) CT kết hợp với (∀x), (∃x) cũng là CT. Sự kết hợp các yếu tố trên chỉ gồm hữu hạn phần tử. Chương 3 ntsơn
26. Một định nghĩa khác[15] • V là tập vô hạn đếm được các biến. • R tập đếm được các ký hiệu quan hệ (vị từ). Mỗi vị từ có arity là số nguyên không âm (non- negative). • F tập đếm được các ký hiệu hàm. Mỗi vị từ có arity là số nguyên không âm (non-negative). • C tập đếm được các ký hiệu hằng. • Σ = được gọi là first-order signature. Chương 3 ntsơn
27. Một định nghĩa khác[15] • Σ = là first-order signature, tập hợp Σ-term là tập nhỏ nhất thỏa : – Biến trong V là một term. – Hằng trong C là một term. – Nếu f là hàm n thông số và t1, , tn là term thì f(t1, , tn) cũng là term. Chương 3 ntsơn
28. Một định nghĩa khác[15] Thí dụ : “All men are mortal”. Định nghĩa một signature Σ = như sau : R = {man(_), mortal(_)}, F = ∅, C = ∅. Câu trên được biểu diễn như sau : ∀x(man(x) → mortal(x)). Chương 3 ntsơn
29. Một định nghĩa khác[15] Thí dụ : Một signature Σ : R = {equal(_,_)}, F = {plus(_,_)}, C = ∅. Tính giao hoán được biểu diễn như sau : ∀x ∀x equal(plus(x, y), plus(y, x)). Viết theo ngôn ngữ thông thường : ∀x ∀x (x + y = y + x). Chương 3 ntsơn
30. Phạm vi của lượng từ • Trong công thức (∀x F), F thuộc phạm vi ảnh hưởng của ∀x. • Trong công thức (∃x F), phạm vi ảnh hưởng của ∃x là F. Thí dụ : (∃y)(r(y)) ∧ (∀x)(p(x) → q(f(x), a)). Phạm vi của (∃y) là r(y), phạm vi của (∀x) là (p(x) → q(f(x), a)). Chương 3 ntsơn
31. Hiện hữu • Hiện hữu của một biến là sự xuất hiện của biến đó trong công thức. Thí dụ : ((∀x) p(x,y) ∧ q(t,y)) → (∃y)(r(x,y,z)) có 4 biến. Biến x có 2 hiện hữu, biến y có 3 hiện hữu. Biến z có 1 hiện hữu, biến t có 1 hiện hữu. Chương 3 ntsơn
32. Hiện hữu • Hiện hữu ràng buộc là hiện hữu thuộc phạm vi của lượng từ có biến cùng tên với nó. • Hiện hữu tự do là hiện hữu không ràng buộc. Thí dụ : ((∀x)(∀y) p(x, y, z)) ∧ ((∀z) q(y, z)) Hiện hữu ràng buộc Hiện hữu tự do (∀z p(z, y)) ∧ (∀x q(x, y, z)) Chương 3 ntsơn
33. Công thức đóng • Công thức đóng : công thức không chứa hiện hữu tự do. • Công thức tự do : công thức chứa ít nhất 1 hiện hữu tự do. Thí dụ : ((∀x)(∀y) p(x, y)) ∧ ((∀z) q(z)) : đóng. ((∀x)(∀y) p(x, y, z)) ∧ ((∀z) q(y, z)) : tự do. (∀z p(z, x)) ∧ (∀x q(x)) : tự do. Chương 3 ntsơn
34. Dịch sang Luận lý vị từ • Thí dụ : Every student is younger than some instructor [3’]. Chọn các vị từ : sv(x) = x là SV, gv(x) = x là giảng viên, yg(x, y) = x trẻ hơn y. For every x, if x is a student, then there is some y which is an instructor such that x is younger than y [3’]. ∀x (sv(x) → ∃y (gv(y) ∧ yg(x,y))) Chương 3 ntsơn
35. Dịch sang Luận lý vị từ • Thí dụ : Not all birds can fly [3’]. Chọn các vị từ : ch(x) = x là chim, by(x) = x có thể bay. ¬(∀x (ch(x) → by(x))) Nói cách khác ∃x (ch(x) ∧ ¬by(x)) Nhưng, “all birds can not fly” ? Chương 3 ntsơn
36. Dịch sang Luận lý vị từ • Thí dụ : Trẻ con nói chuyện không biết lý luận. Không ai làm việc chăm chỉ lại bị chế nhạo. Ai nói chuyện không biết lý luận thì bị chế nhạo. Vì vậy trẻ con không thể làm việc chăm chỉ. Chọn các vị từ : Lýluận(x) = x biết lý luận. Bịchếnhạo(x) = x bị chế nhạo. Chămchỉ(x) = x làm việc chăm chỉ . Chương 3 ntsơn
37. Dịch sang Luận lý vị từ • Trẻ con nói chuyện không biết lý luận ¬Lýluận(trẻcon) (1) • Không ai làm việc chăm chỉ lại bị chế nhạo. ∀x (Chămchỉ(x) → ¬Bịchếnhạo(x)) (2) ∀x (Bịchếnhạo(x) → ¬Chămchỉ(x) ) (2') • Những người không biết lý luận thì bị chế nhạo. ∀x (¬Lýluận(x) → Bịchếnhạo (x)) (3) • Vì vậy trẻ con không thể làm việc chăm chỉ. ¬Chămchỉ(trẻcon) (4) Chương 3 ntsơn
38. Dịch sang Luận lý vị từ Giải : Phân tích hệ thống thành : F = ¬Lýluận(trẻcon) G = ∀x (Bịchêbai(x) → ¬Chămchỉ(x)) H = ∀x (¬Lýluận(x) → Bịchêbai (x)) ├─ ¬Chămchỉ(trẻcon) Chương 3 ntsơn
39. Dịch sang Luận lý vị từ • Sự mơ hồ của ngôn ngữ tự nhiên. Thí dụ : P = “Tất cả vật màu đỏ ở trong hộp”. Vị từ red(x) = x là vật màu đỏ, box(x) = x ở trong hộp Biểu diễn P trong LLVT ? Chương 3 ntsơn
40. Dịch sang Luận lý vị từ P = “Tất cả vật màu đỏ ở trong hộp”. Biểu diễn P trong LLVT : (mã hóa lại red(x) là redx, box(x) là boxx) P1 = ∀x (redx → boxx) P2 = ∀x (redx ∧ boxx) P3 = ∀x ((redx → boxx) ∧ (boxx → redx)) Chương 3 ntsơn
41. Bài tập Chương 3 : Luận lý vị từ ntsơn
42. Dịch sang Luận lý vị từ 1. Dùng các vị từ : tp(x, y) : x thán phục y. td(x, y) : x tham dự y. tg(x) : x là thầy giáo. sv(x) : x là sinh viên. bg(x) : x là bài giảng. Dịch các câu sau thành luận lý vị từ : 1.1 Minh thán phục mọi thầy giáo. 1.2 Một số thầy thán phục Minh. 1.3 Minh thán phục chính mình. 1.4 Không SV nào tham dự mọi bài giảng. 1.5 Không bài giảng nào được tham dự bởi mọi SV. 1.6 Không bài giảng nào được tham dự bởi bất kỳ 1 SV. Chương 3 ntsơn
43. Dịch sang Luận lý vị từ 2. Câu “Minh thán phục mọi thầy giáo” trong câu 1 ở trên được dịch thành ∀x tp(minh, tg(x)) sai vì lý do gì ?*. Có thể sửa lại để câu trên trở thành đúng ?. 3. Dịch các câu vị từ sau thành câu tự nhiên : 3.1 ∀x∀y (td(x, y) ∧ sv(x) ∧ bg(y)) 3.2 ∀x∀y (¬td(x, y) ∧ sv(x) ∧ bg(y)) 3.3 ∀x∀y (td(x, y) ∧ ¬sv(x) ∧ bg(y)) 3.4 ∀x∀y (td(x, y) ∧ sv(x) ∧ ¬bg(y)) 3.5 ∀x∀y (¬td(x, y) ∧ ¬sv(x) ∧ bg(y)) 3.6 ∀x∀y (td(x, y) ∧ ¬sv(x) ∧ ¬bg(y)) 3.7 ∀x∀y (¬td(x, y) ∧ ¬sv(x) ∧ ¬bg(y)) Tương tự thay ∀∀ bằng ∀∃ hay ∃∀ hay ∃∃. * (về phương diện cú pháp và ngữ nghĩa) Chương 3 ntsơn
44. Dịch sang Luận lý vị từ 4. Dịch các câu vị từ sau thành câu tự nhiên : 4.1 ∀x∀y td(x, y) ∧ ∀x sv(x) ∧ ∀y bg(y) 4.2 ∀x∀y td(x, y) ∧ ∀x ¬sv(x) ∧ ∀y bg(y) 4.3 ∀x∀y ¬td(x, y) ∧ ∀x ¬sv(x) ∧ ∀y bg(y) 4.4 ∀x∀y ¬td(x, y) ∧ ∀x sv(x) ∧ ∀y ¬bg(y) 4.5 ∀x∀y ¬td(x,y) ∧ ∀x ¬sv(x) ∧ ∀y ¬bg(y) 4.6 ¬ (∀x∀y td(x, y) ∧ ∀x sv(x) ∧ ∀y bg(y)) Chương 3 ntsơn
45. Dịch sang Luận lý vị từ 5. Dịch các câu sau thành luận lý vị từ : 5.1 Tất cả vật màu đỏ ở trong hộp. 5.2 Chỉ những vật màu đỏ ở trong hộp. 5.3 Không có con vật nào vừa là mèo và vừa là chó. 5.4 Mọi giải thưởng được giật bởi 1 đứa con trai. 5.5 Một đứa con trai giật mọi giải thưởng. Chương 3 ntsơn
46. Dịch sang Luận lý vị từ 6. Dùng các vị từ sau để dịch các câu. b(x, y) : x đánh bại y. f(x) : x là một đội bóng đá. q(x, y) : x là tiền vệ của đội bóng y. l(x, y) : x thua y. 6.1 mọi đội bóng có một tiền vệ. 6.2 Nếu MU đánh bại Chelsi thì MU không thua mọi đội bóng (khác). 6.3 Chelsi đánh bại một số đội bóng mà nó đánh bại MU. Chương 3 ntsơn
47. Dịch sang Luận lý vị từ 7. Chỉ dùng các vị từ cha(x, y), me(x, y), chồng(x, y), anh(x, y), chị(x, y) để dịch các câu sau : 7.1 Mọi người có một mẹ. 7.2 Mọi người có một cha và một mẹ. 7.3 Bất cứ ai có một mẹ thì có một cha. 7.4 Minh đã là ông nội. 7.5 Câu không phải là dì. Chương 3 ntsơn
48. Hết slide Chương 3 ntsơn