离散数学

第一章：略

第二章：命题逻辑

自然语言符号化

什么叫逆命题、否命题和逆否命题

基本等值式

什么叫做等值式

称命题逻辑公式A和B逻辑等值(logically equivalent)，简称等值，记为A=B，如果
对任意真值赋值函数$\sigma:Var→2$，A和B在下的真值都相同，即都有$\sigma(A）=\sigma(B)$

如何证明呢？
- 证明方法
- 非形式化
模式与实例

题型：
- 判断命题逻辑公式类型（永真式、矛盾式、可满足式）
  - 利用等值演算来证明逻辑等值式

析取、合取范式

==单个的文字可以看做是一个合取式或一个析取式，单个的合取式可看做是析取范式，单个的析取式也可看做是合取范式==
易错！

注意：上例子只给出了一个或两个的合、析取范式，但实际上也可以有多个，不要没见过大蛇o屎

范式中==只出现与、或、非运算，且否定只出现在命题变量的前面==

题型：给出一个公式，让你求合取、析取范式
- 求与公式逻辑等值的析取范式
  先通过蕴涵等值式和双蕴涵等值式转换为不含→和↔的公式
  然后用德摩尔根律将所有否定运算符移到命题变量的前面
  最后用分配律将合取运算符放到括号里的文字间，析取运算符放到括号外的合取式之间

![](image_10.jpg)

![](image_11.jpg)

极小项、极大项

合取会变小，析取会变大

超级易错点：极大项是成假赋值

也就是说，命名的下标是通过成真和成假赋值的二进制值来确定的

只是我们在写出对应最大项公式的时候，要反过来

题型
- 给一个公式求主合取范式和主析取范式
- 方法：
  - 真值表
    - 画出真值表，1的就是$m_i$，0的就是$M_i$
    - 如果要写出具体的字母，对m成真赋值，对M成假赋值
  - 等值演算法
    - 先求出主析取范式，遇到不是的，拓展（与一个1，然后用排中律，再用分配律）
    - 然后成真赋值
    - 得到主析取范式（m表示）
    - 不是最小项的就是极大项
    - 例子

推理系统

首先需要注意的是，推理有效与否与公式真假没有关系

题型一：形式化证明

附加前提法

归谬法

题型二：自然语言的证明

易错点：

置换和替换

替换就是完全替代，所以要全部换掉。置换弱一点

第三章：一阶逻辑

谓词逻辑命题符号化

全称量词和存在量词

易错点！！

谓词逻辑命题符号化

谓词逻辑公式及其解释

更多的，只要自由出现了一次，就是自由出现的

改名

约束变量改名

注意：不能换约束出现的，如H中的x

自由变量改名

量词消去和真值

求公式在一定解释下的真值

一阶逻辑的等值演算

前束范式

替换实例

为什么单独放出来呢，是因为我觉得：

他其实就是告诉你
命题逻辑公式那些等值式
全都可以替换
也就是告诉你，全都可以继续用
从而把第二章一下子联系起来了

推理系统

推理系统和命题逻辑的类似

量词引入和消除

易错点！！！

量词例化规则只能针对辖域是整个公式的量词使用

必须先使用存在例化规则引入个体常量c，然后使用全称例化规则时可使用个体常量c

第五章：集合

181定义集合的方法
183重要的定义集合的定义
187交的定义

集合并保持子集关系

192差和补

一些定理

集合运算及其元素定义法

幂集

195空集的幂集相关的易错点、保持子集关系

证明的方法
- 通过定义证明
- 通过集合等式
- 子集的包含关系

集合的容斥原理

==基本集合等式表==

记住以下这些可以加快选择题做题的速度

证明题的时候，优先从有减号的一边入手，将减号化成交

==203集合运算与子集关系==

第六章：关系

211有序对笛卡尔积的定义（用笛卡尔积的定义来证明简单的集合等式）

特殊的关系

212关系的定义
214关系图和关系矩阵

关系的运算

关系逆的定义，关系复合的定义

注意记住符合的定义，本质上是在找中介

218关系的运算，关系矩阵的运算
219关系逆的基本性质
- 逆的逆等于自身
- 关系逆保持子集关系
- 逆和与或是可交换的（谁先谁后）
- 关系逆和关系复合交换次序，括号内要反转
  
  什么叫做保持子集关系呢，就是
  
  这在许多证明中很有用
  
  例题
220-221关系复合的基本性质
- 交换律❌
- 结合律✅
- 恒等关系是单位元
- 关系复合保持子集关系
- 关系复合对并分配，对与不分配（本质上是存在量词对析取分配而对合取不分配）
  - 复合在外，或在括号内

关系的性质

要明确定义：元素定义法，还有性质：集合运算法
自反
- 223自反的定义
- 224上面，易错点，自反与非自反的互斥但非对立关系
- 224下面定理6.8定理的充分必要条件（集合运算）
对称
- 225对称的定义
- 226下面定理6.9对称的充分必要条件（集合运算）
传递
- 228传递的定义
- 229下面定理6.10传递的充分必要条件（集合运算）
汇总
- 231关系定义和性质
  
  注意如果只有一个元素，那么前件为假，蕴含式为真，所以只含有一个元素的关系也是传递的
- 231关系运算与关系性质之间的联系
做题技巧，用关系图来判断关系的性质
- 画出一个关系的关系图，如果每个点都有自回路，那么就是自反的
- 如果每两个点之间，要么没有直接通路，要么有双向直接通路，那么就是对称的
- 如果能形成自闭环，那么是传递的
易错点——下面的都是✔
1. 一个==非空==关系如果是自反的，那它一定不是反自反的
2. 存在既不是自反，也不是反自反的关系——存在某些成立，也有些不成立
3. 存在既是对称也是反对称的关系——ΔA
4. 存在既不是对称也不是反对称的关系
5. 恒等关系除了不是反自反的，其他都是
给出参与运算的关系都有列对应的性质，那么运算的结果关系是否也有列对应的性质


关系运算	自反性	反自反性	对称性	反对称性	传递性
==关系逆运算R^(-1)==	是	是	是	是	是
==集合交运算R∩S==	是	是	是	是	是
集合并运算R∪S	是	是	是	否	否
集合差运算R-S	否	是	是	是	否
关系复合运算R∘S	是	否	否	否	否

可以分别用元素法和集合法证明a

关系的闭包

所谓闭包，就是要用最少的元素补充我们的集合，使其满足基本的性质（自反，对称，传递）

闭包的定义和性质
- 233关系闭包的定义
- 234定理，若R为XX，则XX闭包是自己
- 234定理，闭包保持子集关系
  
  例题
  
  ABD都在考察同一件事情，也就是定义里的“包含R”
  
  C的话考察的是闭包的最小性

闭包的运算

236定理：如何补充以变成自反和对称闭包
237关系的幂运算
237定理：传递如何补充成为闭包


关系代数中的概念	图论中的概念
二元关系 R	有向图的边集 E
关系的传递性	图中节点间的路径可达性
关系幂 Rn	从一个节点到另一个节点的长度为 n 的路径
传递闭包 R∗	图的传递闭包（所有可能路径）

如何补充以变成传递闭包
- 通过逻辑积计算关系矩阵
  - 求幂
  - 所有幂的并
- Warshall算法
  - 每次画出第x行为1的列和第x列为1的行，然后这些线的交点置为一
等价关系
- 242定义
  - 满足自反、对称、传递
- 等价类
  - 244定义
    - 记作$[a]_R$
  - 性质
    - 总有$a∈[a]_R$
  - 理解
    - 就他妈求连通分量，画出图来，圈就行了
    - 也可以直接看跟x有关系的所有值，这些值构成的集合就是x的等价类
    - $[a]_R= [b]_R当且仅当⟨a, b⟩∈R$
    - 以一个模7同余为例子
    - 我们可以将整数集拆分成这样子7组
    - 每一组里面的元素，都是彼此之间满足模7同余的
    - 任意不同组别的元素都是不满足模7同余的
    - 这样的一组就叫一个等价类
    - 所有的等价类构成这个全集的一个划分
    - 把每个等价类作为一个元素，那么这个集合就是👇
- 商集
  - 所有等价类的集合$A/R$
偏序关系
- 247定义
  - 满足自反、反对称、传递
- 偏序集
  - 偏序集（Partially Ordered Set，简称 poset）描述了一个集合中元素之间的一种“部分”顺序关系。与完全排序的集合（例如自然数集合上的大小关系）不同，偏序集中的元素==不一定能够比较大小==，也就是说，==有些元素==之间没有明确的顺序关系。
  - 可比
    - 虽然是用<符号来表示，但其实表达的还是满足偏序关系
  - 全序（链）
    - 全都可比
  - 偏序
    - 部分不可比
- 覆盖
  - $a<b$且不存在c使得$a < c, c < b$（两个不等式都要满足才行）
  - 也就是紧紧挨着，中间不再有更多的元素满足偏序关系
- 哈斯图（用来找极大元和极小元）
  - 去掉自环
  - 只保留覆盖的边（无第三边）
  - 从下往上
- 最大元、最小元
  - 与所有元素都可比才行，不一定存在
  - 就是哈斯图上，连接所有分叉的唯一最高点
  - 例子
    
    12和8、10、9、11都不可比，所以不存在最大元
- 极大元、极小元
  - 没有元素可以a更大/小了
  - 可能有元素和它不可比
  - 可能也不存在，如整数集$\Z$，四个都不存在
  - 例子—同上
    - 8、12、10、9、11、7都是极大元
    - 就是哈希图上面没有分叉了的
- 上界、下界
  - 对象是S的子集
  - 上界b不一定在S中
  - 但是b>S中任意元素，==都要能够比较==才行
  - 可以有很多个
- 上确界、下确界
  - 最小的上界
  - 最大的下界
  - 如果对于全集
    - 上确界就是最大元
    - 下确界就是最小元
  - 对于空集
    - 上确界就是最小元
    - 下确界就是最大元

关系证明题

第一步考虑能不能用集合语言来叙述，因为集合语言是一阶逻辑语言更高级的抽象

如果集合语言行不通，不要傻傻发呆，可以尝试符号语言，老老实实抓住定义去做

第七章函数

260函数的定义

注意是对==所有==的A中的元素，B中都有==唯一==的元素与其对应
260定义域、陪域的定义

260像集和逆像集的定义
- 像集就是给出定义域的子集求值域
- 逆像集就是给出值域范围反求定义域
262性质
- $f$ 保持子集关系$S\subseteq U→f(S)\subseteq f(U)$
- 函数与集合交可以交换次序

单函数、满函数、双函数的定义

单函数
- B中每个元素==至多==有一个A中的元素与其对应
- 可以没有对应
- 做题的时候带入$f(x)=f(y$) 看有无 $x=y$
满函数
- B中每个元素==至少==有一个A中的元素与其对应
- 必须要囊括值域的每一个元素
双函数
- 既是单函数也是满函数
- B中每个元素有==唯一==一个A中的元素与其对应

266函数的复合
- 其实就是关系的复合
- 保持子集关系
- 保持单满性
- 满足结合律

267逆函数的定义
- 注意前提是双函数
集合基数的基本
- 这一部分不会出题考试
- 但是面试的时候可能会问到

函数增长和算法效率分析

281定义大O记号
- 存在k和C当 $x>k$ 有$|f(x)| ≤ C|g(x)|$
- 这一部分出题：证明某个函数是$O(x^3)$而不是$O(x^2)$
- 只需要找到对应的k和C即可
大O记号的传递性
O的加法定理
- $f_1(x) + f_2(x) \in O(max(g_1, g_2))$
O的乘法定理
- $f_1(x). f_2(x) \in O(g_1 . g_2)$
284定义大$\Omega$记号
- $存在k和C当x>k有|f(x)| ≥ C|g(x)|$
O的除法定理
- $f_1(x)是O(g_1), f_2是\Omega (g_2) 那么f_1/f_2 是O(g_1/g_2)$

第八章：计数组合

计数

302加法原理乘法原理
- 独立性
  - 无论前面选择什么，后面的==方法数==（注意仅仅是数字，究竟是什么方法不care）==不变==
  - 也可以理解成，如果可以==直接用乘法原理==的，那就是有独立性
- 相关性
  - 前面的选择就对后面有影响
  - 易错
    - 可以同时有相关性和独立性
    - 不相关→独立
    - 独立 !→ 不相关
- 305减法原理
  - 正难则反
- 306除法原理（不是重点）
  - 必须保证是满射
  - 例子：圆桌排列、苯环取代
- 306一一对应原理
  - 提供了一种通过建立两个集合之间的一一对应关系来计算集合大小的方法。具体来说，如果两个集合之间存在一个一一对应（双射）关系，那么这两个集合的元素个数必然相等。
- 308容斥原理
- 集合差计数公式
- 两集合容斥原理
- 三集合容斥原理
- 鸽笼原理
  - 很容易指导什么是鸽子
  - 但是什么是鸽笼才是最重要的
  - [[组合计数|组合计数]] 例题
  - 不会是考试重点

排列组合

==不允许重复的==
316全排列
- 从n个里选择 r 排列，与顺序有关
- 记作$P_n^r$
318组合数
- 从n个里选择 r 与顺序无关
318证明方法
- 组合证明
  - 举一个针对同一集合的不同计数例子
  - 通常可以举例：学生选学生会，学生会选主席、长度为n的字符串
- 代数证明
  - 通过数学归纳法和组合数计算公式证明
技巧
- 至少有一名男生——全集减去一名男生都没有的
- 奇数偶数、是否重复，注意判断
323二项式定理
- $(x + 1)^n = \Sigma_{i= 0}^n(^n_i)x^i$
- 令$x=1$可得所有项之和
- 令$x=-1$，结合上面，得到奇偶项关系
325帕斯卡等式
- $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
- 在用数学归纳法证明一些等式，归纳递推的时候很好用
326经常用到的公式
==328允许重复的排列组合==
328$每类物体分别有m1、m_2…m_n个的n类物体的重复度为m_1+m_2+…+m_n=r的排列数为\\binom{r}{m_1}\binom{r-m_1}{m_2}…\binom{r - m_1 - m_2 - …-m{n-1}}{m_n} = \frac{r!}{m_1!m_2!…m_n!}$
- 理解1：多次分步来选择
- 理解2：先全排列，即$r！$然后每个类里面都是无关次序的，所以分别除以他们的阶乘
331物体个数不限的n类物体允许重复地选择r个的方案数——$\binom{n+r-1}{r}$
- 理解：
  - 首先可以理解为不定方程的解
  - 和高中的隔板法很像，但是高中的隔板法至少要有一个
  - 而这里可以一个都没有，所以要把隔板也考虑占一个位置
  - 理解1：二进制串，用0来分隔开
  - 理解2：不定方程，那就相当于用n - 1个加号隔开r个数
- trick
  - x的≥限定
    - 如：苹果至少要a个，香蕉至少b个
    - 令$x= x + a$，那么$x>0$，只需要转化为物体个数不限的n类物体允许重复地选择$r - a - b$个的方案数
  - r的 ≤ 限定
    - 例如：$x1+x2+x3+x4 ≤ 15$
    - 等价于$x1+x2+x3+x4+x5 = 15$
    - 添加一个未知数即可
  - x的≤限定
    - 例如：$x1+x2+x3+x4 ≤ 15 且 x1≤ 5, x2≤ 3$
    - 方法：容斥原理
    - 定义事件：
      - U为没有限制$\binom{4+15-1}{15}$
      - $P1为x1 ≥ 6\ r= r- 6\ N(P1) = \binom{4+9-1}{9}$
      - $P2为x2 ≥ 4\ r= r-4\ N(P2) = \binom{4+11-1}{11}$
      - $P1P2为x1≥6,x2 ≥ 4\ r= r-10\ N(P1P2) = \binom{4+5-1}{5}$
    - $由容斥原理\N(\overline{P1}\overline{P2}) = U - N(P1∪ P2) = U - N(P1) - N(P2) + N(P1P2)$
==338排列组合生成算法==
- 339在字典序下覆盖a的全排列
  - 例如63285741
  - 从右往左找到第一个不是递增的，即5
  - 与他右边的换 5 和 7 换
  - 剩下的升序排列（保证字典序）
  - 得到63287145
- 341给定集合S求S的r组合
  - 由于组合的无序性，所以要求生成的数组严格单调递增
  - 例如S={1,2,…,8} a = 13478
  - 从右往左找到第一个可以变大的数字（8、7不能了，但是4可以变大为5、6）
  - 将这个数字变为能变大的最小值，即5
  - 后面同理
  - 13567
  - 继续
  - 13568
  - 13578
==342递推关系式==
- 递推关系：必须由==前面==的项推出来
- 通项公式
- 封闭公式解
  - $a_n$能使用==不包含序列中任意项==的通项公式表示
  - 给出一个即可，不明确初始特解的情况下可能有很多封闭公式解
- 分类的递推，类似于动态规划，一定要相信它满足条件
- 注意最后写出递归式的时候说明n的范围，特殊情况，如n=0、1要单独说明
- 注意分情况讨论，要充分，然后再加起来的时候合并
==349线性递推关系式求解==
- 常系数线性齐次递推关系式
  
  $\sum {i = 1}^{t} (r_i^n.\sum{j = 0}^{mi - 1}\beta{ij}n^j)$
- 常系数线性非齐次递推关系式
  - 解的形式定理——这个定理给出了解是由齐次解+一个特解的结构组成的，所以关键是要找到一个特解
  - 特解构造定理
  - 总结：做题步骤
    1. 求解伴随齐次特征多项式得到特征根r
    2. 将F(n)写成上图标黄的形式
    3. 确定最高次数和s
    4. 根据s是否是特征根分情况讨论得到特解
    5. 将特解带入递推式
    6. 用特殊值带入求解方程
- ==分治算法及其效率分析==
  - 主定理

第九章：图与树

图

基本概念

362无向图的定义
363有向图的定义
- 有向图的==基图==是不考虑方向得到的无向图
364
- n阶图：顶点数为n
- 平凡图：顶点数为1
- 空图：顶点数为0
- 零图：边数为0
364环、简单图的定义
365度的定义
- 注意记号$d(G)$
- 出度是$d^+(G)$入度是$d^-(G)$
- ==图与简单图中对于顶点度的要求==

==365握手定理==

总度数为顶点数的两倍，入度等于出度等于顶点数

这在后面的证明中非常重要，常常矛盾的情况是用握手定理推出来的
推论：总度数为偶数
- 例题：
推论：任何图的奇度顶点个数是偶数
==推论：简单图的最大度====$\Delta(G)≤ n - 1$==
366正则图和完全图的定义
- k正则图：任意顶点的度数都是k
- n完全图：任意两个顶点之间都有边
  - 边数就是$\frac{n(n - 1)}{2}$
366二部图的定义
- 二部图
  
  其实很像一个神经网络的全连接层
367生成子图和导出子图的定义
- 生成子图：指从原始图中选取部分边，但保留所有顶点，形成的子图。
- 导出子图：从原始图中选取部分顶点，并保留这些顶点之间在原始图中存在的所有边，形成的子图。
367
- 删除顶点集：从图中移除指定的一组顶点及其相关联的边。
- 删除边集：从图中移除指定的一组边，同时==保留所有顶点==。
- 删除子图：顶点集不变，但是删除边

==368图的连通性==

通路、回路、简单（有向）通路、简单（有向）回路的定义
回路、初级回路（没有重点）、简单回路（没有重边）

长度为n的通路、回路条数计算

370
- 可达与连通分支
- 类似于握手定理，下面的引理也可以作为一个反证法的矛盾出发点
- 证明方法
- 以上面定理为例子
371点割集和边割集——用于描述破坏图连通性的方法
- 点割集：一组顶点的集合，若将这些顶点（少一个都不行）及其关联的边移除后，图会被分割成多个连通分量（或不再连通）。
- 割点：如果点割集只有一个顶点，这个点就叫做割点
- 边割集：一组边的集合，若将这些边（少一条都不行）移除后，图会被分割成多个连通分量（或不再连通）。
- 割边（桥）：如果边割集只包含一条边，这条边就叫做割边或桥
- 点连通度：最少需要删除多少个顶点才能使图不连通或者成为平凡图——顶点数最少的点割集的顶点数
- 边连通度：最少需要删除多少条边才能使图不连通——边数最少的边割集的边数
- 例子：
372强连通和单项连通
- 强连通：在有向图中，任意两个顶点之间都存在双向可达的路径
- 单向连通：在有向图中，从某个顶点出发可以到达其他所有顶点，但不一定存在返回路径
- 强连通分量：有向图中的最大强连通子图

欧拉图

一定要注意！！欧拉图是==对边做讨论==

补充：无向连通图G只有两个度数为奇数的顶点，则G存在欧拉通路，则G是半欧拉图
注意：==欧拉图没有强调是简单图！！==例如一个图如果是欧拉图，然后你添上一条重边，必然会使得他有两个顶点的度变成奇数，那就变成了欧拉通路，半欧拉图。

哈密顿图

一定要注意！！哈密顿图是==对顶点做讨论==

澄清哈密顿回路的定义
1. 哈密顿回路的定义是：
  - 路径必须经过图中的所有顶点一次且仅一次。
2. 由于回路的起点和终点是同一个顶点，因此==起点会在路径中出现====两次==，这是合法的。这并不违背哈密顿回路的定义。

树

无向树
- 无向树没有根这个说法，只包含内部节点和叶子：内部节点就是度为≥2；叶子就是度为1
- 无向树的每一条边都是桥（删掉就不连通了）
- 无向树是简单图
  - 对于3的证明，用反证法+握手定理注意啊手动阀
  - 对于3，如果是又向根树，是不成立的
- ==注意：数据结构中树是有向树，其节点的度的定义是孩子的数量，但是这的度的定义是无向图中的度的定义==
无向树的证明，遇到度数的，往握手定理靠