第三章一阶谓词逻辑

《第三章一阶谓词逻辑》由会员分享，可在线阅读，更多相关《第三章一阶谓词逻辑（134页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章 一阶谓词逻辑表示知识一阶谓词逻辑表示知识3.1一阶谓词逻辑形式一阶谓词逻辑形式3.2谓词公式、永真性、可满足性、谓词公式、永真性、可满足性、不可满足性不可满足性3.3谓词公式的等价性与永真蕴含谓词公式的等价性与永真蕴含3.4自然演绎推理自然演绎推理3.5归结演绎推理归结演绎推理3.6归结策略讨论归结策略讨论2021/6/413.1 3.1 一阶谓词逻辑形式一阶谓词逻辑形式前面离散数学课程已经讲述过谓词逻辑，在这里简要回顾如下：前面离散数学课程已经讲述过谓词逻辑，在这里简要回顾如下：1.1.命题逻辑命题逻辑定义 具有确定真值的陈述句，称为命题具有确定真值的陈述句，称为命题。例：例：

2、(1)2(1)2是素数。是素数。 (2)(2)雪是黑的。雪是黑的。 (3)(3)今年的十二月一号是个晴天。今年的十二月一号是个晴天。 (4)X+Y5(4)X+Y5 命题若是简单的陈述句，不能分解成更简单的句子，我们称命题若是简单的陈述句，不能分解成更简单的句子，我们称这样的命题为这样的命题为简单命题简单命题或或原子命题原子命题。可以用英文字母。可以用英文字母P P，Q Q，R R，或是带有下标的大写英文字母或是带有下标的大写英文字母P Pi i等表示简单命题，将命题用合等表示简单命题，将命题用合适的符号表示，称为适的符号表示，称为命题符号化命题符号化。2021/6/42命题逻辑的局限性：例如：

3、命题:焦作是一个漂亮的城市 P 郑州是一个漂亮的城市 Q 晋城是一个漂亮的城市 R 新乡是一个漂亮的城市 S 安阳是一个漂亮的城市 T要表达这样一个类别的知识时，命题逻辑表达起来，不方便。用谓词结构的形式最方便定义谓词：Beautiful City (x) ; x是一个漂亮的城市像这样表达知识的形式就是谓词表达知识的形式2021/6/432、一阶谓词逻辑、一阶谓词逻辑 谓词的一般形式是谓词的一般形式是: P(x1, x2, xn) 其中其中P是是谓词谓词，通常才用首字母，通常才用首字母大写开头的字母字符串大写开头的字母字符串表示。表示。 x1, x2, x3 是是个体个体,通常用通常用小写字母

4、小写字母来表示。来表示。 在谓词逻辑中，命题被细分为在谓词逻辑中，命题被细分为谓词谓词和和个体个体两个部分。两个部分。n元谓词元谓词： 含有含有n个个体符号的谓词个个体符号的谓词P(x1,x2, xn)，表示一个映射：，表示一个映射： P：Dn T，F 或是或是 (D1D2D3Dn) T，F2021/6/44谓词：谓词：用于刻画个体的用于刻画个体的性质、状态性质、状态或个体之间的或个体之间的关系关系，称，称为谓词。谓词一般也用为谓词。谓词一般也用P,Q,R等大写字母表示。等大写字母表示。 例例1：x是一个美丽的城市是一个美丽的城市 可以写成：可以写成： Beautiful City (x) 其

5、中：其中：Beautiful City 是谓词；是谓词；x是个体是个体 例例2： xy 可定义成：可定义成： Greater (x, y) 这里：这里：x、y是个体，是个体，Greater是谓词是谓词2021/6/45谓词的一般形式是谓词的一般形式是: P(x1, x2, xn) 其中其中P是是谓词谓词，通常首字母用，通常首字母用大写字母大写字母表示。表示。 x1, x2, x3 是是个体个体,通常用通常用小写字母小写字母来表示。来表示。 在谓词逻辑中，命题被细分为在谓词逻辑中，命题被细分为谓词谓词和和个体个体两个部分。两个部分。n元谓词元谓词： 含有含有n个个体符号的谓词个个体符号的谓词P(

6、x1,x2, xn)，表示一个映射：，表示一个映射： P：Dn T，F 或是或是 (D1D2D3Dn) T，F2021/6/46 谓词的语义是由使用者根据需要谓词的语义是由使用者根据需要人为定义人为定义的。的。 如：如：S（x） 可以定义成可以定义成x是船是船 也可定义成也可定义成x是学生是学生 谓词中包含的个体数目称为谓词中包含的个体数目称为谓词的元数谓词的元数. 如：如：Q(x)是一元谓词，是一元谓词， P(x, y)是二元谓词，是二元谓词， A(x1,x2,xn)是是n元谓词。元谓词。 若若Xi是个体常元、变元或函数，谓词称为一阶谓词；是个体常元、变元或函数，谓词称为一阶谓词；如果某个如

7、果某个Xi本身又是一个一阶谓词本身又是一个一阶谓词，则谓词称为二阶谓词，则谓词称为二阶谓词，依次类推。依次类推。 个体变元的取值范围称为个体域（或称论域），个体变元的取值范围称为个体域（或称论域），个体域个体域可以是有限的也可以是无限的。可以是有限的也可以是无限的。例例 I（x） x是整数，则个体域是所有整数，它是无限的。是整数，则个体域是所有整数，它是无限的。2021/6/47函数符号：函数符号：是从若干个研究对象到某个研究对象的映射的是从若干个研究对象到某个研究对象的映射的符号。符号。n元函数元函数 f(x1,x2,xn) 规定为一个映射：规定为一个映射： f: Dn D谓词与函数的区别谓

8、词与函数的区别：1.谓词的真值是真和假，而函数无真值可言，其值是个体域中的谓词的真值是真和假，而函数无真值可言，其值是个体域中的某个个体。某个个体。2.谓词描述的是谓词描述的是个体域中的个体之间的关系或性质。个体域中的个体之间的关系或性质。而函数实现的而函数实现的是一个个体的出现依赖于是一个个体的出现依赖于个体中中的其他个体，他是一个个体在个体中中的其他个体，他是一个个体在个体域中的个体域中的映射。映射。3.在谓词逻辑中，函数本身不能单独使用，它必须嵌入到谓词中。在谓词逻辑中，函数本身不能单独使用，它必须嵌入到谓词中。注意：有人讲命题逻辑是注意：有人讲命题逻辑是0元谓词逻辑元谓词逻辑2021/

9、6/48 3.2 3.2 谓词公式、永真性、可满足性、不可满足性谓词公式、永真性、可满足性、不可满足性3.2.13.2.1谓词公式谓词公式1 1、联接词：用于联接两谓词公式，组成一个复杂的复合命题：、联接词：用于联接两谓词公式，组成一个复杂的复合命题： ：“否定否定”联接按词，当命题联接按词，当命题P P为真时，则为真时，则P P为假，反之为为假，反之为 真真 ：“析取析取”联接词，它表示两个命题存在联接词，它表示两个命题存在“或或”者的关系。者的关系。 ：“合取合取”联接词，两个命题之间具有联接词，两个命题之间具有“与与”关系。关系。 “ “蕴含蕴含”、“条件命题条件命题”PQ”PQ表示表示

10、“如果如果P P，则，则Q”Q”。 P P为条件，为条件，Q Q为条件的后件为条件的后件 ：（：（ ）“等价等价”“”“双条件双条件”表示表示“P“P当且仅当当且仅当P”P”上述联结词构成谓词公式其定义如下：上述联结词构成谓词公式其定义如下：2021/6/49P P Q P Q P PQ PQ PQPQ PQ PQP QP QT TT TF F T T T T T T T TT T F F F F T T F F F F F FF F T T T T T T F T F F T FF F F T F T F F T T F F T T ；联接词的优先级：；联接词的优先级： ，2021/6/41

11、02 2、量词：、量词：用于刻划谓词与个体之间关系的词，在谓词逻用于刻划谓词与个体之间关系的词，在谓词逻辑中引入了两个量词，全称量词符号（辑中引入了两个量词，全称量词符号（ x x）及存在量）及存在量词符号（词符号（ x x）。）。 全称量词符号全称量词符号 + + 变元变元 = = 全称量词，如（全称量词，如（ x x）；）； 存在量词符号存在量词符号 + + 变元变元 = = 存在量词，如（存在量词，如（ x x）；）； ( ( x) x)：它表示对个体域中：它表示对个体域中所有个体所有个体x x ( ( x) x)： 表示在个体域中表示在个体域中存在某个个体存在某个个体x x2021/6

12、/411例：设谓词例：设谓词P(x)表示表示x是正数，是正数，F(x,y)表示表示x与与y是好朋友，则：是好朋友，则： ( x) P(x)：表示个体域中所有个体：表示个体域中所有个体x都是正数。都是正数。 ( x) ( y)F(x , y)：表示在个体域中：表示在个体域中对任何个体对任何个体x,都存在都存在个体个体y，x与与y是好朋友。是好朋友。 ( x) ( y)F(x , y)：表示在个体域中存在个体：表示在个体域中存在个体x，它与个，它与个体域中的任何个体体域中的任何个体y都是朋友。都是朋友。 ( y) ( x)F(x , y)：表示在个体域中存在个体：表示在个体域中存在个体x与个体与个

13、体y，x与与y是朋友。是朋友。 ( x) ( y) F(x , y)：表示对于个体域中的任何两个个体：表示对于个体域中的任何两个个体x和和y， x与与y都是朋友。都是朋友。2021/6/4123 3、量词辖域与约束变元、量词辖域与约束变元在一个谓词公式中，如果有量词出现，位于量词后面的单个在一个谓词公式中，如果有量词出现，位于量词后面的单个谓词或者用括弧扩起来的合式公式称为量词的辖域。在辖谓词或者用括弧扩起来的合式公式称为量词的辖域。在辖域内与量词同名的变元称谓约束变元，不受约束的变元称域内与量词同名的变元称谓约束变元，不受约束的变元称谓自由变元，例如谓自由变元，例如 （ x x）(P(P（x

14、 x）( y)R(x,y)y)R(x,y)其中（其中（ x x）的辖域是）的辖域是(P(P（x x）( y)R(x,y)y)R(x,y)，辖域内的，辖域内的x x是受（是受（ x x）的约束的变元；而）的约束的变元；而( ( y)y)的辖域是的辖域是R(x,y)R(x,y)，R(x,y)R(x,y)的的y y是受是受( ( y)y)约束的变元。在这个公式中没有自约束的变元。在这个公式中没有自由变元。由变元。2021/6/413在谓词公式中，变元的名字是无关紧要的，可以把一个变元在谓词公式中，变元的名字是无关紧要的，可以把一个变元的名字换成另一个变元的名字。但是，必须注意，当对量的名字换成另一个

15、变元的名字。但是，必须注意，当对量词辖域内的约束变元更名时，必须把同名的约束变元都统词辖域内的约束变元更名时，必须把同名的约束变元都统一改成相同的名字，且不能与辖域内的自由变元同名。同一改成相同的名字，且不能与辖域内的自由变元同名。同样，对辖域内的自由变元改名时，也不能改成与约束变元样，对辖域内的自由变元改名时，也不能改成与约束变元相同的名字。例如，对于公式（相同的名字。例如，对于公式（ x x）R(x,y)R(x,y)，可以改名，可以改名为为（ t t）R(t,u),R(t,u),这里将约束变元这里将约束变元x x改成了改成了t,t,把自由变元把自由变元y y改成改成了了u u。2021/6

16、/4144 4、谓词公式：、谓词公式：按下述规则得到谓词演算的合式公式：按下述规则得到谓词演算的合式公式：(1) (1) 单个谓词和单个谓词的否定，称为原子谓词公式，原单个谓词和单个谓词的否定，称为原子谓词公式，原子谓词公式是合式公式；子谓词公式是合式公式；(2) (2) 若若A A是合式公式，则是合式公式，则 A A也是合式公式；也是合式公式；(3) (3) 若若A A，B B都是合式公式，则都是合式公式，则ABAB，ABAB，ABAB，A BA B也都是合式公式；也都是合式公式；(4) (4) 若若A A是合式公式，是合式公式，x x是任一个体变元，则是任一个体变元，则 ( ( x)Ax)

17、A， ( ( x)Ax)A也都是合式公式。也都是合式公式。2021/6/4155 5 5 5、谓词公式的解释、谓词公式的解释、谓词公式的解释、谓词公式的解释在谓词逻辑中，对谓词公式中各个个体变元的一次真值在谓词逻辑中，对谓词公式中各个个体变元的一次真值在谓词逻辑中，对谓词公式中各个个体变元的一次真值在谓词逻辑中，对谓词公式中各个个体变元的一次真值指派称为谓词公式的一个解释。也即蜕化成命题逻辑，指派称为谓词公式的一个解释。也即蜕化成命题逻辑，指派称为谓词公式的一个解释。也即蜕化成命题逻辑，指派称为谓词公式的一个解释。也即蜕化成命题逻辑，一旦解释确定，根据各联接词的定义就可求出谓词公一旦解释确定，

18、根据各联接词的定义就可求出谓词公一旦解释确定，根据各联接词的定义就可求出谓词公一旦解释确定，根据各联接词的定义就可求出谓词公式中真值（式中真值（式中真值（式中真值（T T T T或或或或F F F F）。）。）。）。定义：谓词公式定义：谓词公式定义：谓词公式定义：谓词公式G G G G的论域为的论域为的论域为的论域为D D D D，根据，根据，根据，根据D D D D和和和和G G G G中的常量符号，中的常量符号，中的常量符号，中的常量符号，函数符号和谓词符号按下列规则作的一组指派成为函数符号和谓词符号按下列规则作的一组指派成为函数符号和谓词符号按下列规则作的一组指派成为函数符号和谓词符号按

19、下列规则作的一组指派成为G G G G的的的的一个解释一个解释一个解释一个解释I I I I（或赋值）（或赋值）（或赋值）（或赋值）解释解释解释解释I I I I：三个赋值规定：三个赋值规定：三个赋值规定：三个赋值规定：（1 1 1 1）对公式）对公式）对公式）对公式G G G G，为每个常量指派，为每个常量指派，为每个常量指派，为每个常量指派D D D D中的一个元素；中的一个元素；中的一个元素；中的一个元素； 2021/6/416解释解释解释解释I I I I：三个赋值规定：三个赋值规定：三个赋值规定：三个赋值规定：（2 2 2 2）对公式）对公式）对公式）对公式G G G G，为每个，为

20、每个，为每个，为每个n n n n元函数指派一个元函数指派一个元函数指派一个元函数指派一个Dn DDn DDn DDn D的映射，的映射，的映射，的映射，其中其中其中其中 Dn = Dn = Dn = Dn =（x1, x2, xnx1, x2, xnx1, x2, xnx1, x2, xn）/ x1, x2, xnD/ x1, x2, xnD/ x1, x2, xnD/ x1, x2, xnD（3 3 3 3）对公式）对公式）对公式）对公式G G G G，为每个，为每个，为每个，为每个n n n n元谓词指派一个元谓词指派一个元谓词指派一个元谓词指派一个Dn TDn TDn TDn T，FF

21、FF的的的的映射；映射；映射；映射；则称这些指派为公式则称这些指派为公式则称这些指派为公式则称这些指派为公式G G G G在在在在D D D D上的一个解释。上的一个解释。上的一个解释。上的一个解释。 ；公式只有经过指派才与现实联系起来，才有意义。；解释I称为公式G在论域D上的一个解释。；对应每个解释，公式G都有一个真值T，F。 2021/6/417；一阶谓词的公式解释数目：；一阶谓词的公式解释数目：；一阶谓词的公式解释数目：；一阶谓词的公式解释数目：一阶谓词的公式解释数通常是相当可观的，是一种排列一阶谓词的公式解释数通常是相当可观的，是一种排列一阶谓词的公式解释数通常是相当可观的，是一种排列

22、一阶谓词的公式解释数通常是相当可观的，是一种排列组合。组合。组合。组合。设个体域有设个体域有设个体域有设个体域有m m m m个元素，则：个元素，则：个元素，则：个元素，则：每个常量有每个常量有每个常量有每个常量有m m m m个取值，个取值，个取值，个取值，n n n n个常量有个常量有个常量有个常量有 m m m mn n n n 种取值的可能性，种取值的可能性，种取值的可能性，种取值的可能性，一个一个一个一个n n n n元函数一般有元函数一般有元函数一般有元函数一般有 种指派，种指派，种指派，种指派，一个一个一个一个n n n n元谓词有元谓词有元谓词有元谓词有 种指派。种指派。种指派

23、。种指派。 整个公式在给定域上的解释数目将达到该公式所包含的所有函数和谓词指派数目的连乘积。2021/6/418；由于存在多种组合情况，所以一个谓词公式的解释可能有很多由于存在多种组合情况，所以一个谓词公式的解释可能有很多由于存在多种组合情况，所以一个谓词公式的解释可能有很多由于存在多种组合情况，所以一个谓词公式的解释可能有很多个。对于每个解释，谓词公式都可求出一个真值（个。对于每个解释，谓词公式都可求出一个真值（个。对于每个解释，谓词公式都可求出一个真值（个。对于每个解释，谓词公式都可求出一个真值（T T T T或或或或F F F F）。）。）。）。( ( ( (需要注意：（需要注意：（需要

24、注意：（需要注意：（ x） P P P P（x x x x）的真值为）的真值为）的真值为）的真值为1 1 1 1当且仅当对论域当且仅当对论域当且仅当对论域当且仅当对论域D D D D的每一个的每一个的每一个的每一个元素元素元素元素x x x x，P P P P（x x x x）都取值为）都取值为）都取值为）都取值为1 1 1 1，（，（，（，（ x x x x） P P P P（x x x x）的真值为）的真值为）的真值为）的真值为0 0 0 0当且仅当且仅当且仅当且仅当对当对当对当对D D D D的每个元素的每个元素的每个元素的每个元素x x x x，P P P P（x x x x）都取值为

25、）都取值为）都取值为）都取值为0)0)0)0)例例例例 3.2.1 3.2.1 3.2.1 3.2.1：设谓词公式：设谓词公式：设谓词公式：设谓词公式A=yA=yA=yA=y（P P P P（y y y y）Q(y,a)Q(y,a)Q(y,a)Q(y,a)）,B=x(P(f(x) ,B=x(P(f(x) ,B=x(P(f(x) ,B=x(P(f(x) Q(x, f(a)(Q(x, f(a)(Q(x, f(a)(Q(x, f(a)(它们不含自由变元它们不含自由变元它们不含自由变元它们不含自由变元),),),),解释给定为解释给定为解释给定为解释给定为: D=2, 3 : D=2, 3 : D=2

26、, 3 : D=2, 3 a=2a=2a=2a=2，f f f f函数和谓词函数和谓词函数和谓词函数和谓词P P P P、Q Q Q Q的解释如下表所示。的解释如下表所示。的解释如下表所示。的解释如下表所示。f(2) f(3)3 20 1P(2) P(3) 1 1 1 1Q(2,2) Q(2,3) Q(3,2) Q(3,3)2021/6/419求求求求A A A A、B B B B的值。的值。的值。的值。则则则则 A=(P(2)Q(2,2)(P(3)Q(3,2) A=(P(2)Q(2,2)(P(3)Q(3,2) A=(P(2)Q(2,2)(P(3)Q(3,2) A=(P(2)Q(2,2)(P(

27、3)Q(3,2) =(01) (11) =(01) (11) =(01) (11) =(01) (11) =0 =0 =0 =0 B=(P(f(2)Q(2,f(2)(P(f(3)Q(3, f(2) B=(P(f(2)Q(2,f(2)(P(f(3)Q(3, f(2) B=(P(f(2)Q(2,f(2)(P(f(3)Q(3, f(2) B=(P(f(2)Q(2,f(2)(P(f(3)Q(3, f(2) =(P(3)Q(2,3)(P(2)Q(3,3) =(P(3)Q(2,3)(P(2)Q(3,3) =(P(3)Q(2,3)(P(2)Q(3,3) =(P(3)Q(2,3)(P(2)Q(3,3) =(1

28、1) (01) =(11) (01) =(11) (01) =(11) (01) =1 =1 =1 =12021/6/420 例例：设变元：设变元x和和y的个体域是的个体域是D=1，2，谓词，谓词P（x，y）表示表示x大于等于大于等于y，给出公式，给出公式A=( x )( y y)P(x,y)在在D上上的解释，并指出在每一种解释下公式的解释，并指出在每一种解释下公式A的真值。的真值。 解：解： 由于在公式由于在公式A中没有包括个体常量和函数，所以可由谓中没有包括个体常量和函数，所以可由谓词词P（x, y）的定义得出谓词的）的定义得出谓词的真值指派真值指派。设对谓词。设对谓词P（x,y）在个体域

29、在个体域D上的真值指派为：上的真值指派为： P(1,1)=T，P(1,2)=F，P(2,1)=T，P(2,2)=T 这就是公式这就是公式A在在D上的一个解释。在此解释下，因为上的一个解释。在此解释下，因为x=1时时有有y=1使使P(x,y)的真值为的真值为T，x=2时也有时也有y=1使使P(x,y)的真值为的真值为T，即，即x对于对于D中的所有取值，都存在中的所有取值，都存在y=1，使，使P(x,y)的真值为的真值为T，所以在此解释下公式，所以在此解释下公式A的真值为的真值为T。2021/6/421例：设个体域例：设个体域例：设个体域例：设个体域 D=1D=1，22，谓词公式，谓词公式，谓词公

30、式，谓词公式B=(B=( x)P(f(x),a)x)P(f(x),a)，已知，已知，已知，已知a=1a=1。若指派若指派若指派若指派 f(1)=1f(1)=1，f(2)=2f(2)=2指派指派指派指派 P(1,1)=TP(1,1)=T，P(2,1)=TP(2,1)=T则上述各个指派就确定了则上述各个指派就确定了则上述各个指派就确定了则上述各个指派就确定了谓词公式谓词公式谓词公式谓词公式B B的一个解释的一个解释的一个解释的一个解释即对即对即对即对 xx在在在在 DD上的任意取值，都使上的任意取值，都使上的任意取值，都使上的任意取值，都使BB为为为为T T2021/6/4223.2.2.谓词公式

31、的永真性、可满足性和永假性谓词公式的永真性、可满足性和永假性永真性永真性若谓词公式若谓词公式若谓词公式若谓词公式P P P P对非空个体域对非空个体域对非空个体域对非空个体域D D D D上的上的上的上的任一解释任一解释任一解释任一解释都有真值都有真值都有真值都有真值 T T T T，则称，则称，则称，则称P P P P在在在在D D D D上是上是上是上是永真的永真的永真的永真的即：若即：若即：若即：若P P P P在任何非空个体域上均永真，则在任何非空个体域上均永真，则在任何非空个体域上均永真，则在任何非空个体域上均永真，则称称称称P P P P永真永真永真永真可满足性可满足性对谓词公式对

32、谓词公式对谓词公式对谓词公式P P P P，若，若，若，若至少存在至少存在至少存在至少存在D D D D上的上的上的上的一个解释一个解释一个解释一个解释，使，使，使，使P P P P在在在在 此解释下真值为此解释下真值为此解释下真值为此解释下真值为T T T T，则称，则称，则称，则称P P P P在在在在D D D D上是上是上是上是可满足的可满足的可满足的可满足的永假性（不可满足性、不相容性）永假性（不可满足性、不相容性）若谓词公式若谓词公式若谓词公式若谓词公式P P P P对非空个体域对非空个体域对非空个体域对非空个体域D D D D上的任一解释都有真值上的任一解释都有真值上的任一解释都

33、有真值上的任一解释都有真值 F F F F，则称，则称，则称，则称P P P P在在在在D D D D上是永假的上是永假的上是永假的上是永假的即：即：即：即：P P P P在任何非空个体域上均永假，则称在任何非空个体域上均永假，则称在任何非空个体域上均永假，则称在任何非空个体域上均永假，则称P P P P永假永假永假永假当个体域个数当个体域个数当个体域个数当个体域个数少少少少，每个域自身又，每个域自身又，每个域自身又，每个域自身又小小小小时，时，时，时，易于判断易于判断易于判断易于判断或当解释的个数或当解释的个数或当解释的个数或当解释的个数有限有限有限有限，也总是可判定的，也总是可判定的，也总

34、是可判定的，也总是可判定的但若解释的个数但若解释的个数但若解释的个数但若解释的个数无限无限无限无限时，就时，就时，就时，就不能确保不能确保不能确保不能确保可以判定可以判定可以判定可以判定或者不能确保在或者不能确保在或者不能确保在或者不能确保在有限的时间有限的时间有限的时间有限的时间内判定内判定内判定内判定 2021/6/4233.3谓词公式的等价性与永真蕴含谓词公式的等价性与永真蕴含3.3.13.3.13.3.13.3.1等价性等价性等价性等价性含义含义含义含义 定义：设与是两个谓词公式，是它们共同的个定义：设与是两个谓词公式，是它们共同的个定义：设与是两个谓词公式，是它们共同的个定义：设与是

35、两个谓词公式，是它们共同的个体域，若对于上的任何解释，和都有相同的真值，体域，若对于上的任何解释，和都有相同的真值，体域，若对于上的任何解释，和都有相同的真值，体域，若对于上的任何解释，和都有相同的真值，则称与在个体域则称与在个体域则称与在个体域则称与在个体域D D D D上是等价的，如果上是等价的，如果上是等价的，如果上是等价的，如果D D D D是任意个体域，是任意个体域，是任意个体域，是任意个体域，则称则称则称则称P P P P和和和和Q Q Q Q是等价的，记作：是等价的，记作：是等价的，记作：是等价的，记作：P P P P Q Q Q Q以下公式是等价式，推理时常用到：以下公式是等价

36、式，推理时常用到：以下公式是等价式，推理时常用到：以下公式是等价式，推理时常用到：(1)(1)(1)(1)双重否定双重否定双重否定双重否定 ( ( ( ( P)P)P)P)P P P P(2)(2)(2)(2)交换律交换律交换律交换律 PQPQPQPQQP PQQP PQQP PQQP PQQP QP QP QP (3)(3)(3)(3)结合律结合律结合律结合律 (PQ)R(PQ)R(PQ)R(PQ)RP(QR)P(QR)P(QR)P(QR) (PQ)R(PQ)R(PQ)R(PQ)RP(QR) P(QR) P(QR) P(QR) (4)(4)(4)(4)分配律分配律分配律分配律P(QR)P(Q

37、R)P(QR)P(QR)(PQ)(PR)(PQ)(PR)(PQ)(PR)(PQ)(PR) P(QR) P(QR) P(QR) P(QR)(PQ)(PR)(PQ)(PR)(PQ)(PR)(PQ)(PR)(5)(5)(5)(5)狄狄狄狄 摩根定律摩根定律摩根定律摩根定律 (PQ)(PQ)(PQ)(PQ) PPPP Q Q Q Q (PQ)(PQ)(PQ)(PQ) PPPP 2021/6/424(6)(6)(6)(6)吸收律吸收律吸收律吸收律 P(PQ)P(PQ)P(PQ)P(PQ)P P P P P(PQ)P(PQ)P(PQ)P(PQ)P P P P(7)(7)(7)(7)补余律补余律补余律补余律

38、 PPPPP PT T T T PPPPP PF F F F(8)(8)(8)(8)联词化归律联词化归律联词化归律联词化归律 P P P P Q Q Q Q P P P PQ Q Q Q 蕴涵式转化蕴涵式转化蕴涵式转化蕴涵式转化 P Q P Q P Q P Q (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) P Q P Q P Q P Q (PQ)( (PQ)( (PQ)( (PQ)( PPPP Q) Q) Q) Q) (9)(9)(9)(9)量词否定量词否定量词否定量词否定 ( ( ( ( x)P(x)x)P(x)x)P(x)x)P(x)( ( ( ( x)(x)(x

39、)(x)( P(x)P(x)P(x)P(x) ( ( ( ( x)P(x)x)P(x)x)P(x)x)P(x)( ( ( ( x)(x)(x)(x)( P(x)P(x)P(x)P(x)(10)(10)(10)(10)量词分配量词分配量词分配量词分配 ( ( ( ( x x x x)P(x)Q(x)P(x)Q(x)P(x)Q(x)P(x)Q(x)( ( ( ( x x x x)P(x)()P(x)()P(x)()P(x)( x x x x)Q(x)Q(x)Q(x)Q(x) ( ( ( ( x x x x)P(x)Q(x)P(x)Q(x)P(x)Q(x)P(x)Q(x)( ( ( ( x x x

40、x)P(x)()P(x)()P(x)()P(x)( x x x x)Q(x)Q(x)Q(x)Q(x2021/6/4253.3.2谓词公式的永真蕴涵性谓词公式的永真蕴涵性永真蕴涵性含义永真蕴涵性含义如果如果如果如果 PQ PQ PQ PQ 永真，则称永真，则称永真，则称永真，则称 P P P P 永真蕴涵永真蕴涵永真蕴涵永真蕴涵 Q Q Q Q 且称且称且称且称 Q Q Q Q 为为为为 P P P P 的逻辑结论，称的逻辑结论，称的逻辑结论，称的逻辑结论，称 P P P P 为为为为 Q Q Q Q 的前提的前提的前提的前提记作记作记作记作 P P P P Q Q Q Q ，这就是知识的一种表

41、达形式。，这就是知识的一种表达形式。，这就是知识的一种表达形式。，这就是知识的一种表达形式。永真蕴涵式永真蕴涵式( (推理规则推理规则) )(1)(1)(1)(1)化简式化简式化简式化简式PQPQPQPQP PQP PQP PQP PQQ Q Q Q(2)(2)(2)(2)附加式附加式附加式附加式 P P P PPQ PQ PQ PQ Q Q Q QP P P PQQQQ(3)(3)(3)(3)析取三段论析取三段论析取三段论析取三段论 P P P P，P P P PQ Q Q QQ Q Q Q （“，”表示表示表示表示 ）(4)(4)(4)(4)假言推理假言推理假言推理假言推理P P P P，

42、PQPQPQPQQ Q Q Q(5)(5)(5)(5)拒取式拒取式拒取式拒取式 Q Q Q Q，PQPQPQPQ P P P P(6)(6)(6)(6)假言三段论假言三段论假言三段论假言三段论 PQPQPQPQ，QRQRQRQRPRPRPRPR(7)(7)(7)(7)二难推理二难推理二难推理二难推理 PQPQPQPQ，PRPRPRPR，QRQRQRQRR R R R 2021/6/426(8)(8)(8)(8)全称固化全称固化全称固化全称固化 ( ( ( ( x x x x)P()P()P()P(x x x x) ) ) )P(P(P(P(y y y y) ) ) ) 作用：作用：作用：作用：

43、y y y y是任一个体，是任一个体，是任一个体，是任一个体，消去全称量词消去全称量词消去全称量词消去全称量词(9)(9)(9)(9)存在固化存在固化存在固化存在固化 ( ( ( ( x)P(x)x)P(x)x)P(x)x)P(x)P(y)P(y)P(y)P(y) 作用：作用：作用：作用：y y y y是某一个体，使是某一个体，使是某一个体，使是某一个体，使P(y)P(y)P(y)P(y)为真，为真，为真，为真，消去存在量词消去存在量词消去存在量词消去存在量词其它规则其它规则1.规则规则：在推理的任何步骤上都可以：在推理的任何步骤上都可以引入前提引入前提2.规则规则：推理时，如果前面步骤中：推

44、理时，如果前面步骤中有一个或多个公式有一个或多个公式永真蕴含公式永真蕴含公式，则可以把引入推理过程中，则可以把引入推理过程中3.规则规则：如果能从和前提集合中推出来，则可：如果能从和前提集合中推出来，则可2021/6/427则可以从前提集合推出则可以从前提集合推出 S来来、反证法：、反证法：Q，当且仅当，当且仅当，PQF，即，即Q为的逻为的逻辑结论，当且仅当辑结论，当且仅当PQ是不可满足的。是不可满足的。定理：为定理：为1n的逻辑结论，当且仅当的逻辑结论，当且仅当（123n）是不可满足的，该公式将在以后的推理中用到，是归结是不可满足的，该公式将在以后的推理中用到，是归结反演的理论依据。反演的理

45、论依据。2021/6/4283.2.3 用谓词公式表示知识的步骤；用谓词公式表示知识的步骤；1.定义谓词及个体，确定每个谓词及个体的确切含义。定义谓词及个体，确定每个谓词及个体的确切含义。2.根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。3.根据所要表达的知识的语义，用适当的联结符号将各个谓词联结根据所要表达的知识的语义，用适当的联结符号将各个谓词联结起来，形成谓词公式。起来，形成谓词公式。例：例：3.2.2 人人爱劳动。人人爱劳动。所有整数不是偶数就是奇数。所有整数不是偶数就是奇数。自然数都是大于零的整数。自然数都是大于零

46、的整数。2021/6/4293.2.3 用谓词公式表示知识的步骤（续用谓词公式表示知识的步骤（续1）；解：解： 首先定义谓词如下首先定义谓词如下 MAN(x): x是人是人 LOVE(x, y): x爱爱y N(x):x是自然数是自然数 I(x):x是整数是整数 E(x):x是偶数是偶数 O(x):x是奇数是奇数 GZ(x):x大于零大于零2021/6/4303.2.3 用谓词公式表示知识的步骤用谓词公式表示知识的步骤（续（续2）；）；按照第按照第2、3步要求，得到步要求，得到 “人人爱劳动人人爱劳动”用谓词公式表示为用谓词公式表示为：( ( ( ( x)x)x)x)(MAN(x)LOVE(x

47、, labour) “所有整数不是偶数就是奇数所有整数不是偶数就是奇数”用谓词公式表示为用谓词公式表示为：( ( ( ( x)x)x)x)(I(x)E(x)O(x) “自然数都是大于零的整数自然数都是大于零的整数”用谓词公式表示为用谓词公式表示为：( ( ( ( x)x)x)x)(E(x)GZ(x)I(x)2021/6/4313.2.3 用谓词公式表示知识的步骤（续用谓词公式表示知识的步骤（续3）；）；例：例： 3.2.3梵塔梵塔(Hanoi)问题表示问题表示 已知已知3个柱子个柱子1、2、3和和3个盘子个盘子A、B、C（A比比B小，小，B比比C小）。小）。初始状态下，初始状态下，A、B、C依

48、次放在依次放在1号柱子上。搬动规则是每次可移号柱子上。搬动规则是每次可移动一个盘子，盘子上方是空时方可移动，任何时候都不允许大盘动一个盘子，盘子上方是空时方可移动，任何时候都不允许大盘在小盘之上。在小盘之上。解解 本问题涉及的常量是三个盘子：本问题涉及的常量是三个盘子：A、B、C；三个柱子：；三个柱子：1、2、3；儿；儿S表示状态。表示状态。 定义谓词和函数如下：定义谓词和函数如下：2021/6/4323.2.3 用谓词公式表示知识的步骤（续用谓词公式表示知识的步骤（续4）；）； Disk(x): x是盘子是盘子 PEE(p,w):盘子盘子w在柱子在柱子p上上 Smaller(x,y):x比比

49、y小小 Free(x,S):状态状态S下，下，x空顶空顶 Legal(x,y,S):状态状态S下下,x可向可向y移动移动 ON(x,y,S):状态状态S下下,x在在y上上 为了实现盘子的移动需要定义一个操作函数为了实现盘子的移动需要定义一个操作函数 S=move(x,y,S)表示状态表示状态S下，下，x移到移到y上得到的新状态上得到的新状态S经上述处理后，他们之间有如下关系经上述处理后，他们之间有如下关系2021/6/4333.2.3 用谓词公式表示知识的步骤用谓词公式表示知识的步骤（续（续5）；）；* （ x）（）（ y）（）（ z）(Smaller(x,y)Smaller(y,z)Smal

50、ler(x,z) 表示盘子大小的传递性表示盘子大小的传递性*（ x）（）（ S）(Free(x,S)（y）ON(x,y,S) 表示状态表示状态S下下,如果如果x是空顶，则必知是空顶，则必知S状态下无状态下无y在在x上上*（ x）（）（ y）（）（ S）(Legal(x,y,S)Free(x,S)Free(y,S)Disk(x)Smaller(x,y) 表示表示x可向可向y上移动的充分必要条件为上移动的充分必要条件为x和和y均空顶均空顶，且，且x比比y小，小，x是盘是盘2021/6/4343.2.3 用谓词公式表示知识的步骤用谓词公式表示知识的步骤（续（续6）；）；*（ x）（）（ y）（）（

51、S）（）（S）(S=move(x,y,S)ON(x,y,S)（ z1）（）（ z2）（）（z1=x）（z2=y）(ON(z1,z2,S)=(ON(z1,z2,S)（z）(ON(x,z,S)Free(z,S)表示如果在状态表示如果在状态S下，将下，将x移动到移动到y上得新状态上得新状态S，则没移动的盘，则没移动的盘子间的子间的ON关系没有变动，而关系没有变动，而x下面的盘子却是空顶了。下面的盘子却是空顶了。定义了谓词、函数后，就可以用一阶逻辑公式对问题进行表示。定义了谓词、函数后，就可以用一阶逻辑公式对问题进行表示。该问题的初始状态和目标状态用谓词公式表示如下。该问题的初始状态和目标状态用谓词公

52、式表示如下。2021/6/4353.2.3 用谓词公式表示知识的步骤（续用谓词公式表示知识的步骤（续7）；）；初始状态初始状态S0的谓词公式：的谓词公式：Disk(A)Disk(B)Disk(C)PEE(1,A)PEE(1,B)PEE(1,C)Smaller(A,B)Smaller(B,C)Free(A,S0)ON(A,B,S0)ON(B,C,S0)目标状态目标状态Sg的谓词公式：的谓词公式：Disk(A)Disk(B)Disk(C)PEE(3,A)PEE(3,B)PEE(3,C)Smaller(A,B)Smaller(B,C)Free(A,Sg)ON(A,B,Sg)ON(B,C,Sg)202

53、1/6/4363.2.3 用谓词公式表示知识的步骤（续用谓词公式表示知识的步骤（续8）；）；初始状态初始状态S0的谓词公式：的谓词公式：Disk(A)Disk(B)Disk(C)PEE(1,A)PEE(1,B)PEE(1,C)Smaller(A,B)Smaller(B,C)Free(A,S0)ON(A,B,S0)ON(B,C,S0)目标状态目标状态Sg的谓词公式：的谓词公式：Disk(A)Disk(B)Disk(C)PEE(3,A)PEE(3,B)PEE(3,C)Smaller(A,B)Smaller(B,C)Free(A,Sg)ON(A,B,Sg)ON(B,C,Sg)2021/6/4373.

54、4自然演绎推理自然演绎推理特点：从一组已知为真的事实出发，直接运用经特点：从一组已知为真的事实出发，直接运用经典逻辑中的推理规则，推出结论的过程。主要规典逻辑中的推理规则，推出结论的过程。主要规则是三段论推理，它是演绎推理的核心。则是三段论推理，它是演绎推理的核心。三段论推理包括假言推理，拒取式推理，假言三三段论推理包括假言推理，拒取式推理，假言三段论，二难推理，析取三段论。段论，二难推理，析取三段论。2021/6/4383.43.4自然演绎推理自然演绎推理自然演绎推理自然演绎推理（续）（续）（续）（续）1 1、 假言推理形式：假言推理形式： P，PQQ 由P，PQ为真，推出Q为真PPQP(P

55、Q)Q(P(PQ) QTTTTTTFFFTTFFFFTFTTT2021/6/4393.43.4自然演绎推理自然演绎推理自然演绎推理自然演绎推理（续（续（续（续1 1）2 2、 拒取式推理：拒取式推理：( (拒取式是假言推理的后件否定形式拒取式是假言推理的后件否定形式) ) PQ， Q P 由P Q为真，Q为假，推出P为假QPQ(PQ) P(PQ)Q P P P P TTTTTTFFFTTFFF FTFTTTQ2021/6/4403.43.4自然演绎推理自然演绎推理自然演绎推理自然演绎推理 （续（续（续（续2 2）3 3 3 3、假言三段论的形式是：、假言三段论的形式是：、假言三段论的形式是：、

56、假言三段论的形式是： PQ PQ PQ PQ，QR QR QR QR PR PR PR PR 由由由由PQPQPQPQ，Q RQ RQ RQ R为真，推出为真，推出为真，推出为真，推出PRPRPRPR为真为真为真为真4 4 4 4、二难推论：、二难推论：、二难推论：、二难推论：PQPQPQPQ，PRPRPRPR，QR QR QR QR R R R R 由由由由PQPQPQPQ，PRPRPRPR，QRQRQRQR为真，推出为真，推出为真，推出为真，推出R R R R为真为真为真为真5 5 5 5、析取三段论：、析取三段论：、析取三段论：、析取三段论：P P P P，PQ PQ PQ PQ Q Q

57、 Q Q 由由由由P P P P为假，为假，为假，为假，PQPQPQPQ为真，推出为真，推出为真，推出为真，推出Q Q Q Q为真为真为真为真2021/6/4413.43.4自然演绎推理自然演绎推理自然演绎推理自然演绎推理（续（续（续（续3 3）P(PQ) QP，PQ QPQ，QR PRPQ，PR，QR R假言推理假言推理拒取式推理拒取式推理假言三段论假言三段论二难推论二难推论析取论三段论析取论三段论(PQ) Q P P P P推理规则总结如下：推理规则总结如下：2021/6/442自然演绎推理自然演绎推理推理规则：通常是正向推理，也可以反向推理推理规则：通常是正向推理，也可以反向推理P P

58、P P规则规则规则规则（引入前提），（引入前提），（引入前提），（引入前提），T T T T规则规则规则规则（引入结论）（引入结论）（引入结论）（引入结论）假言推理假言推理假言推理假言推理 P P P P，PQ PQ PQ PQ Q Q Q Q 由由由由PQPQPQPQ为真及为真及为真及为真及P P P P为真，可推出为真，可推出为真，可推出为真，可推出Q Q Q Q为真为真为真为真拒取式推理拒取式推理拒取式推理拒取式推理 PQPQPQPQ，Q Q Q Q P P P P 由由由由PQPQPQPQ为真及为真及为真及为真及Q Q Q Q为假，可推出为假，可推出为假，可推出为假，可推出P P P

59、P为假为假为假为假已知事实已知事实经典逻辑推理规则经典逻辑推理规则结论结论定义定义2021/6/443自然演绎推理举例自然演绎推理举例举例举例已知如下事实已知如下事实已知如下事实已知如下事实 A A A A，B B B B，ACACACAC，BCDBCDBCDBCD，DQDQDQDQ求证求证求证求证 Q Q Q Q为真（为真（为真（为真（T T T T）证明证明证明证明 因为因为因为因为 A A A A，ACACACACC C C C 假言推理假言推理假言推理假言推理 B B B B，C C C CBC BC BC BC 引入合取词引入合取词引入合取词引入合取词 BCBCBCBC，BCDBCD

60、BCDBCDD D D D 假言推理假言推理假言推理假言推理 D D D D，DQDQDQDQQ Q Q Q 假言推理假言推理假言推理假言推理 所以所以所以所以 Q Q Q Q为为为为T T T T 2021/6/444自然演绎推理应用自然演绎推理应用 已知如下事实已知如下事实已知如下事实已知如下事实: : (1)(1)只要是需要编程序的课，只要是需要编程序的课，只要是需要编程序的课，只要是需要编程序的课，王程都喜欢王程都喜欢王程都喜欢王程都喜欢 (2)(2)所有的程序设计语言课所有的程序设计语言课所有的程序设计语言课所有的程序设计语言课 都是需要编程序的课都是需要编程序的课都是需要编程序的课

61、都是需要编程序的课 (3)C(3)C是一门程序设计语言课是一门程序设计语言课是一门程序设计语言课是一门程序设计语言课 求证求证求证求证 王程喜欢王程喜欢王程喜欢王程喜欢C C这门课这门课这门课这门课 证明证明证明证明 第一步第一步第一步第一步 定义谓词定义谓词定义谓词定义谓词 progprog(x):(x): x x是需要编程序的课是需要编程序的课是需要编程序的课是需要编程序的课 like(like(x,yx,y): x): x喜欢喜欢喜欢喜欢y y langlang(x):(x): x x是一门程序设计语言课是一门程序设计语言课是一门程序设计语言课是一门程序设计语言课第二步第二步第二步第二步

62、用谓词表示已知事实和问题用谓词表示已知事实和问题用谓词表示已知事实和问题用谓词表示已知事实和问题(1)prog(x)like(wang,x)(1)prog(x)like(wang,x)(2)(2)( x)(lang(x)prog(x)x)(lang(x)prog(x)(3)lang(C)(3)lang(C)第三步第三步第三步第三步 应用推理规则进行推理应用推理规则进行推理应用推理规则进行推理应用推理规则进行推理lang(y)prog(y) lang(y)prog(y) 全称固化全称固化全称固化全称固化lang(C)lang(C), ,lang(y)prog(y)lang(y)prog(y) p

63、rog(C)prog(C) 假言推理假言推理假言推理假言推理prog(C)prog(C), ,prog(x)like(wang,x)prog(x)like(wang,x) like(wang,C)like(wang,C) 假言推理假言推理假言推理假言推理因此因此因此因此 王程喜欢王程喜欢王程喜欢王程喜欢C C这门课这门课这门课这门课 2021/6/445自然演绎推理应用自然演绎推理应用 已知如下事实已知如下事实已知如下事实已知如下事实: :1 1、凡是容易的课程小王（、凡是容易的课程小王（、凡是容易的课程小王（、凡是容易的课程小王（WangWang）都喜欢）都喜欢）都喜欢）都喜欢2 2、C C

64、班的课程都是容易的班的课程都是容易的班的课程都是容易的班的课程都是容易的 3 3、dsds是是是是C C班的一门课程班的一门课程班的一门课程班的一门课程求证：小王喜欢求证：小王喜欢求证：小王喜欢求证：小王喜欢dsds这门课程这门课程这门课程这门课程 证明证明证明证明 第一步第一步第一步第一步 定义谓词定义谓词定义谓词定义谓词 EasyEasy（x x）：）：）：）： x x是容易的是容易的是容易的是容易的 Like Like（x x，y y）：）：）：）：x x喜欢喜欢喜欢喜欢y y C C（x x）：）：）：）：x x是是是是C C班的一门课程班的一门课程班的一门课程班的一门课程第二步第二步

65、第二步第二步用谓词表示已知事实和问题用谓词表示已知事实和问题用谓词表示已知事实和问题用谓词表示已知事实和问题(1)(1)Easy(x)Like(WangEasy(x)Like(Wang，x)x)；凡是容易的课程小王都喜欢凡是容易的课程小王都喜欢凡是容易的课程小王都喜欢凡是容易的课程小王都喜欢(2)(2)（ x x）（）（）（）（C(x)EasyC(x)Easy（x x）；）；）；）；C C班的课程是容易的班的课程是容易的班的课程是容易的班的课程是容易的(3)(3) C C（dsds）；）；）；）；ds ds 是是是是C C班的课程班的课程班的课程班的课程(4)(4) Like Like（Wan

66、gWang， ds ds）；小王喜欢）；小王喜欢）；小王喜欢）；小王喜欢dsds这门课程这门课程这门课程这门课程，待证明的问题，待证明的问题，待证明的问题，待证明的问题2021/6/446自然演绎推理应用自然演绎推理应用自然演绎推理应用自然演绎推理应用第三步第三步第三步第三步 应用推理规则进行推理应用推理规则进行推理应用推理规则进行推理应用推理规则进行推理（ x x）（）（）（）（C(x)EasyC(x)Easy（x x） C C（dsds）EasyEasy（dsds）C（ds），），C（ds）Easy（ds） Easy（ds） 假言推理假言推理假言推理假言推理Easy（ds），），Easy（

67、x） Like（wang，x）Like（wang，ds） （变量用（变量用ds代替），代替），假言推理假言推理假言推理假言推理因此因此因此因此 王程喜欢王程喜欢王程喜欢王程喜欢C C这门课这门课这门课这门课 全称固化2021/6/447自然演绎推理特点自然演绎推理特点一般来说，自然演绎推理由已知事实推出的结论一般来说，自然演绎推理由已知事实推出的结论一般来说，自然演绎推理由已知事实推出的结论一般来说，自然演绎推理由已知事实推出的结论可能有很多，只要其中包含了需要证明的结论，可能有很多，只要其中包含了需要证明的结论，可能有很多，只要其中包含了需要证明的结论，可能有很多，只要其中包含了需要证明的结

68、论，就认为问题得到了解决就认为问题得到了解决就认为问题得到了解决就认为问题得到了解决优点优点优点优点证明过程自然，易于理解证明过程自然，易于理解证明过程自然，易于理解证明过程自然，易于理解有丰富的推理规则可用有丰富的推理规则可用有丰富的推理规则可用有丰富的推理规则可用缺点缺点缺点缺点容易产生组合爆炸，推理过程中得到的容易产生组合爆炸，推理过程中得到的容易产生组合爆炸，推理过程中得到的容易产生组合爆炸，推理过程中得到的中间结论中间结论中间结论中间结论一般一般一般一般按指数规律递增按指数规律递增按指数规律递增按指数规律递增对于复杂问题的推理不利，甚至难以实现对于复杂问题的推理不利，甚至难以实现对于

69、复杂问题的推理不利，甚至难以实现对于复杂问题的推理不利，甚至难以实现2021/6/4483.5 3.5 归结演绎推理归结演绎推理 定理证明的实质是对前提定理证明的实质是对前提定理证明的实质是对前提定理证明的实质是对前提P P P P和结论和结论和结论和结论Q Q Q Q，证明，证明，证明，证明PQPQPQPQ的永真性，由的永真性，由的永真性，由的永真性，由PQPQPQPQ的谓词公式可知，如果前件的谓词公式可知，如果前件的谓词公式可知，如果前件的谓词公式可知，如果前件P P P P满足则一定得出满足则一定得出满足则一定得出满足则一定得出Q Q Q Q，只要证明，只要证明，只要证明，只要证明PQP

70、QPQPQ是永真的则可知，从是永真的则可知，从是永真的则可知，从是永真的则可知，从P P P P可推出可推出可推出可推出Q Q Q Q成立。要证明成立。要证明成立。要证明成立。要证明PQPQPQPQ处处永真，处处永真，处处永真，处处永真，有时比较困难。也就是当论域有限，解释有限时可以逐一证明其有时比较困难。也就是当论域有限，解释有限时可以逐一证明其有时比较困难。也就是当论域有限，解释有限时可以逐一证明其有时比较困难。也就是当论域有限，解释有限时可以逐一证明其正确性，当论域无限解释无限时，就无法证明其永真性。这时，正确性，当论域无限解释无限时，就无法证明其永真性。这时，正确性，当论域无限解释无限

71、时，就无法证明其永真性。这时，正确性，当论域无限解释无限时，就无法证明其永真性。这时，必须用反证法，要证明必须用反证法，要证明必须用反证法，要证明必须用反证法，要证明 PQ PQ PQ PQ永真，只要证明永真，只要证明永真，只要证明永真，只要证明 （PQPQPQPQ）是永假）是永假）是永假）是永假的也可以。的也可以。的也可以。的也可以。 （PQPQPQPQ）= = = =（PQPQPQPQ）=P=P=P=P Q Q Q Q即：证明即：证明即：证明即：证明PPPP Q Q Q Q永假性即可，在实际证明中，常将谓词公式变永假性即可，在实际证明中，常将谓词公式变永假性即可，在实际证明中，常将谓词公式

72、变永假性即可，在实际证明中，常将谓词公式变成子句的办法进行证明。成子句的办法进行证明。成子句的办法进行证明。成子句的办法进行证明。2021/6/4493.53.5. .1 1 子句子句 定理证明的实质是对前提定理证明的实质是对前提定理证明的实质是对前提定理证明的实质是对前提P P P P和结论和结论和结论和结论Q Q Q Q，证明，证明，证明，证明PQPQPQPQ的永真性，由的永真性，由的永真性，由的永真性，由PQPQPQPQ的谓词公式可知，如果前件的谓词公式可知，如果前件的谓词公式可知，如果前件的谓词公式可知，如果前件P P P P满足则一定得出满足则一定得出满足则一定得出满足则一定得出Q

73、Q Q Q，只要证明，只要证明，只要证明，只要证明PQPQPQPQ是永真的则可知，从是永真的则可知，从是永真的则可知，从是永真的则可知，从P P P P可推出可推出可推出可推出Q Q Q Q成立。要证明成立。要证明成立。要证明成立。要证明PQPQPQPQ处处永真，处处永真，处处永真，处处永真，有时比较困难。也就是当论域有限，解释有限时可以逐一证明其有时比较困难。也就是当论域有限，解释有限时可以逐一证明其有时比较困难。也就是当论域有限，解释有限时可以逐一证明其有时比较困难。也就是当论域有限，解释有限时可以逐一证明其正确性，当论域无限解释无限时，就无法证明其永真性。这时，正确性，当论域无限解释无限

74、时，就无法证明其永真性。这时，正确性，当论域无限解释无限时，就无法证明其永真性。这时，正确性，当论域无限解释无限时，就无法证明其永真性。这时，必须用反证法，要证明必须用反证法，要证明必须用反证法，要证明必须用反证法，要证明 PQ PQ PQ PQ永真，只要证明永真，只要证明永真，只要证明永真，只要证明 （PQPQPQPQ）是永假）是永假）是永假）是永假的也可以。的也可以。的也可以。的也可以。 （PQPQPQPQ）= = = =（PQPQPQPQ）=P=P=P=P Q Q Q Q即：证明即：证明即：证明即：证明PPPP Q Q Q Q永假性即可，在实际证明中，常将谓词公式变永假性即可，在实际证明

75、中，常将谓词公式变永假性即可，在实际证明中，常将谓词公式变永假性即可，在实际证明中，常将谓词公式变成子句的办法进行证明。成子句的办法进行证明。成子句的办法进行证明。成子句的办法进行证明。2021/6/4503.5.1 3.5.1 子句（续子句（续1 1） 文字：文字：文字：文字： 在谓词逻辑中把原子谓词公式及其否定式统称为文字。在谓词逻辑中把原子谓词公式及其否定式统称为文字。在谓词逻辑中把原子谓词公式及其否定式统称为文字。在谓词逻辑中把原子谓词公式及其否定式统称为文字。例如例如例如例如 R(x)R(x)R(x)R(x)，P(x,f(x) P(x,f(x) P(x,f(x) P(x,f(x) ，

76、Q(x,g(x)Q(x,g(x)Q(x,g(x)Q(x,g(x) 原子谓词公式：单个谓词公式或其否定式称为原子谓词公式。原子谓词公式：单个谓词公式或其否定式称为原子谓词公式。原子谓词公式：单个谓词公式或其否定式称为原子谓词公式。原子谓词公式：单个谓词公式或其否定式称为原子谓词公式。例如：例如：例如：例如：A A A A（x x x x），），），），A A A A（x x x x） 字句定理：任何文字的析取式称为子句。字句定理：任何文字的析取式称为子句。字句定理：任何文字的析取式称为子句。字句定理：任何文字的析取式称为子句。 例如例如例如例如 P(x,f(x) P(x,f(x) P(x,f(x

77、) P(x,f(x) Q(x,g(x)Q(x,g(x)Q(x,g(x)Q(x,g(x) 空子句空子句空子句空子句 不包含任何文字的子句不包含任何文字的子句不包含任何文字的子句不包含任何文字的子句 一般记为一般记为一般记为一般记为、nilnilnilnil 或或或或 NILNILNILNIL 空子句是空子句是空子句是空子句是永假永假永假永假的的的的子句集子句集子句集子句集 由子句或空子句所构成的集合由子句或空子句所构成的集合由子句或空子句所构成的集合由子句或空子句所构成的集合例如例如例如例如 P(x)P(x)P(x)P(x)( ( ( (P(x)P(x)P(x)P(x)Q(y)Q(y)Q(y)Q

78、(y) ) ) )( ( ( (P(y)P(y)P(y)P(y)Q(x)Q(x)Q(x)Q(x) ) ) )2021/6/451子句集子句集子句集子句集合取公（范）式下的各析取式的集合合取公（范）式下的各析取式的集合合取公（范）式下的各析取式的集合合取公（范）式下的各析取式的集合例如例如例如例如 P(x)P(x)P(x)P(x)( ( ( (P(x)P(x)P(x)P(x)Q(y)Q(y)Q(y)Q(y) ) ) )( ( ( (P(y)P(y)P(y)P(y)Q(x)Q(x)Q(x)Q(x) ) ) )的的的的子句子句子句子句集集集集是是是是 P(x)P(x)P(x)P(x)，P(x)P(x

79、)P(x)P(x)Q Q Q Q( ( ( (y y y y) ) ) )，P(y)Q(x) P(y)Q(x) P(y)Q(x) P(y)Q(x) 在谓词逻辑中，任何一个谓词公式都可以通过应用等在谓词逻辑中，任何一个谓词公式都可以通过应用等在谓词逻辑中，任何一个谓词公式都可以通过应用等在谓词逻辑中，任何一个谓词公式都可以通过应用等价关系及推理规则，化成相应的子句集，下述价关系及推理规则，化成相应的子句集，下述价关系及推理规则，化成相应的子句集，下述价关系及推理规则，化成相应的子句集，下述用一用一用一用一个例子，介绍个例子，介绍个例子，介绍个例子，介绍将谓词公式化成子句集的步骤：将谓词公式化成子

80、句集的步骤：将谓词公式化成子句集的步骤：将谓词公式化成子句集的步骤：( ( ( ( x)( (x)( (x)( (x)( ( y)P(x, y) y)P(x, y) y)P(x, y) y)P(x, y) ( ( ( ( y)(Q(x, y) R(x,y)y)(Q(x, y) R(x,y)y)(Q(x, y) R(x,y)y)(Q(x, y) R(x,y)3.5.1 3.5.1 子句（续子句（续2 2）2021/6/452谓词公式化成子句集步骤：谓词公式化成子句集步骤：谓词公式化成子句集步骤：谓词公式化成子句集步骤：(1)(1)(1)(1)消蕴涵符消蕴涵符消蕴涵符消蕴涵符 ，双条件，双条件，双

81、条件，双条件理论根据理论根据理论根据理论根据 PQPQPQPQPQPQPQPQ，P Q P Q P Q P Q (PQ) ( (PQ) ( (PQ) ( (PQ) (PPPPQ)Q)Q)Q)上式变成如下形式：上式变成如下形式：上式变成如下形式：上式变成如下形式：( ( ( ( x)(x)(x)(x)( ( ( ( y)P(x,y) y)P(x,y) y)P(x,y) y)P(x,y) ( ( ( ( y)( y)( y)( y)( Q(x,y) R(x,y)Q(x,y) R(x,y)Q(x,y) R(x,y)Q(x,y) R(x,y)(2)(2)(2)(2)利用等价关系将利用等价关系将利用等价

82、关系将利用等价关系将“”符号移到紧靠谓词的地方符号移到紧靠谓词的地方符号移到紧靠谓词的地方符号移到紧靠谓词的地方理论根据理论根据理论根据理论根据 (P(P(P(PQ)Q)Q)Q) P P P P Q Q Q Q，或，或，或，或 ( ( ( ( P P P P ）P P P P (P(P(P(PQ)Q)Q)Q) P P P P Q Q Q Q ( ( ( ( x)P(x)x)P(x)x)P(x)x)P(x)( ( ( ( x)(x)(x)(x)( P(x)P(x)P(x)P(x) ( ( ( ( x)P(x)x)P(x)x)P(x)x)P(x)( ( ( ( x)(x)(x)(x)( P(x)P

83、(x)P(x)P(x)上式变成下式：上式变成下式：上式变成下式：上式变成下式：( ( ( ( x)(x)(x)(x)( y)y)y)y) P(x, y)(P(x, y)(P(x, y)(P(x, y)( y)( Q(x, y) y)( Q(x, y) y)( Q(x, y) y)( Q(x, y) R(x,y) R(x,y) R(x,y) R(x,y)2021/6/453(3)(3)(3)(3)重重重重新命名变元名，使不同量词约束的变元有不同的名字新命名变元名，使不同量词约束的变元有不同的名字新命名变元名，使不同量词约束的变元有不同的名字新命名变元名，使不同量词约束的变元有不同的名字上式变成如

84、下形式：上式变成如下形式：上式变成如下形式：上式变成如下形式：( ( ( ( x)(x)(x)(x)( y)y)y)y) P(x, y)(P(x, y)(P(x, y)(P(x, y)( z z z z)( Q(x, )( Q(x, )( Q(x, )( Q(x, z z z z) ) ) ) R(x, R(x, R(x, R(x,z z z z)(4)(4)(4)(4)消去存在量词消去存在量词消去存在量词消去存在量词 这里存在两种情况：这里存在两种情况：这里存在两种情况：这里存在两种情况：1)1)1)1)、存在量词不出现在全称量词的辖域内，、存在量词不出现在全称量词的辖域内，、存在量词不出现

85、在全称量词的辖域内，、存在量词不出现在全称量词的辖域内，如：如：如：如：( ( ( ( x) P(x)x) P(x)x) P(x)x) P(x)，此时我们只要用一个新的个体常量替换受该存，此时我们只要用一个新的个体常量替换受该存，此时我们只要用一个新的个体常量替换受该存，此时我们只要用一个新的个体常量替换受该存在量词约束的变元，即可消去存在量词。（因为，若原公式为真，在量词约束的变元，即可消去存在量词。（因为，若原公式为真，在量词约束的变元，即可消去存在量词。（因为，若原公式为真，在量词约束的变元，即可消去存在量词。（因为，若原公式为真，则总能找到一个个体常量，替换后仍使公式为真）则总能找到一

86、个个体常量，替换后仍使公式为真）则总能找到一个个体常量，替换后仍使公式为真）则总能找到一个个体常量，替换后仍使公式为真）也可理解为；此时存在量词的变元的取值不依赖于任何其它变量。也可理解为；此时存在量词的变元的取值不依赖于任何其它变量。也可理解为；此时存在量词的变元的取值不依赖于任何其它变量。也可理解为；此时存在量词的变元的取值不依赖于任何其它变量。并且，这个新的个体常量没有在谓词公式中出现过。并且，这个新的个体常量没有在谓词公式中出现过。并且，这个新的个体常量没有在谓词公式中出现过。并且，这个新的个体常量没有在谓词公式中出现过。即：即：即：即：( ( ( ( x) P(x) P(a)x) P

87、(x) P(a)x) P(x) P(a)x) P(x) P(a)2021/6/454(4)(4)(4)(4)消去存在量词（消去存在量词（消去存在量词（消去存在量词（续）续）续）续） 2) 2) 2) 2)、如果存在量词出现在全称量词的辖域内，、如果存在量词出现在全称量词的辖域内，、如果存在量词出现在全称量词的辖域内，、如果存在量词出现在全称量词的辖域内， 如：如：如：如：( ( ( ( x) (x) (x) (x) ( y) P(x, y)y) P(x, y)y) P(x, y)y) P(x, y)，此时对每一个，此时对每一个，此时对每一个，此时对每一个x x x x都有一个都有一个都有一个都

88、有一个y y y y与之对与之对与之对与之对应，应，应，应，y y y y的取值依赖于的取值依赖于的取值依赖于的取值依赖于x x x x，我们记为，我们记为，我们记为，我们记为f(x)f(x)f(x)f(x)，称，称，称，称f(x)f(x)f(x)f(x)为为为为SkolemSkolemSkolemSkolem（斯格林）（斯格林）（斯格林）（斯格林）函数，用函数，用函数，用函数，用SkolemSkolemSkolemSkolem函数代替每一个存在量词量化的过程称为函数代替每一个存在量词量化的过程称为函数代替每一个存在量词量化的过程称为函数代替每一个存在量词量化的过程称为SkolemSkolem

89、SkolemSkolem化，所以有：化，所以有：化，所以有：化，所以有： ( ( ( ( x)(x)(x)(x)( y)P(x, y)Skolemy)P(x, y)Skolemy)P(x, y)Skolemy)P(x, y)Skolem化化化化后：后：后：后：( ( ( ( x)P(x, x)P(x, x)P(x, x)P(x, f(x)f(x)f(x)f(x) ) ) )；不同变元对应的；不同变元对应的；不同变元对应的；不同变元对应的SkolemSkolemSkolemSkolem函数的函数符号要不同。函数的函数符号要不同。函数的函数符号要不同。函数的函数符号要不同。；更一般形式：存在量词位

90、于多个全称量词的辖域内，如：；更一般形式：存在量词位于多个全称量词的辖域内，如：；更一般形式：存在量词位于多个全称量词的辖域内，如：；更一般形式：存在量词位于多个全称量词的辖域内，如：( ( ( ( x x x x1 1 1 1) () () () ( x x x x2 2 2 2) () () () ( x x x x3 3 3 3) () () () ( x x x xn n n n)()()()( y) P(xy) P(xy) P(xy) P(x1 1 1 1，x x x x2 2 2 2，x x x x3 3 3 3，x x x xn n n n，y)y)y)y)此时需要用此时需要用此

91、时需要用此时需要用SkolemSkolemSkolemSkolem函数函数函数函数 f(x f(x f(x f(x1 1 1 1，x x x x2 2 2 2，x x x x3 3 3 3，x x x xn n n n) ) ) )2021/6/455(4)(4)(4)(4)消去存在量词（消去存在量词（消去存在量词（消去存在量词（续）续）续）续） 替换受该存在量词约束的变元，才能消去存在量词。即：替换受该存在量词约束的变元，才能消去存在量词。即：替换受该存在量词约束的变元，才能消去存在量词。即：替换受该存在量词约束的变元，才能消去存在量词。即：( ( ( ( x x x x1 1 1 1)()

92、()()( x x x x2 2 2 2)()()()( x x x x3 3 3 3) () () () ( x x x xn n n n) P(x1) P(x1) P(x1) P(x1，x2x2x2x2，x3x3x3x3，x x x xn n n n，f(xf(xf(xf(x1 1 1 1，x x x x2 2 2 2，x x x x3 3 3 3，x x x xn n n n)对于上例而言，存在量词对于上例而言，存在量词对于上例而言，存在量词对于上例而言，存在量词( ( ( ( y)y)y)y)及及及及( ( ( ( z)z)z)z)都位于（都位于（都位于（都位于（ x x x x）的辖

93、域内，）的辖域内，）的辖域内，）的辖域内，所以都要用所以都要用所以都要用所以都要用SkolemSkolemSkolemSkolem函数来替换，设替换函数来替换，设替换函数来替换，设替换函数来替换，设替换y y y y与与与与z z z z的的的的SkolemSkolemSkolemSkolem函数分别为函数分别为函数分别为函数分别为f(x)f(x)f(x)f(x)和和和和g(x)g(x)g(x)g(x)，则上例变为：，则上例变为：，则上例变为：，则上例变为： ( ( ( ( x)( x)( x)( x)( P(x,f(x) ( Q(x, g(x) P(x,f(x) ( Q(x, g(x) P(

94、x,f(x) ( Q(x, g(x) P(x,f(x) ( Q(x, g(x) R(x, g(x)R(x, g(x)R(x, g(x)R(x, g(x)(5)(5)(5)(5)全称量词全部移到公式的左边全称量词全部移到公式的左边全称量词全部移到公式的左边全称量词全部移到公式的左边 对于在公式内部的全称量词都要把其移到公式的左边对于在公式内部的全称量词都要把其移到公式的左边对于在公式内部的全称量词都要把其移到公式的左边对于在公式内部的全称量词都要把其移到公式的左边 ( ( ( ( x)( x)( x)( x)( P(x,f(x) ( Q(x, g(x) P(x,f(x) ( Q(x, g(x)

95、P(x,f(x) ( Q(x, g(x) P(x,f(x) ( Q(x, g(x) R(x, g(x)R(x, g(x)R(x, g(x)R(x, g(x)2021/6/456(6)(6)(6)(6)用等价关系用等价关系用等价关系用等价关系P(QR)P(QR)P(QR)P(QR)(PQ)(PR) (PQ)(PR) (PQ)(PR) (PQ)(PR) 把公式化成斯格林标准形：把公式化成斯格林标准形：把公式化成斯格林标准形：把公式化成斯格林标准形：SkolemSkolemSkolemSkolem标准形：标准形：标准形：标准形： ( ( ( ( x x x x1 1 1 1)()()()( x x

96、x x2 2 2 2)()()()( x x x x3 3 3 3) () () () ( x x x xn n n n)M)M)M)M其中其中其中其中M M M M是子句的合取式，称为是子句的合取式，称为是子句的合取式，称为是子句的合取式，称为SkolemSkolemSkolemSkolem（斯格林）标准形的母式。（斯格林）标准形的母式。（斯格林）标准形的母式。（斯格林）标准形的母式。则上例变为：则上例变为：则上例变为：则上例变为：( ( ( ( x)(x)(x)(x)( P(x,f(x)Q(x, g(x) ( P(x,f(x)Q(x, g(x) ( P(x,f(x)Q(x, g(x) (

97、P(x,f(x)Q(x, g(x) ( P(x, f(x) P(x, f(x) P(x, f(x) P(x, f(x) R(x, R(x, R(x, R(x, g(x)g(x)g(x)g(x)(7)(7)(7)(7)消去全称量词消去全称量词消去全称量词消去全称量词, , , ,则上式变为：则上式变为：则上式变为：则上式变为：( P(x,f(x)Q(x, g(x) ( P(x,f(x)Q(x, g(x) ( P(x,f(x)Q(x, g(x) ( P(x,f(x)Q(x, g(x) ( P(x, f(x) P(x, f(x) P(x, f(x) P(x, f(x) R(x, R(x, R(x,

98、R(x, g(x)g(x)g(x)g(x)2021/6/457(8)(8)(8)(8)对变元更名，使不同子句中的变元不同名对变元更名，使不同子句中的变元不同名对变元更名，使不同子句中的变元不同名对变元更名，使不同子句中的变元不同名 上式改写成：上式改写成：上式改写成：上式改写成：( P(x,f(x)Q(x, g(x) P(x,f(x)Q(x, g(x) P(x,f(x)Q(x, g(x) P(x,f(x)Q(x, g(x) ( ( ( ( P( P( P( P(y y y y, f(, f(, f(, f(y y y y) R( R( R( R(y y y y, g(, g(, g(, g(y

99、 y y y)(9)(9)(9)(9)消去合取词得子句集消去合取词得子句集消去合取词得子句集消去合取词得子句集 消去合取词，上例变为子句集：消去合取词，上例变为子句集：消去合取词，上例变为子句集：消去合取词，上例变为子句集： P(xP(xP(xP(x，f(x)Q(xf(x)Q(xf(x)Q(xf(x)Q(x，g(x)g(x)g(x)g(x), , , , P(yP(yP(yP(y，f(y)f(y)f(y)f(y) R(yR(yR(yR(y，g(y)g(y)g(y)g(y)显然，在子句集中各子句之间是合取关系，如果谓词公式是不可显然，在子句集中各子句之间是合取关系，如果谓词公式是不可显然，在子句

100、集中各子句之间是合取关系，如果谓词公式是不可显然，在子句集中各子句之间是合取关系，如果谓词公式是不可满足的，则子句集也一定不可满足，反之亦然，两者在不可满足满足的，则子句集也一定不可满足，反之亦然，两者在不可满足满足的，则子句集也一定不可满足，反之亦然，两者在不可满足满足的，则子句集也一定不可满足，反之亦然，两者在不可满足性上是等价的。性上是等价的。性上是等价的。性上是等价的。2021/6/458定理：设有谓词公式定理：设有谓词公式定理：设有谓词公式定理：设有谓词公式P P P P，其标准形的子句集为，其标准形的子句集为，其标准形的子句集为，其标准形的子句集为S,S,S,S,则则则则P P P

101、 P不可满足的充不可满足的充不可满足的充不可满足的充要条件是：要条件是：要条件是：要条件是：S S S S是不可满足的。是不可满足的。是不可满足的。是不可满足的。 判断子句集的不可满足性，需对判断子句集的不可满足性，需对个体域上的一切解释个体域上的一切解释逐个地进逐个地进行判断，行判断，任何任何一个解释都是不可满足时，才能判定该子句是不可一个解释都是不可满足时，才能判定该子句是不可满足的，这在实际中难以实现。在实际中满足的，这在实际中难以实现。在实际中,如果如果选取个体域的某一选取个体域的某一有限有限部分部分，在，在此个体域此个体域中中处处不可满足处处不可满足，则认为子句集处处不可，则认为子句

102、集处处不可满足成立，就简单多了。满足成立，就简单多了。 海伯伦构造了一特殊的域，并证明海伯伦构造了一特殊的域，并证明只要对这个特殊的域上的一切只要对这个特殊的域上的一切解释进行判定解释进行判定，就可知子句集是否不可满足，这个特殊的域就是，就可知子句集是否不可满足，这个特殊的域就是海伯伦域海伯伦域。3.5.2 3.5.2 3.5.2 3.5.2 海伯伦理论海伯伦理论海伯伦理论海伯伦理论(Herbrand)(Herbrand)(Herbrand)(Herbrand)2021/6/459 按照下述方法构成的个体域称为按照下述方法构成的个体域称为海伯伦域海伯伦域，在此域，在此域中子句处处不可满足，则认

103、为子句集处处不可满足。中子句处处不可满足，则认为子句集处处不可满足。定理定理：设：设S为为子句集子句集，则按下述方法构造成的域，则按下述方法构造成的域H称称为海伯伦域，简记为为海伯伦域，简记为H域域（也有记为（也有记为H（S）：）： （1）令）令H0是是S中所有个体中所有个体常量常量的集合，若的集合，若S中不包含中不包含个体常量，则令个体常量，则令H0=a ，其中，其中a为任意指定的一个个体为任意指定的一个个体常量。常量。（2）Hi+1=Hi f(x1, x2, xn) |f是是S中出现的所有中出现的所有n元元 函数，函数， （3)2021/6/460例1：求子句集S的H域。 看起来，海伯伦全

104、域很庞大，实际上，它至多是一看起来，海伯伦全域很庞大，实际上，它至多是一个可列集。对于不出现函数的任何子句集个可列集。对于不出现函数的任何子句集S，H(S)仅仅有一个或有限个常量组成。从下述举例可以看出。有一个或有限个常量组成。从下述举例可以看出。2021/6/461例2：求子句集S=P(x), Q(f( x), R(g(y)的H域。解： H0=a H1=a, f(a)，g(a)H2=a, f(a), g(a), f(f(a)，f(g(a) ，g(f(a)，g(g(a) 例3：求子句集S=P(x),Q(y) R(y)的H域解： 由于无常量又无函数，指定a为个体常量，从 而得到： H0=H1=H

105、2=H=a2021/6/462 有前面求海伯伦全域可知，全域H实际上可以认为有相应子句集中所有常量和函词组成的各种可能的组合。 基表达式、基例与H基 定义 项、原子、文字、子句，以及他们各自的集合，统称为表达式。不出现变量表达式称为基表达式，不出现变量的项称为基项，基原子、基子句、基子句集等分别是不出现变量的原子、子句和子句集。2021/6/463 定义 如果用H域中的元素代换子句中的变元，则所得的基子句称为子句的一个基例，其中的谓词称为基原子。由基子句构成的集合称为基子句集。另一种讲法：子句集、子句，用域中的元素代替变元而得到的基子句称为子句的一个基例。定义 ：子句集中所有基原子构成的集合称

106、为原子集。2021/6/464海伯伦基（H基）（记B(S)）：由S的谓词符号和H域中的基项组成的全体基原子的集合。B(S)=P(t1,tn)|P是中出现的谓词符号， 例 设S= P(x)Q(a) , R(f(y),求S的海伯伦全域H(S),H基H(S)和第一个子句的基例。H(S)=a,f(a),f(f(a),f(f(f(a),.B(S)=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),P(f(f(a),Q(f(f(a),R(f(f(a),.2021/6/465例 设S= P(x)Q(a) , R(f(y),求S的海伯伦全域H(S),H基H(S)和第一个子句的基例。H(S

107、)=a,f(a),f(f(a),f(f(f(a),.B(S)=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),P(f(f(a),Q(f(f(a),R(f(f(a),.第一个子句 P(x)Q(a)的基例有 P(a)Q(a), P(f(a)Q(a), P(f(f(a)Q(a), .2021/6/466子句集的H解释： 子句集S在海伯伦全域上的一个解释称为H解释，是指对于子句集中出现的常量、函数和谓词符号按下述方法进行赋值：对每个常量指派常量本身；对每个n元函数指派一个从n到的映射；对每个n元谓词指派一个从n到真值，的映射； 注意：与一般论域D的解释不同，H解释对常量和函数的

108、指派是固定的，不随解释的变化而变化。H解释中可以随意指派的只有谓词的真值指派。主要是为了方便公式的判定。2021/6/467 定理定理: : 谓词公式谓词公式谓词公式谓词公式F F F F的子句集为的子句集为的子句集为的子句集为S S S S，则，则，则，则F F F F永假永假永假永假的充要条件是的充要条件是的充要条件是的充要条件是 S S S S不可满足不可满足不可满足不可满足定理：定理： 子句集子句集S S不可满足的充要条件是不可满足的充要条件是S S对对H H域域上的一切上的一切解释均为假。解释均为假。 定理：定理： 子句集子句集S S不可满足的充要条件不可满足的充要条件是存在一个是存

109、在一个有限有限的的不可满足的不可满足的基子句集基子句集S S。该定理称为海伯伦定理。该定理称为海伯伦定理。2021/6/468 对于字句集对于字句集对于字句集对于字句集S S S S在任一论域在任一论域在任一论域在任一论域 D D D D上的一个解释上的一个解释上的一个解释上的一个解释I I I I，都可以，都可以，都可以，都可以构造一个构造一个构造一个构造一个HHHH解释解释解释解释I*I*I*I*与之对应。与之对应。与之对应。与之对应。例：设谓词公式例：设谓词公式例：设谓词公式例：设谓词公式S=PS=PS=PS=P（x x x x）, Q(y,f, Q(y,f, Q(y,f, Q(y,f（

110、y,a)y,a)y,a)y,a)）, D=1, , D=1, , D=1, , D=1, 2 , S2 , S2 , S2 , S在在在在D D D D上的一个解释上的一个解释上的一个解释上的一个解释I I I I定义为：定义为：定义为：定义为： a f(1,1) f(1,2) f(2,1) f(2,2) P(1) P(2) Q(1,1) Q(1, 2) Q(2,1) Q(2, 2) 2 1 2 2 1 T F F T F T 现在构造现在构造现在构造现在构造与与与与I I I I对应的对应的对应的对应的H-H-H-H-解释解释解释解释I*I*I*I*首先给出首先给出S S的海伯伦全域的海伯伦

111、全域H H（S S）以及）以及S S的基原子集的基原子集B(S)B(S)2021/6/469 H0=aH0=aH0=aH0=a H1=a, f (a, a)H1=a, f (a, a)H1=a, f (a, a)H1=a, f (a, a) H2=a, f (a, a),f (f (a, a),a)H2=a, f (a, a),f (f (a, a),a)H2=a, f (a, a),f (f (a, a),a)H2=a, f (a, a),f (f (a, a),a) H3=a, f (a, a),f (f (a, a),a), f (f (f (a, a),a),a),)H3=a, f (

112、a, a),f (f (a, a),a), f (f (f (a, a),a),a),)H3=a, f (a, a),f (f (a, a),a), f (f (f (a, a),a),a),)H3=a, f (a, a),f (f (a, a),a), f (f (f (a, a),a),a),) H=a, f (a), f ( f (a),f( f (f (a)H=a, f (a), f ( f (a),f( f (f (a)H=a, f (a), f ( f (a),f( f (f (a)H=a, f (a), f ( f (a),f( f (f (a)，a),a),a),a), H(S

113、)=a ,f(a, a), f( f(a, a),a), f (f (f (a, H(S)=a ,f(a, a), f( f(a, a),a), f (f (f (a, H(S)=a ,f(a, a), f( f(a, a),a), f (f (f (a, H(S)=a ,f(a, a), f( f(a, a),a), f (f (f (a, a),a),a),)a),a),a),)a),a),a),)a),a),a),) B(S)=P(a), Q(a,a), P(f(a, a), Q(a, f(a, a), Q(f(a, B(S)=P(a), Q(a,a), P(f(a, a), Q(a,

114、f(a, a), Q(f(a, B(S)=P(a), Q(a,a), P(f(a, a), Q(a, f(a, a), Q(f(a, B(S)=P(a), Q(a,a), P(f(a, a), Q(a, f(a, a), Q(f(a, a), a), Q(f(a, a), f(a, a) ) a), a), Q(f(a, a), f(a, a) ) a), a), Q(f(a, a), f(a, a) ) a), a), Q(f(a, a), f(a, a) ) 2021/6/470 按解释按解释按解释按解释I I I I的常量和函数指派把的常量和函数指派把的常量和函数指派把的常量和函数指派把

115、B(S)B(S)B(S)B(S)中每个原子的所有基项代中每个原子的所有基项代中每个原子的所有基项代中每个原子的所有基项代换成换成换成换成D D D D的某各值，再按的某各值，再按的某各值，再按的某各值，再按I I I I的真值指派给出相应基原子的真值：的真值指派给出相应基原子的真值：的真值指派给出相应基原子的真值：的真值指派给出相应基原子的真值：若指派若指派若指派若指派a=2,a=2,a=2,a=2,f(a, a)= f(2,2)=1f(a, a)= f(2,2)=1f(a, a)= f(2,2)=1f(a, a)= f(2,2)=1f(f(a, a),f(f(a, a),f(f(a, a),

116、f(f(a, a),a a a a )= f(1, )= f(1, )= f(1, )= f(1,2 2 2 2)=)=)=)=2 2 2 2确定原子集中各元素的取值确定原子集中各元素的取值确定原子集中各元素的取值确定原子集中各元素的取值P(a)= P(2)=FP(a)= P(2)=FP(a)= P(2)=FP(a)= P(2)=FQ(a,a)= Q(2,2)=TQ(a,a)= Q(2,2)=TQ(a,a)= Q(2,2)=TQ(a,a)= Q(2,2)=TP(f(a, a)= P(f(2, 2)= P(1)=TP(f(a, a)= P(f(2, 2)= P(1)=TP(f(a, a)= P(

117、f(2, 2)= P(1)=TP(f(a, a)= P(f(2, 2)= P(1)=TQ(a, f(a, a)= Q(2, f(2, 2)= Q(2,1)=FQ(a, f(a, a)= Q(2, f(2, 2)= Q(2,1)=FQ(a, f(a, a)= Q(2, f(2, 2)= Q(2,1)=FQ(a, f(a, a)= Q(2, f(2, 2)= Q(2,1)=FQ(f(a, a), a)= Q(f(2, 2), 2)= Q(1,2)=TQ(f(a, a), a)= Q(f(2, 2), 2)= Q(1,2)=TQ(f(a, a), a)= Q(f(2, 2), 2)= Q(1,2)=

118、TQ(f(a, a), a)= Q(f(2, 2), 2)= Q(1,2)=T2021/6/471 Q(f(a, a),Q(f(a, a),Q(f(a, a),Q(f(a, a),f(a,f(a,f(a,f(a, a) a) a) a) ) ) )= Q(f(2, 2),= Q(f(2, 2),= Q(f(2, 2),= Q(f(2, 2),f(2,f(2,f(2,f(2, 2) 2) 2) 2) ) ) )= Q(1,= Q(1,= Q(1,= Q(1,1 1 1 1)=)=)=)=F F F F这就是与这就是与这就是与这就是与I I I I对应的对应的对应的对应的H-H-H-H-解释解释解

119、释解释I I I I* * * *，即，即，即，即，I I I I* * * *=P(a)P(a)，Q(a,a)Q(a,a)，P(f(a,a)P(f(a,a)，Q(a,f(a,a)Q(a,f(a,a)，Q(f(a,a),a),.Q(f(a,a),a),. 2021/6/472海伯伦理论海伯伦理论海伯伦定理海伯伦定理意义意义意义意义 从理论上给出了证明子句集不可满足从理论上给出了证明子句集不可满足从理论上给出了证明子句集不可满足从理论上给出了证明子句集不可满足性的可行性及方法性的可行性及方法性的可行性及方法性的可行性及方法局限局限局限局限 要在计算机上实现其证明过程却是很要在计算机上实现其证明过

120、程却是很要在计算机上实现其证明过程却是很要在计算机上实现其证明过程却是很困难的困难的困难的困难的鲁宾逊归结原理鲁宾逊归结原理1965196519651965年提出，使机器定理证明变为现实年提出，使机器定理证明变为现实年提出，使机器定理证明变为现实年提出，使机器定理证明变为现实2021/6/473 由谓词公式化成子句集的过程可知，在子句集中子句之间是合取关系合取关系，其中只要有一个子句不可满足，则这个子句集就不可满足。另外我们前面已指出过，空子句是不可满足的。因此，若一个子句集中包含空子句,则这个子句集一定是不可满足的。这就是鲁宾逊的归结原理的基本立足点。 鲁宾逊的归结原理基本思想方法是鲁宾逊的

121、归结原理基本思想方法是：检查子句集S中是否包含空子句，若包含，则S不可满足，若不包含，就要在子句集中选择合适的子句进行归结，一旦能归结出空子句，就说明子句集S是不可满足的。3.5.3鲁宾逊归结原理鲁宾逊归结原理2021/6/4741. 命题逻辑中的归结原理命题逻辑中的归结原理定义定义 设设C1与与C2是子句集中的任意两个子句，如果是子句集中的任意两个子句，如果C1中的中的文字文字L1与与C2中的文字中的文字L2互补，那么从互补，那么从C1和和C2中分别中分别消去消去L1和和L2，并将二个子句中，并将二个子句中余下的部分余下的部分析取析取，构成一个新，构成一个新子句子句C12，则称这一过程为，则

122、称这一过程为归结归结，称，称C12为为C1和和C2的归结的归结式，称式，称C1和和C2为为C12的亲本子句。的亲本子句。设子句设子句 C1=LC1C2=(L)C2 则归结式则归结式C12=C1C2 C1和和C2为为C12的的亲本子句亲本子句。互补文字互补文字的定义的定义 若若P是原子谓词公式，则称是原子谓词公式，则称P与与P是互补文字是互补文字2021/6/475P PQQQQP PQQNILNIL举例举例设设设设C C C C1 1 1 1=P=P=P=PQRQRQRQRC C C C2 2 2 2= = = =PSPSPSPS 则归结式则归结式则归结式则归结式C C C C12121212

123、为为为为 C C C C12121212=QR=QR=QR=QRSSSS设设设设C C C C1 1 1 1=P =P =P =P C C C C2 2 2 2= = = =P P P P 则归结式则归结式则归结式则归结式C C C C12121212为为为为 C C C C12121212=NIL=NIL=NIL=NIL归结过程的树形表示归结过程的树形表示例如例如例如例如 C C1 1 1 1= =P PQ CQ C2 2 2 2= =Q CQ C3 3 3 3=P=P求求求求C C1 1 1 1 C C2 2 2 2C C3 3 3 3的归结式的归结式的归结式的归结式C C12312312

124、3123？一一. 命题逻辑中的归结原理命题逻辑中的归结原理2021/6/476定理：定理：定理：定理： 归结式归结式归结式归结式C C C C12121212是其亲本子句是其亲本子句是其亲本子句是其亲本子句C C C C1 1 1 1和和和和C C C C2 2 2 2的逻辑结论的逻辑结论的逻辑结论的逻辑结论 （C C C C12121212的值是的值是的值是的值是C C C C1 1 1 1合取合取合取合取C C C C2 2 2 2的值）的值）的值）的值） 即：即：即：即：C C C C1 1 1 1 C C C C2 2 2 2 C C C C12 12 12 12 是一种推理规则是一种

125、推理规则是一种推理规则是一种推理规则 证明：设证明：设证明：设证明：设C C C C1 1 1 1= LC1, C= LC1, C= LC1, C= LC1, C2 2 2 2= = = = LC2 LC2 LC2 LC2 通过归结可得到：通过归结可得到：通过归结可得到：通过归结可得到：C C C C12121212=C1 C2=C1 C2=C1 C2=C1 C2由定义知：由定义知：由定义知：由定义知：C C C C1 1 1 1和和和和C C C C2 2 2 2是是是是C C C C12121212 的亲本子句的亲本子句的亲本子句的亲本子句 L C1 L C1 L C1 L C1 C1 L

126、 C1 L C1 L C1 L C1 L C1 L C1 L C1 L C1LC1LC1LC1L LC2LC2LC2LC2 L C2 L C2 L C2 L C2 C C C C1 1 1 1 C C C C2 2 2 2 =( =( =( =(C1L) (LC2) C1L) (LC2) C1L) (LC2) C1L) (LC2) 2021/6/477根据假言三假论（根据假言三假论（根据假言三假论（根据假言三假论（PQPQPQPQ，QR QR QR QR PRPRPRPR）得到：）得到：）得到：）得到： ( ( ( ( C1 L) (L C2) C1 L) (L C2) C1 L) (L C2

127、) C1 L) (L C2) C1C2C1C2C1C2C1C2 C1C2C1C2C1C2C1C2 C1 C2= CC1 C2= CC1 C2= CC1 C2= C12121212 C C C C1 1 1 1 C C C C2 2 2 2 C C C C12121212推论推论推论推论1 1 1 1：设：设：设：设C1C1C1C1与与与与C2C2C2C2是子句集是子句集是子句集是子句集S S S S中的两个子句，中的两个子句，中的两个子句，中的两个子句，C12C12C12C12是它们的是它们的是它们的是它们的归结式，若用归结式，若用归结式，若用归结式，若用C12C12C12C12代替代替代替代

128、替C1C1C1C1和和和和C2C2C2C2后得到新子句集后得到新子句集后得到新子句集后得到新子句集S1S1S1S1，则由，则由，则由，则由S1S1S1S1的不可满足性可推出原子句集的不可满足性可推出原子句集的不可满足性可推出原子句集的不可满足性可推出原子句集S S S S的不可满足性。的不可满足性。的不可满足性。的不可满足性。推论推论推论推论2 2 2 2：设：设：设：设C C C C1 1 1 1与与与与C C C C2 2 2 2是子句集是子句集是子句集是子句集S S S S中的两个子句，中的两个子句，中的两个子句，中的两个子句，C C C C12121212是它们的归是它们的归是它们的归

129、是它们的归结式，若把结式，若把结式，若把结式，若把C C C C12121212加入加入加入加入S S S S中，得到新子句集中，得到新子句集中，得到新子句集中，得到新子句集S2S2S2S2，则，则，则，则S S S S与与与与S2S2S2S2在不在不在不在不可满足的意义上是等价的。可满足的意义上是等价的。可满足的意义上是等价的。可满足的意义上是等价的。2021/6/478 从前面的推论中可以看出：要证明子句集从前面的推论中可以看出：要证明子句集从前面的推论中可以看出：要证明子句集从前面的推论中可以看出：要证明子句集S S S S的不可满的不可满的不可满的不可满足性，只要对其中可进行归结的子句

130、进行归结，并把归足性，只要对其中可进行归结的子句进行归结，并把归足性，只要对其中可进行归结的子句进行归结，并把归足性，只要对其中可进行归结的子句进行归结，并把归结式加入子句集结式加入子句集结式加入子句集结式加入子句集S S S S或用归结式替换它的亲本子句，而后，或用归结式替换它的亲本子句，而后，或用归结式替换它的亲本子句，而后，或用归结式替换它的亲本子句，而后，对新子句集证明不可满足性即可，在归结的过程中能得对新子句集证明不可满足性即可，在归结的过程中能得对新子句集证明不可满足性即可，在归结的过程中能得对新子句集证明不可满足性即可，在归结的过程中能得到空子句，立即可得到原子句集到空子句，立即

131、可得到原子句集到空子句，立即可得到原子句集到空子句，立即可得到原子句集S S S S是不可满足的结论。是不可满足的结论。是不可满足的结论。是不可满足的结论。2021/6/479 谓词逻辑与命题逻辑相比是含有变元，需选用谓词逻辑与命题逻辑相比是含有变元，需选用最一最一般合一般合一对变元进行代换，然后才能进行归结。对变元进行代换，然后才能进行归结。定义定义 设设C1与与C2是两个是两个没有相同变元没有相同变元的子句，的子句，L1和和L2分别分别是是C1和和C2中的文字，若中的文字，若是是L1和和L2的的最一般合一最一般合一，则，则称称C12=(C1 L1) (C2 L2)为为C1和和C2的二元归结

132、式，的二元归结式，L1和和L2称为归结式称为归结式的文字。的文字。 二二.谓词逻辑的归结原理谓词逻辑的归结原理2021/6/480例例1 1设设C1=P(a) Q(x) R(x)C2=P(y) Q(b)给出给出C1和和C2的归结式。的归结式。解解 若选若选L1=P(a), L2=P(y)，则，则 =a / y是是L1与与L2的的最一般合一最一般合一, 根据定义，可得：根据定义，可得：C12 =(C1 L1)(C2 L2)=(P(a), Q(x), R(x)P(a)(P(a), Q(b) P(a) =(Q(x), R(x)(Q(b) =Q(x), R(x), Q(B) =Q(x)R(x)Q(B)

133、 2021/6/481本例的一种归结树本例的一种归结树P(A) Q(x)R(x) P(y)Q(B)Q(x)R(x) Q(B)A/y2021/6/482若选若选L1=Q(x),L2=Q(b),=b/x,则可得：则可得：C12=(P(a),Q(b),R(b)Q(b) (P(y),Q(b)Q(b)=(P(a),R(b) (P(y)=P(a),R(b),P(y)=P(a) R(b) P(y)2021/6/483另一种归结树另一种归结树P(a) Q(x)R(x) P(y)Q(b)P(a)R(b) P(y)b/x2021/6/484解解由于由于C1与与C2有相同的变元，不符合定义的要有相同的变元，不符合定

134、义的要求。为了进行归结，需修改求。为了进行归结，需修改C2中变元的名字，令中变元的名字，令C2=P(B) R(y)。此时，对。此时，对C1和和C2有有L1=P(x),L2=P(B)L1与与L2的最一般合一的最一般合一=B/x,则则C12=(P(B),Q(A)-P(B) (P(B),R(y)- P(B)=Q(A),R(y)=Q(A) R(y)例例2 2设设C1=P(x) Q(A),C2=P(B) R(x)写出写出C1和和C2的归结式。的归结式。2021/6/485归结树 P(x) Q(A) P(B)R(y)Q(A)R(y)B/x2021/6/486定义定义：子句：子句C C1 1和和C C2 2

135、的归结式是下列二元归结式之一：的归结式是下列二元归结式之一：(1)C(1)C1 1与与C C2 2的二元归结式；的二元归结式；(2)C(2)C1 1与与C C2 2的因子的因子C C2 22 2二元归结式；二元归结式；(3)C(3)C1 1的因子的因子C C1 11 1与与C C2 2二元归结式；二元归结式；(4)C(4)C1 1的因子的因子C C1 11 1与与C C2 2的因子的因子C C2 22 2二元归结式。二元归结式。2021/6/487三：归结反演三：归结反演 归结原理给出了证明子句集不可满足性的方法，归结反演就是归结原理给出了证明子句集不可满足性的方法，归结反演就是用子句归结的方

136、法证明用子句归结的方法证明Q是前提是前提F的逻辑结论。的逻辑结论。定理：为定理：为1n的逻辑结论，当且仅当的逻辑结论，当且仅当（123n）是不可满足的，这就是归结反演的理论依据。是不可满足的，这就是归结反演的理论依据。定理：设有谓词公式定理：设有谓词公式F，其标准形的子句集为，其标准形的子句集为S，则，则F不可满足的不可满足的充要条件是：充要条件是：S是不可满足的；也就是说，在不可满足的意义上，是不可满足的；也就是说，在不可满足的意义上，公式：（公式：（123n）与其子句集是等价与其子句集是等价的。因此，我们可用归结原理进行定理证明，或在机器上实现定的。因此，我们可用归结原理进行定理证明，或在

137、机器上实现定理的自动证明。理的自动证明。2021/6/488归结反演步骤：归结反演步骤： 设F为已知前提的公式集，Q为目标公式（结论），用归结反演证明Q为结论的步骤是：否定Q，得到Q；把Q并入到公式集F中，得到F， Q；把公式集F， Q化为子句集S；对子句对子句对子句对子句集S S S S应用归结原理应用归结原理应用归结原理应用归结原理, , , ,寻找最一般合一，寻找最一般合一，寻找最一般合一，寻找最一般合一，对子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。 2021/6/489例：已知：F：( x)( ( y)( A(x,

138、y)B(y) ( y)(C(y)D(x, y)G：( x)C(x) ( x)( y)( A( x, y) B(y)求证：G是F的逻辑结论证明：把F和G化为子句集（1）A(x,y)B(y)C(f(x) （2）A(u,v)B(v)D(u,f(u)（3）C(z)（4）A(a, b)（5）B(b)2021/6/490归结如下：（6）A(x,y)B(y) 由（1）与（3）归结,z/f(x)（7）B(b) 由（4）与（6）归结,a/x,b/y（8）nil 由（5）与（7）归结所以，G是F的逻辑结论。用归结树表示如下： 2021/6/491对前对前例注释注释证明证明证明证明 第一步第一步第一步第一步, ,

139、, ,把把把把F F F F化为子句集化为子句集化为子句集化为子句集1.1.1.1.消消消消 : : : :( ( ( ( x)x)x)x)( ( ( ( y)A(x,y)B(y)y)A(x,y)B(y)y)A(x,y)B(y)y)A(x,y)B(y)( ( ( ( y)C(y)D(x,y)y)C(y)D(x,y)y)C(y)D(x,y)y)C(y)D(x,y)2.2.2.2.深入深入深入深入:(:(:(:( x)(x)(x)(x)( y)y)y)y)A(x,y)A(x,y)A(x,y)A(x,y)B(y)(B(y)(B(y)(B(y)( y y y y) ) ) ) C(C(C(C(y y

140、y y)D(x,)D(x,)D(x,)D(x,y y y y) ) ) ) 3.3.3.3.换名换名换名换名 :(:(:(:( x)x)x)x) ( ( ( ( y)y)y)y) A(x,y)A(x,y)A(x,y)A(x,y)B(y)B(y)B(y)B(y) ( z z z z)C()C()C()C(z z z z)D(x,)D(x,)D(x,)D(x,z z z z) 4.4.4.4.消消消消 : : : :( ( ( ( x)x)x)x) ( ( ( ( y)y)y)y) A(x,y)A(x,y)A(x,y)A(x,y)B(y)C(B(y)C(B(y)C(B(y)C(f(x)f(x)f(

141、x)f(x)D(x,)D(x,)D(x,)D(x,f(x)f(x)f(x)f(x)5.5.5.5.前束前束前束前束 ( ( ( ( x)(x)(x)(x)( y)y)y)y) A(x,y)A(x,y)A(x,y)A(x,y)B(y)B(y)B(y)B(y) C(f(x)C(f(x)C(f(x)C(f(x)D(x,f(x)D(x,f(x)D(x,f(x)D(x,f(x) 已知已知已知已知 F:(F:(F:(F:( x)x)x)x) ( ( ( ( y)y)y)y) A(x,y)B(y)A(x,y)B(y)A(x,y)B(y)A(x,y)B(y) ( y)y)y)y) C(y)D(x,y)C(y)

142、D(x,y)C(y)D(x,y)C(y)D(x,y) G: G: G: G: ( ( ( ( x)C(x)(x)C(x)(x)C(x)(x)C(x)( x)(x)(x)(x)( y)A(x,y)y)A(x,y)y)A(x,y)y)A(x,y)B(y)B(y)B(y)B(y)求证求证求证求证 G G G G是是是是F F F F的逻辑结论的逻辑结论的逻辑结论的逻辑结论2021/6/492对对对对例3.5.11注释（续注释（续注释（续注释（续1 1 1 1）6.6.6.6.变合取：变合取：变合取：变合取：( ( ( ( x)(x)(x)(x)( y)y)y)y) A(x,y)A(x,y)A(x,y

143、)A(x,y)B(y)B(y)B(y)B(y)C(f(x)C(f(x)C(f(x)C(f(x) A(x,y)A(x,y)A(x,y)A(x,y)B(y)B(y)B(y)B(y)D(x,f(x)D(x,f(x)D(x,f(x)D(x,f(x) 7.7.7.7.消消消消 ：A(x,y)A(x,y)A(x,y)A(x,y)B(y)C(f(x)B(y)C(f(x)B(y)C(f(x)B(y)C(f(x) A(x,y)A(x,y)A(x,y)A(x,y)B(y)D(x,f(x)B(y)D(x,f(x)B(y)D(x,f(x)B(y)D(x,f(x)8.8.8.8.换名：换名：换名：换名：A(x,y)A(

144、x,y)A(x,y)A(x,y)B(y)C(f(x)B(y)C(f(x)B(y)C(f(x)B(y)C(f(x) A(u,v)A(u,v)A(u,v)A(u,v)B(v)D(u,f(u)B(v)D(u,f(u)B(v)D(u,f(u)B(v)D(u,f(u)9:9:9:9:消消消消得到得到得到得到F F F F的子句的子句的子句的子句: : : : (1) (1) (1) (1) A(x,y)A(x,y)A(x,y)A(x,y)B(y)C(f(x)B(y)C(f(x)B(y)C(f(x)B(y)C(f(x)， (2)(2)(2)(2)A(u,v)A(u,v)A(u,v)A(u,v)B(v)D(

145、u,f(u)B(v)D(u,f(u)B(v)D(u,f(u)B(v)D(u,f(u)2021/6/493第二步第二步第二步第二步 把把把把G G G G化为子句集化为子句集化为子句集化为子句集 ( ( ( ( x)C(x)(x)C(x)(x)C(x)(x)C(x)( x)(x)(x)(x)( y)y)y)y) A(x,y)A(x,y)A(x,y)A(x,y)B(y)B(y)B(y)B(y) 1.1.1.1.消消消消 ( ( ( ( x)C(x)x)C(x)x)C(x)x)C(x) ( ( ( ( x)(x)(x)(x)( y)y)y)y) A(x,y)A(x,y)A(x,y)A(x,y)B(y

146、)B(y)B(y)B(y) 2.2.2.2.深靠深靠深靠深靠 ( ( ( ( x)C(x)(x)C(x)(x)C(x)(x)C(x)( x)(x)(x)(x)( y)y)y)y) A(x,y)A(x,y)A(x,y)A(x,y)B(y)B(y)B(y)B(y) ( ( ( ( x)C(x)x)C(x)x)C(x)x)C(x)( ( ( ( x)(x)(x)(x)( y)y)y)y)A(x,y)A(x,y)A(x,y)A(x,y)B(y)B(y)B(y)B(y) ( ( ( ( x)x)x)x)C(x)C(x)C(x)C(x)( ( ( ( x)(x)(x)(x)( y)y)y)y) A(x,y

147、)A(x,y)A(x,y)A(x,y)B(y)B(y)B(y)B(y) ( ( ( ( x x x x) ) ) )C(C(C(C(x x x x)()()()( x x x x)()()()( y)A(y)A(y)A(y)A(x x x x,y),y),y),y)B(y)B(y)B(y)B(y)3.3.3.3.换名换名换名换名 ( ( ( ( z z z z) ) ) )C(C(C(C(z z z z)()()()( x)(x)(x)(x)( y)(A(x,y)B(y)y)(A(x,y)B(y)y)(A(x,y)B(y)y)(A(x,y)B(y)4.4.4.4.消消消消 ( ( ( ( z)

148、z)z)z)C(z)(A(C(z)(A(C(z)(A(C(z)(A(a a a a, , , ,b b b b)B()B()B()B(b b b b) a,b) a,b) a,b) a,b是常量是常量是常量是常量5.5.5.5.前束前束前束前束 ( ( ( ( z)z)z)z) C(z)A(a,b)B(b)C(z)A(a,b)B(b)C(z)A(a,b)B(b)C(z)A(a,b)B(b) 6. 6. 6. 6.合取不变合取不变合取不变合取不变7.7.7.7.消消消消 C(z)A(a,b)B(b) 8.C(z)A(a,b)B(b) 8.C(z)A(a,b)B(b) 8.C(z)A(a,b)B(

149、b) 8.换名不变换名不变换名不变换名不变 9.9.9.9.消消消消 C(z) , A(a,b) , B(b) C(z) , A(a,b) , B(b) C(z) , A(a,b) , B(b) C(z) , A(a,b) , B(b) G G的子句的子句 (3) (4) (5)(3) (4) (5)对对对对例3.5.11注释（续注释（续注释（续注释（续2 2 2 2）2021/6/494第三步第三步第三步第三步 用归结树描述归结过程用归结树描述归结过程用归结树描述归结过程用归结树描述归结过程(1)(1)(1)(1)A(x,y)A(x,y)A(x,y)A(x,y)B(y)C(B(y)C(B(y

150、)C(B(y)C(f(x)f(x)f(x)f(x) ) ) )(3)(3)(3)(3)C(C(C(C(z z z z) ) ) ) A(A(A(A(x,yx,yx,yx,y)B(y)B(y)B(y)B(y) f(x)/zf(x)/zf(x)/zf(x)/z (4)A(4)A(4)A(4)A(a,ba,ba,ba,b) ) ) ) a/x,b/ya/x,b/ya/x,b/ya/x,b/y B(b)B(b)B(b)B(b)(5)B(b)(5)B(b)(5)B(b)(5)B(b)NILNILNILNIL第四步第四步第四步第四步 出现空出现空出现空出现空子句子句子句子句, , , ,证明证明证明证明G

151、 G G G是是是是F F F F的逻辑结论的逻辑结论的逻辑结论的逻辑结论2021/6/495归结反演应用归结反演应用证明证明证明证明 第一步第一步第一步第一步, , , ,把已知条件和要求证问题把已知条件和要求证问题把已知条件和要求证问题把已知条件和要求证问题用谓词表示用谓词表示用谓词表示用谓词表示出来出来出来出来 设设设设用用用用P(x)P(x)P(x)P(x)录取录取录取录取x x x x，则，则，则，则 已知已知已知已知 F:(1)PF:(1)PF:(1)PF:(1)P(a)P(b)P(c)(a)P(b)P(c)(a)P(b)P(c)(a)P(b)P(c) (2)(P (2)(P (2

152、)(P (2)(P(a)(a)(a)(a)P(b)P(c)P(b)P(c)P(b)P(c)P(b)P(c) (3)P(b)P(c) (3)P(b)P(c) (3)P(b)P(c) (3)P(b)P(c) 求证求证求证求证 G:P(c) G:P(c) G:P(c) G:P(c) 已知已知已知已知 某公司招聘工作人员某公司招聘工作人员某公司招聘工作人员某公司招聘工作人员,a,b,c,a,b,c,a,b,c,a,b,c三人应试三人应试三人应试三人应试, , , ,经面试经面试经面试经面试 后公司表示如下想法后公司表示如下想法后公司表示如下想法后公司表示如下想法: : : : (1) (1) (1)

153、(1)三人中至少录取一人三人中至少录取一人三人中至少录取一人三人中至少录取一人 (2)(2)(2)(2)如果录取如果录取如果录取如果录取a a a a而不录取而不录取而不录取而不录取b,b,b,b,则一定录取则一定录取则一定录取则一定录取c c c c (3) (3) (3) (3)如果录取如果录取如果录取如果录取b,b,b,b,则一定录取则一定录取则一定录取则一定录取c c c c 求证求证求证求证 公司一定录取公司一定录取公司一定录取公司一定录取c c c c2021/6/496归结反演应用归结反演应用 第二步第二步第二步第二步 把把把把F F F F和和和和G G G G化为子句集化为子

154、句集化为子句集化为子句集 F:(1)PF:(1)PF:(1)PF:(1)P(a)P(b)P(c)(a)P(b)P(c)(a)P(b)P(c)(a)P(b)P(c) (2) (2) (2) (2)P P P P(a)P(b)P(c)(a)P(b)P(c)(a)P(b)P(c)(a)P(b)P(c) (3) (3) (3) (3)P(b)P(c)P(b)P(c)P(b)P(c)P(b)P(c)G:G:G:G:P(c)P(c)P(c)P(c)第三步第三步第三步第三步 用归结树描述用归结树描述用归结树描述用归结树描述 归结过程归结过程归结过程归结过程(1)(1)(1)(1) P P P P(a)(a)

155、(a)(a)P(b)P(c)P(b)P(c)P(b)P(c)P(b)P(c)(2)(2)(2)(2)P P P P(a)(a)(a)(a)P(b)P(c)P(b)P(c)P(b)P(c)P(b)P(c) P(b)P(b)P(b)P(b)P(c)P(c)P(c)P(c)(3)(3)(3)(3)P(b)P(b)P(b)P(b)P(c)P(c)P(c)P(c)P(c)P(c)P(c)P(c)(4)(4)(4)(4)P(c)P(c)P(c)P(c)NILNILNILNIL第四步第四步第四步第四步 出现空出现空出现空出现空子句子句子句子句, , , ,证明公司证明公司证明公司证明公司一定录取一定录取一定

156、录取一定录取C C C C2021/6/497应用归结原理求解问题的答案步骤如下：应用归结原理求解问题的答案步骤如下：应用归结原理求解问题的答案步骤如下：应用归结原理求解问题的答案步骤如下： (1) (1) (1) (1) 把已知前提用谓词公式表示出来把已知前提用谓词公式表示出来把已知前提用谓词公式表示出来把已知前提用谓词公式表示出来, , , ,并且化为相应的子句集并且化为相应的子句集并且化为相应的子句集并且化为相应的子句集, , , ,设该子句集的名字为设该子句集的名字为设该子句集的名字为设该子句集的名字为S S S S (2) (2) (2) (2) 把待求解的问题也用谓词公式表示出来把

157、待求解的问题也用谓词公式表示出来把待求解的问题也用谓词公式表示出来把待求解的问题也用谓词公式表示出来, , , ,然后把然后把然后把然后把它否定并与它否定并与它否定并与它否定并与谓词谓词谓词谓词ANSWERANSWERANSWERANSWER构成析取式构成析取式构成析取式构成析取式,ANSWER,ANSWER,ANSWER,ANSWER是一个为了求解问题而专设的谓是一个为了求解问题而专设的谓是一个为了求解问题而专设的谓是一个为了求解问题而专设的谓词词词词, , , ,其变元必须与问题公式的变元完全一致其变元必须与问题公式的变元完全一致其变元必须与问题公式的变元完全一致其变元必须与问题公式的变元

158、完全一致 (3) (3) (3) (3) 把此析取式化为子句集把此析取式化为子句集把此析取式化为子句集把此析取式化为子句集, , , ,并且把该子句集并入到子句集并且把该子句集并入到子句集并且把该子句集并入到子句集并且把该子句集并入到子句集S S S S中中中中, , , ,得到得到得到得到子句集子句集子句集子句集S S S S (4) (4) (4) (4) 对对对对S S S S 应用归结原理进行应用归结原理进行应用归结原理进行应用归结原理进行归结归结归结归结 (5) (5) (5) (5) 若得到归结式若得到归结式若得到归结式若得到归结式ANSWER,ANSWER,ANSWER,ANSW

159、ER,则答案就在则答案就在则答案就在则答案就在ANSWERANSWERANSWERANSWER中中中中四四 应用归结原理求取问题的答案：应用归结原理求取问题的答案：2021/6/498基于归结反演的问题求解举例基于归结反演的问题求解举例例例 设A，B，C三人中有人从不说真话，也有人从不说假话，某人向这三人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答：“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者”。求谁是老实人，谁是说谎者？ 2021/6/499解解 首先，定义谓词首先，定义谓词T(x)表示表示x说真话。说真话。如果如果A说的是真话，则有说的是真话，则有T(A)

160、T(B) T(C)如果如果A说的是假话，则有说的是假话，则有 T(A) T(B)T(C) 对对B和和C说的话作相同的处理，可得：说的话作相同的处理，可得： T(B) T(A) T(C) T(B) T(A)T(C) T(C ) T(A) T(B) T(C ) T(A)T(B)2021/6/4100把上面这些公式化成子句集把上面这些公式化成子句集S：(1)T(A) T(B)(2)T(A) T(C)(3)T(A) T(B) T(C)(4)T(B) T(C)(5)T(C) T(A) T(B)(6)T(C) T(A)(7)T(C) T(B)T(A) T(B) T(C) T(A) T(B)T(C) T(B

161、) T(A) T(C) T(B) T(A)T(C)T(C ) T(A) T(B) T(C ) T(A)T(B)2021/6/4101下面首先求谁是老实人。把目标公式( x)T(x)的否定式( x)T(x)与ANSWER(x)组成的析取式化为子句并入S得到S1, 即S1比S多如下一个子句：(8) T(x)ANSWER(x) 应用归结原理进行归结 2021/6/4102求谁是老实人的归结树求谁是老实人的归结树 （1 1） T(A) T(B)（7）T(C) T(B) T(A)T(C)（6）T(C)T(A)T(C)（8 8） T(x)ANSWER(x)ANSWER(C)C/x 2021/6/4103由

162、ANSWER(C)可得 C是老实人，即C从不说假话。除此之外，无论如何对S1进行归结，都推不出ANSWER（B）和ANSWER（A）。下面来证明A和B不是老实人（归结反演）设A不是老实人，则有 T(A)，把它的否定式T(A)并入到S中，得到子句集S2应用归结原理对S2进行归结2021/6/4104证明A不是老实人的归结树 （1 1）T(A) T(B)（7）T(C) T(B)T(A)T(C)（2 2）T(A) T(C)T(A)（8）T(A)NIL2021/6/4105（1 1）T(A) T(B)（6）T(C) T(A)T(B)T(C)（4 4）T(B) T(C)T(B)（8）T(B)NIL证明B

163、不是老实人的归结树 2021/6/4106例：某村农民张某被害，有四个嫌疑犯A,B,C,D。公安局派出五个侦察员，他们的侦察结果分别是：A，B之中至少有一人作案，B，C中至少有一人作案，C，D中至少有一人作案，A，C中至少有一人与此案无关，B，D中至少有一人与此案无关，所有侦察结果都是可靠的，求出谁是罪犯？2021/6/4107解：设谓词C(y)表示y为罪犯对于第一个侦察员：C(A)C(B) (1)对于第二个侦察员: C(B)C(C) (2)对于第三个侦察员: C(C)C(D) (3)对于第四个侦察员: C(A) C(C) (4)对于第五个侦察员: C(B) C(D) (5)结论： C(U)

164、ANSWER(U) (6)2021/6/4108(1)与（4）归结：C(B) C(C) (7)(2)与（7）归结：C(B) (8)(6)与（8）归结：ANSWER(B). B是罪犯(3)与（5）归结：C(C) C(B) (7)(2)与（7）归结：C(C) (8)(6)与（8）归结：ANSWER(C).C是罪犯 (1)(1)C(A)C(B) (2)(2)C(B)C(C) (3)(3)C(C)C(D) (4)(4)C(A) C(C) (5)(5)C(B) C(D) (6)(6)C(U) ANSWER(U) 2021/6/4109归结反演引起的反思归结反演引起的反思 对子句集进行归结反演时，由于事先

165、不知道哪两个子句可以进行归结，更不知道通过对哪些子句对的归结可以尽快地得到空子句，因而必须对子句集中的所有子句逐对地进行比较，对任何一个可归结的子句对都进行归结。也就是说，在子句集中采用了类似广度优先搜索方法来搜索亲本子句，因此归结的效率很低。 2021/6/41103.6归结策略讨论归结策略讨论要解决的问题要解决的问题要解决的问题要解决的问题如何能尽快找到归结子句对如何能尽快找到归结子句对如何能尽快找到归结子句对如何能尽快找到归结子句对控制策略的目的控制策略的目的控制策略的目的控制策略的目的归结点尽量少归结点尽量少归结点尽量少归结点尽量少控制策略的原则控制策略的原则控制策略的原则控制策略的原

166、则给出控制策略，选择给出控制策略，选择给出控制策略，选择给出控制策略，选择合适的子句合适的子句合适的子句合适的子句方可做归结方可做归结方可做归结方可做归结避免多余的、不必要的归结式出现避免多余的、不必要的归结式出现避免多余的、不必要的归结式出现避免多余的、不必要的归结式出现或者说，少做些归结仍能导出空子句或者说，少做些归结仍能导出空子句或者说，少做些归结仍能导出空子句或者说，少做些归结仍能导出空子句控制策略的分类控制策略的分类控制策略的分类控制策略的分类删除策略删除策略删除策略删除策略 删除某些无用的子句，以缩小搜索范围删除某些无用的子句，以缩小搜索范围删除某些无用的子句，以缩小搜索范围删除某

167、些无用的子句，以缩小搜索范围限制策略限制策略限制策略限制策略 对参加归结的子句进行某些限制对参加归结的子句进行某些限制对参加归结的子句进行某些限制对参加归结的子句进行某些限制( ( ( (启发信息启发信息启发信息启发信息) ) ) )，以减少归结的盲目性，尽快得到空子句以减少归结的盲目性，尽快得到空子句以减少归结的盲目性，尽快得到空子句以减少归结的盲目性，尽快得到空子句2021/6/41113.63.6归结策略讨论（续归结策略讨论（续归结策略讨论（续归结策略讨论（续1 1）一：归结的一般过程一：归结的一般过程一：归结的一般过程一：归结的一般过程设有子句集设有子句集设有子句集设有子句集 S =

168、C1 S = C1 S = C1 S = C1，C2 C2 C2 C2 ，C3 C3 C3 C3 ，C4 C4 C4 C4 其中其中其中其中C1C1C1C1，C2C2C2C2，C3C3C3C3，C4C4C4C4是是是是S S S S中的子句。计算机对此子句进行归结的中的子句。计算机对此子句进行归结的中的子句。计算机对此子句进行归结的中的子句。计算机对此子句进行归结的一般过程是（广度优先搜索方式）：一般过程是（广度优先搜索方式）：一般过程是（广度优先搜索方式）：一般过程是（广度优先搜索方式）：（1 1 1 1）从子句）从子句）从子句）从子句C1C1C1C1开始，逐个与开始，逐个与开始，逐个与开始

169、，逐个与C2C2C2C2，C3C3C3C3，C4C4C4C4进行比较，看哪两个子进行比较，看哪两个子进行比较，看哪两个子进行比较，看哪两个子句可进行归结。若能找到，就求出归结式。然后用句可进行归结。若能找到，就求出归结式。然后用句可进行归结。若能找到，就求出归结式。然后用句可进行归结。若能找到，就求出归结式。然后用C2C2C2C2与与与与C3C3C3C3，C4C4C4C4进进进进行比较，凡可归结的都进行归结，最后用行比较，凡可归结的都进行归结，最后用行比较，凡可归结的都进行归结，最后用行比较，凡可归结的都进行归结，最后用C3C3C3C3与与与与C4C4C4C4比较，若能归结比较，若能归结比较，

170、若能归结比较，若能归结也对它们进行归结；经过这一轮的比较及归结后，就会得到一组也对它们进行归结；经过这一轮的比较及归结后，就会得到一组也对它们进行归结；经过这一轮的比较及归结后，就会得到一组也对它们进行归结；经过这一轮的比较及归结后，就会得到一组归结式，称为第一级归结式。归结式，称为第一级归结式。归结式，称为第一级归结式。归结式，称为第一级归结式。2021/6/4112 S1= C12S1= C12S1= C12S1= C12，C13C13C13C13，C14C14C14C14，C23C23C23C23，C24C24C24C24，C34C34C34C34（2 2 2 2）再从）再从）再从）再从

171、C1C1C1C1开始，用开始，用开始，用开始，用S S S S中的子句分别与第一级归结式中的子句进行中的子句分别与第一级归结式中的子句进行中的子句分别与第一级归结式中的子句进行中的子句分别与第一级归结式中的子句进行比较、归结，这样又会得到一组归结式，称为第二级归结式。比较、归结，这样又会得到一组归结式，称为第二级归结式。比较、归结，这样又会得到一组归结式，称为第二级归结式。比较、归结，这样又会得到一组归结式，称为第二级归结式。S2=C112S2=C112S2=C112S2=C112，C113C113C113C113，C114C114C114C114，C123C123C123C123，C124C

172、124C124C124，C134C134C134C134，C212C212C212C212，C213C213C213C213， （3 3 3 3）仍然从）仍然从）仍然从）仍然从C1C1C1C1开始，用开始，用开始，用开始，用S S S S中的子句及第一级归结式中的子句逐个地中的子句及第一级归结式中的子句逐个地中的子句及第一级归结式中的子句逐个地中的子句及第一级归结式中的子句逐个地与第二级归结式中的子句进行比较，得到第三级归结式。与第二级归结式中的子句进行比较，得到第三级归结式。与第二级归结式中的子句进行比较，得到第三级归结式。与第二级归结式中的子句进行比较，得到第三级归结式。S3=C1112S

173、3=C1112S3=C1112S3=C1112，C1113C1113C1113C1113，C1114C1114C1114C1114，C1123C1123C1123C1123，C1124C1124C1124C1124，C1134C1134C1134C1134， 如此继续，直到出现了空子句或者不能再继续归结时为止。只要子如此继续，直到出现了空子句或者不能再继续归结时为止。只要子如此继续，直到出现了空子句或者不能再继续归结时为止。只要子如此继续，直到出现了空子句或者不能再继续归结时为止。只要子句集是不可满足的，上述归结过程一定会归结出空子句而终止。句集是不可满足的，上述归结过程一定会归结出空子句而终

174、止。句集是不可满足的，上述归结过程一定会归结出空子句而终止。句集是不可满足的，上述归结过程一定会归结出空子句而终止。这这这这种归结是完备的，不会改变子句集的逻辑结论种归结是完备的，不会改变子句集的逻辑结论种归结是完备的，不会改变子句集的逻辑结论种归结是完备的，不会改变子句集的逻辑结论，如果子句集有空子，如果子句集有空子，如果子句集有空子，如果子句集有空子句，则一定可归结出空子句。句，则一定可归结出空子句。句，则一定可归结出空子句。句，则一定可归结出空子句。2021/6/4113 例例例例 3.6.1 3.6.1 3.6.1 3.6.1 设子句集设子句集设子句集设子句集 S= P S= P S=

175、 P S= P， R R R R， PQPQPQPQ， QRQRQRQR 归结过程为：归结过程为：归结过程为：归结过程为： S S S S： （1 1 1 1） P P P P （2 2 2 2） R R R R （3 3 3 3） PQPQPQPQ （4 4 4 4） QRQRQRQR S1 S1 S1 S1： （5 5 5 5）Q Q Q Q （1 1 1 1）与（）与（）与（）与（3 3 3 3）归结）归结）归结）归结 （6 6 6 6） Q Q Q Q （2 2 2 2）与（）与（）与（）与（4 4 4 4）归结）归结）归结）归结 （7 7 7 7） PR PR PR PR （3 3

176、3 3）与（）与（）与（）与（4 4 4 4）归结）归结）归结）归结 S2 S2 S2 S2： （8 8 8 8）R R R R （1 1 1 1）与（）与（）与（）与（7 7 7 7）归结）归结）归结）归结 （9 9 9 9） P P P P （2 2 2 2）与（）与（）与（）与（7 7 7 7）归结）归结）归结）归结2021/6/4114 （10101010） P P P P （3 3 3 3）与（）与（）与（）与（6 6 6 6）归结）归结）归结）归结 （11111111）R R R R （4 4 4 4）与（）与（）与（）与（5 5 5 5）归结）归结）归结）归结 S3 S3 S3

177、S3： （12121212）nil nil nil nil （1 1 1 1）与（）与（）与（）与（9 9 9 9）归结）归结）归结）归结S S S S： P P P P， R R R R， PQPQPQPQ， QR QR QR QR S1S1S1S1： Q Q Q Q ， Q Q Q Q， PR PR PR PR S2S2S2S2： R R R R ， P P P P ， P P P P ，R R R R S3S3S3S3：nilnilnilnil 由此例可以看出，按一般归结过程进行归结时，不仅归结出了许由此例可以看出，按一般归结过程进行归结时，不仅归结出了许由此例可以看出，按一般归结过程进

178、行归结时，不仅归结出了许由此例可以看出，按一般归结过程进行归结时，不仅归结出了许多无用的子句，而且有一些归结式还是重复的，既费时又费空间。多无用的子句，而且有一些归结式还是重复的，既费时又费空间。多无用的子句，而且有一些归结式还是重复的，既费时又费空间。多无用的子句，而且有一些归结式还是重复的，既费时又费空间。2021/6/4115二、删除策略二、删除策略二、删除策略二、删除策略 归结过程是一个不断寻找可归结子句的过程，子句越多，付出归结过程是一个不断寻找可归结子句的过程，子句越多，付出归结过程是一个不断寻找可归结子句的过程，子句越多，付出归结过程是一个不断寻找可归结子句的过程，子句越多，付出

179、的代价就越大。如果在归结时能把子句集中的无用子句删除掉，这的代价就越大。如果在归结时能把子句集中的无用子句删除掉，这的代价就越大。如果在归结时能把子句集中的无用子句删除掉，这的代价就越大。如果在归结时能把子句集中的无用子句删除掉，这样就会缩小寻找范围，减少比较次数，从而提高归结的效率。删除样就会缩小寻找范围，减少比较次数，从而提高归结的效率。删除样就会缩小寻找范围，减少比较次数，从而提高归结的效率。删除样就会缩小寻找范围，减少比较次数，从而提高归结的效率。删除策略正是出于这一考虑提出来的，它有以下几种删除方法：策略正是出于这一考虑提出来的，它有以下几种删除方法：策略正是出于这一考虑提出来的，它

180、有以下几种删除方法：策略正是出于这一考虑提出来的，它有以下几种删除方法：（1 1 1 1）纯文字删除法）纯文字删除法）纯文字删除法）纯文字删除法 如果某文字如果某文字如果某文字如果某文字L L L L在子句集中不存在可与之互补的文字在子句集中不存在可与之互补的文字在子句集中不存在可与之互补的文字在子句集中不存在可与之互补的文字L L L L，则称该，则称该，则称该，则称该文字为纯文字。显然，在归结时纯文字不可能被消去，因而，用包文字为纯文字。显然，在归结时纯文字不可能被消去，因而，用包文字为纯文字。显然，在归结时纯文字不可能被消去，因而，用包文字为纯文字。显然，在归结时纯文字不可能被消去，因而

181、，用包含它的子句进行归结时不可能得到空子句，即这样的子句对归结是含它的子句进行归结时不可能得到空子句，即这样的子句对归结是含它的子句进行归结时不可能得到空子句，即这样的子句对归结是含它的子句进行归结时不可能得到空子句，即这样的子句对归结是无意义的，所以可以把它所在的子句从子句集中删去，这样不会影无意义的，所以可以把它所在的子句从子句集中删去，这样不会影无意义的，所以可以把它所在的子句从子句集中删去，这样不会影无意义的，所以可以把它所在的子句从子句集中删去，这样不会影响子句集的不可满足性。响子句集的不可满足性。响子句集的不可满足性。响子句集的不可满足性。2021/6/4116例如，设有子句集例如

182、，设有子句集例如，设有子句集例如，设有子句集 S=PQR S=PQR S=PQR S=PQR， QRQRQRQR，Q Q Q Q， RRRR其中其中其中其中P P P P是纯文字，因此可将子句是纯文字，因此可将子句是纯文字，因此可将子句是纯文字，因此可将子句PQRPQRPQRPQR从从从从S S S S中删去。中删去。中删去。中删去。（2 2 2 2）重言式删除法）重言式删除法）重言式删除法）重言式删除法 如果一个子句中同时包含互补文字对，则称该子句为重言式。如果一个子句中同时包含互补文字对，则称该子句为重言式。如果一个子句中同时包含互补文字对，则称该子句为重言式。如果一个子句中同时包含互补文

183、字对，则称该子句为重言式。例如例如例如例如 ：P P P P（x x x x）PPPP（x x x x），），），），P P P P（x x x x）QQQQ（x x x x）PPPP（x x x x）都是重言式。）都是重言式。）都是重言式。）都是重言式。 重言式是真值为真的子句，重言式是真值为真的子句，重言式是真值为真的子句，重言式是真值为真的子句，删去删去删去删去后不会影响它的不可满足性，因后不会影响它的不可满足性，因后不会影响它的不可满足性，因后不会影响它的不可满足性，因而可以从子句集中删去重言式。而可以从子句集中删去重言式。而可以从子句集中删去重言式。而可以从子句集中删去重言式。（3

184、3 3 3）包孕删除法）包孕删除法）包孕删除法）包孕删除法 设有子句设有子句设有子句设有子句C1C1C1C1和和和和C2C2C2C2，如果存在一个代换，如果存在一个代换，如果存在一个代换，如果存在一个代换，使得，使得，使得，使得C1 C2C1 C2C1 C2C1 C2，则称，则称，则称，则称C1C1C1C1包孕于包孕于包孕于包孕于C2C2C2C2。例如：。例如：。例如：。例如：2021/6/4117 P P P P（x x x x） 包孕于包孕于包孕于包孕于 P P P P（y y y y） Q Q Q Q（z z z z） =y/x =y/x =y/x =y/x P P P P（x x x

185、x） 包孕于包孕于包孕于包孕于 P P P P（a a a a） =a/x =a/x =a/x =a/x P P P P（x x x x） 包孕于包孕于包孕于包孕于 P P P P（a a a a） Q Q Q Q（z z z z） =a/x =a/x =a/x =a/x P P P P（x x x x）QQQQ（a a a a）包孕于）包孕于）包孕于）包孕于 P P P P（f(a)f(a)f(a)f(a)） Q Q Q Q（a a a a）RRRR（y y y y） =f(a)/x=f(a)/x=f(a)/x=f(a)/x P P P P（x x x x）QQQQ（y y y y）包孕于）

186、包孕于）包孕于）包孕于 P P P P（a a a a） Q Q Q Q（u u u u）RRRR（w w w w） =a/x,u/y=a/x,u/y=a/x,u/y=a/x,u/y把子句集中被包孕的子句删去后，不会影响子句集的不可满足性。把子句集中被包孕的子句删去后，不会影响子句集的不可满足性。把子句集中被包孕的子句删去后，不会影响子句集的不可满足性。把子句集中被包孕的子句删去后，不会影响子句集的不可满足性。例如：例如：例如：例如：S= PS= PS= PS= P（x x x x），），），），P P P P（y y y y）QQQQ（z z z z），），），），P P P P（a a a

187、 a）RRRR（y y y y） 因为因为因为因为 P P P P（x x x x）包孕于）包孕于）包孕于）包孕于P P P P（y y y y）QQQQ（z z z z），所以，从子句集），所以，从子句集），所以，从子句集），所以，从子句集S S S S中删去中删去中删去中删去P P P P（x x x x），并不影响），并不影响），并不影响），并不影响S S S S的不可满足性。的不可满足性。的不可满足性。的不可满足性。2021/6/4118 三：支持集策略三：支持集策略三：支持集策略三：支持集策略 支持集策略是沃斯（支持集策略是沃斯（支持集策略是沃斯（支持集策略是沃斯（WosWosWos

188、Wos）等人在）等人在）等人在）等人在1965196519651965年提出的一种归结策略。年提出的一种归结策略。年提出的一种归结策略。年提出的一种归结策略。它对参加归结的子句对提出了如下限制：每次归结时，亲本子句中它对参加归结的子句对提出了如下限制：每次归结时，亲本子句中它对参加归结的子句对提出了如下限制：每次归结时，亲本子句中它对参加归结的子句对提出了如下限制：每次归结时，亲本子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后至少应有一个是由目标公式的否定所得到的子句，或者是它们的后至少应有一个是由目标公式的否定所得到的子句，或者是它们的后至少应有一个是由目标公式的否定所得到

189、的子句，或者是它们的后裔。支持集策略是完备的，即：如果子句集是不可满足的，则由支裔。支持集策略是完备的，即：如果子句集是不可满足的，则由支裔。支持集策略是完备的，即：如果子句集是不可满足的，则由支裔。支持集策略是完备的，即：如果子句集是不可满足的，则由支持集策略一定可以归结出空子句持集策略一定可以归结出空子句持集策略一定可以归结出空子句持集策略一定可以归结出空子句，该归结方法限制了第一级归结式，该归结方法限制了第一级归结式，该归结方法限制了第一级归结式，该归结方法限制了第一级归结式产生的数量，进而提高了归结速度。产生的数量，进而提高了归结速度。产生的数量，进而提高了归结速度。产生的数量，进而提

190、高了归结速度。例例例例3.6.23.6.23.6.23.6.2：设有子句集：设有子句集：设有子句集：设有子句集S=S=S=S= I I I I（x x x x）RRRR（x x x x），I I I I（a a a a），），），）， R R R R（y y y y） L L L L（y y y y），），），），L L L L（a a a a） 其中其中其中其中I I I I（x x x x）RRRR（x x x x）是目标公式否定后得到的子句。是目标公式否定后得到的子句。是目标公式否定后得到的子句。是目标公式否定后得到的子句。 2021/6/4119 用支持集策略进行归结的过程用支持集策略

191、进行归结的过程用支持集策略进行归结的过程用支持集策略进行归结的过程如下：如下：如下：如下：S S S S： （1 1 1 1） I I I I（x x x x）RRRR（x x x x） （2 2 2 2）I I I I（a a a a） （3 3 3 3） R R R R（y y y y） L L L L（y y y y） （4 4 4 4）L L L L（a a a a） S1 S1 S1 S1： （5 5 5 5）R R R R（a a a a） （1 1 1 1）与（）与（）与（）与（2 2 2 2）归结）归结）归结）归结 =a/x =a/x =a/x =a/x （6 6 6 6） I

192、 I I I（x x x x） L L L L（x x x x） （1 1 1 1）与（）与（）与（）与（3 3 3 3）归结）归结）归结）归结 S2 S2 S2 S2： （7 7 7 7） L L L L（a a a a） （2 2 2 2）与（）与（）与（）与（6 6 6 6）归结）归结）归结）归结 （8 8 8 8） L L L L（a a a a） （3 3 3 3）与（）与（）与（）与（5 5 5 5）归结）归结）归结）归结 （9 9 9 9） I I I I（a a a a） （4 4 4 4）与（）与（）与（）与（6 6 6 6）归结）归结）归结）归结 S3 S3 S3 S3：

193、（10101010）nil nil nil nil （2 2 2 2）与（）与（）与（）与（9 9 9 9）归结）归结）归结）归结2021/6/4120上述归结过程可用下图直观表示出来上述归结过程可用下图直观表示出来I(x)R(x)I(x)R(x)I(x)R(x)I(x)R(x)I(a)I(a)I(a)I(a)R(y)L(y)R(y)L(y)R(y)L(y)R(y)L(y)L(a)L(a)L(a)L(a)S Sa/xa/xa/xa/x R(A)R(A)R(A)R(A)x/yx/yx/yx/yI(x)L(x)I(x)L(x)I(x)L(x)I(x)L(x)S S1 1 L(a) L(a) L(a

194、) L(a) L(a)L(a)L(a)L(a)I(a)I(a)I(a)I(a)S S2 2nilnilnilnilS S3 3该归结方法限制了第一级归结式的数量该归结方法限制了第一级归结式的数量该归结方法限制了第一级归结式的数量该归结方法限制了第一级归结式的数量2021/6/4121上述归结过程可用下图直观表示出来上述归结过程可用下图直观表示出来特点特点特点特点( ( ( (完备的完备的完备的完备的):):):):问题是归结出了许多无用子句，浪费时空问题是归结出了许多无用子句，浪费时空问题是归结出了许多无用子句，浪费时空问题是归结出了许多无用子句，浪费时空; ; ; ;当问题有解时保证能找到最

195、短的归结路径适合小问当问题有解时保证能找到最短的归结路径适合小问当问题有解时保证能找到最短的归结路径适合小问当问题有解时保证能找到最短的归结路径适合小问题，对大问题易产生组合爆炸题，对大问题易产生组合爆炸题，对大问题易产生组合爆炸题，对大问题易产生组合爆炸设有子句集设有子句集设有子句集设有子句集S=S=S=S=I(x)R(x)I(x)R(x)I(x)R(x)I(x)R(x),I(A),I(A),I(A),I(A),R(y)R(y)R(y)R(y)L(y),L(y),L(y),L(y),L(A)L(A)L(A)L(A) 目标公式的否定目标公式的否定目标公式的否定目标公式的否定I(x)R(x)I(

196、x)R(x)I(x)R(x)I(x)R(x)I(a)I(a)I(a)I(a)R(y)L(y)R(y)L(y)R(y)L(y)R(y)L(y)L(a)L(a)L(a)L(a)S Sa/xa/xa/xa/x R(a)R(a)R(a)R(a)x/yx/yx/yx/yI(x)L(x)I(x)L(x)I(x)L(x)I(x)L(x)a/ya/ya/ya/yR(a)R(a)R(a)R(a)S S1 1I(a)I(a)I(a)I(a) L(a) L(a) L(a) L(a) L(a) L(a) L(a) L(a)I(a)I(a)I(a)I(a)S S2 2NILNILNILNIL2021/6/4122四：线

197、性输入策略四：线性输入策略 这种归结策略对参加归结的子句提出了如下限这种归结策略对参加归结的子句提出了如下限制：参加归结的两个子句中必须至少有一个是初制：参加归结的两个子句中必须至少有一个是初始子句集中的子句。所谓初始子句集是指初始时始子句集中的子句。所谓初始子句集是指初始时要求进行归结的那个子句集。例如：在归结反演要求进行归结的那个子句集。例如：在归结反演中，初始子句集就是由已知前提及结论的否定化中，初始子句集就是由已知前提及结论的否定化而得到的子句集。而得到的子句集。例：用线性输入策略对上例的子句集进行归结例：用线性输入策略对上例的子句集进行归结2021/6/4123 S S S S： （

198、1 1 1 1） I I I I（x x x x）RRRR（x x x x） （2 2 2 2）I I I I（a a a a） （3 3 3 3） R R R R（y y y y） L L L L（y y y y） （4 4 4 4）L L L L（a a a a） S1 S1 S1 S1：（：（：（：（5 5 5 5）R R R R（a a a a） （1 1 1 1）与（）与（）与（）与（2 2 2 2）归结）归结）归结）归结 （6 6 6 6） I I I I（x x x x） L L L L（x x x x） （1 1 1 1）与（）与（）与（）与（3 3 3 3）归结）归结）归结）

199、归结 （7 7 7 7） R R R R（a a a a） （3 3 3 3）与（）与（）与（）与（4 4 4 4）归结）归结）归结）归结 S2 S2 S2 S2：（：（：（：（8 8 8 8） I I I I（a a a a） （1 1 1 1）与（）与（）与（）与（7 7 7 7）归结）归结）归结）归结 （9 9 9 9） L L L L（a a a a） （2 2 2 2）与（）与（）与（）与（6 6 6 6）归结）归结）归结）归结 （10101010） L L L L（a a a a） （3 3 3 3）与（）与（）与（）与（5 5 5 5）归结）归结）归结）归结 （11111111）

200、 I I I I（a a a a） （4 4 4 4）与（）与（）与（）与（6 6 6 6）归结）归结）归结）归结S3S3S3S3： （12121212）nil nil nil nil （2 2 2 2）与（）与（）与（）与（8 8 8 8）归结）归结）归结）归结2021/6/4124线性输入策略举例线性输入策略举例I(x)R(x)I(x)R(x)I(x)R(x)I(x)R(x)I(A)I(A)I(A)I(A)R(y)L(y)R(y)L(y)R(y)L(y)R(y)L(y)L(A)L(A)L(A)L(A)S S R(A)R(A)R(A)R(A)I(x)L(x)I(x)L(x)I(x)L(x)I

201、(x)L(x)R(A)R(A)R(A)R(A)S S1 1I(A)I(A)I(A)I(A) L(A) L(A) L(A) L(A) L(A) L(A) L(A) L(A)I(A)I(A)I(A)I(A)S S2 2NILNILNILNILS S3 32021/6/4125线性输入策略特点线性输入策略特点 线性输入策略限制了生成归结式的数量线性输入策略限制了生成归结式的数量，具有，具有简单、高效的优点，但它是不完备的。也就是说，简单、高效的优点，但它是不完备的。也就是说，即使子句集是不可满足的，用线性输入策略进行即使子句集是不可满足的，用线性输入策略进行归结时也不一定能归结出空子句。归结时也不一

202、定能归结出空子句。2021/6/4126五：单文字子句策略五：单文字子句策略五：单文字子句策略五：单文字子句策略如果一个子句只包含一个文字如果一个子句只包含一个文字如果一个子句只包含一个文字如果一个子句只包含一个文字, , , , 则称它为单文字子句则称它为单文字子句则称它为单文字子句则称它为单文字子句. . . .单文字子句策略要求参加归结的两个子句中必须至少有单文字子句策略要求参加归结的两个子句中必须至少有单文字子句策略要求参加归结的两个子句中必须至少有单文字子句策略要求参加归结的两个子句中必须至少有一个是单文字子句一个是单文字子句一个是单文字子句一个是单文字子句. . . . 例例例例:

203、 : : :对上述例子从新归结对上述例子从新归结对上述例子从新归结对上述例子从新归结2021/6/4127 S S S S： （1 1 1 1）I I I I（x x x x）RRRR（x x x x） （2 2 2 2）I I I I（a a a a） （3 3 3 3）R R R R（y y y y）L L L L（y y y y） （4 4 4 4）L L L L（a a a a） S1 S1 S1 S1： （5 5 5 5）R R R R（a a a a） （1 1 1 1）与（）与（）与（）与（2 2 2 2）归结）归结）归结）归结 （6 6 6 6）R R R R（a a a a）

204、 （3 3 3 3）与（）与（）与（）与（4 4 4 4）归结）归结）归结）归结 S2 S2 S2 S2： （7 7 7 7）I I I I（a a a a） （1 1 1 1）与（）与（）与（）与（6 6 6 6）归结）归结）归结）归结 （8 8 8 8）L L L L（a a a a） （3 3 3 3）与（）与（）与（）与（5 5 5 5）归结）归结）归结）归结 S3 S3 S3 S3： （12121212）nil nil nil nil （2 2 2 2）与（）与（）与（）与（7 7 7 7）归结）归结）归结）归结2021/6/4128单文字子句策略树形图单文字子句策略树形图I(x)I

205、(x)I(x)I(x)R(x)R(x)R(x)R(x)I(a)I(a)I(a)I(a)R(y)R(y)R(y)R(y)L(y)L(y)L(y)L(y)L(a)L(a)L(a)L(a)S Sa/xa/xa/xa/x R(a)R(a)R(a)R(a)a/ya/ya/ya/yR(a)R(a)R(a)R(a)S S1 1S S2 2NILNILNILNIL2021/6/4129六：祖先过滤形策略六：祖先过滤形策略六：祖先过滤形策略六：祖先过滤形策略 该策略与线性输入策略比较相似，只是放宽了限制。该策略与线性输入策略比较相似，只是放宽了限制。该策略与线性输入策略比较相似，只是放宽了限制。该策略与线性输入

206、策略比较相似，只是放宽了限制。当对两个子句和进行归结时，只要它们满足下述两个条当对两个子句和进行归结时，只要它们满足下述两个条当对两个子句和进行归结时，只要它们满足下述两个条当对两个子句和进行归结时，只要它们满足下述两个条件中的任意一个就可以进行归结：件中的任意一个就可以进行归结：件中的任意一个就可以进行归结：件中的任意一个就可以进行归结：（1 1 1 1）C1C1C1C1与与与与C2C2C2C2中至少有一个是初始子句集中的子句。中至少有一个是初始子句集中的子句。中至少有一个是初始子句集中的子句。中至少有一个是初始子句集中的子句。（2 2 2 2）如果两个子句都不是初始子句集中的子句，则一个）

207、如果两个子句都不是初始子句集中的子句，则一个）如果两个子句都不是初始子句集中的子句，则一个）如果两个子句都不是初始子句集中的子句，则一个应是另一个的祖先。所谓一个子句（例如应是另一个的祖先。所谓一个子句（例如应是另一个的祖先。所谓一个子句（例如应是另一个的祖先。所谓一个子句（例如C1C1C1C1）是另一个）是另一个）是另一个）是另一个子句（例如子句（例如子句（例如子句（例如C2C2C2C2）的祖先是指）的祖先是指）的祖先是指）的祖先是指C2C2C2C2是有是有是有是有C1C1与别的子句归结后与别的子句归结后与别的子句归结后与别的子句归结后得到的归结式。得到的归结式。得到的归结式。得到的归结式。

208、是完备的归结策略是完备的归结策略是完备的归结策略是完备的归结策略2021/6/4130祖先过滤策略举例祖先过滤策略举例 S=S=S=S=Q(x)Q(x)Q(x)Q(x)P(x),Q(y)P(x),Q(y)P(x),Q(y)P(x),Q(y)P(y),P(y),P(y),P(y), Q(w)P(w),Q(a)P(a)Q(w)P(w),Q(a)P(a)Q(w)P(w),Q(a)P(a)Q(w)P(w),Q(a)P(a)Q(x)Q(x)Q(x)Q(x)P(x)P(x)P(x)P(x)Q(y)Q(y)Q(y)Q(y)P(y)P(y)P(y)P(y)Q(w)P(w)Q(w)P(w)Q(w)P(w)Q(w

209、)P(w)Q(a)P(a)Q(a)P(a)Q(a)P(a)Q(a)P(a)x/yx/yx/yx/yP(x)P(x)P(x)P(x)w/xw/xw/xw/xQ(w)Q(w)Q(w)Q(w)a/wa/wa/wa/wP(a)P(a)P(a)P(a)a/xa/xa/xa/xNILNILNILNILP(x)P(x)P(x)P(x)是是是是P(a)P(a)P(a)P(a)的的的的先辈子句先辈子句先辈子句先辈子句2021/6/4131本章重点1.自然演绎推理的核心公式要熟记2.掌握谓词公式如何化为子句集的步骤3.掌握如何利用归结原理进行问题的证明进行问题证明所用的理论根据就是：（P1P2Pn） Q 永假性成立也即：（P1P2Pn）Q 永真性成立4.掌握用归结原理进行问题的求解过程步骤：把待求的问题也用谓词表示出来，并否定后和ANSWER（x）专用谓词析取子句，然后进行归结，最后只剩下ANSWER（ ），此时x已被常量所替代。 5.归结策略的几种方法要清楚 6.基于规则的正向和逆向演绎推理注意：需要说明的是上面列出的归结过程均是按广度优先策略进行搜索推理的。2021/6/4132部分资料从网络收集整理而来，供大家参考，感谢您的关注！