离散数学 复习笔记
1 命题逻辑
命题符号化
相关概念
- 命题：可以判断真假的陈述句
- 简单命题/复合命题
- 命题常项/命题变项
联结词
优先级顺序：否定 $\neg p$ > 合取 $p\land q$ > 析取 $p\lor q$ > 蕴含 $p\rightarrow q$ > 等价 $p\leftrightarrow q$
命题公式
相关概念
- 赋值、成真赋值/成假赋值
- 重言式/矛盾式/可满足式
- 真值表/真值函数：$n$ 个命题变项有 $2^n$ 种赋值，每种赋值可能对应两种函数值，因此共有 $2^{2^n}$ 种赋值集合到函数值集合的映射，即可以形成 $2^{2^n}$ 种不同的真值函数
命题公式的层数
- $d(\neg p)=d(p)+1$
- $d(p\land q)=\max(d(p),d(q))+1$
- 其余二元联结词同上
等值演算
等值 $A\Leftrightarrow B$：$A\leftrightarrow B$ 是重言式
演算公式
- 德·摩根律
- $\neg (A\lor B)\Leftrightarrow \neg A\land \neg B$
- $\neg (A\land B)\Leftrightarrow \neg A\lor \neg B$
- 蕴含等值式：$A\rightarrow B\Leftrightarrow \neg A\lor B$
- 等价等值式：$A\leftrightarrow B\Leftrightarrow (A\rightarrow B)\land (B\rightarrow A)$
范式
相关概念
- 析/合取范式：有限个简单合/析取式构成的析/合取式
- 极小项 $m_i$/极大项 $M_i$：每个命题变项出现一次的简单合/析取式
- 主析/合取范式：极小/大项构成的析/合取式
存在性与唯一性
- 析/合取范式一定存在，但不唯一
- 主析/合取范式一定存在且唯一
极大项与极小项的关系：$m_i=\neg M_i$
联结词全功能集
与非联结词和或非联结词
- 与非 $p\uparrow q\Leftrightarrow\neg (p\land q)$
- 或非 $p\downarrow q\Leftrightarrow\neg (p\lor q)$
$\lbrace\neg,\land\rbrace,\lbrace \neg,\lor\rbrace ,\lbrace \neg,\rightarrow\rbrace ,\lbrace \uparrow\rbrace ,\lbrace \downarrow\rbrace$ 都是联结词全功能集
2 一阶逻辑
谓词公式
相关概念
- 个体常项/个体变项/个体域/全总个体域
- 谓词常项/谓词变项/0元谓词/特性谓词
- 全称量词/存在量词
- 原子公式/谓词公式
- 指导变项/辖域/约束出现/自由出现/闭式
- 逻辑有效式/矛盾式/可满足式
- 解释/赋值
- 代换实例（命题公式和谓词公式间的关系）
对个体域的限制可以用特性谓词替代
闭式在解释后一定是命题，非闭式在解释和赋值后一定是命题
换名规则：为了避免同一变项既有自由出现又有约束出现，将一个指导变项及其在辖域中所有约束出现替换成新的符号
一阶逻辑等值
等值式
- 量词否定等值式
- $\neg \forall xA(x)\Leftrightarrow \exists x\neg A(x)$
- $\neg\exists xA(x)\Leftrightarrow \forall x\neg A(x)$
- 量词辖域收缩与扩张等值式：
- $\forall x(A(x)\rightarrow B)\Leftrightarrow \exists xA(x)\rightarrow B$
- $\exists x(A(x)\rightarrow B)\Leftrightarrow \forall xA(x)\rightarrow B$
- $\forall x(B\rightarrow A(x))\Leftrightarrow B\rightarrow \forall x A(x)$
- $\exists x(B\rightarrow A(x))\Leftrightarrow B\rightarrow \exists xA(x)$
- 量词分配等值式
- $\forall x(A(x)\land B(x))\Leftrightarrow\forall xA(x)\land \forall xB(x)$
- $\exists x(A(x)\lor B(x))\Leftrightarrow \exists xA(x)\lor \exists B(x)$
前束范式
- 一系列约束+辖域，其中辖域中不含量词
- 任何公式都存在前束范式，但不唯一
3 集合
集合的概念和运算
相关概念
- 补集 $A-B=A\cap \sim B$
- 幂集 $P(A)=\lbrace x|x\subseteq A\rbrace$
- 对称差 $A\oplus B=(A\cup B)-(A\cap B)$
运算律
- $A-(B\cup C)=(A-B)\cap (A-C)$（德·摩根律）
- $A-(B\cap C)=(A-B)\cup (A-C)$（德·摩根律）
- $A\oplus B=(A-B)\cup(B-A)$
4 二元关系与函数
笛卡尔积与二元关系
笛卡尔积
- 两个集合元素构成的有序对集合
- 不符合交换律
- $<<x,y>,z>\neq <x,<y,z>>$，不符合结合律
相关概念
- 定义域 $\text{dom}R$、值域 $\text{ran}R$、域 $\text{fld}R$
- 关系的三种表示方法：关系集合、关系矩阵、关系图
- （$A$ 上的）空关系、全域关系 $E_A$、恒等关系 $I_A$
二元关系的性质
二元关系的运算
- 逆 $F^{-1}=\lbrace <x,y>|yFx\rbrace$
- 合成 $F\circ G=\lbrace <x,y>|xFz\land zGy\rbrace$
- 合成对集合并满足分配律，但对集合交分配得到包含关系 $F\circ(G\cap H)\subseteq F\circ G\cap F\circ H$
- $R^0=I_A, R^n=R^{n-1}\circ R$
二元关系的性质
- 自反性 $I_A\subseteq R$
- 反自反性 $I_A\cap R=\emptyset$
- 对称性 $R^{-1}=R$
- 反对称性 $R\cap R^{-1}=\emptyset$
- 传递性 $R\circ R\subseteq R$
二元关系的闭包：满足条件的最小超集
闭包的构造
- $r(R)=R\cup R^0$
- $s(R)=R\cup R^{-1}$
- $t(R)=R\cup R^2\cup R^3\cup\cdots$
等价关系和偏序关系
相关概念
- 等价类/商集
- 可比/盖住
- 偏序集/全序集
- 哈斯图
等价关系：集合上的自反、对称、传递的关系，记作 $x\sim y$
偏序关系：集合上的自反、反对称、传递的关系，记作 $x\preccurlyeq y$
最大元/极大元/上界/上确界对比
- 最大元：在集合中且比所有都大
- 极大元：在集合中且不存在更小
- 上界：比所有都大
- 上确界：上界集合的最小元
函数
相关概念
- $B^A$（B上A）：所有 $A$ 到 $B$ 的函数构成的集合
- 满射/单射/双射
- 特征函数、自然映射
函数的复合能够保持满射、单射、双射性质
只有双射函数才有反函数
5 图
图的性质
相关概念
- 空图/零图/平凡图
- 环（自环）/平行边（重边）/简单图
- 生成子图/导出子图/补图 $\overline G$
- $K_n$：$n$ 阶无向完全图
握手定理：$\sum_{i=1}^n d(v_i)=2m$，推论：度数为奇数的顶点个数为偶数
图的矩阵表示：关联矩阵/邻接矩阵/可达矩阵
6 特殊的图
二部图
相关概念
- 极大匹配/最大匹配/完美匹配/完备匹配
- $K_{n,m}$：完全二部图
二部图的判定：没有奇环
完备匹配的充要条件（Hall 定理）：$V_1$ 中任意 $k$ 个顶点都至少邻接 $V_2$ 中 $k$ 个顶点
欧拉图&哈密顿图
欧拉通路、欧拉回路的充要条件
哈密顿通路、哈密顿回路的判定
- $n(n\ge 3)$ 阶简单无向图
- 任何一对不相邻顶点的度数之和都大于等于 $n-1$ 则存在哈密顿通路
- 任何一对不相邻顶点的度数之和都大于等于 $n$ 则存在哈密顿回路
平面图
相关概念
- 面/边界/次数
- 极大平面图/极小非平面图
- 对偶图：以面为点，以边为边
极大平面图的性质：$n(n\ge 3)$ 阶简单平面图是极大平面图 $\Leftrightarrow$ 连通且每个面的次数都为 $3$
欧拉公式
- $n-m+r=2$，其中 $r$ 为面数
- 证明：数学归纳法，有叶删叶，没叶删边
- 推广：$n-m+r=p+1$，其中 $p$ 为连通分量个数
库拉图斯基定理
- 基础：$K_5$ 和 $K_{3,3}$ 都不是平面图
- 定理：平面图 $\Leftrightarrow$ 不含与 $K_5$/$K_{3,3}$ 同胚的子图 $\Leftrightarrow$ 不含能收缩到 $K_5$/$K_{3,3}$ 的子图
四色定理：任何平面图都可以用 $4$ 种颜色填充面使得没有相邻的面同色
7 代数
二元运算的性质
二元运算律
- 交换律
- 结合律
- 幂等律 $x\circ x=x$
- 分配律
- 吸收律 $x*(x\circ y)=x,x\circ(x*y)=x$
特异元素
- 左/右单位元
- 左/右零元
- 左/右逆元
代数系统
相关概念
- 子代数/积代数
- 单同态/满同态/同构
同态代数和积代数都保持交换律、结合律、幂等律
代数系统 $\overset{可结合}\longrightarrow$ 半群 $\overset{含单位元}\longrightarrow$ 含幺半群（独异点） $\overset{所有数可逆}\longrightarrow$ 群 $\overset{可交换}\longrightarrow$ 交换群
群的性质
- 幂运算
- 消去律
群的中心：可交换子群
环 $<R,+,\cdot>$
- $<R,+>$ 为阿贝尔群
- $<R,\cdot>$ 为半群
- $\cdot$ 对 $+$ 满足分配律
域 $<R,+,\cdot>$
- 可交换、含单位元、无零因子
- 至少有两个元素、非零可逆
格 $<S,\preccurlyeq>$：任意一对 $\lbrace x,y\rbrace$ 都有上确界和下确界
典型代数系统
Klein 四元群
| $\circ$ | e | a | b | c |
|---|---|---|---|---|
| e | e | a | b | c |
| a | a | e | c | b |
| b | b | c | e | a |
| c | c | b | a | e |
循环群：$G=\lbrace a^k|k\in\mathbf{Z}\rbrace$
置换群：由 $n$ 元置换构成
模 $n$ 整数环：$<\mathbf{Z}_n,\oplus,\odot>$
有理数域/实数域/复数域
离散数学 复习笔记