离散数学(1)

大一上学期离散数学(1)的复习笔记，目前已完结。

一、命题逻辑

基本定义
1. 命题：真值非真即假或待定的陈述句
2. 合式公式：有限次联结，不包含空公式
命题形式化：注意异或和充要条件的判断
波兰表达式
1. 中缀表示的扫描：发现第一个右括号 $\to$ 返回最近的左括号 $\to$ 向右继续扫描
2. 中缀式 $\Rightarrow$ 波兰式：根据优先级加括号 $\to$ 从内层括号逐步向外层脱开
3. 波兰式 $\Rightarrow$ 中缀式：压栈
4. $\neg A$ 的前缀为 $\neg A$，后缀为 $A\neg$
等值公式
1. 蕴含没有结合律、交换律
2. 双蕴含没有分配律
3. 前提合取合并：$P\to (Q\to R)=(P\wedge Q)\to R$
4. 前提析取合并：$(P\to R)\wedge (Q\to R)=(P\vee Q)\to R$
5. 前提交换：$P\to (Q\to R)=Q\to (P\to R)$
6. 从 $T$ 行写双蕴含：$P\leftrightarrow Q=(P\wedge Q)\vee (\neg P\wedge \neg Q)$
7. 从 $F$ 行写双蕴含：$P\leftrightarrow Q=(P\vee \neg Q)\wedge (\neg P\vee Q)$
8. 归谬论：$(P\to Q)\wedge (P\to \neg Q)=\neg P$
9. 代入规则：只能对重言式中的原子命题使用，且必须全部代换
10. 置换规则：只需等值
真值表
1. 从 $T$ 行写：一个个情况累加，$1=T, 0=F$，用极小项构成主析取范式
2. 从 $F$ 行写：一个个情况排除，$1=F, 0=T$，用极大项构成主合取范式
真值函项：对 $n$ 个命题变元，每个变元有 $m$ 种取值：可定义 $m^{m^n}$ 个 $n$ 元联结词
完备集：$\{\neg ,\wedge ,\vee\},\{\neg,\wedge \},\{\neg,\vee\},\{\neg,\to\},\{\uparrow\},\{\downarrow\}$
对偶式
1. $A^*$：将 $A$ 中出现的 $\wedge ,\vee ,T, F$ 分别用 $\vee, \wedge ,F, T$ 代换
2. $A^-$：将 $A$ 中的命题变项分别用各自的互补对代换
3. $\neg A=A^{*-}$
范式
1. 步骤：消去蕴含 $\to$ 将否定内移到命题变项上 $\to$ 利用分配律或利用真值表
  1. $A\wedge (B\vee C)=(A\wedge B)\vee (A\wedge C)$ 多用于求析取范式
  2. $A\vee (B\wedge C)=(A\vee B)\wedge (A\vee C)$ 多用于求合取范式
2. 快速填满变项：$\neg P\vee Q=m^{0 x}\vee m^{x 1}=\bigvee_{0,1,3}$
3. 极大项与极小项的关系：$\neg m_2=M_5,\neg M_2=m_5$
4. 否定：$A=\bigvee_{0,1,3}\Leftrightarrow \neg A=\bigvee_{2,4,5,6,7}, B=\bigwedge_{0,1,3}\Leftrightarrow \neg B=\bigwedge_{2,4,5,6,7}$
5. 主合取范式与主析取范式的转换：$\bigvee_{0,1,3}=\neg \neg \bigvee_{0,1,3}=\neg \bigwedge_{4,6,7}=\bigwedge_{0,1,2,3,5}$
6. 永真式的主合取范式、矛盾式的主析取范式为空公式
推理公式
1. $P\wedge Q\Rightarrow P\Rightarrow P\vee Q$
2. 假言推理： $P\wedge (P\to Q)\Rightarrow Q$
3. 三段论：$(P\to Q)\wedge (Q\to R)\Rightarrow P\to R$
推理演算：注意附加前提引入
归结推理
1. 证明 $A\Rightarrow B$ 步骤：将 $A,\neg B$ 分别化为合取范式，建立子句集，归结出矛盾
2. 半完备性：对真命题能够归结出空子句，对假命题得不到任何结论
公理系统
1. 公理
  1. $(P\vee P)\to P$
  2. $P\to (P\vee Q)$
  3. $(P\vee Q)\to (Q\vee P)$
  4. $(Q\to R)\to ((P\vee Q)\to (P\vee R))$
  5. $\to,\wedge,\leftrightarrow$ 的定义
  6. 代入、置换、分离规则
  7. 演绎定理：若 $A$ 推出 $B$ 过程中不使用代入规则，则 $A\to B$ 成立
2. 定理
  1. $(Q\to R)\to ((P\to Q)\to (P\to R))$
  2. $P\to P$
  3. $\neg P\vee P$
  4. $P\vee \neg P$
  5. $P\to \neg \neg P$
  6. $\neg \neg P\to P$
  7. $(P\to Q)\to (\neg Q\to \neg P)$
3. 例题
  1. $(P\vee Q)\to (Q\to (P\vee Q))$
  2. $(2022) (\neg Q\to P)\to (\neg P\to Q)$
性质
1. 满足完备性：是否所有的定理都可由公理系统推导出来
2. 满足可靠性：非重言式或不成立的公式是否也可推导出来
3. 满足可判定性：存在一种机械的方法在有穷步内判定任意公式是否为定理

二、谓词逻辑

基本定义
1. 与命题逻辑的关系
  1. 谓词逻辑 $=$ 命题逻辑 $+$ 个体词 $+$ 谓词 $+$ 量词 $+$ 函数
  2. $P (x), Q (f(x), y)$ 是命题形式，取定谓词、函数，并量化个体词后化为命题
  3. 一个命题是没有自由变元的谓词常项
2. 合式公式
  1. 两个合式公式的连接：无变元 $x$ 在 $A, B$ 中的一个是约束的而在另一个中是自由的
  2. $A$ 是合式公式，且 $x$ 在 $A$ 中是自由变元，则 $(\forall x) A, (\exists x) A$ 是合式公式
  3. 反例：$(\forall x) F (x)\wedge G (x), (\exists x)(\forall x) F (x), (\forall x) P (y)$
自然语句的形式化：注意唯一性的表示
有限域下公式的表示法
1. 解释：须取定谓词、函数
2. 有限域下公式的可满足性和普遍有效性依赖且仅依赖于个体域个体的数目
3. 在 $k$ 个体域上普遍有效 $\Rightarrow$ 在 $k-1$ 个体域上普遍有效
4. 在 $k$ 个体域上可满足 $\Rightarrow$ 在 $k+1$ 个体域上可满足
等值公式
1. 由命题逻辑移植来的等值式
2. 量词的否定
3. 量词对无关命题变项的分配律（$\to$ 前件不变后件变）
4. 量词 $\forall$ 对 $\wedge$、量词 $\exists$ 对 $\vee$ 的分配律
5. 变元易名
范式
1. 前束范式：消去蕴含 $\to$ 否定符内移 $\to$ 量词左移 $\to$ 变元易名
2. $\mathrm{Skolem}$ 标准形：$(\exists x)(\forall y)(\exists z) P (x, y, z)=P (a, y, f (y))$
3. 前束范式与 $\mathrm{Skolem}$ 标准形在不可满足的意义下一致
推理公式
1. $(\forall x) P (x)\vee (\forall x) Q (x)\Rightarrow (\forall x)(P (x)\vee Q (x))$
2. $(\exists x)(P (x)\wedge Q (x))\Rightarrow (\exists x) P (x)\wedge (\exists x) Q (x)$
3. $(\forall x)(P (x)\to Q (x))\Rightarrow (\forall x)P(x)\to (\forall x)Q(x)$
4. $(\forall x)(P (x)\to Q (x))\Rightarrow (\exists x)P(x)\to (\exists x)Q(x)$
5. $(\forall x)(P (x)\leftrightarrow Q (x))\Rightarrow (\forall x) P (x)\leftrightarrow (\forall x) Q (x)$
6. $(\forall x)(P (x)\leftrightarrow Q (x))\Rightarrow (\exists x) P (x)\leftrightarrow (\exists x) Q (x)$
7. $(\forall x)(P (x)\to Q (x))\wedge (\forall x)(Q (x)\to R (x))\Rightarrow (\forall x)(P (x)\to R (x))$
8. $(\forall x)(P (x)\to Q (x))\wedge P (a)\Rightarrow Q (a)$
9. $(\forall x)(\forall y) P (x, y)\Rightarrow (\exists x)(\forall y) P (x, y)\Rightarrow (\forall y)(\exists x) P (x, y)$
推理演算
1. $UI$：$(\forall x) P (x)\Rightarrow P (y)$，其中 $y$ 不在 $P (x)$ 中约束出现
2. $UG$：$P (y)\Rightarrow (\forall x) P (x)$，其中 $x$ 不在 $P (y)$ 中约束出现
3. $EI$：$(\exists x) P (x)\Rightarrow P (c)$，其中 $c$ 不在 $P (x)$ 中出现，且 $P (x)$ 中无自由变元
  1. 反例：$(\exists x)(x>y)$ 成立，但 $c>y$ 不成立
4. $EG$：$P (c)\Rightarrow (\exists x) P (x)$，其中 $x$ 不在 $P (c)$ 中出现
归结推理
1. 步骤：将 $A,\neg B$ 分别化为前束范式，再化为 $\mathrm{Skolem}$ 标准形，建立子句集
2. 归结方法：$P (x)\vee Q (x)$ 与 $\neg P (a)\vee R (y)$ 归结出 $Q (a)\vee R (y)$
一阶逻辑公理系统
1. 由命题逻辑移植来的公理（演绎定理除外）
2. $(\forall x) P (x)\to P (y)$
3. $P (y)\to (\exists x) P (x)$
4. 约束变元易名规则
5. 后件概括规则：若 $A\to B (x)$ 且 $x$ 在 $A$ 中不出现，则 $A\to (\forall x) B (x)$
6. 前件存在规则：若 $A (x)\to B$ 且 $x$ 在 $B$ 中不出现，则 $(\exists x) A (x)\to B$
7. 演绎定理：不使用代入规则、前件存在和后件概括规则
性质
1. 满足完备性
2. 满足可靠性
3. 不满足可判定性，但有子类是可判定的
  1. 只含有一元谓词变项的公式是可判定的
  2. 个体域有穷时的谓词公式是可判定的
  3. $\exists,\forall$ 前束范式的母式中无量词和其他自由变项时是可判定的

三、集合

集合的运算
1. $A\subseteq B\Leftrightarrow P (A)\subseteq P (B)$
2. $A=B\Leftrightarrow P (A)=P (B)$
3. $P (A)\in P (B)\Rightarrow A\in B$
4. $P (A)\cap P (B)=P (A\cap B)$
5. $P (A)\cup P (B)\subseteq P (A\cup B)$
6. $P (A-B)\subseteq (P (A)-P (B))\cup \{\emptyset\}$
7. 传递集合：$(\forall x)(\forall y)((x\in y\wedge y\in A)\to x\in A)$
  1. 等价描述 $1$：传递集合元素的元素都是它的元素
  2. 等价描述 $2$：传递集合的元素都是它的子集
8. $A$ 是传递集合 $\Leftrightarrow$ $A\subseteq P (A)\Leftrightarrow P(A)$ 是传递集合
9. $A\subseteq B\Rightarrow \bigcup A\subseteq \bigcup B$
10. $A\subseteq B\Rightarrow \bigcap B\subseteq \bigcap A$，其中 $A, B$ 非空
11. $\bigcup (A\cup B)=(\bigcup A)\cup (\bigcup B)$
12. $\bigcap (A\cup B)=(\bigcap A)\cap (\bigcap B)$，其中 $A, B$ 非空
13. $\bigcup (P (A))=A$
14. $A$ 是传递集合 $\Rightarrow$ $\bigcup A$ 是传递集合
15. $A$ 的元素都是传递集合 $\Rightarrow$ $\bigcup A$ 是传递集合
16. 非空集合 $A$ 是传递集合 $\Rightarrow$ $\bigcap A$ 是传递集合，且 $\bigcap A=\emptyset$
17. 非空集合 $A$ 的元素都是传递集合 $\Rightarrow$ $\bigcap A$ 是传递集合
集合论公理系统
1. 外延公理
2. 空集合存在定理
3. 无序对集合存在定理
4. 广义并集合存在定理
5. 子集公理模式
6. 幂集合公理
7. 无穷公理
8. 替换公理模式
9. 正则公理：任意非空集合 $S$ 存在元素 $x$ 使得 $S$ 和 $x$ 不相交
10. 选择公理：对任意关系 $R$ 存在函数 $f$ 使得 $f\subseteq R, dom (f)=dom (R)$
  1. 等价形式：良序定理、$\mathrm{Zorn}$ 引理、基数的三歧性

四、关系

关系的运算
1. $R_1\circ (R_2\cup R_3)=R_1\circ R_2 \cup R_1\circ R_3$
2. $R_1\circ (R_2\cap R_3)\subseteq R_1\circ R_2\cap R_1\circ R_3$
3. $(R_1\cup R_2)\circ R_3=R_1\circ R_3\cup R_2\circ R_3$
4. $(R_1\cap R_2)\circ R_3\subseteq R_1\circ R_3\cap R_2\circ R_3$
5. $R[A\cup B]=R[A]\cup R[B]$
6. $R[\bigcup A]=\bigcup\{R[B]|B\in A\}$
7. $R[A\cap B]\subseteq R[A]\cap R[B]$
8. $R[\bigcap A]\subseteq \bigcap\{R[B]|B\in A\}$，其中 $A$ 非空
9. $R[A]-R[B]\subseteq R[A-B]$
10. $R\uparrow(A\cup B)=R\uparrow A\cup R\uparrow B$
11. $R\uparrow (A\cap B)=R\uparrow A\cap R\uparrow B$
关系的性质
1. 自反：$I_A\subseteq R, r (R)=R\cup I_A$
2. 反自反：$R\cap I_A=\emptyset$
3. 对称：$R=R^{-1}, s (R)=R\cup R^{-1}$
4. 反对称：$R\cap R^{-1}\subseteq I_A$
5. 传递：$R\circ R\subseteq R, t (R)$ 使用 $\mathrm{Warshall}$ 算法
6. $R_1,R_2$ 自反 $\Rightarrow R^{-1}, R_1\cap R_2, R_1\cup R_2, R_1\circ R_2$ 自反
7. $R_1, R_2$ 反自反/对称 $\Rightarrow R^{-1}, R_1\cap R_2, R_1\cup R_2, R_1-R_2$ 反自反/对称
8. $R_1, R_2$ 反对称 $\Rightarrow R^{-1}, R_1\cap R_2, R_1-R_2$ 反对称
9. $R_1, R_2$ 传递 $\Rightarrow R^{-1}, R_1\cap R_2$ 传递
10. $R_1\subseteq R_2\Rightarrow r/s/t (R_1)\subseteq r/s/t (R_2)$
11. $r/s (R_1)\cup r/s (R_2)=r/s (R_1\cup R_2)$
12. $t (R_1)\cup t (R_2)\subseteq t (R_1\cup R_2)$
13. $R$ 自反 $\Rightarrow s/t (R)$ 自反
14. $R$ 对称 $\Rightarrow r/t (R)$ 对称
15. $R$ 传递 $\Rightarrow r (R)$ 传递
16. $rs (R)=sr (R)$
17. $rt (R)=tr (R)$
18. $st (R)\subseteq ts (R)$
19. $(2022) R$ 的等价闭包：$tsr (R), trs (R), rts (R)$
特殊关系
1. 等价关系：自反、对称、传递
2. 相容关系：自反、对称
3. 偏序关系：自反、反对称、传递
4. 拟序关系：反自反、反对称、传递
5. 全序关系：两两都可比的偏序关系
6. 良序关系：任意非空子集都有最小元的偏序关系
7. 偏序关系八大元与链
  1. 最大/小元、上/下确界不一定存在，若存在必唯一
  2. 非空有限集合中极大/小元一定存在，但不一定唯一
  3. 最大/小元为极大/小元、上/下界、上/下确界
  4. 属于子集的上/下界为子集的最大/小元
  5. 最长链的长度为 $n\Rightarrow$ 至少存在 $n$ 个不相交的反链
8. 良序集一定是全序集
9. 有限全序集一定是良序集
10. 良序定理：任意集合都可以良序化

五、函数

函数的性质
1. $f, g$ 是满射/单射/双射 $\Rightarrow f\circ g$ 是满射/单射/双射
2. $f\circ g$ 是满射 $\Rightarrow f$ 是满射
3. $f\circ g$ 是单射 $\Rightarrow g$ 是单射
4. $f\circ g$ 是双射 $\Rightarrow f$ 是满射，$g$ 是单射
5. 左逆：$g\circ f=I_A$；右逆：$f\circ g=I_A$
6. $f$ 存在左逆/右逆 $\Leftrightarrow$ $f$ 是单射/满射
7. $f$ 存在左逆、右逆且两者相等 $\Leftrightarrow f$ 是双射
8. 存在单射：$m\le n$；满射：$m\ge n\gt 0\vee m=n=0$；双射：$m=n$
9. 函数与函数相容：$x\in A\cap C\Rightarrow f (x)=g (x)$
10. 函数与等价关系相容：$\langle x, y\rangle\in R\Rightarrow \langle f (x), f (y)\rangle \in R$
11. $f, g$ 相容 $\Leftrightarrow$ $f\cup g$ 是函数 $\Leftrightarrow f\uparrow (A\cap C)=g\uparrow (A\cap C)$
12. 函数集合 $C$ 相容 $\Rightarrow F=\bigcup C$ 是函数，$dom (F)=\bigcup \{dom (f)|f\in C\}$
13. $R$ 与 $f$ 相容 $\Rightarrow$ $\exists ! F: A/R\to A/R, F ([x]_R)=[f (x)]_R$
开集与闭集
1. 闭集：导集是原集合的子集
2. 任意集合的导集是闭集
3. 任意个闭集的交集是闭集，有限个闭集的并集是闭集
4. 开集：原集合是内点集合的子集
5. 任意个开集的并集是开集，有限个开集的交集是开集
6. 若 $A$ 是开集/闭集，则 $\mathbb R-A$ 是闭集/开集
实数
1. $\mathbb N\to \mathbb Z\to \mathbb Q_1\to \mathbb Q\to \mathbb B\to \mathbb R$
2. $1_\mathbb N=\{\emptyset\}, -1_\mathbb Z=\langle 0,1\rangle,-1_\mathbb Q=\{\frac{1}{-1},\frac{-1}{1},\frac{2}{-2},\frac{-2}{2},\dots\},-1_\mathbb R=\{-1,-1+\frac{1}{n},\dots\}$
3. $\mathbb N\approx \mathbb Z, \mathbb R\approx \mathbb R^+, \mathbb N\times \mathbb N\approx \mathbb N, \mathbb N\approx \mathbb Q, (0,1)\approx \mathbb R,[0,1]\approx (0,1),\neg \mathbb N\approx \mathbb R$
4. $P (A)\approx A_2,\neg A\approx P (A)$
5. $(2022) \mathbb R\approx \mathbb R\times \mathbb N$

笔记

#数学 #大一上

离散数学(1)

https://sqzr2319.github.io/DiscreteMath-1/

作者

sqzr2319

发布于

2025年1月2日

许可协议

线性代数(1) 上一篇

肆叁小灶第二讲数学软件与线性代数下一篇