考完试记录一下复习资料人工智能原理知识点整理「建议收藏」

1、知识表示实际上就是对知识的一种描述，即用一些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。

2、常用的知识表示方法

非结构化方法

逻辑表示法 QA3,STRIPS,DART,MOMO

产生式系统 DENDRAL，MYCIN

结构化方法

框架

语义网络

过程式知识表示法

3、产生式系统的定义

产生式系统是人工智能系统中常用的一种程序结构，是一种知识表示系统。

通常由以下三部分组成：

综合数据库（存放问题的状态描述的数据结构。）
产生式规则集
控制系统

（1）选择规则：

对同一个状态的多个可用规则排序。

（2）检验状态描述是否满足终止条件。

如果满足终止条件，则终止产生式系统的运行，

并用使用过的规则序列构造出问题的解。

4、可交换产生式系统定义：（第二章ppt P34）

一个产生式系统称为可交换的，如果对任意状态描述D具有如下性质：

设RD是可应用于D的规则集，任取r ∈RD， r作用于D得 D’，设为D’= r (D)，则r对D’ 可用(即：设D’的可用规则集为RD’，则r∈ RD’ ，即RDÍ RD’ )；
设D满足目标条件，D的可用规则集为RD，任取 r∈ RD ，用r作用到D产生状态D’ ，D’满足目标条件。
设D的可用规则集为RD，任取 r1, r2, …, rn ∈RD，依据（a）将r1, r2, …, rn依次作用到D及产生的状态上，得状态Dn；设r1’, r2’, …, rn’ 是 r1, r2, …, rn的任意一个排列，用r1’, r2’, …, rn’依次作用到D及产生的状态上，得状态Dn’，则Dn’= Dn 。

例子：

5、产生式系统的工作方式：

1.正向产生式系统（数据驱动控制）：适用条件：初始节点数≤目标节点数

2. 反（逆）向产生式系统（目标驱动控制）：适用条件：初始节点数≥目标节点数

3. 双向产生式系统：正向产生式系统和反向产生式系统结合:

初始节点数与目标节点数都很多特点：效率高；复杂。

6、产生式系统的特点：

一、模块性强。综合数据库、规则集和控制系统相

对独立，程序的修改更加容易。

二、各产生式规则相互独立，不能互相调用，增加

一些或删去一些产生式规则都十分方便。

三、产生式规则的形式与人们推理所用的逻辑形式

十分接近，人们具有的知识转换成产生式规则

很容易，产生式规则也容易被人们读懂。

7、控制策略

不可撤回的控制策略
试探性控制策略：回溯方式和图搜索方式

8、特殊的产生式系统

A、可交换产生式系统：

在某些产生式系统中。规则应用的次序对产生的状态无影响，即从初始状态

到目标状态不依赖规则次序，因此可应用不可撤回式控制策略。从而提高了产

生式系统的效率，这类产生式系统就是可交换的产生式系统

B、可分解的产生式系统（避免搜索多余路径的另一种方法是可分解的产生式系统。）

定义:能够把产生式系统综合数据库的状态描述分解为若干组成部分，产

生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用

各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统。

Procedure PRODUCTION（产生式系统的基本过程）

选取规则所依据的原则称为控制策略。

DATA←初始状态描述
until DATA 满足终止条件，do：
begin
在规则集合中，选出一条可用于DATA的规则R
DATA←把R应用于DATA所得的结果
End

Procedure SPLIT（可分解的产生式系统）

SPLIT的控制策略：在步骤5中如何选取D*，在步骤7如何选取R。

DATA ← 初始状态描述
{Di} ← DATA的分解结果；每个Di看成是独立的状态描述
until 对所有的Di Î{Di}， Di都满足终止条件，do:
begin
在{Di}中选择一个不满足终止条件的D*
从{Di}中删除D*
从规则集合中选出一个可应用于D*的规则R
D ← 把R应用于D*的结果
{di} ← D的分解结果
把{di}加入{Di}中
end

9、不可撤回的控制策略

爬山函数：定义在整个综合数据库上的实数值函数，

目标状态有最大的函数值。

目标：爬到山顶。

控制策略：应用爬山函数选一规则，使得所选下一状态的爬山函数值不减少且最大（有两个相同的最大值时任选一个；若无这样的规则，则终止爬山过程）。

10、八数码问题——回溯

设爬山函数CF(S) ：不在目标位的数码个数的负值。

11、八数码难题回溯式

、

12、图搜索控制策略的特点

不再选择规则，而是使用所有可用的规则，下一步选择节点来扩展。
存储所有产生的节点，占用空间大。
有解一定能找到（相当于穷举）。
平均时间复杂性高，系统效率低。

13、四皇后问题：

存在的问题：回溯的次数很多，22次回溯。

传统回溯法：

原因：没有关于问题的探索性信息指导规则排序。

解决方法之一：在规则排序过程中使用一些探索性信息，减少回溯次数，提高算法效率．

例：使用函数 diag(i, j)来修改APPRULES(RULES)

diag(i, j)：通过单元（i，j）的最长对角线的长度．(在扩展每一层扩展全然后根据启发信息值排序，然后确定探索哪一个节点或状态，回溯的时候直接根据排列好的顺序继续向下扩展)

修改后的 APPRULES(RULES):

if diag（i，j）＜diag（i，k）,then Rij排在Rik前．

if diag（i，j）= diag（i，k），then与以前相同

按照小的顺序进行扩展，这里还是一个深度搜索与后面的启发式搜索用到open表不一样注意！

问题？？？这个意思就是深度搜索的时候根据最长对角线长度来决定先搜索谁，比如第一开始最长对角线是最左和最右，那么先从左边开始，搜索R11放皇后之后，在第二行中搜索R24放皇后具有最长的右上对角线，这样子去扩展？？？

14、图搜索策略

一、相关概念

A、有向图：G=(P,A)，P:点集 A:弧集

对于产生式系统，

节点：用状态描述标记

弧：用规则标记

目的：图搜索策略把寻找从初始状态描述到目标描述的规则序列问题转化成寻找有向图的解路径问题

B、有向树：每一个节点最多只有一个父亲的有向图．

有向树中节点的深度:

1) 根节点的深度是0，

2)其它节点的深度等于它父节点的深度加1。

加权有向图（权图）：每条弧线上都有使用费用（正数）的图。

D、隐含图：由部分节点和一组其它节点生成规则所确定的图．

二、启发式搜索

启发式信息：用于帮助减少搜索量的与问题有关的信息或知识。

启发式搜索：使用启发信息指导的搜索过程叫做启发式搜索。

启发信息特点：

启发信息强，可以降低搜索的工作量，但可能导致找不到最优解；

启发信息弱，一般会导致搜索的工作量加大，极端情况下演变为盲目搜索，但有可能找

到最优解。

常规用法：使用启发信息的一种重要方法是采用估价函数。

启发式搜索例子：

问问问问问是普通的回溯法+启发信息？

答：不是，与回溯法区分，它就是用graphsearch算法的一个搜索，只是当估价函数=0的时候变成了宽度优先搜索，然后与后面你的A*算法区分，A*算法的Closed表中的点可能与当前扩展点重复，需要重新判断更新值，但是比如八数码的启发搜索，他是树的形式，不存在重复，所以只需要考虑将当前节点的后继全部扩展一遍，放入open然后根据启发信息排列，进行下一步的循环扩展即可。

利用估价函数f(n)=d(n)+W(n)反向搜索上例八数码难题。指出反向搜索和正向搜索在什么地方相遇。

(左优先、浅层的优先)

三、相关搜索概念（正向和反向与搜索策略无关与初始状态和目标状态的先后有关）

1.正向搜索：从初始节点到目标的搜索

2.反向搜索：从目标节点到初始节点的搜索

3.双向搜索：正向和反向搜索的结合

搜索需要产生的节点数

1.宽度优先搜索，使用双向搜索要优越许多

2.对于启发式搜索,评价单向搜索和双向搜索的优劣很复杂,双向搜索使用不当可能是单向搜索量的二倍.

3.分阶段搜索：为了完成搜索过程，可对搜索图进行修剪，释放出一部分存储空间。

把OPEN表具有最小f值的一些节点打上标记，记住这些节点和通向这些点的最佳路径，删去搜索图其余部分。然后恢复节点和路径，重新开始搜索。分阶段搜索并不能保证找到一条解路径。

四、可采纳性

定义：如果一个搜索算法对于任何具有解路径的图都能找到一条最佳路径，则称此算法为可采纳的。

A*算法的可采纳性A*算法是可采纳的（如果解路径存在，A*一定由于找到最佳解路径而结束）：

A*可采纳相关定理以及推论：

前要概念：

K(ni, nj) ：隐含图中节点ni到nj最小费用路径的实际费用。

若ni到nj无路，则函数K(ni, nj) 无定义。

h*(n)：设{ti} 是目标节点集合，定义

h*(n)=mini{ K(n, ti) }

表示隐含图中从n到目标节点的最小费用路径的费用。

对不能到达目标节点的节点n，h*(n)无定义。

最佳解路径：从n到目标节点的任何费用为h*(n)的路径。

g*(n)： g*(n)=K(s，n)

表示隐含图中从初始节点s到n的最佳解路径的费用。

f*(n)：f*(n)=g*(n)+h*(n)

表示隐含图中，通过节点n，从s到目标节点的最佳解路径的费用。

当n是从初始节点到目标节点t的最佳解路径上的节点时，

f*(n)= f*(s)=f*(t)=h*(s)。

f*(s)指的是从初始节点到目标节点的最佳解路径费用

A*算法:对任何节点n都有h(n)≤h*(n)的A算法。（理解≤号其实直观的理解应该是=号，≤是为了更加的严谨，因为如果是＞肯定不是A*所以是≤，但是实际上我们不可能或者是很难找出这样的A算法，但是如果它能够找出最佳解路径，我们也都认为这一A算法是A*算法，后面的不同A*算法的比较也可以看作是不同的A算法之间的比较）

定理1：GRAPHSEARCH对有限图必然终止。

引理1 若A*不终止，OPEN表中节点的估价函数值可以

无限变大。

定理2 若存在s到目标的解路径，则算法A*终止前的任何

时刻，OPEN表中总存在一个节点n’， n’在从s到

目标的最佳解路径上，且满足f(n’) ≤f*(s)

定理3 若存在解路径，则A*算法必终止。

推论 OPEN表中的任一满足f(n)<f*(s)的

节点n，最终将被算法A*选作扩展节点。

定理4 算法A*是可采纳的。（若解路径存在,A*一定找到最佳解路径而终止）．

（定理4和定理3的区别是存在解路径的时候某一算法终止不代表找出最佳解路径）

定理5 算法A*选择的任意扩展点n都有f(n)≤f*(s)

五、A*算法比较

定义设A1和A2是两个 A*算法，分别使用如下两个估价函数：

f1(n)=g1(n)+h1(n)

f2(n)=g2(n)+h2(n)

其中，h1(n)和h2(n)是h*(n)的两个下界．若对于所有的非目标节点n，都有h2(n)＞h1(n)，则称算法A2比算法A1有较多的信息．

讨论：启发函数的启发能力在于它所具有的启发性信息。

1. 当h(n)≡0时，反映了启发函数完全没有启发信息，要扩展较多的节点．

2. 在具有可采纳性的前提下， 0≤h≤h*，h*定出了h的上界，当h越接近h*时，它的启发能力就越大．（注意A*的h(n)和h*(n)应该来看是两个东西，h*(n)是一个客观事实，A*的h（n）是一个范围0≤h(n)≤h*(n)，根据这样子来看两个A*算法可以比较启发能力，越近h*(n)启发能力越大）

例八码难题的A*算法的比较．

图3.7的估价函数：f1(n)=d(n)，h1(n)≡0，采用宽度优先搜索；

图3.8的估价函数：f2(n)=d(n)+w(n)，h2(n)≡w(n)．

对于所有非目标节点，有h2(n)＞h1(n)，因此，图3.7所用算法不但比图3.8所用算法有较多的信息，而且扩展的节点数要少。？？？？不应该是3.8多？

定理6 如果A1和A2是两个A*算法，算法A2比A1有较多的信息，且它们搜索同一个隐含图。若该图存在解路径，当这两个算法终止时，A2所扩展的每一节点也必被A1所扩展，即：

A2扩展的节点数≤A1扩展的节点数

六、单调限制及性质

定义如果启发函数h对任何节点ni和nj，只要nj是ni的后继，都有

h(ni)－h(nj)≤c(ni, nj)

h(t)=0 （t是目标节点）

则称启发函数h满足单调限制．

定理7 如果A*算法的启发函数h满足单调限制，则当算法A*选择节点n扩展时，就已经发现了通向节点n的最佳路径，即g(n)=g*(n)．

定理8 如果A*算法启发式函数h满足单调限制，则A*所扩展的节点序列的估价函数值是非递减的

A*算法小结

1. A*算法搜索隐含图时，有解必停，且必停在最佳解路上；

2. 在满足h (n) ≤h*(n)的前提下，启发函数越大，其所包含的启发信息越多，所扩展的节点越少；

3. 若启发函数满足单调限制，则每走一步都在最佳解路上，且估价函数不减，简化了算法的第7步（调整指针）.

七、算法A的启发能力

定义设A1和A2是两个启发式算法，它们分别使用估价函数f1和f2，如果在寻找解路径的过程中，A1所用的计算费用比A2少，则称A1比A2有较强的启发能力，也可以称估价函数f1比f2有较强的启发能力．

影响算法A启发能力的三个重要因素：（注意启发信息和启发能力的区别，启发信息大不一定启发能力强）

（1）算法A所找到的解路径的费用。

（2）算法A在寻找这条解路径的过程中所需要

扩展的节点数。

（3）计算启发函数所需要的计算量。

Tips: h(n) ≤ h*(n) 保证了A*的可采纳性，可采纳性可能意味着算法需要扩展更多的节点，使总的费用提高。

Note1:若能保证高效（增强算法的启发能力），则牺牲可采纳性是可取的。

八、启发能力的度量

1、搜索方法的启发能力主要依赖于给定问题的具体因素。（影响因素）

2、判断启发能力的强弱主要是凭经验而不是凭计算。（判断条件）

3、某些实现上的度量是可计算的。这些度量不能完全决定一个算法的启发能力，在比较各种搜索算法的优劣时是很有用的。（度量作用）

启发能力的一种度量为渗透度：

渗透度是对一个搜索算法的搜索性能的度量，表示搜索集中指向某个目标的程度，而不

是在无关的方向上徘徊。

定义为： P = L / T

其中，L是算法发现的解路径的长度， T是算法在寻找这条解路径期间所产生的节点数

（不包括初始节点，包括目标节点）

一般搜索的渗透度P<1 ；

无信息的搜索P<<1；

渗透度大，所产生的搜索树向纵深发展；

渗透度小，所产生的搜索树沿水平方向发展。

搜索算法的渗透度取决于问题的难度和算法的效率。

当最佳解路短时，可能有较高的渗透度；

当最佳解路长时，算法产生节点的数目将以更快的速度增加，可能有较低的渗透度。

渗透度有时并不能很好地反映搜索向目标方向发展的集中程度。

启发能力的一种度量为有效分枝系数：

有效分枝系数就是一棵搜索树的平均分枝数．

设搜索树的深度是L，算法所产生的总节点数为T，有效分枝系数是B，则有

B＋B2十…＋BL=T

或

B（BL-1）/（B-1）=T

有效分枝系数与路径的长度无关，可以利用这一事实预测不同深度的搜索所需产生的节点个数。

九、AO*算法可采纳性（考试时常与四练习）

若s→N集存在解图，当h（n）≤h*（n）且h（n）满足单调限制条件时能找到最佳解图，即在这种情况下，AO*具有可采纳性，AO*算法一定。

15、剪枝例题

16、与/或图搜索

A、与或图定义：一个可分解的产生式系统定义一个隐含的与/或图．图的根节点表示产生式系统的初始状态描述，连接符表示对一状态描述应用产生式规则或把这一状态描述分解成若干组成部分．

B、可分解产生式系统的任务:从隐含的与/或图出发找出一个从根节点出发到终止节点集的解图。

C、SOLVED节点

搜索过程还要标记能解节点（SOLVED），为此给出如下定义：
能解节点（SOLVED）
①终止节点是能解节点；
②若非终止节点有“或”子节点时，其子节点有一能解，则该非终止节点是能解节点；
③若非终止节点有“与”子节点时，若其子节点均能解，则该非终止节点是能解节点。

17、AO*算法（一种可分解产生式系统的搜索策略）

两个图

G：搜索图

G’：局部解图（准部分解图）（可能变化的）

两个函数

h(n)：启发函数（静态）对h*(n)的估计

q(n)：费用函数（动态变化）

两重循环

外层：从上向下扩展

内层：从下向上修改费用q值、标记指针

AO* Note：

(1)在第6步扩展节点n时，若不存在后继节点（即陷入死胡同），则可在第11步中对m（即n）赋一个高的q值，这个高的q值会依次传递到s，使得含有节点n的子图具有高的q（s），从而排除了被当作候选局部解图的可能性。

(2)如果一个与／或图存在解图，如果对于图中所有的节点n都有h（n）≤h*（n），并且启发函数h满足单调限制，则AO*算法必然终止于找出最佳解图。（有条件的可采纳性）

18、博弈树搜索

双人、具有完备信息博弈问题的特点：

(1)双人对弈，对垒的双方轮流走步。

(2)信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的

情况。

(3)零和。即对一方有利的棋，对另一方肯定不利，不存在对双方均有利、或均无利的棋。

对弈的结果是一方赢，另一方输，或者双方和棋。

双人、具有完备信息博弈的实例有：一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。

博弈下的截图实现一种取胜的策略就是搜索一个解图的问题，解图就代表一种完整的博弈策略。

缺点：对于简单的游戏，采用与寻找 AND／OR图解图相类似的技术是可以解决的．但是，对于复杂的游戏，这种方法是根本行不通的．

静态估值函数e(p)：建立在该棋的各种知识和特征上。对在一定深度处的节点所代表的局面进行评价优劣的估计值．

极小极大原则

MAX节点在其MIN子节点的倒推值中选max；

MIN节点在其MAX子节点的倒推值中选min

倒推值

在极小极大过程中，第i层节点根据第i+1层节点的值使用极小极大原则而获得的值。

极小极大过程存在的问题：

节点数将随着搜索深度的增加呈指数增长。这极大地限制了极小极大搜索方法的使用。

解决方法：让搜索树的产生过程与静态估值与返回值的过程同时进行，在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数，从而使搜索效率大为提高。 —-α-β过程

（1）α剪枝：发生在MIN节点下的剪枝

（2）β剪枝：发生在MAX节点下的剪枝

剪枝效率：在使用相同存储空间的条件下，α-β过程能把搜索深度扩大一倍．

小结：

博弈问题可用产生式系统来描述，求解过程也是一个对与/或图进行搜索的问题。

针对双人完备信息的博弈问题，通常可行的实用策略是搜索被限制在一定的范围，搜索的目标是确定一步好棋，等对手回手后，再继续搜索。MINIMAX就是按这种思想建立的过程，而α-β过程是MINIMAX过程的改进，并可提高效率。

第六章归结原理

1、Herbrand域

定义（Herbrand域）设S为子句集，令H0是出现于子句集S的常量符号集。如果S中无常量符号出现，则H0由一个常量符号a组成。

对于i＝1，2，…，令

Hi = Hi-1È｛所有形如f(t1，…，tn)的项｝

其中f(t1，…，tn)是出现在S中的所有n元函数符号，

tjÎ Hi-1，j＝1，…，n．

称Hi为S的i级常量集，H¥ 称为S的Herbrand域，

简称S的H域

2、基

基：把对象中的变量用常量代替后得到的无变量符号出现的对象。基项、基项集、基原子、基原子集合、基文字、基子句、基子句集

子句是析取式短语是合取式

3、原子集、Herbrand底

设S是子句集，形如P(t1,…,tn)的基原子集合，称为S的Herbrand底或S的原子集．

其中P(x1，…，xn)是出现于S的所有n元谓词符号，t1，…，tn是S的H域中的元素．

4、基例

设S是子句集，C是S中的一个子句．用S的H域中元素代替C中所有变量所得到的基子句称为子句C的基例。

5、已知S＝ {Q(a)Ú～P(f(x))，～Q(b)Ú P(g(x,y))}，求S的原子集，分别给出Q(a)Ú～P(f(x)) ，～Q(b)Ú P(g(x,y))的一个基例。？？？？？？？？？？？？？？？？？？？？？

理解：Q(),P()两个里面都是只有一个元素，因此它们各自是一元谓词，因为有Q(a),Q(b),Q(f(a))…P(a),P(b),P(f(a)),P(g(a,a))…的形式作为原子集中的元素

比如如下的例子

Q(y,f(y,a))里面有a常量，但是不用管，f是个二元函数，就将其当成f(t1,t2)正常去替换就可以了

6、H解释

定义（子句集的H解释）设S是子句集，H是S的H域，I*是S在H上的一个解释．称I*为S的一个H解释，如果I*满足如下条件：

1） I*映射S中的所有常量符号到自身。

2）若f是S中n元函数符号，h1，…，hn是H中元素，则I*指定映射：

(h1，…，hn) ®f (h1，…，hn)

设A={A1，A2，…，An， … } 是S的原子集。于是S的一个H解释I可方便地表示为如下一个集合：

I* ＝｛m1，m2，…，mn，…｝

其中,

谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成：

1. 对每个常量符号，指定D中一个元素；

2. 对每个n元函数符号，指定一个函数，即指
定Dn到D的一个映射；

3. 对每个n元谓词符号，指定一个谓词，即指
定Dn到{T，F}的一个映射。

例 S={P(x)ÚQ(x), R(f(y)) }

S的H域={a, f(a), f(f(a)), … }

S的原子集：

A={P(a), Q(a), R(a), P(f(a)), Q(f(a)), R(f(a)), … }

S的H解释：

I1* ={ P(a), Q(a), R(a), P(f(a)), Q(f(a)), R(f(a)), … }

I2* ={ ～P(a), ～Q(a), R(a), P(f(a)), ～Q(f(a)), ～R(f(a)), … }

S={P(x)ÚQ(x), ～P(a), ～Q(b) }，

求S的所有H解释？？

7、Herbrand解释与普通解释的关系

子句集S的H解释是S的普通解释。
S的普通解释不一定是S的H解释：普通解释不是必须定义在H域上，即使定义在H域上，也不一定是一个H解释。
任取普通解释I，依照I，可以按如下方法构造S的一个H解释I*，使得若 S在 I下为真则 S在I*下也为真。

8、对应于I的H解释I*

对应于I的H解释I*是如下的一个H解释：

任取S中n元谓词符号P(x1,…,xn)，

任取(h1,…,hn)ÎHn，规定

TI*(P(h1，…，hn))=TI(P(h1s，…，hns))

引理如果某区域D上的解释I满足子句集S，

则对应于I的任意一个H解释I*也满足S。

9、只考虑子句集的H解释是否够用？

定理子句集S恒假当且仅当S被其所有H解释弄假。

证明: 必要性显然。

充分性。假设S被其所有H解释弄假，而S又是可满足的。

设解释I满足S，于是由引理知，对应于I的H解释I*也满足S，矛盾．故S是不可满足的．

从现在起，如不特别指出，提到的解释都是指H解释．

***思考：比如后面的语义树，它是根据树结构来找寻能够弄假S的H解释来证明不可满足问题的，对于归结原理里面使用的谓词逻辑，比如你在替换变量的时候其实也是一个在找寻H解释的过程，只不过在那个情况下有的变量可以不用替换直接用归结式或者表推演的形式~

结论

l）子句 C的基例 C’被解释 I满足，当且仅当

C’中的一个基文字L’出现在 I中．

2）子句C被解释I满足，当且仅当

C的每一个基例都被I满足．

3）子句 C被解释 I弄假，当且仅当

至少有一个C的基例C’被I弄假。

4）子句集S不可满足，当且仅当

对每个解释I，至少有一个S中某个子句C的基例C’被I弄假。

例子：

C=～P(x)ÚQ(f(x))

I1={
～P(a),～Q(a),～P(f(a)),～Q(f(a)),～P(f(f(a))),～Q(f(f(a))),…}

I2={P(a),Q(a),P(f(a)),Q(f(a)),P(f(f(a))),Q(f(f(a))),…}

I3={P(a),～Q(a),P(f(a)),～Q(f(a)),P(f(f(a))),～Q(f(f(a))),…}

显然，I1，I2满足C，I3弄假C。

10、Herbrand定理

Herbrand定理是符号逻辑中一个很重要的定理．Herbrand定理就是使用语义树的方法，把需要考虑无穷个H解释的问题，变成只考虑有限个解释的问题．

11、互补对

设 A是原子，两个文字A和～A都是另一个的补，集合｛A，～A｝称为一个互补对．

12、Tautology,重言式: 含有互补对的子句

13、语义树

14、完全语义树

设A={A1,…,An,…｝是子句集S的原子集．

S的一个语义树是完全的，当且仅当

对于语义树中每一个尖端节点N（即从N不再

生出节的那种节点），都有

Ai或～Ai有且仅有一个属于I(N),i=1,…,k,…

例子：

帮助理解前面的L1…Ln

谓词逻辑下的完全语义树，如果太复杂直接打省略号即可，注意里面有Q(f(a))也就是说最多扩展完Q(f(a))后打省略号或者这种箭头，当然想ppt这么写更加方便，不然扩展到Q(f(a))会写不下并混乱

15、封闭语义树相关概念

定义（失效点）称语义树T中的节点N为失效点，如果

(1)I(N)弄假S中某个子句的某个基例；

(2)I(N’)不弄假S中任意子句的任意基例，其中N’是 N的任意祖先节点。

定义（推理点）称封闭语义树的节点 N为推理点，如果N的所有直接下降节点都是失效点．

16、使用Herbrand定理的机器证明过程

Gilmore过程指数复杂性，改进后得到D-P
D-P过程（单文字规则纯文字规则分裂规则）

17、归结原理相关定理及其证明（可能考，理解即可）

A、定理设C1和C2是两个基子句， R(C1, C2) 是C1，C2的归结式，则R(C1, C2)是C1和C2的逻辑结果。

证明：设 C1=L ÚC1’, C2=～LÚC2’。于是

R(C1, C2) ＝C1’ ÚC2’

设I是C1和C2的一个解释，且满足C1也满足C2。因为L和～L中有一个在I下为假，不妨设为L。于是C1’非空，且在I下为真。故R(C1, C2)在I下为真。

Note:

逻辑结果的定义：如果C1 C2是真的，则R(c1,c2)是真的

B、定理

如果基子句集S是不可满足的，则存在从S推出空子句的归结演绎

18、替换

A、定义(替换)一个替换是形如{t1/v1, … , tn/vn }的一个有限集合，其中vi是变量符号，ti是不同于vi的项。并且在此集合中没有在斜线符号后面有相同变量符号的两个元素，称ti为替换的分子，vi为替换的分母。

例. {a/x, g(y)/y, f(g(b))/z}是替换;

{x/x}, {y/f(x)}, {a/x, g(y)/y, f(g(b))/y}不是替换;

基替换:当t1,…,tn是基项时，称此替换为基替换。

空替换：没有元素的替换称为空替换，记为e。

B、定义（改名）设替换 s ={ t1/x1, … , tn/xn }

如果t1, … , tn是不同的变量符号，则称s为一个改

名替换，简称改名。

替换作用对象：表达式（项、项集、原子、原子集、

文字、子句、子句集）

基表达式：没有变量符号的表达式。

子表达式：出现在表达式E中的表达式称为E的子

表达式。

例子：

E=P(x, y, z), q={y/x, z/y}

Eq=P(y, z, z). Eq¹P(z, z, z).

C、替换的乘积

定义（替换的乘积）设q ={ t1/x1, … , tn/xn }，l ={ u1/y1, … , um/ym} 是两个替换。将下面集合 { t1l/x1, … , tnl/xn , u1/y1, … , um/ym } 中任意符合下面条件的元素删除：

1）ui/yi，当yiÎ{x1, … , xn }时；

2）til/xi，当til = xi 时。

如此得到一个替换，称为q与l的乘积，记为q ×l。

例. 令 q ={f(y)/x, z/y}

l ={a/x, b/y, y/z}

于是得集合

{ t1l/x1, t2l/x2 , u1/y1, u2/y2 , u3/y3 }

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

q 与l的乘积为：q ×l = {f(b)/x, y/z } note：q×l ¹ l×q

19、合一替换相关定义定理

定义(合一)称替换q是表达式集合{E1,…,Ek}的合一，当且仅当E1q＝E2q=…=Ekq。

表达式集合｛E1, … , Ek｝称为可合一的，如果存在关于此集合的一个合一。

定义(最一般合一) 表达式集合｛E1, … , Ek｝的合一s 称为是最一般合一(most general unifier, 简写为mgu)，当且仅当对此集合的每一个合一q，都存在替换l，使得

例 S={P(x) Ú ~Q(x),~P(y), Q(b)}

{P(x),P(y)}可合一，q＝{a/x, a/y}是合一，

其mgu s＝{x/y}，有替换 l={a/x}，使

q＝s×l= {x/y} ×{a/x}

理解：子句集S要合一需要有另一个S1子句集且形式和其一样，然后再找差异集慢慢推；如果没有则看子句的合一，S中有若干子句，不同子句之间看是否能合一，若不能则看S中的原子是否能合一，这时找出了P（x）这一谓词，P(x),P(y)是两个原子，因为内部的x，y

W不可合一的三种情况

（1）若D中无变量符号为元素，则W是不可合一的。

例. W={P(f(x)), P(g(x))}

D={f(x), g(x)}

（2）若D中有奇异元素和非奇异元素，则W是不可合一的。

例. W={P(x), P(x, y)}

D={
⊙, y}

（3）若D中元素有变量符号x和项t，且x出现在t中，则W是不可合一的。

例. W={P(x), P(f(x))}

D={x, f(x)}

在这种情况下不能合一，我们可以考虑改名然后进行合一，注意，单纯的这俩没有必要进行合一，是考虑还有其他的合一项，注意一个例子！！！

换名:
- {P(f(x), x), P(x, a)};
- 如果不换名：D={f(x), x}.
- 注意f(x),x在差异集合中不可以合一
- 换名: {P(f(y), y), P(x, a)};
- 换名之后的差异项必然是x和f(y)不会进入内部找寻x,y
- 只有说f(x)，f(u)这样出现在两个谓词中才会用到x，u是差异集合因为会根据f无差异网内推到x,u有差异，上面的f(x),x不可合一不是因为f内是x，x与x无差异导致的不可合一，而是定义出来的它就是不可合一的，与寻找差异项的问题无关
- mgu: {f(a)/x, a/y}

合一算法（Unification algorithm）

步骤1：置 k=0, Wk=W, sk=e

步骤2：若Wk只有一个元素，则停止，sk是W的最一般合一；

否则，找出Wk的差异集合Dk。

步骤3：若Dk非奇异，Dk中存在元素vk和tk，其中vk是变量符号，并且不出现在tk中，则转步骤4；

否则，算法停止，W是不可合一的。

步骤4：令 sk+1=sk×{tk/vk}，Wk+1=Wk （注：Wk+1=W ）

步骤5：置 k=k+1，转步骤2。

例. 令 W={Q(f(a), g(x)), Q(y, y)}, 求W的mgu。

若令W={Q(f(a), g(x)), Q(y, z)}, W是否可合一？

例令 W= {P(a, x, f(g(y))), P(z, f(z), f(u))}，求出W的mgu。

20、归结原理前要概念：因子

定义（因子）如果子句C中，两个或两个以上的文字有一个最一般合一s，则Cs称为C的因子；

如果Cs是单元子句，则Cs称为C的单因子。

例. C=P(x) Ú P(f(y)) Ú ～Q(x)

令 s＝{f(y)/x}，于是

Cs= P(f(y)) Ú ～Q(f(y))

是C的因子。

21、二元归结式

定义设C1, C2是两个无公共变量！！！的子句(称为亲本子句),

L1, L2分别是C1, C2中的两个文字。

如果L1和～L2有最一般合一s ，则子句

(C1s– {L1s}) È ( C2s– {L2s})

称为C1和C2的二元归结式，L1和L2称为归结文字。

例. 设C1=P(x) ÚQ(x), C2=～P(a) ÚR(x)

将C2中x改名为y。取L1＝P(x), L2=～P(a), s={a/x},

于是(C1s– {L1s}) È ( C2s– {L2s})

＝({P(a), Q(a)}-{P(a)}) È ({
～P(a), R(y)}-{～P(a)})

={Q(a), R(y)}= Q(a)Ú R(y) —-C1和C2的二元归结式.

Note:注意虽然是对P（）合一但是应用这个合一替换的但是Q(x)中的x要跟着一起替换，注意他是不会改变之前的意义的

注意事项：

在谓词逻辑中，对子句进行归结推理时，要注意

的几个问题：

（1）若被归结的子句C1 和C2中具有相同的变元时，需要将其中一个子句的变元更名，否则可能无法合一，从而没有办法进行归结。

（2）在求归结式时,不能同时消去两个互补文字对,消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论。

例.设C1=P(x) Ú～Q(b), C2=～P(a) ÚQ(y)ÚR(z)

求C1和C2的二元归结式.，只能消去一个。不能消去两个，如果该归结式还想继续归结则和其他的子句进行归结！

（3）如果在参加归结的子句内含有可合一的文字,则在进行归结之前,应对这些文字进行合一,以实现这些子句内部的化简。

例. 设

C1=P(x) ÚP(f(y)) ÚR(g(y))

C2=～P(f(g(a))) ÚQ(b)

C1的因子C1’= P(f(y)) ÚR(g(y))。于是C1’和C2的二元归结式，从而也是C1和C2的归结式为

R(g(g(a))) ÚQ(b)

Note：子句中有因子先化简因子此时得到子句的因子表达式然后再与其他的子句中的文字进行合一，使用归结原理

几种常用的归结的改进方式

一、支架集归结

定义子句集S的子集T称为S的支架集，如果（S-T）是可满足的。一个支架集归结是一个不同时属于（S-T）的两个子句的归结。

二、语义归结

想法一

用子句集S的语义解释将S分成两部分S1,S2，要求同一部分里的子句不允许进行归结，这样就阻止了很多无用子句的产生。

S1：S中被I弄假的子句组成的集合；

S2：S中被I满足的子句组成的集合。

上例：若取I={～P,～Q,～R},

(S:(1) ～P∨～Q∨R (2) P∨R (3) Q∨R (4) ～R)

则 S1={(2),(3)} ， S2={(1),(4)}

阻止了(1),(4)的归结。

想法二

使用谓词符号的顺序，要求S1中的子句的归结文字是该子句中最大谓词符号。

上例：若令P>Q>R,

则阻止了(2),(4)之间及 (3),(4)之间的归结。

三、PI演绎：从S出发的一个演绎称为PI演绎，当且仅当演绎中的每一个子句或是S中子句，或是一个PI-归结式。

定义（语义互撞clash）设I是子句集S的一个解释，P是S中谓词符号的一个顺序，有限子句序列 (E1,…,Eq,N) (q³1)称为关于P和I的语义互撞（简称PI-互撞），当且仅当E1, … , Eq, N 满足下面条件：

1. E1, … , Eq在I下为假；(E1, … , Eq称为该互撞的电子)
2. 令R1=N（该互撞的核），对每个 i=1, … ,q，存在Ri和Ei的归结式Ri+1。
3. Ei中的归结文字是Ei中最大谓词符号。
4. Rq+1在I下为假。

于是，Rq+1称为此PI-互撞的PI-归结式。

四、线性归结

定义（线性归结演绎）设S是一个子句集，C0是S中的一个子句。以C0为顶子句，从S到Cn的线性归结演绎是如下一个演绎：
1. 对于 i=0, 1, … ,n-1，Ci+1是Ci和Bi的归结式。
2. 每个Bi或者属于S，或者是一个Cj，其中j< i。

五、输入归结

定义：边子句都属于S的线性归结演绎称为输入归结演绎.

（重点在边子句属于S，就是E部分的都是S中的子句即可）

结论：输入归结在Horn集上完备。

补充：Horn逻辑

定义如果一个子句中最多有一个正文字，则称此子句为Horn子句；由Horn子句构成的子句集，称为Horn集。
三种类型的Horn子句

(1)一个单一原子——常被称为一个“事实”。

(2)一个蕴涵——常被称为一个“规则”——它的前件由一个肯定文字的合取组成，而它的后件由一个肯定的文字组成。

(3)一个否定文字的集合——写成带有一个由肯定文字的合取组成的前件和一个空后件的蕴涵形式。常称为一个“目标”。

六、单元归结

定义：若进行归结的两个亲本子句中，有一个是单元子句或者是一个子句的单元因子，则称这种归结为单元归结。

结论：单元归结对Horn子句集完备

七、锁归结

定义设C是子句，若将C中每一个文字都附上一个整数，则称子句C已配锁。这些整数称为这些文字的锁。
定义如果已配锁子句C中有多于一个的相同文字，则保存这些文字中有最小锁的一个，而将其余的删除。这种作法称为配锁子句中关于相同文字的合并规则。
定义设C1和C2是两个配锁子句，R(C1, C2)是C1和C2的归结式，如果C1和C2中的归结文字分别是C1和C2中带有最小锁的文字，则称R(C1, C2)为C1和C2 的锁归结式
结论：锁归结完备

例. 设S是如下配锁子句集