Bài giảng Hệ chuyên gia - Phan Huy Khánh - Chương 2: Biểu diễn tri thức nhờ logic vị từ bậc một (Phần 3)

ack, tuna) ∨
KILLS(curiosity, tuna)i i
∀X CAT(X) →
ANIMAL(X)
48/69
Bài tập 1
a Cho các câu sau :
V Marcus là một người
V Marcus là người xứ Pompeii
(hay xứ Campanie gần Naple nước Ý)
V Mọi người Pompeii đều là người La Mã
V Ceasar là một kẻ cầm quyền
V Người La Mã hoặc là trung thành với Ceasar,
hoặc là thù ghét Ceasar
V Mỗi người đều trung thành với một người nào đó
V Nhân dân chỉ muốn giết những kẻ cầm quyền
mà họ không trung thành
V Marcus muốn giết Ceasar
a Biểu diễn các câu trên thành các wff’s
49/69
Biểu diễn wff’s trong lôgic vị
từ
a Marcus là một người
MAN(marcus)
a Marcus là một người Pompeii
POMPEIAN(marcus)
a Mọi người Pompeian đều là người La Mã
∀x : POMPEIAN(X) →
ROMAN(X)
a Caesar là một kẻ cầm quyền
(giả sử không có sự trùng tên)
RULER(caesar)
a Người La Mã hoặc là trung thành với Caesar,
hoặc là thù ghét Caesar
∀x : ROMAN(X) →
LOYALTO(X, caesar) ∨
HATE(X, caesar)
a Tuy nhiên khi sử dụng với nghĩa hoặc có loại trừ, có thể viết lại :
∀x : ROMAN(X) →
((LOYALTO(X, caesar) ∧
HATE(X, caesar)) ∧
 (¬LOYALTO(X, caesar) ∧
HATE(X, caesar))) 
50/69
Biểu diễn wff’s trong lôgic vị
từ
a Mọi người đều trung thành với một người nào đó
∀X, ∃Y LOYALTO(X, Y)
hoặc
∃Y, ∀X LOYALTO(X, Y)
a Nhân dân chỉ muốn giết những kẻ cầm quyền
mà họ không trung thành
∀X, ∀Y PERSON(X) ∧
RULER(Y) ∧
TRYASSASSINATE(X, Y) →
 ¬LOYALTO(X, Y)
Mệnh đề
này tỏ
ra mập mờ
(ambiguous). Có
phải chỉ
những kẻ
cầm 
quyền mà
nhân dân muốn giết là
những kẻ
họ
không trung thành (theo 
nghĩa đã biểu trưng) hay chỉ
những điều mà
nhân dân có ý định là
giết 
những kẻ
cầm quyền mà
họ
không trung thành ?
a Marcus muốn giết Ceresar
V TRYASSASSINATE(marcus, caesar)
a Câu hỏi : Marcus có trung thành với Caesar không ?
51/69
Bài tập 2
a Cho các câu sau :
V Marcus là một người
V Marcus là người Pompeii
V Marcus sinh năm 40 trong công nguyên (A.D.: Anno Domini)
V Mọi người đều (ai cũng phải) chết
V Tất cả mọi người dân Pompeii đều bị chết
vì núi lửa phun vào năm 79 A.D.
V Không có người nào (không ai) sống nhiều hơn 150 tuổi
V Bây giờ là năm 2007
V Còn sống có nghĩa là không chết
V Nếu ai đó chết, thì người ấy có thể chết ở mọi thời điểm sau đó
V Marcus còn sống không ?
a Biểu diễn các câu trên thành các wff’s
52/69
a Marcus là một người
MAN(marcus)
a Marcus là người Pompeii
POMPEIAN (marcus)
a Marcus sinh năm 40 trong công nguyên
(A.D.: Anno Domini)
BORN(marcus, 40)
a Mọi người đều (ai cũng phải) chết
∀X MAN(X) Ø
MORTAL(X)
a Tất cả mọi người dân Pompeii đều bị chết
vì núi lửa phun vào năm 79 A.D.
∀X ERUPTED(vocalno, 79) ∧
POMPEIAN(X) Ø
DIED(X, 79)
53/69
a Không có người nào (không ai) sống nhiều hơn 150 tuổi
∀X ∀T1 ∀T2
 MAN(X) ∧
BORN(X, T1) ∧
GT(T2 -
T1, 150) Ø
DIED(X, T2)
a Bây giờ là năm 2007
now = 2007
a Còn sống có nghĩa là không chết
∀X ∀T
(ALIVE(X, T) Ø
¬DEAD(X, T))
 ∧
((DIED(X, T) Ø
¬ALIVE(X, T))
a Nếu ai đó chết,
thì người ấy có thể chết ở mọi thời điểm sau đó
∀X ∀T1 ∀T2
DIED(X, T1) ∧
GT(T2, T1) Ø
DEAD(X, T2)
54/69
Diễn giải (Interpretation)
a Cho G là một CTC, một diễn giải của G, ký hiệu I, được xác 
định từ năm bước sau đây :
V Chọn miền diễn giải (Interpretation Domain) là các tập hợp 
khác rỗng, ký hiệu D ≠ ∅
V Gán (Assignation) cho mỗi hằng của G một phần tử của Di
V Gán cho mỗi mệnh đề (hay vị từ bậc 0)
một giá trị true (T) hoặc false (F)
V Gán cho mỗi vị từ bậc n (n≥1) ánh xạ từ Dn lên { T, F } :
P
(T
1
,... T
n
) : Dn
→
{ T, F }
V Gán cho mỗi hàm bậc n (n≥1) ánh xạ từ Dn lên D :
f(X
1
,... X
n
) : Dn
→
D
55/69
Mô hình diễn giải I từ
G lên D 
G
D ≠ ∅
Mệnh đề
 (vị
từ
bậc 0)
 P, Q
 ị
Vị
từ
bậc n
 P(T1
,... Tn
)
ị
Hằng
 a..z
Hàm bậc n
 f(X1
,... Xn
)
{ T, F } Dn
→
{ T, F }
Dn
→
D
a Khi một CTC G có giá trị là T theo một diễn giải I, 
người ta nói rằng diễn giải I là một mô hình của G
56/69
Quan hệ
Translation-Interpretation
Ngôn ngữ
 tự
nhiên
Ngôn ngữ
 lôgic vị
từ
 WFF
Ngôn ngữ
 diễn giải
 D, {T, F}
Translation Interpretation
Application
Quê hương mỗi người chỉ
một,
như là
chỉ
một mẹ
thôi
 i i ỉ
,
 l
ỉ
i
∀X∃Y∃Z (QUE(X,Y) ∧
(QUE(X,Z) →
EQ(Y,Z)) 
↔
∀T∃U∃V (FEMALE(U) ∧
(MOTHER(U,T))
∧
(FEMALE(V) ∧
(MOTHER(V,T))
→
EQ(U,V))
 , 
, 
, 
,
,
,
T
57/69
Tính giá
trị
của CTC theo diễn giải
a Cho G là một CTC và một diễn giải I trên một miền D
a Khi đó :
V Nếu G là một mệnh đề, giá trị gán cho G qua I là I(G)
V Nếu G là một trực kiện, G nhận một giá trị T hay F
V Nếu G có dạng (∀X)G’ :
™ I(G) = T nếu I(G’) = T cho mọi giá trị của biến X trong D
™ I(G) = F nếu không phải
V Nếu G có dạng (∃X)G’ :
™ I(G) = T nếu I(G’) = T với ít nhất một giá trị của X trong D
™ I(G) = F nếu không phải
58/69
Tính giá
trị
của CTC theo diễn giải (tiếp)
a Nếu G có dạng (¬G’) :
V I(G) = T nếu I(G’) = F trong D
V I(G) = F nếu I(G’) = T trong D
a Nếu G có dạng (G’ ∧ G’’), hoặc (G’ ∨ G’’),
hoặc (G’ → G’’), hoặc (G’↔ G’’), khi đó :
G’ G’’ (G’
∧
G’’) (G’
∨
G’’) G’
→
G’’ G’
↔
G’’
F F F F T T
F T F T T F
T F F T F F
T T T T T T
59/69
Tính hợp thức và
tính nhất quán 
aMột CTC được gọi là :
V Hằng đúng (tautology), hay hợp thức (valid)
nếu và chỉ nếu mọi diễn giải đều cho giá trị T
V Nếu không, được gọi là không hợp thức (non−valid) 
aMột CTC được gọi là :
V Mâu thuẫn (contradiction), hay không nhất quán (inconsistent)
nếu và chỉ nếu với mọi diễn giải đều cho giá trị F
V Nếu không, được gọi là nhất quán (consistent)
aQuy ước :
V  biểu diễn một CTC hợp thức-hằng đúng
V ∇ biểu diễn một CTC mâu thuẫn-không nhất quán
60/69
Công thức tương đương
a Cho G và H là hai CTC
a G và H được gọi là tương đương, G ≡ H :
V Nếu và chỉ nếu G và H có cùng giá trị (T hoặc F)
cho mọi diễn giải I, I(G) = I(H)
a Ví dụ :
V (P(a) → Q(b)) ≡ ((¬P(a) ∨ Q(b))
a Có thể dùng bảng chân lý
để kiểm tra tính tương đương của các CTC
61/69
Bảng các công thức tương đương
Công thức tương đương Tên công thức
(G →
H)
((¬G) ∨
H)
(G ↔
H)
((G →
H) ∧
(H →
G))
(¬(¬
G))
G
(¬(G ∧
H))
((¬G) ∨
(¬H))
Luật De Morgan
(¬(G ∨
H))
((¬G) ∧
(¬H))
((G ∧
(H ∨
K))
((G ∧
H) ∨
(G ∧
K))
Luật phân phối
((G ∨
(H ∧
K))
((G ∨
H) ∧
(G ∨
K))
(G ∧
H)
(H ∧
G)
Luật giao hoán
(G ∨
H)
(H ∨
G)
((G ∨
H) ∨
K)
(G ∨
(H ∨
K)) Luật kết hợp cho phép loại bỏ
 dấu ngoặc((G ∧
H) ∧
K))
(G ∧
(H ∧
K))
(
G →
H)
((¬H) →
(¬G)) Luật đối vị
62/69
Bảng các công thức tương đương
Công thức tương đương Tên công thức
(G ∧ ) G
(G ∧
∇)
∇
(G ∨ ) 
(G ∨
∇)
G
(G ∨
(¬G)) 
(G ∧
(¬G)) ∇
(∀X)(G(X))
(∀Y)(G(Y))
Luật dùng chung các biến
(∃X)(G(X))
(∃Y)(G(Y))
¬((∀X)G(X))
(∃Y)(¬G(Y))
¬((∃X)G(X))
(∀Y)(¬G(Y))
(∀X)(G(X) ∧
H(X))
((∀X)G(X)
∧
(∀Y)H(Y))
(∃X)(G(X)) ∨
H(X))
((∃X)G(X) ∨
(∃Y)H(Y))
63/69
Biến đổi các CTC : loại bỏ lượng tử
∀
và
∃
a Standardize Variables
V Make sure that you are not using the same variable name twice 
in a single sentence (unless you really meant to)
Eg. 
(∀X P(X)) ∨
(∃X Q(X))
becomes
(∀X P(X)) ∨
(∃Z Q(Z))
a Move all quantifiers left, but keep them in order!
V Eg.
(∀X P(X) ∨
∃Y Q(Y))
becomes
(∀X ∃Y P(X) ∨
Q(Y))
a Translation into the form:
Q M
 with Q: quantifiers, in order ∀s and then ∃s
 M: Matrix: wffs including V, : Variable
64/69
Biến đổi các CTC
a Skolemize: Eliminate Existential Quantifiers
V Existential quantifiers can be eliminated by the introduction
of a new constant that does not appear elsewhere
in the database
V SUBST{ X|a, a∈D } /* Substitution
V Eg.
∃X P(X) becomes
P(a) 
“Có người vào lớp muộn”
 becomes “Cu Tý vào lớp muộn”∃X P(X) ∨
Q(X)
becomes
P(a) ∨
Q(a)
“Chàng tìm đồng kia bãi nọ”
 becomes
 “Chàng tìm đồng dưới đồng trên”
65/69
Biến đổi các CTC
a Skolemize: Drop Existential Quantifiers
V One possible complication occurs if we also have Universal 
quantifiers… Consider
∀X PERSON(X) →
∃Y
(HEART(Y) ∧
HAS(X, Y))
becomes by SUBST{Y|h}:
∀X PERSON(X) →
HEART(h) ∧
HAS(X, h)
V Instead we have to create a new (Skolem) function to map from a 
person to their HEART(f(x))
∀X ∃Y PERSON(X) → (HEART(Y) ∧ HAS(X, Y)) becomes: 
∀X PERSON(X) →
HEART(f(X)) ∧
HAS(X, f(X))
 Eg., in general:
 ∀X ∀Y ∀Z ... ∃T ... P(X, Y, Z,...T,...) becomes: ∀X ∀Y ∀Z ... P(X, Y, Z,...f(X, Y, Z,...),...) 
a Drop all Universal Quantifiers in the end:
V ∀X ∀Y ∀Z... P(X, Y, Z,...) becomes: P(X, Y, Z,...)
66/69
Biến đổi các CTC
a Move the ↔:
V P ↔ Q becomes (P → Q) ∧ (Q → P)
a Distribute ∧ over ∨
V (A ∧ B) ∨ C becomes (A ∨ C) ∧ (A ∨ B) 
V Just like distribution in arithmetic 
V (5 + 4) * 6 becomes (5 * 6 ) + (4 * 6 )
a Flatten nested conjunctions and disjunctions
V (A ∧ B) ∧ C becomes (A ∧ B ∧ C) 
V (A ∨ B) ∨ C becomes (A ∨ B ∨ C)
67/69
Done!!
a Biến đổi các CTC :
V Standardize Variables
V Move the ↔
V Move Quantifiers left
V Skolemize:
™ Eliminate Existential Quantifiers
™ Drop Universal Quantifiers
V Distribute ∧ over ∨
V Flatten nested conjunctions and disjunctions
a Attention:
V In Proof Theory by Robinson Resolution, they need to before:
™ Eliminate Implications
™Move ¬ inwards
68/69
Xây dựng cơ sở
luật cho HCG
a Sự kiện 1 :
V Con mèo mà trèo cây cau
Hỏi thăm chú chuột đi đâu vắng nhà
Chú chuột đi chợ đường xa
Mua mắm, mua muối về giỗ cha con mèo
a Hỏi :
V Mèo có ăn đuợc (gặp) chuột không rứa ?
a Sự kiện 2 :
V Ông Trăng mà lấy bà Trời
Tháng Năm đi cưới, tháng Mười nộp cheo
Làng xã làm thịt một con mèo
Làng ăn không hết làng treo cột đình
Ông Xã đánh trống thình thình
Bao nhiêu con nít ra đình gặm xương
a Hỏi :
V Cu Tý có gặm đuợc xương không rứa ?
69/69
Tạo không gian : các miền xác định
aSự kiện 1 :
V Con mèo mà trèo cây cau : TREO(X, Y)
V Hỏi thăm chú chuột đi đâu vắng nhà :THAM(X, Y), VANGNHA(X)
V Chú chuột đi chợ đường xa
V Mua mắm, mua muối về giỗ cha con mèo
Gợi ý dùng luật :
MEO(X) ∧
CHUOT(Y) ∧
THAM(X, Y) ∧
COONHA(Y) →
ANTHIT(X,Y)
Các vật
Các con vật
chuột
mèocha_mèo
cau
mắm
muối