Bài giảng Trí tuệ nhân tạo - Phần 5

 E	(4) F	(5) Giả sử cần chứng minh C? Tiên đề: Các công thức đã cho Định lý: các công thức được suy ra Chứng minh: dãy các luật được áp dụng để dẫn tới định lý II. Logic mệnh đề7. Định lý phân giải - Câu phân giải được: Nếu có thể áp dụng luật phân giải cho các câu đó - Giải thức: Kết quả nhận được khi áp dụng luật phân giải cho các câu - Câu rỗng: giải thức của hai câu đối lập nhau P và P, ký hiệu □ - G là tập các câu tuyển, R(G) là tập câu bao gồm các câu thuộc G và tất cả các câu nhận được từ G bằng một dãy áp dụng luật phân giải. A. Định lý phân giải: Một tập câu tuyển là không thỏa được nếu và chỉ nếu câu rỗng □R(G) Một tập luật suy diễn là đầy đủ nếu mọi hệ quả logic của một tập các tiên đề đều chứng minh được bằng cách chỉ sử dụng các luật của tập đó II. Logic mệnh đềB. Thủ tục phân giải Procedure Resolution; Input: G={các câu tuyển}; Begin 1. Repeat 1.1 Chọn hai câu A, B G; 1.2 If A và B phân giải được then tính Res(A,B); 1.3 If Res(A,B) là câu mới then thêm Res(A,B) vào G; Until nhận được câu rỗng hoặc không có câu mới nào xuất hiện; 2. If nhận được câu rỗng then thông báo G không thỏa được else thông báo thỏa được; End; II. Logic mệnh đềB. Thủ tục phân giải Sử dụng luật phân giải ta có thể chứng minh được một công thức bất kì có là hệ quả của một tập công thức đã cho hay không bằng phương pháp chứng minh bác bỏ. Vì vậy luật phân giải được xem là luật đầy đủ cho bác bỏ. II. Logic mệnh đề9. Chứng minh bác bỏ Ví dụ: Giả giử G là tập hợp các câu tuyển sau 	 A ∨  B ∨ P 	(1) 	 C ∨  D ∨ P 	(2) 	 E ∨ C 	(3) 	A 	(4) 	E 	(5) 	D 	(6) 	Giả sử ta cần chứng minh P. Thêm vào G câu sau: 	 P 	(7) 	áp dụng luật phân giải cho câu (2) và (7) ta được câu: 	C ∨ D 	(8) 	Từ câu (6) và (8) ta nhận được câu: 	C 	(9) 	Từ câu (3) và (9) ta nhận được câu: 	 E 	(10) 	Từ câu (5) và (10) ta nhận được câu rỗng 	Vậy P là hệ quả logic của các câu (1) --(6). III. Logic vị từ cấp một1. Cú pháp Các ký hiệu: Hằng: a, b, c,… Biến: x, y, z,… Vị từ: P, Q, R, Thích, yêu… Vị từ n biến p(x1, …, xn) Vị từ không biến là mệnh đề Hàm: f, g, Bố, mẹ, … f(x1, …, xn) - hàm n biến Liên kết logic:  (hội),  (tuyển),  (phủ đinh),  (kéo theo),  (tương đuơng Lượng từ:  (với mọi),  (tồn tại) Dấu phảy, đóng mở ngoặc III. Logic vị từ cấp một1. Cú pháp (tiếp) Các hạng thức: Các ký hiệu hằng và biến Nếu t1, …, tn là các hạng thức, f là hàm n biến, thì f(t1, …, tn) là hạng thức Công thức phân tử (câu đơn): Các vị từ không biến (mệnh đề) Nếu t1, …, tn là các hạng thức, P là vị từ n biến, thì P(t1, …, tn) là công thức phân tử Chẳng hạn, Hoa là một ký hiệu hằng, Love là một vị từ của hai biến, husband là hàm của một biến, thì Love(Hoa, husband(Hoa)) là một công thức phân tử. III. Logic vị từ cấp một1. Cú pháp (tiếp) Công thức: Các công thức phân tử là công thức Nếu P, Q là các công thức thì PQ, PQ, P, PQ, PQ là các công thức Nếu P là công thức, x là biến thì xP, xP là các công thức. Literal: công thức phân tử hoặc phủ định của công thức phân tử Công thức đóng: công thức mà tất cả các biến đều là biến bị buộc Biến bị buộc x nếu trong công thức có dạng xP hoặc xP, còn lại là biến tự do Ví dụ: x P(x, f(x,y))  x Q(x) III. Logic vị từ cấp một2. Ngữ nghĩa Trong một diễn giải: Hằng → đối tượng cụ thể Hàm → hàm cụ thể Ngữ nghĩa của các câu đơn 	Ví dụ: Sinhviên(Lan) Ngữ nghĩa các câu phức Ví dụ: Sinhviên(Lan)  Thích(Lan, Bóngđá) Ngữ nghĩa các câu chứa lượng từ xP : ngữ nghĩa của công thức là hội của tất cả các công thức nhận được từ P bằng cách thay x bởi một đối tượng trong miền xP: ngữ nghĩa của công thức là tuyển của tất cả các công thức nhận được từ P bằng cách thay x bởi một đối tượng trong miền III. Logic vị từ cấp một3. Công thức tương đương x P(x) ≡ y P(y) 	x P(x) ≡ y P(y) (x P(x)) ≡x(P(x)) 	(x P(x) ≡x(P(x)) x (P(x)  Q(x)) ≡ x P(x) x Q(x) 	x (P(x)  Q(x)) ≡ x P(x)  x Q(x) Ví dụ: x Thích(x, Chồng(x)) ≡ y Thích(y, Chồng(y)) III. Logic vị từ cấp một4. Chuẩn hóa công thức Loại bỏ kéo theo 	PQ bởi PQ Chuyển  tới các phân tử 	(P) ≡ P 	(PQ) ≡ PQ 	(PQ) ≡ PQ 	(x P(x)) ≡ x(P(x)) 	(x P(x) ≡ x(P(x)) Loại bỏ lượng tử  Loại bỏ lượng tử  Chuyển các tuyển tới các literal Loại bỏ hội Đặt tên lại các biến III. Logic vị từ cấp một VD Chuẩn hóa công thức Loại bỏ : Giả sử P(x,y) là các vị từ có nghĩa: “y lớn hơn x” trong miền các số. Khi đó, công thức∀x (∃y (P(x,y)) có nghĩa là “với mọi số x, tồn tại y sao cho số y lớn hơn x”. Có thể xem y trong công thức đó là hàm của đối số x. Chẳng hạn, loại bỏ lượng tử ∃y, công thức đang xét trở thành ∀x(P(x,f(x))). Câu hỏi: Loại bỏ  trong công thức sau: ∀x (∃y (P(x,y) ∨ ∀u (∃v (Q(a, v) ∧ ∃y  R(x,y))) (1) Logic vị từ cấp mộtVD Chuẩn hóa công thức * Loại bỏ lượng tử  (lượng tử phổ dụng) ở CT (2): ∀x (P(x,f(x)) ∨ ∀u (Q(a,g(x,u)) ∧  R(x,h(x,u)))) (2) KQ: P(x,f(x)) ∨ (Q(a,g(x,u)) ∧  R(x,h(x,u))) (3) * Chuyển các tuyển tới các literal : Thay các công thức dạng: P∨(Q∧R) bởi (P∨Q)∧(P∨R) Thay (P∧Q)∨R bởi (P∨Q) ∧(P∨R). Sau bước này công thức trở thành hội của các câu tuyển nghĩa là ta nhận được các công thức ở dạng chuẩn tắc hội. Chẳng hạn, câu (3) được chuyển thành công thức sau (P(x,f(x)) ∨ (Q(a,g(x,u))) ∧ (P(x,f(x)) ∨  R(x,h(x,u))) (4) • Loại bỏ các hội: Một câu hội là đúng nếu và chỉ nếu tất cả các thành phần của nó đều đúng. Do đó công thức ở dạng chuẩn tắc hội tương đương với tập các thành phần. Chẳng hạn, câu (4) tương đương với tập hai câu tuyển sau P(f(x)) ∨ (Q(a,g(x,u)) P(f(x)) ∨  R(x,h(x,u)) (5) • Đặt tên lại các biến: Đặt tên lại các biến sao cho các biến trong các câu khác nhau có tên khác nhau, chẳng hạn, hai câu (5) có hai biến cùng tên là x, ta cần đổi tên biến x trong câu hai thành z, khi đó các câu (5) tương đương với các câu sau : P(f(x)) ∨ (Q(a,g(x,u)) P(f(x)) ∨  R(x,h(x,u)) (5’) Logic vị từ cấp mộtVD Chuẩn hóa công thức III. Logic vị từ cấp một5. Các luật suy diễn Luật thay thế phổ dụng (universal instatiation) 	 x P 	P[x/t] VD: từ câu ∀x Like(x, Football) bằng cách thay x bởi An ta suy ra câu Like(An,Football) Hợp nhất: Dùng phép thế để hợp nhất các câu Phép thế θ = [x1/t1 ... xn/tn] (xi : biến, ti: hạng thức) Ví dụ: θ = [x/b, y/g(z)], P(x,y,f(a,x))θ = P(b,g(z),f(q,b)) Hợp nhất được: Nếu tồn tại phép thế θ cho 2 câu phân tử P và Q sao cho Pθ =Qθ, thì P và Q là hợp nhất được và θ là hợp nhất tử 	Ví dụ: Thích(An, y) và Thích(x, Bóngđá) là hợp nhất được với θ = [x/An, y/Bóngđá] III. Logic vị từ cấp một5. Các luật suy diễn (tiếp) a. Luật Modus Ponens tổng quát 	(P1 … Pn  Q), Pi’, …, Pn’ 	 Q’ Trong đó Q’= Qθ, Pi, Pi’, Q: các công thức phân tử, Pi θ = Pi’ θ Ví dụ: Giả sử ta có các câu (Student (x) ∧ Male (x) ⇒ Like (x,Football)) và Student(Anh), Male(Anh). Với phép thế θ = [x|Anh], các cặp câu Student(x),Student(Anh) và Male(x), Male(Anh) hợp nhất được.Do đó ta suy ra câu Like(Anh,Football). III. Logic vị từ cấp một5. Các luật suy diễn (tiếp) b. Luật phân giải tổng quát - Phân giải trên các câu tuyển : Giả sử ta có hai câu tuyển A1∨…∨ Am ∨ C và B1 ∨…∨ Bn ∨D, trong đó Ai (i =1,..,m) và Bj (j=1,..,n) là các literal, còn C và D là các câu phân tử có thể hợp nhất được bởi phép thế θ, Cθθ=Dθ. Khi đó ta có luật: 	A1 … Am C, B1… Bn D 	A’1 …A’mB’1…B’n 	A’i= Aiθ (i=1,..,m), B’j= Bjθ (j=1,..,n) Ví dụ: Giả sử ta có hai câu A=Hear(x,Music)∨ Play(x,Tennis) và B=Play(An,y) ∨ Study (An). Hai câu Play(x,Tennis) và Play(An,y) hợp nhất được bởi phép thế θ=[x|An,y|Tennis]. Do đó từ hai câu đã cho, ta suy ra câu Hear(An,Music) ∨ Study (An). Trong ví dụ này, hai câu A=Hear(x,Music) ∨ Play(x,Tennis) và B=  Play(An,y) ∨ Study (An) là phân giải được và phân giải thức của chúng là Hear(An,Music)∨ Study(An). III. Logic vị từ cấp một5. Các luật suy diễn (tiếp) b. Luật phân giải tổng quát - Phân giải trên các câu Horn: Câu Horn (luật If-Then) là các câu có dạng P1∧…∧ Pm ⇒ Q trong đó Pi(i =1,...,m; m ≥ 0) và Q là các câu phần tử. Giả sử S và T là hai câu phân tử, hợp nhất được bởi phép thế θ. Khi đó ta có luật: 	 P1 … Pn , S Q, T 	 P1’ … Pn’  Q’ Ví dụ: Xét hai câu Student(x) ∧ Male(x) ⇒ Play(x,Football) và Male(Ba). Hai câu Male(Ba) và Male(x) hợp nhất được với phép thế [x|Ba], do đó từ hai câu trên ta suy ra Student (Ba) ⇒ Play (Ba, Football). III. Logic vị từ cấp một5. Các luật suy diễn (tiếp) - Luật phân giải tổng quát Phân giải trên các câu tuyển 	A1 … Am C, B1… Bn D 	A’1 …A’mB’1…B’n 	A’i= Aiθ (i=1,..,m), B’j= Bjθ (j=1,..,n) Phân giải trên các câu Horn 	P1 … Pn  Q 	 T 	P1’ … Pn’  Q’ III. Logic vị từ cấp một6. Chứng minh bằng luật phân giải Chứng minh công thức H là hoặc không là hệ quả logic của tập công thức G bằng luật phân giải Procedure Proof_by_Resolution Input G (các tiên đề) 	 	H – công thức cần chứng minh; Begin 	1. Biến đổi Gi,H về dạng chuẩn hội; 	2. Thành lập các câu tuyển C từ bước 1; 	3. Repeat 	3.1 Chọn 2 câu A, B từ C; 	3.2 If A, B phân giải được then tính Res(A, B); 	3.3 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 nhận được câu rỗng then thông báo H đúng else H sai; End; III. Logic vị từ cấp một 7. Sử dụng logic vị từ cấp 1 để biểu diễn tri thức Logic vị từ cấp một cho phép chúng ta biểu diễn các đối tượng trong thế giới hiện thực với các tính chất của chúng và các mối quan hệ giữa chúng. Để biểu diễn tri thức của chúng ta về một miền đối tượng nào đó trong logic vị từ cấp một, trước hết chúng ta cần đưa ra các kí hiệu: các kí hiệu hằng (hằng đối tượng) để chỉ ra các đối tượng cụ thể; các kí hiệu biến để chỉ các đối tượng bất kỳ trong miền đối tượng; các kí hiệu hàm để biểu diễn các quan hệ hàm; các kí hiệu vị từ để biểu diễn các mối quan hệ khác nhau giữa các đối tượng. Các kí hiệu được đưa ra đó tạo thành hệ thống từ vựng về miền đối tượng mà chúng ta đang quan tâm. Sử dụng các từ vựng đã đưa ra, chúng ta sẽ tạo ra các câu trong logic vị từ cấp một để biểu diễn tri thức của chúng ta về miền đối tượng đó. Tập hợp tất cả các câu được tạo thành sẽ lập nên cơ sở tri thức trong hệ tri thức mà chúng ta mong muốn xây dựng.