人工智能重点总结(正式版)(2)

例题小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。”的格式定义谓词注意：

A）语义网络中不会考量词、继承、匹配

B）就根据题目所描述的写，不要蛋疼的写什么小明ISA人ISA动物ISA生物……题目上怎么说怎么写就可以（老师原话）

5.框架表示（只有概念题）

1>框架：我们无法把过去的经验一一都存在脑子里，而只能以一个通

用的数据结构的形式存储以往的经验。这样的数据结构称为

框架

2>框架的构成：

框架通常由描述事物的各个方面的槽组成，每个槽可以拥有若干

个侧

西电大三下学期09级人工智能重点整理

面，而每个侧面又可拥有若干个值。一个框架的一般结构如下：

<框架名>

<槽1><侧面11><值111>…<侧面12><值121>……

<槽2><侧面21><值211>…

…

…

<槽n><侧面n1><值n11>…

…

<侧面nm><值nm1>…

3>一个框架系统（我觉得应该不会考这个，保险起见所以放上来了）下图所示为表示立方体的一个视图的框架。图中，最高层的框架，用isa槽说明它是一个立方体，并由region槽指示出它所拥有的3个可见面A、B、E。而A、B、E又分别用3个框架来具体描述。用mustbe槽指示出它们必须是一个平行四边形。为了能从各个不同的角度来描述物体，可以对不同角度的视

图分别建立框架，然后再把它们联系起来组成一个框架系统。下图所示的就是从3个不同的角度来研究一个立方体的例子

6.过程、剧本表示不考

第三章经典逻辑推理

3.1归结演绎推理（问题求解&证明）

西电大三下学期09级人工智能重点整理

定理证明即证明P→Q(¬P∨Q)的永真性。根据反证法，只要证明其否定(P

∧¬Q)不可满足性即可。

海伯伦(Herbrand)定理为自动定理证明奠定了理论基础；鲁滨逊

(Robinson)提出的归结原理使机器定理证明成为现实。

在谓词逻辑中，把原子谓词公式及其否定统称为文字。如：P(x)，

¬P(x,f(x))，Q(x,g(x))，任何文字的析取式称为子句，不包含任何文字的子句称为空子句。

3.1.1化简子句集

(1)合取范式：C1∧C2∧C3…∧Cn

(2)子句集:S={C1,C2,C3…,Cn}

(3)任何谓词公式F都可通过等价关系及推理规则化为相应的子句集S。

子句集的性质：

(1)子句集中子句之间是合取关系。

(2)子句集中的变元受全称量词的约束。

把谓词公式化成子句集的步骤：

1)利用等价关系消去“→”和“ ”

例如公式

可等价变换成( x)(( y)P(x,y)→¬( y)(Q(x,y)→R(x,y)))( x)(¬( y)P(x,y)∨¬( y)(¬Q(x,y)∨R(x,y)))

( x)(( y)¬P(x,y)∨( y)(Q(x,y)∧¬R(x,y)))

( x)(( y)¬P(x,y)∨( z)(Q(x,z)∧¬R(x,z)))2)利用等价关系把“¬”移到紧靠谓词的位置上上式经等价变换后3)重新命名变元，使不同量词约束的变元有不同的名字上式经变换后

4)消去存在量词

a.存在量词不出现在全称量词的辖域内，则只要用一个新的个体

常量替换受该量词约束的变元。

b.存在量词位于一个或者多个全称量词的辖域内，此时要用

Skolem函数f(x1,x2,…,xn)替换受该存在量词约束的变元。

上式中存在量词( y)及( z)都位于( x)的辖域内，所以需要用

Skolem函数替换，设替换y和z的Skolem函数分别是f(x)和g(x)，

( x)(¬P(x,f(x))∨(Q(x,g(x))∧¬R(x,g(x))))

西电大三下学期09级人工智能重点整理

则替换后得到

5)把全称量词全部移到公式的左边

6)利用等价关系把公式化为Skolem标准形

P∨(Q∧R) (P∨Q)∧(P∨R)

Skolem标准形的一般形式是

( x1)( x2) ( xn)M

其中，M是子句的合取式，称为Skolem标准形的母式。上式化为

Skolem标准形后得到：

( x)((¬P(x,f(x))∨Q(x,g(x)))∧(¬P(x,f(x))∨¬R(x,g(x))))

7)消去全称量词

8)对变元更名，使不同子句中的变元不同名.上式化为

(¬P(x,f(x))∨Q(x,g(x)))∧(¬P(y,f(y))∨¬R(y,g(y)))

9)消去合取词，就得到子句集

¬P(x,f(x))∨Q(x,g(x))

¬P(y,f(y))∨¬R(y,g(y))

3.1.2替换的定义

推论1设C1与C2是子句集S中的两个子句，C12是它们的归结式。若用

C12代替C1和C2后得到新子句集S1，则由S1的不可满足性可推出原子

句集S的不可满足性，即：

S1的不可满足性S的不可满足性

推论2设C1与C2是子句集S中的两个子句，C12是它们的归结式。若把

C12加入S中得到新子句集S2，则S与S2在不可满足的意义上是等价的，

即：

S2的不可满足性S的不可满足性

推论1及推论2保证了我们可以用归结的方法来证明子句集S的不

可满足性。

西电大三下学期09级人工智能重点整理

为了要证明子句集S的不可满足性，只要对其中可进行归结的子句

进行归结，并把归结式加入子句集S，或者用归结式替换它的亲本子句，

然后对新子句集(S1或者S2)证明不可满足性就可以了。如果经过归结能

得到空子句，则立即可得原子句集S是不可满足的结论。

在命题逻辑中，对不可满足的子句集S，归结原理是完备的。即，若

子句集不可满足，则必然存在一个从S到空子句的归结演绎；若存在一

个从S到空子句的归结演绎，则S一定是不可满足的。

3.1.3归结

命题逻辑中的归结原理

定义4.9若P是原子谓词公式，则称P与¬P为互补文字。在命题逻辑中，

P为命题。

定义4.10设C1与C2是子句集中的任意两个子句。如果C1中的文字L1

与C2中文字L2互补，那么从C1和C2中分别消去L1和L2，并将两个子

句中余下的部分析取，构成一个新子句C12，则称这一过程为归结。称

C12为C1和C2的归结式，C1和C2为C12的亲本子句。

例4.9设C1=¬P∨Q,C2=¬Q∨R,C3=P

C1与C2归结得到：C12=¬P∨R

C12与C3归结得到：C123=R

谓词逻辑中的归结原理

在谓词逻辑中，由于子句中含有变元，所以不能像命题逻辑那样直

接消去互补文字，而需要先用最一般合一对变元进行代换，然后才能进

行归结。

例如,设有两个子句

C1=P(x)∨Q(x),C2=¬P(a)∨R(y)

由于P(x)与P(a)不同，所以C1与C2不能直接进行归结。但是若用最

一般合一

σ={a/x}

对两个子句分别进行代换：

西电大三下学期09级人工智能重点整理

C1σ=P(a)∨Q(a)C2σ=¬P(a)∨R(y)

就可对它们进行归结，得到归结式：

Q(a)∨R(y)

归结反演及其示例*

如欲证明Q为P1,P2,…,Pn的逻辑结论，只需证

(P1∧P2∧…∧Pn)∧¬Q

是不可满足的，或证明其子句集是不可满足的。而子句集的不可满

足性可用归结原理来证明。

应用归结原理证明定理的过程称为归结反演。

设F为已知前提的公式集，Q为目标公式(结论)，用归结反演证明Q

为真的步骤是：

a)否定Q，得到¬Q；

b)把¬Q并入到公式集F中， …… 此处隐藏：2612字，全部文档内容请下载后查看。喜欢就下载吧 ……