BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THỊ HUYÊN

TÌM HIỂU CHƯƠNG TRÌNH
LOGIC ƯU TIÊN VÀ ỨNG DỤNG
ĐỐI VỚI VIỆC LẬP LUẬ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
ĐỊNH HƯỚNG NGHIÊN CỨU

NGƯỜI HƯỚNG DẪN KHOA HỌC

PGS.TS. TRƯƠNG CÔNG TUẤN


Thừa Thiên Huế, 2018


LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này là công trình nghiên cứu của
cá nhân tôi. Tất cả số liệu, kết quả nghiên cứu trong luận văn là
trung thực, chưa được người khác công bố trong bất cứ một công
trình nghiên cứu nào.
Học viên

Nguyễn Thị Huyên

3


LỜI CẢM ƠN
Trước tiên tôi xin gửi lời cảm ơn đặc biệt tới PGS.TS Trương
Công Tuấn, người đã định hướng đề tài và tận tình hướng dẫn, chỉ bảo,
động viên tôi trong suốt quá trình thực hiện luận văn thạc sỹ.
Tôi xin chân thành biết ơn tất cả thầy, cô trong khoa của trường
Đại học khoa học – Đại học Huế đã truyền đạt cho tôi những kiến thức
quý báu về các vấn đề hiện đại của lập trình logic và ngành khoa học
máy tính.
Bản luận văn này được hoàn thành với sự động viên của thầy
hướng dẫn và của các bạn lớp Cao học Khoa học Máy tính năm 2016 –
2018. Tôi xin bày tỏ lòng cảm ơn chân thành đến thầy và các bạn đã
dành nhiều thời gian của mình để trao đổi giúp đỡ tôi khi tôi gặp khó
khăn trong suốt thời gian thực hiện luận văn này.

Học viên
Nguyễn Thị Huyên

4


MỤC LỤC
LỜI CAM ĐOAN......................................................................................................
LỜI CẢM ƠN............................................................................................................
MỤC LỤC..................................................................................................................

DANH MỤC CÁC HÌNH..........................................................................................
DANH MỤC CÁC CHỮ VIẾT TẮT........................................................................

5


DANH MỤC CÁC HÌNH

6


DANH MỤC CÁC CHỮ VIẾT TẮT
AI

Trí tuệ nhân tạo (Artificial Intelligence)

ALP

Chương trình logic phỏng đoán (Abductive Logic Program)

FOL

Ngôn ngữ bậc nhất (First Ordered Language)

PLP

Chương trình logic ưu tiên (Prioritized Logic Program)

PDLP


Chương trình logic ưu tiên dạng tuyển (Prioritized Disjunctive Logic Program)

SLD

Phép hợp giải

7


MỞ ĐẦU
Hiện nay, việc nghiên cứu lập trình logic đã đạt được nhiều thành tựu quan
trọng cả về lý thuyết và ứng dụng và được áp dụng rộng rãi để biểu diễn tri thức và
xử lý thông tin trong nhiều lĩnh vực. 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ừ. Tuy nhiên hiện nay
đã phát sinh một số vấn đề trong việc biểu diễn tri thức và lập luận bằng các chương
trình logic đối với các bài toán phức tạp trong thực tế. Đã có nhiều nghiên cứu
nhằm mở rộng chương trình logic bằng cách bổ sung các dạng phủ định cổ điển,
phủ định mặc định, các phép ưu tiên hay phép tuyển.
Lập luận với các ưu tiên là một vấn đề đang được quan tâm trong biểu diễn
tri thức. Nhiều kỹ thuật lập luận ưu tiên đã được phát triển trong lĩnh vực trí tuệ
nhân tạo (AI). Trong AI một số hệ thống lập luận ưu tiên đã được phát triển như
phân loại theo thứ tự ưu tiên hoặc lập luận ưu tiên mặc định. Tuy nhiên lập trình
logic thiếu cơ chế rõ ràng để biểu diễn các tính ưu tiên trong chương trình. Ưu tiên
trong lập trình logic thường được thể hiện ở chương trình logic phân tầng, các ưu
tiên trong các chương trình phân tầng được xác định bởi cú pháp của một chương
trình, và ứng dụng của chúng chỉ giới hạn trong các chương trình có cấu trúc phân
tầng đơn.
Trong những năm gần đây, việc nghiên cứu về chương trình ưu tiên đã được
nhiều người quan tâm và đã có nhiều công trình nghiên cứu có giá trị. Có hai tiếp

cận được đề xuất trong thời gian gần đây, trong [9], [10] các tác giả đã nghiên cứu
tính chất ưu tiên giữa các quy tắc trong chương trình và đã đưa ra nhiều tính chất
quan trọng. Mặt khác, trong [2], [7], [8] các tác giả nghiên cứu tính ưu tiên giữa các
vị từ trong chương trình. Chương trình logic ưu tiên biểu diễn tri thức tự nhiên hơn
các chương trình phân tầng và có thể áp dụng trong nhiều dạng lập luận khác nhau
như lập luận phỏng đoán, lập luận mặc định,… Việc áp dụng chương trình logic ưu
tiên đối với vấn đề lập luận cũng đã được nghiên cứu trong [3], [4], [6], [7].

8


Luận văn nghiên cứu về “Tìm hiểu chương trình logic ưu tiên và ứng dụng đối
với việc lập luậ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, giải quyết một số bài toán thuộc các lĩnh
vực khác nhau trong thực tế.
Cấu trúc luận văn bao 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 các khái niệm cơ sở, cú pháp, các cách tiếp cận ngữ nghĩa
của chương trình logic. Đây là kiến thức cơ sở làm tiền đề để nghiên cứu các
chương tiếp theo.
Chương 2 tìm hiểu về chương trình logic ưu tiên - là sự mở rộng của chương
trình logic bằng cách thêm vào các ưu tiên. Các ưu tiên được thêm vào gồm hai
dạng đó là ưu tiên giữa các quy tắc và ưu tiên giữa các vị từ.
Chương 3 trình bày việc áp dụng chương trình logic ưu tiên để lập luận trong
chương trình logic phỏng đoán; đồng thời thực hiện cài đặt và thực thi một số bài
toán minh họa các chương trình logic ưu tiên bằng hệ thống DLV và phần mềm
ECLIPSE.
Phần kết luận trình bày những kết quả đã đạt được và hướng phát triển của
luận văn.


9


Chương 1
TỔNG QUAN VỀ CHƯƠNG TRÌNH LOGIC
Chương 1 trình bày các khái niệm cơ sở của chương trình logic. Hai lớp
chương trình logic được xem xét là chương trình logic xác định và chương trình
logic thông thường. Ngữ nghĩa của các lớp chương trình này cùng với mối quan hệ
của chúng được trình bày chi tiết. Đây là những kiến thức cơ sở, làm tiền đề cho
việc nghiên cứu ở các chương tiếp theo.
1.1. MỘT SỐ KHÁI NIỆM CƠ SỞ
Chương trình logic có nền tảng là ngôn ngữ bậc nhất (FOL), trong phần này
chỉ nêu một số khái niệm cơ sở của FOL.
Định nghĩa 1.1 (Bộ ký tự). Bộ ký tự bao gồm các lớp ký hiệu sau:
1.
2.
3.
4.
5.
6.
7.
8.

Hằng, thường ký hiệu là các chữ cái thường a, b, c,...
Biến, thường ký hiệu bởi các chữ cái in hoa X, Y, Z,...
Các ký hiệu hàm, thường ký hiệu bởi f, g, h, ...
Các ký hiệu vị từ, thường ký hiệu bởi p, q, r, ...
Các hằng vị từ: true, false.
Các ký hiệu kết nối ¬(phủ định), ∨(tuyển), ∧(hội), ←(suy ra)
Các ký hiệu lượng từ: ∀(với mọi), ∃(tồn tại).

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 xác định để 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.
Trên cơ sở bộ ký tự đã cho, người ta đưa ra định nghĩa về hạng thức. Hạng
thức là yếu tố quan trọng của công thức logic, được xây dựng từ các hằng, biến,
hàm và được định nghĩa hình thức như sau:
Định nghĩa 1.2 (Hạng thức). Gọi A là bộ ký tự. Hạng thức được định nghĩa đệ
quy như sau:
(i)
(ii)

Mỗi hằng trong A là một hạng thức,
Mỗi biến trong A là một hạng thức,

10


(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.
Một hằng được xem là ký hiệu hàm 0-ngôi. Hằng và biến là các hạng thức
nguyên tố, 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,…,tn), trong đó p là ký
hiệu vị từ n-ngôi và các đối t1,...,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 Để chỉ mối quan hệ cha/con ta có thể định nghĩa nguyên tố father(X,Y),
trong đó vị từ father là vị từ 2-ngôi và father(X,Y) để chỉ X là cha của Y.
Định nghĩa 1.4 (Literal). Literal là một nguyên tố, gọi là literal dương và literal
âm là phủ định của nguyên tố.

Trong phần tiếp theo sẽ trình bày cú pháp và ngữ nghĩa của chương trình
logic xác định – đây là lớp chương trình logic đơn giản nhất.
1.2. CHƯƠNG TRÌNH LOGIC
Các chương trình logic cho phép mô hình hóa khá nhiều bài toán khác
nhau, 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.
1.2.1. Cú pháp
Định nghĩa 1.5 (Chương trình logic). Chương trình logic là một tập hữu hạn khác
rỗng các mệnh đề có dạng:
a ← b1,…,bm, not c1,…, not cn

(1)

trong đó n, m ≥ 0, a và bi, cj là các nguyên tố. Trong mệnh đề (1), nếu m = n = 0 thì
nó được gọi là mệnh đề đơn vị, nghĩa là mệnh đề có dạng: a ←, đó là mệnh đề với
thân rỗng, ký hiệu ← có thể không viết.

11


Chú ý rằng thân mệnh đề chứa các lietral phủ định not c1,…,not cn. Literal not
a sẽ được xem là sai nếu giá trị chân lý của a không được chứng minh một cách hữu
hạn thông qua phép hợp giải SLD. Vì vậy phủ định not còn được gọi là phủ định do
thất bại hoặc phủ định mặc định. Để ý rằng phép phủ định trong logic cổ điển, còn
gọi là phủ định mạnh, ký hiệu là ¬.
Định nghĩa 1.6 (Vũ trụ/Cơ sở). 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 vị từ trong P có đối là các hạng thức nền trong vũ trụ Herbrand UP.

Định nghĩa 1.7 (Thể hiện/Mô hình). Cho P là chương trình logic xác định.
Một thể hiện Herbrand (hoặc đơn giản là thể hiện) của P là một tập con tùy ý của
cơ sở Herbrand BP của P.
Một thể hiện I của P là mô hình của P nếu mọi mệnh đề của P là đúng theo thể hiện I.
Ví dụ 1.2. Xét chương trình logic P:
r1: sotunhien(0)
r2: sotunhien(ketiep(X)) ← sotunhien(X)
Trong chương trình logic này thì ketiep là ký hiệu hàm 1-ngôi và ketiep(X) = X+1
với X ∈ tập số tự nhiên N, nguyên tố sotunhien(X) để chỉ X là một nguyên tố tự
nhiên. Mệnh đề đơn vị r1 có ý nghĩa0 là một số tự nhiên và r2 là mệnh đề với ý
nghĩa nếu X là số tự nhiên thì ketiep(X) cũng là số tự nhiên.
Vũ trụ Herbrand của P là:
UP = {0, ketiep(0), ketiep(ketiep(0)), ketiep(ketiep(ketiep(0))),...}
Cơ sở Herbrand của P là:
BP = {sotunhien(0), sotunhien(ketiep(0)), sotunhien(ketiep(ketiep(0))),...}
Một số thể hiện Herbrand của P là:
12


I1 = {sotunhien(0)}
I2 = {sotunhien(0), sotunhien(ketiep(0))}
I3 = {sotunhien(ketiepn(0)) | n ∈ {0, 1, 2,…}}
I4 = BP
Rõ ràng I1 không phải là mô hình của P vì mặc dầu I1 là mô hình của mệnh đề
sotunhien(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 sotunhien(ketiep(0)) ← sotunhien(0) của r2 mà I1 không phải là mô hình của
mệnh đề nền này. Cũng vậy, 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:
sotunhien(ketiep(ketiep(0))) ← sotunhien(ketiep(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 đề:
sotunhien(ketiep(t)) ← sotunhien(t)
là một mệnh đề nền nào đó của mệnh đề r2, trong đó t∈UP. Rõ ràng mệnh đề
sotunhien(ketiep(t)) ← sotunhien(t) đúng vì sotunhien(t) và sotunhien(ketiep(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.
Định nghĩa 1.8 (Mệnh đề nền). Một mệnh đề nền của mệnh đề C là một mệnh đề C’
nhận được từ C bằng cách thay thế các biến trong C bởi các hạng thức nền trong vũ
trụ Herbrand UP. Ký hiệu ground(C) là tập tất cả mệnh đề nền của C và
đặt:ground(P) = .
Định nghĩa 1.9 (Mô hình cực tiểu/nhỏ nhất). Cho P là chương trình logic.
1. Thể hiện M của P là mô hình cực tiểu của P nếu không tồn tại tập con thực
sự N của M mà N là mô hình của P.
2. Thể hiện M của P là mô hình nhỏ nhất của P nếu M ⊆ N, với mọi mô hình
N của P.

13


1.2.2. Ngữ nghĩa
Đối với chương trình logic không chứa phủ định trong thân các mệnh đề thì nó
luôn có duy nhất một mô hình cực tiểu và cũng chính là mô hình nhỏ nhất. Tuy
nhiên, khi các mệnh đề của chương trình có chứa phủ định not ở thân thì chương
trình có thể có nhiều mô hình cực tiểu và không có mô hình nhỏ nhất. Chẳng hạn,
xem ví dụ sau:
Ví dụ 1.3. Xem chương trình logic P gồm các mệnh đề sau:
man(dung)
single(X) ← man(X), not husband(X)
husband(X) ← man(X), not single(X)
Dễ dàng kiểm tra P có hai mô hình cực tiểu:
M1 = {man(dung), single(dung)},

M2 = {man(dung), husband(dung)}.
và P không có mô hình nhỏ nhất do M1 M2 và M2 M1.
Từ ví dụ trên, ta nhận thấy khi cho phép mệnh đề có chứa literal âm thì
chương trình có thể tồn tại nhiều mô hình cực tiểu nhưng không có mô hình nhỏ
nhất. Vấn đề đặt ra ở đây là khi một chương trình logic không tồn tại mô hình nhỏ
nhất thì ngữ nghĩa của chương trình sẽ được xác định như thế nào? Trong phần tiếp
theo sẽ trình bày hai cách tiếp cận nhằm giải quyết vấn đề này là tiếp cận theo ngữ
nghĩa mô hình hoàn hảo và ngữ nghĩa tập trả lời.
Trước hết chúng ta xem tiếp cận theo ngữ nghĩa mô hình hoàn hảo của chương
trình logic phân tầng.
1.2.2.1. Ngữ nghĩa mô hình hoàn hảo
Phần này xem xét một lớp con hạn chế của chương trình logic thông thường,
gọi là chương trình logic phân tầng. Trước hết ta cần đến khái niệm đồ thị phụ thuộc
của một chương trình logic thông thường.
14


Định nghĩa 1.10 (Đồ thị phụ thuộc). Đồ thị phụ thuộc của một chương trình logic
P, ký hiệu DG(P), là một đồ thị có hướng được xây dựng như sau:
-

Ứng với mỗi vị từ p trong P, có một đỉnh được gán nhãn là p.
Có một cạnh có hướng từ đỉnh q đến đỉnh p nếu có mệnh đề trong P có dạng:
p ←...q...
Lúc đó ta nói cạnh q → p là cạnh dương.

-

Có một cạnh có hướng từ đỉnh q đến đỉnh p được gán nhãn "_" nếu có mệnh đề
trong P có dạng:

p ← . . . ¬q . . .
Lúc đó ta nói cạnh q → p là cạnh âm và vị từ p là phụ thuộc âm vào vị từ q.
Định nghĩa 1.11 (Chương trình logic đệ qui). Một chương trình logic P gọi là đệ qui
nếu đồ thị phụ thuộc của nó có chu trình, ngược lại P được gọi là không đệ qui. Vị từ
nằm trong chu trình được gọi là vị từ đệ qui, ngược lại gọi là vị từ không đệ qui.
Định nghĩa 1.12 (Chương trình logic phân tầng). Chương trình logic P được gọi là
chương trình logic phân tầng nếu đồ thị DG(P) của nó không có chu trình chứa một
hay nhiều cạnh âm, tức là không có đích con phủ định đệ qui.
Định nghĩa 1.13 (Tầng của vị từ). Cho P là chương trình logic phân tầng. Tầng của
vị từ p trong P được xác định theo quy tắc sau :
(i) Nếu vị từ p là phần đầu của mệnh đề có q là đích con phủ định, nghĩa là p
phụ thuộc âm vào q thì tầng của p lớn hơn tầng của q.
(ii) Nếu vị từ p là phần đầu của mệnh đề có q là đích con không phủ định thì
tầng của p lớn hơn hoặc bằng tầng của q.
Do DG(P) không có chu trình chứa cạnh âm (tức không có đích con phủ định
đệ qui) nên tầng của tất cả vị từ đều hữu hạn.
Thuật toán sau đây cho phép kiểm tra một chương trình logic thông thường có
được phân tầng hay không.
15


Thuật toán 1.1 Kiểm tra và xây dựng các tầng
Vào: Chương trình logic thông thường P.
Ra: Kết luận P có phân tầng được hay không. Nếu có thì xây dựng các tầng cho các
vị từ của P.
Phương pháp:
Bước khởi đầu: Mọi vị từ của chương trình được gán ở tầng 1.
Bước lặp: Nếu một mệnh đề có đầu là p và có đích con phủ định q, gọi i, j lần lượt
là các tầng tương ứng của p và q. Nếu i ≤ j thì gán lại tầng của p là j + 1. Hơn nữa,
nếu đầu mệnh đề là p và có đích con không phủ định q thuộc tầng j và i < j thì gán

lại p thuộc tầng j.
Nếu đến một lúc nào đó mà không còn tầng nào bị thay đổi nữa thì thuật toán
tạo ra các tầng của các vị từ trong chương trình. Còn nếu ta đi đến tình huống trong
đó một vị từ được gán cho một tầng lớn hơn tổng số các vị từ thì chương trình logic
P không được phân tầng.
Chi tiết thuật toán viết theo ngôn ngữ tựa Pascal như sau:
for mỗi vị từ p do
tầng[p] = 1;
repeat
for mỗi mệnh đề r có đầu là p do
begin
for mỗi đích con phủ định q của r do
tầng[p] := max{tầng[p],tầng[q]+1};
for mỗi đích con không phủ định q của r do
tầng[p] := max{tầng[p],tầng[q]};
end;
16


until không còn sự thay đổi nào đối với các tầng hoặc có một tầng của vị từ
nào đó vượt quá số lượng các vị từ.
Output trả lời "yes" (chương trình logic P được phân tầng) nếu không còn tầng
nào bị thay đổi, những tầng hiện tại là kết xuất của thuật toán và trả lời " no"
(chương trình logic P không được phân tầng) nếu tầng của vị từ nào đó vượt
quá số lượng các vị từ.
Ví dụ 1.4 Xem chương trình logic P gồm các mệnh đề:
p(X) ← r(X) ∧ not q(X)

(1)


q(X) ← r(X) ∧ not p(X)

(2)

Đồ thị phụ thuộc DG(P) của chương trình P:

_p

pp

qp
_p

rp

Hình 1.1. Đồ thị DG(P) của chương trình logic ở ví dụ 1.4
Đồ thị này có chu trình chứa cạnh âm, vì vậy chương trình P này không phân tầng.
Ví dụ 1.5 Xét chương trình logic P gồm các mệnh đề:
r1: p(X,Y) ← e(X,Y)
r2: p(X,Y) ← p(X,Z) ∧ p(Z,Y)
r3: q(X,Y) ← r(X,Y) ∧ ¬p(X,Y)
17


18


Đồ thị phụ thuộc DG(P) của chương trình P như sau:

qp


_p
pp

ep

rp

Hình 1.2. Đồ thị DG(P) của chương trình logic ở ví dụ 1.5
Đồ thị này không có chu trình chứa cạnh âm, vì vậy chương trình P phân tầng. Mặc
dầu vị từ q phụ thuộc âm vào vị từ p nhưng vị từ p không phụ thuộc vào vị từ q.
Khi một chương trình logic là phân tầng, giả sử có k tầng thì ta có thể tạo nên
một phân hoạch P1, . . . , Pk của P sao cho P = P1 ∪ . . . ∪ Pk, trong đó Pi gồm các
mệnh đề mà vị từ đầu của nó thuộc tầng i, i = 1, . . . , k.
Đối với chương trình logic phân tầng ta cũng có thể định nghĩa toán tử hệ quả
trực tiếp như sau:
Định nghĩa 1.14 (Toán tử hệ quả trực tiếp). Giả sử P là chương trình logic, I là một
thể hiện Herbrand của P. Ta ký hiệu I ⊨A nếu A ∈ I và I ⊨ ¬A nếu A ∉ I. Toán tử
hệ quả trực tiếp TP đối với chương trình P là ánh xạ
TP:

→

19


được định nghĩa như sau: Với mỗi I ∈

,


Tp(I) = {A ∈BP | ∃A ←L1 ∧ . . . ∧ Lm ∈ ground(P) và I ⊨ L1, . . . ,Lm}.
trong đó

là tập các tập con của cơ sở Herbrand BP.

Ký hiệu là giới hạn của dãy:
,
.
Giả sử P là chương trình logic phân tầng và P = P1 ∪ . . . ∪ Pn.
Đặt:
M1 =

(∅)

M2 =

(M1)

...
Mn =

(Mn-1)

Lúc này ta có định lý sau:
Định lý 1.1. Giả sử P là chương trình logic phân tầng. Lúc đó:
(i) MP = Mn là độc lập với phép phân tầng của P.
(ii) MP là mô hình cực tiểu của P.
Định nghĩa 1.15 (Ngữ nghĩa mô hình hoàn hảo). Giả sử P là chương trình logic
phân tầng. Ngữ nghĩa mô hình hoàn hảo của P là mô hình cực tiểu MP được xác
định bởi Định lý 1.1.

Ví dụ 1.6. Xét chương trình logic P gồm các mệnh đề sau:
20


p(X) ← r(X)
p(X) ← p(X)
q(X) ← s(X) ∧ ¬p(X)
r(1) ←
s(1) ←
s(2) ←

21


Đồ thị phụ thuộc DG(P) của chương trình logic này như sau:

qp

_p
pp

sp

rp

Hình 1.3. Đồ thị DG(P) của chương trình logic ở ví dụ 1.6
Đồ thị này không có chu trình chứa cạnh âm, vì vậy chương trình P phân tầng. Ta
có p, r, s thuộc tầng 1 và q thuộc tầng 2. Lúc đó P = P1 ∪ P2, trong đó:
P1:


p(X) ← r(X)
p(X) ← p(X)

P2:

r(1)

←

s(1)

←

s(2)

←

q(X) ← s(X) ∧ ¬p(X)

Ta có mô hình cực tiểu của P1:

22


M1 =

(∅) = {r(1), s(1), s(2), p(1)}

Ta tìm mô hình cực tiểu M2 của P2, ta có:
I0 = M1 = {r(1), s(1), s(2), p(1)}


I1 =

(I0) = I0 ∪{q(2)}

I2 =

(I1) = I1 ∪∅ = I1 = {r(1), s(1), s(2), p(1), q(2)}

Vậy:
M2 =

(M1) = {r(1), s(1), s(2), p(1), q(2)}

Do đó chương trình logic P có mô hình hoàn hảo là:
MP = {r(1), s(1), s(2), p(1), q(2)}.
1.2.2.2. Ngữ nghĩa tập trả lời
Ngữ nghĩa mô hình hoàn hảo đã xét có một hạn chế là chỉ có thể áp dụng cho
các chương trình logic phân tầng. Trong phần này sẽ trình bày một mở rộng của ngữ
nghĩa mô hình hoàn hảo, gọi là ngữ nghĩa mô hình bền vững (hay còn goị là ngữ
nghĩa tập trả lời), được đề xuất bởi Gelfond và Lifschitz. Ngữ nghĩa tập trả lời được
thực hiện dựa trên một phép biến đổi chương trình, gọi là phép biến đổi Gelfond –
Lifschitz và được định nghĩa hình thức như sau:
Định nghĩa 1.16 [5] (Phép biến đổi Gelfond - Lifschitz). Cho P là chương trình
logic và I là một thể hiện của P. Phép biến đổi Gelfond - Lifschitz của P theo I sẽ
biến đổi P thành chương trình ký hiệu là bằng cách thực hiện:
1. Loại bỏ khỏi P tất cả các mệnh đề chứa literal âm not A, với A ∈ I.
2. Loại bỏ các literal not A trong thân của các mệnh đề còn lại.

23



Để ý rằng nếu A ∈ I thì thân mệnh đề có chứa literal not A không thể trở thành
đúng, vì vậy có thể loại bỏ mệnh đề này. Mặt khác, nếu A ∉ I thì not A có thể giả sử
là đúng và được loại bỏ khỏi thân mệnh đề chứa nó.
Rõ ràng là chương trình không có phủ định, nó là chương trình logic xác định,
vì vậy có mô hình nhỏ nhất, ký hiệu Γ(I).
Ví dụ 1.7. Cho P là chương trình logic gồm các mệnh đề:
a ← not b
b ← not a
c ← a, not b
Xét thể hiện M1 = {a, c}. Lúc đó gồm các mệnh đề:
a←
c←a
và mô hình nhỏ nhất của chính là {a,c}.
Xét thể hiện M2 = {b}. Lúc đó gồm 1 mệnh đề:
b←
và mô hình nhỏ nhất của chính là {b}.
Định nghĩa 1.17 [5] (Tập trả lời). Thể hiện I của chương trình logic P được gọi
là tập trả lời của P nếu I là mô hình nhỏ nhất của , nghĩa là Γ(I) = I.
Ví dụ 1.8. Xét chương trình P gồm các mệnh đề sau:
s ← not q
q ← not s
p ← q, not s
f ← s, not p
24


Xét M1 = {p, q}. Khi đó, gồm các mệnh đề: q và p ← q và mô hình nhỏ nhất của nó
là {p, q} = M1. Vậy M1 là tập trả lời của P.

Xét M2 = {s}. Khi đó, gồm các mệnh đề: s và f ← s
Mô hình nhỏ nhất của là {s, f} ≠ M2. Vì vậy M2 không là tập trả lời của P.
Định lý 1.2 [5] Cho P là chương trình logic. Lúc đó mọi tập trả lời của P đều là mô
hình cực tiểu của P.
Để ý là mô hình cực tiểu của chương trình logic chưa hẳn là tập trả lời. Xem
ví dụ sau:
Ví dụ 1.9. Xét chương trình logic P gồm các mệnh đề:
p(a) ←
r(X) ← p(X), not q(X)
Lúc đó P có 2 mô hình cực tiểu là M1 = {p(a), r(a)} và M2 = {p(a), q(a)}. Trong đó
chỉ có M1 là tập trả lời của P còn M2 thì không phải.
Định nghĩa 1.18 (Ngữ nghĩa tập trả lời). Ngữ nghĩa tập trả lời của chương trình
logic P được xác định bởi tập các tập trả lời của P.
Một nguyên tố nền A của P là đúng dưới ngữ nghĩa tập trả lời nếu A thuộc vào tất
cả tập trả lời của P.
Ví dụ 1.10. Xét chương trình logic P gồm các mệnh đề:
a ← not b
b ← not a
c ← not d
d ← not e
p←a
p←b
25