人工智能原理教案02章 归结推理方法2.2 命题逻辑的归结

第一篇：人工智能原理教案02章 归结推理方法2.2 命题逻辑的归结

2.2 命题逻辑的归结 2.2.1 命题逻辑基础

逻辑可分为经典逻辑和非经典逻辑，其中经典逻辑包括命题逻辑和谓词逻辑。归结原理是一种主要基于谓词（逻辑）知识表示的推理方法，而命题逻辑是谓词逻辑的基础。因此，在讨论谓词逻辑之前，先讨论命题逻辑的归结，便于内容上的理解。

本节中，将主要介绍命题逻辑的归结方法，以及有关的一些基础知识和重要概念，如数理逻辑基本公式变形、前束范式、子句集等。

描述事实、事物的状态、关系等性质的文字串，取值为真或假（表示是否成立）的句子称作命题。

命题：非真即假的简单陈述句

在命题逻辑里，单元命题是基本的单元或作为不可再分的原子。下面所列出的是一些基本的数理逻辑公理公式和一些有用的基本定义，如合取范式、子句集，这些公式和定义在归结法的推理过程中是必不可少的，也是归结法的基础，应该熟练掌握。

－数理逻辑的基本定义

下面所列的是一些数理逻辑中重要的定义，在后面的分析中要用到：

·合取式：p与q，记做p ∧ q

·析取式：p或q，记做p ∨ q

·蕴含式：如果p则q，记做p → q

·等价式：p当且仅当q，记做p

q

·若A无成假赋值，则称A为重言式或永真式；

·若A无成真赋值，则称A为矛盾式或永假式；

·若A至少有一个成真赋值，则称A为可满足的；

·析取范式：仅由有限个简单合取式组成的析取式

·合取范式：仅由有限个简单析取式组成的合取式

－数理逻辑的基本等值式

下面这些基本的等式在归结原理实施之前的公式转化过程中是非常重要的。只有将逻辑公式正确转换成为归结原理要求的范式，才能够保证归结的正常进行。

·交换律：p∨q

q ∨p ；

q ∧ p

p ∧ q

·结合律：(p∨q)∨ rp∨(q ∨r);

(p ∧ q)∧ rp ∧(q ∧ r)

·分配律： p∨(q ∧ r)

(p∨q)∧(p ∨r)；(p ∧ q)∨(p ∧ r)

p ∧(q ∨ r)

·双重否定律：p

·等幂律：p

～～p

p∨p；p p∧p

·摩根律: ～(p∨q)～ p ∧ ～ q ； ～ p ∨ ～ q

～(p ∧q)

·吸收律: p∨(p∧q)

p ；

p

p ∧(p∨q)

·同一律: p∨0

p ； p

p∧1

·零律：p∨1

p∧0 0

·排中律：p∨～p

·矛盾律：p∧～p 0

～ p∨q(p → q)∧(q → p)～ p → ～ q

～p～q

～p

·蕴含等值式：p → q

·等价等值式：pq

·假言易位式: p → q

·等价否定等值式：pq

·归谬论：(p → q)∧(p → ～q)

－合取范式

范式：范式是公式的标准形式，公式往往需要变换为同它等价的范式，以便对它们作一般性的处理。

合取范式：单元子句、单元子句的或（∨）的与（∧）。

如：P∧（P∨Q）∧（～P∨Q）

例：求取P ∧(Q → R)→ S 的合取范式

解： P ∧(Q → R)→ S

= ～（P∧(～Q∨R)）∨S

= ～P∨～(～Q∨R)∨S

= ～P∨(～～Q∧～R)∨S

= ～P∨(Q∧～R)∨S

= ～P∨S∨(Q∧～R)

=(～P∨S∨Q)∧(～P∨S∨～R)

注意：首先一定要将原有的命题公式整理、转换成为各个“或”语句的“与”，不然后续推导没有意义。转换是基于数理逻辑的基本等值公式进行的，“或”转换到“与”中。思路与代数学的提取公因式方法相似。

－子句集

命题公式的子句集S是合取范式形式下的子命题（元素）的集合。

子句集是合取范式中各个合取分量的集合，生成子句集的过程可以简单地理解为将命题公式的合取范式中的与符号“∧”，置换为逗号“，”。

上例转换的合取范式：(～P∨S∨Q)∧(～P∨S∨～R)

其子句集为

S = {～P∨S∨Q, ～P∨S∨～R}

又如，有命题公式：P∧（P∨Q）∧（～P∨Q）

其子句集 S：S = {P, P∨Q, ～P∨Q}

2.2.2 命题逻辑的归结

归结法推理的核心是求两个子句的归结式，因此需要先讨论归结式的定义和性质。

归结式的定义

设C1和C2是子句集中的任意两个子句，如果C1中的文字L1与C2中的文字L2互补，那么可从C1和C2中分别消去L1和L2，并将C1和C2中余下的部分按析取关系构成一个新子句C12，则称这一个过程为归结，称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。

例如：有子句：C1＝P∨C1'，C2＝～P∨C2'

存在互补对 P和～P，则可得归结式：C12 = C1'∨C2'

注意：C1ΛC2 → C12，反之不一定成立。

下面证明归结式是原两子句的逻辑推论，或者说任一使C1、C2为真的解释I下必有归结式C12也为真。

证明：

设I是使C1，C2为真的任一解释，若I下的P为真，从而～P为假，必有I下C2'为真，故C12为真。若不然，在I下P为假，从而I下C1'为真，故I下C12为真。于是C1∧C2为真。于是C1∧C2→R(C1,C2)成立。

反之不一定成立，因为存在一个使C1'∨C2'为真的解释I，不妨设C1'为真，C2'为假。若P为真，则～P∨C2'就为假了。因此反之不一定成立。由此可得归结式的性质。

归结式的性质：归结式C12 是亲本子句C12 和C12的逻辑结论。

命题逻辑的归结法证明过程

命题逻辑的归结过程也就是推理过程。推理是根据一定的准则由称为前提条件的一些判断导出称为结论的另一些判断的思维过程。命题逻辑的归结方法推理过程可以分为如下几个步骤：

1.建立待归结命题公式

首先根据反证法将所求证的问题转化成为命题公式，求证其是矛盾式（永假式）。

求取合取范式建立子句集归结

归结法是在子句集S的基础上通过归结推理规则得到的，归结过程的最基本单元是得到归结式的过程。从子句集S出发，对S的子句间使用归结推理规则，并将所得归结式仍放入到S中（注意：此过程使得子句集不断扩大，是造成计算爆炸的根本原因），进而再对新子句集使用归结推理规则。重复使用这些规则直到得到空子句•。这便说明S是不可满足的，从而与S所对应的定理是成立的。

归结步骤：

1)对子句集中的子句使用归结规则

2)归结式作为新子句加入子句集参加归结

3)归结式为空子句□ 为止。

（证明完毕）

得到空子句□，表示S是不可满足的（矛盾），故原命题成立。

例题2-1

证明公式：

(P → Q)→(～Q → ～P)证明：根据归结原理

将待证明公式转化成待归结命题公式：

(P → Q)∧～(～Q → ～P)

分别将公式前项化为合取范式：

P → Q ＝ ～P ∨ Q

结论求～后的后项化为合取范式：

～(～Q → ～P)＝ ～(Q∨～P)＝ ～Q ∧ P

两项合并后化为合取范式：

（～P ∨ Q）∧～Q ∧ P

则子句集为：

{ ～P∨Q，～Q，P}

对子句集中的子句进行归结可得：

1.～P∨Q

2.～Q

3.P

4.Q，（1，3归结）

5.e，（2，4归结）

由上可得原公式成立。

谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。

教师提示：命题逻辑基础是学习归结法的必要基础，应该在前序的课程中学习过。这里列出的只是一些简单的性质。如果大家对这些知识有什么疑惑的话，请参考数理逻辑的有关书籍。命题逻辑的归结法的逻辑基础是假言易位式和摩根律。

第二篇：人工智能原理教案02章 归结推理方法2.4 归结原理

2.4 归结原理

本节在上节的基础上，进一步具体介绍谓词逻辑的归结方法。谓词逻辑的归结法是以命题逻辑的归结法为基础，在Skolem标准性的子句集上，通过置换和合一进行归结的。

下面先介绍一些本节中用到的必要概念：

一阶逻辑：谓词中不再含有谓词的逻辑关系式。

个体词：表示主语的词

谓词：刻画个体性质或个体之间关系的词

量词：表示数量的词

个体常量：a,b,c

个体变量：x,y,z

谓词符号：P,Q,R

量词符号：，归结原理正确性的根本在于，如果在子句集中找到矛盾可以肯定命题是不可满足的。2.4.1 合一和置换

置换：置换可以简单的理解为是在一个谓词公式中用置换项去置换变量。

定义：

置换是形如{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}是一个置换。

{g(y)/x，f(x)/y}不是一个置换，原因是它在x和y之间出现了循环置换现象。置换的目的是要将某些变量用另外的变量、常量或函数取代，使其不在公式中出现。但在{g(y)/x，f(x)/y}中，它用g(y)置换x，用f(g(y))置换y，既没有消去x，也没有消去y。若改为{g(a)/x，f(x)/y}就可以了。

通常，置换用希腊字母θ、σ、α、λ来表示的。

定义：置换的合成

设θ＝{t1/x1, t2/x2, …, tn/xn}，λ＝{u1/y1, u2/y2, …, un/yn}，是两个置换。则θ与λ的合成也是一个置换，记作θ·λ。它是从集合 {t1·λ/x1, t2·l/x2, …, tn·λ/xn, u1/y1, u2/y2, …, un/yn}

即对ti先做λ置换然后再做θ置换，置换xi

中删去以下两种元素：

i.当tiλ＝xi时，删去tiλ/xi(i = 1, 2, …, n);

ii.当yi∈{x1,x2, …, xn}时，删去uj/yj(j = 1, 2, …, m)

最后剩下的元素所构成的集合。

例：

设θ＝{f(y)/x, z/y}，λ＝{a/x, b/y, y/z}，求θ与λ的合成。

解：

先求出集合

{f(b/y)/x,(y/z)/y, a/x, b/y, y/z}＝{f(b)/x, y/y, a/x, b/y, y/z}

其中，f(b)/x中的f(b)是置换l作用于f(y)的结果；y/y中的y是置换λ作用于z的结果。在该集合中，y/y满足定义中的条件i，需要删除；a/x，a/y满足定义中的条件ii，也需要删除。最后得

θ·λ＝{f(b)/x，y/z}

合一：合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。

定义：

设有公式集F＝{F1，F2，…，Fn}，若存在一个置换θ，可使F1θ＝F2θ＝…= Fnθ，则称θ是F的一个合一。同时称F1，F2，...，Fn是可合一的。例：

设有公式集F＝{P(x, y, f(y)), P(a,g(x),z)}，则λ＝{a/x, g(a)/y, f(g(a))/z}是它的一个合一。

注意：一般说来，一个公式集的合一不是唯一的。

定义：最一般合一

设σ是公式集F的一个合一，如果对F的任意一个合一θ都存在一个置换λ，使得θ＝σ·λ，则称σ是一个最一般合一（Most General Unifier，简记为mgu）

一个公式集的最一般合一是唯一的。若用最一般合一去置换那些可合一的谓词公式，可使它们变成完全一致的谓词公式。

归结原理方法与命题逻辑基本相同。但由于有变量与函数，所以要考虑合一和置换。

2.4.2 归结式

在谓词逻辑下求两个子句的归结式，和命题逻辑一样是消互补对，但需考虑变量的合一与置换。

设C1、C2是两个无公共变量的子句，L1、L2分别是C1、C2的文字，如果L1、～L2有mgu σ,则

(C1σ-{L1σ})∪(C2σ-{L2σ})

称作子句C1、C2的一个二元归结式，而L1、L2为被归结的文字。

归结式的注意事项：

·谓词的一致性，P()与Q()，不可以归结

·常量的一致性，P(a, …)与P(b,….)，不可以归结

·变量，P(a, ….)与P(x, …)，可以通过置换归结

变量与函数，P(a, x, ….)与P(x, f(x), …)，不可以归结；

但P(a, x, …)与P(x, f(y), …)，可以通过对两式分别做{f(y)/x}置换和{a/x}，再归结。

·不能同时消去两个互补对，形如P∨Q与～P∨～Q得空，是不正确的

·对子句集中的元素先进行内部简化（置换、合并）

例：

设C1＝P(y)∨P(f(x))∨Q(g(x))，C2＝～P(f(g(a)))∨Q(b)，求C1和C2的归结式。

解：

对C1，取最一般合一σ＝{f(x)/y}，得C1的因子

C1σ＝P(f(x))∨Q(g(x))

对C1的因子和C2进行归结，可得到C1和C2的归结式：Q(g(g(a)))∨Q(b)2.4.3 归结过程

谓词逻辑的归结过程与命题逻辑的归结过程相比，其基本步骤相同，但每步的处理对象不同。谓词逻辑需要把由谓词构成的公式集化为子句集，必要时在得到归结式前要进行置换和合一。

具体的谓词逻辑归结过程如下：

·写出谓词关系公式

·用反演法写出谓词表达式

·化为SKOLEM标准形

·求取子句集S

·对S中可归结的子句做归结

·归结式仍放入S中，反复归结过程

·得到空子句

·命题得证 例题2-4

“快乐学生”问题：

假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。

解：

先将问题用谓词表示如下：

R1:“任何通过计算机考试并获奖的人都是快乐的”

(x)((Pass(x, computer)∧Win(x, prize))→Happy(x))

R2:“任何肯学习或幸运的人都可以通过所有考试”

(x)(y)(Study(x)∨Lucky(x)→Pass(x, y))

R3:“张不肯学习但他是幸运的”

～Study(zhang)∧Lucky(zhang)

R4:“任何幸运的人都能获奖”

(x)(Luck(x)→Win(x,prize))

结论“张是快乐的”的否定

～Happy(zhang)

将上述谓词公式转化为子句集并进行归结如下：

首先将每一个表示逻辑条件的谓词子句转换为子句集可以接受的Skolem标准形。

由R1及逻辑转换公式:P∧W→H = ～（P∧W）∨ 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)Lucky(zhang)

由R4可得

(6)～Lucky(w)∨Win(w，prize)

由结论可得

(7)～Happy(zhang)结论的否定

根据以上7条子句，归结如下：

(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)归结

结论

1．归结法的实质：

·归结法是仅有一条推理规则的推理方法。

·归结的过程是一个语义树倒塌的过程。

2．归结法的问题

·对于传统归结法，子句中有等号或不等号时，完备性不成立。即，传统的归结法不能处理相等的关系。

Herbrand定理式归结原理的理论基础；而正是由于Herbrand定理的不实用性引出了可实用的归结法。

第三篇：人工智能原理教案02章归结推理方法2.3谓词逻辑归结法基础

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不可满足

第四篇：人工智能原理教案02章 归结推理方法2.3 谓词逻辑归结法基础

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）

(Qx)M（x,z）

（Qy）M（y）

（Qy）M（y,z）

量词否定等值式：

～(x)M（x）

～(x)M（x）

量词分配等值式：

(x)(P（x）∧Q（x）)

(x)(P（x）∨ Q（x）)

(x)P（x）∧(x)Q（x）(x)P（x）∨(x)Q（x）

（y）～ M（y）

（y）～ M（y）

消去量词等值式：设个体域为有穷集合（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)(Q → P（x）)

(x)P（x）∨ Q(x)P（x）∧ Q(x)P（x）→ Q Q →(x)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(x)P（x）→ Q 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 不可满足

由上面的定理，我们对SG的讨论，可以用较为简单的S1 ∪ S2 ∪ S3 ∪ …∪ Sn来代替。为方便起见，也称S1 ∪ S2 ∪ S3 ∪ …∪ Sn为G的子句形，即：

S1 ∪ S2 ∪S3 ∪ …∪ Sn不可满足

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)(x)P(x, y)

化为Skolem标准形，表示如下：

S A2：P(f(y), x)

结论：某个人是它的祖父

B：(x)(y)Q(x, y)

否定后得到子句：

S～B：～Q(x, y)∨ANS(x)

则得到的相应的子句集为：{ S A1，S A2，S～B }

解毕。

第五篇：人工智能原理教案03章 不确定性推理方法3.4 证据理论(D-S Theory)

3.4 证据理论（D-S Theory）

证据理论由Dempster首先提出，并由他的学生Shafer发展起来，也称D-S理论。在专家系统的不精确推理中已得到广泛的应用, 也用在模式识别系统中。证据理论中引入了信任函数，它满足概率论弱公理。在概率论中，当先验概率很难获得，但又要被迫给出时，用证据理论能区分不确定性和不知道的差别。所以它比概率论更合适于专家系统推理方法。当概率值已知时，证据理论就成了概率论。因此，概率论是证据理论的一个特例，有时也称证据沦为广义概率论。

在http://yoda.cis.temple.edu:8080/UGAIWWW/lectures/dempster.html上有关于Dempster－Shafer理论的英文介绍。

在http://www.quiver.freeserve.co.uk/Dse.htm上有免费的利用证据理论实现的程序Dempster Shafer Engine下载。有兴趣的读者可以安装这一软件，看看运行效果。这是我们已经下载下来的程序包：DempsterShaferEngine.zip。3.4.1 证据的不确定性

证据用集合来表示：如U中的每个元素代表一种疾病。讨论一组疾病A发生的可能性时，A就变成了单元的集合。U内元素Ai间是互斥的，但Ai中元素间是不互斥的。

图3-4证据理论集合空间分布示意图

t3-4_swf.htm 例如U可以表示疾病空间，而每个Ai可以是一类疾病，各类疾病之间是可以交叉的（同时得多种疾病），但是各类疾病本身是不同的。

证据理论定义了多个函数值来描述证据及规则的不确定性，其中包括：分配函数、信任函数和似然函数，分别定义如下。

· 基本概率分配函数m：2U→[0,1]。

m(Φ)= 0 空的为零

Σm(A)= 1 全空间的和为

1（A属于U）

基本概率分配函数是在U的幂集2U 上定义的，取值范围是[0,1]。

基本概率函数的物理意义是：

若A属于U，且不等于U，表示对A的精确信任度

若A等于U，表示这个数不知如何分配

· 信任函数Bel：2U →[0,1]。

A的信任函数为：包含于A中的所有集合的概率分配函数值之和。

根据定义有：Bel(Φ)＝m(Φ)= 0

Bel(U)＝Σm(B)= 1（B属于U）

信任函数Bel类似于概率密度函数，表示A中所有子集的基本概率分配数值的和。表示对A的总信任度。

· 似然函数Pl：2U →[0,1]

A的似然函数为Pl(A)：与A的“与”不为零的所有集合的概率分配函数值之和。

根据定义有：0 ≤ Bel(A)≤ Pl(A)≤1

可见Bel是Pl的一部分。

称Bel(A)和Pl(A)是A的下限不确定性值和上限不确定性值。因此可用区间（Bel(A)，Pl(A)）来表示A的不确定性度量。

我们可以通过信任函数、似然函数的特殊值，以及这些特殊值的相关关系来讨论它们所描述的证据可信度情况。设函数f(Bel(A), Pl(A))，下列特殊值的含义：

f(1, 1)表示A为真

f(0, 0)表示A为假

f(0, 1)表示对A一无所知

f(1, 0)不可能成立

一般情况都是包含在这些特殊值的某一个区间中的。可以根据与这些特殊值的相对关系来判断其可信程度。

此外，还可以用函数f1(A)来衡量A的不确定性，其定义如下：

f1(A)= Bel(A)+ |A|/|U|(Pl(A)∑m1(X)m2(Y), 当X∩Y =Φ

= ∑m1(X)m2(Y), 当X∩Y ≠Φ

且K-1 ≠ 0，若K-1 = 0，认为m1, m2矛盾。没有联合基本概率分配函数。例题

已知：f1(A1)= 0.40 ,f1(A2)=0.50,|U| = 20.A1→B={b1,b2,b3}，(c1,c2,c3)=(0.1,0.2,0.3)

A2→B={b1,b2,b3}，(c1,c2,c3)=(0.5,0.2,0.1)

求：f1(B)

解：

（1）先求：

m1({b1},{b2},{b3})=(0.4*0.1,0.4*0.2,0.4*0.3)

=(0.04,0.08,0.12);

m1(U)=1-[m1({b1})+m1({b2})+m1({b3})]=0.76;

m2({b1},{b2},{b3})=(0.5*0.5,0.5*0.2,0.5*0.1)

=(0.25,0.10,0.05);

m2(U)=1-[m2({b1})+m2({b2})+m2({b3})]=0.70;

及m = m1⊙ m2

1/K=m1({b1})*m2({b1})+

m1({b1})*m2({U})+ m1({b2})*m2({U})+ m1({b2})*m2({b2})+ m1({b3})*m2({b3})+m1({b3})*m2({U})+m1({U})*m2({b1})+ m1({U})*m2({b2})+ m1({U})*m2({b3})+ m1({U})*m2({U})

=0.01+0.028+0.008+0.056+0.06+0.084+0.19+0.076+0.038+0.532

=1.082

（2）然后计算：

m({b1})=K*(m1({b1})*m2({b1})+ m1({b1})*m2({U})+ m1({U})*m2({b1}))

=1.082*(0.01+0.028+0.19)

=0.247

m({b2})=K*(m1({b2})*m2({b2})+ m1({b2})*m2({U})+ m1({U})*m2({b2}))

=1.082*(0.008+0.056+0.076)

=0.151

m({b3})=K*(m1({b3})*m2({b3})+ m1({b3})*m2({U})+ m1({U})*m2({b3}))

=1.082*(0.06+0.084+0.038)

=0.138

m(U)=1-[ m({b1})+ m({b2})+ m({b3})]=0.464

最后：

Bel（B）＝m({b1})+ m({b2})+ m({b3})＝0.536

P1(B)＝1-Bel(~B)

由于基本概率分配函数只定义在B集合和全集U之上，所以其它集合的分配函数值为0，即Bel(~B)=0

所以，可得

P1(B)＝1-Bel(~B)=1

F1(B)=Bel(B)+(P1(B)-Bel(B))*|B|/|U|

=0.536+(1-0.536)*3/20

=0.606