足球比分直播

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

返回
离散数学N元集合关系个数计算.doc_第1页
第1页 / 共3页
离散数学N元集合关系个数计算.doc_第2页
第2页 / 共3页
离散数学N元集合关系个数计算.doc_第3页
第3页 / 共3页
亲,该文档总共3页,全部预览完了,如果喜欢就下载吧!
资源描述:
Authorssjs Mail632141456qq.com看了离散数学中的关系整理了一点关于 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 元集合上的自反关系数为 12?nN 元集合上的对称关系数为 /?N 元集合上的反对称关系数为 21n3N 元集合上的非对称关系数为 /?N 元集合上的反自反关系数为 1nN 元集合上的自反和对称关系数为 2/N 元集合上的不自反也不反自反 关系数为 1nn??下面是上面结论的计算1,自反也就是说集合 A 有 n 平方个有序对,由自反定义可知,对2A,n??因 为所以 n 个有序对 一定在所求关系中,否Ra??有 ??.3,21iX,ni?其 中则的话此关系就不是自反的了,那么还有 个有序对,所以由集合子集对应二进制串?2可得自反关系数为 12?下图有助于理解。(1,1 2,2.......n,n | 1,2 1,3.........n-1,nN 个有序对 个有序对n22,对称也就是说集合 A 有 n 平方个有序对,由对称定义可知,对于2A,n??因 为。另外知道在 n 平方个有序对中有 n 个有序对Rabb??,a,a有只 要,相应的就有 个有序对(X,Y 且 X ,定义可知后面??.3,1iXi其 中 ?2 Y?的 n?2个有序对只能成对出现,所以有 对。前面的那 n 对可以出现任意多对。/图片如下。(1,1 2,2.......n,n 1,2 1,3.........n-1,nn 个有序对 2,1 3,1.........n,n-1 /2 个有序对对n?2共有 n /2 个元素即 /2 个?2所以得到对称关系数为 2/1?n3,反自反也就是说集合 A 有 n 平方个有序对,由对称定义可知,如果对2A,n??因 为于每个 ,构成该关系的元素个数为 个,所以得出结论 ,这Ra??有 ?2 1n2?个简单,不多说。4,自反和对称即是求自反的又对称的,由 1 知要是自反的就只能在 个有序对中生成子集,又n2由对称定义可知,将 个有序对分成形如 a,b与b,a的 /2 个有序对对。所以有n?2 ?自反和对称关系数为 。如下图/(1,1 2,2.......n,n 1,2 1,3.........n-1,nn 个有序对 2,1 3,1.........n,n-1要自反这 n 个必在所求关系中 /2 个有序对对n?2N 个有序对只有 1 种可能· 有 种可能 /1 2/1n??5,不自反也不反自反不自反也不反自反 不自反 不反自反 ? )不 反 自 反不 自 反( ??2n 反 自 反 )( 自 反 11n2??n ?n6,非对称由定义如果 ,很清楚形如a,a的有序对不在所求关系中。R,,??aba推 出所以所求关系只能中剩下的 个有序对中来生成。如下图。n?2(1,1 2,2.......n,n 1,2 1,3...................................n-1,nn 个有序对 2,1 3,1....................................n,n-1这 n 个一定不在所求关系中 /2 个有序对对 2由定义上图的同色对中只能取一个或是一个也不取,就有三种状态 1)选上面的 2)选下面的 3)两个都不选选取同色对0 1不选 选上还是选下0 1选上 选下由题知,不选,选上,选下是三种互斥结果。同集合二进制求集合个数原理,可得集合子集个为 2/13?n7,反对称由定义如果 如下图。Rababb???,,,Aa和时仅 当(1,1 2,2......................n,n 1,2 1,3...................................n-1,nn 个有序对 2,1 3,1...................................n,n-1这 n 个有序对可以出现任意多次 /2 个有序对对 n?2由 6 可知)2?/13所以得结果 即n2/13?2/1n【注】其它组合或是要求可由定义同理推出。不要怕麻烦,其实不那么难,也还有许多方法可以导出结果,如矩阵之类的。强烈推荐看下 Discrete Mathematics and Its Applications Seventh Edition 更新版的更好哈,讲得真的很不错。参考资料Discrete Mathematics and Its Applications SeventhEdition
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播