《{管理信息化人工智能}人工智能谓词逻辑》由会员分享，可在线阅读，更多相关《{管理信息化人工智能}人工智能谓词逻辑（43页珍藏版）》请在金锄头文库上搜索。
1、谓词逻辑基础,一阶逻辑 基本概念 个体词：表示主语的词 谓词：刻画个体性质或个体之间关系的词 量词：表示数量的词,小王是个工程师。 8是个自然数。 我去买花。 小丽和小华是朋友。 其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。,谓词逻辑基础,谓词逻辑基础,例如：（1）所有的人都是要死的。 （2） 有的人活到一百岁以上。 在个体域D为人类集合时，可符号化
2、为： （1）xP(x)，其中P(x)表示x是要死的。 （2）x Q(x), 其中Q(x)表示x活到一百岁以上。 在个体域D是全总个体域时， 引入特殊谓词R(x)表示x是人，可符号化为： （1）x（R(x) P(x)）, 其中，R(x)表示x是人；P(x)表示x是要死的。 （2）x（R(x) Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。,一阶逻辑 公式及其解释 个体常量：a,b,c 个体变量：x,y,z 谓词符号：P,Q,R 量词符号： ,谓词逻辑基础,量词否定等值式： ( x ） P（x） （ y ） P（y） ( x ） P（x） （ y ） P（y） 量词分配等值
3、式： ( x ）( P（x） Q（x）) ( x ） P（x） ( x ） Q（x） ( x ）( P（x） Q（x）) ( x ） P（x） ( x ） Q（x） 消去量词等值式：设个体域为有穷集合（a1, a2, an） ( x ） P（x） P（ a1 ） P（ a2 ） P（ an ） ( x ）P（x） P（ a1 ） P（ a2 ） P（ an ）,谓词逻辑基础,量词辖域收缩与扩张等值式： ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）(Q P（x）
4、) 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标准形 前束范式 定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。,谓词逻辑归结原理,即： 把所有的量词都提到前面去，然后消掉所有量词 (Q1x1)(Q2x2)(Qnxn)M(x1,x2,xn) 约束变项换名规则： (Qx ） M（x
5、） （Qy ） M（y） (Qx ） M（x,z） （Qy ） M（y,z）,谓词逻辑归结原理, 量词消去原则： 消去存在量词“”，略去全程量词“”。 注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。,谓词逻辑归结原理, Skolem定理： 谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。 SKOLEM标准形定义： 消去量词后的谓词公式。 注意：谓词公式G的SKOLEM标准形同G并不等值。,谓词逻辑归结原理,例：将下式化为Skolem标准形：,(x)(y)P(a, x, y) (x)(y)Q(y, b)R(x) 解：第一步，消去号，
6、得： (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) (u) ( v)(Q(v, b) R(u) 第四步，存在量词左移，直至所有的量词移到前面，(x) (y) (u) ( v) (P(a, x, y) (Q(v, b) R(u) 由此得到前述范式,第五步，消去“”（存在量词），略去“”全称量词 消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到： (x)(u)(v) (P(a, x, f(x
7、) Q(v, b)R(u) 消去(u)，同理使用g(x)代替之，这样得到： (x) (v) ( P(a, x, f(x) Q(v, b) R(g(x) 则，略去全称变量，原式的Skolem标准形为： P(a, x, f(x) Q(v, b) R(g(x),子句与子句集 文字：不含任何连接词的谓词公式。 子句：一些文字的析取（谓词的和）。 子句集S的求取： G SKOLEM标准形 消去存在变量 以“，”取代“”，并表示为集合形式 。,谓词逻辑归结原理,G是不可满足的 S是不可满足的 G与S不等价，但在不可满足得意义下是一致的。 定理： 若G是给定的公式，而S是相应的子句集，则G是不可满足的 S是
8、不可满足的。 注意：G真不一定S真，而S真必有G真。 即： S = G,谓词逻辑归结原理,G = G1 G2 G3 Gn 的子句形 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不可满足,3.3 谓词逻辑归结原理,例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？ 求：用一阶逻辑表示这个问题，并建立子句集。 解：这里我们首先引入谓词： P(
9、x, y) 表示x是y的父亲 Q(x, y) 表示x是y的祖父 ANS(x) 表示问题的解答,谓词逻辑归结原理,对于第一个条件，“如果x是y 的父亲， y又是z 的父亲，则x是z 的祖父”，一阶逻辑表达式如下： A1：(x)(y)(z)(P(x, y)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
10、)ANS(x) 则得到的相应的子句集为： S A1，S A2，SB ,谓词逻辑归结原理,归结原理正确性的根本在于，找到矛盾可以肯定不真。 方法： 和命题逻辑一样。 但由于有函数，所以要考虑合一和置换。,谓词逻辑归结原理,置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。 定义： 置换是形如t1/x1, t2/x2, , tn/xn的有限集合。其中，x1, x2, , xn是互不相同的变量，t1, t2, , tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。 例如 a/x，c/y，f(b)/z是一
11、个置换。 g(y)/x，f(x)/y不是一个置换，,谓词逻辑归结原理,置换,置换的合成,设t1/x1, t2/x2, , tn/xn， u1/y1, u2/y2, , un/yn，是两个置换。 则与的合成也是一个置换，记作。它是从集合 t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , un/yn 中删去以下两种元素： i. 当ti=xi时，删去ti/xi (i = 1, 2, , n); Ii. 当yix1,x2, , xn时，删去uj/yj (j = 1, 2, , m) 最后剩下的元素所构成的集合。 合成即是对ti先做置换然后再做置换，置换xi,谓词逻辑归结原理
12、,例： 设：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,谓词逻辑归结原理,合一,合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。 定义：设有公式集FF1，F2，Fn，若存在一个置换，可使F1F2= Fn，则称是
13、F的一个合一。同时称F1，F2，. ，Fn是可合一的。 例： 设有公式集FP(x, y, f(y), P(a,g(x),z)，则a/x, g(a)/y, f(g(a)/z是它的一个合一。 注意：一般说来，一个公式集的合一不是唯一的。,谓词逻辑归结原理,谓词逻辑归结原理,谓词逻辑归结原理,谓词逻辑归结原理,归结原理,归结的注意事项： 谓词的一致性，P()与Q()， 不可以 常量的一致性，P(a, )与P(b,.)， 不可以 变量，P(a, .)与P(x, )， 可以 变量与函数，P(a, x, .)与P(x, f(x), )，不可以； 是不能同时消去两个互补对，PQ与PQ的空，不可以 先进行内部
14、简化（置换、合并）,谓词逻辑归结原理,归结的过程 写出谓词关系公式 用反演法写出谓词表达式 SKOLEM标准形 子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 得证,谓词逻辑归结原理,例题“快乐学生”问题,假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。 解：先将问题用谓词表示如下： R1:“任何通过计算机考试并获奖的人都是快乐的” (x)(Pass(x, computer)Win(x, prize)Happy(x) R2:“任何肯学习或幸运的人都可以通过所有考
15、试” (x)(y)(Study(x)Lucky(x)Pass(x, y) R3:“张不肯学习但他是幸运的” Study(zhang)Lucky(zhang) R4:“任何幸运的人都能获奖” (x)(Luck(x)Win(x,prize) 结论：“张是快乐的”的否定 Happy(zhang),例题“快乐学生”问题,由R1及逻辑转换公式:PWH = （PW） H ，可得 (1)Pass(x, computer)Win(x, prize)Happy(x) 由R2： (2)Study(y)Pass(y,z) (3)Lucky(u)Pass(u,v) 由R3： (4)Study(zhang) (5)Lu
16、cky(zhang) 由R4： (6)Lucky(w)Win(w，prize) 由结论：(7)Happy(zhang)（结论的否定） (8)Pass(w, computer)Happy(w)Luck(w) (1)(6)，w/x (9)Pass(zhang, computer)Lucky(zhang) (8)(7)，zhang/w (10)Pass(zhang, computer) (9)(5) (11)Lucky(zhang) (10)(3)，zhang/u, computer/v (12) (11)(5),归结法的实质： 归结法是仅有一条推理规则的推理方法。 归结的过程是一个语义树倒塌的过程。 归结法的问题 子句中有等号或不等号时，完备性不成立。 Herbrand定理的不实用性引出了可实用的归结法。,谓词逻辑归结原理,归结过程的控制策略,要解决的问题： 归结方法的知识爆炸。 控制策略的目的 归结点尽量少 控制策略的原
