1、2022-5-201o 推理就是按某种策略由已知判断推出另一判断的思维推理就是按某种策略由已知判断推出另一判断的思维过程过程o 已知判断：包括已掌握的与求解问题有关的知识已知判断：包括已掌握的与求解问题有关的知识 及关于问题的已知事实及关于问题的已知事实 推理的结论：由已知判断推出新判断推理的结论：由已知判断推出新判断o 推理由程序程序实现，称为推理机推理由程序程序实现，称为推理机2022-5-2021、演绎推理、归纳推理、默认推理、演绎推理、归纳推理、默认推理推理的基本任务是从一种判断推出另一种判断推理的基本任务是从一种判断推出另一种判断按判断推出的途径来划分，可分为演绎推理、归结推理按判断
2、推出的途径来划分，可分为演绎推理、归结推理及默认推理及默认推理（1）演绎推理）演绎推理演绎推理是从全称判断推导出特称判断或单称判断的过程演绎推理是从全称判断推导出特称判断或单称判断的过程演绎推理有多种形式，经常用的是三段论式演绎推理有多种形式，经常用的是三段论式三段论式包括三段论式包括大前提：已知的一般性知识或假设大前提：已知的一般性知识或假设小前提：关于所研究的具体情况或个别事实的判断小前提：关于所研究的具体情况或个别事实的判断结论：由大前提推出的适合于小前提所示情况的新判断结论：由大前提推出的适合于小前提所示情况的新判断2022-5-203n 在任何情况下，由演绎推导出的结论都是蕴涵在大前
3、在任何情况下，由演绎推导出的结论都是蕴涵在大前提的一般性知识中提的一般性知识中n 只要大前提和小前提是正确的，则由它们推出的结论只要大前提和小前提是正确的，则由它们推出的结论必然是正确的必然是正确的(2) 归纳推理归纳推理归纳推理是从足够多的事例中归纳出一般性结论的推归纳推理是从足够多的事例中归纳出一般性结论的推理过程，是一种从个别到一般的推理理过程，是一种从个别到一般的推理归纳推理：完全归纳推理、不完全归纳推理归纳推理：完全归纳推理、不完全归纳推理完全归纳推理是在进行归纳时考察了相应事物的全部完全归纳推理是在进行归纳时考察了相应事物的全部对象，并根据这些对象是否都具有某种属性，从而推对象，并
4、根据这些对象是否都具有某种属性，从而推出这个事物是否具有这个属性出这个事物是否具有这个属性不完全归纳推理是指只考察了相应事物的部分对象就不完全归纳推理是指只考察了相应事物的部分对象就得出了结论得出了结论2022-5-204n 枚举归纳推理：若已知某类事物的有限可数个具体事枚举归纳推理：若已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此属性物都具有某种属性，则可推出该类事物都具有此属性n 类比推理：在两个或两类事物有许多属性都相同或相类比推理：在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的似的基础上，推出它们在其他属性上也相同或相似的一
5、种推理一种推理(3) 默认推理默认推理又称缺省推理，它是在知识不完全的情况下假设某些又称缺省推理，它是在知识不完全的情况下假设某些条件已经具备所进行的推理条件已经具备所进行的推理摆脱了需要知道全部事实才能进行推理的需求，使得摆脱了需要知道全部事实才能进行推理的需求，使得在知识不完全的情况下也能进行推理在知识不完全的情况下也能进行推理2022-5-2052 2、确定性推理、不确定性推理、确定性推理、不确定性推理按推理时所用知识的确定性来划分，推理可分为确定按推理时所用知识的确定性来划分，推理可分为确定性推理、不确定性推理性推理、不确定性推理确定性推理：推理时所用的知识都是精确的，推出的确定性推理
6、：推理时所用的知识都是精确的，推出的结论也是确定的，其真值或者为真，或为假，没有第结论也是确定的，其真值或者为真，或为假，没有第三种情况出现三种情况出现不确定性推理：推理时所用的知识不都是精确的，推不确定性推理：推理时所用的知识不都是精确的，推出的结论也不完全是肯定的，真值位于真与假之间，出的结论也不完全是肯定的，真值位于真与假之间，命题的外延模糊不清命题的外延模糊不清2022-5-2063 3、单调推理、非单调推理、单调推理、非单调推理按推理过程中推出的结论是否单调地增加，或推出的按推理过程中推出的结论是否单调地增加，或推出的结论是否越来越接近目标，可分为单调推理和非单调结论是否越来越接近目
7、标，可分为单调推理和非单调推理推理单调推理：在推理过程中随着推理的向前及新知识的单调推理：在推理过程中随着推理的向前及新知识的加入，推出的结论是呈单调增加的趋势，并且越来越加入，推出的结论是呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不出现反复的情况接近最终目标，在推理过程中不出现反复的情况非单调推理：在推理过程中由于新知识的加入，不仅非单调推理：在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始回到前面的某一步，重新开始2022-5-207o 定义：定义：自然演绎推理是指从一组已知
8、的事实出发，直接运用自然演绎推理是指从一组已知的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程命题逻辑或谓词逻辑中的推理规则推出结论的过程。 o 推理规则：推理规则：n P规则：在推理的任何步骤上都可引入前提规则：在推理的任何步骤上都可引入前提n T规则：推理时，如果前面步骤中有一个或多个公式永规则：推理时，如果前面步骤中有一个或多个公式永真蕴涵公式真蕴涵公式S，则可把，则可把S引入推理过程中。引入推理过程中。n CP规则：如果能从规则：如果能从R和前提集合中推出和前提集合中推出S来，则可从前来，则可从前提集合推出提集合推出 来。来。n 反证法：反证法： ，当且仅当，当且仅当
9、。即：。即：Q为为P的逻辑结论，当且仅当的逻辑结论，当且仅当 是不可满足的。是不可满足的。SR QP FQPQP2022-5-208o 假言推理假言推理 表示：由表示：由 及及P为真，可推出为真，可推出Q为真为真 o 拒取式推理拒取式推理 表示：由表示：由 为真及为真及Q为假，可推出为假，可推出P为假为假 QQPP,QP PQQP,QP 2022-5-209o 避免产生两类错误：避免产生两类错误：n 肯定后件肯定后件(Q)的错误：希望通过肯定后件的错误：希望通过肯定后件Q推出前件推出前件P为真为真n 否定前件否定前件(P)的错误：希望通过否定前件的错误：希望通过否定前件P推出后件推出后件Q为假
10、为假2022-5-2010o 例： 设已知事实 （1）只要不怕困难的人，就会获得胜利。 （2）运动员都是不怕困难的人。 （3）王力是运动员。 求证：王力会获得胜利。 2022-5-2011o 自然演绎推理的优缺点自然演绎推理的优缺点n 优点：优点： 定理证明过程自然，容易理解，而且它拥有丰富的定理证明过程自然，容易理解，而且它拥有丰富的推理规则，推理过程灵活，便于在它的推理规则推理规则，推理过程灵活，便于在它的推理规则中嵌入领域启发式知识。中嵌入领域启发式知识。n 缺点：缺点： 容易产生组合爆炸，推理过程中得到的中间结论一容易产生组合爆炸，推理过程中得到的中间结论一般呈指数形式递增。般呈指数形
11、式递增。2022-5-2012o 1、合式公式的定义、合式公式的定义n合式公式合式公式适合于适合于一阶谓词逻辑一阶谓词逻辑n遵从以下递归方式定义的遵从以下递归方式定义的逻辑语句逻辑语句称为称为合式公式合式公式n单一谓词公式是合式公式；单一谓词公式是合式公式；n若若A A是合式公式，则是合式公式，则 A A也是合式公式；也是合式公式；n若若A A和和B B都是合式公式，则都是合式公式，则A AB B、 A AB B、 A AB B和和A AB B也都是合式公式；也都是合式公式；n若若A A是合式公式，是合式公式，x x是约束变量，则是约束变量，则( ( x x)A)A和和( ( x x)A)A也
12、也都是合式公式；都是合式公式；n只有按上述规则只有按上述规则- -求得的公式，才是合式公式。求得的公式，才是合式公式。n连词优先级别连词优先级别是是 ，、，、，但可通过，但可通过括号括号改改变优先级。变优先级。 一、合式公式一、合式公式2022-5-2013一、合式公式一、合式公式o 1、合式公式的定义、合式公式的定义n例例2 2、“所有人所有人(Person)(Person)都喜欢都喜欢(Like)(Like)一种游戏一种游戏(Game)”(Game)”o 谓词谓词公式公式n Person(xPerson(x) )n Like(x,yLike(x,y) )n Game(yGame(y) )o
13、 量词量词n ( ( x x)Person(x)Person(x) )表示表示所有所有人；人；n ( ( y)y)Game(yGame(y) )表示表示一种一种游戏；游戏；o 合式公式合式公式n ( ( x x)()( y)Person(x)y)Person(x)Game(y)Game(y)Like(x,yLike(x,y) ) 2022-5-2014一、合式公式一、合式公式o2、合式公式的解释、合式公式的解释n命题逻辑命题逻辑不存在变量不存在变量o给命题中包含的给命题中包含的各个原子公式指派真值各个原子公式指派真值（T或或F），称这种指派为），称这种指派为命题命题的一个的一个解释解释；o解释
14、确定后，可依据连接原子公式的解释确定后，可依据连接原子公式的连词连词的作用求出命题的真值的作用求出命题的真值（T或或F）。）。n谓词逻辑谓词逻辑涉及变量涉及变量o不可能直接给原子公式指派真值不可能直接给原子公式指派真值；o定义一个拟观察个体的可能定义一个拟观察个体的可能论域论域；o确定原子公式中确定原子公式中变量项变量项和和函数项函数项在论域中的在论域中的取值取值；o给原子公式给原子公式指派真值指派真值。o解释确定后，可依据连接原子公式的解释确定后，可依据连接原子公式的连词连词的作用求出合式公式的的作用求出合式公式的真值（真值（T或或F）。）。2022-5-2015一、合式公式一、合式公式o
15、2、合式公式的解释、合式公式的解释n例例3 3、合式公式、合式公式( ( x x)()( y)P(x)y)P(x)Q(f(x),yQ(f(x),y)一个解释的一个解释的建立。建立。n设定论域设定论域D=1,2; D=1,2; x xD,yD,yD Dn对于对于x x的每个取值的每个取值o 函数函数f(xf(x) )：f(1)=2,f(2)=2;f(1)=2,f(2)=2;n对于对于x x的每个取值的每个取值o 原子公式原子公式P(xP(x) )：P(1)=T,P(2)=TP(1)=T,P(2)=T；n对于对于f(xf(x) )和和y y的每个取值组合的每个取值组合( (只有只有2 2个：个：2
16、 2、1 1；2 2、2)2)o 原子公式原子公式Q(f(x),yQ(f(x),y) )：Q(2,1)=TQ(2,1)=T, Q(2,2)=F, Q(2,2)=F；n上述上述指派指派就确定了该合式公式的就确定了该合式公式的一个解释一个解释；n在在这个解释这个解释下，合式公式有下，合式公式有真值真值T T；2022-5-2016一、合式公式一、合式公式o 3、合式公式的永真性和可满足性、合式公式的永真性和可满足性n(1)(1)合式公式的永真性合式公式的永真性o 若若P P在某个论域在某个论域D D上的上的所有所有可能的解释都有真值可能的解释都有真值T T，则称，则称P P在在D D上是上是永真的
17、永真的；o 若若P P在在每个每个可能的非空论域可能的非空论域D D上均永真，则称上均永真，则称P P是是永真的永真的。n(2)(2)合式公式的可满足性合式公式的可满足性o 若若P P在某个论域在某个论域D D上的上的至少至少可以建立一个解释，使可以建立一个解释，使P P有真值有真值T T，则称则称P P在在D D上是上是可满足的可满足的；o 若若至少至少有一个非空论域有一个非空论域D D使使P P可满足，则称可满足，则称P P是是可满足的可满足的。n(3)(3)合式公式的永假性合式公式的永假性o 若若P P在某个论域在某个论域D D上的上的所有所有可能的解释都有真值可能的解释都有真值F F，
18、则称，则称P P在在D D上是上是永假的永假的；o 若若P P在在每个每个可能的非空论域可能的非空论域D D上均永假，则称上均永假，则称P P是是永假的永假的。2022-5-2017一、合式公式一、合式公式o 3、合式公式的永真性和可满足性、合式公式的永真性和可满足性n 论域个数较论域个数较少少，每个论域较，每个论域较小小o 易易判断合式公式的永真性和可满足性；判断合式公式的永真性和可满足性；n 论域个数较多，每个论域较大，论域个数较多，每个论域较大，解释个数有限解释个数有限o 永真性和可满足性总是永真性和可满足性总是可判断的可判断的；n 解释个数无限解释个数无限o 不能确保可判断不能确保可判
19、断；o 不能确保在有限的时间内判断不能确保在有限的时间内判断。2022-5-2018一、合式公式一、合式公式o 4、合式公式的性质、合式公式的性质n合式公式合式公式优点优点：o 具有强大的形式化表示功能；具有强大的形式化表示功能；n合式公式合式公式缺点缺点：o 包括了多种连词和量词以及它们的嵌套应用，包括了多种连词和量词以及它们的嵌套应用，表示形式过表示形式过于复杂于复杂；o 不利于演绎推理系统的设计和高效运作不利于演绎推理系统的设计和高效运作。n化简合式公式化简合式公式到某些约定的标准形式是很有意义。到某些约定的标准形式是很有意义。o 合取范式合取范式o 析取范式析取范式n合式公式的性质合式
20、公式的性质则为化简工作提供了依据。则为化简工作提供了依据。2022-5-2019一、合式公式一、合式公式o4、合式公式的性质、合式公式的性质n十种常用性质十种常用性质n(1)双重否定：双重否定：o ( P) Pn(2)蕴涵式转化：蕴涵式转化：oP Q P Qn(3)狄狄.摩根定律：摩根定律：o (P Q) P Qo (P Q) P Qn(4)分配律分配律oP (Q R) (P Q) (P R) oP (Q R) (P Q) (P R)n(5)交换律交换律oP Q Q PoP Q Q Pn(6)结合律结合律o(P Q) R P (Q R)o(P Q) R P (Q R)2022-5-2020一、
21、合式公式一、合式公式o4、合式公式的性质、合式公式的性质n十种常用性质十种常用性质n(7)逆否律逆否律o P Q Q Pn(8)量词否定量词否定o ( x) P(x) ( x) ( P(x) o ( x) P(x) ( x) ( P(x) n(9)量词分配量词分配o ( x) P(x) Q(x) ( x)P(x) ( x) Q(x)o ( x) P(x) Q(x) ( x)P(x) ( x) Q(x) n(10)约束变量的虚元化约束变量的虚元化o 约束变量名的变换不影响合式公式的真值约束变量名的变换不影响合式公式的真值o ( x) P(x) ( y) P(y) o ( x) P(x) ( y)
22、 P(y) 2022-5-2021一、合式公式一、合式公式o4、合式公式的性质、合式公式的性质n(9)量词分配量词分配o ( x) P(x) Q(x) ( x)P(x) ( y) Q(y)o ( x) P(x) Q(x) ( x)P(x) ( y) Q(y) n(10)约束变量的虚元化约束变量的虚元化o 约束变量名的变换不影响合式公式的真值约束变量名的变换不影响合式公式的真值o ( x) P(x) ( y) P(y) o ( x) P(x) ( y) P(y) 2022-5-2022 二、合式公式的标准化二、合式公式的标准化o 1、标准化需求、标准化需求n常见的基于谓词演算的推理：常见的基于谓
23、词演算的推理：归结反演归结反演、(正向正向/逆向逆向)演绎推理演绎推理o要求以要求以量词前束范式量词前束范式来表示合式公式来表示合式公式n量词前束范式量词前束范式形式如下：形式如下：o(Q1x1) (Q2x2)(Qkxk)M，其中，其中oM 母式，不包括任何量词；母式，不包括任何量词；oQixiQi可以是可以是量词量词符号符号 或或 ；xi是量词的是量词的约束变量约束变量(i=1,2,k)n归结反演（归结反演（4.5.5，2.3.3）要求要求M标准化为标准化为合取范式合取范式，定义，定义如下：如下：o M=W1W2 Wno Wi=Li1Li2 Lim(i=1,2,n)o Lij=Pij| Pi
24、j:文字（文字（Literal），是，是谓词公式谓词公式Pij或或其取反其取反2022-5-2023 二、合式公式的标准化二、合式公式的标准化o 1、标准化需求、标准化需求n常见的基于谓词演算的推理：常见的基于谓词演算的推理：归结反演归结反演、规则演绎规则演绎o要求以要求以量词前束范式量词前束范式来表示合式公式来表示合式公式n量词前束范式量词前束范式形式如下：形式如下：o(Q1x1) (Q2x2)(Qkxk)Mn归结反演归结反演要求要求M标准化为标准化为合取范式合取范式，定义如下：，定义如下：o M=W1W2 Wno Wi=Li1Li2 Lim(i=1,2,n)o Lij=Pij| Pij:文
25、字（文字（Literal），是原子谓词公式，是原子谓词公式Pij或其取反或其取反n析取范式析取范式定义：定义：o M=W1W2Wno Wi=Li1Li2Lim(i=1,2,n)o Lij=Pij| Pij:文字（文字（Literal），是原子谓词公式，是原子谓词公式Pij或其取反或其取反2022-5-2024o 定义定义 设设F为一谓词公式为一谓词公式，如果其中的所有量词均非否如果其中的所有量词均非否定地出现在公式的最前面定地出现在公式的最前面，而它们的辖域为整个公式而它们的辖域为整个公式，则称则称F为为前束范式前束范式(prenex normal form)。一般地一般地，前束范式可以写成前
26、束范式可以写成:其中其中 为为前缀前缀， 是一个由全称量词是一个由全称量词或存在量词组成的或存在量词组成的量词串量词串， 为为母式母式，它是一，它是一个不含任何量词的谓词公式。个不含任何量词的谓词公式。111()()(,.,)nnnQ xQ xM xx(1,2,., )iQ in1 1()()nnQ xQ x1( ,.,)nM xx前束标准型前束标准型n在一阶逻辑中在一阶逻辑中，为了简化定理证明程序需要引入所为了简化定理证明程序需要引入所谓的谓的“前束标准型前束标准型”。2022-5-2025 下面是一些前束范式的例子下面是一些前束范式的例子： 为了把一个公式化为前束范式，首先看一下包含为了把
27、一个公式化为前束范式，首先看一下包含一阶逻辑特有的等价式对，如下所示。一阶逻辑特有的等价式对，如下所示。 ()()( ( , )( )()()( , )( )()()()( ( , )( )xyP x yQ yxyP x yQ yxyzP x yQ z前束标准型前束标准型2022-5-2026(1) ()( )()( )Qx F xGQxF xG(2) ()( )()( )Qx F xGQxF xG1212(3)() ( )()( )()()( ( )( )Qx F xQ x H xQx Q z F xH z1212(4) () ( )()( )()()( ( )( )Q x F xQ x H
28、 xQ x Q z F xH z 在上述等价公式对中，在上述等价公式对中，F(x)和和 H(x)都表示含未都表示含未量化变量量化变量x的公式，的公式，G表示不含未量化变量表示不含未量化变量x的公的公式，式，Q1,Q2 或为或为 或为或为 。 对对(3)和和(4)，要求，要求z不出现在不出现在F(x) 中，并且符合约中，并且符合约束变量的换名原则。束变量的换名原则。 前束标准型前束标准型2022-5-2027 使用前面定义的等价式，总可以把一个公式化为使用前面定义的等价式，总可以把一个公式化为前束标准型。前束标准型。 变换过程如下：变换过程如下： (1) (1) 使用等价式中的连接词转化规律消去
29、公式中的使用等价式中的连接词转化规律消去公式中的连接词连接词, , 。 (2) (2) 反复使用双重否定律和德反复使用双重否定律和德摩根律将摩根律将“( (或或)”)”移到原子之前。移到原子之前。 (3) (3) 必要时重新命名量化的变量。必要时重新命名量化的变量。 (4) (4) 使用量词分配律和等价式，把所有量词都移到使用量词分配律和等价式，把所有量词都移到整个公式的最左边以得出一个范式。整个公式的最左边以得出一个范式。 前束标准型前束标准型2022-5-2028 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程n应用应用合式公式性质合式公式性质将
30、公式逐步转化的过程。将公式逐步转化的过程。n转化步骤没有严格的规定转化步骤没有严格的规定n较合理的化简过程，分为较合理的化简过程，分为8步：步：o 消去多余的量词（很少出现）；消去多余的量词（很少出现）；o 消去蕴涵符号；消去蕴涵符号；o 内移否定符号；内移否定符号；o 变量换名；变量换名；o 消去存在量词；消去存在量词；o 全称量词前束化；全称量词前束化；o 消去全称量词；消去全称量词；o 把把母式母式转化为转化为合取范式合取范式。2022-5-2029 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程o 消去多余的量词（很少出现）消去多余的量词（很
31、少出现）n若若一个量词的辖域内并未出现量词的约束变量一个量词的辖域内并未出现量词的约束变量，则该量词是多，则该量词是多余的，应该删除；余的，应该删除；n例，例，( x)P(y)，则，则( x)可以消去，得到可以消去，得到P(y)；n正常情况下，合式公式中不应出现多余的量词。正常情况下，合式公式中不应出现多余的量词。o 消去蕴涵符号消去蕴涵符号n蕴涵式转化蕴涵式转化：P Q P Q；n例，例， Q(x,y) P(y) Q(x,y) P(y)。2022-5-2030 二、合式公式的标准化二、合式公式的标准化o2、合取范式的标准化过程、合取范式的标准化过程o内移否定符号内移否定符号n使否定只出现在原
32、子谓词公式前，构成使否定只出现在原子谓词公式前，构成否定文字否定文字；n狄狄.摩根定律：摩根定律：o (P Q) P Qo (P Q) P Qn双重否定：双重否定： ( P) Pn量词否定：量词否定：o ( x) P(x) ( x) ( P(x) o ( x) P(x) ( x) ( P(x) n例，例， ( y) P(y)P(f(x,y)( y)P(y) P(f(x,y)o变量换名变量换名n“全称量词前束化全称量词前束化”后，同名变量的辖域无法区分，所以为避免差错，后，同名变量的辖域无法区分，所以为避免差错，必须换名；必须换名；n约束变量的虚元性约束变量的虚元性进行变换；进行变换；o( x)
33、 P(x) ( y) P(y) o( x) P(x) ( y) P(y)2022-5-2031o消去存在量词消去存在量词Skolem标准化过程111().()(,.,)nnnQ xQ x M xxStep1: 化成前束范式化成前束范式:Step2: 使用下述方法可以消去前缀中存在的所有量词：使用下述方法可以消去前缀中存在的所有量词： 令令 是是 中出现的存在量词中出现的存在量词 。rQ1 1().()n nQ xQ x(1)r n Case1: 若在若在 之前不出现全称量词，则选择一个与之前不出现全称量词，则选择一个与M中出现的所有常量都不相同的新常量中出现的所有常量都不相同的新常量c，用，用
34、c代替代替M中出中出现的所有现的所有xr，并且由前缀中删去，并且由前缀中删去(Qrxr) 。rQCase2: 若在若在 之前出现全称量词之前出现全称量词 ，则选择一，则选择一个与个与M中出现的任一函数符号都不相同的新中出现的任一函数符号都不相同的新m元函数符元函数符号号f，用，用 代替代替M中的所有中的所有xr ，并且由前缀中，并且由前缀中删去删去(Qrxr) 。rQ1,.,ssmQQ1(,.,)ssmf xx 按上述方法删去前缀中的所有存在量词之后得出的公式称为按上述方法删去前缀中的所有存在量词之后得出的公式称为合式公式的合式公式的Skolem标准型标准型。替代存在量化变量的常量。替代存在量
35、化变量的常量c(视为视为0元元函数函数)和函数和函数f称为称为Skolem函数。函数。2022-5-2032( , , , , ,)x y z u v wP x y z u v w 在公式中在公式中， 的前面没有全称量词，的前面没有全称量词， 的前面有全称量的前面有全称量词词 和和 , 在在 的前面有全称量词的前面有全称量词 ， 和和 。所。所以，在以，在 中，用常数中，用常数a代替代替x, 用二元函数用二元函数f(y,z)代代替替u, 用三元函数用三元函数g(y,z,v)代替代替w,去掉前缀中的所有存在量词之去掉前缀中的所有存在量词之后得出后得出Skolem标准型标准型：()y()w()y(
36、) z()v( , , , , ,)P x y z u v w(z)()u() x例题分析例例4.1 化公式化公式为为Skolem标准型。标准型。),(,),(,(vzygvzyfzyavPzy2022-5-2033 二、合式公式的标准化二、合式公式的标准化o2、合取范式的标准化过程、合取范式的标准化过程o消去存在量词消去存在量词n 在在 的辖域内的辖域内o ( z)( w) Q(x,z) P(z,w)o w依赖于依赖于z，由函数，由函数w=g(z)来定义这种依赖关系；来定义这种依赖关系；o 用用g(z)来取代约束变量来取代约束变量w，消去存在量词，消去存在量词 w；o ( z) Q(x,z)
37、 P(z,g(z)n 在在多个多个 的辖域内的辖域内o ( x)( y)( z)( w)P(x,y,z,w)o 用多元函数用多元函数g(x,y,z)来取代约束变量来取代约束变量w，消去存在量词，消去存在量词 w；o ( x)( y)( z)P(x,y,z,g(x,y,z)n 在在 的辖域外的辖域外o ( w)( z) Q(x,z) P(z,w)o 用用任意常量任意常量A取代约束变量取代约束变量w，消去存在量词，消去存在量词 wo ( z) Q(x,z) P(z,A)2022-5-2034 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程o 全称量词前束
38、化全称量词前束化n经过经过“变量换名变量换名”后，所有量词的约束变量均有不同的后，所有量词的约束变量均有不同的名字；名字；n只要简单地将只要简单地将 移到合式公式的最前面；移到合式公式的最前面；n约束变量的作用范围不会变化。约束变量的作用范围不会变化。o 消去全称量词消去全称量词n经过经过“消去存在量词消去存在量词”后，所有变量均受后，所有变量均受 的约束；的约束；n简单地删除简单地删除 ，只留下母式。，只留下母式。o 把母式转化为把母式转化为合取范式合取范式n分配律分配律： P (Q R) (P Q) (P R)2022-5-2035 二、合式公式的标准化二、合式公式的标准化o 2、合取范式
39、的标准化过程、合取范式的标准化过程n例例3、化简合式公式、化简合式公式 ( x)P(x)( y)P(y) P(f(x,y) ( y)( w)Q(x,y)P(y,w)2022-5-2036 二、合式公式的标准化二、合式公式的标准化o2、合取范式的标准化过程、合取范式的标准化过程n例例3、化简合式公式、化简合式公式 ( x)P(x)( y)P(y) P(f(x,y) ( y)( w)Q(x,y)P(y,w)消去蕴涵符号消去蕴涵符号 ( x) P(x)( y) P(y)P(f(x,y) ( y)( w) Q(x,y)P(y,w)2022-5-2037 二、合式公式的标准化二、合式公式的标准化o2、合
40、取范式的标准化过程、合取范式的标准化过程n例例3、化简合式公式、化简合式公式 ( x) P(x)( y) P(y)P(f(x,y) ( y)( w) Q(x,y)P(y,w)内移否定符号内移否定符号( x)P(x)( y)P(y) P(f(x,y)( y)( w) Q(x,y)P(y,w)2022-5-2038 二、合式公式的标准化二、合式公式的标准化o2、合取范式的标准化过程、合取范式的标准化过程n例例3、化简合式公式、化简合式公式( x)P(x)( y)P(y) P(f(x,y)( y)( w) Q(x,y)P(y,w)变量换名变量换名( x)P(x)( y)P(y) P(f(x,y)(
41、z)( w) Q(x,z)P(z,w)2022-5-2039 二、合式公式的标准化二、合式公式的标准化o2、合取范式的标准化过程、合取范式的标准化过程n例例3、化简合式公式、化简合式公式( x)P(x)( y)P(y) P(f(x,y)( z)( w) Q(x,z)P(z,w)消去存在量词消去存在量词P(A)( y)P(y) P(f(A,y)( z) Q(A,z)P(z,g(z)2022-5-2040 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程n例例3、化简合式公式、化简合式公式P(A)( y)P(y) P(f(A,y)( z) Q(A,z)P(
42、z,g(z)全称量词前束化全称量词前束化( y)( z)P(A)P(y) P(f(A,y) Q(A,z)P(z,g(z)2022-5-2041 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程n例例3、化简合式公式、化简合式公式( y)( z)P(A)P(y) P(f(A,y) Q(A,z)P(z,g(z)消去全称量词消去全称量词P(A)P(y) P(f(A,y) Q(A,z)P(z,g(z)2022-5-2042 二、合式公式的标准化二、合式公式的标准化o 2、合取范式的标准化过程、合取范式的标准化过程n例例3、化简合式公式、化简合式公式P(A)P(
43、y) P(f(A,y) Q(A,z)P(z,g(z)把母式转化为把母式转化为合取范式合取范式P(A)P(y) Q(A,z)P(z,g(z) P(f(A,y) Q(A,z)P(z,g(z)完成标准化过程！完成标准化过程！2022-5-2043o 自动定理证明一般表示形式为：自动定理证明一般表示形式为：o F1F2FnWnF1, F2, ,Fn都是合式公式，表示都是合式公式，表示公理公理或或事实事实；nW是合式公式，表示是合式公式，表示待证明的定理待证明的定理，称为，称为目标公式目标公式；o 证明的方法可分两大类：证明的方法可分两大类：n演绎法演绎法o 直接证明直接证明F1F2FnW为为永真永真；
44、n反证法反证法o 间接证明间接证明 (F1F2FnW)为为永假永假；o 证明证明F1F2Fn W的的永假永假n 即即F1, F2, ,Fn W是一个矛盾集。是一个矛盾集。2022-5-2044o 海伯伦（海伯伦（HerbrandHerbrand）n 提出的提出的H H域（海伯伦域）域（海伯伦域）和和海伯伦定理海伯伦定理；n 为为自动定理证明自动定理证明奠定了理论基础；奠定了理论基础；o 鲁宾逊（鲁宾逊（RobinsonRobinson）n 提出的提出的归结原理归结原理；n 使使自动自动定理证明定理证明成为可能。成为可能。2022-5-20451）H域和海伯伦定理（了解）域和海伯伦定理（了解）o
45、 1、子句和子句集、子句和子句集n 子句子句仅由仅由文字文字的的析取析取构成的合式公式构成的合式公式o Wi=Li1Li2 Lim称为称为子句子句；n 合取范式合取范式定义：定义：o M=W1W2 Wno Wi=Li1Li2 Lim(i=1,2,n)o Lij=Pij| Pij:文字（文字（Literal），是原子谓词公式，是原子谓词公式Pij或其取或其取反反n 合取范式合取范式可定义为可定义为子句子句的的合取合取 ；n 合取范式合取范式表示为表示为子句集子句集，子句间隐含，子句间隐含合取合取关系关系o 子句集子句集W1,W2,Wn2022-5-20461）H域和海伯伦定理域和海伯伦定理o 1
46、、子句和子句集、子句和子句集n 子句子句仅由仅由文字文字的的析取析取构成的合式公式构成的合式公式n 合取范式合取范式表示为表示为子句集子句集，子句间隐含具有合取关系，子句间隐含具有合取关系P(A)P(y) Q(A,z)P(z,g(z) P(f(A,y) Q(A,z)P(z,g(z)n 可进一步表示为子句集可进一步表示为子句集P(A),P(y) Q(A,z)P(z,g(z), P(f(A,y) Q(A,z)P(z,g(z)2022-5-20471）H域和海伯伦定理域和海伯伦定理o1、子句和子句集、子句和子句集n子句子句仅由仅由文字文字的的析取析取构成的合式公式构成的合式公式n合取范式表示为合取范
47、式表示为子句集子句集，子句间隐含具有，子句间隐含具有合取关系合取关系( y y) ( z z)P(A)P(y) Q(A,z)P(z,g(z) P(f(A,y) Q(A,z)P(z,g(z)量词分配：量词分配：( x) P(x) Q(x) ( x)P(x) ( x) Q(x)( y y) ( z z)P(A) ( y y) ( z z)P(y) Q(A,z)P(z,g(z) ( y y) ( z z) P(f(A,y) Q(A,z)P(z,g(z)2022-5-20481）H域和海伯伦定理域和海伯伦定理o 1、子句和子句集、子句和子句集n子句中的变量都是子句中的变量都是 的约束变量的约束变量(
48、y y) ( z z)P(A),( y y) ( z z)P(y) Q(A,z)P(z,g(z),( y y) ( z z) P(f(A,y) Q(A,z)P(z,g(z)n为了消除子句间不必要的交互作用，保持子句的独立性，需要为了消除子句间不必要的交互作用，保持子句的独立性，需要做做变量换名变量换名P(A),P(y1) Q(A,z1)P(z1,g(z1), P(f(A,y2) Q(A,z2)P(z2,g(z2)2022-5-2049例例4.2 将合式公式化为子句形。解：（1）消去蕴涵符号）消去蕴涵符号：这可以利用等价式：得到：x(P(x)yP(y) P(f(x,y)yQ(x,y) P(y)（
49、2）减少否定符号的辖域，把减少否定符号的辖域，把“ ”移到紧移到紧靠谓词的位置上：靠谓词的位置上：这可以利用下述等价式： ( ) ( )( ( , ) ( , )( )x P xy P yP f x yy Q x yP y PQP Q例题例题2022-5-2050得到： x(P(x)yP(y) P(f(x,y) yQ(x,y) P(y)（3）变量标准化）变量标准化：重新命名变元名，使不同量词约束的变元有不同的名字：xP(x)yP(y)P(f(x,y)wQ(x,w) P(w)（4）消去存在量词：）消去存在量词： xP(x)yP(y)P(f(x,y)Q(x,g(x) P(g(x) ()PP ()P
50、QPQ ()PQPQ ()() x PxP ()() x PxP2022-5-2051（5）化为前束形：）化为前束形： x yP(x) P(y) P(f(x,y) Q(x,g(x) P(g(x)（6 6）把母式化为合取范式：）把母式化为合取范式： x yP(x) P(y) P(f(x,y) P(x) Q(x,g(x) P(x) P(g(x)（7 7）消去全称量词和合取连接词：）消去全称量词和合取连接词： P(x) P(y)P(f(x,y) P(x) Q(x,g(x) P(x) P(g(x) 2022-5-2052（8）更改变量名，有时称为变量分离标准化。）更改变量名，有时称为变量分离标准化。于
