人工智能基础-25282ai

1、人工智能基础浙江大学计算机学院高 济1谓词演算3）合适公式的标准化 标准化需求常见的基于谓词演算的推理有归结反演和规则演绎。要求以所谓的量词前束范式来表示合适公式， （Q1x1）（Q2x2）（Qkxk ）MM称为母式，不包括任何量词，量词前束，Qi 可以是量词符号 或，xi 是量词的约束变量。归结反演要求母式M标准化为合取范式： M = W1W2Wn Wi = Li1Li2Lim (i=1,2,n) Lij= Pij | Pij (j=1,2,m) / Lij称为文字析取范式（与合取范式对偶）： M = W1W2Wn Wi = Li1Li2Lim (i=1,2,n) Lij= Pij | Pi

2、j (j=1,2,m) 3）合适公式的标准化合取范式的标准化过程应用合适公式性质将公式逐步转化对转化过程步骤的顺序并无严格的规定，遵从一个合理顺序可以降低化简的困难和减少差错。一个较合理的化简过程，分8个步骤：例子： 2 H域和海伯伦定理 定理的自动证明一般表示形式为： F1, F2, ,Fn|= WF1, F2, ,Fn都是合适公式，公式间隐含合取关系，构成一个公式集（也称公理集或事实集），W是待证明的一个合适公式（也称为定理或目标公式）。证明的方法可分二大类：演绎法直接证明F1F2Fn W为永真；从而，当公式集为真时，定理W成立。反证法间接证明(F1F2Fn W)为永假。即证明 F1F2F

3、n W的永假性，即F1, F2, ,Fn W是一个矛盾集。海伯伦提出的H域（海伯伦域）和海伯伦定理为自动定理证明奠定了理论基础：将合适公式标准化为子句集，引入H域（即海伯伦域），从理论上给出了证明子句集(从而合适公式)永假(即不可满足)的可行性及方法。鲁宾逊提出的归结原理使机器定理证明成为可能。 2 H域和海伯伦定理1）子句和子句集 子句仅由文字的析取构成的合适公式（文字：原子谓词公式或其取反）。 合取范式子句的合取。子句集指示合取范式，子句间隐含合取关系。例子： 变量换名P(A)P(y)Q(A,z)P(z,g(z)P(f(A,y)Q(A,z)P(z,g(z) P(A)， P(y)Q(A,z)

4、P(z,g(z)， P(f(A,y)Q(A,z)P(z,g(z)P(A)， P(y1)Q(A,z1)P(z1,g(z1)，P(f(A, y2)Q(A, 2)P(z2,g(z2) 重要性质一个合适公式F化简为标准化的子句集S时， S的不可满足成为F永假的充分必要条件。 F和S并非等价F的化简过程中，为消除存在量词而引入了Sklem函数，使子句集S只是F的一个特例。可以证明F和S在永假性上等价建立海伯伦定理的重要基础。 2 H域和海伯伦定理2）H域(海伯伦域）H域的迭代构造：（S：子句集，D：S的某个论域） (1) 令H0 是S中出现的所有常量的集合，若S中未出现常量，就任取常量aD,并令H0 =

5、a。 (2) 令Hi+1 = Hi出现于S中的函数在Hi上的所有实例,i=1,2,；形如f(x1, x2, , xn)的函数的实例通过让xj = kj Hi来形成（j=1,2,n）。Hi可以迭代扩展到H，称为海伯伦域，简称H域（一个可数无穷集）。 例子2）H域(海伯伦域） 2）H域(海伯伦域）H域上的原子谓词公式实例集A（为研究子句集的永假性）: A=所有出现于S中原子谓词公式的实例。命题（不包含变量）其实例就是其本身；P(t1, t2, tm)其实例通过让ti=kiH(即H)来形成；例子：子句集S=P(x)R(f(x),Q(y,g(y) A=P(a),R(f(a),Q(a,g(a),P(f(

6、a),R(f(f(a),； H=a，f(a),g(a), f(g(a),g(f(a), f(f(a), g(g(a), 基原子A中的元素，是原子命题；A称为基原子集。 2）H域(海伯伦域）I*子句集在H域上的一个解释，通过基原子集来建立：给集中的每个基原子指派一个真值（T或F）。 以基原子自身指示取真值T，前面加取反符号指示取真值F, 例子：（子句集S=P(x)R(f(x),Q(y,g(y)） I1* =P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a) I2* =P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a) I3* =P(a),R(f(a),

7、Q(a,g(a), P(f(a),R(f(f(a) A=P(a),R(f(a),Q(a,g(a),P(f(a),R(f(f(a),；定理对于子句集S的任一可能论域D上的任一解释I,总能在S的H域上构造一个相应的解释I*,使子句集具有相同的真值。子句集不可满足确定子句集S在H域上的所有解释都不满足。 2 H域和海伯伦定理3）H域上解释的语义树 用语义树来形象地描述子句集在H域上的可能解释 命题集基原子集是有限集:每个基原子只可能有二个真值（T或F)，容易画出完整的语义树。例子只包含原子命题公式P、Q 和R的子句集：基原子集A=P、Q、R，语义树。 从树根节点n0到叶子节点n的 路径指示一个解释记

8、为 I(n)，表示为路径上标记的 集合，每个标记是一个文字。I(n32)=P,Q, R从树根 节点n0到叶子节点n32的路径。一般的子句集，H是可数无穷集，语义树可能成为一棵无穷树。 3）H域上解释的语义树 封闭语义树子句集不可满足 时，语义树有穷，语义树上的所 有路径都分别对应一个导致子句 集不满足的解释。 例子： 子句集S =P(x)Q(f(x), P(a), Q(y) H=a,f(a),f(f(a), A=P(a),Q(a),P(f(a)， Q(f(a), 3）H域上解释的语义树基子句变量用H域中元素取代后的子句，即基文字（基原子或其取反）或基文字的析取。 当x=a时，从子句P(x)Q(f(x)生成基子句 P(a)Q(f(a)。 语义树中每一导致子句集S不满足的路径（相应于H域上一解释）都至少引起一个基子句真值为F。 I(n42)=P(a), Q(a), P(f(a),Q(f(a) 就引起了基子句P(a)Q(f(a)真值为F。当建立起一棵封闭语义树时，实际上也建立了一个由有限个不可同时满足的基子句构成的集合S S = P(a)Q(f(