Horn子句与Prolog语言简介.ppt

Horn子句与Prolog语言简介 一阶逻辑公式 优点：表示方法具有表达力强，表示方便等优点。 缺点： 不够规范化 不够简洁 从而不利于其在计算机中的使用与处理，因此需要对这种形式做规范化，从而形成一阶逻辑公式的： 子句形式 Horn子句形式。 定义6.4（子句）： 具有如下形式的公式被称为子句： A1 ∧ A2 ∧ … ∧ AK → AK+1 ∨ AK+2 ∨ … ∨ An 也可以将其简写为： AK+1 ，AK+2 ，… ，An :- A1 ，A2 ，… ，AK 其中Ai为原子公式。在该子句中，A1 ，A2 ，… ，AK被成为前件，AK+1 ，AK+2 ，… ，An被称为后件。在前件和后件中的 ‘,’分别表示不同的逻辑运算符。 子句表示形式单一，非常适合于在计算机中使用，也易于作知识推理。但利用子句作推理会引起推理结论的不确定性，为解决此问题，瑞士数学家Horn将其改造成为一种更简单的形式，即Horn子句。 定义6.5（ Horn子句）： 具有如下形式的公式被称为Horn子句： An :- A1 ，A2 ，… ，AK 由于Horn子句的后件是单一的，因此利用Horn子句做推理可以得到确定的推理结论。 不同的Horn子句可以有完全相同的一组前件。因此，同样一组前件利用不同的Horn子句可以推理得到多个不同的结论。 几种不同形式的Horn子句 例如： r:- p, s　 s:- p, q p:- , q:-。 现在要问r是否成立? (1) r:- p, s　 (2) s:- p, q (3) p:- (4) q:- (5) :-r (6) s:- q 由(2)(3)归结 (7) s:- 由(4)(6)归结 (8) r:- s 由(1)(3)归结 (9) r:- 由(7)(8)归结 (10) :- 由(5)(9)归结 例如： (1) Cousin(x, y):- Parent(u, x), Parent(v, y), Brother(u, v) (2) Parent(贾政，贾宝玉):- (3) Parent(贾敏，林黛玉):- (4) Brother(贾政，贾敏):- (5):- Cousin(贾宝玉，y) (6) Parent(u, 贾宝玉), Parent(v, y), Brother(u, v) (1)(5)归结 贾宝玉/x (7) Parent(v, y), Brother(贾政, v) (2)(6)归结　贾政/u (8) Parent(贾敏, y) (4)(7)归结　贾敏/v (9) :- (3)(8)归结　林黛玉/y 得出了贾宝玉与林黛玉是Cousin的关系。 Prolog语言 Prolog是一种基于一阶谓词的逻辑程序设计语言，它在AI和知识库的实现技术中具有十分重要的作用。 Prolog语言是基于Horn子句的，使用归结推理，具有很强的逻辑描述能力和推理能力。 Prolog语言的特点 一阶逻辑的语言形式是形式化地严格定义的； 一阶逻辑的语法十分简单易懂； 逻辑公式不需重复表达，与不同应用无关； 事实、假设、推理、查询、视图和完整性约束条件都能以基于一阶逻辑的Prolog语言表达； 逻辑语言Prolog可作为定义和比较其它知识表示模型的共同基础。 Datalog语言 是一种纯Horn子句语言，在数据库理论中应用很广。 Datalog语言的优点 克服Prolog语言的缺点：表示方法不够规范，不宜在计算机中使用和处理； 适合于处理具有大容量的数据和知识； 可以改善递归查询算法。 Datalog语言的缺点 不带有函数，建模能力差，较难以描述现实世界中的实际问题。 * 断言：没有前件，只有后件的Horn子句。例如： An :- 一个断言表明该结论是永远成立的。 假设：只有前件，没有后件的Horn子句。例如： :- A1 ，A2 ，… ，AK 空子句：前件与后件均不存在的Horn子句。例如： :- 空子句是数理逻辑中一个非常重要的内容，出现空子句是许多问题求解过程的终止标志。 *