人工智能-谓词逻辑

谓词逻辑基础一阶逻辑基本概念个体词：表示主语词谓词：刻画个体性质或个体之间关系词量词：表示数量词人工智能-谓词逻辑第1页

小王是个工程师。

8是个自然数。 我去买花。 小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示是事物性质，第三个谓词“去买”表示一个动作也表示了主、宾两个个体词关系，最终一个谓词“是朋友”表示两个个体词之间关系。谓词逻辑基础人工智能-谓词逻辑第2页谓词逻辑基础比如：（1）全部人都是要死。（2）

有人活到一百岁以上。在个体域D为人类集合时，可符号化为：（1）

xP(x)，其中P(x)表示x是要死。（2）

xQ(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活到一百岁以上。

人工智能-谓词逻辑第3页一阶逻辑公式及其解释个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R量词符号：

,

谓词逻辑基础人工智能-谓词逻辑第4页量词否定等值式：～(

x

）

P（x）<=>（

y

）～

P（y）～(

x

）

P（x）<=>（

y

）～

P（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

）谓词逻辑基础人工智能-谓词逻辑第5页量词辖域收缩与扩张等值式：(

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）谓词逻辑基础人工智能-谓词逻辑第6页谓词逻辑基础人工智能-谓词逻辑第7页SKOLEM标准形前束范式

定义：说公式A是一个前束范式，假如A中一切量词都位于该公式最左边（不含否定词），且这些量词辖域都延伸到公式末端。谓词逻辑归结原理人工智能-谓词逻辑第8页即：把全部量词都提到前面去，然后消掉全部量词

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)约束变项换名规则：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）谓词逻辑归结原理人工智能-谓词逻辑第9页

量词消去标准： 消去存在量词“

”，略去全程量词“

”。 注意：左边有全程量词存在量词，消去时该变量改写成为全程量词函数；如没有，改写成为常量。

谓词逻辑归结原理人工智能-谓词逻辑第10页

Skolem定理： 谓词逻辑任意公式都能够化为与之等价前束范式，但其前束范式不唯一。SKOLEM标准形定义： 消去量词后谓词公式。注意：谓词公式GSKOLEM标准形同G并不等值。谓词逻辑归结原理人工智能-谓词逻辑第11页例：将下式化为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)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量词左移，直至全部量词移到前面， (

x)(

y)(u)(v)(P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式人工智能-谓词逻辑第12页第五步，消去“

”（存在量词），略去“

”全称量词 消去(

y)，因为它左边只有(

x)，所以使用x函数f(x)代替之，这么得到：

(

x)(

u)(v)(P(a,x,f(x))∨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))

人工智能-谓词逻辑第13页子句与子句集文字：不含任何连接词谓词公式。子句：一些文字析取（谓词和）。子句集S求取：

G→SKOLEM标准形 →消去存在变量 →以“，”取代“∧”，并表示为集合形式。谓词逻辑归结原理人工智能-谓词逻辑第14页

G是不可满足<=>S是不可满足G与S不等价，但在不可满足得意义下是一致。

定理： 若G是给定公式，而S是对应子句集，则G是不可满足<=>S是不可满足。

注意：G真不一定S真，而S真必有G真。 即：S=>G谓词逻辑归结原理人工智能-谓词逻辑第15页G=G1ΛG2ΛG3Λ…ΛGn

子句形G字句集能够分解成几个单独处理。

有SG=S1US2US3U…USn

则SG

与S1US2US3U…USn在不可满足得意义上是一致。 即SG

不可满足<=>S1US2US3U…USn不可满足3.3谓词逻辑归结原理人工智能-谓词逻辑第16页例：对全部x,y,z来说，假如y是x父亲，z又是y父亲，则z是x祖父。又知每个人都有父亲，试问对某个人来说谁是它祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：

P(x,y)表示x是y父亲

Q(x,y)表示x是y祖父

ANS(x)表示问题解答谓词逻辑归结原理人工智能-谓词逻辑第17页对于第一个条件，“假如x是y父亲，y又是z父亲，则x是z祖父”，一阶逻辑表示式以下：

A1：(

x)(

y)(

z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表示式：

A2：(

y)(

x)P(x,y) SA2：P(f(y),y)对于结论：某个人是它祖父

B：(

x)(

y)Q(x,y)

否定后得到子句：～（(

x)(

y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)则得到对应子句集为：{SA1，SA2，S～B}谓词逻辑归结原理人工智能-谓词逻辑第18页归结原理正确性根本在于，找到矛盾能够必定不真。方法：和命题逻辑一样。但因为有函数，所以要考虑合一和置换。

谓词逻辑归结原理人工智能-谓词逻辑第19页置换：能够简单了解为是在一个谓词公式中用置换项去置换变量。定义： 置换是形如{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}不是一个置换，

谓词逻辑归结原理置换人工智能-谓词逻辑第20页置换合成设

＝{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.

当yi

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

最终剩下元素所组成集合。合成即是对ti先做

置换然后再做

置换，置换xi谓词逻辑归结原理人工智能-谓词逻辑第21页例：设：

＝{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)是置换

作用于f(y)结果；y/y中y是置换

作用于z结果。在该集合中，y/y满足定义中条件i，需要删除；a/x，b/y满足定义中条件ii，也需要删除。最终得

·

＝{f(b)/x，y/z}谓词逻辑归结原理人工智能-谓词逻辑第22页合一合一能够简单地了解为“寻找相对变量置换，使两个谓词公式一致”。定义：设有公式集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}是它一个合一。注意：普通说来，一个公式集合一不是唯一。

谓词逻辑归结原理人工智能-谓词逻辑第23页谓词逻辑归结原理人工智能-谓词逻辑第24页谓词逻辑归结原理人工智能-谓词逻辑第25页谓词逻辑归结原理人工智能-谓词逻辑第26页归结原理归结注意事项：谓词一致性，P()与Q()，不能够常量一致性，P(a,…)与P(b,….)，不能够 变量，P(a,….)与P(x,…)，能够变量与函数，P(a,x,….)与P(x,f(x),…)，不能够；是不能同时消去两个互补对，P∨Q与～P∨～Q空，不能够先进行内部简化（置换、合并）

谓词逻辑归结原理人工智能-谓词逻辑第27页归结过程写出谓词关系公式→用反演法写出谓词表示式→SKOLEM标准形→子句集S→对S中可归结子句做归结→归结式仍放入S中，重复归结过程→得到空子句

▯得证谓词逻辑归结原理人工智能-谓词逻辑第28页例题“高兴学生”问题假设任何经过计算机考试并获奖人都是高兴，任何肯学习或幸运人都能够经过全部考试，张不愿学习但他是幸运，任何幸运人都能获奖。求证：张是高兴。

解：先将问题用谓词表示以下：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)人工智能-谓词逻辑第29页例题“高兴学生”问题由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) （结论否定）(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)

人工智能-谓词逻辑第30页归结法实质：归结法是仅有一条推理规则推理方法。归结过程是一个语义树坍毁过程。归结法问题子句中有等号或不等号时，完备性不成立。※Herbrand定理不实用性引出了可实用归结法。谓词逻辑归结原理人工智能-谓词逻辑第31页归结过程控制策略要处理问题：归结方法知识爆炸。控制策略目标归结点尽可能少控制策略标准给出控制策略，以使仅对选择适当子句间方可做归结。防止多出、无须要归结式出现。或者说，少做些归结仍能导出空子句。谓词逻辑归结原理人工智能-谓词逻辑第32页

删除策略 => 完备名词解释：归类：设有两个子句C和D，若有置换

使得C

D成立，则称子句C把子句D归类。 因为小能够代表大，所以小吃掉大了。若对S使用归结推理过程中，当归结式Cj是重言式（永真式）和Cj被S中子句和子句集归结式Ci(i<j)所归类时，便将Cj删除。这么推理过程便称做使用了删除策略归结过程。谓词逻辑归结原理人工智能-谓词逻辑第33页主要思想：归结过程在寻找可归结子句时，子句集中子句越多，需要付出代价就会越大。假如在归结时能把子句集中无用子句删除掉，就会缩小搜索范围，降低比较次数，从而提升归结效率。删除策略对阻止无须要归结式产生来缩短归结过程是有效。然而要在归结式Cj产生后方能判别它是否可被删除，这部分计算量是要花费，只是节约了被删除子句又生成归结式。尽管使用删除策略归结，少做了归结但不影响产生空子句，就是说删除策略归结推理是完备。谓词逻辑归结原理人工智能-谓词逻辑第34页采取支撑集 <=>完备

支撑集：设有不可满足子句集S子集T，假如S-T是可满足，则T是支持集。

采取支撑集策略时，从开始到得到

整个归结过程中，只选取不一样时属于S-T子句，在其间进行归结。就是说，最少有一个子句来自于支撑集T或由T导出归结式。

谓词逻辑归结原理人工智能-谓词逻辑第35页比如：A1ΛA2ΛA3Λ～B中～B能够作为支撑集使用。要求每一次参加归结亲本子句中，只要应该有一个是有目标公式否定（～B）所得到子句或者它们后代。支撑集策略归结是完备，一样，全部可归结谓词公式都能够用采取支撑集策略到达加紧归结速度目标。问题是怎样寻找适当支撑集。一个最轻易找到支撑集是目标子句非，即S～B。谓词逻辑归结原理人工智能-谓词逻辑第36页ST可满足支撑集示意图谓词逻辑归结原理人工智能-谓词逻辑第37页

语义归结 <=> 完备 语义归结策略是将子句S按照一定语义分成两部分，约定每部分内子句间不允许作归结。同时还引入了文字次序，约定归结