人工智能与专家系统课堂作业-02
1、什么是状态空间？状态空间是怎样构成的？
答：由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间。一般用一个三元组表示：
（S,F,G）
其中S是问题的所有初始状态构成的集合；F是算符的集合；G是目标状态的集合。
2、请写出用状态空间表示法表示问题的一般步骤。
答：（1）状态定义——定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来；
（2）算符定义——定义一组算符，通过使用算符可把问题由一个状态转变为另一种状态；
（3）利用状态空间的搜索算法求解。 3、什么是置换？什么是合一？什么是最一般合一？
答：（1）置换是形如：
{t1/x1,t2/x2, ... ,tn/xn}
的有限集合。其中，t1,t2,...,tn是项；x1,x2,...,xn是互不相同的变元；
也不允许变元xi循环地出现在另一个tj中。ti/xi表示用ti代换xi，不允许ti与xi相同，
（2）设有公式集F={F1，F2，?，Fn}，若存在一个代换λ使得
F1λ=F2λ=?=Fnλ
则称λ为公式集F的一个合一，且称F1，F2，?，Fn是可合一的。 （3）设σ是公式集F的一个合一，如果对任一个合一θ都存在一个代换λ，使得
θ=σολ
则称 是公式集F的最一般合一（mgu）。
4、什么是子句？什么是子句集？试写出求谓词公式子句集的步骤。
答：（1）在谓词逻辑中，把原子谓词公式及其否定统称为文字。任何文字的析取式称为子句。
（2）由子句构成的集合称为子句集。 （3）求谓词公式子句集的步骤： ①消去蕴含连词。
利用下述等价关系消去谓词公式中的蕴含连词“→”。
P?Q??P?Q
②减小否定连词的辖域。
利用下述等价关系把“?”移到紧靠谓词的位置上：
?(?P)?P?(P?Q)??P??Q?(P?Q)??P??Q ?(?x)P?(?x)?P?(?x)P?(?x)?P③约束变元标准化。
重新命名约束变元名，使不同量词的约束变元有不同的名字。 ④消去存在量词。
若存在量词不在全称量词的辖域内，则用一个新的个体常量替换受该存在量词约束的变元就可消去存在量词（因为若原公式为真，则总能找到一个个体常量，替换后仍使公式为真）；若存在量词位于一个或多个全称量词的辖域内，例如
(?x1)(?x2)?(?xn)(?y)P(x1,x2,?,xn,y)
则需要用Skolem函数f(x1,x2,?,xn)替换受该存在量词约束的变元y，然后才能消去存在量词。
⑤组成全称量词前缀。
把全称量词全部移到公式的左边，组成全称量词前缀。 ⑥把母式化为Skolem标准形。 利用下述等价关系
P?(Q?R)?(P?Q)?(P?R)
把公式化为Skolem标准形。
Skolem标准形的一般形式是
(?x1)(?x2)?(?xn)M
其中，M是子句的合取式，称为Skolem标准形的母式。 ⑦消去全称量词。
⑧对变元更名，使不同子句中的变元。 ⑨消去合取连词，得到子句集。
5、试写出利用归结原理求解问题答案的步骤。
答：利用归结原理求解问题答案的步骤：
（1）把已知前提用谓词公式表示出来，并且化为相应的子句集，设该子句集的名字为S；
（2）把待求解的问题也用谓词公式表示出来，然后把它否定并与谓词ANSWER构成析取式，ANSWER是一个为了求解问题二专设的谓词，其变元必须与问题公式的变元完全一致；
（3）把此析取式化为子句集，并且把该子句集并入到子句集S中，得到子句集S’；
（4）对S’应用归结原理进行归结；
（5）若得到归结式ANSWER，则答案就在ANSWER中。 6、判断一下公式对是否可合一；若可合一，则求出最一般合一 （1）P（a，b）,
P（x，y）
解：令?0??,S0?{P(a,b),P(x,y)}。
①差异集为{a,x}，做替换{a/x}，则
?1??0?{a/x}?{a/x}
S1?S0?1?{P(a,b),P(a,y)} ②差异集为{b,y}，做替换{b/y}，则
?2??1?{b/y}?{a/x,b/y}
S2?S1?2?{P(a,b)}
已经是单元集，所以原子句集可合一，且最一般合一为：{a/x,b/y}。
（2）P（f（y），y，x），
P（x，f（a），f（b））
解：令?0??,S0?{P(f(y),y,x),P(x,f(a),f(b))}。
①差异集为{f(y),x}，做替换{f(y)/x}，则
?1??0?{f(y)/x}?{f(y)/x}
S1?S0?1?{P(f(y),y,f(y)),P(f(y),f(a),f(b))} ②差异集为{y,f(a)}，做替换{f(a)/y}，则
?2??1?{f(a)/y}?{f(f(a))/x,f(a)/y}
S2?S1?2?{P(f(f(a)),f(a),f(f(a))),P(f(f(a)),f(a),f(b)} ③差异集为{f(a),b}。由于其中不存在变量，所以原子句集不可合一。
7、把下列谓词公式分别化为相应的子句集 （1）(?x)(?y)(P(x,y)?Q(x,y)) 解：
(?x)(?y)(P(x,y)?Q(x,y))去掉蕴含符号：上式?(?x)(?y)(?P(x,y)?Q(x,y))去掉全称量词：上式??P(x,y)?Q(x,y)变成子句集：{?P(x,y)?Q(x,y)}8、某单位招聘工作人员，张三、李四、王五应试，经面试后单位有如下想法： （1）如果录取张三而不录取李四，则一定录取王五。 （2）如果录取李四，则一定录取王五。 （3）三人中至少要录取一人。 求证：王五一定会被单位录取。
证明：设张三、李四、王五分别为A、B、C。
首先，定义谓词L(x)表示x被录取。
把已知前提及待求证问题用谓词公式表示出来： F1：(L(A)?(?L(B)))?L(C)
F2：L(B)?L(C) F3：L(A)?L(B)?L(C) G：L(C)
将前提化为子句集： （1）?L(A)?L(B)?L(C) （2）?L(B)?L(C) （3）L(A)?L(B)?L(C) 将结论否定并化为子句集： （4）?L(C)
应用归结原理进行归结： （5）L(B)?L(C) （6）L(C) （7）NIL
（1）与（3）归结 （2）与（5）归结 （4）与（6）归结
∴公司一定录取C。
上述归结过程可用下图的归结树表示：
?L(A)?L(B)?L(C)L(A)?L(B)?L(C)L(B)?L(C) ?L(B)?L(C) L(C) ?L(C) NIL
