Inference Rules - Các luật suy luận

Model Checking có thể chứng minh entailment bằng cách thử các model. Một hướng khác là biến đổi trực tiếp các sentence bằng những inference rule - luật suy luận đã được chứng minh là hợp lệ.

Ví dụ rất quen thuộc:

Nếu nộp bài muộn thì bị trừ điểm.
An nộp bài muộn.
=> An bị trừ điểm.

Ta không cần liệt kê mọi cách gán True/False cho tất cả symbol để có kết luận này.

Mục tiêu

Sau bài này, bạn cần:

dùng được Modus Ponens và And Elimination;
hiểu double negation, implication elimination và biconditional elimination;
dùng đúng De Morgan và distributive laws;
nhận ra một proof có thể được xem như một search problem;
tránh các lỗi suy luận do đảo chiều implication hoặc biến đổi sai NOT.

Inference Rules - suy luận không cần thử mọi model

Inference rule nhận một số premise và tạo ra conclusion.

Có thể hình dung:

premise 1
premise 2
---------
conclusion

Mục tiêu là sinh tri thức mới trực tiếp từ tri thức cũ.

Modus Ponens

Luật:

\frac{P \to Q,\;P}{Q}

Đọc:

Nếu P thì Q.
P đúng.
=> Q đúng.

Ví dụ:

Nếu có lịch thi thì hệ thống gửi thông báo.
Hôm nay có lịch thi.
=> Hệ thống gửi thông báo.

Đây là một trong những rule nền tảng nhất của suy luận logic.

And Elimination

Từ:

P \land Q

có thể suy ra:

P

và cũng có thể suy ra:

Q

Ví dụ:

An đã nộp bài và An đã check-in.
=> An đã nộp bài.
=> An đã check-in.

Double Negation Elimination

Từ:

\neg\neg P

suy ra:

P

Ví dụ:

Không đúng rằng An không vượt qua bài kiểm tra.
=> An vượt qua bài kiểm tra.

Implication Elimination

Một implication có thể chuyển thành OR:

P \to Q \equiv \neg P \lor Q

Đây không chỉ là mẹo ghi nhớ. Nó rất quan trọng khi chuyển công thức về CNF cho Resolution.

Biconditional Elimination

P \leftrightarrow Q

được thay bằng:

(P \to Q) \land (Q \to P)

Nếu tiếp tục loại implication:

(\neg P \lor Q) \land (\neg Q \lor P)

De Morgan’s Laws

Hai luật cần nhớ:

\neg(P \land Q) \equiv \neg P \lor \neg Q

\neg(P \lor Q) \equiv \neg P \land \neg Q

Ví dụ:

Không đúng rằng cả An và Bình đều đi học.

Có thể viết:

\neg(An \land Binh)

Tương đương:

\neg An \lor \neg Binh

Nghĩa là ít nhất một người không đi học.

Sai lầm phổ biến với De Morgan

Sai:

\neg(P \land Q) = \neg P \land \neg Q

Đúng:

\neg(P \land Q) = \neg P \lor \neg Q

Khi đẩy NOT vào trong ngoặc, AND và OR đổi cho nhau.

Distributive Laws

Logic cũng có dạng phân phối gần giống đại số.

P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)

và:

P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)

Luật thứ hai đặc biệt quan trọng khi chuyển sang CNF.

Inference cũng có thể nhìn như Search

Ta có thể mô hình hóa quá trình chứng minh như một search problem:

Thành phần Search	Trong suy luận
Initial state	Knowledge Base ban đầu
Actions	các inference rule có thể áp dụng
Transition model	KB sau khi thêm kết luận mới
Goal test	query đã được chứng minh chưa
Path cost	số bước suy luận hoặc chi phí proof

Điều này nối lại với phần Search: proof cũng có thể xem là một đường đi trong không gian các trạng thái tri thức.

Ví dụ ghép nhiều rule

Giả sử:

P: An đã đăng ký môn AI.
Q: An đã đóng học phí.
R: An được thêm vào lớp LMS.
S: An xem được tài liệu môn học.

Knowledge Base có:

P \land Q

(P \land Q) \to R

R \to S

Ta có thể suy luận theo chuỗi:

từ $P \land Q$ , lấy ra $P$ và $Q$ bằng And Elimination;
dùng $(P \land Q) \to R$ để suy ra $R$ ;
dùng $R \to S$ để suy ra $S$ .

Đây là một proof gồm nhiều bước. Mỗi bước phải dùng một rule hợp lệ.

Chốt lại

Inference Rules cho phép đi từ facts và rules hiện có sang facts mới mà không cần duyệt toàn bộ truth assignments. Tuy nhiên, để xây một cơ chế chứng minh tổng quát hơn, ta cần chuẩn hóa câu logic và có một rule có thể áp dụng lặp lại. Đó là vai trò của Resolution.

Bản tiếng Anh đang soạn.