使用归结演绎推理证明g是f1f2的逻辑结论

第三章确定性推理方法习题参考解答3.1 练习题3.1 什么是命题？请写出3个真值为T 及真值为F 的命题。

3.2 什么是谓词？什么是谓词个体及个体域？函数与谓词的区别是什么？3.3 谓词逻辑和命题逻辑的关系如何？有何异同？3.4 什么是谓词的项？什么是谓词的阶？请写出谓词的一般形式。

3.5 什么是谓词公式？什么是谓词公式的解释？设D= {1,2} ，试给出谓词公式（ x）（ y）（P（x,y） Q（x,y））的所有解释，并且对每一种解释指出该谓词公式的真值。

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

（1）( x)(P(x, y) ( y)(Q(x, y) R(x, y)))（2）( z)( y)(P(z, y) Q(z, x)) R(u, v)（3）( x)(~ P( x, f (x )) ( z)(Q(x,z) ~ R(x,z)))（4）( z)(( y)(( t)(P(z, t) Q(y, t)) R(z, y))（5）( z)( y)(P(z, y) ( z)(( y)(P(z, y) Q(z, y) ( z)Q(z, y))))什么是谓词公式的永真性、永假性、可满足性、等价性及永真蕴含？3.7什么是置换？什么是合一？什么是最一般的合一？3.8判断以下公式对是否可合一；若可合一，则求出最一般的合一：3.9（1）P(a,b) ，P(x, y)（2）P(f(z),b) ，P(y, x)（3）P(f(x), y) ，P(y, f(a))（4）P(f(y), y,x) ，P(x, f(a), f(b))（5）P(x, y) ，P(y, x)什么是范式？请写出前束型范式与SKOLEM 范式的形式。

3.10什么是子句？什么是子句集？请写出求谓词公式子句集的步骤。

3.113.12谓词公式与它的子句集等值吗？在什么情况下它们才会等价？3.13 把下列谓词公式分别化为相应的子句集：(1)( z)( y)(P(z, y) Q(z, y))(2)( x)( y)(P(x, y) Q(x, y))(3)( x)( y)(P(x, y) (Q(x, y) R(x, y)))(4)( x)( y)( z)(P(x, y) Q(x, y) R(x, z))(5)( x)( y)( z)( u)( v)( w)(P(x, y,z,u,v,w) (Q(x, y, z,u, v, w) ~R(x, z, w)))3.14 判断下列子句集中哪些是不可满足的：(1)S {~ P Q,~ Q,P,~ P}(2)S {P Q,~ P Q,P ~ Q,~ P ~ Q}(3)S {P(y) Q(y), ~ P(f(x)) R(a)}(4)S {~ P(x) Q(x), ~ P(y) R(y), P(a),S(a),~ S(z) ~ R(z)}(5)S {~ P(x) ~ Q(y) ~ L(x, y), P(a), ~ R(z) L(a, z), R(b), Q(b)}(6)S {~ P(x) Q(f(x), a), ~ P(h(y)) Q(f(h(y)), a) ~ P(z)}(7)S {P(x) Q(x) R(x),~ P(y) R(y),~Q(a),~ R(b)}(8)S {P(x) Q(x),~ Q(y) R(y), ~ P(z) Q(z),~ R(u)}3.15 为什么要引入Herbrand 理论？什么是H 域？如何求子句集的H 域？3.16 什么是原子集？如何求子句集的原子集？3.17 什么是H 域解释？如何用域D 上的一个解释I 构造H 域上的解释I *呢？3.18 假设子句集S＝{P(z) ∨Q(z),R(f(t))} ，S 中不出现个体常量符号。

第三章归结演绎推理摘要：本文对归结对归结演绎推理进行了较为详细的介绍，描述了归结演绎推理的基本思路、使用步骤、并指明了其过程是完备的，还给出了运用归结原理进行归归结的具体例子，最后简单总结了其优缺点。

关键词：归结，演绎，推理1 知识背景人工智能是一门新兴的学科，推理技术是实现人工智能的基本技术之一，其中自然演绎推理是基于常用逻辑等价式以及常用逻辑蕴含式(统称推理规则)的推理技术，即从已知事实出发，利用推理规则进行推出结论的过程。

这种推理过程与人类的思维过程极其相似，但其缺点是极易产生知识爆炸，推理过程中得到的中间结论按指数规律递增，对于复杂问题的推理不利，在计算机上实现起来存在诸多困难。

而归结演绎推理是基于归结原理的在计算机上得到了较好实现的一种推理技术，是一种有效的机器推理方法。

归结原理的出现, 使得自动定理证明成为了可能，同时也使得人工智能技术向前迈进了一大步。

2 基本思路归结演绎方法是一种基于鲁滨逊（Robinson ）归结原理的机器推理技术【1】。

鲁滨逊归结原理也称作消解原理，是鲁滨逊于1965年在海伯伦（Herbrand ）理论的基础上提出的一种基于逻辑的“反证法”。

在人工智能中基本上几乎所有的问题都可以转化为一个定理证明问题。

而定理证明的实质就是要从公式集12n P={P P P }，，出发推出结论G ，即需要证明12n P P P G ∧∧∧→（）永真。

要证明P G →永真，若按定义来，需要证明P G →在任何一个非空的个体域上都是永真的。

这将是非常困难的，甚至是不可实现的。

为此人们进行了大量的探索，后来发现可以采用反证法的思想，把关于永真性的证明转化为关于不可满足性的证明。

即要证明P G →永真，只要能够证明P G ∧⌝是不可满足的就可以了。

在这一方面最有成效的的工作就是海伯伦理论和鲁滨逊归结原理。

鲁滨逊归结原理使定理证明的机械化成为了现实。

他们这些研究成果，在人工智能的发展史上都占有很重要的历史地位。

人工智能课后答案第三章本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March1.基于谓词逻辑的机器推理方法：自然演绎推理，归结演绎推理，基于规则的演绎推理。

2. 求下列谓词公式的子句集(1) x y(P(x,y) Q(x,y))解：去掉存在量词变为：P(a,b)Q(a,b) 变成子句集{ P(a,b),Q(a,b )}(2) 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)}(3) {()[(,)(,,)]}x P x y zQ x z zR x y z ∀→∃∀∨∀()(,)(,(),)P x Q x z R x f x z ⌝∨∨(4)((,,,,,)(,,,,,)(,,,,,))x y z u v w P x y z y v w Q x y z y v w R x y z u v w ∃∀∃∃∀∃∨∧ {p(a,y,f(y),y,v,g(y,v)) Q(a,y,f(y),y,v,g(y,v)), p(a,x,f(x),x,z,g(x,z))R(a,x,f(x),h(x),z,g(x,z))} 3. 试判断下列子句集中哪些是不可满足的（1）使用删除策略（2）归结 4.用合一算法求下列公式集的最一般合一。

（1）W={Q(a,x),Q(y,b)} 最一般合一为:{a/y,b/y} （2）{()((,))}W Q x y z Q u h v v u =，，，，，最一般合一为：{z/u,h(v,v)/y,z/x}或{x/u,h(v,v)/y,x/z}5.用归结原理证明，G 是否可肯定是F 的逻辑结果。

(1) F 1 (x)(P(x)(Q(x)∧R(x)) F 2 (x) (P(x) ∧S(x) G (x)(S(x) ∧R(x)) 证明：利用归结反演法，先证明F 1 ∨ F 2 ∨¬G 是不可满足的。

人工智能第1部分绪论1-1.什么是人工智能？试从学科和能力两方面加以说明。

答：从学科方面定义：人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支。

它的近期目标在于研究用机器来模拟和执行人脑的某些智力功能，并开发相关理论和技术从能力方面定义：人工智能是智能机器所执行的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。

1-2.在人工智能的发展过程中，有哪些思想和思潮起了重要作用？答：1）数理逻辑和关于计算本质的新思想，提供了形式推理概念与即将发明的计算机之间的联系；2）1956年第一次人工智能研讨会召开，标志着人工智能学科的诞生；3）控制论思想把神经系统的工作原理与信息理论、控制理论、逻辑以及计算联系起来，影响了许多早期人工智能工作者，并成为他们的指导思想；4）计算机的发明与发展；5）专家系统与知识工程；6）机器学习、计算智能、人工神经网络和行为主义研究，推动人工智能研究的近一步发展。

1-3.为什么能够用机器（计算机）模仿人的智能？答：物理符号系统的假设：任何一个系统，如果它能够表现出智能，那么它就必定能执行输入符号、输出符号、存储符号、复制符号、建立符号结构、条件迁移6种功能。

反之，任何系统如果具有这6种功能，那么它就能够表现出智能（人类所具有的智能）。

物理符号系统的假设伴随有3个推论。

推论一：既然人具有智能，那么他（她）就一定是各物理符号系统；推论二：既然计算机是一个物理符号系统，它就一定能够表现出智能；推论三：既然人是一个物理符号系统，计算机也是一个物理符号系统，那么我们就能够用计算机来模拟人的活动。

1-4.人工智能的主要研究内容和应用领域是什么？其中，哪些是新的研究热点？答：研究和应用领域：问题求解（下棋程序），逻辑推理与定理证明（四色定理证明），自然语言理解，自动程序设计，专家系统，机器学习，神经网络，机器人学（星际探索机器人），模式识别（手写识别，汽车牌照识别，指纹识别），机器视觉（机器装配，卫星图像处理），智能控制，智能检索，智能调度与指挥（汽车运输高度，列车编组指挥），系统与语言工具。

一、选择题1.被誉为“人工智能之父”的科学家是（C ）。

A. 明斯基B.图灵 C. 麦卡锡D. 冯.诺依曼 2. AI的英文缩写是( B ) A. Automatic Intelligence C. Automatic InformationB. Artificial Intelligence D. Artificial Information3.下列那个不是子句的特点（D） A.子句间是没有合取词的(∧) C子句中可以有析取词(∨)4.下列不是命题的是（C ）。

A.我上人工智能课B. 存在最大素数C.请勿随地大小便D. 这次考试我得了101分 5. 搜索分为盲目搜索和（A）A启发式搜索 B模糊搜索 C精确搜索D大数据搜索6.从全称判断推导出特称判断或单称判断的过程，即由一般性知识推出适合于某一具体情况的结论的推理是（B） A. 归结推理 B. 演绎推理 C. 默认推理 D. 单调推理7.下面不属于人工智能研究基本内容的是（ C） A. 机器感知 B. 机器学习B子句通过合取词连接句子(∧)D子句间是没有析取词的(∨)C. 自动化D. 机器思维8.S={P∨Q∨R, ┑Q∨R, Q, ┑R}其中, P 是纯文字，因此可将子句（A）从 S中删去 A. P∨Q∨R C. QB. ┑Q∨RD.┑R9.下列不属于框架中设置的常见槽的是（ B ）。

A. ISA槽B.if-then槽C. AKO槽D. Instance槽 10.常见的语意网络有（ D ）。

A. A-Member-of联系 C. have 联系1.在深度优先搜索策略中，open表是（B ）的数据结构 A.先进先出B.先进后出C. 根据估价函数值重排D.随机出 2.归纳推理是（B）的推理A. 从一般到个别B. 从个别到一般C. 从个别到个别D. 从一般到一般3. 要想让机器具有智能，必须让机器具有知识。

因此，在人工智能中有一个研究领域，主要研究计算机如何自动获取知识和技能，实现自我完善，这门研究分支学科叫（B ） A.专家系统B.机器学习B. Composed–of联系 D.以上全是C.神经网络D.模式识别4. 下列哪个不是人工智能的研究领域（D） A.机器证明B.模式识别 C.人工生命D.编译原理6. 在主观Bayes方法中，几率O(x)的取值范围为（D ） A.[-1, 1] B.[0, 1] C.[-1, ∞）D.[0, ∞）7. 仅个体变元被量化的谓词称为 ( A) A.一阶谓词B.原子公式C.二阶谓词D.全称量词8. 在可信度方法中，CF（H，E）的取值为（C ）时，前提E为真不支持结论H为真。

习题一1.什么是人类智能？它有哪些特征或特点？定义：人类所具有的智力和行为能力。

特点：主要体现为感知能力、记忆与思维能力、归纳与演绎能力、学习能力以及行为能力。

2.人工智能是何时、何地、怎样诞生的？解：人工智能于1956年夏季在美国Dartmouth大学诞生。

此时此地举办的关于用机器模拟人类智能问题的研讨会，第一次使用“人工智能”这一术语，标志着人工智能学科的诞生。

3.什么是人工智能？它的研究目标是什么？定义：用机器模拟人类智能。

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

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

5.人工智能研究的基本内容有哪些？解：知识的获取、表示和使用。

6.人工智能有哪些主要研究领域？解：问题求解、专家系统、机器学习、模式识别、自动定论证明、自动程序设计、自然语言理解、机器人学、人工神经网络和智能检索等。

7.人工智能有哪几个主要学派？各自的特点是什么？主要学派：符号主义和联结主义。

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

8.人工智能的近期发展趋势有哪些？解：专家系统、机器人学、人工神经网络和智能检索。

9.什么是以符号处理为核心的方法？它有什么特征？解：通过符号处理来模拟人类求解问题的心理过程。

特征：基于数学逻辑对知识进行表示和推理。

10.什么是以网络连接为主的连接机制方法？它有什么特征？解：用硬件模拟人类神经网络，实现人类智能在机器上的模拟。

第3章确定性推理部分参考答案判断下列公式是否为可合一，若可合一，则求出其最一般合一。

(1) P(a, b), P(x, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b))(4) P(f(y), y, x), P(x, f(a), f(b))(5) P(x, y), P(y, x)解：(1) 可合一，其最一般和一为：σ={a/x, b/y}。

(2) 可合一，其最一般和一为：σ={y/f(x), b/z}。

(3) 可合一，其最一般和一为：σ={ f(b)/y, b/x}。

(4) 不可合一。

(5) 可合一，其最一般和一为：σ={ y/x}。

把下列谓词公式化成子句集：(1)(∀x)(∀y)(P(x, y)∧Q(x, y))(2)(∀x)(∀y)(P(x, y)→Q(x, y))(3)(∀x)(∃y)(P(x, y)∨(Q(x, y)→R(x, y)))(4)(∀x) (∀y) (∃z)(P(x, y)→Q(x, y)∨R(x, z))解：(1) 由于(∀x)(∀y)(P(x, y)∧Q(x, y))已经是Skolem标准型，且P(x, y)∧Q(x, y)已经是合取范式，所以可直接消去全称量词、合取词，得{ P(x, y), Q(x, y)}再进行变元换名得子句集：S={ P(x, y), Q(u, v)}(2) 对谓词公式(∀x)(∀y)(P(x, y)→Q(x, y))，先消去连接词“→”得：(∀x)(∀y)(P(x, y)∨Q(x, y))此公式已为Skolem标准型。

再消去全称量词得子句集：S={P(x, y)∨Q(x, y)}(3) 对谓词公式(∀x)(∃y)(P(x, y)∨(Q(x, y)→R(x, y)))，先消去连接词“→”得：(∀x)(∃y)(P(x, y)∨(Q(x, y)∨R(x, y)))此公式已为前束范式。

再消去存在量词，即用Skolem函数f(x)替换y得：(∀x)(P(x, f(x))∨Q(x, f(x))∨R(x, f(x)))此公式已为Skolem标准型。

第三章演绎推理自动定理证明是人工智能一个重要的研究领域，是早期取得较大成果的研究课题之一，在发展人工智能方法上起过重大作用。

1956，美国，Newell, Simon, Shaw编制逻辑理论机：The Logic Theory Machine 简称LT. 证明了《数学原理》（罗素）第二章中38个定理, 改进后证明了全部52个定理。

是对人的思维活动进行研究的重大成果，是人工智能研究的真正开端。

在此之后，发展了一些机械化推理算法，很成功地用到人工智能系统中。

第一节鲁滨逊归结原理一、命题逻辑中归结推理1.归结：消去子句中互补对的过程：子句：任何文字的析取式C称为子句，C=P∨Q∨7R={P,Q,7R}如：C1=LVC1`={L,C1`}C2=7LVC2`={7L,C2`}可以证明C12=C1`VC2`={C1`,C2`}是C1,C2的逻辑结论：即：C1∧C2⇒C12证明：C1=LVC1`=77C1`VL=7C1`→LC2=7LVC2`=L→C2`所以7C1`→C2`=77C1`VC2`=C1`VC2`实际上是P→Q, Q → P⇒P→R的应用即前提成立⇒结论成立，也即结论不成立⇒前提不成立S子句集：其中有C1,C2归结式S`子句集：C12代替C1,C2则：S`不可满足⇒S不可满足2.归结推理步骤要证A⇒B成立(或证A→B重言、永真)，只要证A∧7B不可满足(永假)①化A∧7B为合取范式C1∧C2∧……∧Cm②子句集S={C1,C2,…, Cm}③归结规则用于S，归结式入S中.④重复③，直到S中出现空子句。

证明：SVR是P∨Q , P →R，Q→S的逻辑结论。

（P∨Q) ∧(P →R) ∧(Q→S) ∧7(S∨R)=（P∨Q）∧(7P∨R) ∧(7Q∨S) ∧7S∧7R所以S={P∨Q,7P∨R,7Q∨S,7S,7R}(1)P∨Q(2)7P∨R(3)7Q∨S(4)7S(5)7R(6)Q∨R (1)(2) 归结(7)7Q (3)(4) 归结(8)Q (5)(6) 归结(9)F (7)(8) 归结命题逻辑中不可满足的子句集S，使用归结原理，总能在有限步内得到一个空子句⇒归结原理是完备的。

确定性推理练习题1．判断下列公式是否为可合一，若可合一，则求出其最一般合一。

(1) P(a, b), P(x, y)(2) P(f(x), b), P(y, z)(3) P(f(x), y), P(y, f(b))(4) P(f(y), y, x), P(x, f(a), f(b))(5) P(x, y), P(y, x)2．把下列谓词公式化成子句集：(1)(∀x)(∀y)(P(x, y)∧Q(x, y))(2)(∀x)(∀y)(P(x, y)→Q(x, y))(3)(∀x)(∃y)(P(x, y)∨(Q(x, y)→R(x, y)))(4)(∀x) (∀y) (∃z)(P(x, y)→Q(x, y)∨R(x, z))3．判断下列子句集中哪些是不可满足的：(1){¬P∨Q, ¬Q, P, ¬P}(2){ P∨Q ,¬P∨Q, P∨¬Q, ¬P∨¬Q }(3){ P(y)∨Q(y) ,¬P(f(x))∨R(a)}(4){¬P(x)∨Q(x) ,¬P(y)∨R(y), P(a), S(a), ¬S(z)∨¬R(z)}(5){¬P(x)∨Q(f(x),a) ,¬P(h(y))∨Q(f(h(y)), a)∨¬P(z)}(6){P(x)∨Q(x)∨R(x) ,¬P(y)∨R(y), ¬Q(a), ¬R(b)}4．对下列各题分别证明G是否为F1,F2,…,F n的逻辑结论：(1)F: (∃x)(∃y)(P(x, y)G: (∀y)(∃x)(P(x, y)(2)F: (∀x)(P(x)∧(Q(a)∨Q(b)))G: (∃x) (P(x)∧Q(x))(3)F: (∃x)(∃y)(P(f(x))∧(Q(f(y)))G: P(f(a))∧P(y)∧Q(y)(4)F1: (∀x)(P(x)→(∀y)(Q(y)→⌝L(x.y)))F2: (∃x) (P(x)∧(∀y)(R(y)→L(x.y)))G: (∀x)(R(x)→⌝Q(x))(5)F1: (∀x)(P(x)→(Q(x)∧R(x)))F2: (∃x) (P(x)∧S(x))G: (∃x) (S(x)∧R(x))5．设已知：(1)如果x是y的父亲，y是z的父亲，则x是z的祖父；(2)每个人都有一个父亲。