研究生课程 人工智能原理 期末考试试题

AI往年考试试题解析

一、子句集及其化简

不包含任何文字的子句称为空子句。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的。空子句一般被记为NIL。（证明题会用到此结论）

化简步骤：

（l）消去连接词“→”

反复使用如下等价公式：

P →Q<=>?P V Q，即可消去谓词公式中的连接词“→”。 例如公式

(?x)((?y)P(x,y) →?(?y )(Q(x,y) → R(x,y))) 经等价变化后为

(?x)(?(?y)P(x,y) V?(?y )(?Q(x,y)∨R(x,y)))

(2) 减少否定符号的辖域（即把否定符号移到紧靠谓词的位置上） 反复使用双重否定律?(?P) <==>P

狄·摩根定律?（P∨Q）<==>?P∧?Q ?(P∧Q）<==>?P∨?Q

量词转换律?(?x）P<==>（?x）?P ，?（?x）P<==>（?x）?P

将每个否定符号“?”移到仅靠谓词的位置，使每个否定符号最多只作用于一个谓词上。

例如，上步所得公式经本步变换后为

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

（3）对变元标准化

在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字。 例如，上步所得公式经本步变换后为

(?x)((?y)?P(x,y)∨(?z )( Q(x,z)∧?R(x,z)))

（4）化为前束范式

化为前束范式的方法是把所有量词都移到公式的左边，并且在移动时不能改变其相对顺序。由于第（3）步已对变元进行了标准化，每个量词都有自己的变元，这就消除了任何由变元引起冲突的可能，因此这种移动是可行的。 例如，上步所得公式化为前束范式后为:

(?x) (?y) (?z )(?P(x,y)∨( Q(x,z)∧?R(x,z)))

（5）消去存在量词

消去存在量词时，需要区分以下两种情况。 若存在量词不出现在全称量词的辖域内（即它的左边没有全称量词），只要用一个新的个 体常量替换受该存在量词约束的变元，就可消去该存在量词。 若存在量词位于一个或多个全称量词的辖域内，例如 (?x1)(?x2)??(?xn)(?y)P(x1,x2,??,xn,y)

则需要用 Skolem函数y=f（x1,x2,??,xn）替换受该存在量词约束的变元，然后再消去该存在量词。

例如，在上步所得公式中存在量词（?y)和（?z）都位于（?x）的辖域内，因此都需要用Skolem函数来替换。设替换y和z的Skolem函数分别是f（x）和g（x），则替换后的公式为:

(?x) (?y) (?z )(?P(x,f（x）)∨( Q(x,g（x）)∧?R(x,g（x）)))

1

（6）化为Skolem标准形

Skolem标准形的一般形式为

(?x1)(?x2)??(?x2)M(x1,x2,??,xn)

其中，M（x1,x2,??,xn）是Skolem标准形的母式，它由子句的合取所构成。 把谓词公式化为Skolem标准形需要使用以下等价关系 P ∨（Q∧R）<=>（P∨Q）∧（P∨R） 例如，上步所得的公式化为Skolem标准形后为

（?x）((?P(x,f(x))∨Q(x,g(x)))∧(?P(x,f(x))∨?R(x,g(x)))) (7) 消去全称量词

由于母式中的全部变元均受全称量词的约束，并且全称量词的次序已无关紧要，因此可以省掉全称量词。剩下的母式，仍假设其变元是被全称量词量化的。

例如，上步所得公式消去全称量词后为

((?P(x,f(x))∨Q(x,g(x)))∧(?P(x,f(x))∨?R(x,g(x)))) （8）消去合取词

在母式中消去所有合取词，把母式用子句集的形式表示出来。其中，子句集中的每一个元素都是一个子句。

例如，上步所得公式的子句集中包含以下两个子句 ?P(x,f(x)) ∨Q(x,g(x)) ?P(x,f(x)) ∨?R(x,g(x)) （9）更换变元名称

对子句集中的某些变元重新命名，使任意两个子句中不出现相同的变元名。由于每一个子句都对应着母式中的一个合取元，并且所有变元都是由全称量词量化的，因此任意两个相同子句的变元之间实际上不存在任何关系。这样，更换变元名是不会影响公式的真值的 例如，对上步所得公式，可把第二个子句集中的变元名x更换为y，得到如下子句 ?P(x,f(x)) ∨Q(x,g(x)) ?P(y,f(y)) ∨?R(y,g(y))

真题1：将(?x)(?y)(?z)((?P(x,y)∧Q(x,z)∨R(x,y,z))化成子句集。（15分）

解析：根据步骤（5）?(?x) (?y) (?z )((?P(x,f(x))∧Q(x,g(x)))∨R(x,f(x),g(x))) 根据步骤（6）、（7）?子句集为：(?P(x,f(x))∨R(x,f(x),g(x)))∧(Q(x,g(x)∨R(x,f(x),g(x))) 根据步骤（8）、（9）?子句集为：?P(x,f(x))∨R(x,f(x),g(x))和Q(y,g(y)∨R(y,f(y),g(y)) 二、Herbrand域

H 域定义：设S为论域D上的一个子句集，则按下述方法构造的域H∞称为海伯伦域，简记为H域。

（l）令H0是S中所有个体常量的集合，若S中不包含个体常量，则可任取一常量a∈D，并令H0={ a } ; （2）令Hi?1= Hi∨｛ S中所有n元 函数 f(x1,x2,??,xn)|xj是Hi中的元素｝，其中，i=0,1,2,??;j=1,2,??,n。

真题2：已知S={P(f(x),a,g(y),b},求该公式的Herbrand域。（15分）

解析：此例中有两个个体常量a、b和两个函数f(x)、g(y)，依H域的定义有 H0=｛a,b｝

H1=｛a,b｝∨｛f(a), f(b),g(a),(b)｝=｛a, b, f(a), f(b),g(a),g(b)｝

H2=｛a, b, f(a), f(b),g(a),g(b)｝∨ {f(f(a)), f(f(b)), f(g(a)), f(g(b)), g(f(a)), g(f(b)), g(g(a)), g(g(b))}

=｛a, b, f(a), f(b),g(a),g(b),f(f(a)), f(f(b)), f(g(a)), f(g(b)), g(f(a)), g(f(b)), g(g(a)), g(g(b))} ??

H∞=｛a, b, f(a), f(b),g(a),g(b),f(f(a)), f(f(b)), f(g(a)), f(g(b)), g(f(a)), g(f(b)), g(g(a)),

2

g(g(b)),??}

三、归结原理

归结原理基本思想是：首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S’。然后设法检验子句集S’是否含有空子句，若含有空子句，则表明S’是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。

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

例1：设C1=?P∨Q，C2= ?Q，C3=P，求C1、C2、C3的归结式C123。 解：若先对C1、C2归结，可得到 C12=?P

然后再对C12和C3归结，得到 C123=NIL。

在命题逻辑中，已知F，证明G为真的归结反演过程如下： ①否定目标公式G，得?G；

②把?G并入到公式集F中，得到｛F，?G｝； ③把｛F，?G｝化为子句集S；

④应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。

谓词逻辑的归结原理：设C1和C2是两个没有公共变元的子句，L1和L2分别是C1和C2中的文字。如果L1和?L2存在最一般合一σ ，则称 C12=（C1σ －｛L1σ ｝）∪（C2σ － ｛L2σ ｝） 为C1和C2的二元归结式，而L1和L2为归结式上的文字。

这里之所以使用集合符号和集合的运算，目的是为了说明问题的方便。即先将子句Ciσ和Liσ写成集合的形式，并在集合表示下做减法和并集运算，然后再写成子句集的形式。

例2：设 C1=P（a）∨ R（x），C2=?P（y）∨Q（b），求 C12。 解：取L1=P（a）， L2=?P（y），则L1和?L2的最一般合一是σ =（a／y）根据定义，可得

C12=（C1σ －｛L1σ ｝）∪（C2 －｛ L2σ ｝） =（｛P(a)， R(x)｝—｛P(a)｝）∪（｛?P(a)， Q(b)｝—｛?P(a)｝ =｛R(x)｝ ∪｛Q(b) ｝ =｛R(x)，Q(b) ｝= R(x) ∨ Q(b) 真题3：用归结原理证明G是否为F1和F2的逻辑结论。（15分）

F1：(?x)(P(x)?(Q(x)∧R(x))) F2：(?x)(P(x)∧S(x)) G：(?x)(R(x)∧S(x))

解析：假设结论G为假，即?G为真，将?G加入公式集，并化为子句集(具体化简步骤参考第一部分内容，本题假定替换?符号时使用a，替换?符号时用使用x、y，替换符号只是形式上的问题，采用其他符号替换亦可）。

S= ｛(?x)(P(x)?(Q(x)∧R(x)))，(?x)(P(x)∧S(x))，?(?x)(R(x)∧S(x))｝

（1）?P(x)∨Q(x) （2）?P(y)∨R(y) （3）P(a) （4）S(a) （5）?G:?R(x)∨?S(x)，其中（1）（2）是由F1化成的子句，（3）（4）是由F2化成的子句，（5）为?G。

（6）对于（4）（5）采用(如例2的办法)归结原理，设L1=?S(x)，L2=S(a)，则L1与?L2

3

的最一般合一是σ =（a／x）

C12=（｛?R(x)，?S(x)｝—｛?S(x)｝）∪（｛S(a)｝—｛S(a)｝=?R(x) （7）对（2）（6）进行归结并替换变元，C12=?P(a)

（8）NIL （3）（7）进行归结。

注意：①考试答题过程中不必写出取L1、L2及换元的过程，只需写出归结后的结果即可。

②归结过程中，并不一定所有的字句都应用到，只要归结出NIL即可，比如本题目中的（1）字句就并没有应用到。

③如果实在不会，就随便写出一个子句的非语句，然后就说跟此语句结合产生NIL，所以结论成立，这就是所谓的自己编造条件。（不建议使用） 四、产生式表示法、语义网络表示法与框架表示法

例：产生式表示法与框架表示法的区别

真题4：比较语义网络表示法与框架表示法的区别与联系。

解析：框架的表示结构与语义网络节点的表示结构接近，只是由于前者引入了侧面描述，使框架比节点具有更丰富的表示结构。所以有的研究者就把语义网络和框架表示法统称为槽与填充值（slot and filler）表示法。框架系统就像语义网络那样，框架的某些槽的侧面值可以是其它框架，从而能建立起节点是框架的网络。不过这两种表示法在使用上还是存在语义差别的，即框架表示法更强调表示事物的内部结构（利用框架的丰富表示结构），而语义网络更强调表示事物间的关系。

真题5：已知（a）导弹是一种飞行的攻击敌方目标的武器。

（b）导弹分为战略导弹和战术导弹，战略导弹有巡航式导弹和弹道式导弹两种，而战术导弹都是巡航式的。

（c）战术导弹可以用路基发射、飞机发射和军舰发射。 请分别用产生式、框架结构表示出上述内容。

解析：产生式r1：if是武器and自动飞行and攻击敌方目标then导弹。 产生式r2：if是战略导弹or战术导弹then导弹。

产生式r3：if是巡航式导弹or弹道式导弹then战略导弹。 产生式r4：if战术导弹then巡航式。

产生式r5：if路基发射or飞机发射or军舰发射then战术导弹。 框架名：<战术导弹> part-of：<导弹> 属性：巡航式 发射方式：路基发射、飞机发射、军舰发射。

框架名：<战略导弹> part-of：<导弹> 属性：巡航式、弹道式 框架名：<武器> 属性：攻击敌方目标。 框架名：<导弹> ISA：武器。

4

注意：本题只要掌握思路，考试时候随便写出几条即可，不用刻意去背答案。

五、启发式搜索与代价树

没啥说的，直接画出代价树写结论吧。

真题5：下图是一个交通图，设A城是出发地，E是目的地，边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。（画出广度搜索代价树）。（15分）

C 10 E 3

A 3 2 5 4 7

B 4 D 解析： A(S) 4 3 7 B1 C1 D1 3 4 2 10 5 C2 D2 D3 E1 E2 10 5 5 (13) (12)

E3 E4 E5 (17) (13) (10) SG 故最小费用路线为A?C?D?E，且费用为10。 六、A算法（启发式搜索算法）

用来估计节点重要性的函数称为估价函数。估价函数f（n）被定义为从初始节点S0出发，经过节点n到达目标节点SG的所有路径中最小路径代价的估计值。它的一般形式为 f（n）=g（n）＋h（n）

其中，g（n）是从初始节点S0到节点n的实际代价；h（n）是从节点n到目标节点S0的最优路径的估计代价。对g（n）的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0,得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到g（n）的值。对h（n）的值，则需要根据问题自身的特性来确定，它体现的是问题自身的启发性信息，因此也称h（n）为启发函数。

例：八数码难题。估价函数为:f（n）=d（n）＋W（n）

其中，d（n）表示节点 n在搜索树中的深度； w（n）表示节点 n中“不在位”的数码个数。请计算初始状态S0的估价函数值f（S0）。 解：在本例的估价函数中，取g（n）=d（n），h（n）=W（n）。它说明是用从S0到n的路径上的单位代价表示实际代价，用n中“不在位”的数码个数作为启发信息。一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。 对初始节点S0，由于d（S0）= 0，若W（S0）= x，因此有 f（S0）=0＋x=x

全局择优搜索：

每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展，根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序，直到求出结果。由于上述算法要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法中先取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。

注意：书中给出的搜索过程较为抽象，大家只要知道每次都选择估价最小的点就可以了，

5

本文来源：https://www.bwwdw.com/article/n09d.html