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

上传人:hw****26 文档编号:3888798 上传时间:2019-08-17 格式:DOC 页数:3 大小:206.09KB
下载 相关 举报
离散数学N元集合关系个数计算.doc_第1页
第1页 / 共3页
离散数学N元集合关系个数计算.doc_第2页
第2页 / 共3页
离散数学N元集合关系个数计算.doc_第3页
第3页 / 共3页
亲,该文档总共3页,全部预览完了,如果喜欢就下载吧!
资源描述

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

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲资料库 > 生活指南

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。