归结反演

54 阅读 0 评论 36 点赞

我是靠谱客的博主自信耳机，最近开发中收集的这篇文章主要介绍归结反演，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

归结反演

1、每个去临潼游览的人或者参观秦始皇兵马俑，或者参观华清池，或者洗温泉澡。凡去临潼游览的人，如果爬骊山就不能参观秦始皇兵马俑，有的游览者既不参观华清池，也不洗温泉澡。因而有的游览者不爬骊山。

解：
定义G（x）表示“x去临潼游览”；
A（x）表示“x参观秦始皇兵马俑”；
B（x）表示“x参观华清池”；
C（x）表示“x洗温泉澡”；
D（x）表示“x爬骊山”。前提：∀x(G(x)→A(x)∨B(x)∨C(x)) (1) ∀x(G(x)∧D(x)→¬A(x)) (2)
∃x(G(x)∧¬ B(x)∧¬ C(x)) (3)
结论：∃x(G(x)∧¬ D(x))
证明：
（4）G(a) ∧¬ B(a) ∧¬ C(a) 由(3)
（5）G(a)→A(a)∨B(a)∨C(a) 由(1)
（6）G(a)∧D(a)→¬A(a) 由(2)
(7)A(a)→ ¬ G(a) ∨¬ D(a) 由(6)
（8）G(a) 由（4）
（9）A(a)∨B(a)∨C(a) 由（5）（8）
（10）¬ B(a)，¬ C(a) 由（4）
（11）A(a) 由（9）（10）
（12）¬ D(a) 由（7）（8）（11）（13）∃x(G(x) ∧¬ D(x)) 由（8）（12）在这里插入图片描述

2、已知下列事实：任何通过历史考试并中了彩票的人是快乐的；任何肯学习或幸运的人可以通过所有考试；John不学习但很幸运；任何人只要幸运就能中彩。求证：John是快乐的。
解： 1）谓词公式定义：
Pass(x,y): x(人)通过y(考试)
Lottery(x): x(人)中彩票
Happy(x): x(人)快乐
Study(x): x(人)肯学习
Lucky(x): x(人)是幸运的
① (∀x) ( (Pass(x,History)∧Lottery(x)) → Happy(x) ) ② (∀x)( (Study(x)∨Lucky(x)) → (∀y) Pass(x,y) )
③ ¬Study(John) ∧ Lucky(John)
④ (∀x) Lucky(x) → Lottery(x)
⑤ Happy(John)

2）化简为子句集
C1：¬Pass(a,History)∨¬Lottery(a)∨Happy (a)
C2：¬Study(a)∨Pass(a,b)
C3：¬Lucky(a)∨Pass(a,b)
C4：¬Study(John)
C5：Lucky(John)
C6：¬Lucky(a)∨Lottery(a)
T1：¬Happy(John)

3）归结演绎证明
T2：(C1,T1)
¬Pass(John,History)∨¬Lottery(John) {John/a}
T3：(C3,T2)
¬Lucky(John)∨¬Lottery(John) {History/b}
T4：(C6,T3) ¬Lucky(John) {John/a}
T5：(C4,C5)
NIL 结论得证。

3、已知下列事实：John是贼；Paul喜欢酒；Paul也喜欢奶酪；如果Paul喜欢某物，则John也喜欢；如果某人是贼，而且喜欢某物，则他就可能偷窃该物。求解：John可能偷窃什么？
解： 1）谓词公式定义：
Thief(x): x(人)是贼
Like(x,y): x(人)喜欢y(东西)
Steal(x,y): x(人)偷y(东西)
① Thief(John)
② Like(Paul,wine)
③ Like(Paul,cheese)
④ Like(Paul,y) → Like(John,y)
⑤ (Thief(x)∧Like(x,y)) → Steal(x,y)
⑥ Steal(John,y) ∨ANSWER(y)

2）化简为子句集
C1：Thief(John)
C2：Like(Paul,wine)
C3：Like(Paul,cheese)
C4：¬ Like(Paul,y) ∨Like(John,y)
C5：¬ Thief(x) ∨¬Like(x,y)) ∨Steal(x,y)
T1：¬Steal(John,y) ∨ANSWER(y)

3）归结演绎求解
T2：(C1,C5) ¬Like(John,y)) ∨Steal(John,y) {John/x} T3：(C4,T2) ¬ Like(Paul,y) ∨Steal(John,y)
T4：(T1,T3) ¬ Like(Paul,y)∨ANSWER(y)
T5：(C2,T4) ANSWER(wine) {wine/y}
T6：(C3,T4) ANSWER(cheese) {cheese/y}
可知结果为John可能偷wine或cheese。

4、某人被盗，公安局派出所派出5个侦查员去调查。研究案情时，侦查员A说：“赵与钱中至少有一人作案”；侦查员B说：“钱与孙中至少有一人作案”；侦查员C说：“孙与李中至少有一人作案”；侦查员D说：“赵与孙中至少有一人与此案无关”；侦查员E说：“钱与李中至少有一人与此案无关”。如果这5个侦查员的话都是可信的，试问谁是盗窃犯呢？解： 1）谓词公式定义：
Thief(x): x(人)是贼 ①
Thief(Zhao) ∨Thief(Qian) ②
Thief(Qian) ∨Thief(Sun) ③
Thief(Sun) ∨Thief(Li) ④
¬Thief(Zhao) ∨¬Thief(Sun) ⑤
¬Thief(Qian) ∨¬Thief(Li) ⑥
Thief(x) ∨ANSWER(x)

2）化简为子句集
C1：Thief(Zhao) ∨Thief(Qian)
C2：Thief(Qian) ∨Thief(Sun)
C3：Thief(Sun) ∨Thief(Li)
C4：¬Thief(Zhao) ∨¬Thief(Sun)
C5：¬Thief(Qian) ∨¬Thief(Li)
T1：¬Thief(x) ∨ANSWER(x)
3）归结演绎求解
T2：(C1,C4) Thief(Qian) ∨¬Thief(Sun)
T3：(C2,T5) Thief(Sun) ∨¬Thief(Li)
T4：(C2,T2) Thief(Qian)
T5：(C3,T3) Thief(Sun)
T6：(T1,T4) ANSWER(Qian) {Qian/x}
T6：(T1,T5) ANSWER(Sun) {Sun/x}
可知结果为钱和孙都是盗窃犯。

5、已知下列事实：小李喜欢容易的课程；小李不喜欢难的课程；工程类的课程都是难的；物理类的课程都是容易的；小吴喜欢所有小李不喜欢的课程；Phy200是物理类课程；Eng300是工程类课程。试求：小李喜欢什么课程？小吴喜欢Eng300课程吗？
解： 1）谓词公式定义：
Like(x,y): x(人)喜欢y(课程)
Easy(x): x是简单的课程
Eng(x) : x是工程类课程
Phy(x) : x是物理类课程
① Easy(x)→Like(Li,x)
② ¬Easy(x)→¬Like(Li,x)
③ Eng(x) →¬Easy(x)
④ Phy(x) →Easy(x)
⑤ ¬Like(Li,x)→Like(Wu,x)
⑥ Phy(Phy200)
⑦ Eng(Eng300)
⑧ Like(Li,x)
⑨ Like(Wu,Eng300)

2）化简为子句集
C1：¬Easy(x)∨Like(Li,x)
C2：Easy(x)∨¬Like(Li,x)
C3：¬Eng(x)∨¬Easy(x)
C4：¬Phy(x)∨Easy(x)
C5：Like(Li,x)∨Like(Wu,x)
C6：Phy(Phy200)
C7：Eng(Eng300)
T1：¬Like(Li,x)∨ANSWER(x)
T2：¬Like(Wu,Eng300)

3）归结演绎求解
T3：(C1,T1) ¬Easy(x) ∨ANSWER(x)
T4：(C4,T3) ¬Phy(x)∨ANSWER(x)
T5：(C6,T4) ANSWER(Phy200) {Phy200/x}
可知结果为小李喜欢Phy200这门课程。
T6：(C2,C5) Easy(x)∨Like(Wu,x)
T7：(C3,T6) ¬Eng(x)∨Like(Wu,x)
T8：(C7,T7) Like(Wu,Eng300)
T8：(C7,T2) NIL
结论得证，小吴喜欢Eng300这门课程。