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

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

发布时间:2019-07-21 23:10 来源:未知 编辑:admin

  人工智能原理教案02章归结推理方法2.3谓词逻辑归结法基(精)_其它_职业教育_教育专区。人工智能原理教案02章归结推理方法2.3谓词逻辑归结法基(精)

  2.3 谓词逻辑归结法基础 由于谓词逻辑与命题逻辑不同,有量词、变量和函数,所以 在生成子句集之前要对逻辑公式做处理,具体的说就是要将其转 化为 Skolem 标准形,然后在子句集的基础上再进行归结,虽然基 本的归结的基本方法都相同,但是其过程较之命题公式的归结过 程要复杂得多。 本节针对谓词逻辑归结法介绍了 Skolem 标准形、子句集等一 些必要的概念和定理。 2.3.1 Skolem 标准形 Skolem 标准形的定义: 前束范式中消去所有的存在量词,则称这种形式的谓词公式 为 Skolem 标准形,任何一个谓词公式都可以化为与之对应的 Skolem 标准形。但是,Skolem 标准形不唯一。 前束范式:A 是一个前束范式,如果 A 中的一切量词都位于 该公式的最左边(不含否定词),且这些量词的辖域都延伸到公 式的末端。 Skolem 标准形的转化过程为,依据约束变量换名规则,首先 把公式变型为前束范式,然后依照量词消去原则消去或者略去所 有量词。具体步骤如下: 将谓词公式 G 转换成为前束范式 前束范式的形式为: (Q1x1(Q2x2…(QnxnM(x1,x2,…,xn 即: 把所有的量词都提到前面去。 注意:由于所有的量词的辖域都延伸到公式的末端,即,最 左边量词将约束表达式中的所有同名变量。所以将量词提到公式 最前端时存在约束变量换名问题。要严守规则。 约束变量换名规则: (Qx M(x) (Qx M(x,z) (Qy ) M(y) (Qy ) M(y,z) 量词否定等值式: ~( x M(x) ~( x M(x) ( y ) ~ M(y) ( y ) ~ M(y) 量词分配等值式: ( x ( P(x) ∧Q(x) ( x ( P(x) ∨ Q(x) ( x P(x) ∧ ( x Q(x) ( x P(x) ∨ ( x Q(x) 消去量词等值式:设个体域为有穷集合(a1, a2, …an) ( x P(x) ( x P(x) P(a1) ∧ P(a2) ∧ …∧ P(an) P(a1) ∨ P(a2) ∨ … ∨ P(an) 量词辖域收缩与扩张等值式: ( x ( P (x ) ∨ Q ( x P(x) ∨ Q ( x ( P(x) ∧ Q ( x ( P(x) → Q ( x ( Q → P(x) ( x ( P(x) ∨ Q ( x ( P(x) ∧ Q ( x ( P(x) → Q ( x ( Q → P(x) 消去量词 量词消去原则: ( x P(x) ∧ Q ( x P(x) → Q Q → ( x P(x) ( x P (x ) ∨ Q ( x P (x ) ∧ Q ( x P(x) → Q Q → ( x P(x) 1 消去存在量词 ,即,将该量词约束的变量用任意常量 (a, b 等)、或全称变量的函数(f(x, g(y 等代替。如果存在量词左 边没有任何全称量词,则只将其改写成为常量;如果是左边有全 程量词的存在量词,消去时该变量改写成为全程量词的函数。 2 略去全程量词 ,简单地省略掉该量词。 Skolem 定理: 谓词逻辑的任意公式都可以化为与之等价的前束范式,但其 前束范式不唯一。 注意:公式 G 的 SKOLEM 标准形同 G 并不等值。 例题 2-2 将下式化为 Skolem 标准形: ~( x( yP(a, x, y →( x(~( yQ(y, b→R(x 解: 第一步,消去→号,得: ~(~( x( yP(a, x, y ∨( x (~~( yQ(y, b∨R(x 第二步,~深入到量词内部,得: ( x( yP(a, x, y∧~( x (( yQ(y, b∨R(x = ( x( yP(a, x, y ∧( x (( y~Q(y, b∧~R(x 第三步,全称量词左移,(利用分配律),得 ( x( ( yP(a, x, y ∧( y(~Q(y, b∧~R(x 第四步,变元易名,存在量词左移,直至所有的量词移到前 面,得: ( x( ( yP(a, x, y ∧( y(~Q(y, b∧~R(x = ( x ( ( yP(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 不可满足 由上面的定理,我们对 SG 的讨论,可以用较为简单的 S1 ∪ S2 ∪ S3 ∪ …∪ Sn 来代替。为方便起见,也称 S1 ∪ S2 ∪ S3 ∪ …∪ Sn 为 G 的子句形,即: SG=S1 ∪ S2 ∪ S3 ∪ …∪ Sn。根据以上定理可对一个谓词 表达式分而治之,化整为零,大大减少了计算复杂度。 例 2-3 对所有的 x,y,z 来说,如果 y 是 x 的父亲,z 又是 y 的父亲, 则 z 是 x 的祖父。又知每个人都有父亲,试问对某个人来说谁是 它的祖父? 用一阶逻辑表示这个问题,并建立子句集。 解: 这里我们首先引入谓词: P(x, y 表示 x 是 y 的父亲 Q(x, y 表示 x 是 y 的祖父 ANS(x 表示问题的解答 于是有: 对于第一个条件,如果 y 是 x 的父亲,z 又是 y 的父亲,则 z 是 x 的祖父,一阶逻辑表达式如下: A1:( x( y( z(P(x, y∧P(y, z→Q(x, z 则把 A1 化为合取范式,进而化为 Skolem 标准形,表示如 下: S A1:~P(x ,y∨~P(y, z∨Q(x, z 对于第二个条件:每个人都有父亲,一阶逻辑表达式如 下: A2:( y( xP(x, y 化为 Skolem 标准形,表示如下: S A2:P(f(y, x 结论:某个人是它的祖父 B:( x( yQ(x, y 否定后得到子句: S~B:~Q(x, y∨ANS(x 则得到的相应的子句集为:{ S A1,S A2,S~B } 解毕。

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