第3讲 谓词逻辑与归纳原理

1、中国农业大学信息与电气工程学院v马少平，朱小燕，人工智能，清华大学出版社马少平，朱小燕，人工智能，清华大学出版社教学提纲v概述概述v命题逻辑的归结法命题逻辑的归结法v谓词归结子句形谓词归结子句形v归结原理归结原理v归结过程的策略控制归结过程的策略控制vHerbrand定理定理v明星都有钱明星都有钱v有钱人都任性有钱人都任性v明星都任性明星都任性v经典逻辑：主要经典逻辑：主要包括命题逻辑和谓词逻辑包括命题逻辑和谓词逻辑。非经。非经典逻辑：主要典逻辑：主要包括模态逻辑、时态逻辑、弗协调包括模态逻辑、时态逻辑、弗协调逻辑和直觉主义逻辑。逻辑和直觉主义逻辑。归结推理命题逻辑谓词逻辑Skolem标准形、

2、子句集基本概念谓词逻辑归结原理合一和置换、控制策略数理逻辑命题逻辑归结Herbrand定理第3讲 谓词逻辑与归结原理v概述概述v命题逻辑的归结法命题逻辑的归结法v谓词归结子句形谓词归结子句形v归结原理归结原理v归结过程的策略控制归结过程的策略控制概述v 归结原理归结原理由由J.A.Robinson由由1965年提出。年提出。 与演绎法(deductive inference)完全不同，新的逻辑演算(inductive inference)算法。 一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。 语义网络、框架表示、产生式规则等等

3、都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。 而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）v 本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题谓词逻辑问题。 第3讲 谓词逻辑与归结原理v概述概述v命题逻辑的归结法命题逻辑的归结法v谓词归结子句形谓词归结子句形v归结原理归结原理v归结过程的策略控制归结过程的策略控制vHerbrand定理定理命题逻辑的归结法v命题逻辑（命题逻辑（Propositional Logic）基础：）基础： 定义：对于命题定义：对于命题p，q 命题的非： p

4、 命题与（合取式）：p与q，记做p q 命题或（析取式）： p或q，记做p q 蕴含式： 如果p则q，记做p q 等价式：p当且仅当q，记做p q命题逻辑基础：公式v在命题逻辑中，我们将命题成为原子公式（在命题逻辑中，我们将命题成为原子公式（Atomic Formula），简称），简称原子原子。v定义定义：公式公式1.原子是公式；原子是公式；2.若若G，H是公式，则是公式，则(G)、(G H )、 (G H )、 (G H )、 (G H )是公式；是公式；3.所有公式都是有限次使用所有公式都是有限次使用(1)、(2)得到的符号串得到的符号串。命题逻辑基础：真值表（解释）PP0110P QP

5、Q0 000 101 001 11P QP Q0 000 111 011 11P QP Q0 010 111 001 11P QP Q0 010 101 001 11命题逻辑基础v定义：对于公式定义：对于公式A 若A在它的所有解释下，其真值都为T（真），则称A为重言式或恒真式恒真式； 若A在它的所有解释下，其真值都为F（假），则称A为不可满足的不可满足的（Unsatisfiable，或永假式）； 若至少存在一个解释，使得A为真，则称A为可满足的可满足的（Satisfiable）； 逻辑蕴涵逻辑蕴涵：公式G，H，如果（G H）是恒真的，记为G H 。 逻辑等价逻辑等价：公式G，H，如果（G H）

6、是恒真的，记为G H 。命题逻辑基础：范式 析取范式析取范式：公式G为析取范式，如果： G L1 L2 Ln 其中Li（i = 1, 2, , n）是原子或原子的非的合取式。 合取范式合取范式：公式G为合取范式，如果： G L1 L2 Ln 其中Li（i = 1, 2, , n）是原子或原子的非的惜取式。 任何一个公式在等价的意义下，都可转化成析取范式或者合取范式。 文字（文字（Literal）：一个原子或原子的非。 子句（子句（Clause）：文字的析取式。 空子句空子句：不含文字的空集合。命题逻辑基础：基本等值式v基本等值基本等值式式 交换率：pq q p ； p q q p 结合率： (

7、pq) r p(q r); (p q) r p (q r) 分配率： p(q r) (pq)(p r) ； p (q r) (p q) (p r) 命题逻辑基础：基本等值式v基本等值基本等值式式 摩根率: (pq) p q ； (p q) p q 吸收率: p(pq ) p， p (pq ) p ； 泛界律: pF p ， pT p， p F F ， pT T 互余律：G G T(恒真)， G G F(恒假) 蕴含等值式:p q pq 等价等值式： p q （ p q ） （ q p ） 假言易位式: p q q p 等价否等等值式： p q q p 归谬论：（ p q ） （ p q ） p

8、命题例v 命题：命题：能判断真假（不是既真又假）的陈述句。能判断真假（不是既真又假）的陈述句。简单陈述句描述事实、事物的状态、关系等性质。简单陈述句描述事实、事物的状态、关系等性质。例如：例如：1 1+1=2 2 雪是黑色的。 3 北京是中国的首都。 4 到冥王星去渡假。 判断判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，有可句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上能

9、变成真，但不管怎样，真值是唯一的。因此，以上4个例子都是命题。个例子都是命题。而例如：而例如：1 快点走吧！快点走吧！ 2 到那去？到那去？ 3 x+y10等等句子，都不是命题。等等句子，都不是命题。命题表示公式（1）将陈述句转化成命题公式。如：设“下雨”为p，“骑车上班”为q，1“只要不下雨，我骑自行车上班”。p 是 q的充分条件，因而，可得命题公式： p q2“只有不下雨，我才骑自行车上班”。p 是 q的必要条件，因而，可得命题公式：q p 命题表示公式（2）例如：例如：v 1 “如果我进城我就去看你，除非我很累。如果我进城我就去看你，除非我很累。”设：设：p，我进城，我进城，q，去看你，

10、去看你，r，我很累。，我很累。则有则有命题公式：命题公式：r (p q)。v 2“应届高中生，得过数学或物理竞赛的一等应届高中生，得过数学或物理竞赛的一等 奖，奖，保送上北京大学。保送上北京大学。” 设：设：p，应届高中生，应届高中生，q，保送上北京大学上学，保送上北京大学上学， r，是得过数学一等奖。，是得过数学一等奖。t，是得过物理一等奖。，是得过物理一等奖。 则有命题公式公式：则有命题公式公式：p ( r t t ) q。 命题逻辑的归结法v基本单元：简单命题（陈述句）基本单元：简单命题（陈述句）例： 命题： A1、A2、A3 和 B求证： A1A2A3成立，则B成立，即：A1A2A3

11、B反证法：证明A1A2A3B 是矛盾式 （永假式） 命题逻辑的归结法v 建立子句集建立子句集合取范式：命题、命题和的与， 如：P（ PQ）（ PQ）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：P（ PQ）（ PQ） 子句集 S：S = P, PQ, PQ 命题逻辑的归结法v归结式归结式消除互补对，求新子句得到归结式。如子句：C1, C2， 归结式：R(C1, C2) = C1C2 注意：注意：C C1 1CC2 2 R(C R(C1 1, C, C2 2) ) ， 反之反之成立。成立。 命题逻辑的归结法v归结过程归结过程 将命题写成合取范式 求出子句集 对子句集使用归结推理规则

12、 归结式作为新子句参加归结 归结式为空子句 ，S是不可满足的（矛盾），原命题成立。 （证明完毕）v谓词的归结：除了有量词和函数以外，其余和谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。命题归结过程一样。 命题逻辑归结例题（1）v 例题，证明公式：例题，证明公式：(P Q) (Q P)v 证明：证明： （1）根据归结原理，将待证明公式转化成待归结命题公式：）根据归结原理，将待证明公式转化成待归结命题公式：欲证结论的否：欲证结论的否： (P Q) (Q P) ( (P Q) (Q P)= (P Q) (Q P)（2）分别将公式前项化为合取范式：）分别将公式前项化为合取范式：P Q P

13、Q结论求后的后项化为合取范式：结论求后的后项化为合取范式：(Q P) (QP) Q P两项合并后化为合取范式：两项合并后化为合取范式：（P Q）Q P （3）则子句集为：）则子句集为： PQ，Q，P命题逻辑归结例题（2）子句集为：子句集为： PQ，Q，P（4）对子句集中的子句进行归结可得：）对子句集中的子句进行归结可得：v1. PQv2. Qv3. Pv4. Q，（1，3归结）归结）v5. ，（2，4归结）归结）由由上可得原公式成立。上可得原公式成立。第3讲 谓词逻辑与归结原理v概述概述v命题逻辑的归结法命题逻辑的归结法v谓词归结子句形谓词归结子句形v归结原理归结原理v归结过程的策略控制归结过

14、程的策略控制vHerbrand定理定理第3讲 谓词逻辑与归结原理v概述概述v命题逻辑的归结法命题逻辑的归结法v谓词归结子句形谓词归结子句形v归结原理归结原理v归结过程的策略控制归结过程的策略控制vHerbrand定理定理谓词归结原理基础一阶逻辑（一阶逻辑（First-Order Logic )为什么需要一阶逻辑？为什么需要一阶逻辑？命题命题A：人都是要死的。命题：人都是要死的。命题B：秦始皇是人。：秦始皇是人。命题命题C：秦始皇是要死的。：秦始皇是要死的。如何有如何有A、B推出推出C呢呢？命题逻辑：命题逻辑：p:A; q:B;r: pqr苏格拉底三段论的正确性苏格拉底三段论的正确性“命题命题A

15、：人都是要死的。命题：人都是要死的。命题B：秦始皇是人。：秦始皇是人。命题命题C：秦始皇是要死的：秦始皇是要死的。”设设P(x)：x是人是人，Q(x)：x是要死的，是要死的，a：秦始皇：秦始皇. x(P(x)Q(x)P(a)Q(a)设前件为真，即设前件为真，即x(P(x)Q(x)与与P(a)都为真都为真. 由于由于x(P(x)Q(x)为真，为真，故故P(a)Q(a)为真为真. 由由P(a) 与与P(a)Q(a)为真，根据假言推理得为真，根据假言推理得证证Q(a)为真为真.29v基本概念基本概念 个体词：表示主语的词 谓词：刻画个体性质或个体之间关系的词 量词：表示数量的词谓词归结原理基础v小王

16、是个工程师。小王是个工程师。v8是个自然数。是个自然数。v我去买花。我去买花。v小丽和小华是朋友。小丽和小华是朋友。其中，其中，“小王小王”、“工程师工程师”、“我我”、“花花”、“8”、“小丽小丽”、“小华小华”都是个体词，而都是个体词，而“是个工程师是个工程师”、“是是个自然数个自然数”、“去买去买”、“是朋友是朋友”都是谓词。显然前两都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词个谓词表示的是事物的性质，第三个谓词“去买去买”表示的表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓一个动作也表示了主、宾两个个体词的关系，最后一个谓词词“是朋友是朋友”表示两个个体词之间的关系

17、。表示两个个体词之间的关系。谓词归结原理基础一阶逻辑一阶逻辑v公式及其解释公式及其解释 个体常量：a,b,c 个体变量：x,y,z 谓词符号：P,Q,R 函数符号：f, g, h 量词符号： ,谓词归结原理基础：项与原子v定义定义：谓词逻辑中的：谓词逻辑中的项项（term）：）：1.常量符号是项；2.变量符号是项；3.若f是n元函数符号，t1, t2, , tn是项, 则f(t1, t2, , tn)是项；4.所有项都是有限次使用(1)-(3)生成的符号串。定义定义：谓词逻辑中的原子原子：若P(x1, x2, , xn)是n元谓词符号， t1, t2, , tn是项，则P (t1, t2, ,

18、 tn)是原子。谓词归结原理基础：公式v定义定义：谓词逻辑中的：谓词逻辑中的公式公式1.原子是公式；原子是公式；2.若若G，H是公式，则是公式，则(G)、(G H )、 (G H )、 (G H )、 (G H )是公式；是公式；3.若若G是公式，是公式，x 是是G中的自由变量，则中的自由变量，则( x)G，( x)G是公式；是公式；4.所有公式都是有限次使用所有公式都是有限次使用(1)(3)得到的符号串得到的符号串。谓词归结原理基础：解释v定义定义：公式：公式G的一个的一个解释解释I，是由非空区域，是由非空区域D和和下列对下列对G中的常量符号、谓词符号、函数符号的中的常量符号、谓词符号、函数

19、符号的一组指定组成：一组指定组成：1.对每个常量符号，指定对每个常量符号，指定D中一个元素；中一个元素；2.对每个对每个n元函数符号，指定一个函数，即指定元函数符号，指定一个函数，即指定Dn到到D的一个映射；的一个映射；3.对每个对每个m元谓词符号，指定一个谓词，即指定元谓词符号，指定一个谓词，即指定Dm到到T, F的一个映射。的一个映射。谓词归结原理基础：解释举例v 给出如下两个公式：给出如下两个公式：1.(x)(P(f(x) Q(x, f(a).2.( x)(P(x) Q(x, a).给出如下的解释I：D=1, 2a/1, f(1)/2, f(2)/1P(1)/F, P(2)/T, Q(1

20、, 1)/T, Q(1,2)/T, Q(2,1)/F, Q(2,2)/T于是公式（1）在I下取T值，公式（2）在I下取F值。谓词归结原理基础v 例如：（例如：（1）所有的人都是要死的。）所有的人都是要死的。v （2） 有的人活到一百岁以上。有的人活到一百岁以上。在个体域在个体域D为人类集合时，可符号化为：为人类集合时，可符号化为： （1） xPxP( (x x) )，其中，其中P P( (x x) )表示表示x x是要死的。是要死的。 （2） x Qx Q( (x x), ), 其中其中Q Q( (x x) )表示表示x x活到一百岁以上。活到一百岁以上。在个体域在个体域D是全总个体域时，是全

21、总个体域时，引入特殊谓词引入特殊谓词R R( (x x) )表示表示x x是人，可符号化为：是人，可符号化为： （1 1） x x（R R( (x x) ) P P( (x x) )）, , 其中，其中，R R( (x x) )表示表示x x是人；是人；P P( (x x) )表示表示x x是要死的。是要死的。 （2 2） x x（R R( (x x) ) Q Q( (x x) )），），其中，其中，R R( (x x) )表示表示x x是人；是人；Q Q( (x x) )表示表示x x活到一百岁以上。活到一百岁以上。 谓词归结原理基础量词否定等值式：量词否定等值式： ( x ） M（x） （

22、 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

23、（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）谓词归结子句形( Skolem 标准形)SKOLEMSKOLEM标准形标准形 前束范式定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式

24、的末端。 谓词归结子句形( Skolem 标准形)即：即： 把所有的量词都提到前面去，然后把所有的量词都提到前面去，然后消掉所有量词消掉所有量词(Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn)约束变项换名规则：约束变项换名规则： (Qx ） M（x） （Qy ） M（y） (Qx ） M（x,z） （Qy ） M（y,z）谓词归结子句形( Skolem 标准形) 量词消去原则：消去存在量词“”，略去全程量词“”。注意：注意：左边有全程量词的存在量词，消去时左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改该变量改写成为全程量词的函数；如没有，改写成为常量。写成为

25、常量。 谓词归结子句形( Skolem 标准形) Skolem定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。 SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。 谓词归结子句形( Skolem 标准形)例例: :将下式化为将下式化为Skolem标准形：标准形：(x)(y)P(a, x, y) (x)(y)Q(y, b)R(x) 解：第一步，消去号，得：(x)(y)P(a, x, y) (x) (y)Q(y, b)R(x) 第二步，深入到量词内部，得：(x)(y)P(a, x, y) (x) (y)Q(y, b)R(x)

26、第三步，变元易名，得(x)(y)P(a, x, y) (u) ( v)(Q(v, b) R(u) 第四步，存在量词左移，直至所有的量词移到前面，得： (x) (y) (u) ( v)P(a, x, y) (Q(v, b) R(u)由此得到前束范式谓词归结子句形( Skolem 标准形)第五步，消去“”（存在量词），略去“”全称量词消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到：(x)(z)( P(a, x, f(x) Q(z, b)R(x)消去(z)，同理使用g(x)代替之，这样得到：(x) ( P(a, x, f(x) Q(g(x), b)R(x)则，略去全称变量

27、，原式的Skolem标准形为： P(a, x, f(x) Q(g(x), b)R(x) 谓词归结子句形v子句与子句集子句与子句集 文字：不含任何连接词的谓词公式。 子句：一些文字的析取（谓词的和）。 子句集S的求取： G SKOLEM标准形 消去存在变量 以“，”取代“”，并表示为集合形式 。谓词归结子句形v G是不可满足的是不可满足的 S是不可满足的是不可满足的 G与S不等价，但在不可满足的意义下是一致的。 定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的 S是不可满足的。 注意注意：G真不一定S真，而S真必有G真。即： S G例：G = ( x)P(x), S = P(a).

28、令G和S 的解释I如下：D=1, 2 a: 1, P(1): F, P(2): T显然I满足G，但I有假S。谓词归结子句形vG = GG = G1 1 G G2 2 G G3 3 G Gn n 的子句形的子句形 G的子句集可以分解成几个单独处理。 有 SG = S1 U S2 U S3 U U Sn则SG 与 S1 U S2 U S3 U U Sn在不可满足的意义上是一致的。即SG 不可满足 S1 U S2 U S3 U U Sn不可满足求取子句集例(1)例：对所有的例：对所有的x,y,z来说，如果来说，如果y是是x的父亲，的父亲，z又是又是y的父亲，则的父亲，则z是是x的祖父。又知每个人都有

29、父亲，的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：解：这里我们首先引入谓词：vP(x, y) 表示表示x是是y的父亲的父亲vQ(x, y) 表示表示x是是y的祖父的祖父vANS(x) 表示问题的解答表示问题的解答求取子句集例(2)对于第一个条件，对于第一个条件，“如果如果x是是y 的父亲，的父亲， y又是又是z 的父亲，则的父亲，则x是是z 的的祖父祖父”，一阶逻辑表达式如下：，一阶逻辑表达式如下：A1：( x)( y)( z)(P(x, y

30、)P(y, z)Q(x, z)S A1：P(x ,y)P(y, z)Q(x, z)对于第二个条件：对于第二个条件：“每个人都有父亲每个人都有父亲”，一阶逻辑表达式：，一阶逻辑表达式：A2：( y)( x)P(x, y)S A2：P(f(y), y)对于结论：某个人是它的祖父对于结论：某个人是它的祖父B：( x)( y)Q(x, y)否定后得到子句：否定后得到子句： （ ( x)( y)Q(x, y)） ANS(x)SB：Q(x, y)ANS(x)则得到的相应的子句集为：则得到的相应的子句集为： S A1，S A2，SB 第3讲 谓词逻辑与归结原理v概述概述v命题逻辑的归结法命题逻辑的归结法v谓

31、词归结子句形谓词归结子句形v归结原理归结原理v归结过程的策略控制归结过程的策略控制vHerbrand定理定理归结原理v归结原理正确性的根本在于，找到矛归结原理正确性的根本在于，找到矛盾可以肯定不真。盾可以肯定不真。v方法：方法： 和命题逻辑一样。 但由于有函数，所以要考虑合一和置换。 置换：是形为：是形为t1/v1,tn/vn的一个有限集。的一个有限集。其中，其中，vi是变量，而是变量，而ti是不同于是不同于vi的项（常量、变量、函数）的项（常量、变量、函数）且且vivj，（，（ij),i,j=1,2,n例如，例如，a/x,b/y,f(x)/z,f(z)/x,y/z都是置换。都是置换。：不含任

32、何元素的置换。：不含任何元素的置换。令置换令置换 =t1/v1,t2/v2,tn/vn E是一阶谓词是一阶谓词 作用于作用于E，就是将，就是将E中出现的变量中出现的变量vi均以均以ti代入（代入（i=1,2,n)，以，以E 表示结果，并称为表示结果，并称为E的一个的一个。 作用于项作用于项t，是将，是将t中出现的变量中出现的变量vi以以ti代入代入(i=1,n)，结果以，结果以表示。表示。 例：=a/x, f(b)/y, u/z E=P(x, y, z) t = g(x, y) 那么 E = P(a, f(b), u) t=g(a, f(b)置换的合成v 设设 t1/x1, t2/x2, ,

33、tn/xn， u1/y1, u2/y2, , um/ym，是两个置换。，是两个置换。 则则 与与 的合成也是一个置换，记作的合成也是一个置换，记作 。它是从集合。它是从集合t1 /x1, t2 /x2, , tn /xn, u1/y1, u2/y2, , um/ym 中删去以下两种元素：中删去以下两种元素： 当yix1,x2, , xn时，删去ui/yi (i = 1, 2, , m) 当ti=xi时，删去ti/xi (i = 1, 2, , n);最后剩下的元素所构成的集合。最后剩下的元素所构成的集合。 合成即是对合成即是对ti先做先做 置换然后再做置换然后再做 置换，置换置换，置换xi置换

34、的合成v例：例：设：设： f(y)/x, z/y， a/x, b/y, y/z，求，求 与与 的合成的合成。解：先求出集合解：先求出集合f(b/y)/x, (y/z)/y, a/x, b/y, y/zf(b)/x, y/y, a/x, b/y, y/z其中，其中，f(b)/x中的中的f(b)是置换是置换 作用于作用于f(y)的结果；的结果；y/y中的中的y是置换是置换 作用于作用于z的结果。在该集合中，的结果。在该集合中，y/y满足定义中的条件满足定义中的条件i，需要删除，需要删除；a/x，b/y满足定义中的条件满足定义中的条件ii，也需要删除。最后得，也需要删除。最后得 f(b)/x，y/z

35、合一v 合一可以简单地理解为合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致寻找相对变量的置换，使两个谓词公式一致”。v 定义：设有公式集定义：设有公式集FF1，F2，Fn，若存在一个置换，若存在一个置换 ，可使，可使F1 F2 = Fn ，则称，则称 是是F的一个合一。同时称的一个合一。同时称F1，F2，. ，Fn是可合一的。是可合一的。v 例：例：设有公式集设有公式集FP(x, y, f(y), P(a,g(x),z)，则，则 a/x, g(a)/y, f(g(a)/z是它的是它的一个合一。一个合一。注意：一般说来，一个公式集的合一不是唯一的。注意：一般说来，一个公式集的合一不

36、是唯一的。表达式集合表达式集合 F1，F2，Fn的合一的合一 称为是最一般合一（称为是最一般合一（most general unigier， mgu)当且仅当对此集合的每一个合一当且仅当对此集合的每一个合一 ，都存在置换，都存在置换 ：使得：使得 = 。归结原理v 归结的注意事项：归结的注意事项：1.谓词的一致性，P()与Q()， 不可以2.常量的一致性，P(a, )与P(b,.)， 不可以 变量，P(a, .)与P(x, )， 可以3.变量与函数，P(a, x, .)与P(x, f(x), )，不可以；4.是不能同时消去两个互补对，PQ与PQ的空，不可以5.先进行内部简化（置换、合并） 归结

37、原理v归结的过程归结的过程写出谓词关系公式 用反演法写出谓词表达式 SKOLEM标准形 子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 得证归结原理的完备性：归结式v 定义：归结式定义：归结式：设：设C1，C2是两个无公共变量的两个子句，是两个无公共变量的两个子句，L1、L2分别是分别是C1、C2中的两个文字。如果中的两个文字。如果L1、L2有最有最一般合一一般合一 ，则子句，则子句v (C1 - L1 ) (C2 - L2 ) v 称为称为C1和和C2的二元归结式，的二元归结式， L1和和L2称为归结文字。称为归结文字。v 例如：例如： C1P(x) Q(x)

38、, CQ(x), C2 2 = = P(a) R(x)R(x)。将。将C C2 2中的中的x x改为改为y y。取。取L L1 1=P(x)=P(x)，L L2 2= =P(a), P(a), = a/x，于是，于是(C1 - L1 ) (C2 - L2 ) Q(a) R(y).R(y).归结原理的完备性v设设S是子句集，从是子句集，从S推出子句推出子句C的一个演绎是如下的一个演绎是如下一个有限子句序列：一个有限子句序列：vC1，C2，Ckv其中其中Ci或者是或者是S中的子句，或者是中的子句，或者是Cj和和Cr的归结式的归结式(ji, r 完备 名词解释：归类：设有两个子句C和D，若有置换使得

39、C D成立，则称子句C把子句D归类。由于小的可以代表大的，所以小的吃掉大的了。 若对S使用归结推理过程中，当归结式Cj是重言式（永真式）和Cj被S中子句和子句集的归结式Ci(ij)所归类时，便将Cj删除。这样的推理过程便称做使用了删除策略的归结过程。 主要思想：归结过程在寻找可归结子句时，子句集中的子句越多，需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉，就会缩小搜索范围，减少比较次数，从而提高归结效率。删除策略对阻止不必要的归结式的产生来缩短归结过程是有效的。然而要在归结式Cj产生后方能判别它是否可被删除，这部分计算量是要花费的，只是节省了被删除的子句又生成的归结式。尽管使

40、用删除策略的归结，少做了归结但不影响产生空子句，就是说删除策略的归结推理是完备的。控制策略的方法(2)采用支撑集完备 支撑集：设有不可满足子句集支撑集：设有不可满足子句集S的子集的子集T，如果，如果S-T是可满足的，则是可满足的，则T是支持集是支持集。 采用支撑集策略时，从开始到得到采用支撑集策略时，从开始到得到的整个归结过程中，只选取不同时属于的整个归结过程中，只选取不同时属于S-T的子句，在其间进行归结。就是说，至少有一个子句来自于支撑集的子句，在其间进行归结。就是说，至少有一个子句来自于支撑集T或由或由T导出的归结式。导出的归结式。 例如：例如：A1A2A3B中的中的B可以作为支撑集使用

41、。要求每一次参加归结的亲可以作为支撑集使用。要求每一次参加归结的亲本子句中，只要应该有一个是有目标公式的否定（本子句中，只要应该有一个是有目标公式的否定（B）所得到的子句或者它）所得到的子句或者它们的后裔。们的后裔。v 支撑集策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用支支撑集策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非，即容易找到的支撑集是目标子句的非，即SB。 ST可满足支撑集示意图控制策略的方法(3

42、)语义归结 完备 语义归结策略是将子句S按照一定的语义分成两部分，约定每部分内的子句间不允许作归结。同时还引入了文字次序，约定归结时其中的一个子句的被归结文字只能是该子句中“最大”的文字。 语义归结策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法，并根据其含义将子句集两个部分中的子句进行排序。 控制策略的方法(4)线性归结 完备 线性归结策略首先从子句集中选取一个称作顶子句的子句C0开始作归结。归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(j完备 单元归结

43、策略要求在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，词中方法可以简单地削去另一个非单子句中的一个因子，使其长度减少，构成简单化，归结效率较高。 初始子句集中没有单元子句时，单元归结策略无效。所以说“反之不成立”，即此问题不能采用单元归结策略。控制策略的方法(6)输入归结 =完备 与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。可以减少不必要的归结次数。 如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。简单的例

44、子，归结结束时，即最后一个归结式为空子句的条件是，参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。 第3讲 谓词逻辑与归结原理v概述概述v命题逻辑的归结法命题逻辑的归结法v谓词归结子句形谓词归结子句形v归结原理归结原理v归结过程的策略控制归结过程的策略控制vHerbrand定理定理Herbrand定理v问题：问题：一阶逻辑公式的永真性（一阶逻辑公式的永真性（永假性）的判定是否能在永假性）的判定是否能在有限步内完成有限步内完成？Herbrand定理v19361936年图灵年图灵(Turing)(Turing)和邱吉和邱吉(Church)(Church

45、)互相独立互相独立地证明了：地证明了： “没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（或永假）的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。” Herbrand定理vHerbrand的思想的思想 定义：公式G永真：对于G的所有解释，G都为真。 思想：寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且算法在有限步内停止。 Herbrand定理vH域域vH解释解释v语义树语义树v结论：结论：Herbrand定理定理Herbra

46、nd定理vH域域vH解释解释v语义树语义树v结论：结论：Herbrand定理定理Herbrand定理（H域）v基本方法：基本方法： 因为量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限、不可数的 。 简化讨论域。建立一个比较简单、特殊的域，使得只要在这个论域上，该公式是不可满足的。 此域称为H域。),.,(11niittfHHD域H域H域与D域关系示意图H域例题v 设子句集设子句集S = P(x), Q(S = P(x), Q(y,fy,f( (z,bz,b),R(a),R(a)，求，求H H域域v 解：解：H H0 0 a, ba, b为子句集中出现的常量为子句集中出现的常量

47、H H1 1 a, b, f(a, b, f(a,ba,b), f(), f(a,aa,a), f(), f(b,ab,a), f(), f(b,bb,b)H H2 2 a, b, f( a, b, f(a,ba,b), f(), f(a,aa,a), f(), f(b,ab,a), f(), f(b,bb,b) )，f(f(a,fa,f( (a,ba,b), f(), f(a,fa,f( (a,aa,a), f(a, f(), f(a, f(b,ab,a), f(a, f(), f(a, f(b,bb,b),),f(f(b,fb,f( (a,ba,b), f(), f(b,fb,f( (a,

48、aa,a), f(b, f(), f(b, f(b,ab,a), f(), f(b,fb,f( (b,bb,b),),f(f(f(f(a,ba,b),f(),f(a,ba,b), f(f(), f(f(a,ba,b),f(),f(a,aa,a), f(f(), f(f(a,ba,b), f(), f(b,ab,a), f(f(), f(f(a,ba,b), f(), f(b,bb,b),),f(f(f(f(a,aa,a),f(),f(a,ba,b), f(f(), f(f(a,aa,a),f(),f(a,aa,a), f(f(), f(f(a,aa,a), f(), f(b,ab,a), f(

49、f(), f(f(a,aa,a), f(), f(b,bb,b),),f(f(f(f(b,ab,a),f(),f(a,ba,b), f(f(), f(f(b,ab,a),f(),f(a,aa,a), f(f(), f(f(b,ab,a), f(), f(b,ab,a), f(f(), f(f(b,ab,a), f(), f(b,bb,b),),f(f(f(f(b,bb,b),f(),f(a,ba,b), f(f(), f(f(b,bb,b),f(),f(a,aa,a), f(f(), f(f(b,bb,b), f(), f(b,ab,a), f(f(), f(f(b,bb,b), f(), f

50、(b,bb,b)vvH H 称为称为S的的Herbrand域，简称域，简称H域。域。Herbrand定理（H域）v几个基本概念几个基本概念 f（tn）：f为子句集S中的所有函数变量。t1, t2, tn为S的H域的元素。通过它们来讨论永真性。 原子集A：谓词套上H域的元素组成的集合。如A = 所有形如 P(t1, t2, tn)的元素即把H中的东西填到S的谓词里去。S中的谓词是有限的，H是可数的，因此，A也是可数的。原子集例题上例题的原子集为：上例题的原子集为：vA = A = P(a), Q(a, a), R(a), P(b), Q(b, a), P(a), Q(a, a), R(a), P

51、(b), Q(b, a), Q(b, b), Q(a, b), R(b), P( f( Q(b, b), Q(a, b), R(b), P( f(a,ba,b), ), Q(f(a, b), f(a, b), R(f(a, b), Q(f(a, b), f(a, b), R(f(a, b), P(f( P(f(a,aa,a), P(f(), P(f(b,ab,a), ), P(f( P(f(b,bb,b),),) ) 一旦原子集内真值确定好（规定好），则一旦原子集内真值确定好（规定好），则S S在在H H上上的真值可确定。成为可数问题。的真值可确定。成为可数问题。Herbrand定理vH域域v

52、H解释解释v语义树语义树v结论：结论：Herbrand定理定理Herbrand定理（H解释）v解解释释I I：谓词公式谓词公式G G在论域在论域D D上任何一组上任何一组真值的指定称为一个解释。真值的指定称为一个解释。vH H解释：子句集解释：子句集S S在的在的H H域上的解释称为域上的解释称为H H解释。解释。 问题：问题： 对于所有的解释，全是假才可判定。因为所有解释代表了所有的情况，如可穷举，问题便可解决 。Herbrand定理：H解释v定义定义：设：设S是子句集，是子句集，H是是S的的H域，域，I是是S在在H上上的一个解释。称的一个解释。称I为为S的一个的一个H解释，如果解释，如果I

53、满足满足以下条件：以下条件：1.I映射映射S中的每个常量符号到自身；中的每个常量符号到自身；2.若若f是是S中中n元函数符号，元函数符号，h1， hn是是H中元素中元素，则，则I指定映射指定映射(h1， hn)f (h1， hn); 由定义可以看出，由定义可以看出，S的的H解释对于解释对于S中中n原谓词符原谓词符号的指定没有约束。号的指定没有约束。Herbrand定理：H解释v设设A=A1, Sn, 是是S的原子集。于是的原子集。于是S的一个的一个H解释解释I可方便地表示为如下一个集合：可方便地表示为如下一个集合：vI=m1, m2, , mn, v其中其中FIA,TIA,指定为被当指定为被当

54、iiiiiAAmHerbrand定理：H解释v 例例 S=P(x) Q(x), R(f(y),于是，于是，v S的的H域域=a, f(a), f(f(a), v S的原子集的原子集A=P(a), Q(a), R(a), P(f(a), Q(f(a), R(f(a), v 下面的解释就是下面的解释就是S的的H解释：解释：v I1=P(a), Q(a), R(a), P(f(a), Q(f(a), R(f(a), v I1=P(a), Q(a), R(a), P(f(a), Q(f(a), R(f(a), Herbrand定理：H解释v当然，子句集当然，子句集S的一个解释不是必须定义在的一个解释不

55、是必须定义在H域上域上，即使定义在，即使定义在H域上，也不一定是一个域上，也不一定是一个H解释：解释：v例如例如SP(x), Q(y, f(y,a),令令S的一个解释的一个解释I如下：如下：vD 1，2,a/2, f(1,1)/1, f(1,2)/2, f(2,1)/2, f(2,2)/1, P(1)/T, P(2)/F, Q(1,1)/F, Q(1,2)/F, Q(2,1)/F, Q(2,2)/T.Herbrand定理（H解释）v如下三个定理保证了归结法的正确性：如下三个定理保证了归结法的正确性： 定理定理1：设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I = T，必有

56、S|I* = T。 定理定理2：子句集S是不可满足的，当且仅当S 在所有的H解释下为假。 定理定理3：子句集S是不可满足的，当且仅当对每一个解释I下，至少有S的某个子句的某个基例为假。 Herbrand定理（H解释）v基例基例S中某子句中所有变元符号均以S的H域中的元素代入时，所得的基子句C称为C的一个基例。v一般来说，一般来说，D D是无穷不可列的，因此，子句集是无穷不可列的，因此，子句集S S也也是无穷不可列的。但是无穷不可列的。但S S确定后确定后H H是无穷可列的。不是无穷可列的。不过在过在H H上证明上证明S S的不可满足性仍然是不可能的。的不可满足性仍然是不可能的。v解决问题的方法

57、：解决问题的方法：语义树语义树Herbrand定理vH域域vH解释解释v语义树语义树v结论：结论：Herbrand定理定理Herbrand定理（语义树）v构成方法构成方法 原子集中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上（可不完全画完） 。v特点特点 一般情况H是可数集，S的语义树是无限树。 Herbrand定理（语义树）v 设设S是子句集，是子句集，A是是S的原子集。关于的原子集。关于S的语义树是一个的语义树是一个向下生长的树向下生长的树T，在其中每一节上都以如下方式附着，在其中每一节上都以如下方式附着A中一些原子或原子否定的有限集合：中一些原子或原子否定的有限集合

58、：v （1）对于每一个节点）对于每一个节点N，只能向下引出有限的直接的，只能向下引出有限的直接的节节L1, L2, , Ln。设。设Qi是附着在是附着在Li上所有文字的合取上所有文字的合取i=1, , n.则则Q1 Q2 Qn是一个恒真的命题公式。是一个恒真的命题公式。v （2）对每一个节点）对每一个节点N，设，设I(N)是树是树T由向下到节点由向下到节点N并并包含包含N的一个分枝的所有节上附着文字的并集，则的一个分枝的所有节上附着文字的并集，则I(N)不包含任意的互补对。不包含任意的互补对。 Herbrand定理（语义树）v设设A=A1, An, 是子句集是子句集S的原子集。的原子集。S的一个的一个语义树是完全的，当且仅当对于语义树种每一个语义树是完全的，当且仅当对于语义树种每一个尖端节点尖端节点N（亦即从（亦即从N不再生出节的那种节点），不再生出节的那种节点），都有都有I(N)包含着包含着Ai或或Ai。vS 的任一解释都对应的任一解释都对应S的完全语义树中的一个分枝的完全语义树中的一个分枝。v子句集子句集S的一个完全语义树对应的一个完全语义树对应S的所有解释。的所有解释。N0P(a)N12Q(a)P(f(a)N24N31N38无限语义树N11P(a)Q(a