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

摘要：在代数系统中，关系作为一种抽象工具，在计算机科学研究领域有着极其广泛的应用。本文在研究传统闭包求解方法的基础上，结合其思想给出了用人工智能语言Prolog实现传递闭包求解策略的思想与方法，并在实例中给予论证，此方法具有一定的典型研究意义及价值。
论文关键词：二元关系,传递闭包,人工智能,回溯

Prolog是逻辑程序设计（Programming in logic）的缩写。其理论基础是谓词逻辑，它是人们把逻辑作为程序设计的一种语言的努力结果。Prolog由于具有简洁的文法、丰富的表现力以及强大的逻辑推理能力，特别适用于解决人工智能方面的问题，目前已成为实现专家系统最理想的语言工具[1]。

代数结构中，构造关系上的各种闭包在实际中有很多重要的应用，例如，在编译程序中的语法分析中，常常要通过求定义在某字母表上有关语法规则的二元关系的传递闭包，来计算非终结符所能导出的字符表。对于怎样求关系R的闭包，离散数学中有着不同的方法，相对于自反、对称闭包求解方法，无论是用Warshall算法（详细介绍及求解方法见文献2和3）还是寻找连通路径法，传递闭包的求解都比较复杂，求解过程也容易出错。这时可根据传递闭包的定义和性质，用Prolog语言实现闭包运算。

1 传统闭包求解

1.1集合上二元关系的若干基本性质

定义1 设集合A≠φ,R⊆A×A。形式定义[2]

⑴ R是自反的（Reflexive）（或R具有自反性）Iff∀x (x∈R xRx)。

⑵ R是反自反的（Irreflexive）（或R具有反自反性）Iff∃x (x∈R xRx)。

⑶ R是对称的（Symmetric）（或R具有对称性）Iff∀x，y∈A, xRy yRx。

⑷ R是反对称的（Antsymmetric）（或R具有反对称性）Iff∀x，y∈A, （xRyyRx  x=y。

⑸ R是传递的（Transitive）（或R具有传递性）Iff∀x，y，z∈A, （xRyyRz  xRz。

定义2 设集合A≠φ,R⊆A×A。若R ˊ ⊆A×A满足：

⑴ R ˊ是自反的（对称的和传递的）；

⑵ R⊆ R ˊ；

⑶ 对A上的任意满足⑴和⑵的二元关系R 〞,皆有R ˊ ⊆R 〞，则称R ˊ为R的自反（对称或者传递）闭包。

关系R的自反闭包（Reflexive closure）通常记为r(R), 对称闭包（Symmetric closure）记为s(R), 传递闭包（Transitive closure）记为t(R)。r(R) ，s(R)及 t(R)分别是包含R且具有自反性、对称性或传递性的最小二元关系。

1.2传统闭包求解方法

对于怎样求关系R的闭包，离散数学中有着不同的方法，在介绍传统闭包求解方法前，先介绍两个概念。

定义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 + 等于连通关系R*进行求解，即

t(R)= R + = R* =R∪R2∪R3∪…∪Rn（n为集合A的基数，|A| = n）

有关证明详见文献[3]。

2 用prolog实现二元关系的闭包运算

根据上述传统闭包求解方法，很容易可以看出自反、对称闭包的求解方法相对比较容易，只需要在其中添加一些特殊的关系序对即可。而针对传统传递闭包求解的复杂性，可根据上述传递闭包的定义和性质，结合人工智能语言Prolog的语法特点和结构实现闭包运算。

2.1基本思想与步骤

综合传统闭包求解方法和思想以及Prolog语言的语法规则，用Visual Prolog实现传递闭包运算的基本步骤为：

STEP1 分析描述问题

根据上一节对集合二元关系若干基本性质的介绍及闭包的定义及求解方式，用Visual Prolog实现传递闭包运算。

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,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,}， 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 使用传递闭包规则（R + =R*=R∪R2∪R3∪…∪Rn）：

transitive_closure(A,B):-r(A,B); /*求R，Rt(R) */

transitive_closure(A,B):-r(A,C),r(C,B); /* 求R2 ，R2t(R)*/

transitive

 1/2    1 2 下一页 尾页