离散数学基础 · 第 1 讲：集合与基本运算
离散数学基础
2026年9月8日
1. 课程介绍
王若松 ruosongwang@pku.edu.cn
周佳仪 flyfeather@stu.pku.edu.cn
疏彦凯 syksykccc@stu.pku.edu.cn
考试成绩：
- 平时成绩：20-30%
- 期中考试：20%
- 期末考试：60-50%
考试形式：闭卷
期中考试：第九周，11月3日（周二7-8节） 随堂考试
期末考试：2027年1月5日（周二下午），考试范围是全部内容（可能略有侧重）
作业：来自教材，每章讲完后布置
文件名：学号_姓名_离散第X次作业.pdf
完成每次作业即可获得平时作业的满分，注意，不能抄袭AI、同学。
课程大纲
集合论、初等数论、图论、组合数学、代数结构、数理逻辑、计算模型（文法与自动机）
前四个是期中考试的范围（大致）
2. 为什么要学习离散数学？
举例
RSA-260的一个因子被找到了。如果一千位的大整数很容易被分解，那么公钥私钥就不再安全了。
Breaking the sorting barrier for directed single source shortest path
数学的形式化证明。
3. 集合论
- 集合
- 二元关系
- 函数
3.1. 集合
3.1.1. 集合的基本概念
集合：把一些事物汇集到一起组成的整体。
- 集合是一个不能精确定义的基本概念
- 这些事物成为集合的元素或成员
例如
- 方程的实数解集合
- 26个英文字母
- 表示
集合通常用大写英文字母表示： 自然数集：, 整数集：, 有理数集：, 实数集：等。
集合的三要素
- 确定性、互异性、无序性
- 元素与集合的关系： 以及
举例
为了体系上的严谨，我们不考虑 这种情况。
集合之间的关系：
集合相等： 称，如果 且
空集：没有任何元素的集合，记作。
定理1
空集是一切集合的子集。
证明：反证法，略；
推论
空集是唯一的。
幂集：A的全体子集构成的集合称为A的幂集，记作。
全集：在某个特定的讨论范围内，包含所有元素的集合称为全集，记作 。
3.1.2. 集合的运算
或者：, 且：。
交集：
并集：
相对补集： 称为A相对于B的相对补集。
对称差：
绝对补集： 给定全集的子集A的绝对补集定义为：
集族：
由集合构成的集合统称为集族，记作。
前面定义的交并称为初级交、初级并。
设为一个集族。中全体元素的元素组成的集合称为的广义并。记作
也是一个集族。
特别地，
但是我们没有定义全集 ，所以空集的广义交没办法定义。
一元操作从右向左进行：
一元运算优先于二级运算。
3.1.3. 集合运算的性质
幂等律
结合律
交换律
分配律 ,
同一律
零律
排中律
吸收律
德摩根律
双重否定律