利用归结原理进行归结

(6)R(a) [(2),(3), σ1={a/z}]

(7) ¬ R(a) [(4),(5), σ2 ={a/y}] (8)Nil [(6),(7)]

所以S是不可满足得，从而G是F1和F2的逻辑结果。

五·一个农夫要用船带一只狼、一只羊和一捆草从河的左岸到右岸，但受下列条件限制： （1）农夫每次只能带一样东西过河；

（2）人不在的时候，狼会吃羊、羊会吃草。 试用状态空间图求出他们能顺利过河的方案。

解：用四元组(f、w、s、g)表示状态， f 代表农夫，w 代表狼，s 代表羊，g 代表菜，其

中每个元素都可为0或1，用0表示在左岸，用1表示在右岸 。 初始状态S0：(0,0,0,0) 目标状态：(1,1,1,1) 不合法的状态:(1,0,0,*),(1,*,0,0),(0,1,1,*),(0,*,1,1) 操作集F={P1，P2，P3，P4，Q1，Q2，Q3，Q4}

方案有两种：p2→ q0 → p3→ q2 → p2 → q0 → p2 p2→ q0 → p1→ q2 → p3→ q0→ p2

六．给出井字棋游戏的完整状态空间图，并设计一个启发函数，将其应用到搜索过程中。

七．张某被盗，公安局派五个侦察员去调查，研究案情时，侦察员A说：“赵与钱中至少有一人作案”；侦察员B说：“钱与孙至少有一人作案”；侦察员C说：“孙与李中至少有一人作案”；侦察员D说：“赵与孙中至少有一人与此案无关”；侦察员E说：“钱与李中至少有一人与此案无关”。如果这五个侦察员说的都可信，试用消解原理求出谁是盗窃犯。

解：设谓词P(x)表示x是盗窃犯． 则题意可表述为如下的谓词公式： F1:P(zhao) P(qian) F2: P(qian) P(sun) F3: P(sun) P(li)

F4: ¬ P(zhao) ¬ P(sun) F5: ¬ P(qian) ¬ P(li) 求证的公式为： xP(x) 子句集如下： ① P(zhao) P(qian) ② P(qian) P(sun) ③ P(sun) P(li)

④ ¬ P(zhao) ¬ P(sun) ⑤ ¬ P(qian) ¬ P(li) ⑥ ¬ P(x) GA(x)

⑦ P(qian) ¬ P(sun) [①,④] ⑧ P(sun) ¬ P(li) [②,⑤] ⑨ P(sun) [③,⑧] ⑩ GA(sun) [⑥,⑨,{sun/x}] (11)P(qian) [⑦,⑨]

(12)GA(qian) [⑥,(11),{qian/x} 所以，sun和qian都是盗窃犯．即：孙和钱都是盗窃犯． 此题需定义一个辅助谓词GA(x)来求出谁是盗窃犯。

设A、B、C中有人从来不说真话，也有人从来不说谎话，某人向这三人分别同时提出一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个人说谎”。用归结原理求谁是老实人，谁是说谎者？ 解：用T（x）表示x说真话。

如果A说的是真话则有：T(A) (¬T(B) ∧ ¬T(C)) 如果A说的是假话则有： ¬ T(A) (T(B) ∨ T(C)) 对B和C所说的话做相同的处理，可得： T(B) (¬T(A) ∧¬T (C) ) ¬T(B) (T(A) ∨ T(C))

T(C) (¬T(A) ∨ ¬T(B)) ¬ T(C) (T(A) ∧ T(B)) 将上面的公式化为子句集，得到S： (1)¬ T(A) ∨ ¬T(B) (2)¬ T(A) ∨ ¬T(C )

(3)T(A) ∨ T(B ) ∨ T(C ) (4)¬ T(B) ∨ ¬T(C )

(5)¬ T(A) ∨ ¬T(B ) ∨ ¬T(C ) (6)T(C) ∨ T(A)

(7)T(C) ∨ T(B)

首先求谁是老实人。把¬ T(x) ∨ANS(x)并入S中，得到子句集S 1 ，即 S 1比S中多了一个子句： (8) ¬ T(x) ∨ANS(x)

应用归结原理对S 1进行归结：

(9) ¬ T(A) ∨ T(C) [(1),(7)] (10)T(C) [(6),(9)] (11)ANS(C) [(8),(10)]

这样就得到了答案，即C是老实人，即C从来不说假话。

下面来证明B和A不是老实人，设A不是老实人，则有¬ T(A) ,将其 否定并入S中，得到子句集S2，即S2比S多了一个子句： (8) ’¬ (¬ T(A) )即T(A)

利用归结原理对进行归结：

(9) ’T(A) ∨T(C) [(1),(7)] (10)’T(C) *(6),(9)’+ (11)’NIL *(8)’,(10)’+

八．公司招聘工作人员有A、B、C三人应聘，经面试后，公司表示如下想法 (1) 三人中至少录取一人；

(2) 如果录取A而不录取B,，则一定录取C； (3) 如果录取B，则一定录取C 试用归结原理求证：公司一定录取C。 证明：用命题公式表述题意为：

(1)A B C (2)A ¬B C (3)B C

结论：C是子句集的逻辑{A B C , A ¬B C , B C}的逻辑结果。