CHƯƠNG 6 – CÁC PHƯƠNG PHÁP LẬP LUẬN TRÊN LOGIC MỆNH ĐỀ

3. Bài toán lập luận và các giải thuật lập luận trên logic mệnh đề

Như đã nói trong phần 1 của Chương này, lập luận là trả lời câu hỏi một câu q có là đúng khi cho cơ sở tri thức (là một câu phức là hội của tập các câu cho trước) là đúng hay không (KB╞ q)? Một cách đơn giản nhất là chúng ta lập bảng giá trị chân lý cho KB và cho q và kiểm tra xem tất cả các trường hợp làm cho KB nhận giá trị true cũng làm cho q nhận giá trị true không? Nếu có thì ta kết luận KB╞ q, ngược lại thì kết luận là không. Phương pháp suy luận này gọi là phương pháp liệt kê và có thể thuật toán hóa được (chi tiết xem trong mục 6 của Chương này). Một cách tiếp cận khác để trả lời cho câu hỏi KB╞ q là sử dụng các luật hằng đúng của logic mệnh đề (xem trong mục 2.4). Ban đầu KB bao gồm tập các câu (hội của các câu), chúng ta áp dụng các luật của logic mệnh đề trên tập các câu này để sinh ra câu mới, rồi bổ sung câu mới này vào KB, lặp lại áp dụng luật của logic và sinh ra câu mới, v.v., đến khi nào xuất hiện câu q trong KB thì dừng lại (khi đó KB╞ q) hoặc không thể sinh ra câu mới nào nữa từ KB (khi này ta kết luận KB không suy ra được q) Lời giải cho bài toán suy diễn theo cách này là một đường đi từ trạng thái đầu đến trạng thái đích của bài toán tìm đường sau: 9 Trạng thái đầu: KB 9 Các phép chuyển trạng thái: các luật trong logic mệnh đề, mỗi luật x áp dụng cho KB sinh ra câu mới x(KB), bổ sung câu mới này vào KB được trạng thái mới KB ∧ x(KB) 9 Trạng thái đích: trạng thái KB chứa q 9 Chi phí cho mỗi phép chuyển: 1 Vì số luật hằng đúng trong logic mệnh là tương đối lớn nên nhân tố nhánh của bài toán trên cũng là lớn (tất cả các cách áp dụng các luật trên tập con tất cả các câu của KB), vì vậy không gian tìm kiếm lời giải của bài toán trên là rất lớn. Để hạn chế không gian tìm kiếm lời giải của bài toán, chúng ta biểu diễn KB và q bằng chỉ các câu dạng chuẩn hội (xem mục 4), khi đó chúng ta chỉ cần áp dụng một loại luật là luật phân giải trên KB và mỗi phép chuyển là một phép phân giải hai câu có chứa ít nhất một literal là phủ định của nhau trong KB, kết quả của phép phân giải hai câu dạng chuẩn hội lại là một câu dạng chuẩn hội và được bổ sung vào KB, lặp lại áp dụng luật phân giải trên KB đến khi nào KB chứa câu q thì dừng. Chi tiết thuật toán suy diễn dựa trên luật phân giải KB╞ q được trình bày trong mục 7 của Chương này (thực tế thì thuật toán suy diễn phân giải trả lời bài toán tương đương (KB ∧ ¬q)╞ [].) Giải thuật suy diễn phân giải là giải thuật đầy đủ trong logic mệnh đề, tức là với mọi câu q mà kéo theo được từ KB (q đúng khi KB đúng) thì sử dụng giải thuật suy diễn phân giải đều có thể suy diễn được KB ╞ q (tức là không có câu nào kéo được từ KB là không suy diễn phân giải được); bởi vì bất cứ câu trong logic mệnh đề đều có thể biểu diễn được bằng câu dạng chuẩn hội (xem mục 4). Do liên tục phải bổ sung các câu mới vào KB và lặp lại tìm kiếm các cặp câu có thể phân giải với nhau được nên nhân tố nhánh của cây tìm kiếm lời giải tăng dần theo độ sâu của cây tìm kiếm. Vì vậy không gian và thời gian của giải thuật sẽ tăng rất nhanh, giải thuật phân giải làm việc không hiệu quả. Để khắc phục nhược điểm này, người ta tìm cách biểu diễn KB dạng các câu Horn và áp dụng chỉ một loại luật (tam đoạn luận, xem mục 5) để suy diễn (tam đoạn luận áp dụng trên 2 câu dạng Horn và sinh ra câu mới cũng là câu dạng Horn). Thuật giải suy diễn tiến/lùi trên cơ sở tri thức dạng Horn trình bày chi tiết trong mục 8, nó có độ phức tạp tuyến tính đối với số câu trong KB. Tuy nhiên thuật giải suy diễn tiến/lùi lại là không đầy đủ trong logic mệnh đề, bởi vì có những câu trong logic mệnh đề không thể biểu diễn được dưới dạng Horn để có thể áp dụng được giải thuật suy diến tiến/lùi.