·12· 智能系统学报 第2卷 找到最小的i<n使得Em<E+1,然后可以用背景知 S4=1p20;p(3(x)→p(x} 识P(E)把GOL EM系统应用到U,E,上.令 … P(En)为结果」 式中： 定理2给定例子集合E,P(日是简单的 片=fp(50),320}, 证明根据前序的定义，当一个子句π列举在 为=fp(S0),p0}A(p(30),p0y, P(E)中时，π的头在E中总是有最低优先级.这就 lgg(i,)=px),p(3(x)}. 保证了π是简单的. 从上述可知，该实例说明GOL EM系统不是极 这样，可以得出如下定理」 限正确的，且对例子的顺序是敏感的 定理3P是收敛且极限正确的.即给定一个 正例集合的增长序列{E},1){P(Ea}是有集合论 3优先GOL EM系统 极限的Horn逻辑程序序列：2)limP(E)是关于 笔者提出了关于Horn逻辑程序的假设，用 limE.极限正确的. 以保证Horn逻辑程序序列的极限的最小Her 证明根据前文的讨论只需要证明1).根据前 brand模型就是逻辑程序的最小Herbrand模型的 序<的定义，可知<是良定的.给定一个实例e,只 极限，且前一个极限的最小Herbrand模型关于 存在有限多个e使得e'<e.假设对某n,e是在En Horn逻辑程序序列是不变的 中可列举的，则子句π产生.对n'>n,只有当在E 定义2一个子句中，若每个出现在子句体中 中实例e'<e可列举时，r才能从P(E)中提取.这 的子项都出现在该子句头中，则称该子句是简单的 样对无限多n,π不能在P(E)中列举且从P(E)中 一个逻辑程序，若其中的每个子句都是简单的，则称 提取出.因此{P(E)}具有集合论极限 该逻辑程序是简单的 前文的假设要求Horn逻辑程序是简单的.给 4结束语 定例子集合E,将GOL EM系统修改为新的算法P 当输入例子集合E时，优先的GOL EM系统产 使得P(E是简单的， 生一个简单的Horn逻辑程序P(E).简单Horn逻 先定义文字上的优先关系<假设有2个文字1 辑程序有很多好的普通的Horn逻辑程序没有的性 和1'，如果1中出现的每个子项都在1中出现，则说 质.优先的GOL EM系统是基于例子的语法性质， 1比1优先级高，记做1<1 即，文字上的优先序<，该序可以使优先GOL EM 命题1<是一个前序，即<是自反的和传递 系统在多种应用中变得有用 的 将来的工作可以基于一个逻辑语言的项或公式 优先GOL EM系统： 上定义的距离.这种距离定义可以采用Fitting或 假设给定一个逻辑程序「（即一个背景知识）和 Nienhuys-Cheng给出的距离.然后可以定义项或公 2个例子(2个基原子)E和丘使得THE和 式的Cauchy序列.然后根据例子集合的Cauchy序 HE成立.构造一个与T有关的E:和E的 列和Horn逻辑程序定义收敛性和极限正确性.推 1ggC,有「∧CE∧B且C在E,和推导中用 测优先GOL EM系统还满足定义在Cauchy序列上 了一次令T={pi,pm,… 的收敛性和极限正确性 定义 G=((gg Vy Vei) 参考文献： G=(g1VgV…yVa, [1 ]BERGADANO F,GUNETTI D.Inductive logic program- 集合C=lggG,G),其中，，为带序 ming:from machine learning to software engineering <的集合{p,p,E},即，对每个i有{，， [M].London:The MIT Press,1996. a}=fp,,Ei},且a本g;类似地可定义 [2]DA HR M.Deductive eatabases:theory and applications [M].Boston:International Thomson Computer Press, {q1,9取，a} 1997. 序列上的优先GOL EM系统： [3]FITTIN G M.MeETRIC methods,three examples and a 给定例子集合序列{En},在步骤n输入Em.若 theorem[J ]J of Logic Programming,1994,21:113 对任意i<n,有E。大E,则可用GOL EM系统直接 127. 产生一个Horn逻辑程序，记做A(E):否则，可以 [4]LI W.An open logic system[J ]Science in China (Scien- 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net… S3 k+i = { p (s 6 k+4 - 2 i (0) ) ; p (s 2 ( x) ) →p ( x) } , … 式中 : γ1 = { p (s 4 (0) ) ,s 2 (0) ) } , γ2 = { p (s 4 (0) ) , p (0) } ∧{ p (s 2 (0) ) , p (0) } , lgg (γ1 ,γ2 ) = { p ( x) , p (s 2 ( x) ) } . 从上述可知 ,该实例说明 GOL EM 系统不是极 限正确的 ,且对例子的顺序是敏感的. 3 优先 GOL EM 系统 笔者[7 ] 提出了关于 Horn 逻辑程序的假设 ,用 以保证 Horn 逻辑程序序列的极限的最小 Her2 brand 模型就是逻辑程序的最小 Herbrand 模型的 极限 ,且前一个极限的最小 Herbrand 模型关于 Horn 逻辑程序序列是不变的. 定义 2 一个子句中 ,若每个出现在子句体中 的子项都出现在该子句头中 ,则称该子句是简单的. 一个逻辑程序 ,若其中的每个子句都是简单的 ,则称 该逻辑程序是简单的. 前文的假设要求 Horn 逻辑程序是简单的. 给 定例子集合 E ,将 GOL EM 系统修改为新的算法 P 使得 P ( E) 是简单的. 先定义文字上的优先关系 ; . 假设有 2 个文字 l 和 l′,如果 l 中出现的每个子项都在 l′中出现 ,则说 l 比 l′优先级高 ,记做 l ; l′. 命题 1 ; 是一个前序 ,即 ; 是自反的和传递 的. 优先 GOL EM 系统 : 假设给定一个逻辑程序Γ(即一个背景知识) 和 2 个例子 ( 2 个基原子) Ε1 和 E2 使得 Γ|2/ E1 和 Γ|2/ E2 成立. 构造一个 与 Γ 有关的 E1 和 E2 的 lgg C,有Γ∧C|2E1 ∧E2 且 C 在 E1 和 E2 推导中用 了一次令Γ= { p1 , …, pn , …} . 定义 C1 = ( ( q1 ∨ q2 ∨…) ∨e1 ) , C2 = ( ( q′1 ∨ q′2 ∨…) ∨e2 ) , 集合 C = lgg ( C1 , C2 ) ,其中 q1 , q2 , …, e1 为带序 ; 的集合{ p1 , p2 , …, E1 } , 即 , 对每个 i 有{ q1 , q2 , …, e1 } = { p1 , p2 , …, E1 } ,且 e1 ≮qi ; 类似地可定义 { q′1 , q′2 , …, e2 } . 序列上的优先 GOL EM 系统 : 给定例子集合序列{ En } ,在步骤 n 输入 En . 若 对任意 i < n ,有 En ≮Ei ,则可用 GOL EM 系统直接 产生一个 Horn 逻辑程序 ,记做 A ( En ) ; 否则 ,可以 找到最小的 i < n 使得 En ; Ei + 1 ,然后可以用背景知 识 P ( Ei ) 把 GOL EM 系统应用到 ∪n j > i Ej 上. 令 P( En ) 为结果. 定理 2 给定例子集合 E, P( E) 是简单的. 证明 根据前序的定义 ,当一个子句π列举在 P( E) 中时 ,π的头在 E 中总是有最低优先级. 这就 保证了π是简单的. 这样 ,可以得出如下定理. 定理 3 P 是收敛且极限正确的. 即给定一个 正例集合的增长序列{ En } , 1) { P( En ) } 是有集合论 极限的 Horn 逻辑程序序列; 2) limn→∞ P ( En ) 是关于 limn→∞ En极限正确的. 证明 根据前文的讨论只需要证明 1) . 根据前 序 ; 的定义 ,可知 ; 是良定的. 给定一个实例 e ,只 存在有限多个 e′使得 e′; e. 假设对某 n , e 是在 En 中可列举的 ,则子句π产生. 对 n′> n ,只有当在 En 中实例 e′; e 可列举时 ,π才能从 P( En ) 中提取. 这 样对无限多 n ,π不能在 P ( En ) 中列举且从 P( En ) 中 提取出. 因此{ P( En ) }具有集合论极限. 4 结束语 当输入例子集合 E 时 ,优先的 GOL EM 系统产 生一个简单的 Horn 逻辑程序 P( E) . 简单 Horn 逻 辑程序有很多好的普通的 Horn 逻辑程序没有的性 质. 优先的 GOL EM 系统是基于例子的语法性质 , 即 ,文字上的优先序 ; ,该序可以使优先 GOL EM 系统在多种应用中变得有用. 将来的工作可以基于一个逻辑语言的项或公式 上定义的距离. 这种距离定义可以采用 Fitting 或 Nienhuys2Cheng 给出的距离. 然后可以定义项或公 式的 Cauchy 序列. 然后根据例子集合的 Cauchy 序 列和 Horn 逻辑程序定义收敛性和极限正确性. 推 测优先 GOL EM 系统还满足定义在 Cauchy 序列上 的收敛性和极限正确性. 参考文献 : [ 1 ]BERGADANO F , GUN ETTI D. Inductive logic program2 ming : from machine learning to software engineering [ M ]. London : The MIT Press ,1996. [2 ]DA HR M. Deductive eatabases: theory and applications [ M ]. Boston : International Thomson Computer Press , 1997. [3 ] FITTIN G M. MeETRIC methods ,three examples and a theorem[J ]. J of Logic Programming , 1994 , 21 : 113 - 127. [4 ]L I W. An open logic system[J ]. Science in China (Scien2 ·12 · 智 能 系 统 学 报 第 2 卷