Bài giảng Trí tuệ nhân tạo - Bài 11: Prolog

1• Hiện nay đã có nhiều hệ lập trình logic ra đời mà tiêu 
biểu là Prolog. Prolog là viết tắt của cụm từ tiếng 
Pháp ”Programmation en Logique” 
• Hệ Prolog đầu tiên ra đời vào năm 1973 do Alain 
Colmerauer và nhóm trí tuệ nhân tạo thuộc Đại học 
tổng hợp Aix-Marseilie, Pháp xây dựng. 
• Mục đích ban đầu của hệ này là dịch các ngôn ngữ tự 
nhiên. 
SWI ROLOG
2• Điều khác nhau căn bản của lập trình Prolog so 
với lập trình truyền thống là: 
• • Trong Prolog người lập trình mô tả vấn đề 
bằng các câu trong logic. 
• • Hệ sẽ sử dụng lập luận logic để tìm ra các 
câu trả lời cho vấn đề. 
3• Một chương trình Prolog gồm một dãy các luật có 
dạng: A :- B1, ..., Bm 
• trong đó, m ≥ 0, A và Bi (i = 1, ..., m) là các câu phân 
tử. Luật trên được đọc là “A nếu B1 và ... và 
• Bm”. Nó là cách viết trong Prolog của logic mênh đề 
sau: 
• A B B m ⇒ ∧ ∧ 1 
• Trong luật trên, A được gọi là đầu, danh sách các câu 
Bi (B1, ..., Bm) được gọi là thân của luật. 
• Nếu m=0, ký hiệu “:-” sẽ được bỏ đi, khi đó ta có câu 
phân tử A và nó được gọi là một sự kiện. 
4Ví dụ.
• Giả sử chúng ta biết các thông tin sau đây về An và Ba:
• An yêu thích mọi môn thể thao mà cậu chơi. 
• Bóng đá là môn thể thao. 
• Bóng bàn là môn thể thao. 
• An chơi bóng đá. 
• Ba yêu thích mọi thứ mà An yêu thích. 
=> Các câu trên được chuyển thành 1 chương trình Prolog sau :
• likes(an, X) :- sport(X), plays(an, X) 
• sport(football). 
• sport(tennis). 
• plays(an, football). 
• likes(ba, Y) :- likes(an, Y). 
=> Câu hỏi : “An yêu thích cái gì ?”: ? - likes(an, X). 
5
6Tiết 3:
Giáo sinh thực hiện: Đặng Thị Mỹ Bình
SWI ROLOG
CẤU TRÚC DANH SÁCH
7NỘI DUNG
Biễu diễn cấu trúc danh sáchI
Một số vị từ xử lí danh sáchII
Các thao tác cơ bản trên danh sáchIII
4
8- Danh sách là kiểu dữ liệu có cấu trúc được sử dụng rộng 
rãi trong các ngôn ngữ lập trình phi số
- Một danh sách (list) là một dãy các phần tử cùng kiểu
Ví dụ: [ann, tennis, tom, skiing] là một list được viết ở Prolog
I. Biễu diễn cấu trúc danh sách
- Chú ý rằng các list được diễn tả trong Prolog bằng các 
cây nhị phân
9- List rỗng được diễn tả bởi [ ]
- Một list khác rỗng gồm có 
hai thành phần:
 Phần tử đầu tiên 
(head)
 Phần đuôi của list (tail)
ann
tennis
tom
skiing [ ]
.
.
.
.
Head
Tail
- Các phần tử của 1 list có thể là bất kì loại đối tượng nào, kể cả 
1 list.
10
Prolog dùng dấu | (split) để tách biệt phần head và tail của list
• Prolog cung cấp ba cách viết danh sách
– [Item1, Item2, ...]
– [Head | Tail]
– [Item1, Item2, ... | others]
L= [ann, tennis, tom, skiing]
ann
tennis
tom
skiing [ ]
.
.
.
.
L= [ann | [tennis, tom, skiing]]
L= [ann, tennis, tom, skiing | []]
HOẶC:
L= [ann | tennis | [tom, skiing]]
.
11
4 ?- select(3,[3,4,2],L).
L=[4,2]
Yes
Lấy X ra khỏi L để trả về 
phần tử còn lại trong L1. 
4. select(X,L,L1).
3 ?- nextto(b,a,[a,b,c]).
No
Kiểm tra xem Y có đứng 
ngay sau X trong L không.
3. nextto(X,Y,L).
1 ?- member(a,[a,b,c]).
Yes
Kiểm tra xem X có phải là 
một phần tử của danh sách 
L không.
1. member(X,L).
VÍ DỤÝ NGHĨAVỊ TỪ
2 ?- append([a,b,c],[1,2],L).
L = [a, b, c, 1, 2] 
Yes
Ghép danh sách L1 và L2
vào thành L
2. append(L1,L2,L).
II. Một số vị từ xử lí danh sách: có sẵn trong Prolog
- Có thể dùng để chèn thêm 1 
phần tử vào danh sách.
12
4 ?- reverse([a,b,c],L).
L=[c,b,a]
8. reverse(L1,L2).
3 ?- last([a,b,c,d],d).
Yes
Kiểm tra xem X có đứng 
cuối trong L không.
7. last(L,X).
2 ?- nth1(1,[a,b,c],a).
Yes
Kiểm tra xem phần tử thứ 
Index (tính từ 1) của L có 
phải là X không.
6. nth1(Index,L,X).
VÍ DỤÝ NGHĨAVỊ TỪ
1 ?- nth0(1,[a,b,c],a).
No
5. nth0(Index,L,X).
9.Permutation(L1,L2).
Nghịch đảo danh sách L1, 
kết quả trả về L2.
Kiểm tra xem phần tử thứ 
Index (tính từ 0) của L có 
phải là X không.
Danh sách L2 là hoán vị của 
danh sách L1
5 ?- Permutation([a,b ,c], L) .
13
III. Các thao tác cơ bản trên danh sách
1. Kiểm tra một phần tử X có mặt trong danh 
sách L:
Ví dụ:
1 ?- member(a,[a,b,c,d]).
Yes
2 ?- member(d,[a,b,[c,d]]).
No
3 ?- member([c,d],[a,b,[c,d]]).
Yes
a
b
c
d [ ]
.
.
.
.
member (X , L).
=> Phần tử X thuộc danh sách L nếu:
1. X là đầu của L, hoặc nếu
. X là một phần tử của đuôi của L
 Xây dựng lại hai điều kiện trên thành hai mệnh đề:
Sự kiện: member (X, [X | Tail]).
Luật: member (X, [Head | Tail]) :- member(X,Tail).
* Xây dựng lại một số vị từ có sẵn
14
2. Ghép hai danh sách
- Xây dựng lại vị từ này:
Xét hai trường hợp:
1. Nếu L1 = rỗng thì viết như sau: append ([], L, L).
2. Nếu L1 ≠ rỗng thì nó gồm một đầu và một đuôi 
như sau: [X | L1]
Kết quả phép ghép danh sách là: 
append ([X | L1], L2, [X | L3]) :- append (L1, L2, L3).
append (L1, L2, L).
L1 L2X 
L3
- Có thể dùng append để phân tách danh sách đã cho thành 
danh sách mới
Ví dụ: 1 ?- append (L1, L2, [a,b,c]).
L1 = []
L2 = [a, b, c];
L1 = [a]
L2 = [b, c];
L1 = [a, b]; 
-G ép hai danh sách L1 và L2, kết quả trả về L
Ví dụ: 1 ?- append ([a, b], [c, d], L).
L= [a, b, c, d]
Yes
15
3. Nghịch đảo danh sách
- Ví dụ:
1 ?- reverse([a, b, c, d], L).
L = [d, c, b, a] 
Yes
a
b
c
d [ ]
.
.
.
.
reverse (L1, L2).
- Nghịch đảo danh sách L1, kết quả trả 
về danh sách L2.
- Thủ tục nghịch đảo được viết như sau:
Reverse ([], []).
Reverse ([X | Tail], L) :- Reverse (Tail, L1), append (L1, [X], L).
Trong đó: L1 là danh sách nghịch đảo trung gian.
16
4. Hoán vị danh sách
permutation (L1, L2).
- Danh sách L2 là hoán vị của danh sách L1.
- Ví dụ: 1 ?- permutation([a, b, c], L) .
L = [a,b,c] ;
L = [a,c,b] ; 
L = [c,b,a] ;
- Thủ tục hoán vị được viết trong Prolog như sau:
permutation ([], []).
permutation ([X | L], P) :- permutation(L, L1), insert(X, L1, P).
17
H·y nhí!
 Danh sách là một cấu trúc hoặc 
rỗng hoặc gồm hai phần: Head và 
Tail.
 Prolog quản lí danh sách theo cấu 
trúc cây nhị phân và có nhiều cách 
biểu diễn DS
 Các thao tác thường dùng với danh 
sách là: kiểm tra xem một phần tử có 
thuộc DS không, nghịch đảo danh 
sách, hoán vị danh sách,
[Item 1, Item 2, ]
[Head | Tail ]
[Item 1, Item 2, | Others ]
với Tail, Others là các danh sách
18
Bài tập về nhà
Bổ sung một phần tử vào danh sách.1
Loại bỏ một phần tử ra khỏi danh sách.2