Bài giảng Trí tuệ nhân tạo - Lec 11+12+13: Lập trình logic Prolog - Phạm Thị Anh Lê

Nội dung text: Bài giảng Trí tuệ nhân tạo - Lec 11+12+13: Lập trình logic Prolog - Phạm Thị Anh Lê

1. Lec 11-13 Lập trình logic Prolog Lec 11-13. p.1
2. Nội dung ◼ Giới thiệu ngôn ngữ Prolog ◼ Các kiểu dữ liệu sơ cấp ◼ Sự kiện và luật trong Prolog ◼ Kiểu dữ liệu cấu trúc của Prolog ◼ Một số chương trình Prolog Lec 11-13. p.2
3. Giới thiệu ngôn ngữ Prolog ◼ Prolog là ngôn ngữ lập trình khai báo (declarative language), thích hợp để giải quyết các bài toán liên quan đến đối tượng và quan hệ giữa chúng ◼ Prolog được sử dụng phổ biến trong lĩnh vực TTNT ◼ Một chương trình Prolog là sự đặc tả một vấn đề, có thể được xem như một CSDL gồm các mệnh đề Horn (sự kiện - fact hoặc luật - rule). ◼ Nguyên lý lập trình của Prolog dựa trên mệnh đề Horn. Lec 11-13. p.3
4. Cú pháp ngôn ngữ Prolog ◼ Chương trình Prolog là một CSDL gồm các mệnh đề (clause), mỗi mệnh đề được xây dựng từ các vị từ (predicat) ◼ Một mệnh đề có thể là một sự kiện, luật hay câu hỏi ◼ Qui ước: – Sự kiện: (tương ứng với luật :- true) – Luật: :- – Câu hỏi: ?- ◼ Chú thích được đặt giữa hai dấu /* và */ hoặc sau ký hiệu % Lec 11-13. p.4
5. Các kiểu dữ liệu trong Prolog Kiểu dữ liệu Kiểu sơ cấp Kiểu phức hợp Hằng Biến Số Chuỗi ký tự Nguyên tử Các kiểu dữ liệu trong Prolog Lec 11-13. p.5
6. Các kiểu dữ liệu sơ cấp ◼ Hằng – Hằng số: số nguyên được dùng để đếm, số thực ít được dùng do Prolog là ngôn ngữ lập trình ký hiệu, phi số – Hằng logic: True, false – Hằng xâu ký tự: hằng xâu ký tự được đặt giữa 2 dấu nháy kép, hằng rỗng “” – Hằng nguyên tử ◼ Biến Lec 11-13. p.6
7. Xây dựng sự kiện Ví dụ: cây gia hệ biểu diễn mối quan hệ trong gia đình Lec 11-13. p.7
8. Xây dựng sự kiện (tiếp) ◼ Trên cả hình (a) và (b) xây dựng vị từ: parent(tom, bob) ◼ Trên hình a) xây dựng được các vị từ sau: parent(pam, bob) parent(bob, ann) parent(bob, pat) parent(pat, jim) parent(tom, liz) parent(tom, bob) Các câu hỏi: ?-parent(bob, pat) Yes ?-parent(liz, pat) No ?-parent(X, liz) X=tom Lec 11-13. p.8
9. Xây dựng sự kiện (tiếp) Các câu hỏi: ?-parent(X, Y) X=tom Y=liz ?-parent(Y, jim),parent(X, Y) X=pat Y=bob Yes ?-parent(X, ann),parent(X, pat) Yes Lec 11-13. p.9
10. Xây dựng luật Từ các quan hệ ở trên có thể xây dựng các luật: child(Y, X):-parent(X, Y) mother(X, Y):-parent(X, Y),woman(X) grandparent(X, Y):-parent(X, Z), parent(Z, Y) sister(X, Y):-parent(Z, X),parent(Z, Y),woman(X), different(X, Y) Lec 11-13. p.10
11. Xây dựng luật (tiếp) - Định nghĩa luật đệ quy: ancestor(X, Y):-parent(X, Z), ancestor(Z, Y) - Sử dụng biến: - haveachild(X) :- parent(X, Y) - Khi một biến chỉ xuất hiện một lần trong 1 mệnh đề thì không cần đặt tên, gọi là biến nặc danh have_a_child(X) :- parent(X, _) (mỗi vị trí xuất hiện dấu _ trong một mệnh đề tương ứng với một biến nặc danh mới) - someone_has_a_child :- parent(_, _) tương đương với someone_has_a_child :- parent(X, Y) Nếu biến nặc danh xuất hiện trong câu hỏi thì Prolog không hiển thị gía trị của biến này trong kết quả trả về Lec 11-13. p.11
12. Xây dựng luật (tiếp) - Ví dụ: Nếu muốn tìm kiếm những người có con mà không quan tâm đến tên con là gì: ?- parent(X, _) - hoặc tìm kiếm những người con mà không quan tâm đến tên cha mẹ là gì: ?- parent(_, X) Lec 11-13. p.12
13. Kiểu dữ liệu có cấu trúc ◼ Kiểu dữ liệu có cấu trúc tương tự cấu trúc bản ghi: đối tượng có nhiều thành phần, mỗi thành phần có thể là một cấu trúc Prolog xem mỗi thành phần như một đối tượng, để tổ hợp các thành phần thành một đối tượng duy nhất sử dụng hàm tử – Ví dụ: date(2, september, 2002); book(title(Name), author(Author), Year) ◼ So sánh và hợp nhất các hạng thức: – Phép so khớp trên các hạng thức và các vị từ : phép hợp nhất Lec 11-13. p.13
14. Kiểu dữ liệu có cấu trúc ◼ Hai hạng thức là hợp nhất được nếu: – chúng giống hệt nhau – các biến xuất hiện trong 2 hạng có thể được ràng buộc sao cho các hạng của mỗi đối tượng trở nên giống hệt nhau – Ví dụ: + date(D, M, 1890) và date(D1, May, Y1) là hợp nhất được + date(D, M, 1980) và date(D1, May, 2000) hay date(X, Y, Z) và point (X, Y, Z) không hợp nhất được Lec 11-13. p.14
15. Kiểu dữ liệu có cấu trúc ◼ Thuật toán hợp nhất Herbrand so khớp hai hạng thức S và T: – nếu S và T là các hằng, S và T chỉ khớp được nếu và chỉ nếu chúng có cùng giá trị (chỉ là một đối tượng) – Nếu S là biến, T là đối tượng, S và T khớp được nếu S được thay thế bởi T – Nếu S và T là các cấu trúc thì S và T khớp được nếu và chỉ nếu: • S và T có cùng một hàm tử chính • tất cả các thành phần khớp nhau từng đôi một Lec 11-13. p.15
16. Ngữ nghĩa của chương trình Prolog ◼ Prolog diễn giải chương trình: - – các sự kiện và luật xem như các tiên đề, câu hỏi của NSD xem như các định lý cần chứng minh – chứng minh định lý bằng cách chỉ ra định lý có thể được suy luận một cách logic từ các tiên đề. ◼ Về mặt thủ tục: Prolog sử dụng phương pháp suy diễn quay lui để hợp giải bài toán (chiến lược hợp giải) Lec 11-13. p.16
17. Ngữ nghĩa của chương trình Prolog 1. Ngữ nghĩa khai báo: – Thể hiện (instance) của mệnh đề C là mệnh đề C mà mỗi biến của nó được thay thế bởi một hạng – Biến thể (variant) của mệnh đề C là mệnh đề C mà mỗi biến của nó được thay thế bởi một biến khác. Ví dụ: Mệnh đề hasachild(X) :- parent(X, Y) có biến thể hasachild(X1) :- parent(X1, Y1) và thể hiện hasachild(john) :- parent(john, Z) Lec 11-13. p.17
18. Ngữ nghĩa của chương trình Prolog Cho một chương trình và đích G, ngữ nghĩa khai báo nói rằng: Một đích G là đúng (thỏa được, hay suy ra được từ chương trình một cách logic) nếu và chỉ nếu: tồn tại một mệnh đề C của chương trình sao cho tồn tại một thể hiện I của C sao cho: phần đầu của I giống hệt G và mọi đích của phần thân của I là đúng. Lec 11-13. p.18
19. Ngữ nghĩa của chương trình Prolog - Gói mệnh đề (packages of clauses): tập hợp các mệnh đề có cùng tên hạng tử chính (cùng tên, cùng số lượng tham đối) Ví dụ: a(X) :- b(X, _). a(X) :- c(X), e(X). a(X) :- f(X, Y). Các mệnh đề có cùng hạng là a(X), mỗi mệnh đề là một phương án giải bài toán đã cho. Prolog qui ước: mỗi dấu phẩy giữa các mệnh đề (đích) đóng vai trò phép hội; mỗi dấu chấm phẩy giữa các mệnh đề (đích) đóng vai trò phép tuyển. Ví dụ: P :- Q; R. tương đương với P :- Q. P :- R. Thứ tự ưu tiên: phép hội, phép tuyển Lec 11-13. p.19
20. Ngữ nghĩa của chương trình Prolog 2. Ngữ nghĩa logic: - Các mệnh đề không chứa biến - Các mệnh đề chứa biến - Ngữ nghĩa logic của các đích Lec 11-13. p.20
21. Ví dụ Giả sử chúng ta biết những thông tin sau: - An thích tất cả các môn Tin học mà cậu học - Cơ sở dữ liệu là môn Tin học - Trí tuệ nhân tạo là môn Tin học - An học Cơ sở dữ liệu - Nam thích học mọi môn học mà An thích học Lec 11-13. p.21
22. Ví dụ Các thông tin trên được biểu diễn trong Logic vị từ cấp một như sau: thích(An, x) :- tin_học(x), học(An, x) tin_học(CSDL) tin_học(TTNT) học(An, CSDL) thích(Nam, x) :- thich(An, x) Câu hỏi: “An thích môn học nào” được biểu diễn trong Prolog: ?thích(An, x) Lec 11-13. p.22
23. Ví dụ Khi câu hỏi được đưa vào, hệ Prolog sẽ thực hiện quá trình suy diễn logic để trả lời câu hỏi x= CSDL, tức là An thích môn CSDL - Thủ tục tìm câu trả lời của Prolog là cài đặt phương pháp suy diễn lùi, sử dụng kỹ thuật tìm kiếm theo chiều sâu - Các câu trong Prolog được xét từ trên xuống dưới, các đích con được xem xét làm thỏa mãn theo thứ từ từ trái sang phải. Lec 11-13. p.23
24. Ví dụ Cho đồ thị G với các đỉnh: A, B, C, D, E, F, H và các cung: (A, B), (A, C), (B, C), (B, D), (B, E), (E, F), (D, F), (F, H). Đường đi từ đỉnh X đến đỉnh Y được định nghĩa như sau: - hoặc có cung (X, Y) - hoặc có cung (X, Z) và đường đi (Z, Y) Yêu cầu: - Biểu diễn các thông tin trên trong logic vị từ cấp một - Tìm các đường đi trên đồ thị Lec 11-13. p.24