Giáo trình Trí tuệ nhân tạo

n ‰ Áp dụng các luật có mệnh đề giả thiết được thỏa mãn trong KB ‰ Bổ sung kết luận của các luật đó vào KB 49Trí tuệ nhân tạo Suy diễn tiến – Ví dụ (1) 50Trí tuệ nhân tạo Suy diễn tiến – Ví dụ (2) 51Trí tuệ nhân tạo Suy diễn tiến – Ví dụ (3) 52Trí tuệ nhân tạo Suy diễn tiến – Ví dụ (4) 53Trí tuệ nhân tạo Suy diễn tiến – Ví dụ (5) 54Trí tuệ nhân tạo Suy diễn tiến – Ví dụ (6) 55Trí tuệ nhân tạo Suy diễn tiến – Ví dụ (7) 56Trí tuệ nhân tạo Suy diễn lùi (backward chaining) „ Ý tưởng: Quá trình suy diễn bắt đầu từ mệnh đề kết luận Q ể ằ ề„ Đ chứng minh Q b ng tập mệnh đ (cơ sở tri thức) KB ‰ Kiểm tra xem Q đã được chứng minh (trong KB) chưa, ‰ Nếu chưa, tiếp tục chứng minh tất cả các mệnh đề giả thiết của ề ếmột luật nào đó (trong KB) có mệnh đ k t luận là Q „ Tránh các vòng lặp ‰ Kiểm tra xem các mệnh đề mới đã có trong danh sách các mệnh đề cần chứng minh chưa? – Nếu rồi, thi không bổ sung (lại) nữa! „ Tránh việc chứng minh lặp lại đối với 1 mệnh đề ‰ Đã được chứng minh (trước đó) là đúng ‰ Đã được chứng minh (trước đó) là không thể thỏa mãn được (sai) trong KB 57Trí tuệ nhân tạo Suy diễn lùi – Ví dụ (1) 58Trí tuệ nhân tạo Suy diễn lùi – Ví dụ (2) 59Trí tuệ nhân tạo Suy diễn lùi – Ví dụ (3) 60Trí tuệ nhân tạo Suy diễn lùi – Ví dụ (4) 61Trí tuệ nhân tạo Suy diễn lùi – Ví dụ (5) 62Trí tuệ nhân tạo Suy diễn tiến hay Suy diễn lùi? „ Suy diễn tiến là quá trình dựa trên dữ liệu (data-driven) Ví d iệ hậ d đối t iệ đ ết đị h‰ ụ: v c n n ạng ượng, v c ưa ra quy n „ Suy diễn tiến có thể thực hiện nhiều bước suy diễn dư thừa chẳng liên quan tới (cần thiết cho) mục tiêu cần– chứng minh „ Suy diễn lùi là quá trình hướng tới mục tiêu (goal driven)- , phù hợp cho việc giải quyết vấn đề ‰ Ví dụ: Làm sao để giành được học bổng của 1 chương trình PhD? 63Trí tuệ nhân tạo Logic định đề - Ưu và nhược điểm „ (+) Logic định đề cho phép dễ dàng phát biểu (biểu diễn) cơ sở tri thức bằng tập các mệnh đề „ (+) Logic định đề cho phép làm việc với các thông tin ở dạng phủ định, dạng tuyển (disjunctive) „ (+) Logic định đề có tính cấu tạo (kết cấu) ‰ Ngữ nghĩa của mệnh đề (S1 ∧ S2) được suy ra từ ngữ nghĩa của S1 và ngữ nghĩa của S2 „ (+) Ngữ nghĩa trong logic định đề không phụ thuộc ngữ cảnh (context independent)- ‰ Không như trong ngôn ngữ tự nhiên (ngữ nghĩa phụ thuộc vào ngữ cảnh của các câu nói) „ (-) Khả năng diễn đạt (biểu diễn) của logic định đề là rất hạn chế ‰ Logic định đề không thể diễn đạt được (như trong ngôn ngữ tự nhiên): “Nếu X là cha của Y, thì Y là con của X” ‰ Logic định đề phải liệt kê (xét) mọi khả năng gán giá trị chân lý (đúng/sai) cho X và Y 64Trí tuệ nhân tạo Giới hạn của Logic định đề „ Hãy xét ví dụ sau đây: T ấ là ột i h iê ủ HUT‰ u n m s n v n c a ‰ Mọi sinh viên của HUT đều học môn Đại số ‰ Vì Tuấn là một sinh viên của HUT nên Tuấn học môn Đại số , „ Trong logic định đề: Định đề p: “Tuấn là một sinh viên của HUT”‰ ‰ Định đề q: “Mọi sinh viên của HUT đều học môn Đại số” ‰ Định đề r: “Tuấn học môn Đại số” ‰ Nhưng: (trong logic định đề) r không thể suy ra được từ p và q! 65Trí tuệ nhân tạo Logic vị từ (FOL) – Ví dụ „ Ví dụ nêu trên có thể được biểu diễn trong logic vị từ bởi các biểu thức (logic vị từ) sau ‰ HUT_Student(Tuan): “Tuấn là một sinh viên của HUT” ‰ ∀x:HUT_Student(x) → Studies_Algebra(x): “Mọi sinh viên của HUT đều học môn Đại số” ‰ Studies_Algebra(Tuan): “Tuấn học môn Đại số” „ Trong logic vị từ, chúng ta có thể chứng minh được: {HUT Student(Tuan) ∀x:HUT Student(x) →_ , _ Studies_Algebra(x)} Ⱶ Studies_Algebra(Tuan) „ Với ví dụ trên, trong logic vị từ: ầ ằ ế‰ Các ký hiệu Tuan, x được gọi là các ph n tử (Tuan là h ng, x là bi n) ‰ Các ký hiệu HUT_Student và Studies_Algebra là các vị từ ‰ Ký hiệu ∀ là lượng từ với mọi ầ ử ể ễ ể‰ Các ph n t , các vị từ và các lượng từ cho phép bi u di n các bi u thức 66Trí tuệ nhân tạo FOL – Ngôn ngữ (1) „ 4 kiểu ký hiệu (symbols) ‰ Hằng (Constants): Các tên của các đối tượng trong một lĩnh vực bài toán cụ thể (ví dụ: Tuan) ‰ Biến (Variables): Các ký hiệu mà giá trị thay đổi đối với các đối tượng khác nhau (ví dụ: x) ‰ Ký hiệu hàm (Function symbols): Các ký hiệu biểu diễn ánh xạ (quan hệ hàm) từ các đối tương của miền (domain) này sang các đối tượng của miền khác (ví dụ: plus) ‰ Các vị từ (Predicates): Các quan hệ mà giá trị logic là đúng hoặc sai (ví dụ: HUT_Student and Studies_Algebra) Mỗi ký hiệ hà h ặ ị từ đề ó ột tậ á th ố„ u m o c v u c m p c c am s ‰ Ví dụ: HUT_Student và Studies_Algebra là các vị từ có 1 tham số ‰ Ví dụ: plus là một ký hiệu hàm có 2 tham số 67Trí tuệ nhân tạo FOL – Ngôn ngữ (2) „ Một phần tử (term) được định nghĩa (truy hồi) như sau ‰ Một hằng số là một phần tử ‰ Một biến là một phần tử ‰ Nếu t1, t2,…,tn là các thành phần và f là một ký hiệu hàm có n tham số thì f(t t t ) là một phần tử , 1, 2,…, n ‰ Không còn gì khác là một phần tử „ Các ví dụ của phần tử (term) ‰ Tuan ‰ 2 f i d(T )‰ r en uan ‰ friend(x) ‰ plus(x,2) 68Trí tuệ nhân tạo FOL – Language (3) „ Các nguyên tử (Atoms) ‰ Nếu t t t là các thành phần (terms) và p là một vị từ có n 1, 2,…, n tham số, thì P(t1,t2,…,tn) là một nguyên tử (atom) ‰ Ví dụ: HUT_Studies(Tuan), HUT_Studies(x), Studies Algebra(Tuan), Studies(x)_ „ Các biểu thức (Formulas) được định nghĩa như sau ‰ Một nguyên tử (atom) là một biểu thức ‰ Nếu φ và ψ là các biểu thức, thì ¬φ và φ∧ψ là các biểu thức ‰ Nếu φ là một biểu thức và x là một biến, thì ∀x:φ là một biểu thức ‰ Không còn gì khác là một biểu thức „ Lưu ý: ∃x:φ được định nghĩa bằng ¬∀x:¬φ 69Trí tuệ nhân tạo FOL – Ngữ nghĩa (1) „ Một phép diễn giải (interpretation) của một biểu thức φ được biểu diễn bằng cặp , „ Miền giá trị (Domain) D là một tập khác rỗng Hà diễ iải (I t t ti f ti ) I là ột hé„ m n g n erpre a on unc on m p p gán giá trị đối với mỗi hằng, ký hiệu hàm, và ký hiệu vị từ – sao cho: ‰ Đối với hằng c: I(c) ∈D ‰ Đối với ký hiệu hàm (có n tham số) f: I(f): Dn→D Đối ới ký hiệ ị từ ( ó th ố) I( ) D { }‰ v u v c n am s P: P : n→ true, false 70Trí tuệ nhân tạo FOL – Ngữ nghĩa (2) „ Diễn giải đối với một biểu thức logic vị từ. Giả sử φ, ψ và λ là các biểu thức vị từ ‰ Nếu φ là ¬ψ, thì I(φ)=sai nếu I(ψ)=đúng, và I(φ)=đúng nếu I(ψ)=sai ‰ Nếu φ là (ψ∧λ), thì I(φ)=sai nếu I(ψ) hoặc I(λ) là sai, và I(φ)=true nếu cả I(ψ) và I(λ) là đúng Giả ử ∀ φ( ) là ột biể thứ thì‰ s x: x m u c, I(∀x:φ(x))=đúng nếu I(φ)(d)=đúng với mọi giá trị d ∈D 71Trí tuệ nhân tạo FOL – Ngữ nghĩa (3) „ Một biểu thức φ là thỏa mãn được (satisfiable) nếu và chỉ nếu tồn tại một phép diễn giải sao cho I(φ) – , Chúng ta ký hiệu là: ╞I φ „ Nếu ╞I φ, thì chúng ta nói rằng I là một mô hình ( d l) ủ φ Nói á h khá I thỏ ã ( ti fi ) φmo e c a . c c c, a m n sa s es „ Một biểu thức là không thể thỏa mãn được (unsatisfiable) nếu và chỉ nếu không tồn tại bất kỳ phép diễn giải nào „ Một biểu thức φ là đúng (valid) nếu và chỉ nếu mọi phép diễ iải I đề thỏ ã φ Chú t ký hiệ là ╞ φn g u a m n – ng a u : 72Trí tuệ nhân tạo Lượng tử logic Với mọi „ Cú pháp của lượng tử logic Với mọi (universal quantifier): ∀: „ Ví dụ: Tất cả (mọi) sinh viên đang ngồi học trong lớp K4 đều chăm chỉ ∀ N i t l ( K4) Ch hi( )x: go _ rong_ op x, ⇒ am_c x „ Mệnh đề (∀x: P) là đúng trong một mô hình m, khi và chỉ khi P đúng với x là mỗi (mọi) đối tượng trong mô hình đó „ Tức là, mệnh đề (∀x: P) tương đương với sự kết hợp (và) của tất cả các trường hợp của P N i t l (H K4) Ch hi(H )go _ rong_ op ue, ⇒ am_c ue ∧ Ngoi_trong_lop(Cuong,K4) ⇒ Cham_chi(Cuong) ∧ Ngoi_trong_lop(Tuan,K4) ⇒ Cham_chi(Tuan) ∧ … 73Trí tuệ nhân tạo Lượng tử logic Tồn tại „ Cú pháp của lượng tử logic Tồn tại (existential quantifier): ∃: „ Ví dụ: Tồn tại (có) sinh viên đang ngồi học trong lớp K4, và là sinh viên chăm chỉ: ∃ N i t l ( K4) Ch hi( )x: go _ rong_ op x, ∧ am_c x „ Mệnh đề (∃x: P) là đúng trong một mô hình m, khi và chỉ khi P là đúng với x là một đối tượng trong mô hình đó „ Tức là, mệnh đề (∃x: P) tương đương với phép tuyển (hoặc) của các trường hợp của P N i t l (H K4) Ch hi(H )go _ rong_ op ue, ∧ am_c ue ∨ Ngoi_trong_lop(Cuong,K4) ∧ Cham_chi(Cuong) ∨ Ngoi_trong_lop(Tuan,K4) ∧ Cham_chi(Tuan) ∨ … 74Trí tuệ nhân tạo Các đặc điểm của các lượng từ logic „ Tính hoán vị: ‰ (∀x ∀y) là tương đương với (∀y ∀x) ‰ (∃x ∃y) là tương đương với (∃y ∃x) „ Tuy nhiên, (∃x ∀y) không tương đương với (∀y ∃x) ‰ ∃x ∀y: Yeu(x,y) - “Trên thế giới này, tồn tại (có) một người mà người đó yêu quý tất cả mọi người khác” ‰ ∀y ∃x: Loves(x,y) - “Trên thế giới này, mọi người đều được ít nhất một người khác yêu thích” „ Mỗi lượng từ logic (∃ hoặc ∀) đều có thể được biểu diễn bằng lượng từ kia ‰ (∀x: Thich(x,Kem)) là tương đương với (¬∃x: ¬Thich(x,Kem)) ‰ (∃x: Thich(x,BongDa)) là tương đương với (¬∀x: Thi h( B D ))¬ c x, ong a 75Trí tuệ nhân tạo Sử dụng logic vị từ Biểu diễn các phát biểu trong ngôn ngữ tự hiên n „ “x là anh/chị/em của y” tương đương với “x và y là anh em ruột” ∀x,y: Anh_chi_em(x,y) ⇔ Anh_em_ruot(x,y) “Mẹ của c là m” tương đương với “m là phụ nữ và m là„ bậc cha mẹ của c” ∀m,c: Me(c) = m ⇔ (Phu nu(m) ∧ Cha me(m,c))_ _ „ Quan hệ “anh em ruột” có tính chất đối xứng ∀x y: Anh em ruot(x y)⇔ Anh em ruot(y x), _ _ , _ _ , 76Trí tuệ nhân tạo Xây dựng cơ sở tri thức với logic vị từ 1. Xác định lĩnh vực bài toán (cần xây dựng cơ sở tri thức) Tậ h th thậ á t i thứ liê2. p ợp, u p c c r c n quan 3. Xác định tập hợp (từ vựng) của: các vị từ (quan hệ), các hàm và các hằng số, 4. Mã hóa (biểu diễn) các tri thức tổng quát về lĩnh vực bài toán 5. Mã hóa (biểu diễn) các mô tả của các ví dụ (trường hợp) cụ thể Kiể t thủ t diễ đặt á â hỏi (t ấ ) à6. m ra ục suy n: c c c u ruy v n v kiểm tra các câu trả lời nhận lại 7. Kiểm tra và sửa lỗi trong cơ sở tri thức 77Trí tuệ nhân tạo Trí Tuệ Nhân Tạo Nguyễn Nhật Quang quangnn-fit@mail.hut.edu.vn Viện Công nghệ Thông tin và Truyền thông Trường Đại học Bách Khoa Hà Nội Năm học 2009-2010 Nội dung môn học: „ Giới thiệu về Trí tuệ nhân tạo „ Tác tử „ Giải quyết vấn đề: Tìm kiếm, Thỏa mãn ràng buộc „ Logic và suy diễn ‰ Lập trình logic Prolog (Dựa trên bài giảng csc.villanova.edu/~dmatusze/8310summer2001/index.html/prolog1.ppt) „ Biểu diễn tri thức „ Suy diễn với tri thức không chắc chắn „ Học máy ế„ Lập k hoặch 2 Trí tuệ nhân tạo Lập trình logic „ Một chương trình logic biểu diễn một cơ sở tri thức (một tập các mệnh đề logic) „ Các mệnh đề logic phải ở dạng chuẩn Horn p1 ∧ p2 ∧ ∧ p → q1 ∨ q2 ∨ ∨ q… n … m „ Nếu n=0, m=1, thì q1 là một sự kiện (fact) „ Nếu n≥1, m=1, thì (p1 ∧ p2 ∧… ∧ pn→ q1) là một luật (rule) „ Nếu n≥1, m>1, thì tương đương với luật (p1 ∧ p2 ∧… ∧ )pn ∧ ¬q1 ∧ ¬q2 ∧… ∧ ¬qm-1 → qm 3Trí tuệ nhân tạo Ngôn ngữ lập trình logic Prolog „ Prolog = Programming Logic „ Một ngôn ngữ lập trình logic được sử dụng rất phổ biến „ Trong ngôn ngữ Prolog ‰ Các luật và các sự kiện là các tiên đề (axioms) Câ hỏi đ đ bởi ời dù là đị h lý ầ hứ i h‰ u , ược ưa ra ngư ng, n c n c ng m n „ Prolog áp dụng phương pháp suy diễn quay lui (Back Chaining) để chứng minh „ Để chứng minh P(a) ‰ Tìm sự kiện P(t) hoặc luật (Q1 ∧ Q2 ∧… ∧ Qn→ P(t)) ‰ Nếu tìm được sự kiện P(t) thay thế t=a định lý được chứng minh, , ‰ Nếu tìm được luật (Q1 ∧ Q2 ∧… ∧ Qn→ P(t)), thì cần tiếp tục chứng minh các giả thiết ‰ Nếu có các biến, tìm cách thay thế các biến này bằng các giá trị, sao cho đích chứng minh được thỏa mãn 4Trí tuệ nhân tạo Phần mềm SWI-Prolog „ SWI-Prolog là một công cụ lập trình Prolog được sử dụng rất phổ biến có các phiên bản chạy trên các hệ, điều hành Windows, MacOS, và Linux „ Bản quyền sử dụng phần mềm SWI-Prolog là miễn phí cho mục đích học tập và nghiên cứu „ SWI-Prolog có thể tải về từ địa chỉ: prolog.org/ 5Trí tuệ nhân tạo Ví dụ về chương trình Prolog (1) „ Suy diễn logic T ấ là ột i h iê ủ HUT‰ u n m s n v n c a ‰ Mọi sinh viên của HUT đều học môn Toán rời rạc ‰ Tuấn có học môn Toán rời rạc không? „ Chương trình Prolog ‰ studentHUT(tuan). ‰ studDiscretMath(X) :- studentHUT(X). ‰ ?- studDiscretMath(tuan). 6Trí tuệ nhân tạo Ví dụ về chương trình Prolog (2) „ Sự kiện: Tuấn là một sinh viên của HUT t d tHUT(t )‰ s u en uan . „ Luật: Mọi sinh viên của HUT đều học môn Toán rời rạc ‰ studDiscretMath(X) : studentHUT(X)- . „ Câu hỏi (của người dùng): Tuấn có học môn Toán rời rạc không? ‰ ?- studDiscretMath(tuan). „ Các câu hỏi có cùng dạng như các sự kiện 7Trí tuệ nhân tạo Chạy chương trình Prolog (1) „ Sử dụng một chương trình soạn thảo (vd: Notepad) để tạo ra chương trình (cơ sở tri thức) „ Ghi lại chương trình trong một tập tin định dạng văn bản (text only) sử dụng đuôi của tập tin là .pl „ Ví dụ một chương trình Prolog: studentHUT(tuan). studDiscretMath(X) :- studentHUT(X). 8Trí tuệ nhân tạo Chạy chương trình Prolog (2) „ Để chạy chương trình Prolog: (Với hệ điề hà h Wi d ) kí h đú lê tậ ti h t ì h‰ u n n ows , c p n p n c ương r n , hoặc ‰ Chạy phần mềm SWI-Prolog, và tham vấn (consult) tới tập tin h t ì hc ương r n ?- consult('C:\\PrologPrograms\\myPrologProg.pl'). „ Sau đó đưa ra câu hỏi mong muốn, ?- studDiscretMath(tuan). „ Prolog đưa ra câu trả lời Yes 9Trí tuệ nhân tạo Prolog – Chứng minh định lý „ Prolog trả về giá trị Yes có nghĩa là “chứng minh được” P l t ả ề iá t ị N ó hĩ là “khô thể hứ„ ro og r v g r o c ng a ng c ng minh” ?- stud DiscretMath(hai)_ . No „ Closed world assumption: Chương trình Prolog biết tất ả ề hữ ì ó ầ biếtc v n ng g n c n „ Prolog cung cấp các giá trị cho các biến khi cần, để có thể hoàn chỉnh một chứng minh ?- stud_DiscretMath(X). X = tuan 10Trí tuệ nhân tạo Cú pháp: Các cấu trúc „ Một cấu trúc (structure) gồm một tên (name) và không, một hoặc nhiều tham số (arguments), „ Bỏ đi cặp dấu ngoặc (), nếu như không có tham số „ Các ví dụ của cấu trúc ‰ sunshine ‰ man(socrates) ‰ path(garden, south, sundial) 11Trí tuệ nhân tạo Cú pháp: Các mệnh đề cơ sở „ Một cấu trúc chính là một mệnh đề cơ sở (base clause) Một ệ h đề ở biể diễ ột kiệ (f t)„ m n cơ s u n m sự n ac „ Các ví dụ của mệnh đề cơ sở j hn‰ o . ‰ mary ‰ bill ‰ loves(john, mary). ‰ loves(mary, bill). 12Trí tuệ nhân tạo Cú pháp: Biểu diễn luật „ Một luật được biểu diễn bao gồm Một ấ t ú (biể diễ ệ h đề kết l ậ ủ l ật ệ h đề‰ c u r c u n m n u n c a u – m n THEN) ‰ Ký hiệu :- ‰ Một danh sách các cấu trúc (biểu diễn mệnh đề giả thiết của luật – mệnh đề IF), ngăn cách nhau bởi dấu , „ Các ví dụ của luật ‰ mortal(X) :- man(X). ‰ happy(X) :- healthy(X), wealthy(X), wise(X). „ Dấu , giữa các cấu trúc có nghĩa như toán tử logic AND 13Trí tuệ nhân tạo Cú pháp: Các vị từ logic „ Một vị từ (predicate) là một tập hợp các mệnh đề với cùng tên và một số (>=1) các tham số „ Ví dụ: Các mệnh đề biểu diễn vị từ loves loves(john mary), . loves(mary, bill). loves(chuck, X) :- female(X), rich(X). 14Trí tuệ nhân tạo Cú pháp: Chương trình „ Một chương trình (program) là một tập hợp các mệnh đề „ Các mệnh đề trong chương trình có thể được sắp xếp theo bất kỳ trật tự (thứ tự) nào „ Các mệnh đề của một vị từ được sử dụng (được xét đến) theo đúng trật tự của chúng trong chương trình 15Trí tuệ nhân tạo Cú pháp: Các biến và hằng „ Các biến bắt đầu bằng chữ cái in hoa hoặc ký tự đặc biệt Vd X S t lt: , ocra es, _resu „ Các hằng không bắt đầu bằng chữ cái in hoa hoặc ký tự đặc biệt Vd: x, socrates „ Các hằng chứa các ký tự đặc biệt, hoặc bắt đầu với chữ ả ''cái in hoa, thì ph i đặt vào trong cặp ký tự nháy đơn Vd: 'C:\\My Documents\\examples.pl' Để hiển thị ký t nhá đơn thì phải sử d ng '' hoặc \'„ ự y , ụ : 16Trí tuệ nhân tạo Cú pháp: Chú thích „ Được đặt trong cặp dấu: /*…*/ H ặ đ đặt dấ %„ o c ược sau u „ Ví dụ t(x ) % s kiệ mô tả x là h m ủ‰ paren ,y . ự n c a ẹ c a y 17Trí tuệ nhân tạo Cú pháp: Các lỗi hay gặp „ Phân biệt giữa chữ hoa và chữ thường là rất quan trọng Khô đ ó kh ả t ắ ( h t ) iữ„ ng ược c o ng r ng space c arac ers g a tên và danh sách tham số của một cấu trúc ‰ Biểu diễn hợp lệ: man(socrates). ‰ Biểu diễn không hợp lệ: man (socrates). „ Kết thúc của mỗi mệnh đề phải có dấu chấm (.) ‰ Có thể đặt dấu chấm ở dòng kế tiếp 18Trí tuệ nhân tạo Suy diễn lùi trong Prolog „ Giả sử chúng ta có cơ sở tri thức (chương trình Prolog): loves(chuck X) :- female(X) rich(X), , . female(jane). female(mary). rich(mary). „ Giả sử người dùng đặt câu hỏi loves(chuck, X) „ Quá trình suy diễn lùi (Back chaining) của Prolog: ‰ female(X) = female(jane) X = jane, . rich(jane). : thất bại (không thể chứng minh được!) ‰ female(X) = female(mary), X = mary. rich(mary) : thành công (chứng minh được!). 19Trí tuệ nhân tạo Các lời gọi „ Mỗi lời gọi (call) trong chương trình Prolog được thể hiện bởi: call fail exit redo „ Mỗi cấu trúc (trong chương trình Prolog) có bốn cổng (ports): call, exit, redo, fail „ Cổng exit kết nối với cổng call „ Cổng fail kết nối với cổng redo 20Trí tuệ nhân tạo Các lời gọi lồng nhau (nested calls) „ loves(chuck, X) :- female(X), rich(X). loves(chuck X), female(X) rich(X) call fail exit redo 21Trí tuệ nhân tạo Các câu trả lời bổ sung f l (j )„ ema e ane . female(mary). female(susan) female(X) . „ ?- female(X). X j female(jane) = ane X = mary X female(mary) = susan Yes female(susan) 22Trí tuệ nhân tạo Các cách đọc „ loves(chuck, X) :- female(X), rich(X). Cá h đ th kiể kh i bá Ch k ê X ế X là h„ c ọc eo u a o: uc y u n u p ụ nữ và giàu có „ Cách đọc theo kiểu thủ tục xấp xỉ: Để tìm được một đối tượng X mà Chuck yêu, thì trước tiên phải tìm được một phụ nữ X, sau đó kiểm tra xem X có giàu hay không Cá h đ th kiể kh i bá th ờ đ thí h h„ c ọc eo u a o ư ng ược ưa c ơn 23Trí tuệ nhân tạo Logic đơn điệu „ Logic đơn điệu (monotonic logic): Một khi chứng i h đ ột điề ì đó là đú thì điề đó ẽ ãim n ược m u g ng, u s m mãi đúng „ Logic đơn điệu không phù hợp với các bài toán (ứng dụng) thực tế ‰ Nếu cái ví ở trong túi xách tay và túi xách tay ở trong xe ô-tô, thì chúng ta có thể kết luận là cái ví ở trong xe ô tô - ‰ Nhưng, điều gì xảy ra nếu cái ví được lấy ra khỏi xe ô-tô? 24Trí tuệ nhân tạo Logic không đơn điệu „ Prolog sử dụng logic không đơn điệu (nonmonotonic logic) ‰ Một mệnh đề được chứng minh là đúng ở một thời điểm trước có thể không còn (không thể được chứng minh) là đúng ở một thời điểm sau „ Trong Prolog các sự kiện và các luật có thể được thay đổi , ở một thời điểm nào đó ‰ Những sự kiện và luật như vậy được gọi là động (không cố định) „ assert(...) : để bổ sung một sự kiện hoặc một luật vào cơ sở tri thức „ retract( ) : để loại bỏ một sự kiện hoặc một luật khỏi cơ sở tri... thức „ assert và retract được gọi là các vị từ ngoài logic (extralogical predicates) 25Trí tuệ nhân tạo Các ví dụ về assert và retract „ assert(man(plato)). t((l ( h k X) f l (X) i h(X)))„ asser oves c uc , :- ema e , r c . „ retract(man(plato)). „ retract((loves(chuck X) :- female(X) rich(X))), , . „ Lưu ý là đối với các luật, phải sử dụng 2 cặp ngoặc đơn ((…)) ‰ Để tránh xảy ra lỗi cú pháp Giả ử ế iết ss t(f : b b )‰ s n u v : a er oo - ar, az . ‰ Sẽ có bao nhiêu tham số đối với assert? 26Trí tuệ nhân tạo Sử dụng Prolog trong bài toán thực tế „ Trong các bài toán (ứng dụng) thực tế, mọi thứ có thể thay đổi (một điều đã chứng minh là đúng thì có , thể sẽ không còn đúng vào một thời điểm sau đó) „ Prolog rất phù hợp cho việc biểu diễn các thay đổi trong các bài toán thực tế „ Các ứng dụng trò chơi là một ví dụ điển hình về các ể ổbài toán mà trong đó các sự việc có th thay đ i „ Prolog là ngôn ngữ rất phù hợp để xây dựng các h t ì h t ò h i hiểc ương r n r c ơ mạo m 27Trí tuệ nhân tạo Ví dụ minh họa chương trình trò chơi „ Chạy ứng dụng SWI-Prolog… Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.59) Copyright (c) 1990-2008 University of Amsterdam. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit for details. For help, use ?- help(Topic). or ?- apropos(Word) 1 ?- consult('C:\\prolog\\dragon.pl'). % C:\prolog\dragon.pl compiled 0.00 sec, 12,468 bytes true. 28Trí tuệ nhân tạo Các lệnh của trò chơi „ ?- start. E t d i t d d P l tn er comman s us ng s an ar ro og syn ax. Available commands are: start. -- to start the game. t i th t di tin. s. e. w. -- o go n a rec on. take(Object). -- to pick up an object. drop(Object). -- to put down an object. (Obj t) t bj tuse ec . -- o use an o ec . attack. -- to attack an enemy. look. -- to look around you again. i i hi instruct ons. -- to see t s message aga n. halt. -- to end the game and quit. 29Trí tuệ nhân tạo Bắt đầu chương trình „ You are in a meadow. To the north is the dark th f t th th i ll b ildi mou o a cave; o e sou s a sma u ng. Your assignment, should you decide to accept it, is to recover the famed Bar-Abzad ruby and return it to this meadow. true. 30Trí tuệ nhân tạo Đi về hướng nam „ ?- s. You are in a small building. The exit is to the north. The room is devoid of furniture, and the only feature seems to be a small door to the east. There is a flashlight here. true. 31Trí tuệ nhân tạo Lấy đồ vật, Cửa bị khóa „ ?- take(flashlight). OK. true. „ ?- e. The door appears to be locked. You can't go that way. true. 32Trí tuệ nhân tạo Mở khóa cửa, Quan sát „ ?- use(key). The closet is no longer locked. true. „ ?- look. Y i bi d k Th i i f tidou are n a g, ar cave. e a r s e . There is a chest here. true. 33Trí tuệ nhân tạo Biểu diễn các sự kiện „ Vị trí (nơi) hiện tại của tôi: ‰ i am at(meadow)_ _ . „ Vị trí của các đồ vật: ‰ at(flashlight building), . „ Tôi đang giữ (nắm) đồ vật gì: ‰ holding(key). „ Những sự kiện nào có thể được thay đổi: ‰ :- dynamic i am at/1 at/2 holding/1_ _ , , . 34Trí tuệ nhân tạo Đầu vào và đầu ra „ Đầu vào (input) là các lệnh (các câu hỏi) trực tiếp đối với Prolog ‰ take(flashlight). Đầ à ( t t) ử d it ( ) để đ á hiể„ u v o ou pu : s ụng wr e ... ưa ra c c n thị „ Sử dụng nl để kết thúc dòng hiển thị (để bắt đầu viết dòng hiển thị mới) „ Ví dụ: describe(closet) :- it ('Y i ld t l t ') lwr e ou are n an o s orage c ose . , n . 35Trí tuệ nhân tạo Bản đồ của trò chơi N cave_entrance cave W E S meadow b ildi l tu ng c ose 36Trí tuệ nhân tạo Biểu diễn bản đồ „ path(cave, w, cave_entrance). th( t )pa cave_en rance, e, cave . „ path(meadow, s, building). path(building, n, meadow). „ Hoặc có thể biểu diễn như sau: ‰ path(cave, w, cave_entrance). path(X, e, Y) :- path(Y, w, X). 37Trí tuệ nhân tạo Liệt kê „ Liệt kê các mệnh đề của một vị từ là một cách để kiể t t thái hiệ t i ủ h t ì h ( ở t im ra rạng n ạ c a c ương r n cơ s r thức) Cú há li ti ( di t )„ p p: s ng pre ca e „ ?- listing(at). (k )‰ at ey, cave_entrance . at(flashlight, building). at(sword, closet). true. 38Trí tuệ nhân tạo Di chuyển theo các hướng „ Biểu diễn việc di chuyển theo 4 hướng tương ứng với 4 lệnh n, s, e, w, sử dụng vị từ go „ n :- go(n). s :- go(s). e :- go(e). ( )w :- go w . 39Trí tuệ nhân tạo Vị từ go „ go(Direction) :- i_am_at(Here), path(Here, Direction, There), retract(i am at(Here)),_ _ assert(i_am_at(There)), look. „ go(_) :- write('You can''t go that way.'). 40Trí tuệ nhân tạo Vị từ take „ take(X) :- i am at(Place)_ _ , at(X, Place), retract(at(X, Place)), assert(holding(X)), write('OK.'), nl. „ take(X) :- holding(X), it ('Y \' l d h ldi it!') lwr e ou re a rea y o ng , n . „ take(X) :- it ('I d \'t it h ') lwr e on see ere. , n . 41Trí tuệ nhân tạo Sử dụng từ khóa fail „ Một vị từ thất bại (fail) nếu nó không thành công (không thể chứng minh được) „ Có thể phát biểu rõ ràng một mệnh đề là thất bại, bằng cách sử dụng fail fail call fail „ Sử dụng fail chỉ đảm bảo là mệnh đề hiện tại của vị ấ ắtừ là th t bại; chứ không b t buộc toàn bộ vị từ là thất bại 42Trí tuệ nhân tạo Cắt „ Sử dụng cắt, được ký hiệu là ! , như là một điểm kết thúc ‰ Kết thúc việc đánh giá mệnh đề hiện tại ở vị trí cắt „ Ý nghĩa của cắt: Không xem xét (thêm nữa) bất kỳ mệnh đề nào khác ! call exit 43Trí tuệ nhân tạo Sử dụng kết hợp cắt-thất bại „ Sử dụng kết hợp cắt-thất bại, ký hiệu là !, fail , sẽ có nghĩa chỉ định rằng toàn bộ vị từ là thất bại (không thể chứng minh được) ế ề„ !, fail k t thúc mệnh đ hiện thời, và chỉ định vị từ thất bại ! f l ấ ề„ Theo sau , ai sẽ không có b t kỳ mệnh đ nào của vị từ được xem xét nữa, và vì vật toàn bộ vị từ sẽ thất bại 44Trí tuệ nhân tạo Ví dụ về !, fail „ Biểu diễn cửa của phòng kho bị khóa „ path(building, e, closet) :- locked(closet), write('The door appears to be locked.'), nl, !, fail. path(building, e, closet). „ Nếu cửa của phòng kho không bị khóa, thì mệnh đề thứ nhất sẽ thất bại “một cách bình thường”, và mệnh đề thứ hai sẽ được