Đề cương bài giảng Trí tuệ nhân tạo

 giải thuật so khớp. 
* Giải thuật so khớp 
1) Hằng / hằng so khớp : chỉ khi chúng giống hệt nhau 
2) Hằng a / biến X so khớp: 
a) Biến chưa kết buộc: biến trở thành kết buộc với hằng {X/a} 
b) Biến đã kết buộc : xem (1) 
3) Biến / biến so khớp: 
a) Hai biến chưa kết buộc: luôn luôn so khớp 
b) Một biến kết buộc và một biến chưa kết buộc: xem (2) 
c) Hai biến kết buộc: xem (1) 
4) Biểu thức / biểu so khớp: chỉ khi các tên hàm hoặc vị từ, số ngôi giống 
nhau thì áp dụng so khớp từng đối số một. 
Lưu ý : Phạm vi của một biến là một câu. Một khi biến đã bị kết buộc, các phép 
hợp nhất theo sau và các suy luận kế tiếp phải giữ sự kết buộc này. 
* Định lý phân giải 
Một tập câu tuyển G là không thỏa nếu và chỉ nếu câu rỗng thuộc R(G) 
* Chứng minh một công thức là hệ quả của một tập công thức đã cho bằng 
luật phân giải. 
 Ta sử dụng thủ tục sau đây: 
Procedure Proof_by_Resolution 
Input: Tập G các công thức G ={G1, G2, … , Gn} 
 H là công thức cần chứng minh 
Begin 
1. Biến đổi các công thức Gi (i= 1, 2,…, n) và công thức ¬H về dạng 
chuẩn hội 
 60
2. Từ dạng chuẩn hội nhận được ở bước 1, thành lập tập các câu tuyển C 
3. Repeat 
 Chọn ra hai câu A và B trong C 
 If A và B phân giải được then 
Tính giải thức Res(A, B) 
 If Res(A, B) là câu mới then thêm Res(A, B) vào C 
Until Nhận được câu rỗng hoặc không có câu mới nào được sinh ra; 
4. If câu rỗng được sinh ra then thông báo H đúng 
Else thông báo H sai 
End; 
Ví dụ: 
Giả sử chúng ta biết các thông tin sau đây: 
1. Ông Ba nuôi một con chó 
2. Hoặc ông Am hoặc ông Ba đã giết con mèo Bibi. Chúng ta cũng biết 
rằng: 
3. Mọi người nuôi chó đều yêu quý động vật 
4. Ai yêu quý động vật thì không giết động vật 
Và đượng nhiên là: 
5. Chó và mèo đều là động vật 
 Ta chuyển các câu ở trên thành các câu được biểu diễn bằng các công thức 
của logic vị từ cấp 1 như sau: 
6) dog(d) ^rear(ba, d) 
7) cat(bibi)^(kill(ba, bibi) v kill(am, bibi)) 
8) ∀X(∀Y(dog(Y)^ rear(X, Y)) => animalLover(X)) 
9) ∀X(animalLover(x) => (∀Y(animal(Y) => ¬kill(X, Y)))) 
10) ∀x(dog(X) => animal(X)) ^∀Y(cat(Y)=> animal(Y)) 
* Chuẩn hóa các câu trên thành dạng chuẩn hội ta thu được các câu tuyển 
sau: 
1) dog(d). 
2) rear(ba, d) 
 61
3) cat(bibi) 
4)(kill(ba, bibi) v kill(am, bibi)) 
5) ¬dog(Y) v ¬rear(X, Y) v animalLover(X) 
6) ¬animalLover(X) v ¬animal(Y)v ¬kill(X, Y) 
7) (¬dog(X) v animal(X)) 
8) (¬cat(Y) v animal(Y)) 
* Sau đó sử dụng luật phân giải để chứng minh Câu ông am đã giết chú mèo 
Bibi. 
Ta thêm vào tập các câu tuyển ở trên câu ¬kill(am, bibi) (9) 
áp dụng luật phân giải cho tập 9 câu tuyển ở trên: 
4 9 
¬kill(am, bibi) (10) 6
¬animalLover(ba) v ¬ animal(bibi) (11) 5 
¬dog(y) v ¬rear(ba, Y)v ¬ animal(bibi) (12) 1
 ¬rear(ba, d)v ¬ animal(bibi) (13) 2
 62
Vậy Ông Am đã giết Bibi là đúng 
3.2.4 Các câu hỏi và các trả lời 
Khi có một câu hỏi đến chương trình, chương trình sẽ coi đó như là một 
goal và cố gắng làm thỏa goal đó. Làm thỏa một goal có nghĩa là chương trình 
sẽ cố gắng chứng minh goal đó được suy luận trực tiếp từ cơ sở tri thức có trong 
chương trình. Nếu chương trình có thể chứng minh goal đó được suy luận từ 
chương trình thì câu trả lời sẽ là yes, và nếu trong câu hỏi có chứa các biến, thì 
sự thay thế các biến bằng các đối tượng cụ thể mà chương trình sử dụng trong 
quá trình suy diễn sẽ được hiển thị. Ngược lại nếu goal đó không được suy luận 
từ chương trình thì câu trả lời sẽ là no. 
Để tìm kiếm câu trả lời cho câu hỏi, chương trình sử dụng các thuật toán 
suy diễn tiến và suy diễn lùi. 
3.2.4.1 Suy diễn tiến / Lập luận tiến 
Chiến lược suy diễn bắt đầu bằng tập sự kiện đã biết, rút ra các sự kiện mới 
nhờ dùng các luật mà phần giả thiết khớp với sự kiện đã biết, và tiếp tục qúa 
trình này cho đến khi thấy trạng thái đích, hoặc cho đến khi không còn luật nào 
khớp được các sự kiện đã biết hay được sự kiện suy diễn. 
Ta tách Cơ sở tri thức thành hai phần: 
Luật cơ sở: Ký hiệu là RB 
Sự kiện: Ký hiệu là FB 
animal(bibi) (13) 8
 ¬cat(bibi) (13) 3
câu rng 
 63
Với mỗi luật R: nếu P1 và P2 và Pn thì Q 
Ta ký hiệu danh sách các điều kiện của luật là Conds =[P1, P2, .., Pn] và 
phần kết luận của luật được ký hiệu là Conc = Q 
Ta có thủ tục lập luận tiến: 
Procedure Forchain(Conds, Conc) 
Begin 
 For each S in FB do 
 { 
If S hợp nhất với Pi trong Conds bởi phép thế θ then 
 { 
 Conds1 Í [P1θ, P2θ, Pi-1θ, Pi+1θ…, Pnθ] 
 Conc1 Í Concθ 
If Cond1 rỗng then 
Add(Conc1, FB) // Nếu Conc1 là sự kiện mới thì add vào FB 
Else 
ForChain(Conds1, Conc1); 
 } 
} 
End; 
Procedure forward_reasoning(RB, FB) 
Begin 
 Repeat 
 For each luật(Conds, Conc) in RB do 
 ForChain(Conds, Conc) 
 Until Không có luật nào sinh ra sự kiện mới; 
End; 
Như vậy hệ thống suy diễn tiến làm việc như sau: 
 64
 Ví dụ: 
Giả sử cơ sở luật chứa luật sau: 
Nếu 
1. x là ngựa và 
2. x là mẹ của y và 
3. y chạy nhanh 
thì 
 x có giá. 
Cơ sở sự kiện gồm các sự kiện sau: 
Tom là ngựa 
Ken là ngựa 
Kit là ngựa 
Bin là ngựa 
Tom là mẹ của Bin 
Tom là mẹ của Ken 
Bin là mẹ của Kit 
Kit chạy nhanh 
Bin chạy nhanh 
Bằng cách sử dụng các vị từ 
 65
 horse(X): X là ngựa 
mother(X, Y): x là mẹ của y 
fast(X): x chạy nhanh 
valueable(X): x có giá trị 
Ta có luật: 
(1) horse(X)^ mother(X, Y)^ fast(Y) => valueable(X) 
 Và các sự kiện 
(2) horse(tom) 
(3) horse(ken) 
(4) horse(kit) 
(5) horse(bin) 
(6) mother(tom, bin) 
(7) mother(tom, ken) 
(8) mother(bin, kit) 
(9) fast(kit) 
(10) fast(Bin) 
Ta có: 
Conds= [horse(X), mother(X, Y), fast(Y)] 
Conc = valueable(X) 
FB =[horse(tom), horse(ken), horse(kit), horse(bin), mother(tom, bin), 
mother(tom, ken), mother(bin, kit), fast(kit), fast(Bin)] 
áp dụng thủ tục lập luận tiến ta có: 
horse(X), mother(X, Y), fast(Y)
mother(tom, Y), fast(Y) 
fast(bin) 
valueable(tom) 
fast(ken) 
mother(ken, Y), fast(Y) mother(kit, Y), fast(Y) mother(bin, Y), fast(Y)
fast(kit)
X/tom, (2) 
X/ken, (3) X/kit, (4)
X/bin, (5) 
valueable(bin)
Y/bin, (6) Y/ken, (7) Y/kit, (8)
(10) (9)
 66
 3.2.4.2 Suy diễn lùi/ Lập Luận lùi 
Kỹ thuật suy diễn tiến là tốt khi làm việc với bài toán bắt đầu từ các thông 
tin và cần suy lý một cách logic đến các kết luận. Trong bài toán loại khác, 
người ta bắt đầu từ các giả thuyết định chứng minh rồi tiến hành thu thập thông 
tin. Chẳng hạn bác sĩ nghi người bệnh bị bệnh nào đó, ông ta tìm ra triệu chứng 
của bệnh đó. Loại suy lý này được mô hình hóa trong trí tuệ nhân tạo như hệ 
chuyên gia với tên là "Suy diễn lùi". 
Suy diễn lùi là chiến lược suy diễn để chứng minh một giả thiết bằng cách 
thu thập thông tin hổ trợ. 
Hệ thống suy diễn lùi bắt đầu từ đích cần chứng minh: 
Trước hết nó kiểm tra trong bộ nhớ làm việc để xem đích này đã được bổ 
sung trước đó chưa. Bước này cần thiết vì cơ sở tri thức khác có thể đã chứng 
minh đích này. 
Nếu đích chưa hề được chứng minh, nó tìm các luật có phần THEN chứa 
đích. Luật này gọi là luật đích. 
Hệ thống xem phần giả thiết của các luật này có trong bộ nhớ làm việc 
không. Các giả thiết không được liệt kê trong bộ nhớ gọi là các đích mới, hoặc 
đích con, cần được chứng minh. Các đích con này được cung cấp, tức giải, nhờ 
các luật khác. 
Quá trình này tiếp tục đệ qui cho đến khi hệ thống tìm thấy một giả thiết 
không được luật nào cung cấp. Đó là một "sơ khởi". Sơ khởi là giả thiết của một 
luật mà không do luật nào kết luận. 
 67
Khi thấy sơ khởi hệ thống yêu cầu người sử dụng các thông tin về nó. Hệ 
thống dùng các thông tin này để giải đích con và đích ban đầu. Suy diễn lùi thực 
hiện tương tự như cách con người kiểm tra một giả thiết có đúng không. 
Gọi Hyp là danh sách các giả thiết cần chứng minh. Ta coi mỗi một câu hỏi 
là một giả thuyết Hyp = H1^H2^.. ^ Hn, thì ta có danh sách hyp = [H1, H2, .. 
,Hn] 
Với mỗi luật R: nếu P1 và P2 và Pn thì Q ta tách luật này ra thành hai 
phần: danh sách các điều kiện và phần kết luận. Ta ký hiệu danh sách các điều 
kiện của luật là Conds=[P1, P2, .., Pn] và phần kết luận của luật được ký hiệu là 
Conc = Q. 
Ta coi các sự kiện là các luật có phần điều kiện là một danh sách rỗng. 
Cơ chế suy diễn lùi được mô tả như thủ tục sau đây: 
Procedure Backchain(Hyp, θ) 
Begin 
H Í giả thiết đầu tiên trong danh sách Hyp 
For each Luật R(Conds, Q) do 
{ 
If H hợp nhất với Q bởi phép thế θ1 then 
 { 
 Hyp1 = Hyp - H 
 Hyp1 = Hyp1 + Conds 
Hyp1 = Hyp1θ1 
 θ’=θ + θ1 
If Hyp1 = rỗng then 
Write(θ’) 
Else 
BackChain(Hyp1, θ’); 
 } 
} 
End; 
 68
Ví dụ: 
Giả sử tri thức chứa các sự kiện sau: 
(1) horse(tom) 
(2) horse(ken) 
(3) horse(kit) 
(4) horse(bin) 
(5) mother(tom, bin) 
(6) mother(tom, ken) 
(7) mother(bin, kit) 
(8) fast(kit) 
(9) winner(bin) (bin thắng cuộc) 
Luật: 
 (10) horse(X)^ mother(X, Y)^ fast(Y) => valueable(X) 
(11) winner(X) => fast(X) (Con ngựa nào thắng cuộc thì con ngựa đó chạy 
nhanh) 
Câu hỏi đặt ra là: Con ngựa nào có giá? 
Giả thuyết ban đầu : Hyp = valueable(W), θ = [] 
HYP = VALUEABLE(W), θ = [] 
HYP = [ MOTHER(TOM, Y), FAST(Y)] 
θ = [W/TOM] 
HYP = [HORSE(X), MOTHER(X, Y), 
FAST(Y)] 
HYP = [FAST(BIN)] 
θ = [W/TOM, 
HYP = [WINNER(BIN)] 
θ = [W/TOM, Y/BIN, 
HYP = [MOTHER(KEN, Y),
FAST(Y)] 
θ = [W/KEN] 
HYP = [ 
MOTHER(KIT, Y), 
FAST(Y)] 
θ = [W/KIT]
HYP = [MOTHER(BIN, Y), FAST(Y)]
θ = [W/BIN] 
HYP = [FAST(KIT)] 
θ = [W/BIN, Y/KIT]
H =[] 
θ1 = [W/X], (10) 
θ1 = [X/TOM], (1) θ1 = [X/KEN], (2) θ1 = [X/KIT], (3) θ1 = [X/BIN], (4) 
θ1 = [Y/BIN], (5) 
θ1 = [Z/BIN], 
(11)
θ1 = [Y/KIT], (7) 
θ1 = [], 
(8)
 69
Chú ý: Do trong thời gian ngắn, cộng thêm việc phải có đề cương tiếng Việt cho sinh viên 
tham khảo nên tài liệu này được tổng hợp từ một số nguồn khác nhau, trong đó một phần 
không nhỏ được lựa chọn trong cuốn “Trí tuệ nhân tạo” của thầy Đinh Mạnh Tường. 
Cuốn tiếng Anh: Russell and S.Norvig, Artificial intelligence: Modenrn approach, Prentice-
Hall, 3rd edition, 2003 là rất đầy đủ và hay!