域矩阵与简化域矩阵的应用研究

汪小燕，杨思春，申元霞

（安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243032）

二元关系包括等价关系、相容关系、序关系等，它可以应用于粒计算[1-2]、形式背景[3-4]、粗糙集[5]等相关问题研究，因此，有必要对二元关系的性质进行研究。二元关系的性质一般包括自反、反自反、对称、反对称、传递，前四个性质借助于关系图或关系矩阵都能够直接判断，而传递性从关系图或关系矩阵中不能直接反映出来，二元关系中包含序偶时，判断反对称性容易产生误解。文献[6]对传递性的前提条件进行补充，给出一种传递性判断的等价定义。文献[7]利用二元关系的关系矩阵，通过行与行之间的布尔加运算，判断关系矩阵是否为衡平矩阵来判定二元关系的传递性。文献[8]用数理逻辑方法和命题制作方法给出二元关系传递性的等价定义，并给出判断二元关系传递性的几个充分必要条件。文献[9]对反对称性进行研究，给出一种反对称性判断的等价定义。文献[10]通过对二元关系反对称性定义的深入分析，给出两种等价的定义形式。为了能够直观判断二元关系的传递性，笔者定义了域矩阵和简化域矩阵，将域矩阵和简化域矩阵分别用于二元关系和其自身的复合运算、判断二元关系的传递性及反对称性，基于两种矩阵提出关于传递性、反对称性判断和关系复合运算的相关理论。

1 相关概念

二元关系通常是由若干个序偶构成的集合，序偶是二元关系的元素。若R是集合A上的二元关系，x，y∈A且xRy，也可以用序偶表示为：∈R。

定义1[11]R为集合A上的二元关系，对于任意a，b，c∈A，当∈R且∈R时，有∈R，称R为A上的传递关系，或者说R在A上具有传递性。

设R1，R2为集合{1，2，3}上的二元关系，R1={<1，2>，<1，3>}，R2={<1，2>}，这两个二元关系都具有传递性，而使用定义1判断这两种类型的二元关系为什么具有传递性就不好理解。

定义2[11]R为集合A上的二元关系，如果对于任意∈R且a≠b，∉R，则称R在A上具有反对称性。

定义3[11]设R是一个二元关系，由∈R的所有x组成的集合domR称作R的前域，即domR={x|∃y（∈R）}。

定义3指出前域是由二元关系中所有序偶的第一元素构成的集合。

定义4[11]设R是一个二元关系，由∈R的所有y组成的集合ranR称作R的值域，即ranR=｛y|∃x（∈R）｝。

定义4指出值域是由二元关系中所有序偶的第二元素构成的集合。任何一个非空的二元关系都具有非空的前域和值域。

定义5设R是集合A上的二元关系，x，y，z是A中的任意三个元素，若任意s，t∈R，且s=，t=，若以y为中间元素，则s和t可以形成新的序偶，将这一运算称为序偶的复合，记作s◦t=。

定义6[12]设R是集合A上的二元关系，若IR={|x∈A且∈R}，则称IR为R中的第一元素和第二元素相等的序偶的集合。

2 传递性质的域矩阵判断方法

为了方便表达判断传递性质的矩阵，现给出如下两个定义。

定义7设R是集合A中的二元关系，称（y）1={x|x∈A and y∈A and xRy}是y的R第一元素集合。

定义8设R是集合A中的二元关系，称（x）2={y|x∈A and y∈A and xRy}是x的R第二元素集合。

根据以上相关概念，提出域矩阵的定义。

定义9设R是集合A中的二元关系，定义域矩阵为：矩阵的每一行对应一个元素的R第二元素集合，即（x）2，每一列对应一个元素的R第一元素集合，即（y）1，矩阵中元素取值表示如下

其中x∈domR，y∈ranR。

文献[11]指出R是集合A上的二元关系，设R1=R-IR，如果R1具有传递的性质，则二元关系R也一定具有传递性质。所以，研究二元关系R的传递性质，可以借助删减后的二元关系R1来判断。这样可以降低矩阵的规模，提高判断的速度。改进的简化域矩阵定义如下。

定义10设R是集合A中的二元关系，R1=R-IR，定义简化域矩阵为：矩阵的每一行对应一个元素的R1第二元素集合，即（x）2，每一列对应一个元素的R1第一元素集合，即（y）1，矩阵中元素取值表示如下

其中x∈domR1，y∈ranR1。

根据简化域矩阵，下面研究判断二元关系传递性质的相关理论。

定理1设R是集合A中的二元关系，R1=R-IR，M为简化域矩阵，（x）2和（y）1分别为元素的R1第二元素集合和R1第一元素集合。对∀x∈domR1，∀y∈ranR1，若（x）2∩（y）1=Ø或者（x）2∩（y）1≠Ø且∈R，则R具有传递性质。

证明当（x）2∩（y）1=Ø时，也就是∈R1，不存在∈R1。而当（x）2∩（y）1≠Ø且∈R时，也就是对∈R1，存在∈R1且∈R，根据定义1可知R在A上具有传递性。

根据简化域矩阵和定理1，可得如下推论。

推论1设R是集合A中的二元关系，R1=R-IR，M为简化域矩阵。若矩阵中的元素为1或Ø，则R具有传递性质。

推论2设R是集合A中的二元关系，R1=R-IR，M为简化域矩阵。若矩阵中至少有一个元素为0，则R不具有传递性质。

定理2设R是集合A中的二元关系。若简化域矩阵不存在，则R具有传递性质。

证明设R是集合A中的二元关系，R1=R-IR，若R1=Ø时，则domR1=Ø，ranR1=Ø，简化域矩阵不存在，在定理1中，前提条件不满足，即前提为假，根据命题逻辑的条件联结词运算可知，关于定理1的命题为真。所以R具有传递性质。

R1无论是非空集合上的空关系还是空集上的空关系，只要关于R1的简化域矩阵不存在，R就一定具有传递性质。

定理3设R是集合A中的二元关系，R1=R-IR，M为简化域矩阵，（x）2和（y）1分别为元素的R1第二元素集合和R1第一元素集合。对∀x∈domR1，∀y∈ranR1，若x=y，对应矩阵元素为Ø，则R具有反对称性质。

证明对∀x∈domR1，∀y∈ranR1，当x=y时，对应矩阵元素为Ø，则（x）2∩（y）1=Ø，也就是对∈R1，不存在∈R1，根据定义2可知R在A上具有反对称性质。

定理4设R是集合A中的二元关系，R1=R-IR，M为简化域矩阵，（x）2和（y）1分别为元素的R1第二元素集合和R1第一元素集合，∃x∈domR1，∃y∈ranR1。若x=y时，对应矩阵元素为0或1，则R不具有反对称性质。

证明若∃x∈domR1，∃y∈ranR1，当x=y时，对应矩 阵元 素为0或1，则（x）2∩（y）1≠Ø，也就是对∈R1，存在∈R1，根据定义2可知R在A上不具有反对称性质。

推论3设R是集合A中的二元关系。若简化域矩阵不存在，则R具有反对称性质。

根据定义9建立的域矩阵既可以用于传递性质的判断，还可以用于二元关系与其自身的复合运算。

定理5设R是集合A中的二元关系，M为域矩阵，则矩阵中取值为0或1的元素所对应的序偶∈R◦R。

证明当矩阵中元素取值为0或1时，根据定义9知：（x）2∩（y）1≠Ø，也就是对∈R，存在∈R，根据复合运算的定义知：∈R◦R。

定理6设R是集合A中的二元关系，M为域矩阵，则矩阵中取值为0或1的元素所对应的序偶集合为R2，则R◦R=R2。

证明由复合运算的定义和定理5可证。

推论4设R是集合A中的二元关系，M为域矩阵。若矩阵中所有元素都是Ø，则R◦R=Ø。

根据简化域矩阵，判断二元关系传递性的步骤如下：（1）计算R1=R-IR；（2）分别计算出二元关系R1的前域domR1和值域ranR1；（3）对∀x∈domR1，∀y∈ranR1，分别计算（x）2和（y）1；（4）按照定义10给出R1的简化域矩阵；（5）检查矩阵中是否有0元素存在，若不存在0元素，则R具有传递性质，否则R不具有传递性质。

若根据简化域矩阵，判断二元关系反对称性质，只需要将上述步骤（5）改为：检查矩阵中对∀x∈domR1（R1的前域），∀y∈ranR1（R1值域），若x=y时，对应矩阵元素为Ø，则R具有反对称性质。

根据域矩阵，计算一个二元关系和其自身复合的步骤如下：（1）分别计算出二元关系R的前域domR和值域ranR；（2）对∀x∈domR，∀y∈ranR，分别计算（x）2和（y）1；（3）按照定义9给出R的域矩阵；（4）R◦R为矩阵中所有取值为0或1的元素所对应的序偶集合。

下面通过实例来说明判断二元关系传递性质、反对称性质和二元关系与其自身复合的过程。

例1设集合A={1，2，3，4，5}，R是A上的一个二元关系，

判断过程如下

根据定义10，所得到的简化域矩阵为

该矩阵中有0元素存在，则二元关系R不具有传递性质，该矩阵中第二行第一列以及第三行第二列所对应的元素都是Ø，故二元关系R具有反对称性质。

同理，根据定义9，所得到的域矩阵为

由定理5可得：R◦R={<1，1>，<1，2>，<1，3>，<1，5>，<2，2>，<2，3>，<2，5>，<4，4>}。

3 结语

结合二元关系的前域和值域，提出域矩阵和简化域矩阵，简化域矩阵降低了矩阵规模，更适合二元关系传递性和反对称性的判断。将域矩阵用于二元关系与其自身的复合运算，运算过程中不会产生重复的序偶。利用两种矩阵，提出了传递性质和反对称性质判断的相关理论和判断方法以及复合运算的理论与方法。利用新的方法进行关系的复合运算和判断传递性、反对称性，计算和判断过程直观，步骤清晰，而且容易理解。接下来将研究适合不同二元关系复合的域矩阵和适合数据挖掘领域的域矩阵。