Xem mẫu
- Lec 11-13
Lập trình logic
Prolog
Lec 11-13. p.1
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
nguon tai.lieu . vn
