二元关系的判定与计数.doc

中南林业科技大学本科毕业论文 二元关系的判定与计数1. 引言二元关系是离散数学中的一个重要的基本概念。定义在某一集合上的二元关系有自反性、反自反性、对称性、反对称性和传递性等性质，它在整个离散数学中占有重要的地位，并且在诸如模式识别、模糊分析、数字电路设计和关系数据库理论分析等学科有着重要应用。显然，二元关系的研究对科学研究有着重要的现实作用和意义。而二元关系的判定与计数又是学习研究整个二元关系的关键，是利用二元关系的入口。目前，国内外数学界对二元关系的研究成果颇为丰富，各种离散数学的教材及各种杂志的论文都或轻或重的涉及到了二元关系的判定与计数，我们能很容易的查阅到相关的资料。但是，从整体来看，各种资料所述内容还是比较分散，并没有系统的对各种二元关系的判定与计数进行总结。另外，各研究成果基本都局限于数学理论范围内，都是需要人工的进行相关的判定或者计算。我们知道，随着科学技术的日益发展，问题的规模与日增大是不可避免的，那么即使有相当简便的方法，要人工计算也是不可取的，这样既降低了效率又容易出错。出于此考虑，本论文参考并结合了各类研究成果，在此基础上系统的提出了各种二元关系的判定与计数的方法，并对比较麻烦费时的问题给与了计算机程序进行实现，与计算机技术进行了良好的结合应用。论文中第二章属于基础知识部分，第三、四、五章是重点。第二章主要针对各种二元关系进行了定义，了解各种二元关系的内涵并对其表示方法进行了相应的介绍。第三章主要系统的介绍二元关系的判定，对各种二元关系都相应的进行了详细的讲解，并对部分可能会比较复杂的进行了计算机程序的实现，并且该程序都经过了实际调试运行，确保了代码的正确可行性。第四章主要阐述了二元关系的计数问题，对各种关系都相应的给出了最终数学计算公式及证明过程，容易让人理解并进行应用。第五种主要针对二元关系中非常重要的一个关系等价关系进行了剖析，并给出了对应的判定与计数的方法，特别的，该关系的计数相当繁琐，本文给出了相当优越的程序进行了实现。二元关系的判定与计数的研究有着很重要的科学意义。我们知道，随着科学技术的进步，科研的理论研究日益深入，碰到的各种问题越来越来复杂，丰富的研究手段对各种复杂问题的解决不言而喻有着极其重要的作用。数学作为科学的基础，而二元关系又作为离散数学中的一个极重要的概念，它有着特别的性质及意义，充分的应用这些性质能够帮我们找到更多的解决问题的途径和方法，这样必然会加速很多问题的解决，而要应用此关系事先对属于何种二元关系进行判定是必须的，因而在整个应用判定与计数是关键。然而各种关系之间的联系很紧密，但又相互区别。用普通的概念判别法对各种关系进行区分与计数的过程相当繁琐，那么我们能不能找出一种便捷有效的方法实现二元关系的判定与计数？能否用计算机进行实现从而代替我们完成这些繁琐的过程？我相信一个肯定的答案是每个接触离散数学的人员所愿意看到的。2. 二元关系的相关概念2.1 二元关系的定义“关系”是我们最熟悉、最常用的概念。在日常生活中，我们常用父子关系、兄弟关系、夫妻关系、师生关系等，其实这就已经属于我们离散数学中的二元关系的范畴，符合二元关系的定义了。在数学中，“关系”被抽象成为一个基本概念，它在计算机科学中“被广泛应用；在形式语言、编译程序设计、信息检索、数据结构，算法分析、数据库和有限自动机等方面起着重要作用。表示两个元素间的关系称为“二元关系”表示三个及三以上元素之间的关系称为多元关系，关系的基本概念中包含自反关系，反自反关系，对称关系，反对称关系，传递关系。为了便于研究，在数学的范畴内常用集合论的观点来描述关系。我们可以说关系是一个集合，有序对是其元素。例如，设集合A=a, b, c, d, e, f,元素a, b, c, d, e, f分别表示了六个人，其中a是b和c的父亲，b是d的父亲，c是e和f的父亲。现在便可以用有序对（a，c）（a，c）（b，d）（c，e）（c，f）来表示，以这些有序对作为元素构成的集合记为R，即： R=（a，c）（a，c）（b，d）（c，e）（c，f）集合R完整的描述了集合A中的元素的父子关系，我们便称R为集合A上的一个二元关系。值得的注意的是这里的有序对必须是固定的，不能随意更改顺序，如（a，c）改为（c，a）意义则完全相反了，表示的不再是a是c的父亲而是c是a的父亲。类似的可以定义其他含义的二元关系。对于多元关系我们亦可类似定义，只是集合中的有序对的元素是多元而已。2.2 二元关系的表示方法如前面所见到的，那种常规的集合表示方法显然不适合二元关系中有序对较多的情形，那样会显得很冗长，不便于分析。在离散数学中，常用的二元关系的表示方法有表格表示法、矩阵表示方法、图形表示方法及坐标图法。这四种表示方法极大的简化了二元关系的表示，显得非常直观，更便于我们以后的研究及在计算机中的存储。2.2.1 表格表示法 设集合，显然对于集合A到B的有序对可有n*m种。先画一个n行m列的表格，用A中的元素x1 ，x2 ， , xn顺序标记在竖列的左方，用B中的元素y1, y2, ym标记在横行的上方；这个n行m列的表格恰好能表示n*m种有序对，我们可以在相应的表格中画上一个“”表示该关系的存在，例如有序对（x1，y2）可以在第一行第二列中的表格中画上“”表示。实例：设A=x1，x2，x3，x4，x5，x6，B=y1，y2，y3，y4，y5，R是A到B的二元关系，且R=（x1，y2），（x2，y3），（x3，y5），（x4，y1），（x4，y5），（x5，y4），（x6，y2），则R的表格表示法如下图所示： y1 y2 y3 y4 y5 x1 x2 x3 x4 x5 x6如果在上面的的实例中，如果B=A，即B=x1，x2，x3，x4，x5，x6,此时问题为R是在集合A上的二元关系，且R=（x1，x2），（x2，x3），（x3，x5），（x4，x1），（x4，x5），（x5，x4），（x6，x2），（x2 ,x6）同样处理，此时yj就是xi，如下图： x1 x2 x3 x4 x5 x6 x1 x2 x3 x4 x5 x62.2.2 矩阵表示法矩阵是表格的数学表示，因此由二元关系的表格表示很容易得到二元关系的矩阵表示。设，R是A到B的二元关系，R的矩阵表示为一个n*m阶的矩阵rij，当xi对yj以R相关时，矩阵中的第i行、第j列元素rij取值为1，当xi对yj不以R相关时，取值0，即:实例：设A=x1，x2，x3，x4，x5，x6，B=y1，y2，y3，y4，y5，R是A到B的二元关系，且R=（x1，y1），（x1，y2），（x2，y3），（x3，y3），（x4，y5），（x5，y2），（x6，y4），（x6，y5），则R的矩阵表示法如下图所示：如果在上面的的实例中，如果B=A，即B=x1，x2，x3，x4，x5，x6,此时问题为R是在集合A上的二元关系，且R=（x1，x2），（x2，x3），（x3，x5），（x4，x1），（x4，x5），（x5，x4），（x6，x2），（x2 ,x6）同样处理，此时yj就是xi，如下图：2.2.3 图形表示法 设，R是A到B的二元关系。R的图形表示在平面上用n个点分别表示A中的元素x1 ，x2 ， , xn ;再在平面上画出m个点分别表示B中的元素y1, y2, ym；当（xi，yj）R时，从点xi至yj 画一条有向边，其箭头指向yj，否则不画边。例如：设A=x1，x2，x3，x4，x5 ，B=y1，y2，y3，y4 ，R是A到B的二元关系，且R=（x1，y1），（x2，y3），（x3，y1），（x4，y2），（x5，y4）则R的图形表示法如下图所示： A x1 x2 x3 x4x5 RBy1y2y3y4如果在上面的的实例中，如果B=A，即B=x1，x2，x3，x4，x5，x6,此时问题为R是在集合A上的二元关系，且R=（x1，x1），（x1，x2），（x2，x3），（x2，x4），（x3，x4），（x5，x3），（x5，x4）则这样处理，此时yj就是xi，如下图：x2x5x3x4x12.2.4 坐标图法顾名思义，坐标图法就是采用坐标来表示，把集合中的元素分别标在横纵坐标上便形成了我们表示方法的坐标系，再把存在于关系中的有序对依次在坐标系中用点表示出来即可。实例：设A=x1，x2，x3，x4，x5，B=y1，y2，y3，y4，y5，R是A到B的二元关系，且R=（x1，y2），（x2，y3），（x3，y5），（x4，y1），（x5，y4），则R的坐标图法表示如下图所示：3. 二元关系的基本类型及判断方法 二元关系的定义及其表示方法我们从上面已有了一个初步的了解，我们知道二元关系包含自反关系，反自反关系，对称关系，反对称关系，传递关系，那么关键问题是各种二元关系是如何定义的及如何去判定的。3.1 自反的二元关系及其判定定义：R是A上的二元关系，如果对于A中每一个元素x，都有（x，x）R，则称R为自反的二元关系，也称R具有自反性。例如，A=x，y，z，A上的二元关系R=（x ,x）,（y ,y）,（z ,z）,（x ,z）,（y ,z）,则R是自反的二元关系。但当R=（x ,x）,（y ,y）,（x ,z）,（y ,z）时则不是A上的自反关系，因为该关系R中并未满足对A中任意一个元素a都有（a，a）R，对于元素中的元素z有（z，z）R，所以R不是A上的自反关系。根据上面介绍的三种二元关系的表示方法，下面依次给与了相对应的关于自反关系的判定方法。当然，对于简单的二元关系，采用上面的定义法判定也不失一种方法。1） 在表格表示法中，我们很容易得出，如果关系R在A上是自反的，则处于对角线上的空格都应该是画上“”的，否则就不是自反的二元关系。其证明方法也相当简单，根据自反关系的定义，对于A中每一个元素x，都有（x，x）R，而（x，x）都位于表格表示法中的对角线上，显然，每个空格对应的关系都是存在的，故都应该是画上“”。2） 在矩阵表示法中，和表格表示法一样，只要对角线上的元素值全为1即对矩阵中的元素有rii=1对任意的符合题意的i成立，否则就不是自反的。可以这样证明，根据自反关系的定义，对于集合A中每一个元素x，都有（x，x）R，对应于矩阵表示法，即为rii=1。3) 对于图形表示法，很容易类似得出，只要对于任意的元素x有个环（代表（x，x）R），我们即可得出该关系是自反的。证明，根据自反关系的定义，对于A中每一个元素x，都有（x，x）R，对应于图形表示法，即每个元素都有一个代表（x，x）R的环。4）对于坐标图法，同样可以容易的得出，当坐标中的45度角直线上的点的个数等于集合中的元素的个数时就可以判定该关系在此集合上是自反的。证明，我们知道，在自反关系R中，对于集合A中每一个元素x，都有（x，x）R，而（x，x）都在坐标中的45度角直线上，所以只要满足该直线上的点的个数等于元素的个数即可判断对集合A中的每个元素都满足自反关系的定义，故该关系是自反的。自反关系的判断相当简单，对于用计算机程序的实现显得不是很重要，有时甚至还会费时些，所以此程序实现略。3.2 反自反的二元关系及其判定定义：R是A上的二元关系，如果对于A中每一个元素a，都有（a，a）R，则称R为反自反的二元关系，也称R具有反自反性。例如A=x，y，z，R=（x, y），（x, z），（y, z），（z, y）,则R是A上的反自反关系。如果R=（x, y），（x, z），（y, z），（z, z）,则R不是A上的反自反关系，因为对于A中的z有（z，z）R，故不是反自反的。根据上面介绍的三种二元关系的表示方法，下面依次给与了相对应的关于自反关系的判定方法。同样，对于简单的二元关系，采用上面的定义法判定也不失一种方法。当然我们应该注意到反自反的关系与自反关系的相反性，这促进我们的快速判定。1） 与自反关系完全相反，在表格表示法中只要对角线上的空格全没选中，该关系即为反自反的。其证明很简单，我们知道反自反的关系要求对于A中任一个元素a，都有（a，a）R，在表格表示法中即为对角线上的空格全部都不能选中。2） 矩阵表示法中的判定与表格基本是一致的，只要对角线上的元素值全为0即可判定该关系是反自反的。其证明方法与自反关系的证明完全一致。3） 在图形表示法中，只要对任意一个元素都没有环（代表（x，x）R），我们即可下结论该关系是反自反的。证明方法参考自反关系。4）在坐标图法中，与自反关系完全相反，只要在45度斜角的直线上没有点则表示该关系是反自反的。证明也完全相同，参考自反关系。自反关系的判断相当简单，对于用计算机程序的实现显得不是很重要，有时甚至还会费时些，所以此程序实现略。3.3 对称的二元关系及其判定定义：R是A上的二元关系，每当（x， y）R时就一定有（y， x）R，则称R为A上的对称关系，也称R具有对称性。例如，A=x，y，z，R=（x，y），（y，x），（y，z），（z，y），则R是A上的对称关系。倘若R=（x，y），（y，x），（y，z），（z，x），则R不是A上的对称关系，因为此时R中存在（y，z）和（z，x），根据定义，（z，y）和（x，z）并不存在R中，所以此时R并不是对称的。同样，对于上面给出的三种表示方法相对应的给出对称关系的判定方法。1） 由于对称性的特性可知，当表格中选定的空格关于对角线对称时，该关系即为对称关系。可这样分析证明，根据对称关系的定义有：每当（x， y）R时就一定有（y， x）R，而这一组有序对在表格表示法中是处在对称的位置上的，正好符合上面的判定方法。2) 在矩阵表示法中，上面的表格表示法的判别法同样适用，对应的只要表示矩阵关于对角线是对称即可得出该关系是对称的。证明，根据对称关系的定义有：每当（x， y）R时就一定有（y， x）R，而这一组有序对在矩阵表示法中即表示每当rij=1时，就一定有rji=1，对应矩阵的视觉表现形式即该矩阵式对称的。3）在图形表示法中，对称关系表现为要么两元素之间没有边，要么若两个元素之间有一条有向边，则一定有另外一条相反方向的边。证明分析，根据对称关系的定义很容易得知，对任意的两个元素x，y，只要它们存在有序对（x，y），就一定有（y，x），即：只要有一条边就一定有另外一条相反方向的边。4）在坐标图法中，对称关系表现为坐标中的所有点关于45度斜角的直线对称，具有此特征的关系即可判断为对称关系。证明分析，根据对称关系的定义很容易得知，对集合中的任意的两个元素x，y，只要它们存在有序对（x，y），就一定有（y，x），而这两个有序对在坐标图法中表示出来一定是关于45度斜角的直线对称的。用计算机程序实现如下：#includeusing namespace std;void main()/输入二元关系数组cout请输入数组元素：endl; const int n=5; int ann;/初始化 int r,s;for(r=0;rn;r+)for(s=0;sars;/根据判定方法进行计算 int i,j;int count=0;for (i=0;in;i+)for(j=0;jn;j+)if(aij=1&aji!=1)count=count+1;break;break;if(count=1) cout该关系不是对称的endl;else cout该关系是对称的endl;运行结果：3.4 反对称的二元关系及其判定定义：R是A上的二元关系，当xy时，如果（x，y）R，则必有（x，y）R，称R为A上的反对称关系，也称R具有反对称性。例如，A=x，y，z，R=（x，x），（x，y），（y，z），则R是A上的反对称关系。对于二元关系的三种表示方法下面同样给出相对应的判定反对称关系的方法。1) 在表格表示法中，与对称关系的相反，若所有关于对角线对称的元素的空格没有同时选中，对角线上的不受限制，此时即为对称的二元关系。反之则不是。证明分析，根据反对称关系的定义有：如果有（x， y）R时就一定有（y， x）R，而这一组有序对在表格表示法中是处在对称的位置上的，与上面的判定方法结论一致。2） 在矩阵表示法中，反对称关系表现为所有关于主对角线对称的两个元素的值不能同时为1。若关系矩阵为rij,则当ij时，rij和rji不能同时为1，也就是rij=0。证明分析，根据反对称关系的定义有：如果有（x， y）R时就一定有（y， x）R，而这一组有序对在矩阵表示法中表现为在矩阵rij中,则当ij时，rij和rji不能同时为1，也就是rijrji=0。3）在图形表示法中，此处与对称关系则完全相反了，任何两个元素之间至多有一条边存在。证明分析，一条边表示一个有序对，反对称关系中一定不存在相反的有序对，故两个元素之间不同时存在两条边。4）在坐标图法中，除了45度斜角直线上的点外，没有其他关于该直线对称的点就可以判定该关系是反对称的。证明分析，根据反对称关系的定义有：如果有（x， y）R时就一定有（y， x）R，但当x= y时例外，即除去了45度斜角直线上的点，其他的点一定不会关于该直线对称。另外，这里特别注意，对称关系和反对称关系两个概念并不是相互否定的，即：不是对称关系的也不一定就是反对称关系，不是反对称关系的也不一定是对称关系。存在既不是对称关系也不是对称关系的关系，也存在即是对称关系又是反对称的关系。例如：A=x，y，z，v，R和R1是A上的二元关系，其中R=（x，y），（y，x），（z，v）R1=(x，x)，(y，y)很容易判别，R既不是对称的关系也不是反对称的关系，R1即是对称关系又是反对称关系。计算机程序实现与上面对称关系的一样，上面程序能判别关系是对称或者是非对称的。如一运行结果为：3.5 可传递的二元关系及其判定定义：R是A上的二元关系，每当有（x， y）R且有（y，z）R时，必有（x，z）R，则称R为可传递的二元关系，也称R具有可传递性。可传递的关系的判定有点复杂，下面介绍几种有效的方法进行判定。3.5.1 关系矩阵判别法有可传递二元关系的定义，可根据二元关系的关系矩阵直接判定关系的传递性。把定义转换成矩阵的表达就是：当矩阵中的元素rij=1且rjk=1时，则必有rik=1。否则可以判定该关系不是传递的。显然，该判定法事是对定义的一种转换，只适合规模比较小的情形，对于大型的问题该判别法是可行不可取的，繁琐且容易出错。3.5.2 关系复合矩阵判别法复合关系的定义：R是A到B的二元关系，S是B到C的二元关系，R和S的复合关系记作R S,它是A到C的二元关系，仅当（x, y）R且（y，z）R时，（x，z）R S定理：R是A到B的二元关系，其关系矩阵为MR，S是B到C的二元关系，其关系矩阵为MS，复合关系R S是A到C的二元关系，其关系的矩阵为MR S,则MR S=MRMS。由此我们可以得出传递关系的复合矩阵判别法：设R是集合A上的二元关系，如果RR2,则R是传递关系。证明：当（x, y）R且（y，z）R时，由复合关系的定义可知必有（x， z） R2，而RR2，所以（x， z）R，由此可知R是传递关系。因此，结合上面定理中的关系：MR S=MRMS易知，如果矩阵MR-（MR）2的元素中没有负数，则R是传递关系，否则R不是传递关系。3.5.3 Warshall算法引申判别法由二元关系的性质，一般的讲，当关系矩阵中的元素rij=1时，则应对第i行和第j行的元素作比较：第i行：ri1 ，ri2 ， rin第j行：rj1 ，rj2 ， rjn对于第j行中取值为1的元素，如：rj2=1，则第i行的对应列的元素值必定为1，否则该关系就不是传递的。如果取值为1则继续考察下一个，如果不是1则可以肯定该关系R不是传递的，立刻可退出判定。如前rj2=1，如果ri2=0则可以判定该关系R不是传递的。有了上面的理解，我们便不难理解下面的判定方法:首先介绍一种逻辑运算法布尔运算，布尔运算的规则如下： 0+0=0 1+0=0+1=1 1+1=1由于关系矩阵中的元素值仅为1或0，所以我们可以使用布尔运算的特点进行判定会带来很多方便。由布尔运算的特点，我们把矩阵中的第j行元素值布尔加到第i行的对应元素上，影响第i行结果的仅仅是第j行中元素值为1的元素。由上面的分析我们知道如果该关系是传递的，对于rij=1当第j行的任何一列的元素值为1则对应第i行的元素也是1，关系矩阵布尔运算之后不会发生变化，反之便会发生改变。由此我们便可以得出利用矩阵布尔运算判定传递关系的步骤：从矩阵的第1行开始，依次对各元素值进行判断，如果第j列元素值为1，则把关系矩阵中的第j行的元素值与第1行对应的元素值进行布尔运算，如此依次进行直到最后一行最后一列的那个元素为止。如果得到的关系矩阵与原来的关系矩阵相等则可以下结论：该二元关系是传递的，否则不是传递关系。上面运算过程实质上是体现了Warshall算法。实例：设A=x，y，z，v，w，R是A上的二元关系，R=（x, y）,（x, z）,（y, z）,（z, z）,（v, x）,（v, y）,（v, z）,（w, x）,（w, y）,（w, z）,（w, v）,是判定R是否是传递关系。判定步骤如下：该关系的关系矩阵为：从关系矩阵中第1行第一个元素开始依次考察元素值为1的元素。对于r12=1，把第2行的元素布尔加到第1行上去，操作后第1行没有发生变化，矩阵亦不变。对于r13=1，把第3行的元素布尔加到第一行上去，操作后第1行没有发生变化，矩阵亦不变。对于r23=1，把第3行中的元素布尔加到第2行上去，操作后第2行没有发生变化，矩阵亦不变。对于r33=1，把第3行中的元素布尔加到第3行上去，操作后第3行没有发生变化，矩阵亦不变。对于r41=1，r42=1，r43=1，r51=1，r52=1，r53=1，r54=1，依次同样的进行验证，验证完成后矩阵没有发生变化，由此可以判定该关系R是传递的。下面对穿的关系的判断给出计算机程序进行实现：#includeusing namespace std;void main()/输入二元关系数组cout请输入数组元素：endl; const int n=5; int ann;/初始化 int r,s;for(r=0;rn;r+)for(s=0;sars;/根据判定方法进行计算int bnn=0; int i,j,k;for (i=0;in;i+)for(j=0;jn;j+)if(aij=1)for(k=0;kn;k+)/依次进行布尔加运算bik=(aik|ajk|bik); /输出计算后的数组结果cout计算的结果数组为：endl;int p,q;for(p=0;pn;p+)for(q=0;qn;q+)coutbpq ;coutendl;/判断是否与原数组相等，相等则是传递的否则不是 int h,l;int count=0;for(h=0;hn;h+)for(l=0;ln;l+)if(ahl!=bhl)count=count+1;break;if(count=1)break;if(count=1) cout该关系不是传递的;else cout该关系是传递的;运行结果如下：4. 二元关系的计数我们经常遇到存在多少种情况的问题，在二元关系里该问题也同样存在，如在一个含有若干个元素的集合上能定义多少种某种二元关系等等，这就是本论文的另一个重点二元关系的计数。我们该如何解决它呢？下面将依次对各种情况予以分析并得出简单易行的结论。 为了便于推导计算，我们将借助二元关系的表格表示法。首先画出一个的表格，表示所含的个有序对。4.1 二元关系个数由二元关系的定义可知，能在集合A上定义多少个有序对即表示能定义多少种二元关系。根据表格表示法的含义，由上面的表格容易得知，共含个有序对。这些有序对构成二元关系时，可以取其中0个，1个，2个，个构成任一种二元关系。所有A上可定义不同的二元关系的个数为：。4.2 自反关系的个数从前面介绍的自反关系在表格表示法中的特征可知：如果R是A上的自反关系，显然R必含表格表示法中对角线上个方格表示的有序对。这是作为自反关系的充要条件。而决定自反关系个数则是余下方格的数目是，因为这几个有序对对于关系R是否为自反关系并无决定意义，关系R中含有余下的有序对的个数即为该关系可表示的自反关系的个数。由于余下的方格数可以取0个，1个，2个，个。因此A上可定义不同的自反关系的个数为：。4.3 反自反关系的个数从前面反自反关系在表格表示法中的含义，如果R是A上的反自反关系，显然R必不含表格对角线上个方格所表示的有序对，这是作为反自反关系的充要条件。而余下方格的数目是，我们可以任意从中取0个，1个，2个，个。因此，在A上可定义不同的反自反关系的个数为：。4.4 对称关系的个数对称关系在表格表示法中的特征是关于对角线对称的。因此当R是A上的对称关系时，只需考虑表格的上半部分（包括对角线上的个方格），因为下半部分对应的有序对必在其中。上半部分能进行选取的有序对数目（空格数）是：。因此A上可定义不同的对称关系的个数是：。4.5 反对称关系的个数当R是A上的反对称关系时，由定义，主对角线空格数可以取0个， 1个，2个，个，在此前提下，同时可以选取剩余的空格数，但须满足任意一空格被选择之后，其对应的关于对角线对称的空格一定不能选。因为不含主对角线的上半部分方格数目是，令。则在这m中取k个时，下半部分除与这k个关于主对角线对称的元素不能取，其它可取0个， 1个，2个，个。所以A上可定义不同的反对称关系的个数是：，其中。4.6 自反且对称关系的个数从前面章节的内容，我们很容易得知自反且对称的二元关系的充要条件是：表格中对角线上的空格全部必须包含在内，其他剩余的空格可从中任意选取但必须是关于对角线对称的。由此我们容易得知：当R是A上自反且对称关系时，决定该关系个数的只能是表格中不含对角线方格的部分的有序对（空格数）。而不含对角线方格的上半部分方格的数目是：。因此A上可定义不同的自反且对称关系的个数是：。4.7 不是自反又不是反自反关系的个数我们知道，自反关系的充要条件是对角线上的空格必须全部选中，反自反的充要条件是则是对角线上的空格全部不能包含。因此当R为A上的既不是自反，又不是反自反的二元关系时，R的表格表示在对角线上只能选1个，2个，个空格数，这也是既不是自反又不是反自反关系的充要条件。在此前提下，对角线外的个方格数的选择决定了该种关系的可定义个数并且可以任意选取，因此可以在A上可定义的不同的既不是自反又不是反自反的二元关系的个数是：。4.8 结论有了上面的分析，于是我们可以得出以下结论，设，则有：1. A上可以定义种二元关系。2. A上可以定义个不同的自反关系。3. A上可以定义个不同的反自反关系。4. A上可以定义个不同的对称关系。5. A上可以定义个不同的自反且对称的二元关系（即相容关系）。6. 上可以定义 种不同的反对称关系，其中，7. A上可以定义个既不是自反的又不是反自反的二元关系。8. A上的全部等价关系数目, 则（下一章节内容）。5. 等价关系的判定与计数定义：R是A上的二元关系，如果R是自反的、对称的、传递的二元关系，则称R是A上的等价关系。5.1 等价关系的判定由等价关系的定义知，如果以集合的观点来看，等价关系实际上是自反关系、对称关系、传递关系的一个交集。里面的元素（有序对）同时满足以上三种二元关系。由此易知，如果把有限集合A中的元素按组排列，则等价关系在表格表示、矩阵表示、图形表示中具有明显的特征，这些特征能帮助我们很快的判断出等价关系。在表格表示法中，由于自反关系要求对角线上的元素全部选中，对称关系要求是对称的，结合传递关系的特殊性可知：等价关系的表格表示法中，选中的元素成若干个正方形，且对角线上的元素全部在内。同样矩阵表示法与表格表示法特征一样。例如：A=1，2，3，4，5，6，7，R是A上的模3同余关系。我们把A中的元素以余数为组进行排列：A=1，4，7，2，5，3，6，则A的表格表示与矩阵表示呈现如下特征：表格特征： 1 4 7 2 5 3 6 1 4 7 2 5 3 6 矩阵特征：在图形表示法中，等价关系同样出了很显眼的特征：关系图中每个点都有回路，即环，同一组内的任意两点都有两条方向相反的有向边。同样，在坐标图法中，45度斜角直线上的点的个数等于集合元素的个数外，其他点一定是关于该直线对称的。由于这几种显眼的特征，等价关系的判断很容易。5.2 等价关系的计数定义：设A是集合，A1, A2, An,是A的子集，如果满足以下条件：则以A1, A2, An作为元素构成的集合S= A1, A2, An 称为集合A的划分，每一个子集Ai称为块。定理：集合A的划分能唯一的确定A上的一个等价关系；反之确定了A上的等价关系也能唯一的确定A上的一个划分。A上的等价关系与划分是一一对应的。（由于该定理的证明还牵涉到其他知识点，覆盖面比较广，在此不再证明，有兴趣了解该定理的详细证明可以参考参考文献2的第38页。）于是，求一个有限集合A 上等价关系的个数问题就转化为求集合A 的不同划分个数。现在的问题令表示将有n 个元素集合A划分为r 个块的方案数，显然r 可取1 ，2 ，n ，并且A 上的总的划分数，若把A集合的n 个元素抽象成n个可区分的球，r 个无序的块抽象为r 个不可区分的盒子，则就表示将n 个可区分的球放入r 个不可区分的盒子内，不允许有空盒子的放置方案数，可按如下方法进行计算：若 独占一盒，则放置方案数为。若 不独占一盒，可认为先将放入r 个盒内，不允许有空盒，共有 种放置方案数，再将放入r 个盒中的任意一个盒子中，共有r 种放置方案。 由乘法原理知，共有 种放置方法。 再根据加法原理知，我们有递推公式：。显然，。通过推导有A上的等价关系的个数是：，其中表示从r个元素中取出i个元素的组合数。从上面的分析不难看出，虽然有最后的计算公式，但对于一个比较大的集合其计算量是非常大的，因此如何用计算机程序进行实现成了大家所期望的。下面给出了上面等价关系计数的计算机程序进行实现：#include#includeusing namespace std;int main()int n,r;static int sum=0;/等价关系总数int i=0;int j=0;cout请输入集合中元素个数：n;int f(int ,int );/格式控制for(j=0;j=n+1;j+)if(j=0)coutsetw(8)n/r;else if(j=n+1)coutsetw(8)SUMendl;else coutsetw(8)j;/按格式输出结果for(i=0;i=n+1;i+)if(i=0)coutsetw(8)n;else if(i0) coutsetw(8)f(n,i); sum=sum+f(n,i);else coutsetw(8)sumendl;/函数递归计算int f(int n,int r)int sum=0;if(n=r|r=1)sum=1;elsesum=f(n-1,r-1)+r*f(n-1,r);return sum;运行结果如下图所示：小结 本文主要针对自反、反自反、对称、反对称、传递几种二元关系给出了相对应的