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

Author ssjs Mail 632141456 看了离散数学中的关系整理了一点关于 n 元集合中各种关系的计算 现写下这个方便大家 学习交流理解 对文章所致一切后果不负任何责任 请谨慎使用 如有错误之处请指正 如有错误之处请指正 定义 1 对称 对于 a b Rab b a A有如果只要 2 反对称 如果RabRbabb a A a和时仅当 3 自反 如果对每个元素R Aa aa有 4 反自反 如果对于每个R Aa aa有 5 传递 如果对R R R A cacbbacba则且 6 非对称 如果 注 其中是含 a a 这样的有序对的 R R abba推出 重要 集合 A 的关系是从 A 到 A 的关系 也就是说集合 A 的关系是的子集 AA 如下结论 N 元集合上的自反关系数为 1 2 nn N 元集合上的对称关系数为 2 1 2 nn N 元集合上的反对称关系数为 2 1 n3 2 nn N 元集合上的非对称关系数为 2 1 3 nn N 元集合上的反自反关系数为 1 n 2 n N 元集合上的自反和对称关系数为 2 1 n 2 n N 元集合上的不自反也不反自反关系数为 1 nn 222 2 n 下面是上面结论的计算 1 自反 也就是说集合 A 有 n 平方个有序对 由自反定义可知 对 2 AA Ann 因为 所以 n 个有序对一定在所求关系中 否R Aa aa有 3 2 1iX X n ii 其中 则的话此关系就不是自反的了 那么还有个有序对 所以由集合子集对应二进制串nn 2 可得自反关系数为 1 n 22 2 nnn 下图有助于理解 1 1 2 2 n n 1 2 1 3 n 1 n N 个有序对 个有序对nn 2 2 对称 也就是说集合 A 有 n 平方个有序对 由对称定义可知 对于 2 AA Ann 因为 另外知道在 n 平方个有序对中有 n 个有序对Rabb b a A a有只要 相应的就有个有序对 X Y 且 X 定义可知后面 3 2 1iX X n ii 其中nn 2 Y 的 nn 2 个有序对只能成对出现 所以有对 前面的那 n 对可以出现任意多对 2 n2n 图片如下 1 1 2 2 n n 1 2 1 3 n 1 n n 个有序对 2 1 3 1 n n 1 2 个有序对对nn 2 共有 n 2 个元素nn 2 即 2 个nn 2 所以得到对称关系数为 2 1 2 nn 3 反自反 也就是说集合 A 有 n 平方个有序对 由对称定义可知 如果对 2 AA Ann 因为 于每个 构成该关系的元素个数为个 所以得出结论 这R Aa aa有nn 2 1 n 2 n 个简单 不多说 4 自反和对称 即是求自反的又对称的 由 1 知要是自反的就只能在个有序对中生成子集 又nn 2 由对称定义可知 将个有序对分成形如 a b 与 b a 的 2 个有序对对 所以有nn 2 nn 2 自反和对称关系数为 如下图 2 1 n 2 n 1 1 2 2 n n 1 2 1 3 n 1 n n 个有序对 2 1 3 1 n n 1 要自反这 n 个必在所求关系中 2 个有序对对nn 2 N 个有序对只有 1 种可能 有种可能 2 1 n 2 n2 1 n 21 n 5 不自反也不反自反 不自反也不反自反 不自反不反自反 不反自反不自反 2 n 2 反自反 自反 2 n 2 22 2 1 1 n2 nnnn 1 n 222 2 nn 6 非对称 由定义 如果 很清楚形如 a a 的有序对不在所求关系中 R R abba推出 所以所求关系只能中剩下的个有序对中来生成 如下图 nn 2 1 1 2 2 n n 1 2 1 3 n 1 n n 个有序对 2 1 3 1 n n 1 这 n 个一定不在所求关系中 2 个有序对对 nn 2 由定义上图的同色对中只能取一个或是一个也不取 就有三种状 态 1 选上面的 2 选下面的 3 两个都不选 选取同色对 0 1 不选 选上还是选下 0 1 选上 选下 由题知 不选 选上 选下是三种互斥结果 同集合二进制求集合个数原理 可得集合子 集个为 2 1 3 nn 7 反对称 由定义 如果 如下图 RabRbabb a 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 个有序对对 nn 2 由 6 可知 n 2 2 1 3 nn 所以得结果 即 n 2 2 1 3 nn2 1 n3 2 nn 注 其它组合或是要求可由定义同理推出 不要怕麻烦 其实不那么难 也还有许多方 法可以导出结果 如矩阵之类的 强烈推荐看下 Discrete Mathematics and Its Ap