网站设计与管理方向上海市城乡建设部网站首页
一.命题逻辑基础——基本等值式
①交换率
p∨q <=> q∨p
p∧q <=> q ∧p
②结合率
(p∨q)∨r<=> p∨(q∨r)
(p ∧q)∧r<=> p ∧(q∧r)
③分配率
p∨(q∧r)<=>(p∨q)∧(p∨r)
p∧(q∨r)<=>(p∧q)∨(p∧r)
④摩根率
～ (p∨q) <=> ～ p ∧～ q
～ (p∧q) <=> ～ p ∨ ～ q
⑤吸收率
p∨(p∧q ) <=>p
p∧(p∨q )<=>p
⑥同一律
p∨0 <=> p
p∧1 <=> p
⑦蕴含等值式
p→q<=>～p∨q
⑧假言易位式
p→q<=>～p→～q
二.消解原理
1.消解推理技术
已知两子句L1∨α和～L2∨β ，如果L1和L2具有最一般合一者σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β) σ。
这个新子句叫做消解式，它是由取这两个子句的折取，然后消去互补对而得到的。
2.消解推理常用规则
| 父辈子句 | 消解式 |
|---|---|
| p 和 ~ p ∨ q (即p → q) | q |
| p ∨ q和 ~ p ∨ q | q |
| p ∨ q和p ∨ ~ q | q ∨ ~q 或 p ∨ ~p |
| ~ p ∨ p | NIL |
| ~ p ∨ q (即p→q) 和~ q ∨ r (即q→r) | ~ p ∨ r (即p→r) |
| B(x)和 ~ B(x) ∨ C(x) | C(x) |
| P(x,f(y)) ∨ Q(x) ∨ R(f(y)) | P(f(y)), σ=(f(y)/x) |
| P(x,f(y)) ∨ Q(x) ∨ R(f(y))和~ P(f(f(a)),z) ∨ R(z,w) | Q(f(f(a)) ∨ R(f(a)) ∨ R(f(y),w),σ=f(f(a))/x,f(y)/z) |
3.消解反演
(1)否定L，得～L；
(2)把～L添加到S中去；
(3)把新产生的集合｛～L，S｝化成子句集；
(4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。
例题：快乐学生问题
假设：任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。
解：先将问题用谓词表示如下&