资源描述：
《基于prolog二元关系闭包运算的研究和实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于Prolog二元关系闭包运算的研究和实现.freelminginlogic)的缩写。其理论基础是谓词逻辑,它是人们把逻辑作为程序设计的一种语言的努力结果。Prolog由于具有简洁的文法、丰富的表现力以及强大的逻辑推理能力,特别适用于解决人工智能方面的问题,目前已成为实现专家系统最理想的语言工具1。代数结构中,构造关系上的各种闭包在实际中有很多重要的应用,.freelmetric)(或R具有对称性)x,y∈A,xRy?yRx。⑷R是反对称的(Antsymmetric)(或R具有反对称性)x,y∈A,(xRy?yRx?x=y。⑸R是传递的(Transitive)(或R具有传递性)x,y,z
2、∈A,(xRy?yRz?xRz。定义2设集合A≠φ,R?A×A。若Rˊ?A×A满足:⑴Rˊ是自反的(对称的和传递的);⑵R?Rˊ;⑶对A上的任意满足⑴和⑵的二元关系R〞,皆有Rˊ?R〞,则称Rˊ为R的自反(对称或者传递)闭包。关系R的自反闭包(Reflexiveclosure)通常记为r(R),对称闭包(Symmetricclosure)记为s(R),传递闭包(Transitiveclosure)记为t(R)。r(R),s(R)及t(R)分别是包含R且具有自反性、对称性或传递性的最小二元关系。1.2传统闭包求解方法对于怎样求关系R的闭包,离散数学中有着不同的方法,在介绍传统闭包求解方法前,
3、先介绍两个概念。定义3二元关系的逆设R?A×B,则R的逆(Inverse)或逆关系记为R-1,,是从B到A的二元关系。形式定义R-1={(y,x)︳xRy}>定义4集合上的恒等关系设有集合A={x1,x2,…xn},A上的恒等关系IA={(x,x)︳x∈R}。根据闭包的定义及性质,求解各个闭包的一般方法如下:⑴自反闭包:若存在x∈A,把序偶(x,x)添加到关系R中即可,即r(R)=R∪IA。⑵对称闭包:若存在序偶(x,y)∈R,把序偶(y,x)添加到关系R中即可,即s(R)=R∪R-1。⑶传递闭包:关于传递闭包的求解相对比较复杂,方法也较多,可以用矩阵运算,也可以根据R上的传递闭包R+等于
4、连通关系R*进行求解,即t(R)=R+=R*=R∪R2∪R3∪…∪Rn(n为集合A的基数,
5、A
6、=n)有关证明详见文献3。2用prolog实现二元关系的闭包运算根据上述传统闭包求解方法,很容易可以看出自反、对称闭包的求解方法相对比较容易,只需要在其中添加一些特殊的关系序对即可。而针对传统传递闭包求解的复杂性,可根据上述传递闭包的定义和性质,结合人工智能语言Prolog的语法特点和结构实现闭包运算。2.1基本思想与步骤综合传统闭包求解方法和思想以及Prolog语言的语法规则,用VisualProlog实现传递闭包运算的基本步骤为:STEP1分析描述问题根据上一节对集合二元关系若干基本性质的介
7、绍及闭包的定义及求解方式,用VisualProlog实现传递闭包运算。STEP2定义谓词在Prolog中,谓词表示子句中关系的名称,本问题领域定义的相关谓词分别为:r-关系对序偶(包含两个变元)transitive_closure-传递闭包(包含两个变元)STEP3定义事实及规则在理解二元关系的有关定义及性质基础上,按照Prolog语言的语法和上面所定义的谓词,首先定义的事实和规则(子句)分别为:①r(A,B)/*元素A和B之间存在关系R*/②transitive_closure(A,B):-r(A,B)./*求R,R?t(R)*/③transitive_closure(A,B):-r(A
8、,C),r(C,B)./*求R2,R2?t(R)*/④transitive_closure(A,B):-r(A,D),r(D,E),r(E,B)./*求R3,R3?t(R)*/…/*定义求解传递闭包规则*/根据Prolog的取规则②~④又等价于:transitive_closure(A,B):-r(A,B);r(A,C),r(C,B);r(A,D),r(D,E),r(E,B);…以上,①~④都是Prolog中的子句,①称为无条件子句,一般情况下在知识库中只表示事实;而②~④称为条件子句,①~④合起来构成一个Prolog程序。下面的步骤需要根据实例进行。2.2举例例1设集合A={a,b,c,
9、},R={(a,a),(a,b),(b,a),(c,b)},求关系R的传递闭包。关系R的有向图和布尔矩阵表示法分别如图1(a)和(b)所示。传递闭包图1关系R的有向图和矩阵表示STEP1按照Prolog语言语法,对上述实例,建立如下事实:r('a','a')./*(a,a)∈R*/r('a','b')./*(a,b)∈R*/r('b','a')./*(b,a)∈R*/r('c','b')./*(c,b)∈R*/STEP2
