离散复习

集合

• 给定两个集合$A,B$和全集$S$求：
  • 交集$A\cup B$
    • A与B的所有元素
  • 并集
    • A与B中都有的元素
  • 差集$A-B$
    • 将$A$中元素减去$B$中存在的
  • 对称差$A△B$
    • $A△B=(A-B)\cup (B-A)$
  • $A$的余集
    • 全集中非$A$的部分,即 $S-A$
  • 笛卡尔积$A\times B$
    • $A\times B=\{(a,b)|a\in A,b\in B\}$
    • 最后形式上应该如$\{(a_1,b_1),(a_1,b_2),(a_1,b_3),(a_2,b_1)\cdots (a_3,b_3)\}$
    • 笛卡尔积对交并差有结合律
  • $2^A$ 即$A$所有子集构成的集合 注意不要忘记$\varnothing$和本身
• 证明两个集合相等
  • 互为子集法
  • 例：集合A为偶数集合，集合B$\{x|x\mathrm{mod}2=0,x\in Z\}$
  • 具体步骤
    1. 任取元素 ： 设 $x\in A$
    2. 性质处理 ： 则 $x$ 为偶数，即 $\exists k,x=2k$
    3. 证明子集 ： $2k\mathrm{mod}2=0$即$x\in B$ ,故$A\subseteq B$
    4. 反向证明 ： 设 $y\in B$ 有 $y\mathrm{mod}2=0$,即 $y$ 为偶数，故 $B\subseteq A$
    5. 证明相等 ： 因为 $A\subseteq B$ 且 $B\subseteq A$,故 $A=B$
• 证明对称差满足结合率
  • 即证明 ： $A△(B△C)=(A△B)△C$
  • 证明思路：
    • $A△B=(A-B)\cup (B-A)$
    • 将上式左右打开即可证明
• 容斥原理
  • $\left|\sum _{i=1}^n{A}_i\right|=\sum _{i=1}^n|A_i|-\sum _{i=1}^{\frac{n}{2}}|A_{2i+1}{A}_{2(i+1)}|+\cdots (-1{)}^{n-1}\left|{\bigcup }_{i=1}^n{A}_i\right|$

指向原始笔记的链接

---

关系

写法习惯注意

本文以下内容表示$x,y$的一个二元关系$R$的写法表现为$(x,y)\in R$ 也有如同 $xRy$ 表示二元关系的

五种关系

由集合$S$上的元素构成二元关系$R$

• 自反
  • 定义：对于 $\forall x\in S$ 都有 $(x,x)\in R$
  • 证明思路：
    • 设$x\in S$
    • 根据基于$R$的具体定义构造x与x的关系并且满足于R
    • 因此$(x,x)\in R$
• 对称
  • 定义：$\forall x,y\in S$,如果 $(x,y)\in R$,那么$(y,x)\in R$
  • 证明思路：
    • 设$x，y\in S$且$(x,y)\in R$
    • 根据$(x,y)\in R$ 与$R$的具体定义，推导出$y$与$x$也满足关系 $R$
    • 因此$(y,x)\in R$
• 传递
  • 定义：$\forall x,y,z\in S$,如果$(x,y)\in R$且$(y,z)\in R$ 那么 $(x,z)\in R$
  • 证明思路：
    • 设 $x,y,z\in S$ 且 $(x,y)\in R\text{and}(y,z)\in R$
    • 根据$R$推导出$x$与$z$也满足关系
    • 因此$(x,z)\in R$
• 反对称
  • 定义：$\forall x,y\in A$ 如果$(x,y)\in R$且$(y,x)\in R$ 那么$x=y$
  • 证明思路：
    • 设$x,y\in S$ 且 $(x,y)\in R$ 且 $(y,x)\in R$
    • 根据$R$推导出如果假设成立则必须有$x=y$
    • 因此 $x=y$,故$R$是反对称的

等价类

等价类代表某一特性在这个等价关系中是 等价的 如在$x\equiv y(\mathrm{mod}3)$关系下有三个等价类： $[0]=\{x|x\mathrm{mod}3=0,x\in I\}$ $[1]=\{x|x\mathrm{mod}3=1,x\in I\}$ $[2]=\{x|x\mathrm{mod}3=2,x\in I\}$

等价关系与偏序关系

若一个二元关系R满足自反 对称 传递 则这个二元关系为等价关系 若一个二元关系R满足自反 反对称 传递 则这个二元关系为偏序关系

关系的运算

关系的复合运算一般使用矩阵形式展开

$$A_{ij}=\{\begin{array}{ll}1& (i,j)\in R\\ 0& (i,j)\notin R\end{array}$$

• 复合关系 $R\circ S$ 则使用$R$矩阵与$S$矩阵进行矩阵乘法
• 逆关系矩阵为原矩阵的转置

指向原始笔记的链接

---

映射

单射与满射

映射最重要的两个概念：单射，满射 有一个映射 $f$ 满足 $X\to Y$

• 对单射证明：
  • $\forall x_1,x_2\in A$ 如果 $x_1\ne x_2⟹f(x_1)\ne f(x_2)$ 则$f$为单射
• 对满射的证明：
  • $\forall y\in Y\text{if}\exists x\in X⟹f(x)=y$ 则 $f$ 为满射
• 对双射的证明：
  • 如果映射 $f$ 同时满足单射和满射，则 $f$ 为双射

映射的复合

我们可以将集合的复合看为函数的复合

• 求映射的复合
  • 将两个映射看为函数复合

事实上，我们可以完全等价 $(f\circ g)(x)⟺f(g(x))$ 在我们解决一些问题上也会应用这个概念

• 已知 $f:X\to Y,g:Y\to Z$ 且 $g\circ f$ 为满射，证明$g$为满射
  • 思路：
    • $\forall z\in Z$ 有 $\exists x\in X$使得 $(g\circ f)(x)=z$
    • $(g\circ f)(x)⟺g(f(x))$
    • 因为$x\in X$且$f:X\to Y$ 则$f(x)\in y$
    • 令$f(x)=y_0$ 且$g:Y\to Z$,则有$g(y_0)\in Z$
    • 即证

映射的逆

映射存在逆的充要条件是映射是双射

• 如何求逆？
  • 令$f(x)=y$ 则 $f^{-1}(y)$就是将$f(x)=y$中$x，y$互换

指向原始笔记的链接

---

谓词逻辑与命题推理

谓词符号化

一般而言这类题目不难，思路是设出$R(x)$:x为xxx,$S(x)$:x为xxx 然后注意对$\forall ,\exists$的使用

• 谓词符号化：所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
  • 设$M(x)$:$x$是人
  • 设$R(x)$:$x$会死
  • 设$s$:$s$是苏格拉底
  • 有：因为$(\forall x)(M(x)\to R(x))\wedge M(s)$故$R(s)$
• 谓词符号化:所有的大学生都会说英语，有一些大学生会说法语
  • 设$E(x)$:$x$会说英语
  • 设$F(x)$:$x$会说法语
  • 设$S(x)$:$x$是大学生
  • 有1.$(\forall x)(S(x)\to E(x))$ 2.$(\exists x)(S(x)\wedge F(x))$
  • 注意，在使用$\exists$时候，我们需要使用合取来表示含义而不是蕴含
  • 同时两个陈述并列的时候应该不要使用$\vee$链接

命题推理

以题目形式表现

• 证明下列推理形式的有效性:今天或者是晴天,或者会下雨。如果是晴天,我就会去打球;如果我去打球,那么我就不读书。所以如果我在读书,那么天就在下雨。
  • 命题符号化
    • 设$p$为今天是晴天
    • 设$q$为今天是雨天
    • 设$b$表示我去打球
    • 设$r$表示我在读书
  • 符号化有:

$$\begin{array}{rlr}& p\vee q,p\to b,b\to \neg r& \Rightarrow r\to q\\ & & \\ & (1)r& P(附加)\\ & (2)b\to \neg r& P\\ & (3)\neg b& T(1)(2)I\\ & (4)p\to b& P\\ & (5)\neg p& T(3)(4)I\\ & (6)p\vee q& P\\ & (7)q& T(5)(6)I\\ & (8)r\to q& CP\end{array}$$

• 主要逻辑规则

  • 如果有$p\to q$和$p$,则可以推出$q$
  • 如果有$p\to q$和$\neg q$,则可以推出$\neg p$
  • 如果有$p\vee q$和$\neg q$ 则可以推出$p$,反之亦然
  • 如果有$p$和$q$,则可以推出$p\wedge q$ ,反之亦然
  • 如果有$p\to q$和$q\to r$，则可以推出$p\to q$
  • 如果有$(p\to q)\wedge (r\to s)$和$p\vee r$，则可以推出$q\wedge s$

• 反证法例子

  • 一个具体的例子:证明 $p\to q\Rightarrow \neg q\to \neg p$

\begin{align*} & (1) \quad p \to q & P \\ & (2) \quad \neg (\neg q \to \neg p) & P \quad (\text{反证假设}) \\ & (3) \quad \neg q \land \neg (\neg p) & T(2) \quad (\text{由 } \neg (A \to B) \equiv A \land \neg B \text{}) \\ & (4) \quad \neg q \land p & T(3) \quad (\text{由双重否定 } \neg(\neg p) \equiv p \text{}) \\ & (5) \quad p & T(4) \quad (\text{由合取消除}) \\ & (6) \quad \neg q & T(4) \quad (\text{由合取消除}) \\ & (7) \quad q & T(1)(5) \quad (\text{由 } p \to q \text{ 和 } p \text{，通过肯定前件}) \\ & (8) \quad q \land \neg q & T(6)(7) \quad (\text{由 } q \text{ 和 } \neg q \text{，得到矛盾}) \\ & (9) \quad \neg \neg (\neg q \to \neg p) & IP(2-8) \quad (\text{由矛盾，推导出假设的否定}) \\ & (10) \quad \neg q \to \neg p & DN(9) \quad (\text{由双重否定，得到原结论}) \end{align*} $$ - 显然反证法没有CP好用指向原始笔记的链接

近世代数

群

一个代数系统通常包括一个集合$A$和一个关系$\ast$ 记作$(A,\ast )$

$$群\{\begin{array}{l}半群\{\begin{array}{l}封闭性\\ 结合律\end{array}\\ \\ \downarrow \\ \\ 幺半群:\exists 单位元\\ \\ \downarrow \\ \\ 对每个元素有逆元\end{array}$$

当然还有阿贝尔群(群的基础上添加交换律)和循环群(有生成元)

现在我们主要讲讲如何考虑单位元和逆元，封闭性和结合律的证明都是通过任取元算($\forall x,y,z\in A$),通过*证明满足$x\ast y\in A$和$x\ast (y\ast z)=(x\ast y)\ast z$即可

• 单位元
  • 定义：$\exists e\in A$,使得$\forall a\in A$都有$a\ast e=a$且 $e\ast a=a$
  • 证明思路：
    • 猜测或找到一个候选的单位元$e$
    • 证明这个$e$确实在集合$G$中
    • 对$\forall a\in A$：
      • 证明 $a\ast e=a$
      • 证明 $e\ast a=a$
    • tips: 如果运算是交换的，证明上述一个即可
• 逆元
  • 定义：$\forall a\in A$ 都 $\exists a^{-1}\in A$使得 $a\ast a^{-1}=eand{a}^{-1}\ast a=e$
  • 证明思路
    • 任取$a\in A$ ($\forall a\in A$)
    • 找到或猜测$a$的候选逆元$a^{-1}$，这通常是基于运算的定义和单位元
    • 证明$a^{-1}\in G$
    • 证明$a\ast a^{-1}=e$
    • 证明$a^{-1}\ast a=e$

指向原始笔记的链接

布尔逻辑与格

本篇依旧是在代数系统$(A,\ast )$上进行讨论

• 偏序集
  • 也就是判断给定$(A,\ast )$是不是偏序关系
    • 证明自反，反对称，传递
• 格
  • 对任意两个元素$a,b\in A$都存在最小上界($a\vee b$)和最大下界($a\wedge b$)
• 有界格
  • 在格的基础上存在最大元素(记作$1$)和最小元素(记作$0$)
• 有补格
  • 在有界格$(A,\ast ,0,1)$基础上，对$\forall a\in A$ 有 $\exists a^{\prime }\in A\Rightarrow a\wedge a^{\prime }=0anda\vee a^{\prime }=1$
  • 补元不一定是唯一的
• 分配格
  • 满足以下两个等价的分配律中的任意一个
    • $\forall a,b,c\in A⟹a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$
    • $\forall a,b,c\in A⟹a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$
• 布尔代数
  • $(B,\wedge ,\vee {,}^{\prime },0,1)$是一个布尔代数，如果它是一个有补分配格

指向原始笔记的链接

---

图论与树

Tips

考虑历年题目，按重要程度书写

最小生成树问题

• 通常以一个带权无向图的形式出现（图可能代表城市、村庄、矿井采集点等）
• 问题直接明了：“求总成本最低的补给线路”、“设计总造价最小的修路方案”、“计算最小成本”等。
• 要求：不仅要算出最小的总权值，通常还需要画出或列出构成最小生成树的边集。

算法：

• 克鲁斯卡尔算法：按权值从小到大选择边，只要不形成回路就加入，直到链接完所有定点为止
• Prim算法：从一个顶点开始，每次选择连接已选顶点集和未选顶点集的权值最小的边
• 一般而言选择第一种算法，更加直观清晰

主要模型建模

• 哈密顿回路/路径：
  • 场景：“圆桌会议”,“旅行商问题”
  • 问题：“能否安排座位使得相邻的人都能交谈？”,“能否找到一条路径访问所有点一次？”
  • 方法：将人/地点视为 顶点，将可以交流/连接的关系视为 边，问题转化为寻找一条经过所有顶点的回路。
  • 判断是否存在哈密顿回路方法：
    • 这是一个完全NP问题，我们可以依据下面一些条件初步判断
      • 若顶点数大于3：
        • Dirac定理：若每个顶点的度数 $deg(v)\ge \frac{n}{2}$则为哈密顿图
        • Orc定理 ：若对两个不相邻的顶点$u,v$ 有$deg(v)+deg(u)\ge n$则是哈密顿图
      • 这是一个充分条件，有时候不满足上述两条也可能构成哈密顿图，需要自己再看看
• 图的着色 (Graph Coloring)
  • 场景：“考试时间安排”、“会议安排”、“地图着色”。
  • 问题：“最少需要多少时间段才能考完所有课程？”
  • 方法：将课程/事件/国家视为顶点，如果两个课程有学生同时选修（即存在冲突），则在对应顶点间连一条边。问题转化为求该图的色数（最少需要多少种颜色给顶点着色，使得相邻顶点颜色不同）。
    • 这是一个著名的NP完全问题，在考试情景下不可能过分困难
    • 勇敢尝试
• 匹配 (Matching)
  • 场景：“配对问题”、“任务分配”
  • 问题：“能否选出4组不同的配对，用完所有8种颜料？
  • 建模方法：将颜料/人员视为顶点，能互相搭配的关系视为边。问题转化为寻找图中的 完美匹配（一个覆盖所有顶点的边子集，且边与边之间不共享顶点）。
    • 完美匹配存在的性质
      • 当一个图的顶点数量$|V|$为偶数时候才有可能存在完美匹配
      • 最大匹配是指图中边数最多的匹配
      • 如果一个最大匹配包含了图中的所有顶点，那么它就是一个完美匹配
      • 如果一个图有偶数个顶点且存在哈密顿回路，那么这个图一定存在完美匹配

理论证明：平面图与欧拉公式

主要考虑

• 欧拉公式：$v-e+f=2$ 
• 其中，$v$:顶点数,$e$:边数, $f$:面数(不用忘记外部面)
  • 推论1： 对于$v\ge 3$的简单连通平面图$e\le 3v-6$
  • 推论2： 如果简单连通平面图中没有长度为3的回路（即没有三角形），$e\le 2v-4$
  • 面度数推论 ：根据握手定理我们可以得出$\sum _{i=1}^{f}deg(F_i)=2e$
  • 即所有面的度数之和等于2倍的边数

指向原始笔记的链接

---

数理逻辑

• 数理逻辑只需要记住三个公式(会不会自求多福吧因为我也不会)
• 一

$P\to Q⟺\neg P\vee Q$

• 二

$$\begin{array}{rl}\neg (\exists x)P(x)⟺& (\forall x)\neg P(x)\\ \neg (\forall x)P(x)⟺& (\exists x)\neg P(x)\end{array}$$

• 三 ：量词分配：$\forall$只能对$\wedge$分配 $\exists$只能对$\vee$分配

$$\begin{array}{r}\forall x(P(x)\wedge Q(x))⟺\forall xP(x)\wedge \forall xQ(x)\\ \exists x(P(x)\vee Q(x))⟺\exists xP(x)\vee \exists xQ(x)\end{array}$$指向原始笔记的链接