第二章 本章练习参考答案

一、填空题（每小题4分，共68分）

1．初始状态集；算符集合；目标状态集合

2．随谓词逻辑中变量取值的变化而变化

3．真

4．辖域；约束变元；自由变元

5．状态空间法；问题归约法；谓词逻辑法

6．问题归约法

7．吸收；摩根

8．一

9．可解节点；不可解节点

二、谓词描述题（每小题10分，共20分）

将下列自然语言转化为谓词表示形式：

1．Man（x）：x是人；    Breath（y）:y需要呼吸    （x）（Man（x）→Breath（x））

2．L（x，y）：某人x喜欢某物y；    P（y）：某物y是清洁的东西    （y）（x）[P（y）→L（x，y）]

三、简答题（本题12分）

状态空间法是一种基于解答空间的问题表示和求解方法，它是以状态和操作符为基础的。在利用状态空间图表示时，从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。由于状态空间法需要扩展过多的节点，容易出现“组合爆炸”，因而只适用于表示比较简单的问题。

问题归约法从目标（要解决的问题）出发，逆向推理，通过一系列变换把初始问题变换为子问题集合和子子问题集合，直至最后归约为一个平凡的本原问题集合。这些本原问题的解可以直接得到从而解决了初始问题，用与或图来有效地说明问题归约法的求解途径。问题归约法能够比状态空间法更有效地表示问题。状态空间法是问题归约法的一种特例。在问题归约法的与或图中，包含有与节点和或节点，而在状态空间法中只含有或节点。

谓词逻辑法采用谓词合适公式和一阶谓词演算把要解决的问题变为一个有待证明的问题，然后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导出的，从而证明这个新语句也是正确的。谓词逻辑是一种形式语言，能够把数学中的逻辑论证符号化。谓词逻辑法常与其它表示方法混合使用，灵活方便，可以表示比较复杂的问题。