您好、欢迎来到现金彩票网!
当前位置:刘伯温四肖中特料 > 推理子句 >

人工智能原理教案02章归结推理方法23谓词逻辑归结法基础

发布时间:2019-08-09 08:08 来源:未知 编辑:admin

  人工智能原理教案02章归结推理方法2.3谓词逻辑归结法基础_财会/金融考试_资格考试/认证_教育专区。2.3 谓词逻辑归结法基础 由于谓词逻辑与命题逻辑不同,有量词、变量和函数,所以在生成子句集之前要对逻辑 公式做处理,具体的说就是要将其转化为 Skolem 标准形,然后在子句集的基础上再进行归 结,

  2.3 谓词逻辑归结法基础 由于谓词逻辑与命题逻辑不同,有量词、变量和函数,所以在生成子句集之前要对逻辑 公式做处理,具体的说就是要将其转化为 Skolem 标准形,然后在子句集的基础上再进行归 结,虽然基本的归结的基本方法都相同,但是其过程较之命题公式的归结过程要复杂得多。 本节针对谓词逻辑归结法介绍了 Skolem 标准形、子句集等一些必要的概念和定理。 2.3.1 Skolem 标准形 Skolem 标准形的定义: 前束范式中消去所有的存在量词,则称这种形式的谓词公式为 Skolem 标准形,任何一 个谓词公式都可以化为与之对应的 Skolem 标准形。但是,Skolem 标准形不唯一。 前束范式:A 是一个前束范式,如果 A 中的一切量词都位于该公式的最左边(不含否定 词) ,且这些量词的辖域都延伸到公式的末端。 Skolem 标准形的转化过程为,依据约束变量换名规则,首先把公式变型为前束范式, 然后依照量词消去原则消去或者略去所有量词。具体步骤如下: 将谓词公式 G 转换成为前束范式 前束范式的形式为: (Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn) 即: 把所有的量词都提到前面去。 注意:由于所有的量词的辖域都延伸到公式的末端,即,最左边量词将约束表达式中的 所有同名变量。所以将量词提到公式最前端时存在约束变量换名问题。要严守规则。 约束变量换名规则: (Qx ) M(x) (Qy ) M(y) (Qx ) M(x,z) (Qy ) M(y,z) 量词否定等值式: ~(x ) M(x) (y ) ~ M(y) ~(x ) M(x) (y ) ~ M(y) 量词分配等值式: (x )( P(x) ∧Q(x)) (x ) P(x) ∧ (x ) Q(x) (x )( P(x) ∨ Q(x)) (x ) P(x) ∨ (x ) Q(x) 消去量词等值式:设个体域为有穷集合(a1, a2, …an) (x ) P(x) P(a1) ∧ P(a2) ∧ …∧ P(an) (x ) P(x) P(a1) ∨ P(a2) ∨ … ∨ P(an) 量词辖域收缩与扩张等值式: ( x )( P(x) ∨ Q) ( x ) P(x) ∨ Q (x )( P(x) ∧ Q) ( x ) P(x) ∧ Q (x )( P(x) → Q) (x ) P(x) → Q (x )( Q → P(x) ) Q → (x ) P(x) (x )( P(x) ∨ Q) (x ) P(x) ∨ Q (x )( P(x) ∧ Q) (x ) P(x) ∧ Q (x )( P(x) → Q) (x ) P(x) → Q (x )( Q → P(x) ) Q → (x ) P(x) 消去量词 量词消去原则: 1) 消去存在量词,即,将该量词约束的变量用任意常量(a, b 等) 、或全称变量的函 数(f(x), g(y)等)代替。如果存在量词左边没有任何全称量词,则只将其改写成为常量;如果是 左边有全程量词的存在量词,消去时该变量改写成为全程量词的函数。 2) 略去全程量词,简单地省略掉该量词。 Skolem 定理: 谓词逻辑的任意公式都可以化为与之等价的前束范式,但其前束范式不唯一。 注意:公式 G 的 SKOLEM 标准形同 G 并不等值。 例题 2-2 将下式化为 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)) = (x)(y)P(a, x, y) ∧(x) ((y)~Q(y, b)∧~R(x)) 第三步,全称量词左移, (利用分配律) ,得 (x)( (y)P(a, x, y) ∧(y)(~Q(y, b)∧~R(x))) 第四步,变元易名,存在量词左移,直至所有的量词移到前面,得: (x)( (y)P(a, x, y) ∧(y)(~Q(y, b)∧~R(x))) = (x) ( (y)P(a, x, y) ∧(z)(~Q(z, b)∧~R(x))) = (x) (y) (z) (P(a, x, y) ∧~Q(z, b)∧~R(x)) 由此得到前述范式 第五步,消去(存在量词) ,略去全称量词 消去(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)) 则,略去全称变量,原式的 Skolem 标准形为: P(a, x, f(x)) ∧~Q(g(x), b)∧~R(x) 2.3.2 子句集 文字:不含任何连接词的谓词公式。 子句:一些文字的析取(谓词的和) 。 子句集:所有子句的集合 对于任一个公式 G,都可以通过 Skolem 标准形,标准化建立起一个子句集与之相对应。因 为子句不过是一些文字的析取,是一种比较简单的形式,所以对 G 的讨论就用对子句集 S 的讨论来代替,以便容易处理。 子句集 S 可由下面的步骤求取: 1. 谓词公式 G 转换成前束范式 2. 消去前束范式中的存在变量,略去其中的任意变量,生成 SKOLEM 标准形 3. 将 SKOLEM 标准形中的各个子句提出,表示为集合形式 教师提示:为了简单起见,子句集生成可以理解为是用,取代 SKOLEM 标准形中的 Λ ,并表示为集合形式 。 注意:SKOLEM 标准形必须满足合取范式的条件。即,在生成子句集之前逻辑表达式必 须是各谓词表达式或谓词或表达式的与。 定理 谓词表达式 G 是不可满足的当且仅当 其子句集 S 是不可满足的 公式 G 与其子句集 S 并不等值,但它们在不可满足的意义下是一致的。因此如果要证明 A1 ∧A2∧A3→B,只需证明 G= A1∧A2∧A3∧~B 的子句集是不可满足的,这也正是引入子 句集的目的。 注意:公式 G 和子句集 S 虽然不等值,但是它们的之间一般逻辑关系可以简单的说明 为:G 真不一定 S 真,而 S 真必有 G 真,即,S G。在生成 SKOLEM 标准形时将存在量词用 常量或其他变量的函数代替,使得变量讨论的论域发生了变化,即论域变小了。所以 G 不 能保证 S 真。 定理的推广 对于形如 G = G1Λ G2Λ G3Λ …Λ Gn 的谓词公式, G 的子句集的求取过程可以分解 成几个部分单独处理。如果 Gi 的子句集为 Si,则 有 S = S1 ∪ S2 ∪ S3 ∪ …∪ Sn,虽然 G 的子句集不为 S,但是可以证明: SG 与 S1 ∪ S2 ∪ S3 ∪ …∪Sn 在不可满足的意义上是一致的。 即 SG 不可满足 S1 ∪ S2 ∪S3 ∪ …∪ Sn 不可满足

http://mojdzwonek.com/tuiliziju/492.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有