归结推理方法

归结推理⽅法（三）归结推理⽅法（三）引⼊新课：数理逻辑为知识的推理奠定了基础；基于⼀阶谓词逻辑的推理⽅法，是⼀种机械化的可在计算机上加以实现的推理⽅法。

⼀、命题逻辑命题逻辑和谓词逻辑是两种逻辑；对知识的形式化表⽰，特别是定理的⾃动证明发挥了重要作⽤。

谓词逻辑是在命题逻辑的基础上发展起来的。

命题逻辑可看作是谓词逻辑的⼀种特殊形式。

（⼀）命题定义1能够分辨真假的语句称作命题定义2⼀个语句如果不能再进⼀步分解成更简单的语句，并且⼜是⼀个命题，则称此命题为原⼦命题。

说明：（1）原⼦命题是命题中最基本的单位，⽤P,Q,R,…..⼤写拉丁字母表⽰。

⽽命题的真与假分别⽤“T”与“F”表⽰。

命题代表⼈们进⾏思维时的⼀种判断，或者是真。

或者是假，只有这两种情况。

若命题的意义为真，则记为T。

若命题的意义为假，则记为F。

（2）⼀般情况下，只有陈述句才可能是命题，因为只有陈述句才能分辨真假。

如“太阳从西边升起”、“雪是⽩⾊的”等等都是陈述句，⽽其他的⼀些句⼦如疑问句、祈使句、感叹句等均不能分辨其真假。

象这样的没有真假意义的句⼦就不是命题。

（3）并不是所有的陈述句都是命题；例如，“这个句⼦是假的”。

显然⽆法判断该语句的真假，这个语句不是命题。

（4）在有些情况下，要判断⼀个陈述句的真假，是需要⼀定条件的，即该陈述句在⼀种条件下，其逻辑值为真，但在另⼀种条件下，其逻辑值为假。

⽐如，“1+1=10”。

（5）⽤⼤写字母表⽰的命题既可以是⼀个特定的命题，也可以是⼀个抽象命题。

前者称为命题常量，后者称为命题变量。

对于命题变量，只有把确定的命题代⼊后，它才可能有明确的逻辑值（T或F）。

（⼆）命题公式连接词：在⽇常⽣活中，可以通过连接词将⼀些简单的陈述句组成较为复杂的语句，称为复合句。

较复杂的定义。

～：称为“⾮”或“否定”。

其作⽤是否定位于它后⾯的命题。

当命题P为真时，～P为假；当P 为假时，～P为真。

∨：称为“析取”。

它表⽰被它连接的两个命题具有“或”关系。

命题逻辑归结法是一种用于判断命题之间是否逻辑等价的推理方法。

具体来说，它是通过将两个命题的否定命题应用于彼此的逻辑项，来判断它们是否可以转化为同一命题。

其基本步骤如下：
1.确定待判断的两个命题P和Q。

2.将命题P和Q转化为合取范式或析取范式。

3.对P和Q的合取范式或析取范式中的逻辑项进行编号，以区分
不同的逻辑项。

4.构造一个包含P和Q的集合S，并将S的否定命题取出，形成
一个新的集合S'。

5.遍历S和S'中的所有逻辑项，如果存在两个逻辑项分别出现在
S和S'中，且它们的逻辑关系相反，则将这两个逻辑项从S和
S'中删除，并加入一个新的逻辑项，该逻辑项是这两个逻辑项
的剩余部分。

6.重复步骤5，直到S和S'中不存在相同的逻辑项或者无法再进
行归结。

7.若最终S和S'中均不包含任何逻辑项，则P和Q是逻辑等价
的；否则，它们不是逻辑等价的。

命题逻辑归结法是一种常用的推理方法，它可以应用于计算机科学、人工智能、自然语言处理等领域。

使用归结演绎推理证明g是f1f2的逻辑结论
一、引言
在数学中，归结演绎推理是一种绐理推理形式，它可以从一组已知条件来证明一个逻辑结论，比如证明g是f1f2的逻辑结论。

这种推理方式可以从给定的任务开始，把已知的事实以演绎的方式，一步步递进下去来证明要证明的结论，给出一系列反证考虑，最终达到“全部正确”的地步，则认为结论可以得到证明。

因此本文旨在全面阐述归结演绎推理证明g是f1f2的逻辑结论。

二、归结演绎推理的基本原理
1. 定义
归结演绎推理是一种解决问题逻辑处理的重要方法，它从一组已知条件出发，连续推出一个或者多个逻辑结论，从而达到把复杂问题变为简单问题的目的。

2. 演绎法的顺序
演绎法顺序主要有三个：首先说明要证明的结论，然后说明各个具体步骤，再将每一步前后的理由相连起来，最后得出结论。

三、对g是f1f2的逻辑结论证明的演绎步骤
1. 首先，假设f1f2的逻辑结论是g，即：g=f1f2。

2. 接着，将f1f2以逻辑表达式的形式表示出来，形如：g1=f1，g2=f2。

3. 比较g1和g2，易知f1要满足g1的条件，而f2要满足g2的条件，而且两个条件一定会同时成立。

4. 因此，可以知道若f1、f2同时满足自身的要求g1、g2，则g也必定成立，所以已有结论g=f1f2得到证明。

五、结论
本文简要介绍了归结演绎推理的基本原理及其在证明g是f1f2的逻辑结论问题上的应用，即f1，f2同时满足自身的要求g1，g2，则g也必定成立，其应用过程也被简要介绍出来，经过一系列的反证思考，最终达到全部正确的地步，结果得出结论g=f1f2。

可见，归结演绎推理是一种有效明确的方法，可以有效地解决一些复杂的逻辑问题。

人工智能第三章归结推理方法
第三章主要讨论归结推理方法，归结推理方法是人工智能领域中的一种重要技术。

归结推理是一种推理过程，它从一个给定的知识库出发，将给定的输入推断，得出想要的结果。

归结推理是一种推断过程，它把已有的规则和数据应用到新的数据中，来解决新问题。

归结推理可以从三个层面来分析：
1.处理模型
在归结推理中，首先要建立一个处理模型，这个模型是一种结构，它描述了归结推理的步骤，以及归结推理过程中用到的数据和知识。

2.知识表示
归结推理过程是基于知识库，而知识的表示是归结推理中最重要的环节。

知识的表示是一种在计算机中存储、表示和管理数据的方法，它决定了归结推理过程中的正确性和性能。

3.推理机制
推理机制是归结推理过程中，根据已有的输入，对知识进行推理以及解决问题的一种机制。

它可以把归结推理分为计算环节和决策环节，从而实现和可靠的知识表示，实现更精确的推理过程。

基于上述三个层面，归结推理方法可以有效的解决知识表示、理解和存储问题，实现可靠的推理过程，从而解决复杂的问题。

2.4 归结原理本节在上节的基础上，进一步具体介绍谓词逻辑的归结方法。

谓词逻辑的归结法是以命题逻辑的归结法为基础，在Skolem 标准性的子句集上，通过置换和合一进行归结的。

下面先介绍一些本节中用到的必要概念：一阶逻辑：谓词中不再含有谓词的逻辑关系式。

个体词：表示主语的词谓词：刻画个体性质或个体之间关系的词量词：表示数量的词个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R量词符号：,归结原理正确性的根本在于，如果在子句集中找到矛盾可以肯定命题是不可满足的。

2.4.1 合一和置换置换：置换可以简单的理解为是在一个谓词公式中用置换项去置换变量。

定义：置换是形如{t1/x1, t2/x2, …, t n/x n}的有限集合。

其中，x1, x2, …, x n是互不相同的变量，t1, t2, …, t n是不同于x i的项（常量、变量、函数）；t i/x i表示用t i置换x i，并且要求t i与x i不能相同，而且x i不能循环地出现在另一个t i中。

例如{a/x，c/y，f(b)/z}是一个置换。

{g(y)/x，f(x)/y}不是一个置换，原因是它在x和y之间出现了循环置换现象。

置换的目的是要将某些变量用另外的变量、常量或函数取代，使其不在公式中出现。

但在{g(y)/x，f(x)/y}中，它用g(y)置换x，用f(g(y))置换y，既没有消去x，也没有消去y。

若改为{g(a)/x，f(x)/y}就可以了。

通常，置换用希腊字母θ、σ、α、λ来表示的。

定义：置换的合成设θ＝{t1/x1, t2/x2, …, t n/x n}，λ＝{u1/y1, u2/y2, …, u n/y n}，是两个置换。

则θ与λ的合成也是一个置换，记作θ·λ。

它是从集合{t1·λ/x1, t2·l/x2, …, t n·λ/x n, u1/y1, u2/y2, …, u n/y n}即对ti先做λ置换然后再做θ置换，置换xi中删去以下两种元素：i. 当t iλ＝x i时，删去t iλ/x i(i = 1, 2, …, n);ii. 当y i∈{x1,x2, …, x n}时，删去u j/y j(j = 1, 2, …, m)最后剩下的元素所构成的集合。

第四章归结推理方法
归结推理方法是推断和推理过程中非常重要的一种方法，它可以帮助学习者把已有的知识和经验运用在新的情况中。

简而言之，它就是把总的结论推导出更精确的结论。

归结推理的原理很简单：从一般的结论得出具体的结论。

可以说从一般原理中“抽离”出具体的结论。

那么，归结推理具体指的是什么呢？它指的是从具体的经历、观察和思考的结果推导出一般性的结论，然后再从这些结论推导出新的具体的结论，最后得出最终的结论。

归结推理的步骤主要有三个：首先，从具体的观察或经验中归纳出一般原理；其次，根据这些一般原理，以及其他相关的原理和知识系统，推出一般结论；最后，继续推出新的具体结论。

归结推理的结果总是以一般结论作为起点，以更为具体的结论作为终点。

它可以帮助我们提取出更多的知识，找出更深层的原因，并从中得到更准确的结论。

归结推理的过程很简单，但也需要一定的观察和思考能力，如果可以认知到这一点，就可以更好地利用这一推理方法。

在实践中，归结推理方法可以帮助我们提取出更多的知识，分析问题的原因，提出更有效的解决方案。

归结原理简单概述
归结原理是一种推理规则。

归结原理是一种推理规则。

从谓词公式转化为子句集的过程中看出，在子句集中子句之间是合取关系，其中只要有一个子句不可满足，则子句集就不可满足。

若一个子句集中包含空子句，则这个子句集一定是不可满足的。

归结原理就是基于这一认识提出来的。

他的原理就是：
P->Q,Q->R 则P->R
由于P->Q 就是￢P∨Q
而Q->R 就是￢Q∨R
所以，他相当于将Q 和￢Q合并。

也就是说，
P∨{∑1} 与~P∨{∑2}
可以归结为{∑1}∨{∑2}
其中∑1,∑2是文字的集合
一种归结技术
当外加上完备的查找算法的时候，归结规则生成一个可靠的和完备的算法来决定命题公式的可满足性，并且经过扩展，决定句子在一组公理下的有效性。

这种归结技术使用反证法，并基于在命题逻辑中的任何句子都能转换成等价的合取范式句子的事实。

2.5归结过程控制策略从命题逻辑和谓词逻辑的归结方法中我们可以看出，当使用归结法时，若从子句集S出发做所有可能的归结，并将归结式加入S中，再做第二层这样的归结，…直到产生空子句的这种盲目的全面归结的话，同样会产生组合爆炸问题。

这种无控制的盲目全面归结导致大量的不必要的归结式的产生，严重的是，它们又将产生下一层的更大量的不必要的归结式的产生。

于是，如何给出控制策略，以使系统仅选择合适的子句对其做归结来避免多余不必要的归结式的出现，或者说少做些归结但仍然导出空子句来，这已经成为一个重要的问题。

归纳起来，归结过程策略控制的要点如下：a)要解决的问题：归结方法的知识爆炸。

b)控制策略的目的：归结点尽量少c)控制策略的原则：删除不必要的子句，或对参加归结的子句做限制d)给出控制策略，以使仅选择合适的子句对其做归结。

避免多余的、不必要的归结式出现。

2.5.1删除策略归类：设有两个子句C和D，若有置换σ使得CσD成立，则称子句C把子句D归类。

画外音：可以理解为，由于小的可以代表大的，所以小的吃掉大的了。

若对S使用归结推理过程中，当归结式C j是重言式和Cj j被S中子句和子句集的归结式C i(i<j)所归类时，便将C j 删除。

这样的推理过程便称做使用了删除策略的归结过程。

删除策略的主要想法是：归结过程在寻找可归结子句时，子句集中的子句越多，需要付出的代价就会越大。

如果在归结时能把子句集中无用的子句删除掉，就会缩小搜索范围，减少比较次数，从而提高归结效率。

删除策略对阻止不必要的归结式的产生来缩短归结过程是有效的。

然而要在归结式C j产生后方能判别它是否可被删除，这部分计算量是要花费的，只是节省了被删除的子句又生成的归结式。

尽管使用删除策略的归结，少做了归结但不影响产生空子句，就是说删除策略的归结推理是完备的。

删除策略=>完备；但是，完备的归结推理采用删除策略不一定都有效。

删除策略是完备的意思是，采用归结策略进行的归结过程没有破坏归结法的完备性。

2.3 谓词逻辑归结法基础由于谓词逻辑与命题逻辑不同，有量词、变量和函数，所以在生成子句集之前要对逻辑公式做处理，具体的说就是要将其转化为Skolem 标准形，然后在子句集的基础上再进行归结，虽然基本的归结的基本方法都相同，但是其过程较之命题公式的归结过程要复杂得多。

过程要复杂得多。

本节针对谓词逻辑归结法介绍了Skolem 标准形、子句集等一些必要的概念和定理。

一些必要的概念和定理。

2．3．1 Skolem 标准形Skolem 标准形的定义：标准形的定义： 前束范式中消去所有的存在量词，则称这种形式的谓词公式为Skolem 标准形，任何一个谓词公式都可以化为与之对应的Skolem 标准形。

但是，Skolem 标准形不唯一。

标准形不唯一。

前束范式：A 是一个前束范式，如果A 中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。

式的末端。

Skolem 标准形的转化过程为，依据约束变量换名规则，首先把公式变型为前束范式，然后依照量词消去原则消去或者略去所有量词。

具体步骤如下：所有量词。

具体步骤如下：将谓词公式G 转换成为前束范式转换成为前束范式前束范式的形式为：前束范式的形式为：(Q 1x 1)(Q 2x 2)…(Q n x n )M(x 1,x 2,…,x n )即：即： 把所有的量词都提到前面去。

把所有的量词都提到前面去。

注意：由于所有的量词的辖域都延伸到公式的末端，即，最左边量词将约束表达式中的所有同名变量。

所以将量词提到公式最前端时存在约束变量换名问题。

要严守规则。

最前端时存在约束变量换名问题。

要严守规则。

约束变量换名规则：约束变量换名规则：(Qx ) M （x ） （Qy ） M （y ）(Qx ) M （x,z ） （Qy ）M （y,z ） 量词否定等值式：量词否定等值式：～(x ) M （x ） （y ） ～ M （y ）～(x ) M （x ） （y ） ～M （y ） 量词分配等值式：量词分配等值式：(x )( P （x ） ∧Q （x ）)(x ) P （x ） ∧ (x ) Q （x ） (x )( P （x ） ∨ Q （x ）) (x ) P （x ） ∨ (x ) Q （x ）消去量词等值式：设个体域为有穷集合（a1, a2, …an ）(x ) P （x ） P （a1） ∧ P （a2） ∧…∧ P （an ） (x ) P （x ） P （a1） ∨ P （a2） ∨… ∨ P （an ） 量词辖域收缩与扩张等值式：量词辖域收缩与扩张等值式：( x )( P （x ） ∨Q) ( x ) P （x ） ∨ Q (x )( P （x ） ∧Q) ( x ) P （x ） ∧ Q (x )( P （x ）→ Q) (x ) P （x ） → Q (x )( Q → P （x ） ) Q → (x ) P （x ）(x )( P （x ） ∨Q) (x ) P （x ） ∨ Q (x )( P （x ） ∧Q) (x ) P （x ） ∧ Q (x )( P （x ）→ Q) (x ) P （x ） → Q (x )( Q → P （x ）) Q → (x ) P （x ）消去量词量词消去原则： 1) 消去存在量词""，即，将该量词约束的变量用任意常量（a, b 等）、或全称变量的函数(f(x), g(y)等)代替。

2.2 命题逻辑的归结2.2.1 命题逻辑基础逻辑可分为经典逻辑和非经典逻辑，其中经典逻辑包括命题逻辑和谓词逻辑。

归结原理是一种主要基于谓词（逻辑）知识表示的推理方法，而命题逻辑是谓词逻辑的基础。

因此，在讨论谓词逻辑之前，先讨论命题逻辑的归结，便于内容上的理解。

本节中，将主要介绍命题逻辑的归结方法，以及有关的一些基础知识和重要概念，如数理逻辑基本公式变形、前束范式、子句集等。

描述事实、事物的状态、关系等性质的文字串，取值为真或假（表示是否成立）的句子称作命题。

命题：非真即假的简单陈述句在命题逻辑里，单元命题是基本的单元或作为不可再分的原子。

下面所列出的是一些基本的数理逻辑公理公式和一些有用的基本定义，如合取范式、子句集，这些公式和定义在归结法的推理过程中是必不可少的，也是归结法的基础，应该熟练掌握。

－数理逻辑的基本定义下面所列的是一些数理逻辑中重要的定义，在后面的分析中要用到：·合取式：p与q，记做p ∧q·析取式：p或q，记做p ∨q·蕴含式：如果p则q，记做p → q·等价式：p当且仅当q，记做p q·若A无成假赋值，则称A为重言式或永真式；·若A无成真赋值，则称A为矛盾式或永假式；·若A至少有一个成真赋值，则称A为可满足的；·析取范式：仅由有限个简单合取式组成的析取式·合取范式：仅由有限个简单析取式组成的合取式－数理逻辑的基本等值式下面这些基本的等式在归结原理实施之前的公式转化过程中是非常重要的。

只有将逻辑公式正确转换成为归结原理要求的范式，才能够保证归结的正常进行。

·交换律：p∨q q ∨p ；p ∧q q ∧p·结合律：(p∨q) ∨r p∨(q ∨r);(p ∧q) ∧r p ∧(q ∧r)·分配律：p∨(q ∧r) (p∨q)∧(p ∨r) ；p ∧(q ∨r) (p ∧q) ∨(p ∧r)·双重否定律：p ～～p·等幂律：p p∨p；p p∧p·摩根律: ～(p∨q) ～p ∧～q ；～(p ∧q) ～p ∨～q·吸收律: p∨(p∧q ) p ；p ∧(p∨q ) p·同一律: p∨0 p ；p∧1 p·零律：p∨1 1p∧0 0·排中律：p∨～p 1·矛盾律：p∧～p 0·蕴含等值式：p → q ～p∨q·等价等值式：p q (p → q)∧(q → p)·假言易位式: p → q ～p → ～q·等价否定等值式：p q ～p～q·归谬论：(p → q)∧(p → ～q) ～p－合取范式范式：范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们作一般性的处理。

简述归结演绎推理的基本原理
归结演绎推理是一种基于逻辑的推理方法，其基本原理是通过寻找两个假设的矛盾，从而得出一个结论。

具体步骤如下：
1. 归结：首先，将问题的前提和待求解的目标转化为逻辑表达式，且将其转换为逻辑语句的否定形式。

2. 归结规则：根据归结演算的规则，对逻辑语句应用归结规则，将其转化为一个新的逻辑语句。

3. 归结过程：通过不断应用归结规则，将逻辑语句归结为矛盾语句，即找到一个逻辑语句和其否定形式互为矛盾。

4. 得出结论：如果找到了矛盾语句，则说明原始问题是无解的，否则，根据矛盾语句的表达形式，可以得出结论。

归结演绎推理的基本原理是基于逻辑的矛盾，通过不断的应用归结规则，将问题化简为一个矛盾语句，从而得出结论。

这个推理过程类似于数学中的反证法，通过假设的否定形式来推导出矛盾的结果从而证明原假设的不成立。