BỘ GIÁO DỤC VÀ ĐÀO TẠO
Trường Đại học Sư phạm Hà Nội 2
Khoa Công Nghệ Thông Tin

Môn: Trí tuệ nhân tạo
Đề tài: Tìm hiểu ngôn ngữ Prolog và giải bài toán người nông dân qua
sông bằng thuật toán BFS
Nhóm thực hiện: Nhóm 6
Lớp: K38 - Công nghệ thông tin
Hà Nội, ngày 19 – 9 - 2014
1
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
Mục Lục
I. Giới thiệu ngôn ngữ lập trình Prolog
1. Prolog là ngôn ngữ lập trình logic
Prolog là từ viết tắt của 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 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á
bài toán liên quan đến các đối tượng (Object) và mối quan hệ (Relation) giữa
chúng.
Ngôn ngữ Prolog là ngôn ngữ lập trình trên cơ sở toán học logic, được thiết
kế đề giải quyết các vấn đề liên quan đến trí tuệ nhân tạo. Nguyên lý lập trình
logic dựa trên các mệnh đề Horn. Một mệnh đề Horn biểu diễn một sự kiện hay
2

Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
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í dụ: Mệnh đề Horn:
1. Nếu một người già mà (và) khôn ngoan thì người đó hạnh phúc.
2. Jim là người hạnh phúc.
3. Nếu X là cha mẹ của Y và Y là cha mẹ của Z thì X là ông của Z.
Trong các mệnh đề Horn ở trên thì mệnh đề 1, 3 được gọi là 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 logic
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. Người sử dụng gọi chạy một chương trình logic
bằng cách đặt câu hỏi (query/ question) truy vấn trên cở sở dữ liệu này.
2. Cú pháp Prolog
2.1. 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ừ.
a. Vị từ - định nghĩa vấn đề trong Prolog
- Vị từ là những kiến thức mà người lập trình cần cung cấp cho chương
trình.
- Vị từ có thể được xem là các hàm nhưng giá trị trả về chỉ là các giá trị
chân lý đúng (true) hoặc sai (fail).
- Một vị từ có thể có các đối là các nguyên logic (logic atom).
b. Mệnh đề - cách giải thích vấn đề trong Prolog
- Các khái niệm được mô tả qua các vị từ sẽ được giải thích bằng các
mệnh đề.
- Mỗi nguyên tử 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à
3

Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
hạng sơ cấp (Elementary tern) 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ụ:
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.
• 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)
II. Cú pháp và ngữ nghĩa của các chương trình Prolog
Cú pháp gồm 4 đoạn cơ bản sau: domains, predicates, clause, goal
4
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
1. Domains : là nơi để người lập trình định nghĩa những tập hợp mới
( hoặc đặt tên lại)

- Nơi tạo tập hợp mới có cùng kiểu dữ liệu với tập hợp sẵn có
Ví dụ:
Domains
Tên= symbol
Tuổi= integer
Nghề nghiệp = symbol
- Tạo tập hợp là tích các tập hợp
Ví dụ:
Domains
Ấn phẩm = Tạp chí (symbol, symbol)
Tiểu sử = lý lịch(symbol, integer,symbl,symbol)
- Tạo tập hợp là hội các tập hợp
Ví dụ:
Domains
Tên = symbol
Tài liệu = Book(tên,tên) or Magazine(tên,tên)
Dấu = âm; dương; kýsố(integer)
2. Predicates: là phàn khai báo các quan hệ giữa các domains
- Tạo quan hệ giữa các tập hợp
Ví dụ:
Domains
Tên= symbol
Tuổi= integer
5
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
Nghề nghiệp = symbol
Predicates
Lý lịch(tên, tuổi, nghề nghiệp)
- Tạo quan hệ trống

Ví dụ:
Predicates
Repeat()
Không màu
Repeat và không màu là tên của hai quan hệ . Tập hợp mà nó quan hệ
là tập trống. Quan hệ Repeat() còn có thể viết là Repeat. Quan hệ
không màu có thể viết là không màu ()
3. Clauses: là phần định nghĩa các quan hệ đã khai báo trong phần
predicates
- Biến và hằng
Turbo Prolog qui định biến có ký tự bắt đầu là ký tự in (uppercase) hoặc ký
tự gạch dưới (underscore). Hằng có ký tự bắt đầu là ký tự thường
(lowercase).
Ví dụ:
Minh, X, Người, _minh,_x,…là 5 biến.
Minh,x,người,…là 3 hằng
- Fact
Fact là một quan hệ trên các tập hợp đã xác định (có sẵn hoặc đã được xác
định trong Domains)
Đây là cách xác định tập hợp bằng liệt kê
Ví dụ:
Predicates
Chơi(symbol,symbol)
6
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
Biết(symbol, symbol)
Clauses
Chơi(sơn,piano)
Chơi(tân,keyboard)

Biết (kính, điêu khắc)
- Rule
Rule là quan hệ được định nghĩ từ nhiều quan hệ khác.
Rule có dạng của câu điều kiện, nghĩa là gồm nguyên nhân và hậu quả
(nguyên nhân -> hậu quả). Tuy nhiên Rule là câu điều kiện được trình bày theo
dạng thức : Hậu quả  nguyên nhân.
Các dạng sau đây tương đương:
Hậu quả <- nguyên nhân
Hậu quả if nguyên nhân
Hậu quả :- nguyên nhân
Do đó Fact có thể được xem là một loại rule đặc biệt – rule không có điều kiện
Nếu mệnh đề nguyên nhân gồm 3 mệnh đề nguyên nhân ngnh1, ngnh2, ngnh3 kết
hợp lại thì được biểu diễn như sau:
Nguyên nhân = Ngnh1 and Ngnh2 and Ngnh3.
Hoặc
Nguyên nhân = Ngnh1, Ngnh2, Ngnh3.
Ví dụ:
Predicates
Chơi(symbol, symbol) /*định nghĩa ở trên*/
Biết(symbol, symbol) /*định nghĩa ở trên*/
Clauses
Đa năng(X):-Biết (X,Y), chơi(X,Z)
7
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
Một học sinh X đa năng nếu biết ít nhất một môn nghệ thuật Y và chơi được một
môn thể thao Z
Nhận xét:
Một predicates được định nghĩa trong clauses bằng nhiều fact hoặc nhiều rule hoặc
kết hợp vừa fact vừa rule

4. Goal
- Goal là một nơi đặt câu hỏi với hệ thống và hệ thống sẽ cho câu trả lời
- Goal gồm một hay nhiều predicates cùng với thông số. Nếu goal gồm nhiều
thành phần thì mỗi thành phần được gọi là subgoal
III. Cấu trúc dữ liệu, danh sách, các phép toán số học
1. Cách biểu diễn một danh sách
- Danh sách là dãy các phần tử cùng kiểu
- Danh sách là kiểu cấu trúc dữ liệu đượ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 là một dãy bất kỳ các đối tượng. Khác với
kiểu dữ liệu tập hợp, các đối tượng của danh sách có thể trùng nhau (xuất
hiện nhiề lần) và mỗi vị trí xuất hiện của đối tượng đều có ý nghĩa.
ví dụ: list=integer*.
[1,2,3,4] là list
- Kí hiệu * biểu hiện cho danh sách. List là kiểu dữ liệu danh sách có phần tử
thuộc kiểu integer
- Cấu trúc của 1 danh sách, gồm 2 phần:
Phần đầu: là phần tử đầu tiên của danh sách
Phần đuôi là danh sách các phần tử còn lại của danh sách
Chú ý: danh sách rỗng biểu diễn là [] và lúc đó không có đầu danh sách
- Mô tả danh sách theo 2 cách:
Liệt kê các phần tử của danh sách. VD [1,2,3,4]
Mô tả phần đầu và đuôi của ds, ngăn cách bởi dấu “|”. VD: [1|[2,3,4]]
8
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
2. Các thao tác trên danh sách
- Chiều dài danh sách
length(L,Kq): chiều dài danh sách L
- Quan hệ thành viên:
member(X,L): X có phải là thành viên của L?

- Nôi danh sách:
conc(L1,L2,L3):nối L1 và L2 thành L3
- Thêm 1 phần tử vào danh sách
add(X,L,[X|L]).
- Xóa 1 phần tử ra khỏi danh sách
del(X,L,L1).
- Thêm 1 phần tử và bất kì chỗ nào
insert(X,L,L1):-del(X,L1,L).
3. Các phép toán số học
Phép gán: bien is bieu_thuc.
Các hàm chuẩn
- abs(x): cho giá trị tuyệt đối
- cos(x), sin(x), tan(x), arctan(x), exp(x), ln(x), log(x), sqrt(x).
- round(x): đối số là thực, kết quả là số nguyên do x được làm tròn
9
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
- Biểu thức số học được tạo thành từ các số, các biến, các phép toán số học
và ta phải sử dụng phép toán “is”: biến is biểu thức
- So sánh: <, =<, =:=, =\=, >,>=, =
Khác nhau giữa “=” và “=:=”
= là phép hợp nhất
=:= là phép so sánh giá trị
IV. Sự đệ qui, cơ chế quay lui và kĩ thuật nhát cắt
1. Đệ qui
Tương tự ngôn ngữ lập trình mệnh lệnh, thủ tục đệ qui trong Prolog phải
thỏa mãn 3 điều kiện:
- một khởi động quá trình lặp
- một sơ đồ lặp lại chính nó
-một điều kiện dừng

2. Quay lui và cơ chế tìm lời giải
- so khớp
- 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
sự kiện và luật trong chương trình
- thực thi tiếp các luật
- thực thi thành công thì các biến ở phần câu hỏi đã ở trạng thái có lời giải
3. Kĩ thuật nhát cắt
- Prolog sử dụng kĩ thuật nhát cắt để kiểm soát quay lui hay cấm quay lui
- Ta phải cẩn thận trong việc sử dụng nhát cắt vì nó có thể thay đổi hoàn toàn ý
nghĩa của chương trình
Ví dụ:p:-a,b.
p:-c.
- nghĩa khai báo tương ứng là p đúng khi cả a và b đều đúng hoặc c đúng.
- biểu thức logic là
p<=>(a^b)vc
10
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
- nghĩa khai báo không đúng nữa khi ta thêm nhát cắt vào mệnh đề 1
p:-a,!,b.
p:-c.
- biểu thức logic tương ứng là
p<=>(a^b)v(-a^c)
Nếu ta đảo thứ tự 2 mệnh đề
p:-c.
p:-a,!,b.
Thì biểu thức logic ko thay đổi
p<=>c v (a^b)
- Vị từ fail
- fail là vị từ của Prolog là luôn luôn thất bại

VD thich(lan,X):-toan(X),!,fail.
- nhát cắt và fail kết hợp cho định nghĩa:
+ phép phủ định
+ phép so sánh khác nhau
- So sánh khác nhau: là vị từ thất bại khi 2 đối của nó không thể hợp nhất
được
VD: X/=X:-!,fail.
X/=Y.
?-a/=a.
No
?-a/=b.
Yes
- Phép phủ định: phép phủ định 1 vị từ thành công nếu vị từ đó thất bại và
ngược lại
11
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
- với F là 1 vị từ. PPĐ kí hiệu là not(F)
- chứng minh not(F) = cách CM F thất bại
- not(F) nghĩa là F ko chứng minh được chứ không phải F sai.
/
V. Thuật toán
Bài toán: Một người nông dân có một con trâu, một con hổ và một bó ở bên bờ
sông. Ông ta muốn tất cả cùng sang bờ bên kia. Người nông dân chỉ có một chiếc
thuyền và thuyền ngoài người nông dân chỉ chở thêm được một trong ba vật trên.
Không được chỉ để có con trâu và con hổ cùng ở bên bờ sông vì hổ có thể ăn thịt
trâu, tương tự đối với con trâu và bó cỏ. Làm thế nào để tất cả cùng qua sông?
Giải quyết bài toán.
Ý tường thuật toán:
Lần 1: chở trâu qua trước (còn hổ và cỏ ở lại vì hổ không ăn cỏ)

Lần 2: chở hổ qua nhưng khi chở hổ qua thì người nông dân phải chở trâu về
lại bên kia bờ (nếu không trâu sẽ bị hổ ăn)
Lần 3: chở cỏ qua để trâu lại.
Lần 4: quay lại chở trâu qua.
12
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
Không gian trạng thái:
Trạng thái Bờ sông bên này Bờ sông bên kia
1 Người, hổ, trâu, bó cỏ
2 Người, hổ, trâu Bó cỏ
3 Người, hổ, bó cỏ Trâu
4 Người, trâu, bó cỏ Hổ
5 Người, trâu Hổ, bó cỏ
6 Hổ, bó cỏ Người, trâu
7 Hổ Người, trâu, bó cỏ
8 Trâu Người, hổ, bó cỏ
9 Bó cỏ Người, hổ, trâu
10 Người, hổ, trâu, bó cỏ
Trạng thái 1 là trạng thái bắt đầu và trạng thái 10 là trạng thái kết thúc mà
chúng ta cần đạt được. Ngưởi nông dân mỗi lần chèo thuyền sẽ dẫn tới sự thay đổi
một trạng thái. Bước thứ nhất, người mang một thứ qua sông, bờ sông bên này chỉ
còn lại hai thứ (trạng thái 5 + 6), nhưng chỉ có thể là trạng thái 6, tức là người chở
trâu qua sông. Bước thứ hai người nông dân sẽ chèo thuyền quay lại, tức là thể
hiện trạng thái thứ 3. Bước thứ ba, người lại chở một vật qua sông, ở bờ sông bên
kia sẽ xuất hiện hai khả năng (tức là trạng thái 7 và 9), cũng tức là có hai phương
án. Ta xét phương án một, người chở bó cỏ qua sông (tức trạng thái 7). Bước thứ 4,
người không thể bơi thuyền không lại được, vì trâu sẽ ăn hết cỏ, cho nên phải chở
một thứ nào đó quay lại, đương nhiên sẽ không phải là cỏ vì như vậy sẽ giống như
viễ hủy bỏ bước 3. Do vậy, người ta sẽ chở trâu quay lại và trở lại trong trạng thái

thứ 2. Bước thứ 5, người chở hổ qua sông và để dê ở lại như vậy sẽ xuất hiện trạng
thái thứ 8. Bước thứ 6, lần này người chèo thuyền không trở lại bởi bờ bên này hổ
sẽ không ăn cỏ (tức trạng thái thứ 5). Bước 7, người chở trâu qua sông. Công việc
hoàn tất.
Thuật toán:
#include <stdio.h>
int check_bosong(int A[])
{
13
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
int t = 0;
if(A[1] ==2&&A[2]==3&&A[0]!=1) {
printf(“ho an thit trau!”);
t=1;
} else if(A[2] ==3&&A[3]==4&&A[0]!=1) {
printf(“trau an co!”);
t=1;
} else if(A[2] ==-3&&A[3]==-4&&A[0]!=-1) {
printf(“trau an co!”);
t=1;
}
return t;
}
void swap_vat(int i, int A[], int B[]) {
int temp;
temp = A[i];
A[i]=B[i];
B[i]=temp;
}

void swap_nguoi(int A[], int B[]) {
int temp;
temp = A[0];
A[0]=B[0];
B[0]=temp;
}
void dichuyen(int i, int A[], int B[]) Ơ
14
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
swap_nguoi(A, B);
swap_vat(I, A, B);
if(check_bosong(A)==1) {
printf(“\n Game over!\n”);
exit(0);
}
If(A[0]==-1&&A[1]==-2&&A[2]==-3&&A[3]==-4) {
Printf(“\n qua song!\n”);
Printf(“\n Chuc mung!\n”);
Exit(0);
}}
Void main() {
Printf(“\t\t Nguoi Nong Dan Qua Song \n”);
Int i, A[]={1,2,3,4}, B[]={-1,-2,-3,-4};
Int t=0;
While(t>=0) {
Printf(“\n\t0. Nguoi\t1.Ho\t2.Trau\3.bo co\n”);
Printf(“hay chon so tuong ung voi luot di: “);
Scant(“%d”, &i);
If(i==0) {

Swap_nguoi(A,B);
If(check_bosong(A)==1) {
Printf(“\nGame over!\n”);
Exit(0);
}}
Else if((A[0]==1&&A[i]>0)||(A[0]==-1&&A[i]<0))
15
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO
Dichuyen(I,A,B);
Else {
Printf(“chac la ban quen gi roi!”);
Printf(“\nlai nhe!\n”)’
}}}
16
Nhóm 6: Vũ Thị Ánh Linh – Nguyễn Văn Khánh
BÁO CÁO TRÍ TUỆ NHÂN TẠO