基于Prolog二元关系闭包运算的研究与实现

1、基于Prolog二元关系闭包运算的研究与实现摘要：在代数系统中，关系作为一种抽象工具，在计算机科学研究领域有着极其广泛的应用。本文在研究传统闭包求解方法的根底上，结合其思想给出了用人工智能语言Prolog实现传递闭包求解策略的思想与方法，并在实例中给予论证，此方法具有一定的典型研究意义及价值。论文关键词：二元关系,传递闭包,人工智能,回溯Prolog是逻辑程序设计有关证明详见文献【3】。2 用prolog实现二元关系的闭包运算根据上述传统闭包求解方法，很容易可以看出自反、对称闭包的求解方法相比照拟容易，只需要在其中添加一些特殊的关系序对即可。而针对传统传递闭包求解的复杂性，可根据上述传递闭包的

2、定义和性质，结合人工智能语言Prolog的语法特点和结构实现闭包运算。2.1根本思想与步骤综合传统闭包求解方法和思想以及Prolog语言的语法规那么，用Visual Prolog实现传递闭包运算的根本步骤为：STEP1 分析描述问题根据上一节对集合二元关系假设干根本性质的介绍及闭包的定义及求解方式，用Visual Prolog实现传递闭包运算。STEP2 定义谓词在Prolog中，谓词表示子句中关系的名称，本问题领域定义的相关谓词分别为：r-关系对序偶transitive_closure-传递闭包STEP3 定义事实及规那么在理解二元关系的有关定义及性质根底上，按照Prolog语言的语法和上面

3、所定义的谓词，首先定义的事实和规那么子句分别为：r(A,B) /*元素A和B之间存在关系R*/transitive_closure(A,B):-r(A,B). /*求R，Rt(R) */transitive_closure(A,B):-r(A,C),r(C,B). /* 求R2 ，R2t(R)*/transitive_closure(A,B):- r(A,D),r(D,E),r(E,B). /* 求R3 ，R3t(R)*/*定义求解传递闭包规那么*/根据Prolog的取规那么又等价于：transitive_closure(A,B):-r(A,B);r(A,C),r(C,B);r(A,D),r(

4、D,E),r(E,B);以上，都是Prolog中的子句，称为无条件子句，一般情况下在知识库中只表示事实；而称为条件子句，合起来构成一个Prolog程序。下面的步骤需要根据实例进行。2.2 举例例1设集合A=a, b ,c,， R=(a ,a),(a, b),(b ,a),(c, b)，求关系R的传递闭包。关系R的有向图和布尔矩阵表示法分别如图1a和b所示。图1 关系R的有向图和矩阵表示STEP1 按照Prolog语言语法,对上述实例，建立如下事实：r(a,a). /*a, aR */r(a,b). /*a, bR */r(b,a). /*b, aR */r(c,b). /*c, bR */ST

5、EP2 使用传递闭包规那么R + =R*=RR2R3Rn：transitive_closure(A,B):-r(A,B); /*求R，Rt(R) */transitive_closure(A,B):-r(A,C),r(C,B); /* 求R2 ，R2t(R)*/transitive_closure(A,B):-r(A,C),r(C,D),r(D,B) ; /* 求R3 ，R3t(R)*/STEP3 用目标transitive_closure(X,Y)进行提问。STEP4 完整的程序运行界面及结果分别参见图2图2 求传递闭包的运行界面及结果STEP5 分析结果：在这里求出的所有关系序对图3消除重

6、复解的运行界面及结果图由运行结果图可以看到，求解的最终结果中，没有出现重复解，使得求解传递闭包的过程完全自动化，当然这只是其中的一种设计方法。4结语关系作为一种抽象工具，它在计算机科学中的形式语言与自动机理论等方面又重要作用。特别是几种特殊关系，其求解方法更应该被掌握。本文所介绍的基于Prolog实现二元关系闭包运算有着一定的典型研究意义及价值。根据同样的设计步骤和思想，可并对其做以扩展，对二元关系上组合关系的性质进行判断，例如，自反、对称、传递、等价和偏序关系等。参考文献【1】 苏畅,蔡经球. 新一代智能语言VISUAL PROLOG.计算机应用研究,1999.【2】 马光思. 离散数学.西安：西安电子科技大学出版社,2004.7.【3】 Kenneth H.Rosen. Discrete Mathematics and its Applications(Fifth Edition).China Machine Press北京：机械工业出版社,2003.3.【4】 雷英杰,华继学,徐彤