Giáo trình Lập trình hàm và lập trình lôgic - Phan Huy Khánh (Phần 2)

LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 122 
CHƯƠNG 3 
NGÔN NGỮ PROLOG 
A line may take us hours, yet if it does not seem a moment's thought 
All our stitching and unstitching has been as nought. 
Yeats - Adam's Curse 
I. Giới thiệu ngôn ngữ Prolog 
I.1. Prolog là ngôn ngữ lập trình lôgich 
Prolog là ngôn ngữ được sử dụng phổ biến nhất trong dòng các ngôn ngữ lập trình lôgich 
(Prolog có nghĩa là PROgramming in LOGic). Ngôn ngữ Prolog do giáo sư người Pháp Alain 
Colmerauer và nhóm nghiên cứu của ông đề xuất lần đầu tiên tại trường Đại học Marseille đầu 
những năm 1970. Đến năm 1980, Prolog nhanh chóng được áp dụng rộng rãi ở châu Âu, được 
người Nhật chọn làm ngôn ngữ phát triển dòng máy tính thế hệ 5. Prolog đã được cài đặt trên 
các máy vi tính Apple II, IBM-PC, Macintosh. 
Prolog còn được gọi là ngôn ngữ lập trình ký hiệu (symbolic programming) tương tự các 
ngôn ngữ lập trình hàm (functional programming), hay lập trình phi số (non-numerical 
programming). Prolog rất thích hợp để giải quyết các bài toán liên quan đến các đối tượng 
(object) và mối quan hệ (relation) giữa chúng. 
Prolog được sử dụng phổ biến trong lĩnh vực trí tuệ nhân tạo. Nguyên lý lập trình lôgich 
dựa trên các mệnh đề Horn (Horn logíc). Một mệnh đề Horn biễu diễn một sự kiện hay một sự 
việc nào đó là đúng hoặc không đúng, xảy ra hoặc không xảy ra (có hoặc không có, v.v...). 
Ví dụ I.1 : Sau đây là một số mệnh đề Horn : 
Nếu một người già mà (và) khôn ngoan thì người đó hạnh phúc. 
Jim là người hạnh phúc. 
Nếu X là cha mẹ của Y và Y là cha mẹ của Z thì X là ông của Z. 
Tom là ông của Sue. 
Tất cả mọi người đều chết (hoặc Nếu ai là người thì ai đó phải chết). 
Socrat là người. 
Trong các mệnh đề Horn ở trên, các mệnh đề 1, 3, 5 được gọi là các luật (rule), các mệnh 
đề còn lại được gọi là các sự kiện (fact). Một chương trình lôgich có thể được xem như là một 
cơ sở dữ liệu gồm các mệnh đề Horn, hoặc dạng luật, hoặc dạng sự kiện, chẳng hạn như tất cả 
các sự kiện và luật từ 1 đến 6 ở trên. Người sử dụng (NSD) gọi chạy một chương trình lôgich 
bằng cách đặt câu hỏi (query/ question) truy vấn trên cơ sở dữ liệu này, chẳng hạn câu hỏi : 
Socrat có chết không ? 
(tương đương khẳng định Socrat chết đúng hay sai ?) 
Một hệ thống lôgich sẽ thực hiện chương trình theo cách «suy luận»-tìm kiếm dựa trên vốn 
«hiểu biết» đã có là chương trình - cơ sở dữ liệu, để minh chứng câu hỏi là một khẳng định, là 
đúng (Yes) hoặc sai (No). Với câu hỏi trên, hệ thống tìm kiếm trong cơ sở dữ liệu khẳng định 
Socrat chết và «tìm thấy» luật 5 thoả mãn (vế thì). 
Vận dụng luật 5, hệ thống nhận được Socrat là người (vế nếu) chính là sự kiện 5. 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 123 
Từ đó, câu trả lời sẽ là : 
Yes 
có nghĩa sự kiện Socrat chết là đúng. 
I.1.1. Cú pháp Prolog 
I.1.2. Các thuật ngữ 
Một chương trình Prolog là một cơ sở dữ liệu gồm các mệnh đề (clause). Mỗi mệnh đề 
được xây dựng từ các vị từ (predicat). Một vị từ là một phát biểu nào đó về các đối tượng có 
giá trị chân đúng (true) hoặc sai (fail). Một vị từ có thể có các đối là các nguyên lôgich (logic 
atom). 
Mỗi nguyên tử (nói gọn) biểu diễn một quan hệ giữa các hạng (term). Như vậy, hạng và 
quan hệ giữa các hạng tạo thành mệnh đề. 
Hạng được xem là những đối tượng “dữ liệu” trong một trình Prolog. Hạng có thể là hạng 
sơ cấp (elementary term) gồm hằng (constant), biến (variable) và các hạng phức hợp 
(compound term). 
Các hạng phức hợp biểu diễn các đối tượng phức tạp của bài toán cần giải quyết thuộc lĩnh 
vực đang xét. Hạng phức hợp là một hàm tử (functor) có chứa các đối (argument), có dạng 
Tên_hàm_tử(Đối_1, ..., Đối_n) 
Tên hàm tử là một chuỗi chữ cái và/hoặc chũ số được bắt đầu bởi một chữ cái thường. Các 
đối có thể là biến, hạng sơ cấp, hoặc hạng phức hợp. Trong Prolog, hàm tử đặc biệt “.” (dấu 
chấm) biểu diễn cấu trúc danh sách (list). Kiểu dữ liệu hàm tử tương tự kiểu bản ghi (record) 
và danh sách (list) tương tự kiểu mảng (array) trong các ngôn ngữ lập trình mệnh lệnh (C, 
Pascal...). 
Ví dụ I.2 : 
f(5, a, b). 
student(robert, 1975, info, 2, 
address(6, 'mal juin', 'Caen')). 
[a, b, c] 
Mệnh đề có thể là một sự kiện, một luật (hay quy tắc), hay một câu hỏi. 
Prolog quy ước viết sau mỗi mệnh đề một dấu chấm để kết thúc như sau : 
• Sự kiện : . 
(tương ứng với luật :- true. ) 
• Luật : :- . 
• Câu hỏi ?- . 
(ở chế độ tương tác có dấu nhắc lệnh) 
I.1.3. Các kiểu dữ liệu Prolog 
Hình 1.1. biểu diễn một sự phân lớp các kiểu dữ liệu trong Prolog gồm kiểu dữ liệu sơ cấp 
và kiểu dữ liệu có cấu trúc. Sự phân lớp này nhận biết kiểu của một đối tượng nhờ bề ngoài cú 
pháp. 
Cú pháp của Prolog quy định mỗi kiểu đối tượng có một dạng khác nhau. Prolog không cần 
cung cấp một thông tin nào khác để nhận biết kiểu của một đối tượng. Trong Prolog, NSD 
không cần khai báo kiểu dữ liệu. 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 124 
Hình I.1. Các kiểu dữ liệu trong Prolog 
Các kiểu dữ liệu Prolog được xây dựng từ các ký tự ASCII : 
• Các chữ cái in hoa A, B, ..., Z và chữ cái in thường a, b, ..., z. 
• Các chữ số 0, 1, ..., 9. 
• Các ký tự đặc biệt, chẳng hạn + - * / = : . & _ ~. 
I.1.4. Chú thích 
Trong một chương trình Prolog, chú thích (comment) được đặt giữa hai cặp ký hiệu /* và 
*/ (tương tự ngôn ngữ C). Ví dụ : 
/*************************/ 
/*** Đây là một chú thích ***/ 
/*************************/ 
Trong trường hợp muốn đặt một chú thích ngắn sau mỗi phần khai báo Prolog cho đến hết 
dòng, có thể đặt trước một ký hiệu %. 
Ví dụ : 
%%%%%%%%%%%%%%%%%%%%% 
% Đây cũng là một chú thích 
%%%%%%%%%%%%%%%%%%%%% 
Prolog sẽ bỏ qua tất cả các phần chú thích trong thủ tục. 
I.2. Các kiểu dữ liệu sơ cấp của Prolog 
I.2.1. Kiểu hằng số 
Prolog sử dụng cả số nguyên và số thực. Cú pháp của các số nguyên và số thực rất đơn 
giản, chẳng hạn như các ví dụ sau : 
1 1515 0 -97 
3.14 -0.0035 100.2 
Tuỳ theo phiên bản cài đặt, Prolog có thể xử lý các miền số nguyên và miền số thực khác 
nhau. Ví dụ trong phiên bản Turbo Prolog, miền số nguyên cho phép từ -32768 đến 32767, 
miền số thực cho phép từ ±1e-307 đến ±1e+308. Các số thực rất khi được sử dụng trong 
Prolog. Lý do chủ yếu ở chỗ Prolog là ngôn ngữ lập trình ký hiệu, phi số. 
Các số nguyên thường chỉ được sử dụng khi cần đếm số lượng các phần tử hiện diện trong 
một danh sách Prolog dạng [a1, a2, ..., an ]. 
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ử 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 125 
I.2.2. Kiểu hằng lôgich 
Prolog sử dụng hai hằng lôgich có giá trị là true và fail. Thông thường các hằng lôgich 
không được dùng như tham số mà được dùng như các mệnh đề. Hằng fail thường được dùng 
để tạo sinh lời giải bài toán. 
I.2.3. Kiểu hằng chuỗi ký tự 
Các hằng là chuỗi (string) các ký tự được đặt giữa hai dấu nháy kép. 
"Toto \#\{@ tata" chuỗi có tuỳ ý ký tự 
"" chuỗi rỗng (empty string) 
"\"" chuỗi chỉ có một dấu nháy kép. 
I.2.4. Kiểu hằng nguyên tử 
Các hằng nguyên tử Prolog là chuỗi ký tự ở một trong ba dạng như sau : 
(1) Chuỗi gồm chữ cái, chữ số và ký tự _ luôn luôn được bắt đầu bằng một chữ cái 
in thường. 
newyork a_ 
nil x__y 
x25 tom_cruise 
(2) Chuỗi các ký tự đặc biệt : 
 .:. 
======> ::== 
... 
(3) chuỗi đặt giữa hai dấu nháy đơn (quote) được bắt đầu bằng chữ in hoa, dùng phân biệt 
với các tên biến : 
’Jerry’ ’Tom SMITH’ 
I.2.5. Biến 
Tên biến là một chuỗi ký tự gồm chữ cái, chữ số, bắt đầu bởi chữ hoa hoặc dấu gạch dưới 
dòng : 
X, Y, A 
Result, List_of_members 
_x23, _X, _, ... 
II. Sự kiện và luật trong Prolog 
II.1. Xây dựng sự kiện 
Ví dụ II.1 : Quan hệ gia đình 
Để xây dựng các sự kiện trong một chương trình Prolog, ta lấy một ví dụ về. Ta xây dựng 
một cây gia hệ như Hình II.1. 
Trong cây gia hệ (a), các nút chỉ người, còn các mũi tên chỉ quan hệ cha mẹ của (parent 
of). Sự kiện Tom là cha mẹ của Bill được viết thành một vị từ Prolog như sau (chú ý mệnh đề 
được kết thúc bởi một dấu chấm) : 
parent(tom, bill). % Chú ý không có dấu cách trước dấu mở ngoặc 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 126 
Ở đây, vị từ parent có hai đối là tom và bill. Người ta có thể biểu diễn vị từ này bởi 
một cây như trong Hình II.1 (b) : nút gốc là tên của vị từ, còn các nút lá là các đối. 
(a) (b) 
Hình II.1.Cây gia hệ. 
Từ cây gia hệ trên đây, có thể tiếp tục viết các vị từ khác để nhận được một chương trình 
Prolog gồm 6 vị từ như sau : 
parent(mary, bill). 
parent(tom, bill). 
parent(tom, liz). 
parent(bill, ann). 
parent(bill, sue). 
parent(sue, jim). 
Sau khi hệ thống Prolog nhận được chương trình này, thực chất là một cơ sở dữ liệu, người 
ta có thể đặt ra các câu hỏi liên quan đến quan hệ parent. Ví dụ câu hỏi Bill có phải là cha 
mẹ của Sue được gõ vào trong hệ thống đối thoại Prolog (dấu nhắc ?-_) như sau : 
?- parent(bill, sue). 
Sau khi tìm thấy sự kiện này trong chương trình, Prolog trả lời : 
Yes 
Ta tiếp tục đặt câu hỏi khác : 
?- parent(liz, sue). 
No 
Bởi vì Prolog không tìm thấy sự kiện Liz là người mẹ của Sue trong chương trình. Tương 
tự, Prolog trả lời No cho sự kiện : 
?- parent(tom, ben). 
Vì tên ben chưa được đưa vào trong chương trình. Ta có thể tiếp tục đặt ra các câu hỏi thú 
vị khác. Chẳng hạn, ai là cha (hay mẹ) của Liz ? 
?- parent(X, liz). 
Lần này, Prolog không trả lời Yes hoặc No, mà đưa ra một giá trị của X làm thoả mãn câu 
hỏi trên đây : 
X = tom 
Để biết được ai là con của Bill, ta chỉ cần viết : 
?- parent(bill, X). 
Với câu hỏi này, Prolog sẽ có hai câu trả lời, đầu tiên là : 
X = ann ->; 
mar tom 
bil
l
liz
ann sue 
jim
parent 
tom bill 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 127 
Để biết được câu trả lời tiếp theo, trong hầu hết các cài đặt của Prolog, NSD phải gõ vào 
một dấu chấm phẩy (;) sau -> (Arity Prolog) : 
X = sue 
Nếu đã hết phương án trả lời mà vẫn tiếp tục yêu cầu (;), Prolog trả lời No. 
NSD có thể đặt các câu hỏi tổng quát hơn, chẳng hạn : ai là cha mẹ của ai ? Nói cách khác, 
cần tìm X và Y sao cho X là cha mẹ của Y. Ta viết như sau : 
?- parent(X, Y). 
Sau khi hiển thị câu trả lời đầu tiên, Prolog sẽ lần lượt tìm kiếm những cặp cha mẹ − con 
thoả mãn và lần lượt hiển thị kết quả nếu chừng nào NSD còn yêu cầu cho đến khi không còn 
kết quả lời giải nào nữa (kết thúc bởi Yes) : 
X = mary 
Y = bill ->; 
X = tom 
Y = bill ->; 
X = tom 
Y = liz ->; 
X = bill 
Y = ann ->; 
X = bill 
Y = sue ->; 
X = sue 
Y = jim 
Yes 
Tuỳ theo cài đặt Prolog, NSD có thể gõ vào một dấu chấm (.) hoặc Enter để chấm dứt giữa 
chừng luồng trả lời. 
Ta có thể tiếp tục đưa ra những câu hỏi phức tạp hơn khác, chẳng hạn ai là ông (bà) của 
Jim ? Thực tế, quan hệ ông − bà (grandparent) chưa được định nghĩa, cần phải phân tách 
câu hỏi này thành hai phần sơ cấp hơn : 
1. Ai là cha (mẹ) của Jim ? Giả sử có tên là Y. 
2. Ai là cha (mẹ) của Y ? Giả sử có tên là X. 
Hình II.2. Quan hệ ông bà được hợp thành từ hai quan hệ cha mẹ. 
Lúc này, có thể viết trong Prolog như sau : 
?- parent(Y, jim), parent(X, Y). 
Prolog trả lời : 
Y = sue 
X = bill 
Yes 
Câu hỏi trên đây tương ứng với câu hỏi : tìm X và Y thoả mãn : 
Y 
X 
jim 
parent 
grandparent 
parent 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 128 
parent(Y, jim) 
và 
parent(X, Y). 
Nếu thay đổi thứ tự hai thành phần câu hỏi, thì nghĩa lôgich vẫn không thay đổi và Prolog 
trả lời cùng kết quả (có thể thay đổi về thứ tự), nghĩa là ta có thể đặt câu hỏi như sau : 
?- parent(X, Y), parent(Y, jim). 
X = bill 
Y = đường dẫn 
Yes 
Bây giờ ta đặt câu hỏi ai là cháu của Tom ? 
?- parent(tom, X), parent(X, Y). 
X = bill 
Y = ann->; 
X = bill 
Y = sue ->; 
No 
Một câu hỏi khác có thể như sau : Ann và Sue có cùng người ông không ? nghĩa là ta diễn 
đạt thành hai giai đoạn : 
1. Tìm X là cha mẹ của Ann. 
2. X tìm thấy có cùng là cha mẹ của Sue không ? 
Câu hỏi và trả lời trong Prolog như sau : 
?- parent(X, ann), parent(X, sue). 
X = bill 
Trong Prolog, câu hỏi còn được gọi là đích (goal) cần phải được thoả mãn (satisfy). Mỗi 
câu hỏi đặt ra đối với cơ sở dữ liệu có thể tương ứng với một hoặc nhiều đích. Chẳng hạn dãy 
các đích : 
parent(X, ann), parent(X, sue). 
tương ứng với câu hỏi là phép hội (conjunction) của 2 mệnh đề : 
X là một cha mẹ của Ann, và 
X là một cha mẹ của Sue. 
Nếu câu trả lời là Yes, thì có nghĩa đích đã được thoả mãn, hay đã thành công. Trong 
trường hợp ngược lại, câu trả lời là No, có nghĩa đích không được thoả mãn, hay đã thất bại. 
Nếu có nhiều câu trả lời cho một câu hỏi, Prolog sẽ đưa ra câu trả lời đầu tiên và chờ yêu 
cầu của NSD tiếp tục. 
II.2. Xây dựng luật 
II.2.1. Định nghĩa luật 
Từ chương trình gia hệ trên đây, ta có thể dễ dàng bổ sung các thông tin khác, chẳng hạn 
bổ sung các sự kiện về giới tính (nam, nữ) của những người đã nêu tên trong quan hệ parent 
như sau : 
woman(mary). 
man(tom). 
man(bill). 
woman(liz). 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 129 
woman(sue). 
woman(ann). 
man(jim). 
Ta đã định nghĩa các quan hệ đơn (unary) woman và man vì chúng chỉ liên quan đến một 
đối tượng duy nhất. Còn quan hệ parent là nhị phân, vì liên quan đến một cặp đối tượng. 
Như vậy, các quan hệ đơn dùng để thiết lập một thuộc tính của một đối tượng. Mệnh đề : 
woman(mary). 
được giải thích : Mary là nữ. Tuy nhiên, ta cũng có thể sử dụng quan hệ nhị phân để định nghĩa 
giới tính : 
sex(mary, female). 
sex(tom, male). 
sex(bill, male). 
. . . 
Bây giờ ta đưa vào một quan hệ mới child, đối ngược với parent như sau : 
child(liz, tom). 
Từ đó, ta định nghĩa luật mới như sau : 
child(Y, X) :- parent(X, Y). 
Luật trên được hiểu là : 
Với mọi X và Y, 
Y là con của X nếu 
X là cha (hay mẹ) của Y. 
hay 
Với mọi X và Y, 
nếu X là cha (hay mẹ) của Y thì 
 Y là con của X. 
Có sự khác nhau cơ bản giữa sự kiện và luật. Một sự kiện, chẳng hạn : 
parent(tom, liz). 
là một điều gì đó luôn đúng, không có điều kiện gì ràng buộc. Trong khi đó, các luật liên quan 
đến các thuộc tính chỉ được thoả mãn nếu một số điều kiện nào đó được thoả mãn. Mỗi luật 
bao gồm hai phần: 
• phần bên phải (RHS: Right Hand Side) chỉ điều kiện, còn được gọi là thân (body) của 
luật, và 
• phần bên trái (LH: Left Hand Side S) chỉ kết luận, còn được gọi là đầu (head) của luật. 
Nếu điều kiện parent(X, Y) là đúng, thì child(Y, X) cũng đúng và là hậu quả 
lôgich của phép suy luận (inference). 
Câu hỏi sau đây giải thích cách Prolog sử dụng các luật : Liz có phải là con của Tom không 
? 
?- child(liz, tom) 
child(Y, X) :- parent(X, Y). 
đầu thân 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 130 
Thực tế, trong chương trình không có sự kiện nào liên quan đến con, mà ta phải tìm cách 
áp dụng các luật. Luật trên đây ở dạng tổng quát với các đối tượng X và Y bất kỳ, mà ta lại cần 
các đối tượng cụ thể liz và tom. 
Ta cần sử dụng phép thế (substitution) bằng cách gán giá trị liz cho biến Y và tom cho 
X. Người ta nói rằng các biến X và Y đã được ràng buộc (bound) : 
X = tom 
và 
Y = liz 
Lúc này, phần điều kiện có giá trị parent(tom, liz) và trở thành đích con (sub-goal) 
để Prolog thay ...  tạo thành từ danh sách có dạng : 
[ head | queue ] 
và có độ dài bằng 1 cộng với độ dài của queue. 
Ta có chương trình Prolog như sau : 
length( [ ], 0 ). 
length( [ _ | Queue ], N ) :- 
length(Queue, N1 ), 
N is 1 + N1. 
Kết quả chạy Prolog như sau : 
?- length( [ a, b, c, d, e ], N ). 
N = 5 
Yes 
?- length( [ a, [ b, c ], d, e ], N ). 
N = 4 
Yes 
Ta thấy rằng trong mệnh đề thứ hai, hai đích của phần thân là không thể hoán đổi cho nhau, 
vì rằng N1 phải được ràng buộc trước khi thực hiện đích : 
N is 1 + N1 
Chẳng hạn, nếu gọi trace, quá trình thực hiện length( [ 1, 2, 3 ], N ) như 
sau : 
(0) gọi length([1, 2, 3], N) -> 
(1) gọi length([2, 3], N’) -> 
(2) gọi length([3], N’’) -> 
(3) gọi length([ ], N’’’) -> N’’’ = 0 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 194 
(4) gọi N’’ is 1 + 0 -> N’’ = 1 
(5) gọi N’ is 1 + 1 -> N’ = 2 
(6) gọi N is 1 + 2 -> N = 3 
Với is, ta đã đưa vào một quan hệ nhạy cảm với thứ tự thực hiện các đích, và do vậy 
không thể bỏ qua yếu tố thủ tục trong chương trình. 
Điều gì sẽ xảy ra nếu ta không sử dụng is trong chương trình. Chẳng hạn : 
length1( [ ], 0 ). 
length1( [ _ | Queue ], N ) :- 
length1( Queue, N1 ), 
N = 1 + N1. 
Lúc này, nếu gọi : 
?- length1( [ a, [ b, c ], d, e ], N ). 
Prolog trả lời : 
N = 1 + (1 + (1 + (1 + 0))) 
Yes 
Phép cộng do không được khởi động một cách tường minh nên sẽ không bao giờ được thực 
hiện. Tuy nhiên, ta có thể hoán đổi hai đích của mệnh đề thứ hai trong length1 : 
length1( [ ], 0 ). 
length1( [ _ | Queue ], N ) :- 
N = 1 + N1, 
length1( Queue, N1 ). 
Kết quả chạy chương trình sau khi hoán đổi vẫn y hệt như cũ. Bây giờ, ta lại có thể rút gọn 
mệnh đề về chỉ còn một đích : 
length1( [ ], 0 ). 
length2( [ _ | Queue ], 1 + N ) :- 
length2( Queue, N ). 
Kết quả chạy chương trình lần này vẫn y hệt như cũ. Prolog không đưa ra trả lời như mong 
muốn, mà là : 
?- length1([ a, b, c, d], N). 
N = 1+ (1+ (1+ (1+0))) 
Yes 
X.2.3. Tạo sinh các số tự nhiên 
Chương trình sau đây tạo sinh và liệt kê các số tự nhiên : 
% Natural Numbers 
nat(0). 
nat(N) :- nat(M), N is M + 1. 
Khi thực hiện các đích con trong câu hỏi : 
?- nat(N), write(N), nl, fail. 
các số tự nhiên được tạo sinh liên tiếp nhờ kỹ thuật quay lui. Sau khi số tự nhiên đầu tiên 
nat(N) được in ra nhờ write(N), hằng fail bắt buộc thực hiện quay lui. Khi đó, luật thứ 
hai được vận dụng để tạo sinh số tự nhiên tiếp theo và cứ thế tiếp tục cho đến khi NSD quyết 
định dừng chương trình (^C). 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 195 
Bài tập chương 3 
1. Tìm các đối tượng Prolog đúng đắn về mặt cú pháp trong số đối tượng được cho dưới đây. 
Cho biết kiểu của chúng (là nguyên tử, số, biến hay cấu trúc) ? 
a) Diane 
b) diane 
c) ‘Diane’ 
d) _diane 
e) ‘Diane va en vacances’ 
f) va( diane, vacances ) 
g) 45 
h) 5(X , Y) 
i) +( nord , owest ) 
j) three( small( cats ) ) 
2. Hãy tìm một biểu diễn dạng đối tượng cấu trúc cho các hình chữ nhật, hình vuông và hình 
tròn. Xem hình 2.4 để có cách giải quyết. Sử dụng các biễu diễn cho các hình cụ thể để 
minh họa. 
3. Chương trình sau nói rằng hai người là có quan hệ dòng họ với nhau nếu : 
a) một là tổ tiên của người kia, hoặc, 
b) hai người có chung tổ tiên, hoặc, 
c) hai người có cùng con cháu. 
kindred( X, Y) :- 
ancestor(X , Y). 
kindred(X , Y) :- 
ancestor(X , Y). 
kindred(X , Y) :- % X và Y có cùng tổ tiên 
ancestor( Z, X), 
ancestor(Z , Y). 
kindred(X , Y) :- % X và Y có cùng con cháu 
ancestor (X , Z), 
ancestor(Y , Z). 
Hãy cho biết có thể làm ngắn chương trình trên bằng cách sử dụng dấu chấm phẩy ; 
được không ? 
4. Hãy tìm hiểu một định nghĩa mới về quan hệ ancestor : 
ancestor(X Z) :- 
parent(X Z) . 
ancestor(X Z) :- 
parent(Y , Z), 
ancestor( X, Y). 
Định nghĩa này có đúng hay không ? Có thể thay đổi lại sơ đồ đã cho trong hình 1.7 để 
tương ứng với định nghĩa mới này ? 
5. Ngoài các định nghĩa quan hệ gia đình đã có trong phần lý thuyết và bài tập, hãy định nghĩa 
các quan hệ khác theo tập quán Việt Nam (cô, dì, chú, bác...) ? 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 196 
6. Hãy định nghĩa các quan hệ trong thế giới sinh vật (động vật, thực vật) ? 
7. Cho biết các hạng Prolog hợp thức sau đây (valid Prolog terms) : 
23 +(fred, jim) 
foo(X, bar(+(3, 4))) 1+2. 
Foo(x) Alison Cawsey 
8. Cho quan hệ parent được định nghĩa trong phần lý thuyết cho biết kết quả của các câu 
hỏi sau : 
a) ?- parent(jim , X). 
b) ?- parent( X , jim). 
c) ?- parent(mary , X) , parent( X , part). 
d) ?- parent(mary , X) , parent( X , y ) , parent(y , jim). 
9. Viết các mệnh đề Prolog diễn tả các câu hỏi liên quan đến quan hệ parent : 
a) Ai là cha mẹ của Sue ? 
b) Liz có con không ? 
c) Ai là ông bà (grandparent) của Sue ? 
10. Viết trong Prolog các mệnh đề sau : 
a) Ai có một đứa trẻ người đó là hạnh phúc. 
Hướng dẫn : Xây dựng quan hệ một ngôi happy. 
b) Với mọi X, nếu X có một con mà người con này có một chị em gái, thì X có hai con 
(xây dựng quan hệ have_two_children). 
11. Định nghĩa quan hệ grandchild bằng cách sử dụng quan hệ parent. 
Hướng dẫn : tìm hiểu quan hệ grandparent. 
12. Định nghĩa quan hệ aunt( X, Y ) bằng cách sử dụng quan hệ parent. 
Để thuận tiện, có thể vẽ sơ đồ minh họa. 
13. Các phép so khớp dưới đây có đúng không ? Nếu đúng, cho biết các ràng buộc biến tương 
ứng ? 
a) point( A , B ) = point( 1 , 2 ) 
b) point( A , B ) = point( X , Y, Z ) 
c) addition( 2 , 2 ) = 4 
d) +( 2 , D ) = +( E , 2 ) 
e) triangle( point( -1 , 0 ) , P2, P3 ) = triangle( P1, 
point( 1, 0 ), point( 0, Y ) ) 
Các ràng buộc ở đây đã định nghĩa một lớp các tam giác. Làm cách nào để mô tả 
lớp này ? 
14. Sử dụng mô tả các đường thẳng đã cho trong bài học, tìm một hạng biễu diễn mọi đường 
thẳng đứng X = 5. 
15. Cho hình chữ nhật được biễu diễn bởi hạng: rectangle(P1, P2, P3, P4). 
Với Pi là các đỉnh của hình chữ nhật theo chiều dương, hãy định nghĩa quan hệ : 
regular( R ) 
là đúng nếu R là một hình chữ nhật có các cạnh thẳng đứng và nằm ngang (song song với 
các trục tọa độ). 
16. Cho biết kết quả của các câu hỏi sau đây : 
?- X=Y. 
?- X is Y 
?- X=Y, Y=Z, Z=1. 
?- X=1, Z=Y, X=Y. 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 197 
?- X is 1+1, Y is X. 
?- Y is X, X is 1+1. 
?- 1+2 == 1+2. 
?- X == Y. 
?- X == X. 
?- 1 =:= 2-1 
?- X =:= Y. 
17. Cho biết kết quả của các câu hỏi sau đây : 
?- op(X) is op(1). 
?- op(X) = op(1). 
?- op(op(Z), Y) = op(X, op(1)). 
?- op(X, Y) = op(op(Y), op(X)). 
18. Từ các định nghĩa số tự nhiên (nat) và phép cộng (addi) cho trong ví dụ 1 ở mục định 
nghĩa hàm, hãy viết tiếp các hàm trừ (subt), nhân (multi), chia (divi), luỹ thừa 
(power), giai thừa (fact), so sánh nhỏ hơn (less) và tìm ước số chung lớn nhất (pdg) 
sử dụng các hàm đã có (chẳng hạn less, subt...). 
19. Viết hàm Prolog để kiểm tra một số nguyên tuỳ ý N : 
a. N là số chẵn (even number) sử dụng đệ quy trực tiếp 
 Hướng dẫn : N chẵn thì N±2 cũng là số chẵn 
b. N là số lẻ (odd number) sử dụng đệ quy trực tiếp 
 Hướng dẫn : N lẻ thì N±2 cũng là số lẻ 
c. N chẵn sử dụng hàm kiểm tra số lẻ câu d (N chẵn thì N±1 là số lẻ) 
d. N là số lẻ sử dụng hàm kiểm tra số chẵn câu c (N lẻ thì N±1 chẵn). 
20. Viết hàm Prolog để làm duyệt (tracking/traverse) trên cây nhị phân theo các thứ tự trước 
(reorder), sau (post-order) và giữa (in-order). 
Giả sử cây nhị phân tương ứng với biểu thức số học (5+6)*(3-(2/2)) là các mệnh đề 
Prolog như sau : 
tree(’*’, tree(’+’, leaf(5), leaf(6)), tree(’-’, leaf(3), 
tree(’/’, leaf(2), leaf(2))) 
Kết quả duyệt cây như sau : theo thứ tự trước : 
[*, +, 5, 6, -, 3, /, 2, 2] 
thứ tự giữa : 
[5, +, 6, *, 3, -, 2, /, 2] 
thứ tự sau : 
[5, 6, +, 3, 2, 2, /, -, *] 
21. Viết lại hàm tạo 10 số tự nhiên chẵn đầu tiên (đã cho trong phần đệ quy) sao cho kết quả 
trả về là dãy số tăng dần. 
22. Lập bảng nhân table(R, N) có số bị nhân (multiplicator) từ 1 trở đi với số nhân N 
(multiplier) và dừng lại khi gặp số bị nhân R (kết quả R * N). 
23. Viết các hàm tính gần đúng giá trị các hàm sau với độ chính xác e = 10-5 : 
π
4
1 1
3
1
5
1
7
= − + − +... cho đến khi 1
2n -1
ε< 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 198 
2 4 6x 2 x 2 4 x1 + + + + ...
2 3 4 3 5 6
× × × cho đến khi phần tử thứ n < e 
S = 1 - x + x
2!
 - x
3!
 + ... + (-1) x
n!
 + ... 
2 3
n
n
 cho đến khi 
nx
n!
ε<
S x x x x
n
n
= + + + + + +1
2 4 6 2
2 4 6 2
! ! !
...
( )!
... cho đến khi x
n
n2
5
2
10
( )!
< − 
y = x + x + ... + x có n > 1 dấu căn 
24. Trình Prolog dưới đây là một trình diễn dịch (interpreter) cho một ngôn ngữ lập trình đơn 
giản chỉ gồm các số nguyên int(N), các biến id(X), các hàm fn(X,E), và gọi hàm 
app(E1,E2) : 
%% subst(E1, E2, X, V) 
%% thực hiện phép thế biến X bởi biến V trong E1 để trả về E2. 
subst(int(N), int(N), _, _). 
subst(id(X), V, X, V). 
subst(id(Y), id(Y), X, _) :- 
X \= Y. 
subst(fn(X, E), fn(X, E), X, _). 
subst(fn(Y, Ea), fn(Y, Eb), X, V) :- 
X \= Y, 
subst(Ea, Eb, X, V). 
subst(app(E1a, E2a), app(E1b, E2b), X, V) :- 
subst(E1a, E1b, X, V), 
subst(E2a, E2b, X, V). 
%% reduce(E, V) 
%% thực hiện phép tính giá trị của E để trả về V. 
reduce(int(N), int(N)). 
reduce(fn(X, B), fn(X, B)) 
reduce(app(E1, E2), V) :- 
reduce(E1, fn(X, B)), 
reduce(E2, V2), 
subst(B, E, X, V2), 
reduce(E, V). 
Câu hỏi : 
a. Cho biết cách trao đổi tham biến hợp lệ trong ngôn ngữ mô tả trên đây ? Cách trao 
đổi tham biến nào thì không thể thực hiện được ? 
b. Tìm cách thay đổi trình Prolog trên đây để có thể thực hiện được các 
phương pháp trao đổi tham biến khác nhau. 
c. Cho biết tầm vực (scope) của các biến là tĩnh hay động ? 
25. Cho ví dụ một đồ thị không định hướng dưới đây : 
arc(a,b). arc(d,f). 
arc(b,c). arc(f,a). 
arc(c,d). arc(a,b). 
arc(c,e). arc(h,i). 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 199 
arc(c,g). arc(i,j). 
arc(g,f). 
Hãy viết hàm tìm đường đi giữa hai đỉnh của đồ thị. 
26. Viết một thủ tục sử dụng append để xóa ba phần tử cuối cùng của danh sách L, tạo ra 
danh sách L1. Hướng dẫn : L là phép ghép của L1 với một danh sách của ba phần tử (đã bị 
xóa khỏi L). 
27. Viết một dãy các đích để xóa ba phần tử đầu tiên và ba phần tử cuối cùng của một danh 
sách L, để trả về danh sách L2. 
28. Định nghĩa quan hệ : 
last_element( Object, List ) 
sao cho Object phải là phần tử cuối cùng của danh sách List. Hãy viết thành hai mệnh 
đề, trong đó có một mệnh đề sử dụng append, mệnh đề kia không sử dụng append. 
29. Định nghĩa hai vị từ : 
even_length( List ) và odd_length( List ) 
được thõa mãn khi số các phân tử của danh sách List là chẵn hay lẻ tương ứng. Ví dụ 
danh sách : 
[ a, b, c, d ] có độ dài chẵn, 
[ a, b, c ] có độ dài lẽ. 
30. Cho biết kết quả Prolog trả lời các câu hỏi sau : 
?- [1,2,3] = [1|X]. 
?- [1,2,3] = [1,2|X]. 
?- [1 | [2,3]] = [1,2,X]. 
?- [1 | [2,3,4]] = [1,2,X]. 
?- [1 | [2,3,4]] = [1,2|X]. 
?- b(o,n,j,o,u,r) =.. L. 
?- bon(Y) =.. [X,jour]. 
?- X(Y) =.. [bon,jour]. 
31. Viết chương trình Prolog kiểm tra một danh sách có phải là một tập hợp con của một danh 
sách khác không ? Chương trình hoạt động như sau : 
?- subset2([4,3],[2,3,5,4]). 
Yes 
32. Viết chương trình Prolog để lấy ra các phần tử từ một danh sách. Chương trình cũng có thể 
chèn các phần tử vào một danh sách hoạt động như sau : 
?- takeout(3,[1,2,3],[1,2]). 
Yes 
?- takeout(X,[1,2,3],L). 
X = 1 
L = [2, 3] ; 
X = 2 
L = [1, 3] ; 
X = 3 
L = [1, 2] ; 
No 
?- takeout(4,L,[1,2,3]). 
4 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 200 
L = [4, 1, 2, 3] ; 
L = [1, 4, 2, 3] ; 
L = [1, 2, 4, 3] ; 
L = [1, 2, 3, 4] ; 
No 
33. Viết vị từ Prolog getEltFromList(L,N,E) cho phép lấy ra phần tử thứ N trong một 
danh sách. Thất bại nếu danh sách không có đủ N phần tử. Chương trình hoạt động như 
sau : 
?- getEltFromList([a,b,c],0,X). 
No 
?- getEltFromList([a,b,c],2,X). 
X = b 
?- getEltFromList([a,b,c],4,X). 
No 
34. Viết chương trình Prolog tìm phần tử lớn nhất và phần tử nhỏ nhất trong một danh sách các 
số. Chương trình hoạt động như sau : 
?- maxmin([3,1,5,2,7,3],Max,Min). 
Max = 7 
Min = 1 
Yes 
?- maxmin([2],Max,Min). 
Max = 2 
Min = 2 
Yes 
35. Viết chương trình Prolog chuyển một danh sách phức hợp, là danh sách mà mỗi phần tử có 
thể là một danh sách con chứa các danh sách con phức hợp khác, thành một danh sách 
phẳng là danh sách chỉ chứa các phần tử trong tất cả các danh sách con có thể, giữ nguyên 
thứ tự lúc đầu. Chương trình hoạt động như sau : 
flatten([[1,2,3],[4,5,6]], Flatlist). 
Flatlist = [1,2,3,4,5,6] 
Yes 
flatten([[1,[hallo,[[aloha]]],2,[],3],[4,[],5,6]], Flatlist) 
Flatlist = [1, hallo, aloha, 2, 3, 4, 5, 6] 
Yes 
36. Sử dụng vị từ forall để viết chương trình Prolog kiểm tra hai danh sách có rời nhau 
(disjoint) không ? Chương trình hoạt động như sau : 
?- disjoint([a,b,c],[d,g,f,h]). 
Yes 
?- disjoint([a,b,c],[f,a]). 
No 
37. Vị từ forall(Cond, Action) thực hiện kiểm tra sự so khớp tương ứng giữa Cond, 
thường kết hợp với vị từ member, và Action. Ví dụ dưới đây kiểm tra việc thực hiện các 
phép toán số học trong danh sách L là đúng đắn. 
?- forall(member(Result = Formula, [2 = 1 + 1, 4 = 2 * 2]), 
Result =:= Formula). 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 201 
Result = _G615 
Formula = _G616 
Yes 
38. Sử dụng vị từ forall để viết chương trình Prolog kiểm tra một danh sách có là một tập 
hợp con của một danh sách khác hay không ? Chương trình hoạt động như sau : 
?- subset3([a,b,c],[c,d,a,b,f]). 
Yes 
?- subset3([a,b,q,c],[d,a,c,b,f]) 
No 
39. Sử dụng vị từ append ghép hai danh sách để viết các chương trình Prolog thực hiện các 
việc sau : 
prefixe(L1, L2) danh sách L1 đứng trước (prefixe list) danh sách L2. 
suffixe(L1, L2) danh sách L1 đứng sau (suffixe list) danh sách L2. 
isin(L1, L2) các phần tử của danh sách L1 có mặt trong danh sách L2. 
40. Sử dụng phương pháp Quicksort viết chương trình Prolog sắp xếp nhanh một danh sách các 
số đã cho theo thứ tự tăng dần. 
41. Đọc hiểu chương trình sau đây rồi dựng lại thuật toán : 
/* Missionarys & Cannibals */ 
/* Tránh vòng lặp */ 
lNotExist(_,[]). 
lNotExist(X,[T|Q]) :- 
 X\==T, lNotExist(X,Q). 
/* Kiểm tra tính hợp lý của trạng thái */ 
valid(MG,CG,MD,CD) :- 
 MG>=0, CG>=0, MD>=0, CD>=0, MG=0, MD>=CD. 
valid(MG,CG,MD,CD) :- 
 MG>=0, CG>=0, MD>=0, CD>=0, MG>=CG, MD=0. 
valid(MG,CG,MD,CD) :- 
 MG>=0, CG>=0, MD>=0, CD>=0, MG>=CG, MD>=CD. 
/* Xây dựng cung và kiểm tra */ 
sail(1,0). sail(0,1). sail(1,1). sail(2,0). sail(0,2). 
arc([left,MGi,CGi,MDi,CDi],[droite,MGf,CGf,MDf,CDf]) :- 
sail(Mis,Can), 
MGf is MGi-Mis, MDf is MDi+Mis, 
CGf is CGi-Can, CDf is CDi+Can, 
valid(MGf,CGf,MDf,CDf). 
arc([right,MGi,CGi,MDi,CDi],[left,MGf,CGf,MDf,CDf]) :- 
 sail(Mis,Can), 
MGf is MGi+Mis, MDf is MDi-Mis, 
CGf is CGi+Can, CDf is CDi-Can, 
valid(MGf,CGf,MDf,CDf). 
/* Phép đệ quy */ 
cross(A,A,[A],Non). 
cross(X,Y,Ch,Non) :- 
arc(X,A), lNotExist(A,Non), 
cross(A,Y,ChAY,[A|Non]), Ch=[X|ChAY]. 
/* Đi qua */ 
traverse(X,Y,Ch) :- 
 cross(X,Y,Ch,[X]).