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

上传人:gbs****77 文档编号:10445726 上传时间:2020-04-12 格式:DOC 页数:3 大小:206.09KB
返回 下载 相关 举报
离散数学N元集合关系个数计算_第1页
第1页 / 共3页
离散数学N元集合关系个数计算_第2页
第2页 / 共3页
离散数学N元集合关系个数计算_第3页
第3页 / 共3页
亲,该文档总共3页,全部预览完了,如果喜欢就下载吧!
资源描述
Author:ssjs Mail:632141456qq.com看了离散数学中的关系整理了一点关于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 Edition 更新版的更好哈,讲得真的很不错。参考资料:Discrete Mathematics and Its Applications SeventhEdition
展开阅读全文
相关资源
相关搜索

当前位置:首页 > 办公文档 > 解决方案


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!