tailieunhanh - Loại bỏ luật thừa

b. Kiểm tra mâu thuẫn và vòng lặp suy diễn Thêm luật (1) A, F ® ù E vào CSTT luật R Kiểm tra mâu thuẫn: (A, F)+ R’ = {A, F, E, H, C, B} có chứa E. Vậy thêm A, F ® ùE vào tập R sẽ nảy sinh mâu thuẫn luật. (R’ là R thêm luật (1)) Kiểm tra vòng lặp suy diễn: không nảy sinh vòng lặp suy diễn khi thêm A, F ® ùE vào tập R (tính (VP(ri)+ R’ )) Thêm luật (2) F ® A vào CSTT luật R Kiểm tra mâu thuẫn: (F)+ R’ = {F, } không chứa ùA. Vậy không thể nảy sinh. | 1. Cho tập luật R như sau: R = { r1: A, C B; r2: B, D E, D; r3: G, H K; r4: F, H E; r5: F H; r6: B F; r7: F C; } Loại bỏ những luật thừa trong R (nếu có). Kiểm tra xem có nảy sinh mâu thuẫn và vòng lặp suy diễn hay không khi lần lượt thêm các luật sau vào R: (1) A, F E (2) F A Thuật toán loại bỏ luật thừa B1 : Rút gọn vế phải r R A {Vếphải(r)} Nếu A {Vếtrái(r)+{R\{r}}U{r’} }thì Loại A ra khỏi vế phải của r. (r’: Vếtrái(r) Vếphải(r)\{A} ) Nếu Vếphải(r) là rỗng thì loại r ra khỏi tập luật Cuối Cuối . B2 : Phân rã các luật: r: X1 X2 Xn Y trong R R := R { Xi Y } (i:1n) R := R \ {r} B3 : Loại bỏ luật thừa: r R Nếu {Vếphải(r)} {(Vếtrái(r)+ R\{r})} thì R = R\{r} Cuối B4 : Rút gọn vế trái r có dạng X : A1 A2, , An Y thuộc R Ai X (vế trái của r) Nếu VP(r) {(X\{Ai})+R} thì X := X \ {Ai} Cuối Cuối Gợi ý bài giải Bài 1. a. Loại bỏ luật thừa Rút gọn vế phải: r2 r2’ : B, D E; Luật thừa: Để loại luật ri nào đó ta . | 1. Cho tập luật R như sau: R = { r1: A, C B; r2: B, D E, D; r3: G, H K; r4: F, H E; r5: F H; r6: B F; r7: F C; } Loại bỏ những luật thừa trong R (nếu có). Kiểm tra xem có nảy sinh mâu thuẫn và vòng lặp suy diễn hay không khi lần lượt thêm các luật sau vào R: (1) A, F E (2) F A Thuật toán loại bỏ luật thừa B1 : Rút gọn vế phải r R A {Vếphải(r)} Nếu A {Vếtrái(r)+{R\{r}}U{r’} }thì Loại A ra khỏi vế phải của r. (r’: Vếtrái(r) Vếphải(r)\{A} ) Nếu Vếphải(r) là rỗng thì loại r ra khỏi tập luật Cuối Cuối . B2 : Phân rã các luật: r: X1 X2 Xn Y trong R R := R { Xi Y } (i:1n) R := R \ {r} B3 : Loại bỏ luật thừa: r R Nếu {Vếphải(r)} {(Vếtrái(r)+ R\{r})} thì R = R\{r} Cuối B4 : Rút gọn vế trái r có dạng X : A1 A2, , An Y thuộc R Ai X (vế trái của r) Nếu VP(r) {(X\{Ai})+R} thì X := X \ {Ai} Cuối Cuối Gợi ý bài giải Bài 1. a. Loại bỏ luật thừa Rút gọn vế phải: r2 r2’ : B, D E; Luật thừa: Để loại luật ri nào đó ta cần tính bao đóng nếu có chứa VP(ri) thì khi đó ta có thể loại luật ri. Loại r2’ do (B, D)+R\{r2’} = {B, D, F, H, E, C} có chứa E. Tương tự ta có r1, r3, r4, r5, r6, r7 không thể loại bỏ. RRút gọn vế trái R = {r1, r3, r4, r5, r6, r7} - Xét r1: Không thể rút gọn - Xét r2: Không thể rút gọn - Xét r3: Không thể rút gọn Xét r4: Loại H ra khỏi VT(r4: F, H E) do (F)+R chứa E. r4 r4’: F E Vậy sau khi loại bỏ luật thừa cho kết quả tập luật R như sau: R = { r1: A, C B; r3: G, H K; r4’: F E; r5: F H; r6: B F; r7: F C;} b. Kiểm tra mâu thuẫn và vòng lặp suy diễn Thêm luật (1) A, F E vào CSTT luật R Kiểm tra mâu thuẫn: (A, F)+R’ = {A, F, E, H, C, B} có chứa E. Vậy thêm A, F E vào tập R sẽ nảy sinh mâu thuẫn luật. (R’ là R thêm luật (1)) Kiểm tra vòng lặp suy diễn: không nảy sinh vòng lặp suy diễn khi thêm A, F E vào tập R (tính (VP(ri)+R’ )) Thêm luật (2) F A vào CSTT luật R Kiểm tra mâu thuẫn: (F)+R’ = {F, } không chứa A. Vậy không thể nảy sinh mâu thuẫn luật khi thêm F A vào R. Kiểm tra vòng lặp suy diễn: R = { r1: A, C B; r3: G, H K; r4’: F E; r5: F H; r6: B F; r7: F C;} Ta có: F A (thêm mới) F C (r7) F A, C Mà ta có A, C B (r1) suy ra có F B. Trong R ta có B F. Như vậy khi thêm F A vào R có nguy cơ tạo ra vòng lặp trong quá trình suy diễn.