答：归结法证明定理的过程： 1）否定结论G，得到?G； 2）将前提条件A?ΛA?Λ…ΛAn和?G化为子句集S； 3）应用归结原理，反复对子句集S进行归结，若能归结出空子句，则证明子句 集S的不可满足性，从而证明了公式A?ΛA?Λ…ΛAn →G为真。 P95第17题：
证明：先将问题用谓词描述如下： (?x)(Pass(x,computer) ∧Win(x,prize)) →Happy(x)) (?x) (?y)(Study(x)∨Lucky(x) →Pass(x,y)) ┐Study(zhang) ∧Lucky(zhang) (?x)( Lucky(x) →Win(x,prize)) 结论“张是快乐的”的否定 ┐Happy(zhang)(3分)
将上述公式转化为子句集如下：
(1)┐Pass(x,computer) ∨┐Win(x,prize) ∨Happy(x) (2) ┐Study(y) ∨Pass(y,z) (3) ┐Lucky(u) ∨Pass(u,v) (4) ┐Study(zhang) (5) Lucky(zhang)
(6) ┐Lucky(w) ∨Win(w,prize) (7) ┐Happy(zhang) (3分)
┐Pass(x,computer) ∨┐Win(x,prize) ∨Happy(x) ┐Lucky(w) ∨Win(w,prize) {W/x} ┐Pass(w,computer) ∨Happy(w) ∨┐Lucky(w) ┐Happy(zhang) {zhqang/x} Lucky(zhang) ┐Pass(zhang,computer) ∨┐Lucky(zhang) ┐Pass(zhang,computer) ┐Lucky(u) ∨Pass(u,v) {zhqang/u,computer/v} ┐Lucky(zhang) Lucky(zhang) NIL P95第20题：设已知：
(1) 能阅读的人是识字的； (2) 海豚不识字； (3) 有些海豚是很聪明的。 证明：有些很聪明的人并不识 解：第一步，先定义谓词， 设R(x)表示x 是能阅读的； K(y)表示y 是识字的； W(z) 表示z 是很聪明的； 第二步，将已知事实和目标用谓词公式表示出来 能阅读的人是识字的：(? x)(R(x))→K(x)) 海豚不识字：(? y)(?K (y)) 有些海豚是很聪明的：( ? z)W(z) 有些很聪明的人并不识字：( ? x)(W(z)∧?K(x)) 第三步，将上述已知事实和目标的否定化成子句集： ?R(x))∨K(x) ?K (y) W(z)
?W(z)∨K(x))
第四步，用归结演绎推理进行证明
(4分)
3-6. 如何通过归结法求取问题的答案? P95 18 19 答：归结法求取问题的步骤如下：
1） 把已知前提条件用谓词公式表示出来，并且化为子句集S；
2） 把待求解的问题用谓词公式表示出来，然后将其否定，并与谓词公式ANSWER
构成析取式，ANSWER是一个为了求解问题而专设的谓词，并且其変元必须与谓词公式中的変元一致；
3） 将2)中的析取式化为子句集，并且将该子句集并入到子句集S中。得到子句集
S’;
4） 对子句集S’应用归结原理进行归结。
P95第18题：
定义谓词： p （ x ）： x 作案。 由五个侦察员的话为真，有 P （ z ） ∨ p （ q ）（ 1 ）
P （ q ） ∨ p （ s ）（ 2 ） P （ s ） ∨ p （ l ）（ 3 ） ┐p （ z ） ∨ ┐p （ s ）（ 4 ） ┐p （ q ） ∨ ┐p （ l ）（ 5 ）
把结论的否定加入结论的否定的否定的子句中去，得： ┐ p （ x ） ∨ ┐ P （ x ）（ 6 ）
因为这些全都是子句，所以化为子句集的步骤可以省略了。 （ 1 ），（ 4 ）归结得：
p （ q ） ∨ ┐p （ s ）（ 7 ） （ 2 ），（ 7 ）归结得： p （ q ） （ 8 ） 即：钱是盗窃犯。
（ 5 ），（ 8 ）归结得：┐p （ l ）（ 9 ） 李不是盗窃犯。
（ 3 ），（ 9 ）归结得： p(s) (10) 孙是盗窃犯。
（ 4 ），（ 10 ）归结得：┐p （ z ） 赵不是盗窃犯。
所以，钱和孙是盗窃犯。
P95第19题：看附件
3-7. 与/或形演绎推理有哪几种推理方式? 简述推理过程 （见课本例题）P95 21 22 答：与/或形演绎推理分为正向演绎、逆向演绎和双向演绎推理。 与/或正向演绎推理过程如下：
1） 用与/或树将已知事实表示出来；
2） 用F规则的左部和与/或树的叶结点进行匹配，并将匹配成功的F规则加入大
与/或树中；
3） 重复步骤2），直至产生一个含有目标结点的一致解图。 与/或逆向演绎推理过程如下：
1） 用与/或树将求解目标表示出来；
2） 用B规则的右部和与/或树的叶结点进行匹配，并将匹配成功的B规则加入
大与/或树中； 重复步骤2），直至产生一个含有已知事实结点的一致解图。 P95第21题：看附件
第5部分 搜索问题求解
5-1 说明用状态空间法求解问题的过程，基本的求解方法有哪些？ 答：求解问题过程：
1)将所要求的问题表示成状态空间，问题的解就在状态空间中
2)根据给定的条件，在状态空间中搜索出目标状态，从而求得问题的解 基本的求解方法有：
1)状态空间的穷搜索法
a,广度优先搜索算法 b,深度优先搜索算法。 2)启发式搜索法
a,图启发式搜索算法A、b,图启发式搜索算法A*
5-2什么是盲目搜索？启发式搜索法的基本思想是什么？评估函数如何定义？评估函数的作用是什么？ 答：盲目搜索：指从当前状态到目标状态需要走多少步，或者每条路径的花费并不知道， 所能做的只是可以区分出哪个是目标状态。因此它一般是按预定的搜索策略进行搜 索，没有考虑到问题 本身的特性，所以具有很大的盲目性，效率不高，不便于复 杂问题的求解。
启发式搜索法的基本思想：是在搜索过程中加入了与被解问题有关的启发性信息 （特征），用于指导搜索朝着有希望至达目标结点的的方向前进，加速问题的求解 并找到最优解。只要知道问题 的部分状态空间就可以求解，效率高。 评估函数定义：f(n)=g(n)+h(n)
这里个g(n)表示迄今为止搜索已产生的从初始结点S?到结点n的实际代价，h(n) 表示从结点n到目标结点的估计代价，h(n)称为启发函数，它体现了搜索的启发信 息。
评估函数的作用： 估计待扩展各结点在问题求解中的价值。
5-3 什么是问题归约法？与或图的作用是什么？为什么应用问题规约得到的状态空间可表示为与或图？ 答：问题归约法把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分 别求解：只有当这些子问题全部解决时，问题才算解决，问题的解答由子问题的解 答联合构成。
与或图的作用是可以方便地把问题归约为子问题替换集合。 5-4 说明博弈树搜索的极大极小过程、?-?过程？P150 6 答：参照以下例题：
设有如图所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树作如下工作：
(1) 计算各节点的倒推值；
(2) 利用α-β剪枝技术剪去不必要的分枝。
S0 A B C G H I D J K E L M F N 0 5 -3 3 3 6 6 -2 3 5 4 -3 0 6 8 9 -3 博弈树
解：各节点的倒推值和剪枝情况如下图所示：
≥4 ≤0 A ≤4 B S0
≥0 ≤0 G C ≤-3 H ≤3 ≥3 I D J ≤4 ≥4 E L ≤6 ≥6 M F K ≤-3 N 0 5 -3 3 3 3 6 6 -2 3 5 4 -3 0 6 8 9 -3 倒推值和剪枝情况
相关推荐：
loading