AI课后习题

习题一

1. 什么是人类智能？它有哪些特征或特点？

定义：人类所具有的智力和行为能力。

特点：主要体现为感知能力、记忆与思维能力、归纳与演绎能力、学习能力以及行为能力。 2. 人工智能是何时、何地、怎样诞生的？

解：人工智能于1956年夏季在美国Dartmouth大学诞生。此时此地举办的关于用机器模拟人类智能问题的研讨会，第一次使用“人工智能”这一术语，标志着人工智能学科的诞生。 3. 什么是人工智能？它的研究目标是什么？

定义：用机器模拟人类智能。

研究目标：用计算机模仿人脑思维活动，解决复杂问题；从实用的观点来看，以知识为对象，研究知识的获取、知识的表示方法和知识的使用。

4. 人工智能的发展经历了哪几个阶段？

解：第一阶段：孕育期（1956年以前）；第二阶段：人工智能基础技术的研究和形成（1956~1970年）；第三阶段：发展和实用化阶段（1971~1980年）；第四阶段：知识工程和专家系统（1980年至今）。 5. 人工智能研究的基本内容有哪些？

解：知识的获取、表示和使用。 6. 人工智能有哪些主要研究领域？

解：问题求解、专家系统、机器学习、模式识别、自动定论证明、自动程序设计、自然语言理解、机器人学、人工神经网络和智能检索等。

7. 人工智能有哪几个主要学派？各自的特点是什么？

主要学派：符号主义和联结主义。

特点：符号主义认为人类智能的基本单元是符号，认识过程就是符号表示下的符号计算，从而思维就是符号计算；联结主义认为人类智能的基本单元是神经元，认识过程是由神经元构成的网络的信息传递，这种传递是并行分布进行的。 8. 人工智能的近期发展趋势有哪些？

解：专家系统、机器人学、人工神经网络和智能检索。 9. 什么是以符号处理为核心的方法？它有什么特征？

解：通过符号处理来模拟人类求解问题的心理过程。 特征：基于数学逻辑对知识进行表示和推理。

10. 什么是以网络连接为主的连接机制方法？它有什么特征？

解：用硬件模拟人类神经网络，实现人类智能在机器上的模拟。 特征：研究神经网络。

习题二

1. 什么是知识？它有哪些特性？有哪几种分类方法？

定义：人们对自然现象的认识和从中总结出来的规律、经验。 特性：相对正确性、不确定性、可表示性和可利用性。

分类方法：（1）按知识的作用范围分为：常识性知识和领域性知识；（2）按知识的作用及表示分为：事实性知识、规则性知识、控制性知识和元知识；（3）按知识的确定性分为：确定知识和不确定知识；（4）按人类思维及认识方法分为：逻辑性知识和形象性知识。

2. 何谓知识表示？陈述性知识表示法与过程性知识表示法的区别是什么？

定义：研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，考虑知识的存储与使用。 区别：陈述性知识表示法主要用来描述事实性知识，将知识表示与应用分开处理，是一种表态的描述方法；过程性知识表示法主要用来描述规则性知识和控制结构知识，将知识的表示与应用相结合，是一种动态的描述方法。 3. 在选择知识的表示方法时，应该考虑哪些主要因素？

解：可行性、有效性、易理解性、模块性和灵活性。

4. 一阶谓词逻辑表示法适合于表示哪种类型的知识？它有哪些特点？

1

解：可以表示事物的状态、属性、概念等事实性的知识，也可以表示事物间具有确定关系的规则性知识。

特点：（1）自然性，表示问题易于理解和接受；（2）适用于精确性知识的表示，不适用不确定性知识的表示；（3）易实现性；（4）会产生组合爆炸，效率低。

5. 请写出用一阶谓词逻辑表示法表示知识的步骤。

步骤：（1）定义谓词及个体，确定每个谓词及个体的确切含义；（2）根据所要表达的事物或概念，为每个谓词中的变元赋予特定的值；（3）根据所要表达的知识的语义用适当的联接符号将各个谓词联接起来，形成谓词公式。 6. 设有下列语句，请用相应的谓词公式把它们表示出来：

（1） 有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。 解：定义谓词如下：

Like(x,y)：x喜欢y。 Club(x)：x是梅花。 Human(x)：x是人。 Mum(x)：x是菊花。

“有的人喜欢梅花”可表达为：(?x)(Human(x)?Like(x,Club(x))) “有的人喜欢菊花”可表达为：(?x)(Human(x)?Like(x,Mum(x)))

“有的人既喜欢梅花又喜欢菊花”可表达为：(?x)(Human(x)?Like(x,Club(x))? Like(x,Mum(x))) （2） 他每天下午都去玩足球。 解：定义谓词如下：

PlayFootball(x)：x玩足球。 Day(x)：x是某一天。 则语句可表达为：(?x)(D(x)?PlayFootball(Ta)) （3） 太原市的夏天既干燥又炎热。 解：定义谓词如下：

Summer(x)：x的夏天。 Dry(x)：x是干燥的。 Hot(x)：x是炎热的。 则语句可表达为：Dry(Summer(Taiyuan))?Hot(Summer(Taiyuan)) （4） 所有人都有饭吃。 解：定义谓词如下：

Human(x)：x是人。 Eat(x)：x有饭吃。 则语句可表达为：(?x)(Human(x)?Eat(x)) （5） 喜欢玩篮球的人必喜欢玩排球。 解：定义谓词如下：

Like(x,y)：x喜欢y。 Human(x)：x是人。

则语句可表达为：(?x)((Human(x)?Like(x,basketball))?Like(x,volleyball)) （6） 要想出国留学，必须通过外语考试。 解：定义谓词如下：

Abroad(x)：x出国留学。 Pass(x)：x通过外语考试。

则语句可表达为：Abroad(x)?Pass(x)

10. 产生式的基本形式是什么？它与谓词逻辑中的蕴含式有什么共同处及不同处？

解：基本形式：P?Q 或者 IF P THEN Q 其中，P是产生式的前提，用于指出该产生式是否可用的条件；Q是一组结论或操作，用于指出前提P所指示的条件被满足时应该得出的结论或应该执行的操作。

产生式与谓词逻辑中蕴含式的区别：（1）蕴含式只能表示精确性知识，而产生式可以表示精确性知识，也可以表示不精确性知识。（2）产生式前提条件的匹配可以是精确匹配，也可以是不精确匹配，而蕴含式前提条件的匹配问题要求精确匹配。 11. 何谓产生式系统？它由哪几部分组成？

解：一组产生式一起相互配合，协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以解决问题，这样的系统称为产生式系统。 组成：规则库、综合数据库和推理机。 12. 试述产生式系统求解问题的一般步骤。

解：（1）事实库初始化；（2）若存在未用规则前提能与事实库相匹配则转（3），否则转（5）；（3）使用规则，更新事实库，

2

标记所用规则；（4）事实库是否包含解，若是，则终止求解过程，否则转（2）；（5）要求更多的关于问题的信息，若不能提供所要信息，则求解失败，否则更新事实库并转（2）。

13. 产生式系统中，推理的推理方式有哪几种？在产生式推理过程中，如果发生策略冲突，如何解决？

解：推理方式有正向，反向和双向推理三种。在产生式推理过程中，如果发生策略冲突，常见的解决策略有专一性排序、规则排序、规模排序和就近排序。

16. 何谓语义网络？语义网络表示法的特点是什么？

定义：通过概念及其语义关系来表示知识的一种带有标注的有向图。 特点：结构性、自然性、联想性和非严格性。

17. 语义网络表示法与产生式表示法、谓词逻辑表示法之间的关系如何？

解：产生式表示法是以一条产生式规则作为知识的单位，各条产生式规则之间没有直接的联系。语义网络将基本网元视作

一种知识的单位，各个网元之间相互联系。从谓词逻辑表示法来看，一个基本网元相当于一组一阶二元谓词。 18. 请写出用语义网络表示法表示知识的步骤。

解：（1）确定问题中的所有对象以及各对象的属性；（2）确定所论对象间的关系；（3）语义网络中，如果节点间的联系是

ISA/AKO，则下层节点对上层节点的属性具有继承性。整理同一层节点的共同属性，并抽出这些属性，加入上层节点中，以免造成属性信息的冗余。（4）将各对象作为语义网络的一个节点，而各对象间的关系作为网络中各节点间的弧，连接形成语义网络。

20. 用语义网络表示下列知识： （1）所有的鸽子都是鸟； （2）所有的鸽子都有翅膀； （3）信鸽是一种鸽子，它有翅膀。

解：本题涉及对象有信鸽、鸽子和鸟。鸽子和信鸽的属性是有翅膀。鸽子和鸟是ISA关系，信鸽和鸽子是AKO关系。根据

分析得到本题的语义网络如下：

21. 请对下列命题分别写出它的语义网络： （1）每个学生都有多本书。

解：根据题意可得本题的语义网络如下：

（2）孙老师从2月至7月给计算机应用专业讲《网络技术》课程。 解：根据题意可得本题的语义网络如下：

（3）雪地上留下一串串脚印，有的大，有的小，有的深，有的浅。 解：根据题意可得本题的语义网络如下：

（4）王丽萍是天发电脑公司的经理，她35岁，住在南内环街68号。 解：根据题意可得本题的语义网络如下：

3

22. 请把下列命题用一个语义网络表示出来： （1）猪和羊都是动物；

（2）猪和羊都是偶蹄动物和哺乳动物； （3）野猪是猪，但生长在森林中； （4）山羊是羊，且头上长着角； （5）绵羊是一种羊，它能生产羊毛。

解：本题涉及对象有猪、羊、动物、野猪、山羊和绵羊。猪和羊的属性是偶蹄和哺乳。野猪的属性是生长在森林中。山羊

的属性是头上长着角。绵羊的属性是产羊毛。根据对象之间的关系得到本题的语义网络如下：

23. 在基于语义网络的推理系统中，一般有几种推理方法，简述它们的推理过程。 解：推理方法一般有两种：匹配和继承。

匹配推理过程：（1）根据提出的待求解问题，构造一个局部网络；（2）根据局部网络到知识库中寻找可匹配的语义网络；

（3）匹配成功时，与未知处相匹配的事实就是问题的解。 继承推理过程：下层节点从上层节点继承一些属性。 24. 何谓框架？框架的一般表示形式是什么？ 定义：一种描述所论对象属性的数据结构。

一个框架可以由框架名、槽、侧面和值四部分组成。一般可表示为： 框架名 ＜槽名＞ ＜侧面＞ ＜值＞ ＜侧面＞ ＜值＞ ＜槽名＞ ＜侧面＞ ＜值＞ ＜侧面＞ ＜值＞ ?

25. 框架表示法有何特点？请叙述用框架表示法表示知识的步骤。 解：特点：结构性、继承性和自然性。

框架表示知识的步骤：（1）分析等表达知识中的对象及其属性，对框架中的槽进行合理设置。（2）对各对象间的各种联系

进行考察。使用一些常用的或根据具体需要定义一些表达联系的槽名，来描述上下层框架间的联系。（3）对各层对象的“槽”及“侧面”进行合理的组织安排，避免信息描述的重复。 26. 试构造一个描述你的办公室或卧室的框架系统。

4

解：框架名：<卧室> 墙数：4 窗数：1 门数：1 电脑数：3 前墙：<前墙> 门数：1 插座数：2 后墙：<后墙> 窗数：1 书架数：1 暖气片数：1 左墙：<左墙> 书架数：3 右墙：<右墙> 书架数：4 插座数：1 门：<门> 门前： 锁：1把 室员表：1张 门后：

值日表：1张 课程表：1张 窗：<窗> 扇数：2 窗帘：1副 天花板：<天花板> 日光灯：1座 蚊帐：4张 地板：<地板> 性质：水泥地 地面： 书桌：1张 电脑桌：1张 凳子：3张 床：4张 27. 试写出“学生框架”的描述。 解：框架名：<学生> 姓名：温安平 班级：24020102 学号：2402010214 性别：男 年龄：22 职务：无

5

籍贯：福建龙岩 民族：汉 政治面貌：团员

28. 框架系统中求解问题的一般过程是什么？

解：（1）把待求解问题用一个框架表示出来，其中有的槽是空的，表示待求解的问题，称作未知处。（2）通过与知识库中

已有的框架进行匹配。（3）使用一种评价方法对预先框架进行评价，以便决定是否接受它。（4）若可接受，则与问题框架的未知处相匹配的事实就是问题的解。 29. 何谓对象？何谓类？封装及继承的含义是什么？

解：对象就是由一组数据和与该组数据相关的操作构成的封装体或实体。类是一种抽象机制，是对一组相似对象的抽象。

继承就是一个类拥有另一个类的全部变量和属性。封装就是把一切局部于对象的信息及操作都局限于对象之内。 30. 面向对象的基本特征是什么？

解：抽象性、封装性、继承性和多态性。 31. 请写出用面向对象表示法表示知识的步骤。

解：（1）定义类名，在系统中唯一标识该类。（2）指出当前定义类的父类（可省略）。（3）定义全局变量。（4）定义该类

对象的构成方法。（5）定义对类元素可施行的操作。（6）指出该类元素所应满足的限制条件。 32. 什么是状态空间？状态空间是怎样构成的?如何表示状态空间？ 定义：表示一个问题的全部状态及一切可用算符构成的集合。

构成：问题的所有可能初始状态构成的集合S；算符集合F；目标状态集合G。 状态空间用一个三元组（S，F，G）来表示。 33. 请写出用状态空间表示法表示问题的一般步骤。

解：（1）定义状态的描述形式。（2）用所定义的状态描述形式把问题的所有可能的状态都表示出来，并确定出问题的初始

状态集合描述和目标状态集合描述。（3）定义一组算符，使得利用这组算符可把问题由一种状态转变为另一种状态。

习题三

1. 什么是命题？请写出3个真值为T及真值为F的命题。

定义：能够分辨真假的语句。

3个真值为T的命题：太阳从东边升起；地球绕着太阳转；人是高级动物。 3个真值为F的命题：太阳从西边升起；瞎子看得见；太阳绕着地球转。 2. 什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？

解：谓词是用于刻画个体的性质、状态或个体间关系语句片断。谓词个体是可以独立存在的物体。个体域是谓词个体的集合。

区别：谓词具有逻辑值“真”或“假”，而函数是自变量到因变量之间的一个映射。 3. 谓词逻辑和命题逻辑的关系如何？有何异同？

解：谓词逻辑是命题逻辑的扩充与发展，它将一个原子命题分解成谓词与个体两部分。命题逻辑是谓词逻辑的基础，是谓词逻辑的一种特殊形式。

不同点：命题逻辑不能描述不同事物的共同特征，而谓词逻辑可以。命题逻辑中可以直接通过真值指派给出解释，而谓词逻辑不行。

相同点：归结原理都是完备的，都可以用来表示事实性知识。 4. 什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。

解：项是个体常数、变量和函数的统称。若谓词个体是常量、变元或函数，则为一阶谓词，若谓词个体是一阶谓词，则为二阶谓词，依此类推是为谓词的阶。

谓词的一般形式：P（x1，x2，?，xn），其中P是谓词，x1，x2，?，xn是个体。

5. 什么是谓词公式？什么是谓词公式的解释？设D＝｛1,2｝，试给出谓词公式(?x)(?y)(P(x,y)?Q(x,y))的所有解释，并且

对每一种解释指出该谓词公式的真值。

解：谓词公式是按照下述五个规则由原子公式、连接词、量词及圆括号所组成的字符串。

(1)原子谓词公式是合式公式。 (2)若A是合式公式，则?A也是合式公式。 (3)若A和B都是合式公式，则A?B、

6

A?B、A?B、A?B也都是合式公式。 (4)若A是合式公式，x是任一个体变元，则(?x)A和(?x)A也都是合式公式。 (5)只有按(1) ? (4)所得的公式才是合式公式。

谓词公式的解释：设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按照如下规定赋值：(1)为每个个体常量指派D中的一个元素；(2)为每个n元函数指派一个从Dn到D的映射，其中Dn=｛(x1，x2，?，xn)| x1，x2，?，xn ?D｝ (3)为每个n元谓词指派一个从Dn到{F，T}的映射；则这些指派称为公式P在D上的解释。

下面给出本题的所有解释：

1. 对谓词指派的真值为：P(1,1)=T，P(1,2)=F，P(2,1)=T，P(2,2)=F，Q(1,1)=T，Q(1,2)=F，Q(2,1)=T，Q(2,2)=F，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

2. 对谓词指派的真值为：P(1,1)=T，P(1,2)=F，P(2,1)=F，P(2,2)=T，Q(1,1)=T，Q(1,2)=F，Q(2,1)=T，Q(2,2)=F，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为F。所以在此解释下，本题谓词公式的真值为T。

3. 对谓词指派的真值为：P(1,1)=F，P(1,2)=T，P(2,1)=T，P(2,2)=F，Q(1,1)=T，Q(1,2)=F，Q(2,1)=T，Q(2,2)=F，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为F；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

4. 对谓词指派的真值为：P(1,1)=F，P(1,2)=T，P(2,1)=F，P(2,2)=T，Q(1,1)=T，Q(1,2)=F，Q(2,1)=T，Q(2,2)=F，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为F；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为F。所以在此解释下，本题谓词公式的真值为F。

5. 对谓词指派的真值为：P(1,1)=T，P(1,2)=F，P(2,1)=T，P(2,2)=F，Q(1,1)=T，Q(1,2)=F，Q(2,1)=F，Q(2,2)=T，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为F，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

6. 对谓词指派的真值为：P(1,1)=T，P(1,2)=F，P(2,1)=T，P(2,2)=F，Q(1,1)=F，Q(1,2)=T，Q(2,1)=T，Q(2,2)=F，

在此解释下，x=1时，P(1,1)?Q(1,1)为F，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

7. 对谓词指派的真值为：P(1,1)=T，P(1,2)=F，P(2,1)=T，P(2,2)=F，Q(1,1)=F，Q(1,2)=T，Q(2,1)=F，Q(2,2)=T，

在此解释下，x=1时，P(1,1)?Q(1,1)为F，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为F，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为F。

8. 对谓词指派的真值为：P(1,1)=T，P(1,2)=F，P(2,1)=F，P(2,2)=T，Q(1,1)=T，Q(1,2)=F，Q(2,1)=F，Q(2,2)=T，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

9. 对谓词指派的真值为：P(1,1)=T，P(1,2)=F，P(2,1)=F，P(2,2)=T，Q(1,1)=F，Q(1,2)=T，Q(2,1)=T，Q(2,2)=F，

在此解释下，x=1时，P(1,1)?Q(1,1)为F，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为F。所以在此解释下，本题谓词公式的真值为F。

10. 对谓词指派的真值为：P(1,1)=T，P(1,2)=F，P(2,1)=F，P(2,2)=T，Q(1,1)=F，Q(1,2)=T，Q(2,1)=F，Q(2,2)=T，

在此解释下，x=1时，P(1,1)?Q(1,1)为F，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

11. 对谓词指派的真值为：P(1,1)=F，P(1,2)=T，P(2,1)=T，P(2,2)=F，Q(1,1)=T，Q(1,2)=F，Q(2,1)=F，Q(2,2)=T，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为F；x=2时，P(2,1)?Q(2,1)为F，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为F。

12. 对谓词指派的真值为：P(1,1)=F，P(1,2)=T，P(2,1)=T，P(2,2)=F，Q(1,1)=F，Q(1,2)=T，Q(2,1)=T，Q(2,2)=F，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

13. 对谓词指派的真值为：P(1,1)=F，P(1,2)=T，P(2,1)=T，P(2,2)=F，Q(1,1)=F，Q(1,2)=T，Q(2,1)=F，Q(2,2)=T，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为F，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

7

14. 对谓词指派的真值为：P(1,1)=F，P(1,2)=T，P(2,1)=F，P(2,2)=T，Q(1,1)=T，Q(1,2)=F，Q(2,1)=F，Q(2,2)=T，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为F；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

15. 对谓词指派的真值为：P(1,1)=F，P(1,2)=T，P(2,1)=F，P(2,2)=T，Q(1,1)=F，Q(1,2)=T，Q(2,1)=T，Q(2,2)=F，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为F。所以在此解释下，本题谓词公式的真值为F。

16. 对谓词指派的真值为：P(1,1)=F，P(1,2)=T，P(2,1)=F，P(2,2)=T，Q(1,1)=F，Q(1,2)=T，Q(2,1)=F，Q(2,2)=T，

在此解释下，x=1时，P(1,1)?Q(1,1)为T，P(1,2)?Q(1,2)为T；x=2时，P(2,1)?Q(2,1)为T，P(2,2)?Q(2,2)为T。所以在此解释下，本题谓词公式的真值为T。

6. 对下列谓词公式分别指出哪些是约束变元？哪些是自由变元？并指出各量词的辖域。

（1）(?x)(P(x,y)?(?y)(Q(x,y)?R(x,y)))

解：(?x)的辖域是(P(x,y)?(?y)(Q(x,y)?R(x,y)))，x是受(?x)约束的变元；(?y)的辖域的(Q(x,y)?R(x,y))，y是受(?y)约束的变元；没有自由变元。

（2）(?z)(?y)(P(z,y) ?Q(z,x)) ?R(u,v)

解：(?z)的辖域是(?y) (P(z,y) ?Q(z,x))，z是受(?z)约束的变元；(?y)的辖域是(P(z,y) ?Q(z,x))，y是受(?y)约束的变元；u、v是自由变元。

（3）(?x)(?P(x,f(x)) ?(?z)(Q(x,z) ??R(x,z)))

解：(?x)的辖域是(?P(x,f(x)) ?(?z)(Q(x,z) ??R(x,z)))，x是受(?x)约束的变元；(?z)的辖域是(Q(x,z) ??R(x,z))，z是受(?z)约束的变元；没有自由变元。

（4）(?z)((?y)((?t)(P(z,t) ?Q(y,t))?R(z,y)))

解：(?z)的辖域是((?y)((?t)(P(z,t) ?Q(y,t))?R(z,y)))，z是受(?z)约束的变元；(?y)的辖域是((?t)(P(z,t) ?Q(y,t))?R(z,y))，y是受(?y)约束的变元；(?t)的辖域是(P(z,t) ?Q(y,t))，t是受(?t)约束的变元；没有自由变元。 （5）(?z)(?y)(P(z,y) ?(?z)((?y)(P(z,y) ?Q(z,y) ?(?z)(Q(z,y)))))

解：(?z)的辖域是(?y) (P(z,y) ?(?z)((?y)(P(z,y) ?Q(z,y) ?(?z)(Q(z,y)))))，z是受(?z)约束的变元；(?y)的辖域是(P(z,y) ?(?z)((?y)(P(z,y) ?Q(z,y) ?(?z)(Q(z,y)))))，y是受(?y)约束的变元；(?z)的辖域是((?y)(P(z,y) ?Q(z,y) ?(?z)(Q(z,y))))，z是受(?z)约束的变元；(?y)的辖域是(P(z,y) ?Q(z,y) ?(?z)(Q(z,y)))，y是受(?y)约束的变元；(?z)的辖域是(Q(z,y))，z是受(?z)约束的变元；没有自由变元。 7. 什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含？

解：永真性：如果谓词公式P，对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。

永假性：如果谓词公式P，对个体域D上的任何一个解释都取得真值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。

可满足性：对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可满足的。 等价性：若对共同的个体域D上的任何一个解释，谓词公式P与Q的取值都相同，则公式P和Q在域D上是等价的；如果D是任意个体域，则称P和Q是等价的。

永真蕴含：对于谓词公式P和Q，如果P?Q永真，则称P永真蕴含Q。 8. 谓词的永假性和不可满足性等价吗？

解：根据永假性和不可满足性的定义可知，两者是等价的。 9. 什么是置换？什么是合一？什么是最一般的合一？

解：置换是形如｛t1/x1，t2/x2，?，tn/xn｝的一个有限集。其中xi是变量，ti是不同于xi的项（常量，变量，函数），且xi?xj（i?j），i，j=1，2，?，n。

设有公式集｛E1，E2，?，En｝和置换?，使E1?＝E2?＝?＝En?，便称E1，E2，?，En是可合一的，用称?为合一置换。 若E1，E2，?，En有合一置换?，且对E1，E2，?，En的任一置换?都存在一个置换?，使得?＝???，则称?是E1，E2，?，En的最一般合一置换。 10. 写出最一般合一置换的步骤。

8

解：设E1，E2两个谓词公式，其最一般合一置换算法： （1） 令W=｛E1，E2｝。

（2） 令k=0，Wk=W，?k=?；?是空置换，它表示不作置换。

（3） 如果Wk只有一个表达式，则算法停止，?k就是所要求的mgu。 （4） 找出Wk的不一致集Dk。

（5） 若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk 中出现，则置： ?k+1=?k?{ tk/xk} Wk+1=Wk?{ tk/xk} k=k+1 然后转（3）。 （6） 算法终止，W的mgu不存在。

11. 判断以下公式对是否可合一；若可合一，则求出最一般的合一。

（1）P(a,b)， P(x,y) 解：依据算法：

(1) 令W={P(a,b)，P(x,y)}。 (2) 令?0=?，W0=W。 (3) W0未合一。

(4) 从左到右找不一致集，得D0={a，x}。 (5) 取x0=x，t0=a，则

?1=?0?{ t0/ x0}=?0?{a/ x}={a/ x} W1= W0?1={P(a,b)，P(a,y)}

(3’) W1未合一。

(4’) 从左到右找不一致集，得D1={b，y}。

(5’) 取x1=y，t1=b，则

?2=?1?{ t1/ x1}=?1?{b/ y}={a/ x}?{b/ y}={a/x，b/y} W2= W1?2={P(a,b)，P(a,b)}

(3’’) W2已合一，因为其中包含相同的表达式，这时?2={a/x，b/y}即为所求的mgu。

（2）P(f(z)),b)， P(y,x) 解：依据算法：

(1) 令W={P(f(z),b)，P(y,x)}。 (2) 令?0=?，W0=W。 (3) W0未合一。

(4) 从左到右找不一致集，得D0={f(z)，y}。 (5) 取x0=y，t0=f(z)，则

?1=?0?{ t0/ x0}=?0?{f(z)/ y}={f(z)/y} W1= W0?1={P(f(z),b)，P(f(z),x)}

(3’) W1未合一。

(4’) 从左到右找不一致集，得D1={b，x}。

(5’) 取x1=x，t1=b，则

?2=?1?{ t1/ x1}=?1?{b/ x}={ f(z)/ y}?{ b/ x}={f(z)/y，b/x} W2= W1?2={P(f(z),b)，P(f(z),b)}

(3’’) W2已合一，因为其中包含相同的表达式，这时?2={f(z)/y，b/x}即为所求的mgu。

（3）P(f(x),y)， P(y,f(a)) 解：依据算法：

(1) 令W={P(f(x),y)，P(y,f(a))}。 (2) 令?0=?，W0=W。 (3) W0未合一。

(4) 从左到右找不一致集，得D0={f(x)，y}。

9

(5) 取x0=y，t0=f(x)，则

?1=?0?{ t0/ x0}=?0?{f(x)/ y}={f(x)/y} W1= W0?1={P(f(x),f(x))，P(f(x),f(a))}

(3’) W1未合一。

(4’) 从左到右找不一致集，得D1={y，f(a)}。

(5’) 取x1=y，t1=f(a)，则

?2=?1?{ t1/ x1}=?1?{f(a)/ y}={ f(x)/ y}?{ f(a)/ y}={f(x)/y} W2= W1?2={P(f(x),f(x))，P(f(x),f(a))}

(6) 算法终止，W的mgu不存在。 （4）P(f(y),y,x)， P(x,f(a),f(b)) 解：依据算法：

(1) 令W={P(f(y),y,x)，P(x,f(a),f(b))}。 (2) 令?0=?，W0=W。 (3) W0未合一。

(4) 从左到右找不一致集，得D0={f(y)，x}。 (5) 取x0=x，t0=f(y)，则

?1=?0?{ t0/ x0}=?0?{f(y)/ x}={f(y)/x} W1= W0?1={P(f(y),y,f(y))，P(f(y),f(a),f(b))}

(3’) W1未合一。

(4’) 从左到右找不一致集，得D1={y，f(a)}。

(5’) 取x1=y，t1=f(a)，则

?2=?1?{ t1/ x1}=?1?{f(a)/ y}={ f(y)/ x}?{ f(a)/ y}={f(f(a))/x,f(a)/y} W2= W1?2={P(f(f(a)),f(a),f(f(a)))，P(f(f(a)),f(a),f(b))}

(6) 算法终止，W的mgu不存在。 （5）P(x,y)， P(y,x) 解：依据算法：

(1) 令W={P(x,y)，P(y,x)}。 (2) 令?0=?，W0=W。 (3) W0未合一。

(4) 从左到右找不一致集，得D0={x，y}。 (5) 取x0=x，t0=y，则

?1=?0?{ t0/ x0}=?0?{y/ x}={y/ x} W1= W0?1={P(y,y)，P(y,y)}

(3’) W2已合一，因为其中包含相同的表达式，这时?1={y/x}即为所求的mgu。 12. 什么是范式？请写出前束范式与SKOLEM范式的形式。

定义：量词按照一定的规则出现的谓词公式。

前束范式形式：(?x) (?y)(?z)(P(x)?F(y,z)?Q(y,z)) SKOLEM范式形式：(?x1) (?x2)? (?xn)M(x1，x2，?，xn） 13. 什么是子句？什么是子句集？请写出谓词公式子句集的步骤。

解：子句就是由一些文字组成的析取式。由子句构成的集合称为子句集。

步骤：（1）消去谓词公式中的蕴涵和双条件符号，以?A?B代替A?B，以(A?B)?(?A??B)替换A?B。 （2）减少不定符号的辖域，使不定符号最多只作用到一个谓词上。

（3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。 （4）消去存在量词。

（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。

10

本文来源：https://www.bwwdw.com/article/mlht.html