# 离散数学

## 离散数学部分

### 试卷1, 部分来自历年卷(sp24)

#### 单选题

> [!NOTE]
>
> **1\. \[猜测\]**
>
> 设论域为全体实数，\\(P(x)\\) 表示“\\(x\>0\\)”，\\(Q(x)\\) 表示“\\(x^2=1\\)”。命题 \\(\\exists x(P(x)\\land Q(x))\\) 的真值为（）
>
> (A) 真
>
> (B) 假
>
> (C) 不确定
>
> (D) 无法判断
>
> > **点击查看答案**
> >
> > **A（真）**。\\(\\exists x(x\>0 \\land x^2=1)\\)，取 \\(x=1\\) 即可满足。

> [!NOTE]
>
> **2\. \[猜测\]**
>
> 设 \\(A=\\{\\emptyset,\\{\\emptyset\\}\\}\\)，则 \\(\\mathcal{P}(A)\\) 中元素的个数为（）
>
> (A) \\(2\\)
>
> (B) \\(3\\)
>
> (C) \\(4\\)
>
> (D) \\(8\\)
>
> > **点击查看答案**
> >
> > **C（4）**。\\(A=\\{\\emptyset, \\{\\emptyset\\}\\}\\) 有 2 个元素，\\(|\\mathcal{P}(A)|=2^2=4\\)。

> [!NOTE]
>
> **3\. \[猜测\]**
>
> 设函数 \\(f:\\mathbb{Z}\\to\\mathbb{Z}\\) 定义为 \\(f(x)=x^2\\)，则 \\(f\\) 是（）
>
> (A) 单射且满射
>
> (B) 单射但非满射
>
> (C) 满射但非单射
>
> (D) 既非单射也非满射
>
> > **点击查看答案**
> >
> > **D（既非单射也非满射）**。\\(f(x)=x^2\\) 在 \\(\\mathbb{Z}\\) 上：\\(f(1)=f(-1)=1\\) 非单射；负数不在值域中，非满射。
>
> > **单射 / 满射 / 双射**
> >
> > - **单射**：\\(f(a)=f(b)\\Rightarrow a=b\\)（不同输入不同输出）
> > - **满射**：\\(\\forall y\\in Y,\\exists x\\in X,\\ f(x)=y\\)（值域=陪域）
> > - **双射**：既单又满，可逆。

> [!NOTE]
>
> **4\. \[猜测\]**
>
> 设 \\((G,\*)\\) 是群，\\(e\\) 是单位元，\\(a,b\\in G\\)。以下说法正确的是（）
>
> (A) 若 \\(a\*b=e\\)，则 \\(a\\) 和 \\(b\\) 互为逆元
>
> (B) 群中一定存在零元
>
> (C) 群中每个元素的逆元可以不唯一
>
> (D) 若 \\(a\\neq e\\)，则 \\(a\*a\\neq e\\)
>
> > **点击查看答案**
> >
> > **A（若 \\(a\*b=e\\)，则 \\(a\\) 和 \\(b\\) 互为逆元）**。由群的定义，每个元素都有逆元，且 \\(a\*b=e\\) 即 \\(b=a^{-1}\\)。
> >
> > - ✗ B：群中不一定有零元。注意零元 \\(\\neq\\) 单位元：零元 \\(z\\) 满足 \\(\\forall a, a\*z=z\\)（吸收性），而单位元 \\(e\\) 满足 \\(a\*e=a\\)（不变性）。反例：\\((\\mathbb{Z},+)\\) 中 \\(0\\) 是单位元（\\(a+0=a\\)），但不是零元——若存在零元 \\(z\\) 则需 \\(a+z=z\\) 即所有 \\(a=0\\)，矛盾。事实上只有平凡群 \\(\\{e\\}\\) 才有零元。
> > - ✗ C：群中每个元素的逆元唯一。若 \\(b,c\\) 都是 \\(a\\) 的逆元，则 \\(b=b\*e=b\*(a\*c)=(b\*a)\*c=e\*c=c\\)。
> > - ✗ D：\\(a\\neq e\\) 时也可能 \\(a\*a=e\\)。反例：\\((\\{0,1\\},\\oplus)\\)（异或群），单位元 \\(e=0\\)，\\(1\\neq0\\) 但 \\(1\\oplus1=0=e\\)（即 1 是二阶元）。

> [!NOTE]
>
> **5\. \[猜测\]**
>
> 设 \\(R\\) 是集合 \\(A=\\{1,2,3,4\\}\\) 上的关系，\\(R=\\{(1,2),(2,3),(3,4)\\}\\)，则 \\(R\\) 的传递闭包 \\(t(R)\\) 中元素的个数为（）
>
> (A) \\(4\\)
>
> (B) \\(5\\)
>
> (C) \\(6\\)
>
> (D) \\(7\\)
>
> > **点击查看答案**
> >
> > **C（6）**。\\(t(R)\\) 需补充传递关系：\\((1,2)+(2,3)\\to(1,3)\\)，\\((2,3)+(3,4)\\to(2,4)\\)，\\((1,3)+(3,4)\\to(1,4)\\)。原 3 对 + 新增 3 对 = 6。

> [!NOTE]
>
> **6\. \[猜测\]**
>
> 一个无向连通图是欧拉图的充要条件是（）
>
> (A) 所有顶点的度数均为偶数
>
> (B) 恰好有两个顶点的度数为奇数
>
> (C) 边数大于顶点数
>
> (D) 图中无环
>
> > **点击查看答案**
> >
> > **A（所有顶点的度数均为偶数）**。欧拉图的充要条件：连通且每个顶点度数为偶数。
>
> > **欧拉图 vs 欧拉通路**
> >
> > - **欧拉通路**：经过每条边恰好一次的**路径**（不要求回到起点）→ 充要：连通 + 恰有 0 或 2 个奇度顶点
> > - **欧拉图（欧拉回路）**：经过每条边恰好一次的**回路**（回到起点）→ 充要：连通 + 0 个奇度顶点

> [!NOTE]
>
> **7\. \[猜测\]**
>
> 下列命题公式中，是永真式的是（）
>
> (A) \\((P\\to Q)\\to(Q\\to P)\\)
>
> (B) \\((P\\land Q)\\to(P\\lor Q)\\)
>
> (C) \\((P\\to Q)\\land\\neg P\\to\\neg Q\\)
>
> (D) \\(P\\land(P\\to Q)\\to\\neg Q\\)
>
> > **点击查看答案**
> >
> > **B（\\((P\\land Q)\\to(P\\lor Q)\\)）**。这是永真式：如果 \\(P\\land Q\\) 成立则 \\(P\\lor Q\\) 必成立。其余选项均非永真。

---

#### 不定项选择题

> [!NOTE]
>
> **1\. \[真题\]**
>
> 设 \\((G,\*)\\) 是群，其中 \\(\*\\) 是通常的加法运算，则以下能够构成群的是（）
>
> (A) 整数集 \\(\\mathbb{Z}\\)
>
> (B) 有理数集 \\(\\mathbb{Q}\\)
>
> (C) 偶数集 \\(\\{2k\\mid k\\in\\mathbb{Z}\\}\\)
>
> (D) 自然数集 \\(\\mathbb{N}\\)
>
> > **点击查看答案**
> >
> > **ABC**。\\(\\mathbb{Z},\\mathbb{Q}\\) 对加法构成群；偶数集也是加法子群。\\(\\mathbb{N}\\) 无负元（逆元）。
>
> > **群的四条公理**
> >
> > 1. **封闭性**：\\(\\forall a,b\\in G,\\ a\*b\\in G\\)
> > 2. **结合律**：\\(\\forall a,b,c\\in G,\\ (a\*b)\*c=a\*(b\*c)\\)
> > 3. **单位元**：\\(\\exists e\\in G,\\forall a\\in G,\\ e\*a=a\*e=a\\)
> > 4. **逆元**：\\(\\forall a\\in G,\\exists a^{-1}\\in G,\\ a\*a^{-1}=a^{-1}\*a=e\\)

> [!NOTE]
>
> **2\. \[猜测\]**
>
> 关于集合的幂集，下列说法中正确的有（）
>
> (A) 对于任何集合 \\(A\\)，恒有 \\(\\emptyset\\in\\mathcal{P}(A)\\)
>
> (B) 若 \\(A\\subseteq B\\)，则 \\(\\mathcal{P}(A)\\subseteq\\mathcal{P}(B)\\)
>
> (C) \\(\\mathcal{P}(A\\cap B)=\\mathcal{P}(A)\\cap\\mathcal{P}(B)\\) 恒成立
>
> (D) \\(A\\in\\mathcal{P}(A)\\) 恒成立
>
> > **点击查看答案**
> >
> > **ABCD**。(A) 空集是任何集合的子集；(B) 幂集单调性；(C) 幂集保交(不保并)；(D) \\(A\\subseteq A\\) 恒成立，故 \\(A\\in\\mathcal{P}(A)\\)。

> [!NOTE]
>
> **3\. \[猜测\]**
>
> 设映射 \\(f:X\\to Y\\)，\\(A,B\\subseteq X\\)，\\(C,D\\subseteq Y\\)。下列关系式中恒成立的有（）
>
> (A) \\(f^{-1}(C\\cap D)=f^{-1}(C)\\cap f^{-1}(D)\\)
>
> (B) \\(f(A\\cap B)=f(A)\\cap f(B)\\)
>
> (C) \\(f^{-1}(f(A))\\supseteq A\\)
>
> (D) \\(f(f^{-1}(C))\\subseteq C\\)
>
> > **点击查看答案**
> >
> > **ACD**。(A) 原像保交；(B) \\(f(A\\cap B)\\subseteq f(A)\\cap f(B)\\)，但未必相等；(C) \\(f^{-1}(f(A))\\) 包含 \\(A\\) 及其在 \\(f\\) 下的原像；(D) \\(f(f^{-1}(C))\\subseteq C\\)，满射时可取等。

> [!NOTE]
>
> **4\. \[猜测\]**
>
> 设 \\(R\\) 是集合 \\(A\\) 上的二元关系。下列说法正确的有（）
>
> (A) \\(R\\) 是自反的当且仅当 \\(I\_A\\subseteq R\\)（其中 \\(I\_A\\) 为恒等关系）
>
> (B) \\(R\\) 是对称的当且仅当 \\(R=R^{-1}\\)
>
> (C) \\(R\\) 是传递的当且仅当 \\(R\\circ R\\subseteq R\\)
>
> (D) \\(R\\) 是反对称的当且仅当 \\(R\\cap R^{-1}\\subseteq I\_A\\)
>
> > **点击查看答案**
> >
> > **ABCD**。均为关系性质的等价刻画。
>
> > **关系四性质速记**
> >
> > - **自反**：\\(\\forall x,\\ xRx\\)（对角线全在）
> > - **反自反**：\\(\\forall x,\\ \\neg(xRx)\\)（对角线全不在）
> > - **对称**：\\(xRy\\Rightarrow yRx\\)（矩阵对称）
> > - **反对称**：\\(xRy\\land yRx\\Rightarrow x=y\\)（矩阵非对角线无对称对）
> > - **传递**：\\(xRy\\land yRz\\Rightarrow xRz\\)

> [!NOTE]
>
> **5\. \[猜测\]**
>
> 关于图的同构和性质，下列说法正确的有（）
>
> (A) 两个同构的简单无向图的顶点数和边数一定分别相等
>
> (B) 两个同构的图一定具有相同数量的连通分支
>
> (C) 若两个简单无向图的度序列完全相同，则它们一定同构
>
> (D) 任何简单图的生成子图一定包含原图的所有顶点
>
> > **点击查看答案**
> >
> > **ABD**。(A)(B) 同构定义保证；(C) 度序列相同非充分条件（存在不同构但度序列相同的图）；(D) ✓，生成子图 (spanning subgraph) 的定义就是 \\(V\_1=V\_2\\)，即包含原图所有顶点，只是边集可以是原边集的子集。
>
> > **子图 / 真子图 / 生成子图**
> >
> > - **子图** (subgraph)：\\(V\_1\\subseteq V\_2\\)，\\(E\_1\\subseteq E\_2\\)
> > - **真子图** (proper subgraph)：子图且 \\(G\_1\\neq G\_2\\)
> > - **生成子图** (spanning subgraph)：子图且 \\(V\_1=V\_2\\)（顶点全含，边可少）
>
> > **度序列相同 ⇏ 同构（反例）**
> >
> > 下图两个图度序列均为 \\((2,2,2,2,2,2)\\)，但不同构：
> >
> > - \\(C\_6\\)（6-cycle，连通）
> > - \\(2\\times C\_3\\)（两个分离三角形，不连通）
> >
> > 一个连通、一个不连通，显然不同构。

> [!NOTE]
>
> **6\. \[猜测\]**
>
> 下列谓词逻辑等值式中，正确的有（）
>
> (A) \\(\\neg\\forall x A(x)\\iff\\exists x\\neg A(x)\\)
>
> (B) \\(\\forall x(A(x)\\land B(x))\\iff\\forall x A(x)\\land\\forall x B(x)\\)
>
> (C) \\(\\exists x(A(x)\\lor B(x))\\iff\\exists x A(x)\\lor\\exists x B(x)\\)
>
> (D) \\(\\forall x\\forall y(A(x)\\to B(y))\\iff\\exists x A(x)\\to\\forall y B(y)\\)
>
> > **点击查看答案**
> >
> > **ABCD**。(A)(B)(C) 为谓词逻辑基本等值式；(D) 也是正确的等值式。
> >
> > > **D 的证明**
> > >
> > > \\\[ \\begin{aligned} \\forall x\\forall y(A(x)\\to B(y)) &\\iff \\forall x\\forall y(\\neg A(x)\\lor B(y)) &&\\text{(蕴含展开)} \\\\ &\\iff \\forall x(\\neg A(x)\\lor\\forall y B(y)) &&\\text{($y$ 不在 $\\neg A(x)$ 中自由)} \\\\ &\\iff \\forall x\\neg A(x)\\lor\\forall y B(y) &&\\text{($x$ 不在 $\\forall y B(y)$ 中自由)} \\\\ &\\iff \\neg\\exists x A(x)\\lor\\forall y B(y) &&\\text{(量词否定)} \\\\ &\\iff \\exists x A(x)\\to\\forall y B(y) &&\\text{(蕴含定义)} \\end{aligned} \\\]
>
> > **谓词逻辑常用等值式总结**
> >
> > | 等值式 | 说明 |
> > | --- | --- |
> > | \\(\\neg\\forall x A \\iff \\exists x\\neg A\\) | 量词否定 |
> > | \\(\\neg\\exists x A \\iff \\forall x\\neg A\\) | 量词否定 |
> > | \\(\\forall x(A\\land B) \\iff \\forall x A\\land\\forall x B\\) | \\(\\forall\\) 对 \\(\\land\\) 可分配 |
> > | \\(\\exists x(A\\lor B) \\iff \\exists x A\\lor\\exists x B\\) | \\(\\exists\\) 对 \\(\\lor\\) 可分配 |
> > | \\(\\forall x A\\lor\\forall x B \\Rightarrow \\forall x(A\\lor B)\\) | 单向，反向不成立 |
> > | \\(\\exists x(A\\land B) \\Rightarrow \\exists x A\\land\\exists x B\\) | 单向，反向不成立 |
> > | \\(\\forall x\\forall y(A(x)\\to B(y)) \\iff \\exists x A(x)\\to\\forall y B(y)\\) | 量词前移等值式 |
> > | \\(\\forall x(A\\to B) \\Rightarrow \\forall x A\\to\\forall x B\\) | 全称实例化+假言推理 |

---

#### 计算题

> [!NOTE]
>
> **1\. \[真题\]**
>
> 设 \\(X=\\{0,1,2,3\\}\\)，\\(X\\) 上有两个关系： \\(R\_1=\\{(i,j)\\mid j=i+1\\text{ 或 }j=\\dfrac{i}{2}\\}\\)， \\(R\_2=\\{(i,j)\\mid i=j+2\\}\\)。 求下列复合关系： (1) \\(R\_1\\circ R\_2\\) (2) \\(R\_2\\circ R\_1\\) (3) \\(R\_1\\circ R\_2\\circ R\_1\\)
>
> > **点击查看答案**
> >
> > **先写出集合形式：**
> >
> > \\\[R\_1=\\{(0,1),(0,0),(1,2),(2,3),(2,1)\\}\\\]
> >
> > \\\[R\_2=\\{(2,0),(3,1)\\}\\\]
> >
> > ---
> >
> > **(1) \\(R\_1\\circ R\_2\\)**
> >
> > \\(R\_1\\circ R\_2\\) 表示先 \\(R\_1\\) 后 \\(R\_2\\)：\\(R\_1\\circ R\_2=\\{(x,z)\\mid\\exists y,(x,y)\\in R\_1\\land(y,z)\\in R\_2\\}\\)。
> >
> > 遍历 \\(R\_1\\) 中的 \\((x,y)\\)，检查 \\(y\\) 是否在 \\(R\_2\\) 的定义域 \\(\\{2,3\\}\\) 中：
> >
> > - \\((1,2)\\in R\_1\\)，而 \\((2,0)\\in R\_2\\) → 得 \\((1,0)\\)
> > - \\((2,3)\\in R\_1\\)，而 \\((3,1)\\in R\_2\\) → 得 \\((2,1)\\)
> >
> > \\\[R\_1\\circ R\_2=\\{(1,0),(2,1)\\}\\\]
> >
> > ---
> >
> > **(2) \\(R\_2\\circ R\_1\\)**
> >
> > \\(R\_2\\circ R\_1\\) 表示先 \\(R\_2\\) 后 \\(R\_1\\)：\\(R\_2\\circ R\_1=\\{(x,z)\\mid\\exists y,(x,y)\\in R\_2\\land(y,z)\\in R\_1\\}\\)。
> >
> > - \\((2,0)\\in R\_2\\)，而 \\((0,1),(0,0)\\in R\_1\\) → 得 \\((2,1),(2,0)\\)
> > - \\((3,1)\\in R\_2\\)，而 \\((1,2)\\in R\_1\\) → 得 \\((3,2)\\)
> >
> > \\\[R\_2\\circ R\_1=\\{(2,1),(2,0),(3,2)\\}\\\]
> >
> > ---
> >
> > **(3) \\(R\_1\\circ R\_2\\circ R\_1\\)**
> >
> > 按结合律：\\(R\_1\\circ R\_2\\circ R\_1 = (R\_1\\circ R\_2)\\circ R\_1 = \\{(1,0),(2,1)\\}\\circ R\_1\\)。
> >
> > 注意先 \\((R\_1\\circ R\_2)\\) 后 \\(R\_1\\)：
> >
> > - 对于 \\((1,0)\\)：\\(0\\) 在 \\(R\_1\\) 中有后继 \\((0,1),(0,0)\\) → 得 \\((1,1),(1,0)\\)
> > - 对于 \\((2,1)\\)：\\(1\\) 在 \\(R\_1\\) 中有后继 \\((1,2)\\) → 得 \\((2,2)\\)
> >
> > \\\[R\_1\\circ R\_2\\circ R\_1=\\{(1,1),(1,0),(2,2)\\}\\\]

> [!NOTE]
>
> **2\. \[真题\]**
>
> 证明下列逻辑等值式：
>
> \\\[P\\to(Q\\to R)\\iff(P\\land Q)\\to R\\\]
>
> > **点击查看答案**
> >
> > \\\[ \\begin{aligned} P\\to(Q\\to R) &\\iff \\neg P\\lor(\\neg Q\\lor R) \\\\ &\\iff (\\neg P\\lor\\neg Q)\\lor R \\\\ &\\iff \\neg(P\\land Q)\\lor R \\\\ &\\iff (P\\land Q)\\to R \\end{aligned} \\\]

---

#### 证明题

> [!NOTE]
>
> **1\. \[真题\]**
>
> 设 \\(G\\) 是无向连通图，且 \\(G\\) 中恰好有两个顶点的度数为奇数，其余顶点的度数均为偶数。证明：这两个奇数度顶点之间一定存在一条路径（即它们一定连通）。
>
> > **点击查看答案**
> >
> > **反证法**。假设这两个奇度顶点 \\(u\\) 和 \\(v\\) 之间没有路径（不连通），那么它们必然分属两个不同的连通分支。
> >
> > 单独看 \\(u\\) 所在的连通分支：在这个分支里，除了 \\(u\\) 的度数为奇数，其余顶点度数全都是偶数（因为题目说整个图只有 \\(u\\) 和 \\(v\\) 两个奇度点，而 \\(v\\) 在另一个分支）。
> >
> > 但根据握手定理，任何图中奇度顶点的个数必须是偶数。这个分支只有 \\(u\\) 一个奇度顶点，矛盾。同理 \\(v\\) 所在的分支也会推出矛盾。所以假设不成立，\\(u\\) 和 \\(v\\) 必在同一连通分支中，即它们之间一定连通。
> >
> > > **握手定理 (Handshaking Lemma)**
> > >
> > > **内容**：无向图中所有顶点的度数之和等于边数的两倍，即 \\(\\sum\_{v\\in V}\\deg(v)=2|E|\\)。
> > >
> > > **推论**：任何图中，奇度顶点的个数一定是偶数。
> > >
> > > **直观理解**：每条边连接两个顶点，贡献 2 度。所以总度数 = \\(2\\times\\)边数，必为偶数。偶数 = 所有偶度顶点的度数（偶数） + 所有奇度顶点的度数。偶数减去偶数还是偶数，所以所有奇度顶点的度数之和必须是偶数——每个奇度顶点贡献奇数，必须成对出现才能凑成偶数。\\(\\square\\)

> [!NOTE]
>
> **2\. \[真题\]**
>
> 证明：对任意非负整数 \\(n\\)，\\(4^{2n+1}+3^{n+2}\\) 能被 \\(13\\) 整除。
>
> > **点击查看答案**
> >
> > **数学归纳法**。
> >
> > \\(n=0\\)：\\(4^1+3^2=4+9=13\\)，成立。
> >
> > 设 \\(n=k\\) 成立：\\(4^{2k+1}+3^{k+2}=13m\\)。
> >
> > \\(n=k+1\\)：
> >
> > \\\[ \\begin{align\*} 4^{2k+3}+3^{k+3} &= 16\\cdot4^{2k+1}+3\\cdot3^{k+2} \\\\ &= 13\\cdot4^{2k+1}+3(4^{2k+1}+3^{k+2}) \\\\ &= 13(4^{2k+1}+3m) \\end{align\*} \\\]
> >
> > 能被 13 整除。得证。

---

### 试卷2, 部分来自历年卷(sp25)

#### 单选题

> [!NOTE]
>
> **1\. \[真题\]**
>
> 设论域为 \\(\\{1,2\\}\\)，则 \\(\\exists x A(x)\\) 等价于（）
>
> (A) \\(A(1)\\land A(2)\\)
>
> (B) \\(A(1)\\lor A(2)\\)
>
> (C) \\(\\neg A(1)\\lor\\neg A(2)\\)
>
> (D) \\(A(1)\\to A(2)\\)
>
> > **点击查看答案**
> >
> > **B（\\(A(1)\\lor A(2)\\)）**。论域有限时，\\(\\exists x A(x)\\) 等价于对各元素的析取。

> [!NOTE]
>
> **2\. \[猜测\]**
>
> 设 \\(A=\\{a,b,c\\}\\)，\\(B=\\{1,2\\}\\)，则从 \\(A\\) 到 \\(B\\) 的函数的个数为（）
>
> (A) \\(5\\)
>
> (B) \\(6\\)
>
> (C) \\(8\\)
>
> (D) \\(9\\)
>
> > **点击查看答案**
> >
> > **C（8）**。从 \\(A\\)（3 元素）到 \\(B\\)（2 元素）的函数个数为 \\(2^3=8\\)。

> [!NOTE]
>
> **3\. \[真题\]**
>
> 已知 \\(A=\\{\\langle1,2\\rangle,\\langle2,1\\rangle,\\langle2,3\\rangle,\\langle3,4\\rangle\\}\\)，则 \\(A\\circ A=\\)（）
>
> (A) \\(\\{\\langle1,1\\rangle,\\langle1,3\\rangle,\\langle2,2\\rangle,\\langle2,4\\rangle\\}\\)
>
> (B) \\(\\{\\langle1,1\\rangle,\\langle2,4\\rangle\\}\\)
>
> (C) \\(\\{\\langle1,1\\rangle,\\langle1,3\\rangle,\\langle2,2\\rangle\\}\\)
>
> (D) \\(\\{\\langle2,1\\rangle,\\langle3,2\\rangle\\}\\)
>
> > **点击查看答案**
> >
> > **A（\\(\\{\\langle1,1\\rangle,\\langle1,3\\rangle,\\langle2,2\\rangle,\\langle2,4\\rangle\\}\\)）**。 \\(A\\circ A\\) 计算：\\((1,2)\\circ(2,1)=(1,1)\\)，\\((1,2)\\circ(2,3)=(1,3)\\)，\\((2,1)\\circ(1,2)=(2,2)\\)，\\((2,3)\\circ(3,4)=(2,4)\\)。共 4 个。

> [!NOTE]
>
> **4\. \[真题\]**
>
> 无向图 \\(G\\) 是欧拉图的充要条件为（）
>
> (A) \\(G\\) 连通且所有顶点度数为偶数
>
> (B) \\(G\\) 连通且恰有两个奇度顶点
>
> (C) \\(G\\) 中所有顶点度数均为奇数
>
> (D) \\(G\\) 的边数大于等于顶点数
>
> > **点击查看答案**
> >
> > **A（\\(G\\) 连通且所有顶点度数为偶数）**。

> [!NOTE]
>
> **5\. \[真题\]**
>
> 设 \\(A=\\{1,2,3,4,5,6,7,8\\}\\)，\\(R\\) 是 \\(A\\) 上的整除关系，\\(B=\\{2,4,6\\}\\)。关于 \\(B\\) 的以下叙述正确的是（）
>
> (A) \\(B\\) 有最大元 \\(6\\)，无最小元
>
> (B) \\(B\\) 有上确界，无下确界
>
> (C) \\(B\\) 无最大元，有极大元 \\(4\\) 和 \\(6\\)
>
> (D) \\(B\\) 的上确界是 \\(6\\)
>
> > **点击查看答案**
> >
> > **C（\\(B\\) 无最大元，有极大元 \\(4\\) 和 \\(6\\)）**。在整除关系下：\\(2\\mid4\\)，\\(2\\mid6\\)，但 \\(4\\nmid6\\) 且 \\(6\\nmid4\\)，故 \\(4\\) 和 \\(6\\) 不可比较，无最大元。\\(2\\) 是极小元（整除 \\(4\\) 和 \\(6\\)）。
> >
> > ✗ (A) \\(2\\) 是最小元（整除 \\(4\\) 和 \\(6\\)），无最大元。
> >
> > ✗ (B) 下确界为 \\(2\\)（\\(\\gcd(2,4,6)=2\\)）；上界需是 \\(\\operatorname{lcm}(2,4,6)=12\\) 的倍数，\\(A\\) 中没有，故无上确界。
> >
> > ✗ (D) \\(6\\) 不是上界（\\(4\\nmid6\\)），上确界不存在。

> [!NOTE]
>
> **6\. \[真题\]**
>
> 下列谓词逻辑等值式中错误的是（）
>
> (A) \\(\\neg\\forall x A(x)\\iff\\exists x\\neg A(x)\\)
>
> (B) \\(\\forall x(A(x)\\land B(x))\\iff\\forall x A(x)\\land\\forall x B(x)\\)
>
> (C) \\(\\exists x(A(x)\\land B(x))\\iff\\exists x A(x)\\land\\exists x B(x)\\)
>
> (D) \\(\\forall x\\forall y(A(x)\\to B(y))\\iff\\exists x A(x)\\to\\forall y B(y)\\)
>
> > **点击查看答案**
> >
> > **C（\\(\\exists x(A(x)\\land B(x))\\iff\\exists x A(x)\\land\\exists x B(x)\\)）**。方向 \\(\\to\\) 成立，但 \\(\\gets\\) 不成立（两个存在量词可能指不同 \\(x\\)）。
>
> > **量词转换口诀**
> >
> > - \\(\\neg\\forall x A \\iff \\exists x\\neg A\\)，\\(\\neg\\exists x A \\iff \\forall x\\neg A\\)
> > - \\(\\forall\\) 对 \\(\\land\\) 可分配；\\(\\exists\\) 对 \\(\\lor\\) 可分配
> > - \\(\\forall\\) 对 \\(\\lor\\)、\\(\\exists\\) 对 \\(\\land\\) **不可**分配（不同 \\(x\\) 可能不同）

---

#### 不定项选择题

> [!NOTE]
>
> **1\. \[真题\]**
>
> 设 \\(A=\\emptyset\\)，\\(B=\\mathcal{P}(\\mathcal{P}(A))\\)，则以下叙述正确的是（）
>
> (A) \\(\\emptyset\\in B\\)
>
> (B) \\(\\{\\emptyset,\\{\\emptyset,\\{\\emptyset\\}\\}\\}\\in B\\)
>
> (C) \\(\\{\\emptyset\\}\\in B\\)
>
> (D) \\(\\emptyset\\subseteq B\\)
>
> > **点击查看答案**
> >
> > **ACD**。\\(A=\\emptyset\\)，\\(\\mathcal{P}(A)=\\{\\emptyset\\}\\)，\\(\\mathcal{P}(\\mathcal{P}(A))=\\{\\emptyset,\\{\\emptyset\\}\\}=B\\)。 (A) \\(\\emptyset\\in B\\) ✓；(B) \\(\\{\\emptyset,\\{\\emptyset,\\{\\emptyset\\}\\}\\}\\) 不在 \\(B\\) 中 ✗；(C) \\(\\{\\emptyset\\}\\in B\\) ✓；(D) \\(\\emptyset\\subseteq B\\) ✓。
> >
> > > **如何理解A与D**
> > >
> > > - (A) \\(\\emptyset\\in B\\)：问的是 \\(\\emptyset\\) 是不是 \\(B\\) 的**元素**。\\(B=\\{\\emptyset,\\{\\emptyset\\}\\}\\)，\\(\\emptyset\\) 就在 \\(B\\) 里，所以成立
> > > - (D) \\(\\emptyset\\subseteq B\\)：问的是 \\(\\emptyset\\) 是不是 \\(B\\) 的**子集**。空集是任何集合的子集（\\(\\forall S,\\ \\emptyset\\subseteq S\\)），所以也成立

> [!NOTE]
>
> **2\. \[真题\]**
>
> 以下关于集合运算的说法正确的是（）
>
> (A) 若 \\(S\\cup T=S\\cup M\\)，则 \\(T=M\\)
>
> (B) 若 \\(S-T=\\emptyset\\)，则 \\(S=T\\)
>
> (C) 若 \\(S\\cap T=S\\cap M\\) 且 \\(S\\cup T=S\\cup M\\)，则 \\(T=M\\)
>
> (D) 若 \\(\\overline{S}\\cup T=E\\)（\\(E\\) 为全集），则 \\(S\\subseteq T\\)
>
> > **点击查看答案**
> >
> > **CD**。(A) 反例：\\(S=\\{1\\},T=\\{1,2\\},M=\\{2\\}\\)；(B) \\(S-T=\\emptyset\\) 只说明 \\(S\\subseteq T\\)；(C) 正确，集合相等可由上下界刻画；(D) 正确，\\(\\overline{S}\\cup T=E \\iff S\\subseteq T\\)。

> [!NOTE]
>
> **3\. \[真题\]**
>
> 以下函数中是单射函数的是（）
>
> (A) \\(f(x)=x+3\\)
>
> (B) \\(f(x)=(x+3)^2\\)
>
> (C) \\(f(x)=x^3+x\\)
>
> (D) \\(f(x)=|x+3|\\)
>
> > **点击查看答案**
> >
> > **AC**。(A) \\(x+3\\) 严格单调，单射；(B) \\((x+3)^2\\) 对称，\\(x=-2\\) 和 \\(x=-4\\) 同值；(C) \\(x^3+x\\) 严格单调（导数为 \\(3x^2+1\>0\\)），单射；(D) \\(|x+3|\\) 对称。
> >
> > > **单射 / 满射 / 双射**
> > >
> > > - **单射**：\\(f(x\_1)=f(x\_2)\\Rightarrow x\_1=x\_2\\)（不同输入不同输出）
> > > - **满射**：\\(\\forall y\\in Y,\\exists x\\in X,\\ f(x)=y\\)（值域=陪域）
> > > - **双射**：既单又满，可逆。

> [!NOTE]
>
> **4\. \[真题\]**
>
> 设 \\(A=\\{1,2,3,4,5,6,7,8,9,10\\}\\)，关系 \\(R=\\{(x,y)\\mid x+y=11\\}\\)，则 \\(R\\) 具有的性质是（）
>
> (A) 自反性
>
> (B) 反自反性
>
> (C) 对称性
>
> (D) 传递性
>
> > **点击查看答案**
> >
> > **BC**。(A) \\((1,1)\\notin R\\)，非自反；(B) \\(x+x=11\\) 在 \\(A\\) 中无解，故所有 \\((x,x)\\) 均不在 \\(R\\) 中，反自反；(C) \\(x+y=11\\iff y+x=11\\)，对称；(D) \\((1,10)\\in R,(10,1)\\in R\\) 但 \\((1,1)\\notin R\\)，非传递。

> [!NOTE]
>
> **5\. \[真题\]**
>
> 关于无向简单图 \\(G\\)，下列说法正确的是（）
>
> (A) 若边数 \\(e\>v-1\\)（\\(v\\) 为顶点数），则 \\(G\\) 一定连通
>
> (B) 完全图 \\(K\_v\\) 的边数为 \\(\\dfrac{v(v-1)}{2}\\)
>
> (C) 若 \\(G\\) 是二分图，则 \\(G\\) 不含奇圈
>
> (D) \\(v=4\\) 的完全图有 \\(11\\) 个非同构子图（不含空图）
>
> > **点击查看答案**
> >
> > **BC**。
> >
> > (A) 反例：\\(v=5\\)，在 4 个顶点上取 \\(K\_4\\) 的 5 条边，剩余 1 个顶点孤立，此时 \\(e=5\>4=v-1\\) 但不连通；
> >
> > (B) 完全图每对顶点恰有一条边，共 \\(C\_v^2=v(v-1)/2\\) 条；
> >
> > (C) 二分图顶点可二染色，边只能连接异色顶点。假设含奇圈 \\(v\_1v\_2\\cdots v\_{2k+1}v\_1\\)，从 \\(v\_1\\) 出发交替染色，绕一圈后 \\(v\_1\\) 同时被染两种颜色，矛盾。故二分图不含奇圈，正确；
> >
> > (D) 错。11 是 \\(|V|=4\\) 的生成子图数（按边数 0\~6: 1,1,2,3,2,1,1），但子图可取更少顶点：\\(|V|=1\\) 有 1 个，\\(|V|=2\\) 有 2 个，\\(|V|=3\\) 有 4 个，加空图共 \\(1+1+2+4+11=19\\) 个（不含空图 18 个）。

> [!NOTE]
>
> **6\. \[真题\]**
>
> 下列逻辑关系式中正确的是（）
>
> (A) \\(\\forall x(A(x)\\to B(x))\\to(\\forall x A(x)\\to\\forall x B(x))\\)
>
> (B) \\((\\forall x A(x)\\to\\forall x B(x))\\to\\forall x(A(x)\\to B(x))\\)
>
> (C) \\(\\exists x(A(x)\\land B(x))\\to\\exists x A(x)\\land\\exists x B(x)\\)
>
> (D) \\(\\exists x A(x)\\land\\exists x B(x)\\to\\exists x(A(x)\\land B(x))\\)
>
> > **点击查看答案**
> >
> > **AC**。(A) 全称实例化+假言推理，正确；(B) 方向不成立；(C) \\(\\exists x(A\\land B)\\) 蕴含各自存在，正确；(D) 方向不成立，两存在量词可能不同。

---

#### 计算题

> [!NOTE]
>
> **1\. \[真题\]**
>
> 设 \\(A=\\{0,1\\}\\)，\\(B=\\{1,2\\}\\)，求 \\(A^2\\times B\\)。
>
> > **点击查看答案**
> >
> > \\(A^2=A\\times A=\\{(0,0),(0,1),(1,0),(1,1)\\}\\)， \\(A^2\\times B=\\{(0,0,1),(0,0,2),(0,1,1),(0,1,2),(1,0,1),(1,0,2),(1,1,1),(1,1,2)\\}\\)，共 8 个有序三元组。
> >
> > > **笛卡尔积**
> > >
> > > \\(A\\times B=\\{(a,b)\\mid a\\in A,\\ b\\in B\\}\\)，即从 \\(A\\) 和 \\(B\\) 各取一元素组成有序对。
> > >
> > > 基数：\\(|A\\times B|=|A|\\cdot|B|\\)。推广：\\(A\_1\\times A\_2\\times\\cdots\\times A\_n\\) 的元素是有序 \\(n\\) 元组，基数等于各集合基数的乘积。

> [!NOTE]
>
> **2\. \[真题\]**
>
> 求命题公式 \\((P\\to\\neg Q)\\to R\\) 的主析取范式和主合取范式。
>
> > **点击查看答案**
> >
> > \\((P\\to\\neg Q)\\to R\\)
> >
> > \\(\\iff \\neg(\\neg P\\lor\\neg Q)\\lor R\\)
> >
> > \\(\\iff (P\\land Q)\\lor R\\)
> >
> > 展开为小项：\\((P\\land Q\\land R)\\lor(P\\land Q\\land\\neg R)\\lor(P\\land R)\\lor(\\neg P\\land R)\\) \\(=m\_7\\lor m\_6\\lor(m\_7\\lor m\_3)\\lor(m\_3\\lor m\_1)\\) \\(=m\_1\\lor m\_3\\lor m\_6\\lor m\_7\\)
> >
> > 主合取范式：\\(M\_0\\land M\_2\\land M\_4\\land M\_5\\)。

---

#### 证明题

> [!NOTE]
>
> **1\. \[真题\]**
>
> 证明：\\((A-B)-C=A-(B\\cup C)\\)。
>
> > **点击查看答案**
> >
> > \\\[ \\begin{aligned} (A-B)-C &= (A\\cap\\overline{B})\\cap\\overline{C} \\\\ &= A\\cap(\\overline{B}\\cap\\overline{C}) \\\\ &= A\\cap\\overline{B\\cup C} \\\\ &= A-(B\\cup C) \\end{aligned} \\\]

> [!NOTE]
>
> **2\. \[真题\]**
>
> 证明：对任意大于 \\(1\\) 的自然数 \\(n\\)，
>
> \\\[\\left(1+\\frac{1}{3}\\right)\\cdot\\left(1+\\frac{1}{5}\\right)\\cdots\\left(1+\\frac{1}{2n-1}\\right)\\ge\\frac{\\sqrt{2n+1}}{2}\\\]
>
> > **点击查看答案**
> >
> > **数学归纳法**。
> >
> > **基础** \\(n=2\\)：
> >
> > \\\[(1+\\frac{1}{3})=\\frac{4}{3},\\qquad \\frac{\\sqrt{5}}{2}\\approx1.118,\\qquad \\frac{4}{3}\>1.118 \\;\\Rightarrow\\; \\text{成立。}\\\]
> >
> > **归纳假设**：设 \\(n=k\\) 时成立，即
> >
> > \\\[\\left(1+\\frac{1}{3}\\right)\\cdots\\left(1+\\frac{1}{2k-1}\\right)\\ge\\frac{\\sqrt{2k+1}}{2}\\\]
> >
> > **归纳递推** \\(n=k+1\\)：
> >
> > \\\[ \\begin{align\*} \\text{左边} &= \\left\[\\left(1+\\frac{1}{3}\\right)\\cdots\\left(1+\\frac{1}{2k-1}\\right)\\right\]\\cdot\\left(1+\\frac{1}{2k+1}\\right) \\\\ &\\ge \\frac{\\sqrt{2k+1}}{2}\\cdot\\frac{2k+2}{2k+1} \\qquad\\text{（归纳假设）}\\\\ &= \\frac{\\sqrt{2k+1}}{2}\\cdot\\frac{2(k+1)}{2k+1} \\\\ &= \\frac{k+1}{2k+1}\\sqrt{2k+1} \\end{align\*} \\\]
> >
> > 只需证 \\(\\displaystyle\\frac{k+1}{2k+1}\\sqrt{2k+1}\\ge\\frac{\\sqrt{2k+3}}{2}\\)，两边平方等价于：
> >
> > \\\[ \\begin{align\*} \\frac{(k+1)^2}{(2k+1)^2}\\cdot(2k+1) &\\ge \\frac{2k+3}{4} \\\\ \\frac{(k+1)^2}{2k+1} &\\ge \\frac{2k+3}{4} \\\\ 4(k^2+2k+1) &\\ge (2k+1)(2k+3) \\\\ 4k^2+8k+4 &\\ge 4k^2+8k+3 \\\\ 4 &\\ge 3 \\end{align\*} \\\]
> >
> > 故 \\(n=k+1\\) 时也成立。由数学归纳法，原不等式对任意 \\(n\>1\\) 成立。

---

### 模拟卷(来自复习课)

---