Bài giảng Trí tuệ nhân tạo - Chương 5: Ngôn ngữ Lập trình Prolog - Lê Thanh Hương

1Chương 5 . Ngôn ngữ lập trình Prolog Lê Thanh Hương Khoa CNTT Đại học Bách khoa Hà Nội 5.1. Giới thiệu ếŠ PROgramming in LOGic (sử dụng cách ti p cận logic) Š Alain Calmerauer & Philippe Roussel, 1972 Š Dùng ngôn ngữ mô tả/khai báo (declarative language) để đặc tả vấn đề Š Ứng dụng nhiều trong xử lý ngôn ngữ tự nhiên 2 và TTNT. Š Turbo Prolog, Visual Prolog, B-Prolog, SWI- Prolog, Lê Thanh Hương – Khoa CNTT - ĐHBKHN 5.2. Cú pháp Š Chương trình là tập các mô tả logic vị từ dưới dạng chuẩn Horn „ Không có cấu trúc điều khiển (rẽ nhánh, lặp) „ Không có phép gán Š Vị từ được diễn giải thông qua sự kiện và 3 luật, kết thúc bằng ký tự ‘.’. Š Prolog trả lời các câu hỏi nhờ cơ chế suy luận dựa trên kiến thức được cung cấp Lê Thanh Hương – Khoa CNTT - ĐHBKHN Ví dụ owns(john,house). owns(mary,house). young(john). rich(X) :- owns(X,house). talent(X) :- rich(X), young(X). sự kiện luật Chương trình 4 ?- consult(‘E:\\swi_prolog\\test.pl’). ?- talent(john). YES ?- talent(X). X = john Truy vấn 25.2.1 Sự kiện Š Sự kiện là những điều ta công nhận là đúng Š Ví dụ: cat(tom). khoang_cach(‘Hà nội’,’TP Hồ Chí Minh’,2000). Š Tên vị từ bắt đầu bằng kí tự thường 5 Š Chuỗi kí tự đặt trong ‘ ‘ Š Biến bắt đầu bằng chữ hoa. Lê Thanh Hương – Khoa CNTT - ĐHBKHN 5.2.2 Luật Sử d để đị h hĩ ột ị từ ( hệ) ới d t êŠ ụng n ng a m v quan m ựa r n các vị từ (quan hệ) đã biết. Š Gồm 2 phần, phân cách bởi dấu :- Š Ví dụ: giaithua(N,Kq):- N1 is N-1, giaithua(N1,Kq1), Kq is Kq1*N. Š VT là vị từ cần xác định; VP là điều kiện để VT nhận giá trị đúng 6 Š VP gồm các lời gọi vị từ khác, ngăn cách bởi dấu “,” Š Tham số truyền trong các vị từ không được là biểu thức. Š Ví dụ: giaithua(N-1,kq). %sai Lê Thanh Hương – Khoa CNTT - ĐHBKHN 5.3. Cơ chế tìm lời giải của Prolog nguoi(socrate). nguoi(xeda). vua(xeda). ?- consult(‘E:\\swi prolog\\a.pl’). Chương trình 7 _ ?- vua(xeda). YES ?- nguoi(X), vua(X). X = xeda Truy vấn Lê Thanh Hương – Khoa CNTT - ĐHBKHN 5.3. Cơ chế tìm lời giải của Prolog ?- nguoi(X), vua(X). X=socrate, vua(socrate) r1 - nguoi(socrate). r2 - nguoi(xeda). r3 - vua(xeda). X=xeda, vua(xeda) 8 Không thành công Quay lui Thành công Lê Thanh Hương – Khoa CNTT - ĐHBKHN 35.3. Cơ chế tìm lời giải của Prolog 1. So khớp 2. Tạo mối liên kết giữa các thông số ở phần câu hỏi và các thông số của các sự kiện và luật trong chương trình. 3 Thực thi tiếp các luật 9 . . 4. Nếu thực thi thành công (các biến ở phần câu hỏi đã ở tình trạng bound) Æ có lời giải Lê Thanh Hương – Khoa CNTT - ĐHBKHN Điều khiển quá trình quay lui (backtracking) ầ ếŠ Prolog tự động quay lui khi c n thi t Š Có thể điều khiển quá trình thực thi của chương trình bằng cách sắp lại thứ tự các mệnh đề Š Nhát cắt là một toán tử dùng để ngăn cản quá trình backtracking của Prolog. nhát cắt 10 Š Ví dụ: f(X,0):- X <3. f(X,2) :- 3=<X, X<6. f(X,4) :- 6=<X. f(X,0):- X <3, !. f(X,2) :- 3=<X, X<6, !. f(X,4) :- 6=<X. Lê Thanh Hương – Khoa CNTT - ĐHBKHN Các phép toán số học Š + Š - Š * Š / (chia số thực) Š // (chia số nguyên) Š mod Š ** (luỹ thừa) Š between(Low,High,Value) Š succ(Int1,Int2) Š plus(Int1,Int2,Int3) 11 Š phép gán: Bien is Bieu_thuc Š so sánh: , >= Lê Thanh Hương – Khoa CNTT - ĐHBKHN Bài tập 1 Cho góc X = 600 góc Y = 600 Chứng minh. , . các cạnh XY = XZ, XY = YZ bang(X,Y) banggoc(X,A) bangnhau(XY,UV) ??? 12 A + B + C = 180 Î C is 180 - A - B Lê Thanh Hương – Khoa CNTT - ĐHBKHN 4Bài tập 2. Chứng minh tứ giác nối trung điểm 4 cạnh của 1 tứ giác là hình bình hành. 3. Biết Tùng là bố của Dương. Dương là anh của Hoa. Hoa là mẹ của Trung. Trung là anh của Kiên. Cho biết mối quan hệ giữa Tùng và Kiên, giữa Dương và Kiên. 13 4. Tìm USCLN(X,Y) 5. Viết chương trình tính giai thừa cho số tự nhiên. giaithua(N,Kq):- N1 is N-1, giaithua(N1,Kq1), Kq is Kq1*N. Lê Thanh Hương – Khoa CNTT - ĐHBKHN 5.4. Danh sách (list) ầ ểŠ là dãy các ph n tử cùng ki u Š Ví dụ: [mai, ghita, sơn, trống] là list Š [ ] - list rỗng Š List khác rỗng gồm: „ phần tử đầu tiên (head) hầ ò l i (t il) 14 „ p n c n ạ a Š Dấu | được dùng để tách phần head và tail Š Phần tử của 1 list là bất kì loại đối tượng nào, kể cả list Lê Thanh Hương – Khoa CNTT - ĐHBKHN 5.4. Danh sách Š 3 cách viết danh sách: „ [Item1, Item2, ] „ [Head | Tail] „ [Item1, Item2, | others] 15 Š List được tổ chức bên trong bằng cây nhị phân Lê Thanh Hương – Khoa CNTT - ĐHBKHN Các thao tác với danh sách Š Chiều dài d/s length(L,Kq): chiều dài d/s L length( [ ], 0). length( [ _ | T], Kq) :- length(T,Kq1), Kq is Kq1 + 1 16 . _: biến vô danh Lê Thanh Hương – Khoa CNTT - ĐHBKHN 5Các thao tác với danh sách Š Quan hệ thành viên member(X, L): X có phải là 1 thành phần của L? Ví dụ: member(b, [a,b,c]).Æ true 17 member(H,[H | _ ]). member(H,[_| Tail]) :- member(H, Tail). Lê Thanh Hương – Khoa CNTT - ĐHBKHN Các thao tác với danh sách ốŠ N i d/s (concatenation) conc(L1, L2, L3): Nối L1 và L2 thành L3 ?- conc([a,b],[c,d],L). L = [a,b,c,d] conc([],L,L). conc([H|T1],L2,[H|T3]) :- conc(T1,L2,T3). 18 ?- conc(L1,L2, [a,b,c]). Š Thêm 1 phần tử vào d/s add(X,L, [X|L]). Lê Thanh Hương – Khoa CNTT - ĐHBKHN Các thao tác với danh sách ầŠ Xoá 1 ph n tử X ra khỏi d/s del(X,L,L1). del(X, [X|T], T). del(X, [Y|T], [Y|T1]) :- del(X,T,T1). ?- del(a,[a,b,a,a],L) L = [b,a,a] L = [a,b,a] 19 L = [a,b,a] Š Thêm 1 phần tử vào bất kì chỗ nào trong d/s insert(X,L,L1) :- del(X,L1,L). Lê Thanh Hương – Khoa CNTT - ĐHBKHN Bài tập 1. Tính chiều dài 1 danh sách 2. Tính tổng các phần tử của d/s 3. Viết thủ tục nghịch đảo 1 d/s. VD [1,2,3] -> [3,2,1] 4. Cài đặt chương trình phân tích cú pháp cho phép xác nhận câu “Tôi đọc” là câu đúng ngữ pháp. 1. C Æ CN VN 2. CN Æ DT 3. VN Æ ĐgT 4. DT Æ “tôi” 5. ĐgT Æ “đọc” Mở rộng cho trường hợp “tôi đọc sách”, “tôi đọc sách ngữ pháp” Xá đị h hầ ử hứ ủ d/5. c n p n t t n c a s 6. Tìm phần tử max và min của 1 d/s. Ví dụ: ?- maxmin([1,4,8,3],Max,Min). Max = 8 Min = 1 Yes Lê Thanh Hương – Khoa CNTT - ĐHBKHN