等价关系判断系统的设计

姜 楠，焉德军，李笑牛，王 波，紫春平

(大连民族学院计算机科学与工程学院，辽宁大连 116605)

等价关系判断系统的设计

姜 楠，焉德军，李笑牛，王 波，紫春平

(大连民族学院计算机科学与工程学院，辽宁大连 116605)

介绍了关系的定义、关系的自反性和反自反性、对称性和反对称性、传递性五条性质，及其在计算机领域中的应用。设计了判断给定集合上关系的各种性质的函数，并进行了相关算法分析。设计了判断等价关系的流程图，利用计算机语言编程实现了等价关系判定的实验系统。该系统简单易于实现，在离散数学教学中，对学生掌握抽象理论具有较好的帮助作用。

等价关系;系统原理;算法设计;函数

集合的元素之间的关系被表示成一种结构，这种结构叫做关系。在计算机科学中，关系理论具有重要意义。例如，数字计算机的逻辑设计和时序设计中，都应用了等价关系和相容关系的概念。在编译程序设计，数据结构等领域中，也涉及到关系的部分内容。关系理论在计算机科学技术中的应用还包括计算机程序的输入、输出关系、数据库的数据特性关系等。关系理论在信息安全中的基于角色的访问控制中也有应用，角色关系就是一种偏序关系。关系理论还被应用在软件测试中，等价类划分是黑盒测试的典型方法之一［1－3］。关系的应用是十分广泛的，尤其是等价关系在计算机科学中有着重要的地位，因而，对等价关系的研究具有重要意义［4－5］。本文主要设计了对关系性质进行判断的算法，进而设计出判断给定的关系是否为等价关系的函数，最后通过程序设计实现了该判断系统。等价关系判断系统把抽象难以理解的关系性质通过形象直观的软件程序表现出来，这样既可以激发学生的学习兴趣，又可以促进学生对抽象理论的理解。

1 系统原理

关系是一个集合，而这个集合满足以下条件之一:集合非空，且它的元素都是有序对;或者集合是空集［6］。

1.1 关系的性质

1.1.1 自反与反自反性质

设R为集合A上的关系，如果∀x(x∈A→＜x，x＞∈R)，则称R在A上是自反的;如果∀x(x∈A→＜x，x＞∉R)，则称R在A上是反自反的。也就是说如果关系R的关系矩阵主对角线上的值全为1，则R是自反的;如果主对角线上的值全为0，则R是反自反的。如果主对角线上的值既有1又有0，则R是既不是自反的也不是反自反的。因而可以通过判断关系矩阵中的主对角线上元素值是否为1来确定这个关系是自反的或反自反的［6］。

1.1.2 对称与反对称性质

设R为集合A上的关系，若∀x∀y(x，y∈A∧ ＜x，y＞∈R→ ＜y，x＞ ∈R)，则称 R 为 A 上对称的关系;若∀x∀y(x，y∈A∧ ＜x，y＞∈R∧ ＜y，x＞∈R→x=y)，则称R为A上反对称的关系。如果关系R是对称的，则其关系矩阵MR关于主对角线是对称的;如果关系R是反对称的，则对于其关系矩阵中第i行第j列的元素mij在i≠j并且mij=1 时，一定有 mji=0。即当 i≠j时 mij与 mji可以同时为0，可以一个是1，一个是0，但是不能同时为1。如果一个关系矩阵只在主对角线位置的元素有1，其他元素都是0，那么这个关系既是对称的又是反对称的。

1.1.3 关系传递性质

设R为集合A上的关系，若∀x∀y∀z(x，y，z∈A∧ ＜x，y＞∈R∧ ＜y，z＞∈R→ ＜x，z＞∈R)，则称R是A上的传递关系。给定关系R的关系矩阵MR，也可以判断关系R是否为可传递的。由关系R的可传递性定义可知，若关系R是可传递的，则由mik=1∧mkj=1一定可以推出mij=1。关系R是可传递的还可以描述为由mij=0一定可以推出 mik=0∨mkj=0［7］。

1.2 等价关系

设R为非空集合A上的关系，如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一个等价关系，若＜x，y＞∈R，称x等价于y，记做 x～y。

2 算法分析

为了判断关系的自反、反自反、对称、反对称、传递性质，可以设计出5个函数对这5条性质分别进行判断。

2.1 判断给定的关系是否为自反关系

判断给定的关系是否为自反的函数记为int Reflexive()。如果给定的关系是自反的，则返回1，否则返回0。通过判断给定关系R的关系矩阵MR主对角线上元素是否全部为1，来确定给定的关系R是否为自反的。如果MR主对角线上元素全部为1，则R是自反的，否则R不是自反的。

具体步骤如下:

(1)给定包含k个元素的集合A，其上的关系R及n阶关系矩阵MR，计数器count=0，i=1;

(2)在关系矩阵MR中查看主对角线第i个元素 m［i］［i］是否等于 1，若 m［i］［i］=1，则计数器count++ ，若 m［i］［i］ =0，则计数器 count值不变，i=i+1;

(3)if i=n，执行(4)，否则，回到(2);

(4)若计数器count值与A中元素个数相等，则R为A上的自反关系;否则，R不是A上的自反关系。

2.2 判断给定的关系是否为对称关系

判断给定的关系R是否对称的函数为int Symmetric()，如果R是对称的，则返回1，否则返回0。通过判断矩阵MR中的所有元素是否关于主对角线对称来确定给定的关系是否为对称的，如果MR中的所有元素关于主对角线都是对称的，则R是对称的，否则R不是对称的。

具体步骤如下:

(1)给定包含p个元素的集合A，定义在其上的包含l个元素的关系R，及n阶关系矩阵MR。初始化R中对称元素计数器count=0，对角线计数器 k=0，i=1，j=1;

(2)if m［i］［i］=0，则计数器 k++;否则，k不变，i=i+1;

(3)若 m［i］［j］=1 并且 m［i］［j］=m［j］［i］，则计数器 count++;否则，count不变，j=i+1;j=j+1，i=i+1;

(4)if i=n，j=n，执行(5)，否则，回到(3);

(5)若 count=(l－k)/2，则R具有对称性;否则R不具有对称性。

2.3 判断给定的关系是否为传递关系

判断给定的关系R是否为传递的函数为int Transitive()，如果R是传递的，则返回1，否则返回0。首先求出该关系R的二次幂R2的关系矩阵MR2，然后判断 MR2中所有的值为1的元素m'ij与MR中对应位置的元素 mij是否相等且为1，如果是，则R是可传递的，否则R不是可传递的［8］。

具体步骤如下:

(1)给定包含p个元素的集合A，定义在其上的包含l个元素的关系R，及n阶关系矩阵MR。初始化标识符为flag=0，i=1，j=1;

(2)计算R2的关系矩阵MR2的所有元素;

(3)若 m［i］［j］=1，且 m'［i］［j］!=1，则标识符改变为flag=0，且退出循环执行第(5)步;否则，flag 不变，j=i+1;j=j+1，i=i+1;

(4)if i=n，j=n，执行(5)，否则，回到(3);

(5)判断标识符flag的值，若flag=1，则关系R具有传递性;若flag=0，则关系R不具有传递性。

3 系统实现流程

对于给定集合A上的关系R，如果是以集合或关系图的形式表示的，要把它们转换成关系矩阵的形式，然后才能进行判断。对于用户输入的关系，系统先判断关系中的定义域和值域中的每一个元素是否为集合A中的元素，如果有不属于A的元素，则提示用户的输入不合法并提示系统停止运行。然后判断给定的关系是否具有自反性、对称性和传递性，如果具有这些性质，则可以确定关系R是为等价关系。

创建关系类，其中包含的函数有构造函数、赋值函数、判断自反性质函数、判断对称性质函数、判断传递性质函数;类中包含的数据有关系R的关系矩阵、集合A的元素个数、关系R的元素个数。构造函数首先对关系矩阵赋初值全为0的矩阵;在赋值函数中输入集合A中各元素值、二元关系R中的各有序对，并将关系矩阵中相对应的元素值改为1。在对关系自反性质的判断函数中按照算法2.1编程实现算法，并完成结果判断;在对关系对称性质的判断函数中按照算法2.2编程实现算法，并完成结果判断;在对关系传递性质的判断函数中按照算法2.3编程实现算法，并完成结果判断。系统主函数提供菜单供用户选择，通过输入的选项分别调用不同的函数。判断给定的关系是否为等价关系的系统流程如图1。

图1 系统流程图

4 结论

关系是离散数学课程的重要部分，在计算机和通信等领域中也有广泛的应用。本文主要研究等价关系判断系统的原理与算法设计，对任意输入的表示有穷集上的关系，确定这个关系是否为自反的或反自反的、对称的或反对称的、是否传递的，进而判断出这个关系是否为等价关系。该系统设计的目的是使学生掌握利用计算机语言实现判断关系性质的基本方法，这不仅可以使学生巩固书本上学过的理论知识，把抽象知识转化为具体的程序设计，提高学生的学习兴趣，而且可以培养学生的算法设计和程序设计能力。使学生在做中学，学中做，进而提高学生的抽象思维能力、分析问题和解决问题能力。

［1］冯玉芬，杨天栋.等价类划分测试用例设计［J］.株洲师范高等专科学校学报，2007(10):43－45.

［2］张大陆，童熙.基于二元关系的语义Web的建立［J］.同济大学学报:自然科学版，2004(12):1677－1681.

［3］易国洪，卢炎生.基于EFSM模型的等价类测试［J］.计算机科学，2007，34(1):281 －284.

［4］姜楠，王立明，林珅，等.离散数学网上学习系统的设计与实现［J］.计算机工程与科学，2008(10):96－98.

［5］姜楠.离散数学课程建设与教学改革探讨［J］.大连民族学院学报，2005(6):86－87.

［6］屈婉玲，耿淑云，张立昂.离散数学［M］.北京:清华大学出版社，2005.

［7］曹晓东.离散数学、算法及CAI［M］.大连:大连海事大学出版社，1996.

［8］ BERNARD K，ROBERT C B，SHARON C R.Discrete Mathematical Structures［M］.Higher Education Press，2001.

Design of Equivalence Relations Judge System

JIANG Nan，YAN De－jun，LI Xiao －niu，WANG Bo，Zi Chun －ping
(College of Computer Science and Engineering，
Dalian Nationalities University，Dalian Liaoning 116605 ，China)

The definition of relation，relations properties about to reflexive and irreflexive，symmetric and antisymmetric and transitive，and its application in computer science has been recited.The functions for judging relations properties in the set has been designed，and the interrelated algorithms have been analyzed.The flow chart for determining equivalence relations has been developed，and the experiment system of equivalence relations judgement has been implemented based on computer programming language.The system is easy to be realized and can be used in discrete mathematics teaching to help the students to understanding of abstract theory.Key words:equivalence relations;system principle;algorithm design;function

O158

A

1009－315X(2011)05－0496－03

2011－07－04

中央高校基本科研业务专项资金资助项目(DC10020114)，大连民族学院博士基金项目(20096203)。

姜楠(1964－)，女，山东龙口人，教授，主要从事信息安全研究。

(责任编辑 刘敏)