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

6. Thuật toán suy diễn dựa trên bảng giá trị chân lý

Trong các phần còn lại của Chương này, chúng ta sẽ xây dựng các giải thuật cài đặt cho máy tính để nó biết lập luận. Giải thuật lập luận tự động là giải thuật chỉ ra rằng nếu KB (cơ sở tri thức) là đúng thì câu truy vấn q có đúng hay không? Phương pháp lập luận đầu tiên là dựa liệt kê các tất cả các trường hợp có thể có của tập các ký hiệu mệnh đề, rồi kiểm tra xem liệu tất cả các trường hợp làm cho KB đúng xem q có đúng không. Chi tiết thuật giải như bảng sau: Function Suydien_Lietke(KB, q) return true or false symbols=get_list_of_symbols(KB,q); n=symbols.size(); int bộ_giá_trị[n]; //dùng để lưu bộ các giá trị logic (true:1, false:0) for (i=1; i≤2

ⁿ

; i++) { bộ_giá_trị [1,..,n]=generate(i); // sinh ra bộ thứ i if (evaluate(KB, bộ_giá_trị)==true && evaluate(q, bộ_giá_trị)=false) return false return true; Thuật giải trên là sinh ra toàn bộ bảng giá trị chân lý để đánh giá KB và q, nếu chỉ cần một trường hợp KB đúng mà q sai thì q sẽ kết luận KB không suy diễn được ra q. Giải thuật trên có độ phức tạp thời gian là 2

ⁿ

* m, với n là số ký hiệu có trong KB,q và m độ dài câu trong KB.