归结反演

归结反演

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这门课程。