离散数学

A（真）。\(\exists x(x>0 \land x^2=1)\)，取 \(x=1\) 即可满足。

C（4）。\(A=\{\emptyset, \{\emptyset\}\}\) 有 2 个元素，\(|\mathcal{P}(A)|=2^2=4\)。

D（既非单射也非满射）。\(f(x)=x^2\) 在 \(\mathbb{Z}\) 上：\(f(1)=f(-1)=1\) 非单射；负数不在值域中，非满射。

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 是二阶元）。

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。

A（所有顶点的度数均为偶数）。欧拉图的充要条件：连通且每个顶点度数为偶数。

B（\((P\land Q)\to(P\lor Q)\)）。这是永真式：如果 \(P\land Q\) 成立则 \(P\lor Q\) 必成立。其余选项均非永真。

ABC。\(\mathbb{Z},\mathbb{Q}\) 对加法构成群；偶数集也是加法子群。\(\mathbb{N}\) 无负元（逆元）。

ABCD。(A) 空集是任何集合的子集；(B) 幂集单调性；(C) 幂集保交(不保并)；(D) \(A\subseteq A\) 恒成立，故 \(A\in\mathcal{P}(A)\)。

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\)，满射时可取等。

ABCD。均为关系性质的等价刻画。

ABD。(A)(B) 同构定义保证；(C) 度序列相同非充分条件（存在不同构但度序列相同的图）；(D) ✓，生成子图 (spanning subgraph) 的定义就是 \(V_1=V_2\)，即包含原图所有顶点，只是边集可以是原边集的子集。

ABCD。(A)(B)(C) 为谓词逻辑基本等值式；(D) 也是正确的等值式。

先写出集合形式：

(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)\)

(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)\)

(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)\)

反证法。假设这两个奇度顶点 \(u\) 和 \(v\) 之间没有路径（不连通），那么它们必然分属两个不同的连通分支。

单独看 \(u\) 所在的连通分支：在这个分支里，除了 \(u\) 的度数为奇数，其余顶点度数全都是偶数（因为题目说整个图只有 \(u\) 和 \(v\) 两个奇度点，而 \(v\) 在另一个分支）。

但根据握手定理，任何图中奇度顶点的个数必须是偶数。这个分支只有 \(u\) 一个奇度顶点，矛盾。同理 \(v\) 所在的分支也会推出矛盾。所以假设不成立，\(u\) 和 \(v\) 必在同一连通分支中，即它们之间一定连通。

数学归纳法。

\(n=0\)：\(4^1+3^2=4+9=13\)，成立。

设 \(n=k\) 成立：\(4^{2k+1}+3^{k+2}=13m\)。

\(n=k+1\)：

能被 13 整除。得证。

B（\(A(1)\lor A(2)\)）。论域有限时，\(\exists x A(x)\) 等价于对各元素的析取。

C（8）。从 \(A\)（3 元素）到 \(B\)（2 元素）的函数个数为 \(2^3=8\)。

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 个。

A（\(G\) 连通且所有顶点度数为偶数）。

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\)），上确界不存在。

C（\(\exists x(A(x)\land B(x))\iff\exists x A(x)\land\exists x B(x)\)）。方向 \(\to\) 成立，但 \(\gets\) 不成立（两个存在量词可能指不同 \(x\)）。

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\) ✓。

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\)。

AC。(A) \(x+3\) 严格单调，单射；(B) \((x+3)^2\) 对称，\(x=-2\) 和 \(x=-4\) 同值；(C) \(x^3+x\) 严格单调（导数为 \(3x^2+1>0\)），单射；(D) \(|x+3|\) 对称。

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\)，非传递。

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 个）。

AC。(A) 全称实例化+假言推理，正确；(B) 方向不成立；(C) \(\exists x(A\land B)\) 蕴含各自存在，正确；(D) 方向不成立，两存在量词可能不同。

\(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 个有序三元组。

\((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\)。

数学归纳法。

基础 \(n=2\)：

归纳假设：设 \(n=k\) 时成立，即

归纳递推 \(n=k+1\)：

只需证 \(\displaystyle\frac{k+1}{2k+1}\sqrt{2k+1}\ge\frac{\sqrt{2k+3}}{2}\)，两边平方等价于：

故 \(n=k+1\) 时也成立。由数学归纳法，原不等式对任意 \(n>1\) 成立。