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