Gi
ả
H
ọ
M
ã





BI
ỂU
Đề t
à
ả
ng viên:
P

ọ
c viên: Đà
ã
số: CH1
1
TRƯỜN
G
BÀI
T
U
DI
ỄN
à
i: Bi
ể
u
d
P
GS.TS Đ
ỗ
o Thị Phấ
n
1
01118
G
ĐẠI H
Ọ
ĐẠI HỌ
C
T

HU
H
N
TRI
d
iễn lo
gi
ỗ
Văn Nhơ
n
n

TPH
C
Ọ
C CÔNG
C
QUỐC G
H
OẠC
H
THỨ
C
i
c vị từ
b
n

C
M, Tháng

NGHỆ T
H
G
IA TPHC
M
H
MÔ
N
C
VÀ
Ứ
bằ
n
g
n
gô
01/2013
H
ÔNG TI
N
M

N
HỌ
C
Ứ
NG
D
ô
n n

g
ữ
P
N

C

D
ỤN
G
P
rolo
g

G

Trang 2

Mục lục

Lời nói đầu 3
Phần 1: Ngôn ngữ Prolog 4
1.1. Giới thiệu 4
1.2. Các thuật ngữ 4
1.3. Các kiểu dữ liệu 5
1.4. Chú thích 6
1.5. Biến 6
1.6. Phép toán số học 6
1.7. Sự kiện và luật 7
1.8. Chương trình Prolog 9

1.9. Phép hợp nhất 13
1.10. Cơ chế tìm câu trả lời của Prolog 14
1.11. Sự quay lui (back-tracing) 16
1.12. Nhát cắt 18
1.13. Cấu trúc danh sách 19
Phần 2: Một số chương trình minh họa bằng Prolog 21
2.1. Bài toán Tháp Hà Nội 22
2.2. Bài toán Tính giai thừa 24
2.3. Bài toán gia hệ 25
Tài liệu tham khảo 30



Trang 3

Lời nói đầu
Trong thời đại của công nghệ thông tin, ngày càng có nhiều ứng dụng thông minh
hơn hỗ trợ con người trong nhiều lĩnh vực như giáo dục, kinh doanh, Các chương trình
dạy học, ôn tập, tư vấn chiến lược kinh doanh ngày càng phổ biến. Hầu hết các phần
mềm, trang web như thế đều phải dựa trên những tri thức nhất định về một lĩnh vực nào
đó và chúng được chọn lọc, mô hình hóa và biểu diễn lại dưới dạng mà máy có thể hiểu
và cũng gần gũi với con người. Có nhiều mô hình biểu diễn tri thức cơ bản, phổ biến là
dùng logic vị từ, mạng ngữ nghĩa, hệ luật dẫn, …Đã từ lâu, sử dụng logic vị từ và sự suy
luận logic giúp giải quyết các vấn đề nhanh hơn và ngắn gọn hơn. Trong lĩnh vực lập
trình, cũng đã có nhiều trình biên d
ịch ra đời hỗ trợ ngôn ngữ lập trình cho lập trình logic.
Trong số đó nổi bật là Prolog.
Tiểu luận này trình bày khái quát về ngôn ngữ Prolog, đồng thời trình bày một vài ví
dụ minh họa cho việc biểu diễn tri thức dùng logic vị từ thông qua ngôn ngữ Prolog.
Em xin chân thành cảm ơn PGS.TS. Đỗ Văn Nhơn – Giảng viên môn học Biểu Diễn

Tri Thức và Ứng Dụng đã truyền đạt cho em những kiến thức vô cùng quý báu. Em cũng
xin chân thành cảm ơ
n quý Thầy Cô thuộc phòng đào tạo Sau đại học và các bạn về tài
liệu tham khảo để em có thể hoàn thành môn học này.

Chân thành cảm ơn!

Trang 4

Phần 1: Ngôn ngữ Prolog
1.1. Giới thiệu
Prolog là một ngôn ngữ lập trình. Tên gọi Prolog được xuất phát từ cụm từ tiếng
Pháp Programmation en logique, nghĩa là "lập trình theo lô-gích". Xuất hiện từ năm 1972
(do Alain Colmerauer và Robert Kowalski thiết kế), mục tiêu của Prolog là giúp người
dùng mô tả lại bài toán trên ngôn ngữ của logic, dựa trên đó, máy tính sẽ tiến hành suy
diễn tự động dựa vào những cơ chế suy diễn có sẵn (hợp nhất, quay lui và tìm kiếm theo
chiều sâu) để tìm câu trả
lời cho người dùng.
Prolog được sử dụng nhiều trong các ứng dụng của trí tuệ nhân tạo và ngôn ngữ học
trong khoa học máy tính (đặc biệt là trong ngành xử lý ngôn ngữ tự nhiên vì đây là mục
tiêu thiết kế ban đầu của nó). Cú pháp và ngữ nghĩa của Prolog đơn giản và sáng sủa, nó
được người Nhật coi là một trong những nền tảng để xây dựng máy tính thế hệ thứ năm
mà ở đó, thay vì phải mô tả cách gi
ải quyết một bài toán trên máy tính, con người chỉ cần
mô tả bài toán và máy tính sẽ hỗ trợ họ phần còn lại.
Nguyên lý của lập trình theo lô-gích dựa trên các mệnh đề Horn. Một mệnh đề Horn
biểu diễn một sự kiện nào đó là đúng hoặc không đúng, xảy ra hay không xảy ra.
Ví dụ 1:
Lan là một sinh viên
Nếu Lan học tốt thì sẽ có học bổng

Nếu X là cha mẹ của Y và Y là cha mẹ của Z thì X là ông bà của Z.
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ừ. Một vị từ có thể có một hoặc nhiều nguyên tử logic (logic
atom). Mỗi logic atom biểu diễn quan hệ giữa các hạng (term). Term có thể
sơ cấp
(elementary term) như các hằng, các biến và phức hợp (compound term).
Trang 5

Các term phức hợp biểu diễn các đối tượng phức tạp của bài toán đang xét. Term
phức hợp là một hàm tử (functor) có đối số (argument), các functor này có dạng:
Tên_functor(Đối_1, Đối_2,…, Đối_n)
Tên_functor là một chuỗi gồm các chữ cái và chữ số, và được bắt đầu bằng một chữ cái
thường ; các đối có thể là biến, term sơ cấp hoặc phức hợp.
Mệnh đề có thể là một sự kiện, m
ột luật hay một câu hỏi. Prolog quy ước sau mỗi
mệnh đề cần có một dấu chấm để kết thúc.
1.3. Các kiểu dữ liệu
Trong Prolog, có hai dạng kiểu dữ liệu, một là “kiểu sơ cấp”, hai là “kiểu có cấu
trúc”. Kiểu dữ liệu sơ cấp bao gồm một số kiểu dữ liệu được định nghĩa sẵn trong Prolog,
bao gồm:
9 char: kiểu ký tự, khi sử dụ
ng đặt trong cặp dấu nháy đơn. Ví dụ: ‘a’, ‘b’, …
9 string: kiểu chuỗi, khi sử dụng đặt trong cặp dấu nháy đôi. Ví dụ: “day la chuoi”
9 integer: số nguyên
9 unsigned: số nguyên không dấu (nguyên dương)
9 real: số thực
Kiểu dữ liệu có cấu trúc do người dùng tự định nghĩa dựa trên các kiểu sơ cấp đã có
sẵn và sẽ được nhắc đến trong các phần tiếp theo.
Có một số trình biên dị

ch ngôn ngữ Prolog không yêu cầu người dùng phải khai báo
kiểu dữ liệu được dùng như SWI-Prolog. Tuy nhiên, với Visual Prolog thì điều này là cần
thiết đối với các hàm hay vị từ.
Trang 6

1.4. Chú thích
Tương tự như các ngôn ngữ khác, trong một chương trình Prolog, người dùng có thể
thêm vào các chú thích (comment). Khi muốn chú thích cho một dòng, có thể sử dụng dấu
% và sử dụng cặp dấu /* và */ khi chú thích nhiều dòng.
Ví dụ 2:
%%%%%%%%%%%%%%
% đây là một dòng chú thích
% đây cũng là một dòng chú thích
/* đây cũng là một dòng chú thích */
/* đây là chú thích
đây cũng là chú thích
đây cũng là chú thích */
%%%%%%%%%%%%%%
1.5. Biến
Trong Prolog, người dùng có thể sử dụng các biến. Tên biến được quy ước là một
chuỗi gồm chữ cái và chữ số và luôn bắt đầu bằng một chữ cái hoa hoặc dấu gạch dưới _.
Ví dụ 3:
Tên các biến sau là không hợp lệ: so_nguyen, 1n, 123, …
Tên các biến sau là hợp lệ: X, Ten, _, _Nam, So_nguyen, …
Trong Prolog, có một biến đặc biệt, không cần chỉ định kiểu khi sử dụng, đó là dấu
gạch dưới _. Dấu này được xem như một biến có thể sử dụng cho trường hợp một vị từ
nào đó có một đối mà với bất kỳ giá trị nào của đối này cũng nhận được một giá trị duy
nhấ
t.
1.6. Phép toán số học

Prolog chủ yếu hỗ trợ xử lý các ký hiệu, tuy nhiên, nó cũng hỗ trợ một số phép toán
hai ngôi chuẩn như sau:

Trang 7

Phép toán Ý nghĩa
+ Cộng hai số
- Trừ hai số
* Nhân hai số
/ Chia hai số
Mod Chia lấy phần dư
Div Chia lấy phần nguyên

Phép so sánh hai ngôi
Phép so sánh Ý nghĩa
> Lớn hơn
>= Lớn hơn hoặc bằng
< Nhỏ hơn
<= Nhỏ hơn hoặc bằng
<>hoặc >< Khác
:= Bằng
Với toán tử logic, Prolog sử dụng dấu phẩy , thay cho toán tử and (và) và dấu chấm
phẩy ; thay cho or (hoặc).
1.7. Sự kiện và luật
Sự kiện là một vị từ diễn tả một sự thật. Để hiểu rõ hơn về sự kiện, xét các ví dụ sau:
Ví dụ 4: “2 là một số nguyên tố” là một sự kiện vì nó diễn tả sự thật “2 là một số nguyên
tố”. Và diễn đạt nó dưới một vị từ trong Prolog như sau: nguyen_to(2).
Ví dụ 5: Xét cây phả hệ như sau:

T

“cha
m
p
aren
t
V
từ nh
ư
L
dưới
d
Xét c
á
Ví d
ụ
của
Y
Luật
t
Ví d
ụ
T
rong hìn
h
m
ẹ của”.
S
t
(“mar”, “
b

V
ị từ pare
n
ư
sau:
p
p
p
p
p
p
L
uật là vị
t
d
ạng một
m
á
c ví dụ sa
u
ụ
6: giả sử
đ
Y
. Ta có luậ
t
child
(
tr
ên được h

7: để suy
d
h
trên, các
n
S
ự kiện “m
a
b
il”).
n
t có hai đố
i
p
arent(“ma
r
p
arent(“to
m
p
arent(“to
m
p
arent(“bil
”
p
arent(“bil
”
p
arent(“su

e
t
ừ diễn tả
q
m
ệnh đề. T
r
u
để hiểu
r
õ
đ
ịnh nghĩa
t
như sau:
(
X,Y):-
p
are
iểu là: X l
à
d
iễn số ngu
y
Hình 1:
n
út thể hiệ
n
a
r là cha

m
i
là “mar”
v
r
”, “bil”).
m
”, “bil”).
m
”, “liz”).
”
, “ann”).
”
, “sue”).
e
”, “jim”).
q
uy luật s
u
r
ong Prolo
g
õ
hơn về lu
ậ
thêm vị từ
n
t(Y,X)
à
con của Y

y
ên N bất
k
Trang 8
Cây phả h
ệ
n
cho ngườ
m
ẹ của bil”
v
à “bil”. Đ
ể
u
y diễn đư
ợ
g
, để định
n
ậ
t.
child(X,Y
)
Nếu Y là
c
k
ỳ là một s
ố
ệ
gia đình

ờ
i, các mũi
t
được diễn
ể
diễn đạt c
h
ợ
c công nh
ậ
n
ghĩa cho
m
)
với hai đ
ố
c
ha mẹ của
X
ố
nguyên tố

t
ên thể hiệ
n
đạt bằng
m
h
o cây phả
ậ

n đúng. L
u
m
ột luật, sử
ố
i số, man
g
X.
ta viết:
n
cho mối
q
m
ột vị từ
n
hệ t
r
ên thì
u
ật được t
r
dụng cặp
k
g
ý nghĩa:
X
q
uan hệ
n
hư sau:

cần 6 vị
r
ình bày
k
ý tự :
X
là con
Trang 9

“N là một số nguyên tố nếu N>0, M là số nguyên tố nào đó, M<N và N không chia hết
cho M”. Khi biểu diễn bằng Prolog, có thể viết như sau:
nguyen_to(N):-N>0, nguyen_to(M), M<N, N mod M <> 0.
Ví dụ 8: để diễn tả luật: ai là người đều phải chết, ta viết như sau
chet(X):-nguoi(X).
Ở đây, có sự khác nhau cơ bản giữa sự kiện và luật. Sự kiện là một điều gì đó luôn
đúng và không có ràng buộc. Trong khi đó, các luật thì phải phụ thuộc vào các biến hay
thuộc tính và khi thoả mãn điều kiện nào đó thì là đúng. Một luật thường gồm hai phần:
phần bên trái dấu :- được gọi là kết luận hay phần đầu (head) của luật, và phần bên phải
được gọi là
điều kiện hay phần thân (body) của luật. Nếu điều kiện đúng thì phần kết luận
cũng đúng và đây là hậu quả logic của phép suy luận (inference).
1.8. Chương trình Prolog
Một chương trình Prolog thường gồm 3 hoặc 4 phần cơ bản như sau: domains,
predicates, clauses và goal.
Phần domains
Đây là phần định nghĩa kiểu dữ liệu mới dựa vào các kiểu dữ liệu đã biết. Các kiểu
dữ liệu được định nghĩa ở đây sẽ được sử dụng cho các đối số trong các vị từ. Nếu các vị
từ sử dụng đối số có kiểu cơ bản thì có thể không cần phải định nghĩa lại các kiểu đó. Tuy
nhiên để cho chương trình sáng sủa, người ta sẽ định nghĩa lại cả các kiểu cơ bản.
Cú pháp:

<danh sách kiểu mới> = <kiểu đã biết>
hoặc <danh sách kiểu mới> = <danh sách kiểu đã biết>
<kiểu đã biết>: có thể là kiểu cơ bản (như số nguyên, số thực, …) hoặc các kiểu đã
được định nghĩa trước.
Trong đó các kiểu mới phân cách nhau bởi dấu phẩy, còn các kiểu đã biết phân cách
nhau bởi dấu chấm phẩy.
Ví dụ 9:
Trang 10

domains
ten, tac_gia, nha_xb, dia_chi = string.
nam, thang, so_luong = integer.
dien_tich = real.
nam_xb = nxb(thang, nam).
do_vat = sach(tac_gia, ten, nha_xb, nam_xb); xe(ten, so_luong); nha(dia_chi,
dien_tich).
Trong ví dụ trên, các kiểu mới đã được định nghĩa, trong đó các kiểu mới ten,
tac_gia, nha_xb, dia_chi dựa vào cùng một kiểu cơ bản đã biết là string; các kiểu mới
nam, thang, so_luong dựa vào cùng một kiểu đã biết là integer; kiểu mới dien_tich dựa
vào kiểu đã biết là real; kiểu mới năm_xb dựa vào kiểu nxb được xây dựng từ các kiểu đã
biết là thang, nam; còn kiểu do_vat lại dựa vào các kiểu sach, xe, nha mà các kiểu này lại
dựa vào các kiểu đã biết.
Phần predicates
Đây là phần bắt buộc phải có. Trong phần này, cần phải khai báo đầy đủ các vị từ sử
dụng trong phần clauses, ngoại trừ các vị từ mà trình biên dịch Prolog đã xây dựng sẵn.
Cú pháp:
<Tên vị từ> (<danh sách các kiểu>)
<danh sách các kiểu> là các kiểu cơ bản hoặc là các kiểu đã được định nghĩa trong
phần domains và được viết phân cách nhau bởi dấu phẩy.
Ví dụ 10:

predicates
so_huu (ten, do_vat).
nguyen_to(integer).
nguoi(ten).
chet(ten).
parent(ten, ten).
Trang 11

Trong ví dụ trên ta khai báo năm vị từ. Trong đó vị từ so_huu (ten, do_vat) để chỉ một
người có tên là ten sẽ sở hữu môt do_vat nào đó. Còn vị từ nguyen_to(integer) để xét xem
một số nguyên nào đó có phải là số nguyên tố hay không. Vị từ thứ ba để xét xem một cái
tên ten nào đó có là người không, còn vị từ chet(ten) sẽ xét xem có phải chết hay không.
Vị từ cuối cùng đã được xét trong ví dụ bên trên, xét xem một người có tên là ten (đối thứ
nhất) có là cha/mẹ của người có tên là ten (đối thứ hai) hay không.
Phần clauses
Đây là phần bắt buộc phải có dùng để mô tả các sự kiện và các luật, sử dụng các vị
từ đã khai báo trong phần predicates.
Cú pháp:
<Tên vị từ>(<danh sách các tham số>) <kí hiệu>
<Tên vị từ 1>(<danh sách các tham số 1>) <kí hiệu>
………
<Tên vị từ N>(<danh sách các tham số N>) <kí hiệu>
Trong đó: Tên vị từ phải là các tên vị từ đã được khai báo trong phần predicates.
Các tham số có thể là các hằng hoặc biến có kiểu tương thích với các kiểu tương ứng đã
được khai báo trong các vị từ ở trong phần predicates; các tham số được viết cách nhau
bởi dấu phẩy. Các kí hiệu bao gồm:
:- (điều kiện nếu).
, (điều kiện và).
; (điều kiện hoặc).
. (kết thúc vị từ)

Ví dụ 11:
clauses
nguyen_to(2):-!.
nguyen_to(N):-N>0,
nguyen_to(M),
Trang 12

M<N,
N mod M <>0.
so_huu(“Nguyen Van A”, sach(“Do Xuan Loi”, “Cau truc DL”, “Khoa hoc Ky
thuat”, nxb(8,1985))).
nguoi(“Socrates”).
chet(X):-nguoi(X).
Chú ý: Nếu trong các tham số của một vị từ có biến thì biến này phải xuất hiện ít
nhất 2 lần trong vị từ đó hoặc trong các vị từ dùng để suy diễn ra vị từ đó. Nếu chỉ xuất
hiện một lần thì bắt buộc phải dùng biến tự do.
Ví dụ 12: Để diễn tả sự kiện: Tổ hợp chập 0 của N (N bất kỳ) bằng 1, không thể viết
Tohop(N,0,1) vì biến N chỉ xuất hiện đúng một lần trong vị từ này, do đó phải viết
Tohop(_,0,1) .
Phần goal
Trong phần này, người dùng sẽ đưa ra các mục tiêu cần tìm kết quả. Đây thực chất
là các câu hỏi mà người dùng muốn Prolog trả lời dựa vào các sự kiện và luật đã được
khai báo và định nghĩa ở trên.
Cú pháp phần goal giống như cú pháp phần clauses. Tức là đưa vào một hoặc một số
các vị từ. Nếu tất cả các tham số của vị từ là hằng thì kết quả nhận được là true (hoặc Yes
- đúng) hoặc false (hoặc No - sai). Nếu trong các tham số của vị từ có biến thì kết quả trả
về sẽ là các giá trị của biến.
Ví dụ 13: muốn biết 4 có phải là số nguyên tố không, trong phần goal sẽ nhập vị từ sau:
nguyen_to(4).
Kết quả nhận được sẽ là true

Nếu phần goal được nhập là nguyen_to(X). thì câu trả lời là X=2
Ngoài các phần chủ yếu nói trên, có thể đưa vào các phần liên quan đến khai báo
hằng, các tập tin liên quan hoặc chỉ thị dịch.
Ví dụ 14: khai báo hằng
Trang 13

constants
Pi = 3.141592653
Thể hiện phần goal cũng khác nhau tùy theo trình biên dịch, có một số trình biên
dịch sẽ cho người dùng nhập phần goal sau dấu nhắc ?- (như B-Prolog hay SWI-Prolog).
Tuy nhiên, cũng có trình biên dịch như Turbo-Prolog hay Visual Prolog thì các mục tiêu
viết sau từ khóa goal.
1.9. Phép hợp nhất
Công việc quan trọng nhất của Prolog trong việc tìm câu trả lời là thực hiện việc hợp
nhất. Để tiện cho việc theo dõi, phép hợp nhất được ở đây sẽ được biểu diễn bởi dấu =.
Nó có hai thành phần, tạm gọi là vế trái vế phải. Phép hợp nhất sẽ trả về kết quả true
(thành công) hoặc false (thất bại).
Có các trường hợp hợp nhấ
t sau:
a) Cả hai vế đều là hằng hoặc biểu thức chứa toàn hằng. Nếu giá trị của hai vế là bằng
nhau thì phép hợp nhất thành công (đáp số là true), ngược lại phép hợp nhất sẽ thất bại
(kết quả là false)
Ví dụ 15:
7 = 7 Æ true
7 = 8 Æ false
“abc” = “abc” Æ true
“abcd” = “abc” Æ false
2 = 1 +1 Æ false
1+1 = 1+1 Æ true
Một trong hai vế là hằng hoặc trong biểu thức chứa toàn hằng, vế kia là biến hoặc biểu

thức có chứa biến.
Trường hợp 1: Nếu tất cả các biến đều có giá trị (gọi là các biến ở tình trạng
bound), quay về trường hợp a
7 = X Æ false nếu X đã có giá trị là 6
7 = X +1 Æ true nếu X đã có giá trị
là 6
Trang 14

Y = “Socrates”Æ true nếy Y đã có giá trị là “Socrates”
Trường hợp 2: Nếu có biến chưa có giá trị (gọi là biến ở tình trạng unbound), Prolog
sẽ gán giá trị cho biến sao cho hai vế có giá trị như nhau và trả về kết quả là true. Nếu
không tìm giá trị như vậy, phép hợp nhất sẽ cho kết quả là false.
7 = X Æ true nếu X chưa có giá trị, sau phép hợp nhất này, X sẽ có giá trị là 7
-1 = X*X Æ false vì không thể tìm cho X giá trị nào làm cho giá trị hai vế là như nhau.
b) Cả hai vế đều là biến hoặc các biểu thức có chứa biến
Trường hợp 1: tất cả các biến đều có chứa giá trị, quay về trường hợp a
X = Y Æ true nếu cả X và Y đều đã có giá trị và những giá trị này bằng nhau
X -1 = Y Æ false nếu X và Y đều đã có giá trị và X nhỏ hơn Y
Trường hợp 2: tất cả các biến của một vế đều đã có giá trị, quay về về trường hợp b.
X = Y Æ true nếu X chưa có giá trị và Y đã có giá trị, sau phép hợp nhất, X sẽ nhận
giá trị của Y
X - 1 = Y Æ true nếu X chưa có giá trị, Y đã có giá trị. Sau phép hợp nhất, X sẽ có giá
trị bằng Y +1
Trường hợp 3: cả hai vế đều còn chứa biến ở tình trạng unbound thì hợp nhất vẫn
thành công và mỗi khi một biến nào đó trong vế phải hoặc vế trái có giá tr
ị thì biến còn lại
cũng sẽ được ràng buộc với giá trị đó.
X = Y Æ true nếu cả X và Y đều chưa gán giá trị
X-1 = Y Æ true nếu cả X và Y đều chưa gán giá trị
1.10. Cơ chế tìm câu trả lời của Prolog

Khi người dùng đặt ra cho Prolog một câu hỏi (phần goal), Prolog sẽ thực hiện công
việc so trùng (match), tức là tìm mệnh đề đầu tiên đề cập đến khái niệm mà người dùng
muốn hỏi. Nói m
ột cách chi tiết hơn, Prolog sẽ dùng phép hợp nhất đã trình bày ở phần
trên trong quá trình so trùng cấu trúc dữ liệu một mục tiêu với một mệnh đề. Giả sử người
dùng đặt ra câu hỏi như sau:
nguoi(“Socrates”).
Trang 15

Prolog sẽ tìm mệnh đề đầu tiên có liên quan đến khái niệm nguoi. Hiển nhiên, mệnh
đề đầu tiên (và duy nhất) có liên quan đến khái niệm này là: nguoi(“Socrates”).
Như vậy, khi đã có câu hỏi (nguoi(“Socrates”).) và tìm thấy mệnh đề liên quan
(nguoi(“Socrates”).), Prolog sẽ tiến hành tìm kiếm lời giải, công việc này tiến hành bằng
cách 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ố ở phần mệnh đề.
Sau khi đã tạo mối quan hệ giữa các thông số ở ph
ần câu hỏi và phần mệnh đề, Prolog sẽ
tiến hành các mệnh đề (nếu mệnh đề này một luật). Nếu tất cả các mệnh đề thành công và
các biến ở phần câu hỏi đã ở tình trạng bound (tức là đã có giá trị), Prolog sẽ thông báo
lời giải.
Nếu là câu hỏi thuộc dạng true/false (Yes/No) như ví dụ trên, tức là câu hỏi không
chứa biến, Prolog sẽ trả lời true (Yes) nếu công việc hợp nh
ất thành công và các mệnh đề
đều thành công (nếu mệnh đề so trùng là một luật).
Với ví dụ trên, thông số của câu hỏi là một hằng (“Socrates”), và thông số của mệnh
đề tương ứng cũng là một hằng (“Socrates”), hai hằng này hợp nhất thành công, và kết
quả trả lời là true(Yes).
Nếu người dùng đặt ra câu hỏi khác: nguoi(“Xeda”)
Prolog cũng chỉ tìm thấy một mệnh đề liên quan đến khái niệm này
(nguoi(“Socrates”).), và vì sự hợp nhất giữa hai hằng “Socrates” và “Xeda” thất bại, đáp
số sẽ trả lời là false(No).

Xét trường hợp câu hỏi có chứa biến: nguoi(X)
Hệ thống sẽ tìm thấy mệnh đề có liên quan đến vấn đề này (nguoi(“Socrates”)) , và
tiến hành hợp nhất giữa X và “Socrates”, và vì X chưa có giá trị (unbound) nên phép hợp
nhất thành công, X có giá trị là ‘“Socrates”.
Khi việc hợp nhất giữa các thông số giữa phần câu hỏi và phần mệnh đề đã thành
công, tất cả các biến cần tìm đã có giá trị (ở đây chỉ có một biến là X), hệ thống sẽ công
bố đã tìm ra lời giải và in ra giá trị của X ( X = “Socrates”)
Xét trường hợp khi ở câu hỏi so trùng với một luật: chet(Y)
Câu hỏi được so trùng với mệnh đề sau: chet(X): - nguoi (X).
Trang 16

Vì hai biến X (đối của mệnh đề) và Y (đối của câu hỏi) đều chưa chứa giá trị, hệ
thống sẽ xem cả hai biến là một, tức là, khi X có được giá trị thì Y cũng có giá trị đó và
ngược lại.
Quá trình thực hiện các mệnh đề con ở vế phải sẽ được thực hiện như sau:
• Nếu mệnh đề con này có thông số là biến unbound, Prolog sẽ tìm giá trị của biến này
để m
ệnh đề con có giá trị true(Yes), nếu không tìm được giá trị như vậy, mệnh đề con sẽ
thất bại.
• Nếu mệnh đề con có đối đều là biến bound (đã có giá trị) hoặc là hằng, Prolog sẽ kiểm
tra xem mệnh đề con có trả về giá trị true(Yes) hay không, nếu không, mệnh đề con sẽ
thất bại.
Các mệnh đề con sẽ được tiến hành từ trái qua phải, và nếu có một mệnh đề con
thấ
t bại, mệnh đề được so trùng sẽ thất bại.
Trong trường hợp trên, khi tiến hành mệnh đề nguoi(X), do biến X là unbound, nên
rơi vào trường hợp a, hệ thống sẽ tìm giá trị của X cho mệnh đề con trên là đúng. Cách
tìm kiếm câu trả lời cho mệnh đề con này hoàn toàn giống như cách hệ thống tìm câu trả
lời khi đặt câu hỏi này trong phần câu hỏi, và như vậy X sẽ có giá trị là “Socrates”sau khi
mệnh đề con này thực hiện xong.

Do X và Y
được xem như một, nên khi X có giá trị là “Socrates” thì Y cũng có giá
trị này và Prolog công bố là đã tìm ra lời giải và in ra giá trị của Y là : Y=“Socrates”
1.11. Sự quay lui (back-tracing)
Trong Prolog, phép hợp nhất là chủ đạo, tuy nhiên, để tìm ra lời giải đúng, Prolog
cần phải sử dụng cơ chế quay lui, khi giá trị đầu tiên được gán cho đối số không phải là
lời giải. Xét ví dụ sau: giả sử có các mệnh đề:
nguoi(“Socrates”).
nguoi(“Xeda”).
vua(“Xeda”).
sungsuong(X) :- nguoi(X), vua(X).
Trang 17

Trong ví dụ này, ngoài khái niệm về người, còn có khái niệm về vua và sự sung
sướng. Có thể diễn giải những thông tin trong các vị từ trên thành ngôn ngữ tự nhiên như
sau : "Có hai người tên là Socrates và Xeda. Một người là vua tên Xeda. Và một luật là :
một thực thể nào đó chỉ sung sướng nếu thực thể đó vừa người vừa là vua."
Giả sử có câu hỏi sau: sungsuong(X)
Trong quá trình tìm lời giải, trước tiên hệ thống sẽ so trùng câu hỏi trên với mệnh
đề
sungsuong(X) :- nguoi(X),vua(X). Tuy nhiên, khi so trùng câu hỏi với mệnh đề, do cả
hai biến X lúc này đều chưa chứa giá trị, nên chúng sẽ được xem như một.
Sau đó Prolog sẽ tiến hành các mệnh đề con. Ở mệnh đề con đầu tiên, nguoi(X),
tương tự như ví dụ ở phần trên, Prolog sẽ tìm được câu trả lời là X = “Socrates”. Khi thực
hiện mệnh đề con thứ hai, vua(X), do X đã có giá trị (Socrates), Prolog sẽ kiểm tra xem
giá trị này có làm giá trị của mệnh đề là true hay không.
Như các ví dụ trên, việc tiến hành trả lời một mệnh đề con cũng tương tự như khi trả
lời một câu hỏi, Prolog lại so trùng mệnh đề con với một mệnh đề cùng tên. Prolog tìm
thấy một mệnh đề liên quan đến vua là vua(“Xeda”) và tiến hành hợp nhất giữa X và
Xeda. Do X đã có giá trị là Socrates, việc hợp nhất thất bại.

Tuy nhiên khi mệnh đề con này thất bại, không có nghĩa rằng Prolog sẽ vội kết luận
rằng mệnh đề này thất bại. Ở đây công việc tìm kiếm câu trả lời thất bại sau khi biến X
được gán giá trị và chuyển từ trạng thái bound sang unbound. Hệ thống sẽ quay lại thời
điểm biến X được gán giá trị (khi trả lời mệnh đề con nguoi(X)), X được chuyển lại sang
tình trạng unbound, và cố gắng tìm kiếm một giá trị khác của X để cho mệnh đề con này
vẫn
đúng. Công việc này được gọi là sự quay lui (back-tracing).
Do việc so trùng mệnh đề con này với mệnh đề nguoi(“Socrates”) thất bại, hệ thống
sẽ so trùng với mệnh đề khác. Nếu không còn mệnh đề nào khác liên quan đến mệnh đề
con, việc thực hiện mệnh đề mới thật sự thất bại, tuy nhiên ở đây hệ thống tìm thấy một
mệnh đề khác liên quan đến khái niệm này là nguoi(“Xeda”). Việc hợp nhất giữ
a X và
Xeda lại được thực hiện, X sẽ có giá trị là Xeda và sau đó, khi lại tiếp tục thực hiện mệnh
đề con vua(X) thì chúng ta sẽ dễ dàng thấy rằng mệnh đề con lần này được thực hiện
Trang 18

thành công. Prolog đã tìm ra lời giải, tuy nhiên, ở trường hợp này, ngoài sự hợp nhất,
Prolog còn sử dụng kỹ thuật quay lui. Như vậy, câu trả lời cho câu hỏi sungsuong(X) sẽ là
X= “Xeda”.
1.12. Nhát cắt
Prolog tự động quay lui khi cần tìm một tìm kiếm một mệnh đề khác để thoả mãn
mục tiêu đưa ra. Điều này rất có ích đối với người lập trình khi cần sử dụng
nhiều phương án giải quyết vấn
đề . Tuy nhiên, nếu không kiểm soát tốt quá trình này,
việc quay lui sẽ trở nên kém hiệu quả. Vì vậy, Prolog sử dụng kỹ thuật nhát cắt để kiểm
soát quay lui, hay cấm quay lui, đồng thời giúp khống chế số lời giải nhằm khắc phục
khiếm khuyết này.
Trong ví dụ sau đây, một chương trình Prolog sử dụng kỹ thuật quay lui kém hiệu
quả. Giả sử có ba quy tắc để xác định mối liên hệ giữa hai s
ố X và Y:

1. Nếu X < 3 thì Y = 0
2. Nếu X ≤ 3 và X < 6 thì Y = 2
3. Nếu X ≤ 6 thì Y = 4
Và định nghĩa vị từ f( X, Y ) trong Prolog như sau :
f( X, 0) :- X < 3. % luật 1
f( X, 2) :- 3 =< X, X < 6. % luật 2
f( X, 4) :- 6 =< X. % luật 3
Giả sử đặt ra câu hỏi: f( 1, Y ), 2 < Y.
Lúc này, Y nhận giá trị 0, đích thứ hai trở thành : 2<0, và câu trả lời là false(No) –
thất bại. Tuy nhiên, do sự quay lui nên Prolog xét cả hai luật còn lại như hình bên dưới.

N
quay
một
n
1.13.
M
đối t
ư
của đ
(head
lại củ
a
D
cách
n
a)
.
b)
Ví

Danh
N
hư vậy,
đ
lui không
c
n
hát cắt tại
v
f( X,
0
f( X,
2
f( X,
4
Cấu trúc
d
M
ột danh
s
ư
ợng của d
a
ối
t
ượng đ
ề
)
là phần t
ử

a
danh sác
h
D
anh sách
n
hư sau:
.
Liệt kê cá
c
.
Mô tả ph
ầ
dụ 16: Mô
sách trên
c
[1,2,3,4,
đ
ể thông bá
o
c
ần thiết, c
ó
v
ị trí cần d
ừ
0
) :- X < 3,
2
) :- 3 =<

X
4
) :- 6 =<
X
d
anh sách
s
ách là mộ
t
a
nh sách c
ó
ề
u có ý ng
ử
đầu tiên
c
h
.
r
ỗng được
c
phần tử c
ủ
ầ
n đầu và p
h
t
ả một dan
h

c
ó thể mô t
ả
5
]
o
cho Prol
o
ó
thể sử dụ
n
ừ
ng. Các lu
ậ
!.
X
, X < 6,!.
%
X
.
%
t
dãy bất k
ỳ
ó
thể t
r
ùng
hĩa. Một d
c

ủa danh sá
mô tả là:
[
ủ
a danh sá
c
h
ần đuôi c
ủ
h
sách bao
ả
theo các c
á
Trang 19
o
g biế
t
là c
ầ
n
g nhát cắt
ậ
t t
r
ên thể
h
% luật 1
%
luật 2

%
luật 3
ỳ
các đối
t
ư
nhau (xuấ
t
anh sách t
r
ch và phần
[
]. Một da
n
c
h, ví dụ: [
1
ủ
a danh sác
h
gồm 5 số
n
á
ch sau:
ầ
n phải dừ
n
t
. Dấu chấ
m

h
iện lại có
s
ư
ợng. Khác
t
hiện nhiề
u
r
ên Prolog
n
đuôi (tail)
n
h sách kh
á
1
,2,3,4,5]
h
, ngăn các
h
n
guyên là 1
,
n
g ngay đi
ể
m
than !, đ
ạ
s

ử dụng nh
á
với kiểu d
ữ
u
lần) và
m
bao gồm
h
là danh sá
c
á
c
r
ỗng có
h bởi dấu |
,
,
2,3,4,5
ể
m nào để
t
ạ
i diện cho
s
á
t cắt như s
ữ
liệu tập
h

m
ỗi vị trí x
u
h
ai phần: p
h
c
h các phầ
n
thể mô tả
t
,
ví dụ [1|[
2
t
ránh sự
s
ử dụng
s
au :
h
ợp, các
u
ất hiện
h
ần đầu
n
tử còn
t
heo hai

2
,3,4,5]]
Trang 20

[1|[2,3,4,5]]
[1|[2|[3,4,5]]]
[1|[2|[3|[4,5]]]]
[1|[2|[3|[4|[5]]]]]
[1|[2|[3|[4|[5|[]]]]]]
Các phần tử của một danh sách có thể là các đối tượng có kiểu bất kỳ, kể cả kiểu
danh sách. Thông thường, phần đuôi của danh sách được xử lý như là một danh sách.
Prolog hỗ trợ một số vị từ cho các thao tác trên danh sách như sau:
Vị từ Ý nghĩa
append(List1, List2, List3) Ghép hai danh sách List1 và List2 thành List3.
member(Elem, List) Kiểm tra Elem có là phần tử của danh sách List hay
không, nghĩa là Elem hợp nhất được với một trong các
phần tử của List.
delete(List1, Elem,List2) Xoá khỏi danh sách List1 những phần tử hợp nhất được
với Elem để trả về kết quả List2.
select(Elem, List, Rest) Lấy phần tử Elem ra khỏi danh sách List để trả về
những phần tử còn lại trong Rest, có thể dùng để chèn
một phần tử vào danh sách.
last(List, Elem) Kiểm tra phần tử đứng cuối cùng trong danh sách List
có phải là Elem hay không.
reverse(List1, List2) Nghịch đảo thứ tự các phần tử của danh sách List1 để
trả về kết quả List2.
nth0(Index, List, Elem) Kiểm tra phần tử thứ Index (tính từ 0) của danh sách
List có phải là Elem hay không.



Trang 21

Phần 2: Một số chương trình minh họa bằng Prolog
Phần này trình bày một số chương trình minh họa viết bằng Prolog, cụ thể là sử
dụng trình biên dịch Visual Prolog. Như đã nêu trong phần trên, cùng hỗ trợ ngôn ngữ
Prolog nhưng các trình biên dịch khác nhau sẽ có những quy tắc riêng và hỗ trợ riêng dựa
trên cái lõi chung là ngôn ngữ Prolog. Sau đây trình bày một số nét khác biệt khi sử dụng
ngôn ngữ Prolog trong Visual Prolog.
Khai báo các sự kiện (facts)
Trong Visual Prolog, khi khai báo các vị từ có thể cần chỉ định kiểu (mode) của vị
từ. Các mode này bao gồm:
9 single: với mode này, sự kiện chỉ có một giá trị duy nhất, nếu giá trị khác được
thêm vào thì sẽ ghi đè (overwrite) lên giá trị cũ. Nếu một sự kiện có mode này thì
khi gọi luôn nhận được giá trị đúng.
9 determ: với mode này, sự kiện có thể có một hoặc không có giá trị nào cả. Khi sự
kiện không có giá trị thì khi gọi sẽ trả về thất bại, ngược lại sẽ thành công.
9 nondeterm: với mode này, s
ự kiện có thể có một hoặc nhiều hoặc không có giá trị
nào cả.
Nếu lúc khai báo mà không chỉ định các mode này thì kiểu nondeterm được dùng
làm mặc định.
Khai báo vị từ (predicates)
Tương tự như fact, có thể dùng thêm các mode hỗ trợ khi khai báo các vị từ, các
mode bao gồm:
9 procedure: với mode này, vị từ luôn thành công và có một lời giải duy nhất và
không có sự quay lui
9 determ: với mode này, vị từ có thể thành công hoặc thất bại, nếu thành công thì
chỉ
một lời giải và cũng không có sự quay lui.
9 multi: với mode này, vị từ sẽ không bao giờ thất bại và cho nhiều lời giải.

9 nondeterm: với mode này, vị từ có thể thất bại hoặc thành công và có sự quay lui.
Trang 22

9 erroneous: đây là một mode đặc biệt, với mode này thì không có sự thành công
cũng như thất bại, nó chỉ nêu lên các ngoại lệ (exception). Ví dụ như không tìm
thấy tập tin (file cannot be found), tràn bộ nhớ (memory overflow), …
Nếu người dùng không chỉ định mode cho vị từ thì procedure được sử dụng làm
mode mặc định.
Khai báo danh sách
Visua Prolog sử dụng dấu * cho việc khai báo một biến nào đó là kiểu danh sách.
Ví dụ 17: khai báo biến mang là danh sách các số nguyên: mang=integer*.
Visual Prolog hỗ trợ hai chế độ thực thi, đó là console và giao diện người dùng (GUI).
Hai ví dụ sau thể hiện cho hai chế độ này.
2.1. Bài toán Tháp Hà Nội
Mô tả bài toán như sau: có một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm
xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích
thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón.
Yêu cầu của bài toán là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc
sau:
• một lần chỉ được di chuyển một đĩa
• một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải
có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất)
Thuật giải đệ quy cho bài toán tháp Hà Nội như sau:
• đặt tên các cọc là A, B, C những tên này có thể chuyển ở các bước khác nhau (ở
đây: A = Cọc Nguồn, B = Cọc Đích, C = Cọc Trung Gian)
• gọi n là tổng số đĩa
• đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng)
Để chuyển n đĩa từ cọc A sang cọc B thì cần:
1. chuyển n-1 đĩa từ A sang C. Chỉ còn lại đĩa #n trên cọc A
2. chuyển đĩa #n từ A sang B


3
.
Đoạn
p
redi
c
h
claus
e
h
class
p

m
claus
e

m

m



goal

h
Khi b
chuyển n
-

chương trì
n
c
ates
anoi : (uns
i
e
s
anoi(N) :-
m
p
redicates
m
ove : (uns
i
e
s
m
ove(0, _,
_
m
ove(N, A,
move(N-
1
stdio::wri
t
move(N-
1
h
anoi(4).

iên dịch và
-
1 đ
ĩ
a từ C
s
n
h viết bằn
g
i
gned N).
m
ove(N, "t
r
i
gned N, st
r
_
, _) :- !.
B, C) :-
1
, A, C, B),
t
ef("di chu
y
1
, B, A, C).
chạy, thu
đ
Hình

2
s
ang B cho
g
Prolog c
h
r
ai", "giua"
r
ing A, stri
n
y
en mot di
a
đ
ược kết q
u
2
: Kết quả
c
Trang 23
chúng nằ
m
h
o bài toán
t
, "phai").
n
g B, strin
g

a
tu cot % s
a
u
ả sau:
c
hạy cho b
à
m
t
r
ên đ
ĩ
a #
n
t
háp Hà N
ộ
g
C).
a
ng cot %
\
à
i toán thá
p
n

ộ
i như sau:

\
n", A, C),
p
Hà Nội

Trang 24

2.2. Bài toán Tính giai thừa
Như đã trình bày ở trên, Visual Prolog hỗ trợ chạy chương trình ở hai chế độ
(console và GUI), ngoài ra, nó còn hỗ trợ người lập trình thực hiện các chức năng như các
ngôn ngữ khác, đó là các luồng nhập, xuất dữ liệu, tương tác người dùng. Sau đây là một
ví dụ về chương trình tính giai thừa của một số nguyên mà hàm tính giai thừa được định
nghĩa dưới dạng một vị từ, và s
ử dụng kỹ thuật đệ quy cho vị từ này. Vị từ tính giai thừa
được khai báo như sau:
predicates
giaithua:(integer N,integer F) procedure(i,o).
N: số nguyên cần tính giai thừa
F: chứa kết quả
Ở đây, vị từ giai thừa có mode là procedure và (i,o) để chỉ định là đối thứ nhất (N) là
input và đối thứ hai (F) là output.
Phần thân của vị từ để thực hiện tính giai thừa như sau:
clauses
giaithua(1,1) :- !.
giaithua(N, F) :-
N1 = N - 1,
giaithua(N1, F1),
F = N * F1.
Trong luật thứ nhất cho biết giai thừa c
ủa 1 là 1. Luật thứ hai sẽ tính N giai thừa với

lời gọi đệ quy giaithua(N1,F1) và kết quả của F là N*F1, nghĩa là giá trị hiện tại của N
nhân với kết quả giai thừa của N-1 (N1).
Đoạn chương trình sau khi thực thi sẽ cho phép người dùng nhập vào một số nguyên
và gọi tới vị từ giaithua để tính giai thừa và in ra kết quả. Trong Visual Prolog, đoạn
chương trình thực hiện công việc này là vị từ run() được đị
nh nghĩa như sau:
clauses
run():-












K

2.3.
B
B
các d
ữ
conso
l
stdIO:

hasdo
m
N = st
N <>
0
main:
:
stdIO:
stdIO:
_ = st
d
run().
run().
K
hi chạy c
h
B
ài toán gi
B
ài toán n
à
ữ
kiện về c
l
e::init(),
:write("Nh
a
m
ain(integ
e

dIO::read(
)
0
, !,
giaithua(N
:write("Gi
a
:nl,
d
IO::readc
h
h
ương trìn
h
Hình 3
a
hệ
à
y nói về c
á
ác mối liê
n
a
p 1 so (ke
t
e
r, N),
)
,
, F),

a
i thua cua
"
h
ar(),
h
, thu được
:
K
ết quả c
h
á
c mối qua
n
n
hệ này, n
g
Trang 25
t
thuc, nha
p
"
,N," la ",
F
kết quả nh
ư
h
ạy chươn
g
n

hệ trong
g
g
ười dùng
c
p
0) -> "),
F
),
ư
hình sau:
g
t
r
ình tính
g
ia đình n
h
c
ó thể đặt
r
giai thừa
h
ư cha mẹ,
r
a câu hỏi
a
ông bà, tổ
t
a

i là cha m
ẹ

t
iên. Từ
ẹ
của X,