《人工智能 搜索推理技术消解原理》由会员分享，可在线阅读，更多相关《人工智能 搜索推理技术消解原理（147页珍藏版）》请在金锄头文库上搜索。
1、人 工 智 能 Artificial Intelligence (AI),第3章 搜索推理技术,3.1 图的搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 与或树搜索（补充） 3.5 博弈树搜索（补充） 3.6 消解原理,3.6 消解原理 3.6.1 子句集的求取 3.6.2 消解原理（补充） 3.6.3 消解推理规则 3.6.4 含有变量的消解式 3.6.5 消解反演求解过程 3.6.6 Horn子句集消解（补充） 3.6.7 Prolog 语言简介 （补充）,3.6 消解原理,第2章中介绍： 谓词逻辑的基本知识 合一算法（求最一般的一致置换或合一者mgu） 本节： 消解原理（或者归
2、结原理）,3.6.1 子句集的求取 如何将谓词公式转化为子句集，作为合一算法的输入（公式集） 3.6.1.1 若干基本概念 3.6.1.2 子句集的求取,3.6.1.1 若干基本概念 1 自由变元与约束变元 2 前束范式与前束合取范式 3 斯科伦（Skolem）范式 4 子句集,设，是一个谓词公式，将量词记作（即 或 ）,1 自由变元与约束变元,如果中包含部分公式 (x)，则中变元 x 的一切出现都称为 x 在 中的约束出现，相应地称 x 为约束变元（哑元、虚构变量、约束变量）,约束变元,中不在任何量词作用域内的变元 x ，称为变元 x 在 中的自由出现，相应地称 x 为自由变元（自由变量）,
3、自由变元：,量词的作用域（辖域）是直接跟在它后面的公式 如果有括号，则是括号里的公式 如果没有括号，则是最短的完整公式,说明：,例1： x ( P(x) y (R(x, y) ) x , y 都是约束变元 例2： x ( P(x) (R(x, y) ) x 是约束变量，y 是自由变元,改名：将谓词公式中一个变元名改成另一个变元名，但是要求改名后的公式与原公式意义相同（真假值相同） 原则：改成的新的变元名一定是量词作用域中没有出现过的变元名（包括约束变元和自由变元）,约束变元的改名或变量的标准化,例3： x ( P(x) (R(x, y) 除了 y 外，可以将 x 改成任何变元名 例4： x P
4、(x) Q(y) 可以改成任何变元名，包括 y（建议不要用）,2 前束范式与前束合取范式,定义：设谓词公式具有形式： (1x1)(nxn) M 其中：i ( i = 1 , , n ) 是 或 M 是不包含量词的谓词公式 则，称是前束范式 称 (1x1)(nxn ) 为前束 称 M 为母式,定义：设谓词公式是一个前束范式，如果的母式具有形式： （M11M12M1 n1） （M21M22M2 n2） (Mm1Mm2Mm nm） 其中，M i j 是原子公式或其非，则称是前束合取范式。相应地有前束析取范式,前束范式： (x) (y) (z)(P(x)Q(y)R(z) 前束合取范式（交换律、分配律）
5、 (x) (y) (z)(R(z)P(x)(R(z)Q(y),例：,3 斯柯伦范式,定义：前束中不含存在量词的前束范式称为斯柯伦范式,若xk (1kn )左边没有全称量词，则取不在母式中出现的常量替代母式中的所有 xk ，并删除前束中的 xk,消去存在量词的规则 或 前束范式化成斯柯伦的步骤是：,若 xk (1 kn )左边有全称量词 (xs1) (xs2)(xsr) ( 1r，1s1s2srk) 则，取不在母式中出现的 r 阶函数 fr (xs1, xs2,xsr)替代母式中的所有xk ，并删除前束中的 xk,反复使用上述两条规则，消除前束中的所有存在量词，即得到斯柯伦范式 其中，引入的函数
6、称为斯柯伦函数,x y z u v w A(x,y,z,u,v,w) (用a替代x，删除x) = y z u v w A(a,y,z,u,v,w) （用f(y,z)代替u，删除u） = y z v w A(a,y,z, f(y,z),v,w) （用h(y,z,v)代替w，删除w） = y z v A(a,y,z, f(y,z),v,h(y,z,v),例：求斯柯伦范式,说明： 一个谓词公式的斯科伦范式不是唯一的，尽可能将斯科伦函数取得简单一点,化成前束范式 化成前束合取范式 化成斯科伦范式（斯科伦函数的变元较多）,对于谓词公式：=12,正常的做法：,将1、2 分别化成前束范式 对1、2 分别求出
7、斯柯伦范式1、2 将12 的量词左移得到的斯柯伦范式（即前束范式）,简化的做法：,好处：简化斯科伦函数,=12, = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = y1 x1 x2 y2 (P( x1 , y1 ) Q( x2 , y2 ) （前束合取范式） = x1 x2 (P( x1 , a1 ) Q( x2 , f(x1,x2) ),例：正常化法, = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = x1 P( x1 , a1 ) x2 Q( x2 , f(x2) ) （先分别化成斯科伦范式） = x1 x2 (P( x1
8、 , a1 ) Q( x2 , f(x2) ) (前束合取范式）,简化化法,4 子句集,原子命题是原子公式 如果t1,tn(n1)是项，P是谓词，则P(t1,tn)是原子公式 其它表达式都不是原子公式,原子公式的定义：, 文字（或基本式）：“原子公式”或者“原子公式的非” 子句：一个或多个基本式的 析取,子句的定义：,一个谓词公式具有形式： ( x1 )( xn )( c1c2cm ) 其中，ci ( i = 1, , m )为子句 x1, , xn 是子句中出现的约束变元 则，称谓词公式具有子句形式,子句形式的定义：,闭公式：不含自由变量的谓词公式 谓词公式的子句形式是闭公式 母式为子句的合
9、取范式 前束中只有全称量词，无存在量词,说明：,若谓词公式 具有子句形式，记 S = ( c1 , c2 , , cm ) 则，称 S 为谓词公式的子句集,( x1 )( xn )( c1c2cm ),子句集的定义：,为了便于消解推理，要通过改名使得一个变量符号不出现在一个以上的子句中，即每一个子句具有不同的变量,说明：,子句形式： (x) (y) (z)(R(z)P(x)(R(z)Q(y) 子句集： R(z)P(x) , R(z)Q(y) R(z1)P(x1) , R(z2)Q(y1) （改名）,例：,3.6.1.2 子句集的求取,子句集的求取（将谓词公式化成子句集）有两种方法，其形式上会有
10、差别，但是其逻辑意义是相同,1、将谓词合适公式转化为前束合取范式 消去“蕴含”和“等价”连结词 将“”连结词直接作用到原子公式前 约束变元改名，使所有的约束变元名都不相同 将量词移到谓词公式的左边，得到前束范式 将前束范式化成前束合取范式,方法1（离散数学、数理逻辑采用的方法）：,2、将前束范式转化为斯柯伦（Skolem）范式 得到斯科伦范式 3、将斯柯伦范式转化为子句集 消去前束（全称量词） 消去合取连词 变量改名，得到子句集,为了使斯科伦函数更简单一些，可以将合取关系的各个谓词公式分别先分成前束范式、斯科伦范式，再综合起来化成前束范式、前束合取范式（后面的定理证明部分就采用了这一种化法）,
11、说明：, 消去“蕴含”和“等价”连结词 减少“非”连结词的辖域（将“”连结词直接作用到原子公式前） 对变量标准化（约束变元改名）,方法2 （教材采用的方法）：,消去存在量词（引入斯科伦函数） 化成前束范式 将母式化成合取范式 消去全称量词 消去合取连结词 更改变量名，得到子句集,两者的差别：在于三步 方法 1 是先得到前束合取范式，再化成斯科伦范式 方法 2 是先引入斯科伦函数消去存在量词，再化成前束合取范式,三步的结果： 得到不含存在量词的前束合取范式,谓词公式 = 全称量词串 + 合取范式的母式,注：母式中的斯科伦函数变元个数可能不相同,求取子句集的步骤：,使用的公式： AB = AB A
12、B = (AB)(B A), 消去“蕴含”和“等价”连结词,将“”连结词直接作用到原子公式前，使得每一个“非”联结词最多只能作用于一个原子公式（谓词符号）, 减少“非”连结词的辖域,(A) A (AB) = AB (AB) = AB (x)A(x) = (x)(A(x) (x)A(x) = (x)(A(x),使用的公式是：,说明： 到现在为止，谓词公式只包含三种连结词 “合取”： “析取” “非” ,对约束变元改名，使得所有的约束变元名都不相同，保证每一个量词都有自己唯一的约束变元, 对变量标准化,以一个斯科伦函数代替每一个带存在量词的约束变元，斯科伦函数的变元是（左边）带全称量词的约束变元，
13、而且这些全称量词的辖域必须包括被消去的存在量词的辖域, 消去存在量词,消去存在量词的规则：,如果要消去的存在量词不在任何一个全称量词的辖域内，则用常量来代替 斯科伦函数和常量的符号必须是未在谓词公式出现过的符号, = y1 x1 P( x1 , y1 ) x2 y2 Q( x2 , y2 ) = x1 P( x1 , a1 ) x2 Q( x2 , f(x2) ) （引入斯科伦函数，消去存在量词， x1 的辖域不包含y2 的辖域）,例：,将全称量词移到谓词公式的左边，使得每一个量词的辖域包括该量词后面的整个谓词公式, 化成前束范式,(x)A(x)R = (x) (A(x)R) (x)A(x)R
14、 = (x) (A(x)R) (1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z) (1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z) 说明：A(x), B(z), R中允许含有与x，z不同的自由变量,使用的规则：,前束范式 （前束） （母式）,全称量词串,无量词公式, 将母式化成合取范式,利用分配律将前束范式化成前束合取范式： P(QR) = (PQ)(PR) （析取 合取）,谓词公式已经化成了前束合取范式，且只包含全称量词，此时全称量词的次序也不重要了，所以可以消去全部量词（即前束、前缀）, 消去全称量词, 消去合取连结词 ,母式为合取范式：
15、A1 A2 An 消去合取连结词，得到子句集： A1 , A2, , An 子句：基本式（文字）的析取（只含）,更改变元名，使得一个变量符号不出现在一个以上的子句中，即不同的子句包含不同的约束变元名, 更换变元名,(x)A(x) (x)B(x) = (x)A(x)(x)B(x) （消去“蕴含”） = (x) (A(x)(x)B(x) （“非”直接作用谓词符号） = ( x) (A(x) ) (z) B(z) (改名) = A(a)B(b) （消去存在量词） 子句集= A(a)B(b) 注：两种方法的结果相同,例1：,仔细分析量词的辖域,(x) (y)( (z)(A(x,z)A(y,z) (u)B(x,y,u) =(x) (y)( (z)(A(x,z)A(y,z)(u)B(x,
