离散数学N元集合关系个数计算.doc

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