CHƯƠNG 1 CƠ SỞ TOÁN HỌC Chương này nhắc lại các cơ sở về toán học sẽ được sử dụng trong các chương tiếp theo của luận văn, bao gồm logic vị từ và tính toán lambda. LOGIC VỊ TỪ CẤP MỘT VÀ PHÉP HỢP NHẤT 1.1 Các khái niệm cơ bản Nội dung phần này có tham khảo tài liệu của tác giả Đỗ Đức Giáo [2]. Để tiện theo dõi, luận văn không trình bày lại các khái niệm cơ sở mà chỉ nhắc lại các thuật ngữ. Ta xét câu tiếng Anh sau: (1) If Pedro owns a donkey, he likes it.
Phân tích cú pháp của câu trên ta được: - Trong mệnh đề thứ nhất: Chủ ngữ là danh từ riêng “Pedro”, vị ngữ là ngoại động từ “own” với bổ ngữ “donkey”. Ta có biểu diễn dưới dạng vị từ 2 đối: own(Pedro,donkey). Vì “donkey” chưa xác định nên ta kí hiệu là x, ta có: donkey(x). - Tương tự mệnh đề thứ hai được biểu diễn thành: like(Pedro, x).
Ta kí hiệu danh từ riêng Pedro là a. Thay “donkey”, “own” và “like” lần lượt thành các vị từ P, Q, R ta được biểu diễn ngữ nghĩa của câu trên bằng công thức logic vị từ cấp một như sau: Trong công thức trên ta có: - a là hằng. Biến x bị ràng buộc trong phạm vi lượng từ , các biến khác (nếu có) sẽ là biến tự do. - x, a và P(x), Q(x), , ,… (các công thức con) là các hạng tử 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com - P(x), Q(x) là các công thức nguyên tử Trong logic vị từ cấp một, những công thức không chứa biến tự do được gọi là một câu.2 Các khái niệm ngữ nghĩa Nội dung phần này có tham khảo tài liệu của tác giả A.
Các khái niệm ngữ nghĩa sau đây phục vụ cho việc biểu diễn ngữ nghĩa thành công thức logic vị từ cấp một. Ta vẫn dùng ví dụ (1) để minh họa. Từ vựng Khi nói về một chủ đề, ta cần từ vựng. Đó là yếu tố cơ bản của ngôn ngữ để tiến hành hội thoại, là các thuật ngữ ta có thể sử dụng để diễn tả chủ đề.
Cấu trúc từ vựng trong logic vị từ cấp một như sau: (Tập các hằng, tập các vị từ (có chỉ rõ số các đối của mỗi vị từ)) Ví dụ, từ vựng cho (1) là: ({PEDRO}, {(DONKEY, 1), (OWN, 2), (LIKE, 2)}) Mô hình vị từ cấp một Mô hình vị từ cấp một (ta sẽ gọi là mô hình) là một cấu trúc mô tả một tình huống. Mô hình đưa ra hai thông tin sau: - Tập các thực thể được nói đến D, còn gọi là miền xác định (trường minh họa) - Hàm minh họa F, ánh xạ mỗi từ vựng thành một (nhiều) bộ các phần tử trên trường minh họa. Một bộ tương ứng với một vị từ sẽ có số phần tử là số đối của vị từ đó, một bộ tương ứng với ký hiệu hằng sẽ có một phần tử. Tức là với mỗi ký hiệu hằng a trong tập từ vựng ta có , còn với mỗi quan hệ n-ngôi R ta có.
11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Định nghĩa 1.3 Phép hợp nhất (Unification) Phần này trình bày theo tài liệu của tác giả A. Trước hết ta định nghĩa một số giả thiết và khái niệm liên quan: Cho trước các đối tượng sau: - Tập vô hạn các biến V. - Tập các hạng tử T (chứa V). - Ánh xạ vars: T → Vn, cho tương ứng mỗi hạng tử t T với tập các biến tự do trong t:.
- Quan hệ tương đương trên T, ký hiệu là ≡, hai hạng tử tương đương nhau nếu chúng đối sánh.2 (Phép thế) Phép thế là một ánh xạ σ: V → T từ tập các biến vào tập các hạng tử., tk/xk) mô tả phép thế mỗi biến thành hạng tử tương ứng, i=1,.,k, còn các biến khác được thay thế bởi chính nó., tk/xk) nghĩa là thay thế đồng thời tất cả các vị trí của mỗi biến xi trong hạng tử t bằng ti. Kết quả t(σ) sau khi áp dụng phép thế σ cho một hạng tử t gọi là một trường hợp của t. 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Định nghĩa 1.3 (Bài toán hợp nhất) Cho một tập hữu hạn các cặp hạng tử {li ri,…, lk rk}, ta cần tìm phép thế để các cặp hạng tử này đối sánh nhau. Phép thế σ là nghiệm của bài toán hợp nhất (hay còn gọi là phần tử hợp nhất: unifier) nếu li(σ) và ri(σ) đối sánh nhau (i = 1, 2,…,k).
Bài toán hợp nhất có thể không có nghiệm hoặc có nhiều nghiệm. Ví dụ bài toán hợp nhất { } có nghiệm (x/y) Phép hợp nhất là một thuật toán dùng để xác định những phép thế cần thiết cho các tham biến vị từ để làm cho hai công thức vị từ đối sánh nhau. Với các công thức logic vị từ cấp một, nếu bài toán hợp nhất có nghiệm thì luôn có một nghiệm, phần tử hợp nhất khi đó gọi là phần tử hợp nhất tổng quát nhất (mgu: most general unifier). * Thuật toán hợp nhất Thuật toán sau đây Martelli và Montanari đề xuất năm 1982.
Cho trước tập hữu hạn các cặp hạng tử cần hợp nhất G = {s1 t1,., sn tn}, thuật toán hợp nhất áp dụng các luật để biến đổi nó thành một tập tương đương có dạng {x1 u1,., xm um } trong đó x1,., xm là các biến phân biệt và u1,., um là các hạng tử không chứa biến xi nào. Tập có dạng này có thể coi là phép thế. Ta ký hiệu G(t/x) là toán tử thực hiện thay thế tất cả các vị trí của biến x trong bài toán thành hạng tử t. Để đơn giản trong trình bày, ta coi các ký hiệu hằng như các ký hiệu hàm không có đối.
Trường hợp Kết quả Luật sử dụng G ∪ {t t} G Xóa G ∪ {f(s0,…, sk) f(t0,…, tk)} G ∪ {s0 t0,…, sk tk} Phân tích 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. TÍNH TOÁN LAMBDA Phần này trình bày theo tài liệu của P. Để biểu diễn ngữ nghĩa qua logic vị từ cấp một, ta phải có biến và hằng đại diện cho các đối tượng trong câu và đưa chúng vào làm đối của các vị từ thích hợp. Câu càng phức tạp thì cách chọn và sắp xếp các biến càng gặp nhiều khó khăn.
Tính toán Lambda là công cụ rất hữu ích giải quyết vấn đề này. 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Cú pháp của tính toán lambda Định nghĩa 1.1 (Biểu thức lambda) Giả sử V là tập vô hạn các biến. A là bảng chữ cái tạo nên các phần tử của V và các ký hiệu đặc biệt “(“, “)”, “λ”, “. Gọi A* là tập các chuỗi trên A.
Tập hợp các biểu thức lambda là tập con nhỏ nhất Λ ⊆ A* thỏa mãn: (i) Nếu x V thì x Λ và đây được gọi là một biến, (ii) Nếu M, N Λ thì (M N) Λ và đây được gọi là phép áp dụng (app), (iii) Nếu x V và M Λ thì (λx.M) Λ và đây được gọi là một phép trừu tượng hóa lambda. Ta sử dụng ký hiệu (M N) để chỉ sự áp dụng của hàm M cho đối N. Ký hiệu trong phép trừu tượng λx.M thể hiện M là một hàm có đối x. * Kỹ thuật tham biến hóa từng phần Khi biểu diễn hàm M có nhiều tham biến x1, x2,…, xn, ta sử dụng kỹ thuật tham biến hóa từng phần để đưa về dạng trừu tượng chỉ sử dụng một biến: λx1.M)…) * Cây cú pháp của biểu thức lambda Ta có thể biểu diễn biểu thức lambda bằng cây cú pháp (hay còn gọi là cấu trúc lambda).
Ví dụ biểu thức (λx.(x y)(x y)) được biểu diễn bằng cây cú pháp sau: 15 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com app λx app app x y x y Hình 1: Cây cú pháp của một biểu thức lambda. * Một số quy ước Để tiện cho việc trình bày, ta quy ước như sau: - Ta sẽ bỏ các cặp ngoặc đơn ngoài cùng. Ví dụ ta viết M N thay cho (M N), - Các phép áp dụng có tính chất kết hợp trái nên M N P có thể viết thành (M N) P, tương tự khi viết f xyz ta sẽ hiểu là ((f x) y) z, - Phần chính của phép trừu tượng hóa lambda (phần sau dấu chấm) sẽ được mở rộng nhất có thể về bên phải, giả sử khi ta viết λx.M N thì ta hiểu là λx.(M N) chứ không phải (λx.M) N, - Các phép trừu tượng hóa lambda có tính chất kết hợp phải nên λx.M có thể viết thành λxyz.2 Biến tự do và biến ràng buộc Biến tự do và biến ràng buộc trong tính toán lambda được định nghĩa tương tự như trong logic vị từ cấp một. Trong biểu thức λx.M, tất cả các vị trí của x trong phần chính M đều là ràng buộc.
Một vị trí của biến không phải ràng buộc thì là vị trí tự do. Biến có vị trí tự do gọi là biến tự do, biến có vị trí ràng buộc gọi là biến ràng buộc. 16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Về mặt hình thức, ta có thể định nghĩa biến tự do như sau: Định nghĩa 1.2 (Biến tự do) Ký hiệu FV(M) là tập các biến tự do của M. Ta có: FV(x) = {x} FV(M N) = FV(M) U FV(N) FV(λx.3 Các phép biến đổi * Phép biến đổi alpha (α-conversion) Ta ký hiệu là phép tương đương alpha.
Với mọi công thức M và mọi biến y không xuất hiện trong M, ta có: λx.(M{y/x}) Quan hệ tương đương alpha tuân theo một số luật sau (ta viết = thay cho ký hiệu ): (Phản xạ) (Kết hợp) (Đối xứng) (Bắc cầu) * Phép thay thế (substitution) Ta ký hiệu M[N/x] là phép thay thế x bởi N trong M với x là một biến tự do trong M. Ta định nghĩa phép thay thế như sau: 17 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.(M[y’/y][N/x]) nếu x ≠ y, y FV(N), y’ là biến mới * Phép rút gọn beta (β-reduction) Ta ký hiệu là phép rút gọn beta với các luật sau: (Kết hợp trái) (Kết hợp phải) Ví dụ ta kết hợp tính toán lambda để biểu diễn ngữ nghĩa cho câu sau: (2) Pedro owns a donkey. Khi phân tích cú pháp của câu này, ta có các luật sau: S -> NP, VP VP -> TV, NP NP -> PN NP -> Det, Noun Biểu diễn lambda của các thành phần câu tương ứng với phân tích này là: Thành phần câu Biểu diễn lambda Áp dụng Noun λx.DONKEY(x) (danh từ chung) 18 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. w(Q(w) ^ R(w)) (lượng từ: ở đây là lượng từ tồn tại) Các thành phần trên kết hợp thành câu, quá trình kết hợp được thực hiện theo phân tích cú pháp.