离散数学及其应用课程复习Kenneth H.Rosen

离散数学及其应用课程笔记

chap1 The Foundations: Logic and Proofs

英文 中文 英文 中文
proposition 命题 equivalence 等价式
predicate 谓词 quantifier 量词
inference 推理 negation 否定 NOT$\lnot$
conjunction 合取 AND$\land$ Disjunction 析取 OR$\lor$
Exclusive or 异或 XOR$\oplus$ Implication IF-THEN$\rightarrow$
Biconditional IF AND ONLY IF$\leftrightarrow$ hypothesis 假设
antecedent 前件 premise 前提
conclusion 结论 consequence 后件
converse 逆 contrapositive 逆否
inverse 反 bitwise 逐位
knight 骑士 knave 无赖
Tautologies 永真式 Contradictions 矛盾式
Contingencies 可能式 Normal Forms 范式
Dual 对偶式 Pierce arrow 或非$\downarrow$
Sheffer stroke 与非$ $ satisfiable
DNF 析取范式 CNF 合取范式
clause 子句 domain 论域
Universal Quantifier 全称量词$\forall$ Existential Quantifier 存在量词$\exists$
counterexample 反例 Uniqueness Quantifier 唯一性量词$\exists$!
scope （变量的）作用域 nested 嵌套的
argument 论证 proof 证明
theorem 定理 axioms 公理
lemma 引理 corollary 推论
猜想 trivial 平凡证明
vacuous proof 空证明 rational number 有理数
without loss of generality 不失一般性
  • 异或
$p$ $q$ $p\oplus q$
T T F
T F T
F T T
F F F

  • IF p THEN q

    p implies q

    p only if q=q if p

    q when p

    q whenever p

    q follows from p

    p is sufficient for q 充分

    q is necessary for p 必要

    q unless $\lnot$p

  • 逆、逆否、反

符号 含义 定义
$q\rightarrow p$ is the converse of $p\rightarrow q$ 逆(左右颠倒)
$\lnot q\rightarrow \lnot p$ is the contrapositive of $p\rightarrow q$ 逆否(与原命题等价)
$\lnot p\rightarrow \lnot q$ is the inverse of $p\rightarrow q$ 反
  • 优先级
operator precedence
$\lnot$ 1
$\land$ 2
$\lor$ 3
$\rightarrow$ 4
$\leftrightarrow$ 5

  • 对偶式

    $S=(p\lor \lnot q)\land r\land T$

    $S^*=(p\land \lnot q)\lor r\lor F$

    即所有 and 变成 or，所有 or 变成 and，所有 T 变成 F，所有 F 变成 T

    $s\Leftrightarrow t$ if and only if $s^\Leftrightarrow t^$

  • 功能完备符号：

    $\{\lnot, \lor\}$、$\{\lnot, \land\}$、$\{|\}$、$\{\downarrow\}$

  • 析取 DNF 范式：$(A_1\land A_2)\lor B_1\lor (C_1\land C_2)$

    合取 CNF 范式：$(A_1\lor A_2)\land B_1\land (C_1\lor C_2)$

  • 量词优先级比逻辑运算符更高

  • 命题中的变量必须是 Bound variable（被赋值的或被量词约束的）

在这里插入图片描述

corresponding tautology
Modus Ponens 假言推理 $(p\land(p\rightarrow q))\rightarrow q$
Modus Tollens 取拒式 $(\lnot q\land(p\rightarrow q))\rightarrow \lnot p$
Hypothetical Syllogism 假言三段论 $((p\rightarrow q)\land(q\rightarrow r))\rightarrow(p\rightarrow r)$
Disjunctive Syllogism 析取三段论 $(\lnot p\land(p\lor q))\rightarrow q$
Addition 附加律 $p\rightarrow (p\lor q)$
Simplification 简化律 $(p\land q)\rightarrow p$
Conjunction 合取律 $((p)\land(q))\rightarrow(p\land q)$
Resolution 消解律 $((\lnot p\lor r)\land(p\lor q))\rightarrow (r\lor q)$

  • 平凡证明：$p\rightarrow T$ is $T$

    空证明：$F\rightarrow q$ is $T$

chap2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

英文 中文 英文 中文
Sequences 序列 Summation 求和
Cardinality 基数 paradox 悖论
Power Set 幂集 tuple 有序元组
Cartesian Product 笛卡尔积 union 集合的并$\cup$
intersection 集合的交$\cap$ complement 集合的补$\bar A$
Inclusion-Exclusion 容斥原理 symmetric difference 对称差
Domain 定义域 Codomain 陪域、值域
Image 像 Preimage 原像
Injection 单射 Surjection 满射
Bijection 双射 Inverse Function 反函数
progression 级数 Recurrence Relations 递推关系
lexicographic 字典序 computable 可计算的
rectangular 矩形的 identity matrix 单位矩阵
transpose 转置 symmetric 对称的

  • 集合的基数记为$\vert A\vert$，即集合中元素的个数

  • 幂集$\mathcal{P}(A)$：集合中所有子集组成的集合，一个 n 个元素的集合的幂集有$2^n$个元素

  • 两个元素的元组被称为 ordered pairs 序偶

  • 笛卡尔积：$A\times B=\{(a,b)\vert a\in A \land b\in B\}$

  • 对称差：$A\oplus B=(A-B)\cup(B-A)$

  • 反函数的前提是原函数是双射的

  • $f\circ g(x)=f(g(x))$

  • $n!\sim \sqrt{2\pi n}(\frac n e)^n$

Sum Closed Form
$\sum_{k=0}^n ar^k$ $\frac{ar^{n+1}-a}{r-1}, r\neq 1$
$\sum_{k=1}^n k$ $\frac{n(n+1)}2$
$\sum_{k=1}^n k^2$ $\frac{n(n+1)(n+2)}6$
$\sum_{k=1}^n k^3$ $\frac{n^2(n+1)^2}4$
$\sum_{k=0}^\infty x^k, \vert x\vert <1$ $\frac 1{1-x}$
$\sum_{k=1}^\infty kx^{k-1}$ $\frac 1 {(1-x)^2}$

  • 可数集：基是有限的或跟正整数集相同，则是可数的

  • 一个无限且可数的集合的基被称为$\aleph_0$（可以跟正整数集建立一个一一对应的映射）

  • 实数集的基为$\aleph_1$

  • 一个集合的幂集的基，一定大于原集合的基

chap3 Algorithms

英文 中文 英文 中文
Brute-Force 暴力算法 Tractable 易解
Intractable 难解 polynomial 多项式
Notation Explaination
Big-O:$f(x)$ is $O(g(x))$ $\vert f(x)\vert\leq C\vert g(x)\vert$
Big-Omega:$f(x)$ is $\Omega(g(x))$ $\vert f(x)\vert\geq C\vert g(x)\vert$
Big-Theta:$f(x)$ is $\Theta(g(x))$ $O(g(x)) \& \Omega(g(x))$

  • NP 类：可以在多项式复杂度内被 check，但不能在多项式复杂度内解决

  • NP 完全类：if you find a polynomial time algorithm for one member of the class, it can be used to solve all the problems in the class

chap5 Induction and recursion

  • 数学归纳法:$P(1)\land \forall k(P(k)\to P(k+1))\to \forall nP(n)$
    • BASIC STEP:
    • INDUCTIVE STEP:
    • Hence,…
  • 每个简单多边形都会把一个区域变为内部区域和外部区域
  • 任何一个简单多边形都有其内部的对角线（lemma）
  • 良序性（正整数体系的公理）：A set is well ordered if every subset has a least element.
    • 数学归纳法和强归纳法与良序性的成立是等价的

chap6 Counting

英文 中文 英文 中文
Pigeonhole 鸽巢 Permutation 排列
Combination 组合 Binomial Coefficient 二项系数
distinguishable 可分辨的

  • 排列：$P(n,r)=\frac{n!}{(n-r)!}$

  • 组合：$C(n,r)=\frac{n!}{(n-r)! r!}$

  • 二项式定理：$(x+y)^n=\Sigma_{j=0}^n \begin{pmatrix} n\\j \end{pmatrix}x^{n-j}y^j$

  • $\Sigma_{k=1}^n(-1)^k \begin{pmatrix}n\\k\end{pmatrix}=0$

  • 帕斯卡定理：$\begin{pmatrix}n+1\\k\end{pmatrix}=\begin{pmatrix}n\\k-1\end{pmatrix}+\begin{pmatrix}n\\k\end{pmatrix}$

  • Vandermonde’s：$\begin{pmatrix}m+n\\r\end{pmatrix}=\Sigma_{k=0}^r\begin{pmatrix}m\\r-k\end{pmatrix}\begin{pmatrix}n\\k\end{pmatrix}$

    • 推论：$\begin{pmatrix}2n\\n\end{pmatrix}=\Sigma_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}^2$

  • 有 n 种饼干，取出共 r 个饼干的组合数量为：$C(n+r-1,r)$

  • n 个物体，k 个盒子：

n 个物体 r 个盒子 数量
不同 不同 $\frac{n!}{n_1!n_2!··n_k!}$
相同 不同 $C(n+r-1,n-1)$
不同 相同 —
相同 相同 —

chap8 Advanced Counting Techniques

英文 中文 英文 中文
Homogeneous 齐次的 Nonhomogeneous 非齐次的
generating function 生成函数 Inclusion-Exclusion 容斥原理
Derangement 错位排序

  • degree：$a_n=a_{n-1}+a_{n-8}$的 degree 为 8

    a recurrence relation of degree 8

  • Hanoi 汉诺塔（3 个柱子）：$H_n=2^n-1$

  • 齐次：每个 x 都是 1 次方的

  • 非齐次公式：

    如果递推关系是为：$a_n=c_1a_{n-1}+c_2a_{a-2}+···+c_ka_{n-k}+F(n)$

    非齐次项$F(n)$可以被记为$F(n)=(b_tn^t+b_{t-1}n^{t-1}+···+b_1n+b_0)s^n$

    如果 s 是$a_n=c_1a_{n-1}+c_2a_{a-2}+···+c_ka_{n-k}$的一个根，m 为次数，最后的特解可以被记为：$f(n)=n^m(p_tn^t+p_{t-1}n^{t-1}+···+p_1n+p_0)s^n$

    如果 s 不是是$a_n=c_1a_{n-1}+c_2a_{a-2}+···+c_ka_{n-k}$的一个根，最后的特解可以被记为：$f(n)=(p_tn^t+p_{t-1}n^{t-1}+···+p_1n+p_0)s^n$

    例如

    $a_n=6a_{n-1}-9a_{n-2}+F(n)$

    $F(n)=(n^2+1)3^n$

    则$m=2, s=3, f(n)=n^2(p_2n^2+p_1n+p_0)3^n $（s=3 为一个根）

    $a_n=6a_{n-1}-9a_{n-2}+F(n)$

    $F(n)=n^22^n$

    则$s=2, f(n)=(p_2n^2+p_1n+p_0)2^n $（s=2 不是一个根）

  • 分治算法复杂度：

    $f(n)=af(n/b)+cn^d$

  • 生成函数：

    1. $f(x)+g(x)=\Sigma_{k=0}^\infty(a_k+b_k)x^k$
    2. $\alpha\cdot f(x)=\Sigma_{k=0}^\infty\alpha \cdot a_kx^k$
    3. $x\cdot f’(x)=\Sigma_{k=0}^\infty k \cdot a_kx^k$
    4. $f(\alpha x)=\Sigma_{k=0}^\infty \alpha^k\cdot a_k x^k$
    5. $f(x)g(x)=\Sigma_{k=0}^\infty(\Sigma_{j=0}^k a_j b_{k-j}x^k)$

  • 广义二项式定理：

    例如

    请找到$(1+x)^{-n}$的生成函数

在这里插入图片描述

  • n 元素集合的错位排序个数：$D_n=n![1-\frac{1}{1!}+\frac 1{2!}-\frac 1{3!}+···+(-1)^n\frac 1 {n!}]$

chap9 Relations

英文 中文 英文 中文
properties 性质 closure 闭包
reflexive 自反的 symmetric 对称的
antisymmetic 反对称的 transitive 可传递的
Composition 组合 diagonal 对角线上
Equivalence 等价 Congruence 同余
representive 代表元 partition 划分
partial ordering 偏序 hasse diagram 哈塞图
lattices 格 total order/linear order 全序/线序$\preccurlyeq$
chain 链 maximal 极大元
minimal 极小元 greatest element 最大元
least element 最小元 compatible 兼容的

  • 集合的性质

    • 自反性 Reflexive

      $(a,a)\in R$，$\forall x[x\in U\to(x,x)\in R]$

      空集上的空关系是自反的

    • 对称性 Symmetric

      $\forall x \forall y[(x,y)\in R \to (y,x)\in R]$

    • 反对称性 Antisymmetric

      $\forall x \forall y[(x,y)\in R\land(y,x)\in R \to x=y]$

      不存在除了自反之外的对称关系

    • 传递性 Transitive

      $\forall x \forall y\forall z [(x,y)\in R \land (y,z)\in R\to (x,z)\in R]$

  • $R^n\subset R\leftrightarrow \text{R is transitive}$

  • 逆关系：$R^{-1}=\{(a,b)|(b,a)\in R\}$

  • 关系操作：

    • $(R\cup S)^{-1}=R^{-1}\cup S^{-1}$
    • $(R\cap S)^{-1}=R^{-1}\cap S^{-1}$
    • $(\overline R)^{-1}=\overline{(R^{-1})}$
    • $(A\times B)^{-1}=B\times A$

  • transitive closure：

    连通关系 connectivity relation：$R^*=\cup _1 ^\infty R^n$

    关系的传递闭包就是关系的连通关系$R^*=t(R)$

  • 等价关系：自反、对称且传递

    $a\text{~}b$

  • R 为集合 A 上的一个等价关系，则在集合 A 中与元素 a 相关的所有元素可以被表示为$[a]_R$（等价类）

  • 代表元：等价类中的任何一个元素都可以被成为代表元

  • 集合的划分：$pr(A)=\{A_i|i\in I\}$

  • $R_1$、$R_2$为 A 上的两个等价关系，则$R_1\cup R_2$是 A 上的自反、对称关系，$(R_1\cup R_2)^*$是自反、对称、传递关系即等价关系

  • 偏序关系：自反、传递、==反对称==（分大小的不平等关系）

    • $poset(S,\preccurlyeq)$：定义在集合 S 上的一个偏序关系
    • 如果集合中任意两个元素都是可比的，则成为全序、线序，整个集合被称为一个链
    • 良序：拥有最小元素
    • 极小（大）元：没有一个小于它
    • 最小（大）元：所有元素都大于等于它
    • 格：任意一对元素都拥有最大上界和最小下界的偏序集，被称为一个格

chap10 Graphs

英文 中文 英文 中文
vertice 顶点 edge 边
endpoint 端点 multigraph 多重图
pseudograph 伪图 adjacent 相邻顶点
incident 关联 pendant 悬挂
in degree 入度 out degree 出度
Bipartite 二分图 regular graph 正规图
proper subgraph 真子图 Isomorphism 同构
path 通路 connected component 连通部分
articulation point 割点 Approximation algorithm 近似算法
planer 平面图 region 区域
Elementary subdivision 初等细分 Homeomorphic 同胚
dual graph 对偶图 chromatic number 着色数
  • $G=(V,E)$

  • 无向图分类：

    • 简单图：没有环，没有多重边
    • 多重图：没有环，可以有多重边
    • 伪图：可以有环和多重边

  • 有关图的术语：

    • adjacent：两个顶点之间有边相连，则称这两个顶点相关联
    • incident with vertices u and v：这条边连接了顶点 u 和 v
    • loop：环
    • degree of a vertex 顶点的度：在无向图中即为有多少条边与这个点关联（==环算两个度==）
      • $deg(v)=0$，v is isolated
      • $deg(v)=1$，v is pendant
    • 无向图中，$\Sigma_{v\in V}deg(v)=2e$
      • 无向图中，偶数个顶点是奇数个度
    • 有向图中，一条边的起点 initial vertex，终点 terminal vertex
      • $\Sigma_{v\in V}deg^+(v)=\Sigma_{v\in V}deg^-(v)=E$
  • 一些特殊的图：
    • 完全图$K_n$：每对顶点之间有且只有一条边相连
    • 圈图$C_n$：n 个顶点围成一个圈首尾相连
    • 轮图$W_n$：在圈图中间加个点
    • 立方图$Q_n$
  • 完全二分图$K_{mn}$:两组集合中每个点都与对面任意一个点相连
  • 正规图：每个顶点的度都相同

  • induced subgraph 诱导子图：当且仅当子图中的边都在原图里，仅删除与子图中不存在的顶点相连的边

  • Incidence matrices 关联矩阵：纵坐标为顶点，横坐标为边，针对无向图

  • path is simple：没有一条边被重复的通路
    • 单个顶点的通路长度为 0
  • 图的连通：任意一对顶点间都有 path
  • 割点：关节点，删去后会增加 connected components 的个数
  • 割边/桥：关节边，删去后会增加 connected components 的个数

  • 任何一个强连通的有向图都是弱连通的，可以把弱连通看作无向图，而强连通指有向图每对顶点间都双向连通

    • strongly connected components/strong components：有向图中的最大强连接子图

  • 欧拉回路：遍历所有的边，每条边只访问一遍

    • 区别欧拉通路和欧拉回路：是否要求回到原点
    • 欧拉图：包含欧拉回路的图
    • 对于无向图：
      • ==欧拉回路充要条件==：当且仅当每个顶点都是偶数个度
      • ==欧拉通路充要条件==：当且仅当只有 2 个顶点是奇数个度
    • 对于有向图
      • ==欧拉回路==：弱连接+出度与入度相同
      • ==欧拉通路==：弱连接+起点的出度多一个，终点的入度多一个

  • 哈密尔顿问题：遍历所有点，每个点只访问一遍

    • 还有没充要条件
    • 充分条件（满足条件则一定有，不满足也可能有）：
      • 狄拉克定理：$\forall v\in V, deg(v)\geq \frac n 2$则有哈密尔顿通路
      • 欧尔定理：$\forall 不相邻顶点v,u\in V, deg(v)+deg(u)\geq n$
    • 必要条件（用于判断不是哈密尔顿）：
      • 连通图，每个顶点的度都必须大于等于 1
      • 最多只有两个顶点的度是 1
      • 如果一个顶点的度为 2，则两条边都为哈密尔顿回路的一部分
      • 从顶点集合 V 中去掉一组顶点 S，则新图的连接部分数量<=S 的个数

  • weighted graph 加权图：$G=(V,E,W)$

  • Dijkstra:寻找最短路径，要求所有路径都是正权重的

    • iterative
    • $L_k(v)=\min\{L_{k-1}(v),L_{k-1}(u)+w(u,v)\}$
    • $O(n^2)$

  • 旅行商问题

    • 最短的哈密尔顿回路
    • 近似算法

  • 平面图：可以画在平面上且边与边不交叉

  • 区域 Region：包括有界区域和无界区域

  • ==欧拉公式==：对于连通的平面简单图

    对于非平面图也可能成立

  • 区域的度：区域边的总数（绕一圈的边的总数）

    • 推论 1：

      对于不连通的平面简单图也成立

    • 推论 2：对于一个平面简单图，G 一定有一个顶点的度不超过 5

    • 推论 3：对于一个平面简单图，如果任何一个回路的长度都大于 3，则$e\leq 2v-4$

  • Kuratowski 定理

    • 初等细分：增加原有道路上的细分点
    • 同胚：可以通过一系列的初等细分所获得的图
    • 一个图是非平面的$\Leftrightarrow$包含一个与$K_{3,3}$或$K_5$同胚的子图

  • 着色问题

    • 地图的对偶图，相邻的区域间连线
    • 等价于对偶图的顶点着色，使每条边上的两个顶点不同颜色
    • 最少着色数记为$\chi(G)$
    • ==四色定理==：一个平面图的着色数不超过 4

chap11 Trees

英文 中文 英文 中文
root 根 internal vertice 有孩子的节点
subtrees 子树 isomorphic 同构的
preorder 前序 inorder 中序
postorder 后序 spanning tree 生成树
backtracking 回溯
  • 树：没有简单回路的连通无向图

  • 无向图是一棵树$\Leftrightarrow$每两个顶点之间都有唯一的简单通路

  • 满 m 叉树：每个中间节点都有 m 个孩子

  • 树的同构：

    • 根树的同构（有向图的同构）
    • 无根树的同构（无向图的同构）

  • 树的性质：

    • n 个顶点的树就有 n-1 条边
    • 一个有 i 个内节点的满 m 叉树有$mi+1$和顶点
    • 树一定是个二分图

  • 二叉搜索树

    • 插入一个新节点，最多发生$\lceil \log(n+1)\rceil$次比较

  • 决策树

    • 由一系列节点生成一个解

  • prefix code

    • huffman code

  • 生成树

    • 一个简单图是连通的$\Leftrightarrow$包含一个生成树
    • DFS 深度优先搜索（回溯）会形成一个根树
    • BFS 广度优先搜索

  • 最小生成树

    • Prim 算法：找与已经连接的生成树距离最短的点，直到完全连通，$O(E\log(V))$
    • Kruskal 算法：找现存的最短边（不会产生回路），直到完全联通，$O(V\log(E))$

  • 树：没有简单回路的连通无向图

  • 无向图是一棵树$\Leftrightarrow$每两个顶点之间都有唯一的简单通路

  • 满 m 叉树：每个中间节点都有 m 个孩子

  • 树的同构：

    • 根树的同构（有向图的同构）
    • 无根树的同构（无向图的同构）

  • 树的性质：

    • n 个顶点的树就有 n-1 条边
    • 一个有 i 个内节点的满 m 叉树有$mi+1$和顶点
    • 树一定是个二分图

  • 二叉搜索树

    • 插入一个新节点，最多发生$\lceil \log(n+1)\rceil$次比较

  • 决策树

    • 由一系列节点生成一个解

  • prefix code

    • huffman code

  • 生成树

    • 一个简单图是连通的$\Leftrightarrow$包含一个生成树
    • DFS 深度优先搜索（回溯）会形成一个根树
    • BFS 广度优先搜索

  • 最小生成树

    • Prim 算法：找与已经连接的生成树距离最短的点，直到完全连通，$O(E\log(V))$
    • Kruskal 算法：找现存的最短边（不会产生回路），直到完全联通，$O(V\log(E))$