离散数学基础 · 第 2 讲：集合运算与有穷集计数
离散数学基础
2026年9月10日
1. 集合运算的性质
1.1. 例题
证明：
证：
证明：
证：
计算：
2. 有穷集的计数
集合之间的关系和初级运算可以使用Venn图来表示。
这是小学奥数的内容，在此略去。
2.1. 一个有趣的例子
伯努利信封排错问题
2.1.1. 问题描述
一共有编号为的信封和张写有对应号码的信纸。将信纸放入信封中，要求每个信封里恰好放入一张信纸。问有多少种放法使得没有任何一封信纸被放入与它号码相同的信封中？
解答：我们可以很容易列出：（假设代表有选定个一定安装正确，而其他的任意安放）
…
设 表示：选定 个号码，要求这 张信纸一定放入对应的信封中，其余信纸任意放置。
选定这 个号码有 种。固定它们后，剩余的 张信纸可以任意排列，共有 种。因此
特别地，
由于一种放法中可能有多个号码同时放置正确，所以这些情况会被重复计算，需要使用容斥原理。
先从全部 种放法中减去至少有一个选定号码正确的情况，再加回至少有两个选定号码正确的情况，然后继续正负交替。因此，全部错排的数量为
代入 ，得到
所以答案为
3. 二元关系
3.1. 有序对
由元素组成的对称为有序对或者序偶。记作 当且仅当有序对对应位置上的数相等才认为两个有序对相等。
笛卡尔积
用中的元素作为第一元素，中的元素作为第二元素组成的有序对的集合称为和的笛卡尔积，记作
例如：
性质：
笛卡尔积不满足交换律！
对并和交满足分配律：
关于笛卡尔积的一个问题
那么逆推是否成立？
分析：
需要讨论 和 的情况。
若
任取 。因为 ，可以取 ，于是
因此 ，从而 。
同理可得 。
若
此时
所以无论 和 是什么，都有
其中 恒成立，但不能推出 。
若
此时
其中 恒成立，但不能推出 。
若
此时
并且
都恒成立。
因此，一般情况下逆推不成立。只有当 且 时，才有