1、Author：ssjs Mail：看了离散数学中的关系整理了一点关于 n 元集合中各种关系的计算，现写下这个方便大家学习交流理解。对文章所致一切后果不负任何责任，请谨慎使用。如有错误之处请指正。定义：1，对称：对于 a,b Rab),(),a(,A有如 果 只 要2，反对称：如果 bb,a和时仅 当3，自反：如果对每个元素 ),(有4，反自反：如果对于每个 a有5，传递：如果对 ),(, cacc则且6，非对称：如果 【注】其中是含（ a,a)这样的有序对的。R)()(ba推 出【重要】集合 A 的关系是从 A 到 A 的关系 （也就是说集合 A 的关系是 的子集） 。如下结论：N 元集合上的
2、自反关系数为： )1(2nN 元集合上的对称关系数为： /N 元集合上的反对称关系数为： 2)1(n3N 元集合上的非对称关系数为： /N 元集合上的反自反关系数为： )1(nN 元集合上的自反和对称关系数为： 2/N 元集合上的不自反也不反自反 关系数为： )1(nn下面是上面结论的计算1，自反也就是说集合 A 有 n 平方个有序对，由自反定义可知，对2A,n因 为所以 n 个有序对 一定在所求关系中，否R)(a有 ).3,21iX,(ni其 中则的话此关系就不是自反的了，那么还有 个有序对，所以由集合子集对应二进制串2可得自反关系数为 )1(2下图有助于理解。（1,1) (2,2).(n,
3、n) | (1,2) (1,3).(n-1,n)N 个有序对 个有序对n22，对称也就是说集合 A 有 n 平方个有序对，由对称定义可知，对于2A,n因 为。另外知道在 n 平方个有序对中有 n 个有序对Rabb),()a(,a有只 要，相应的就有 个有序对（X,Y) 且 X ，定义可知后面.3,1iX(i其 中 2 Y的 n2个有序对只能成对出现，所以有 对。前面的那 n 对可以出现任意多对。/)(图片如下。（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n)n 个有序对 (2,1) (3,1).(n,n-1)( )/2 个有序对对n2共有 n+ ( )/2 个元素即
4、( )/2 个2所以得到对称关系数为： 2/)1(n3，反自反也就是说集合 A 有 n 平方个有序对，由对称定义可知，如果对2A,n因 为于每个 ，构成该关系的元素个数为 个，所以得出结论 ，这R)(a有 2 )1(n2个简单，不多说。4，自反和对称即是求自反的又对称的，由 1 知要是自反的就只能在 个有序对中生成子集，又n2由对称定义可知，将 个有序对分成形如 (a,b)与(b,a)的( )/2 个有序对对。所以有n2 自反和对称关系数为： 。如下图/)(（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n)n 个有序对 (2,1) (3,1).(n,n-1)要自反这 n
5、 个必在所求关系中 ( )/2 个有序对对n2N 个有序对只有 1 种可能 有 种可能 = /)1 2/)1(n5，不自反也不反自反不自反也不反自反 = 不自反 不反自反 = ）不 反 自 反不 自 反（ 2n= 反 自 反 ）（ 自 反= )(1()1n2n= n6，非对称由定义：如果 ，很清楚形如(a,a)的有序对不在所求关系中。R),(),(aba推 出所以所求关系只能中剩下的 个有序对中来生成。如下图。n2（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n)n 个有序对 (2,1) (3,1).(n,n-1)这 n 个一定不在所求关系中 ( )/2 个有序对对 2
6、由定义上图的同色对中只能取一个或是一个也不取，就有三种状态 1）选上面的 2）选下面的 3）两个都不选选取同色对？0 1不选 选上还是选下？0 1选上 选下由题知，不选，选上，选下是三种互斥结果。同集合二进制求集合个数原理，可得集合子集个为： 2/)1(3n7，反对称由定义：如果 如下图。Rababb),(),(,Aa和时仅 当（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n)n 个有序对 (2,1) (3,1).(n,n-1)这 n 个有序对可以出现任意多次 ( )/2 个有序对对 n2(由 6 可知）2/)13所以得结果 ： 即n2/)1(32/)1(n【注】其它组合或是要求可由定义同理推出。不要怕麻烦，其实不那么难，也还有许多方法可以导出结果，如矩阵之类的。强烈推荐看下 Discrete Mathematics and Its Applications Seventh Edition 更新版的更好哈，讲得真的很不错。参考资料：Discrete Mathematics and Its Applications SeventhEdition
