Suy diễn trong logic vị từ

1


Suy diễn trong logic cấp một
•
•
•
•
•
•

Phép chứng minh
Phép hợp nhất
Luật Modus Ponens tổng quát
Lập luận tiến và lập luận lùi
Tính đầy đủ
Luật phân giải

2


Phép chứng minh
• Suy diễn tin cậy: tìm ra α sao cho KB ╞ α
Q trình chứng minh có thể quy về vấn đề tìm kiếm, trong đó các
tốn tử là các luật suy diễn.
• Thí dụ, Modus Ponens (MP)
Hoc( An, DHTL) Hoc( An, DHTL)  Gioi( An)
,   


Gioi( An)
• Thí dụ, Đưa vào hội (AI)
, 
 

Gioi( An) NganhCNTT ( An)
Gioi( An)  NganhCNTT ( An)

• Thí dụ, Loại bỏ mọi (UE)
x 
x Hoc( x, DHTL)  Gioi( x)
 {x /  }
Hoc( Lan, DHTL)  Gioi( Lan)
 phải là hạng tử gốc (tức là, không chứa biến)

3


Ví dụ về chứng minh

4


Ví dụ về chứng minh

5


Tìm kiếm với các luật suy diễn cơ
sở

•
•
•

Các tốn tử là các luật suy diễn
Các trạng thái là tập các câu
Hàm kiểm soát mục tiêu kiểm tra
trạng thái để biết nó có chứa câu
truy vấn hay khơng

AI, UE, MP là các mơ hình suy diễn phổ biến
Vấn đề: số lượng nhân tố nhánh khổng lồ đối
với UE
Ý tưởng: tìm ra một phép thế sao cho nó tạo ra
phần giả thiết của luật khớp với một số sự kiện
đã biết
 một luật suy diễn đơn mạnh hơn
6


Phép hợp nhất
• Một phép thế σ hợp nhất các câu đơn p và q nếu pσ = qσ

7


Phép hợp nhất
• Một phép thế σ hợp nhất các câu đơn p và q nếu pσ = qσ

• Ý tưởng: Hợp nhất các giả thiết luật với các sự kiện, áp dụng hợp

nhất tử cho phần kết luận
• Thí dụ,
nếu chúng ta biết q và Biet(Trung, x)  Yeuquy(Trung, x)
thì chúng ta kết luận Yeuquy(Trung, Lan)
Yeuquy(Trung, XuanDieu)
Yeuquy(Trung, Me(Trung))

8


Modus Ponens tổng qt (GMP)
•

trong đó pi '  pi với mọi i
• Thí dụ, p '  Nhanhhon( Capi , Bibi )
1
p '2  Nhanhhon( Bibi , Mike )
p1  p 2  q  Nhanhhon( x , y )  Nhanhhon( y , z )  Nhanhhon( x , z )
  { x / Capi , y / Bibi , z / Mike }
q  Nhanhhon( Capi , Mike )
• GMP được sử dụng với KB gồm các câu rõ ràng (có đúng một chữ
dương):
hoặc là câu đơn hoặc là câu có dạng
(hội của các câu đơn)  (câu đơn)
• Tất cả các biến đều được giả định là đi với lượng tử mọi

9


Lập luận tiến

• Khi một sự kiện p mới được thêm vào KB

for mỗi luật mà p hợp nhất được với một giả thiết
if các giả thiết khác đã có
then thêm phần kết luận vào KB và tiếp tục lập luận

• Lập luận tiến phụ thuộc vào dữ liệu

Thí dụ, suy diễn ra các tính chất và các hạng mục từ những thứ
quan sát được

10


Ví dụ về lập luận tiến
• Lần lượt thêm vào các sự kiện 1, 2, 3, 4, 5, 7
• Chữ số trong [] = chữ hợp nhất; √ chỉ việc cháy luật

11


Lập luận lùi
• Khi có một truy vấn q được gọi
if nó khớp với một sự kiện q’ đã có, trả về hợp nhất tử
for mỗi luật mà phần kết luận q’ của nó khớp với q
cố gắng chứng minh mỗi giả thiết của luật bằng lập luận lùi

• Hai phiên bản: tìm một giải pháp bất kỳ, tìm tất cả các
giải pháp
• Lập luận lùi là cơ sở cho các ngơn ngữ lập trình logic, thí

dụ Prolog

12


Ví dụ về lập luận lùi

13


Tính đầy đủ trong FOL
• Thủ tục i là đầy đủ nếu vào chỉ nếu
KB │─ i α bất cứ khi nào KB │═ α
• Lập luận tiến và lập luận lùi là đầy đủ đối với các KB Horn nhưng
không đầy đủ đối với logic mệnh đề và logic vị từ cấp một nói chung
• Thí dụ, từ

phải có thể suy diễn ra Rich(Me), nhưng FC/BC không thực hiện
được điều này
• Liệu có tồn tại một giải thuật đầy đủ không?
14


Phương pháp phân giải
• Phương pháp phân giải là một thủ tục bác bỏ:
để chứng minh KB │═ α, chỉ ra rằng KB ٨  α là khơng thoả
được
• Phương pháp phân giải sử dụng KB,  α trong CNF (hội các câu
tuyển)
• Luật suy diễn phân giải kết hợp hai câu tuyển để tạo ra một câu

tuyển mới

• Quá trình suy diễn được tiếp tục cho đến khi nhận được một câu
rỗng (sự mâu thuẫn)
15


Luật suy diễn phân giải
• Phiên bản cơ sở cho mệnh đề:
hoặc tương đương với
• Phiên bản đầy đủ cho vị từ:

trong đó
• Ví dụ,

với
16


Dạng chuẩn hội (CNF)
•
•
•
•

Chữ = (có thể có phép phủ định) câu đơn, thí dụ,  Rich(Me)
Câu tuyển = tuyển của các chữ, thí dụ,  Rich(Me) ۷ Unhappy(Me)
KB là hội của các câu tuyển
Một KB FOL bất kỳ có thể chuyển về dạng CNF như sau:
1. Thay thế P  Q bởi P  Q

2. Di chuyển  vào phía trong, thí dụ
trở thành
3. Chuẩn hố các biến để chúng tách rời nhau,
thí dụ
trở thành
4. Chuyển các lượng tử sang trái theo thứ tự,
thí dụ
trở thành
5. Loại bỏ  bằng Skolemization (slide tiếp theo)
6. Bỏ các lượng tử mọi đi
7. Phân phối ٨ đối với ۷,
17
thí dụ
trở thành ( P  R )  ( Q  R )


Skolemization
•

trở thành

trong đó G1 là một hằng Skolem mới

trở thành
• Địi hỏi tinh vi hơn khi  nằm phía trong 
• Thí dụ, “Tất cả mọi người đều có một trái tim”
Sai:
Đúng:
trong đó H là một ký hiệu mới (“hàm Skolem”)
• Tất cả các đối số của hàm Skolem đều đi cùng với các biến lượng tử

mọi
18


Ví dụ: Chuyển về CNF
 Tất cả những người yêu động vật đều được yêu bởi một ai đó:
∀x ([∀y Animal(y) ⇒ Loves(x,y)] ⇒ [∃y Loves(y,x)])
 Loại bỏ phép kéo theo (và phép nếu và chỉ nếu)
∀x ([¬(∀y ¬Animal(y) ∨ Loves(x,y))] ∨ [∃y Loves(y,x)])

 Di chuyển ¬ vào phía trong: ¬∀x p ≡ ∃x ¬p, ¬ ∃x p ≡ ∀x ¬p
∀x [∃y ¬(¬Animal(y) ∨ Loves(x,y))] ∨ [∃y Loves(y,x)]
∀x [∃y ¬¬Animal(y) ∧ ¬Loves(x,y)] ∨ [∃y Loves(y,x)]
∀x [∃y Animal(y) ∧ ¬Loves(x,y)] ∨ [∃y Loves(y,x)]
19


Ví dụ: Chuyển về CNF
 Chuẩn hóa các biến: mỗi lượng tử nên sử dụng một biến khác
nhau:
∀x [∃y Animal(y) ∧ ¬Loves(x,y)] ∨ [∃z Loves(z,x)]

 Skolemize: Mỗi biến tồn tại được thay thế bởi một hàm Skolem của
các biến lượng tử tồn thể bao phía ngồi:
∀x [Animal(F(x)) ∧ ¬Loves(x,F(x))] ∨ Loves(G(x),x)
 Xóa các lượng tử tồn thể:
[Animal(F(x)) ∧ ¬Loves(x,F(x))] ∨ Loves(G(x),x)

 Phân phối ∨ đối với ∧ :
[Animal(F(x)) ∨ Loves(G(x),x)] ∧ [¬Loves(x,F(x)) ∨ Loves(G(x),x)]


20


Chứng minh bằng p.p. giải
• Để chứng minh α:
– lấy phủ định của nó
– chuyển về dạng CNF
– thêm vào cơ sở tri thức CNF
– suy ra sự mâu thuẫn
• Thí dụ, để chứng minh Rich(me), thêm  Rich(me) vào
cơ sở tri thức CNF

21


Chứng minh bằng p.p. giải

22


Ví dụ
Jack ni một chú chó.
Tất cả mọi người ni chó đều là người u động vật.
Khơng có người nào yêu động vật lại giết một động vật.

Jack hoặc Curiosity đã giết mèo Tuna.
Liệu có phải Curiosity đã giết mèo Tuna?



Dạng chuẩn tác hội (CNF)
D là một hằng Skolem.

Thêm phủ
định của định
lý vào KB


Chứng minh bằng p.p. giải
kills(Curiosity,Tuna)

kills(Jack,Tuna)  kills(Curiosity,Tuna)

{}
AnimalLover(w)  Animal(y)  kills(w,y)

kills(Jack,Tuna)

{w/Jack, y/Tuna}
Animal(z)  Cat(z)

AnimalLover(Jack)  Animal(Tuna)

{z/Tuna}
AnimalLover(Jack)  Cat(Tuna)

Cat(Tuna)

{}
AnimalLover(Jack)


Dog(y)  Owns(x,y)  AnimalLover(x)

{x/Jack}
Dog(D)
Dog(y)  Owns(Jack,y)
{y/D}
Owns(Jack,D)

NIL

Owns(Jack,D)