BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN ĐÀO BÍCH GIANG

T×m hiÓu vÒ lËp luËn suy diÔn
trong lËp tr×nh logic pháng ®o¸n

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Huế, 2015


MỤC LỤC
Trang phụ bìa
Lời cam đoan
Lời cảm ơn
Danh mục các thuật ngữ
Danh mục các ký hiệu
Các chữ viết tắt
Danh mục các hình vẽ
MỞ ĐẦU ........................................................................................................... 1
Chương 1. TỔNG QUAN VỀ CHƯƠNG TRÌNH LOGIC .............................. 3
1.1. Ngôn ngữ bậc nhất ..................................................................................... 3
1.2. Chương trình logic ..................................................................................... 5
1.2.1. Chương trình logic xác định.................................................................... 5
1.2.2. Chương trình logic thông thường .......................................................... 11

1.3. Tiểu kết chương 1..................................................................................... 15
Chương 2. CHƯƠNG TRÌNH LOGIC PHỎNG ĐOÁN ............................... 16
2.1. Giới thiệu về lập trình logic phỏng đoán ................................................. 16
2.2. Tính toán phỏng đoán trong lập trình logic.............................................. 17
2.2.1. Thủ tục hợp giải SLD đối với chương trình logic xác định .................. 17
2.2.2. Thủ tục hợp giải SLDNF đối với chương trình logic thông thường ..... 24
2.3. Cú pháp và ngữ nghĩa của chương trình logic phỏng đoán ..................... 27
2.3.1. Cú pháp chương trình logic phỏng đoán ............................................... 27
2.3.2. Ngữ nghĩa chương trình logic phỏng đoán ........................................... 30
2.4. Tiểu kết chương 2..................................................................................... 32
Chương 3. PHƯƠNG PHÁP TÍNH TOÁN PHỎNG ĐOÁN ........................ 33
3.1. Thủ tục chứng minh phỏng đoán ............................................................. 33
3.1.1. Thủ tục chứng minh phỏng đoán EK .................................................... 33
3.1.2. Thủ tục chứng minh phỏng đoán KM ................................................... 39


3.2. Cài đặt và thực thi một số chương trình logic phỏng đoán
bằng SMODELS ..................................................................................... 42
3.2.1. Giới thiệu hệ thống SMODELS ............................................................ 42
3.2.2. Cài đặt và thực thi ................................................................................. 43
3.3. Tiểu kết chương 3..................................................................................... 52
PHẦN KẾT LUẬN ......................................................................................... 53
TÀI LIỆU THAM KHẢO ............................................................................... 54


DANH MỤC CÁC THUẬT NGỮ
Chương trình logic

Logic program


Chương trình logic nền

Ground program

Chương trình logic phỏng đoán

Abductive logic program

Chương trình logic thông thường

Normal logic program

Chương trình logic xác định

Definite logic program

Cơ sở Herbrand

Herbrand base

Giả thiết thế giới đóng

Closed world assumption

Hạng thức

Term

Lập trình logic


Logic programming

Literal âm

Negative literal

Literal dương

Positive literal

Mô hình bền vững

Stable model

Mô hình cực tiểu

Minimal model

Mô hình nhỏ nhất

Least model

Ngữ nghĩa mô hình bền vững

Stable model semantics

Nguyên tố

Atom


Phép thế

Substitution

Phỏng đoán

Abductive

Quy tắc

Rule

Thể hiện

Interpretation

Toán tử hệ quả trực tiếp

The immediate consequence operator

Vị từ

Predicate

Vị từ phỏng đoán

Abducible predicate

Vũ trụ Herbrand


Herbrand universe


DANH MỤC CÁC KÝ HIỆU
BP

Cơ sở Herbrand của chương trình P

UP

Vũ trụ Herbrand của chương trình P

2 BP

Tập tất cả các tập con của cơ sở Herbrand BP

MP

Mô hình nhỏ nhất của P

TP

Toán tử hệ quả trực tiếp trên 2 BP


CÁC CHỮ VIẾT TẮT
ALP

Abductive logic programming


CWA

Closed World Assumption.

EK

Eshghi và Kowalski

FF

Finite Failure

KM

Kakas và Mancarella

NG

Negative Goal

PG

Positive Goal

SLD

Linear Selection resolution for Definite clauses

SLDNF


SLD - resolution with Negation as finite Failure


DANH MỤC CÁC HÌNH VẼ
Số hiệu hình vẽ

Tên hình vẽ

Trang

3.1

Tính câu trả lời cho ví dụ 3.1

35

3.2

Tính câu trả lời cho ví dụ 3.2

37

3.3

Tính câu trả lời cho ví dụ 3.3

38

3.4


Tính câu trả lời cho ví dụ 3.4

39

3.5

Tính câu trả lời cho ví dụ 3.5

41

3.6

Kiến trúc hệ thống SMODELS

43

3.7

Kết quả thực thi ví dụ 1.13 bằng hệ thống SMODELS

43

3.8

Kết quả thực thi ví dụ 1.14 bằng hệ thống SMODELS

44

3.9


Kết quả thực thi ví dụ 1.15 bằng hệ thống SMODELS

45

3.10

Kết quả thực thi ví dụ 1.16 bằng hệ thống SMODELS

45

3.11

Kết quả thực thi ∆1 = {b} bằng hệ thống SMODELS

46

3.12
3.13
3.14

Kết quả thực thi ∆2 = { nhỏ_con(Sang)}
bằng hệ thống SMODELS
Kết quả thực thi ∆3 = { cơ_bắp(Sang)}
bằng hệ thống SMODELS
Kết quả thực thi ∆1 = {chim_cánh_cụt(Kin)}
bằng hệ thống SMODELS

48
48
50


Kết quả thực thi ∆2 =
3.15

{chim_cánh_cụt_bất_thường(Kin)} bằng hệ thống

51

SMODELS
3.16

Kết quả thực thi ∆3 = {đà_điểu_lạ(Kin)}
bằng hệ thống SMODELS

51

Kết quả thực thi ∆8 =
3.17

{chim_cánh_cụt_bất_thường(Kin),
đà_điểu_lạ(Kin)} bằng hệ thống SMODELS

52


1

MỞ ĐẦU
Trong suốt những thập kỷ qua, lĩnh vực nghiên cứu về lập trình logic đã
được nhiều nhà khoa học quan tâm và không ngừng phát triển. Lập trình logic

chủ yếu dựa trên ý tưởng lập trình khai báo, ở đó các chương trình logic không
được tạo ra từ các câu lệnh cũng như từ các hàm mà được tạo ra chủ yếu dựa
trên tập các vị từ. Vì vậy, một chương trình logic được xem như là một lý thuyết
logic, có dạng là một tập các quy tắc liên quan đến giá trị đúng của một literal
(phần đầu của mệnh đề) đối với một tập các literal khác (phần thân của mệnh
đề).
Lập trình logic chủ yếu là lý luận suy diễn bằng các quy tắc. Tuy nhiên,
hiện nay lập trình logic đã bộc lộ những hạn chế nhất định và không thể giải
quyết đối với các bài toán phức tạp trong thực tế. Đã có nhiều công trình nghiên
cứu nhằm mở rộng lập trình logic, trong số đó – Lập trình logic phỏng đoán
(ALP - Abductive Logic Programming) là một hướng nghiên cứu được nhiều
nhà khoa học quan tâm [3], [5], [7], [8]. ALP được bắt nguồn từ sự phỏng đoán,
phỏng đoán là một hình thức suy luận để giải thích cho các quan sát, xuất phát
từ một cơ sở tri thức T và một quan sát Q để tìm các giải thích có thể cho Q dựa
theo một tập vị từ đặc biệt được gọi là các vị từ phỏng đoán.
ALP là sự kết hợp của lập trình logic và phỏng đoán, trong ALP hình
thành nên một cú pháp mới của chương trình logic, được định nghĩa bởi một bộ
ba <P, A, IC>, trong đó P là một chương trình logic thông thường, A là một tập
hợp các vị từ và được gọi là các vị từ phỏng đoán, IC là một tập các ràng buộc
toàn vẹn. ALP là một khuôn khổ biểu diễn tri thức cấp cao, cho phép giải quyết
các bài toán dựa trên lập luận phỏng đoán. ALP thường được dùng để giải quyết
các bài toán trong Chuẩn đoán, Lập kế hoạch, Xử lý ngôn ngữ tự nhiên và Học
máy,…


2

Luận văn nghiên cứu về lập luận suy diễn đối với chương trình logic
phỏng đoán. Những nội dung nghiên cứu của luận văn có ý nghĩa về mặt lý
thuyết cũng như ứng dụng trong thực tiễn.

Cấu trúc luận văn gồm phần mở đầu, ba chương nội dung, phần kết luận
và tài liệu tham khảo.
Chương 1 trình bày về ngôn ngữ logic bậc nhất, cú pháp và ngữ nghĩa
của chương trình logic. Trên cơ sở đó trình bày lập luận suy diễn trong lập
trình logic.
Chương 2 trình bày các phương pháp tính toán phỏng đoán trong lập trình
logic, bao gồm thủ tục SLD đối với chương trình logic xác định, thủ tục
SLDNF đối với chương trình logic có chứa ký hiệu phủ định. Cũng trong
chương 2, cú pháp và ngữ nghĩa của chương trình logic phỏng đoán được trình
bày chi tiết.
Chương 3 trình bày phương pháp để tính toán phỏng đoán đối với các
chương trình logic phỏng đoán và đồng thời trình bày việc cài đặt, thực thi một
số ví dụ minh họa về các chương trình logic phỏng đoán bằng phần mềm
SMODELS.
Phần kết luận nêu những kết quả đã đạt được và hướng phát triển của luận
văn.
Do thời gian có hạn và bản thân chỉ mới bước đầu nghiên cứu về lĩnh vực
này nên không thể tránh khỏi những thiếu sót, kính mong sự giúp đỡ và góp ý
thêm của quý Thầy, Cô và các bạn.


3

Chương 1
TỔNG QUAN VỀ CHƯƠNG TRÌNH LOGIC
Chương 1 trình bày về ngôn ngữ logic bậc nhất, cú pháp và ngữ nghĩa
của chương trình logic. Trên cơ sở đó trình bày lập luận suy diễn trong lập
trình logic.
1.1. Ngôn ngữ bậc nhất
Định nghĩa 1.1 (Bộ ký tự) Bộ ký tự bao gồm 8 lớp ký hiệu sau:

1. Hằng, thường ký hiệu là các chữ cái thường a, b, c,...
2. Biến, thường ký hiệu bởi các chữ cái in hoa X, Y, Z,...
3. Các ký hiệu hàm, thường ký hiệu bởi f, g, h,...
4. Các ký hiệu vị từ, thường ký hiệu bởi p, q, r,...
5. Các hằng vị từ: true, false.
6. Các ký hiệu kết nối:



(phủ định),  (tuyển),  (hội),  (suy ra), 

(tương đương).
7. Các ký hiệu lượng từ:  (với mọi),  (tồn tại).
8. Dấu ngoặc đơn trái (, dấu ngoặc đơn phải ), dấu phẩy ,.
Mỗi ký hiệu hàm, ký hiệu vị từ có kèm theo một số tự nhiên để chỉ số các
đối số tham gia cùng với ký hiệu hàm hoặc ký hiệu vị từ đó, gọi là ngôi của
chúng.
Định nghĩa 1.2 (Hạng thức) Gọi A là bộ ký tự. Hạng thức được định nghĩa đệ
qui như sau:
(i) Mỗi hằng c trong A là một hạng thức,
(ii) Mỗi biến V trong A là một hạng thức,
(iii) Nếu f là ký hiệu hàm n ngôi trong A và t1,..,tn là các hạng thức thì
f(t1,...,tn) là một hạng thức,
(iv) Hạng thức chỉ được sinh ra bởi các mệnh đề trên.


4

Một hằng được xem là ký hiệu hàm 0-ngôi. Hạng thức nền là hạng thức
không chứa biến.

Định nghĩa 1.3 (Nguyên tố) Một nguyên tố có dạng p(t1, t2, …, tn), trong đó p là
ký hiệu vị từ n-ngôi và các đối t1, t2, …, tn là các hạng thức. Nguyên tố nền là
nguyên tố không chứa biến.
Ví dụ 1.1 Xét nguyên tố father(Hung,Dung), trong đó vị từ 2 ngôi father chỉ
mối quan hệ bố con, hạng thức Hung, Dung là các hằng. Nguyên tố này có ý
nghĩa là Hung là bố của Dung. Nguyên tố này cũng là nguyên tố nền vì nó
không chứa biến.
Định nghĩa 1.4 (Literal) Literal là một nguyên tố (gọi là literal dương) hoặc phủ
định của nguyên tố (gọi là literal âm). Với p là một nguyên tố, literal âm của p
được ký hiệu  p.
Ví dụ 1.2 Xét nguyên tố father(Hung, Dung) ở ví dụ 1.1, father(Hung, Dung) là
literal dương và  father(Hung, Dung) là literal âm.
Định nghĩa 1.5 (Công thức) Công thức được định nghĩa đệ qui như sau:
(i) Mỗi nguyên tố là một công thức,
(ii) Các hằng vị từ true và false là các công thức,
(iii) Nếu E và F là các công thức thì:
(E  F),  (E), (E  F), (E  F), (E  F)
là các công thức,
(iv) Nếu E là công thức và X là một biến thì X ( E ), X ( E ) là các công
thức,
(v) Công thức chỉ được sinh ra bởi một số hữu hạn các mệnh đề trên.
Ví dụ 1.3 Xem công thức sau:
 X (  Y ((father(X,Y)  male(X)



child_of(Y,X)))

Trong ví dụ này thì male(X) là nguyên tố để chỉ X là nam và child_of(Y,X) để chỉ



5

Y là con của X và father(X,Y) là nguyên tố để chỉ X là bố (father) của Y. Công
thức trên có ý nghĩa nếu X là nam và Y là con của X thì X là bố của Y.
Ví dụ 1.4 Xét công thức sau:
X(công_dân(X)  sinh_ở_Mỹ(X))
Trong ví dụ này, công_dân(X) là nguyên tố để chỉ X là công dân và
sinh_ở_Mỹ(X) để chỉ X được sinh ra ở Mỹ. Công thức này có ý nghĩa nếu X
được sinh ra ở Mỹ thì X là công dân Mỹ.
Định nghĩa 1.6 (Ngôn ngữ bậc nhất) Một ngôn ngữ bậc nhất bao gồm một bộ
ký tự và những công thức được xây dựng trên bộ ký tự đó.
1.2. Chương trình logic
Trong phần này sẽ xem xét cú pháp và ngữ nghĩa của hai lớp chương trình
logic: chương trình logic xác định (definite logic program) và chương trình logic
thông thường (normal logic program).
1.2.1. Chương trình logic xác định
1.2.1.1. Cú pháp
Định nghĩa 1.7 (Mệnh đề xác định) Mệnh đề xác định là công thức có dạng:
X1 ... Xk (p  q1 ,..., qn)

(1)

trong đó n  0, p, qi là các nguyên tố, p được gọi là đầu và q1, ..., qn được gọi là
thân của mệnh đề, dấu phẩy ký hiệu thay cho phép hội (), X1 ... Xk là các biến
xuất hiện trong p, q1, ..., qn.
Ta thường viết mệnh đề (1) dưới dạng:
p  q1 ,..., qn

(2)


Ngữ nghĩa của mệnh đề (1) là: Nếu tất cả các nguyên tố qi là đúng thì p
cũng đúng.


6

Trong mệnh đề (1), nếu n = 0 thì (1) được gọi là mệnh đề đơn vị, nghĩa là
mệnh đề có dạng: p  , đó là mệnh đề với thân rỗng. Ngữ nghĩa của mệnh đề
đơn vị là với mọi phép thay thế các biến của p bởi các hằng thì p luôn luôn
đúng.
Định nghĩa 1.8 (Chương trình logic xác định) Chương trình logic xác định là
một tập hữu hạn khác rỗng các mệnh đề xác định.
Ví dụ 1.5 Cho chương trình logic xác định P gồm các mệnh đề:
r1 : even(0) 
r2 : even(s(s(X)))  even(X)
Trong chương trình này thì s là một hàm 1-ngôi, được xác định bởi s(X) =
X +1 với X  , nguyên tố even(X) để chỉ X là một số chẵn. Mệnh đề đơn vị r1
even(0) có ý nghĩa là 0 một số chẵn và r2 là mệnh đề với ý nghĩa là nếu X là số
chẵn thì s(s(X)) cũng là số chẵn.
Định nghĩa 1.9 (Vũ trụ/Cơ sở Herbrand) Cho P là chương trình logic xác định.
 Vũ trụ Herbrand của P, ký hiệu UP, là tập các hạng thức nền được xây
dựng từ các hằng và các ký hiệu hàm trong P.
 Cơ sở Herbrand của P, ký hiệu BP, là tập các nguyên tố nền được xây dựng
từ các ký hiệu vị từ trong P có đối là các hạng thức nền lấy từ vũ trụ
Herbrand UP.
Vũ trụ Herbrand, cơ sở Herbrand của chương trình logic xác định P luôn
luôn là những tập vô hạn nếu P có chứa ký hiệu hàm.
Ví dụ 1.6 Xét chương trình logic xác định P ở ví dụ 1.5:
Vũ trụ Herbrand của P là: UP = {0, s(0), s(s(0)), s(s(s(0))),...}

Cơ sở Herbrand của P là:
BP = {even(0), even(s(s(0)), even(s(s(s(0))),...}


7

Trong trường hợp chương trình logic xác định không chứa ký hiệu hàm
thì vũ trụ Herbrand, cơ sở Herbrand đều là những tập hữu hạn.
Ví dụ 1.7 Xét chương trình logic xác định P gồm các mệnh đề sau:
r1 : công_dân(X)  sinh_ở_Mỹ(X)
r2 : công_dân(X)  sinh_ngoài_Mỹ(X)

 cư_dân_Mỹ(X) 
nhập_tịch(X)

r3 : công_dân(X)  sinh_ngoài_Mỹ(X)



 mẹ(Y,X)

cư_dân_Mỹ(Y)



đăng_ký(X)

r4 : mẹ(Mary,John) 
r5 : công_dân(X) 
Vũ trụ Herbrand của P là:

UP={ Mary, John }
Cơ sở Herbrand của P là:
BP={ công_dân(Mary), công_dân(John), sinh_ở_Mỹ(Mary),
sinh_ở_Mỹ(John), sinh_ngoài_Mỹ(Mary),

sinh_ngoài_Mỹ(John),

cư_dân_Mỹ(Mary), cư_dân_Mỹ(John),
nhập_tịch(Mary), nhập_tịch(John), mẹ(Mary, Mary),
mẹ(Mary, John), mẹ(John, Mary), mẹ(John, John),
đăng_ký(Mary), đăng_ký(John)}
1.2.1.2. Ngữ nghĩa chương trình logic xác định
Định nghĩa 1.10 (Thể hiện Herbrand, mô hình Herbrand) Cho P là chương trình
logic xác định.
 Một thể hiện Herbrand của P là một tập con tùy ý của cơ sở Herbrand BP
của P.
 Một mô hình Herbrand của P là một thể hiện Herbrand I của P sao cho
mọi mệnh đề của P đều đúng trong thể hiện I.


8

 Mô hình Herbrand của P được gọi là mô hình nhỏ nhất nếu nó được bao
hàm trong mọi mô hình của P.
Ví dụ 1.8 Xét trở lại chương trình logic xác định P ở ví dụ 1.5:
r1 : even(0) 
r2 : even(s(s(X)))  even(X)
Xét các thể hiện Herbrand:
I1 = {even(0)}
I2 = {even(0), even(s(0))}

I3 = {even(sn(0)) | n  {0, 2, 4,…}}
I4 = BP
Thể hiện I1 không phải là mô hình của P vì mặc dù I1 là mô hình của mệnh đề
even(0) nhưng I1 không phải là mô hình của mệnh đề r2 vì tồn tại mệnh đề nền
even(s(s(0)))  even(0) của r2 mà I1 không phải là mô hình của mệnh đề nền
này. Tương tự, I2 cũng không phải là mô hình của P vì mệnh đề tồn tại mệnh đề
nền:
even(s(s(s(0))))  even(s(0))
của r2 mà I2 không phải là mô hình của nó. Tuy nhiên, I3 là mô hình của P. Ta có
I3 là mô hình của r1. I3 cũng là mô hình của r2. Thật vậy, xét mệnh đề:
even(s(s(t))))  even(t)
là một hiện hành nền nào đó của mệnh đề r2, trong đó t  UP. Rõ ràng mệnh đề
even(s(s(t)))  even(t) đúng vì even(t) và even(s(s(t)))) đều thuộc I3. Vậy I3 là mô
hình của P. Ta cũng có ngay I4 là mô hình của P.
Ví dụ 1.9 Cho chương trình logic xác định P gồm các mệnh đề:
r1 : proud(X)  parent(X,Y)  newborn(Y)
r2 : parent(X,Y)  father(X,Y)
r3 : parent(X,Y)  mother(X,Y)


9

r4 : father(Khoa,Mai) 
r5 : newborn(Mai) 
Xét một số thể hiện Herbrand của P:
I1 = {newborn(Khoa), proud(Khoa)}
I2 = {newborn(Mai), proud(Mai), parent(Khoa,Mai)}
I3 = {newborn(Mai), father(Khoa,Mai), parent(Khoa,Mai), proud(Khoa)}
I1 và I2 đều không phải là mô hình của P vì tồn tại mệnh đề father(Khoa,Mai)
của r4 không đúng trong I1 và I2. Tuy nhiên, I3 là mô hình của P vì mọi mệnh

đề của P đều đúng trong I3.
Định nghĩa 1.11 (Ngữ nghĩa chương trình logic xác định) Cho P là chương trình
logic xác định, ngữ nghĩa của P là mô hình nhỏ nhất của P, ký hiệu MP.
Mô hình nhỏ nhất MP có thể xây dựng bằng cách dùng toán tử hệ quả trực
tiếp. Ta có định nghĩa sau:
Định nghĩa 1.12 (Toán tử hệ quả trực tiếp) Cho P là chương trình logic xác
định. Ánh xạ TP: 2 BP  2 BP được xác định như sau: Với mỗi I  2 BP ,
TP(I) = { A  BP |  mệnh đề nền A  A1,…, An của P và {A1,…, An}  I }
trong đó 2 BP là tập các tập con của cơ sở Herbrand BP. TP được gọi là toán tử hệ
quả trực tiếp trên 2 BP .
Định lý 1.1 [2] Toán tử TP đơn điệu theo quan hệ bao hàm và có điểm bất động
nhỏ nhất. Hơn nữa, điểm bất động nhỏ nhất đó cũng chính là mô hình nhỏ nhất
của chương trình logic xác định P.
Định lý 1.2 [2] Cho P là chương trình logic xác định. Mô hình nhỏ nhất của P là
giới hạn của dãy TP  n ,n , ký hiệu TP  , trong đó:
TP  0 = , TP  (i + 1) = TP (TP  i)


10

Ví dụ 1.10 Xét chương trình logic P ở Ví dụ 1.5:
r1 : even(0) 
r2 : even(s(s(X)))  even(X)
Áp dụng Định lý 1.2 ở trên ta tính được:
Ta có:
TP  n = 
TP  1 = {even(0)}
TP  2 = {even((s(s(0))))}
…
TP   = {even(sn(0)) | n  {0, 2, 4,…}}

Ví dụ 1.11 Xét chương trình logic sau:
path(X,Y) ← edge(X,Y)
path(X,Y) ← edge(X,Z)  path(Z,Y)
edge(1,2), edge(2,3), edge(3,4), edge(4,5)
Mô hình nhỏ nhất (MP) của P được tìm qua các bước lặp sau:
I1 = 
I2 = Tp (I1) = {edge(1,2), edge(2,3), edge(3,4), edge(4,5)}
I3 = Tp (I2) = I2  {path(1,2), path(2,3), path(3,4), path(4,5)}
I4 = Tp (I3) = I3  {path(1,3), path(2,4), path(3,5)}
I5 = Tp (I4) = I4  {path(1,4), path(2,5)}
I6 = Tp (I5) = I5  {path(1,5)}
I7 = Tp (I6) = I6   = I6
Vậy mô hình nhỏ nhất của P chính là MP = I6.
1.2.1.3. Lập luận suy diễn trong chương trình logic xác định
Vấn đề ta quan tâm là làm thế nào xác định được các nguyên tố nền là hệ


11

quả logic (nghĩa là được suy diễn logic) từ các mệnh đề của chương trình logic
xác định đã cho. Điều này được thể hiện qua kết quả sau:
Định lý 1.3 [2] Mô hình nhỏ nhất MP của chương trình logic xác định P là tập
các nguyên tố nền mà là hệ quả logic của P. Nghĩa là:
MP = {A  BP | P A}
Đối với chương trình logic xác định, ta thường dùng giả thiết thế giới đóng
(CWA – Closed World Assumption) sau đây để kết luận về sự kiện phủ định:
nếu một nguyên tố nền A không thể suy diễn logic từ chương trình logic xác định
P thì  A là đúng. Vì vậy, từ định lý trên ta có thể kết luận về giá trị chân lý của
nguyên tố nền: nếu A  MP thì A được xem là đúng, ngoài ra A là sai. Điều này
có thể biểu diễn bởi mệnh đề suy diễn sau:

P A
(CWA)
A

Ví dụ 1.12 Xét chương trình logic ở ví dụ 1.11, tất cả các nguyên tố nền không
thuộc mô hình nhỏ nhất MP = {edge(1,2), edge(2,3), edge(3,4), edge(4,5),
path(1,2), path(2,3), path(3,4), path(4,5), path(1,3), path(2,4), path(3,5),
path(1,4), path(2,5)} đều được xem là sai, chẳng hạn path(2,1) là sai.
1.2.2. Chương trình logic thông thường
Các chương trình logic xác định biểu diễn tri thức dương, các mệnh đề
trong chương trình mô tả các đối tượng xác định và mối quan hệ giữa chúng.
Các quan hệ này được thể hiện rõ trong mô hình nhỏ nhất - chứa các nguyên tố
nền là hệ quả logic của chương trình. Đối với chương trình logic thông thường,
khi các mệnh đề có chứa phủ định ở thân thì ngữ nghĩa của nó trở nên phức tạp
hơn nhiều. Lúc này chương trình có thể không có mô hình nhỏ nhất nhưng tồn
tại nhiều mô hình cực tiểu.
Ví dụ 1.13 Chẳng hạn, xét chương trình logic P gồm các mệnh đề sau:


12

p(X)  r(X)   q(X)
q(X)  r(X)   p(X)
r(1) 
Chương trình này chỉ có hai mô hình cực tiểu là S1 = {q(1), r(1)}, S2 =
{p(1), r(1)} và không có mô hình nhỏ nhất vì S1  S2 và S 2  S1 .
1.2.2.1. Cú pháp và ngữ nghĩa
Định nghĩa 1.13 (Chương trình logic thông thường) Chương trình logic thông
thường là một tập hữu hạn khác rỗng các mệnh đề có dạng:
p  q1, ..., qn


(1)

trong đó n  0, p là nguyên tố, qi là các literal.
Từ đây về sau ta gọi chương trình logic thông thường là chương trình
logic.
Để giải quyết vấn đề ngữ nghĩa của chương trình logic thông thường (có
chứa phủ định), đã có nhiều tiếp cận khác nhau, trong đó thường sử dụng tiếp
cận ngữ nghĩa mô hình bền vững [4]. Việc xác định mô hình bền vững sẽ được
thực hiện nhờ vào một phép biến đổi, được gọi là phép biến đổi Gelfond –
Lifschitz. Ta có định nghĩa sau:
Định nghĩa 1.14 (Phép biến đổi Gelfond - Lifschitz) [4] Gọi ground(P) là
chương trình nhận được từ chương trình logic P bằng cách thay thế các biến
trong mọi mệnh đề của P bởi các hằng trong P. Đối với mọi thể hiện M của
ground(P), ký hiệu PM là chương trình nhận được từ ground(P) bằng cách loại
bỏ:
1. Các mệnh đề có literal âm  B trong thân của nó, với B  M.
2. Tất cả literal âm trong thân của các mệnh đề còn lại.
Rõ ràng PM là chương trình không có phủ định, nó là chương trình logic
xác định, vì vậy PM có mô hình nhỏ nhất.


13

Ví dụ 1.14 Cho P là chương trình logic:
ab
ba
cab
Bây giờ, P có hai mô hình bền vững: M1 = {a, c} và M2 = {b}.
M


Thu gọn P 1 là tập các quy tắc:
a
ca
và mô hình nhỏ nhất của nó chính là {a,c}.
Thu gọn P

M2

là tập quy tắc:

b
và mô hình nhỏ nhất của nó chính là {b}.
Tập M3 = {a, b, c} là một mô hình của P theo nghĩa thông thường, nhưng
M

nó không bền vững vì mô hình nhỏ nhất của P 3 là tập rỗng.
Ví dụ 1.15 Cho P là chương trình logic:
fly(X)  bird(X)   ab(X)
bird(tweety)
Chương trình ground(P) thu được từ P sau khi thay thế các đối của các vị
từ bằng hằng:
fly(tweety)  bird(tweety)   ab(tweety)
bird(tweety) 
Bây giờ, P có một mô hình bền vững: M = {fly(tweety), bird(tweety)}.
M
Thu gọn P là tập các quy tắc:

bird(tweety) 
fly(tweety)  bird(tweety)

và mô hình nhỏ nhất của nó chính là {fly(tweety), bird(tweety)}.


14

Định nghĩa 1.15 (Mô hình bền vững) Tập M các nguyên tố được gọi là mô hình
bền vững của chương trình logic P nếu M là mô hình nhỏ nhất của PM.
Định lý 1.4 [4] Cho P là chương trình logic. Mọi mô hình bền vững của P đều là
mô hình cực tiểu của P.
Các mô hình bền vững là sự tổng quát hóa ngữ nghĩa của chương trình
logic xác định, điều này được thể hiện bởi kết quả sau:
Định lý 1.5 [4] Đối với chương trình logic xác định thì mô hình bền vững chính
là mô hình nhỏ nhất của nó.
1.2.2.2. Lập luận suy diễn trong chương trình logic thông thường
Bởi vì một chương trình logic có thể có một hoặc nhiều hoặc không có
mô hình bền vững. Vấn đề đặt ra là cách thức suy luận từ P sẽ được xác định
như thế nào. Đối với một mô hình bền vững cụ thể, một nguyên tố nền a được
xem là đúng nếu a  M và sai nếu a  M. Điều này thường được mở rộng để
suy luận từ tất cả mô hình bền vững của P theo hai dạng đối ngẫu nhau sau đây:
 Lập luận bất chấp (Brave Reasoning): Một nguyên tố nền a là hệ quả bất
chấp (brave consequence) của P, ký hiệu ⊨b nếu a thuộc vào một mô hình
bền vững M nào đó của P.
 Lập luận thận trọng (Cautious Reasoning) Một nguyên tố nền a là hệ quả
thận trọng (brave consequence) của P, ký hiệu ⊨c nếu a thuộc mọi mô
hình bền vững M của P.
Ví dụ 1.16 Xem chương trình logic P:
p(a)
r(X)  p(X),  q(X)
P có 2 mô hình cực tiểu là M1 = {p(a), r(a)} và M2 = {p(a), q(a)} và chỉ có M1 là
mô hình bền vững của P. Lúc đó P ⊨b r(a) và P ⊨c r(a) vì r(a) đúng trong mọi

mô hình bền vững. Tuy nhiên với P’ = P  {q(a)} thì cả hai P’ ⊨b r(a) và P’ ⊨c


15

r(a) đều không thỏa mãn vì r(a) là sai trong mô hình bền vững duy nhất của
{p(a), q(a)} của P’.
1.3. Tiểu kết chương 1
Chương 1 đã trình bày cú pháp của chương trình logic xác định và chương
trình logic thông thường. Đối với chương trình logic xác định, ngữ nghĩa của nó
là mô hình nhỏ nhất, trong khi ngữ nghĩa mô hình bền vững được thiết lập cho
chương trình logic thông thường (có chứa phép phủ định). Việc lập luận suy
diễn trong các lớp chương trình này đã được trình bày chi tiết cùng với các ví dụ
minh họa. Trong chương 2 sẽ tiếp tục tìm hiểu vấn đề lập luận suy diễn trong
các chương trình logic phỏng đoán – một sự mở rộng của chương trình logic.


16

Chương 2
CHƯƠNG TRÌNH LOGIC PHỎNG ĐOÁN
Chương này trình bày về việc tính toán phỏng đoán trong các chương
trình logic, đồng thời trình bày về cú pháp và ngữ nghĩa của chương trình logic
phỏng đoán  một mở rộng của chương trình logic đã xét ở chương 1.
2.1. Giới thiệu về lập trình logic phỏng đoán
Phỏng đoán là một dạng suy luận dựa vào một số mệnh đề logic (còn gọi
là các quy tắc logic) và một quan sát cho trước nhằm mục đích tìm một giải
thích cho quan sát đó bằng cách sử dụng các quy tắc logic đã cho. Xem ví dụ sau
đây:
Ví dụ 2.1 Cho chương trình logic P gồm các quy tắc sau:

bị_cảm(X)  đau_đầu(X)  sốt_cao(X)
bị_cảm(X)  đi_mưa (X)
Giả sử ta có quan sát X bị cảm, nghĩa là bị_cảm(X) là đúng. Từ hai quy tắc
của P ta nhận thấy nguyên nhân X bị cảm có thể là do X đi ra ngoài bị mắc mưa
hoặc cũng có thể là do X bị sốt cao và đau đầu. Lúc này nếu ta có thêm ràng
buộc  đi_mưa (X), thì quy tắc thứ 2 không thỏa mãn ràng buộc này. Chính vì
vậy nguyên nhân X bị cảm ở đây là do X sốt cao và đau đầu vì nó thỏa mãn ràng
buộc  đi_mưa (X).
Trong lập luận phỏng đoán, các giải thích phù hợp với trạng thái của cơ
sở tri thức có thể trở nên không phù hợp với thông tin mới. Trong ví dụ trên lời
giải thích đi_mưa có thể hóa ra là sai lầm, và giải thích khác đau_đầu  sốt_cao
có thể là nguyên nhân thực sự cho quan sát đã cho. Sự tồn tại của nhiều nguyên
nhân là một đặc tính tổng quát của lập luận phỏng đoán và việc lựa chọn giải
thích “hợp lý hơn” là một vấn đề quan trọng.


17

Ví dụ 2.2 Cho chương trình logic P gồm các quy tắc sau:
Không_hiểu_bài(X)  nói_chuyện(X)  hiểu_sai(X)
Không_hiểu_bài(X)  chưa_giảng_kỹ(Y, X)
Không_hiểu_bài(X)  hiểu_sai(X)
Nguyên nhân X “không_hiểu_bài” có thể là do X “nói_chuyện” và
“hiểu_sai” ý người giảng trong lúc học hoặc cũng có thể là do Y
“chưa_giảng_kỹ” cho X. Ở đây, nếu ta có ràng buộc  nói_chuyện (X) nên quy
tắc đầu tiên không thỏa mãn ràng buộc toàn vẹn này. Chính vì vậy, nguyên nhân
X “không_hiểu_bài” ở đây là do Y “chưa_giảng_kỹ” cho X vì nó thỏa mãn ràng
buộc  nói_chuyện (X).
2.2. Tính toán phỏng đoán trong lập trình logic
Trong lập trình logic, phỏng đoán cũng có thể được giải thích bằng cách

sử dụng các thủ tục hợp giải SLD và SLDNF. Đối với chương trình logic xác
định, một quan sát Q có thể được giải thích bằng cách dùng thủ tục hợp giải
SLD, trong khi đối với chương trình logic thông thường, phỏng đoán cũng có
thể giải thích bằng thủ tục hợp giải SLDNF.
2.2.1. Thủ tục hợp giải SLD đối với chương trình logic xác định
Phần này trình bày về thủ tục hợp giải SLD [2], trong thủ tục hợp giải
SLD, phép thế đóng vai trò quan trọng, ta có định nghĩa sau:
Định nghĩa 2.1 (Đích) Đích là công thức có dạng:
 B1  ...  Bm

(m > 0)

trong đó Bi là các nguyên tố, i = 1, ..., m.
Người ta còn gọi đích là một ràng buộc toàn vẹn (hoặc ràng buộc).
Định nghĩa 2.2 (Phép thế) Một phép thế  là một ánh xạ từ tập các biến vào tập
các hạng thức sao cho tập tất cả các cặp Xi/ti là hữu hạn (trong đó Xi là biến, ti là


18

hạng thức), ký hiệu  = {X1/t1, ..., Xn/tn }, các biến Xi phân biệt nhau, ti là hạng
thức và Xi  ti, mỗi phần tử Xi/ti là ký hiệu của phép thay thế biến Xi với hạng
thức ti, i = 1,..., n. Phép thế  được gọi là phép thế nền nếu tất cả ti đều là hạng
thức nền.
Ví dụ 2.3 Cho nguyên tố p(f(X), Y) và phép thế 1 = {X/a, Y/b}. Lúc đó p(f(X),
Y) là nguyên tố p(f(a), b). Tương tự, nếu 2 = { X/a, Y/X } thì p(f(X), Y)2 =
p(f(a), X).
Định nghĩa 2.3 (Hợp hai phép thế) Giả sử ta có hai phép thế:
 = {X1/t1, X2/t2,...,Xn/tn}
 = {Y1/s1, Y2/s2,...,Ym/sm}

Hợp của hai phép thế  và , ký hiệu  là phép thế được nhận được từ tập:
{X1/t1,...,Xn/tn, Y1/s1,..., Ym/sm }
bằng cách loại bỏ trong tập này mọi phần tử Xi/ti mà Xi = ti (1  i  n) và loại
bỏ mọi phần tử Yj/sj mà Yj  {X1, X2..., Xn} (1  j  m).
Ví dụ 2.4 Cho hai phép thế  ={Y/f(X), Z/a} và  = {X/a}. Hợp của  và  là
phép thế  = {Y/ f(a), X/a, Z/a}.
Định nghĩa 2.4 Cho E và F là hai nguyên tố. Lúc đó:
(i) E và F gọi là hợp nhất được nếu tồn tại phép thế  sao cho E  F, lúc
đó  được gọi là phép hợp nhất của E và F.
(ii) Phép thế  gọi là tổng quát hơn phép thế  nếu tồn tại một phép thế  sao
cho  =.
(iii) Phép hợp nhất  của E và F được gọi là phép hợp nhất tổng quát nhất
của E và F nếu  tổng quát hơn mọi phép hợp nhất khác của E và F, ký
hiệu mgu(E,F).