习题 5 · 离散数学

本题干的题目逐字取自原书 PDF 第 143–147 页（印刷 p128–p132），解答逐字取自答案书第 5 章「习题解答与分析」（PDF p97–p100，印刷 p85–p88）。题干与答案书原解答均不进入折叠块；只有 AI 补充的额外说明才放进 :::details，且标题标注「AI 生成，非原书」。该节答案书原解答完整，无需 AI 兜底。

5.1 从下面各题的备选答案中选出一个正确的答案.

(1) 设 X=\{a,b,c,d\}，Y=\{1,2,3\}，f=\{\langle a,1\rangle,\langle b,2\rangle,\langle c,3\rangle\}，则 f 是

A. 从 X 到 Y 的二元关系，但不是从 X 到 Y 的函数

B. 从 X 到 Y 的函数，但不是满射，也不是单射

C. 从 X 到 Y 的满射，但不是单射

D. 从 X 到 Y 的双射

(2) 下面定义中的哪些 f 是从实数集 \mathbf{R} 到 \mathbf{R} 的双射函数？

A. f(x)=1，x>0；f(x)=-1，x\leqslant 0

B. f(x)=\ln x，x>0

C. f(x)=1/(x^3+8)，x\neq -2

D. f(x)=x^3+8

解答　(1) A.　(2) D.

说明　(1) 因为 \mathrm{dom}f=\{a,b,c\}\neq X.

(2) A 中函数不是单射的，因为 f(2)=f(1)；B 和 C 中函数的定义域不是实数集合 \mathbf{R}，而是实数集合的真子集；D 中函数满足要求.

5.2 设 f:\mathbf{Z}\times\mathbf{Z}\to\mathbf{Z}，\mathbf{Z} 为整数集，\forall\langle n,k\rangle\in \mathbf{Z}\times\mathbf{Z}，f(\langle n,k\rangle)=n^2k，求 f 的值域.

解答　\mathrm{ran}f=\{n^2k\mid n,k\in\mathbf{Z}\}=\mathbf{Z}.

5.3 设 A=\{a,b\}，B=\{0,1,2\}，计算 B^A=\{f\mid f:A\to B\}.

解答　B^A=\{f_1,f_2,\cdots,f_9\}，其中：

f_1=\{\langle a,0\rangle,\langle b,0\rangle\},\quad f_2=\{\langle a,0\rangle,\langle b,1\rangle\},\quad f_3=\{\langle a,0\rangle,\langle b,2\rangle\},

f_4=\{\langle a,1\rangle,\langle b,0\rangle\},\quad f_5=\{\langle a,1\rangle,\langle b,1\rangle\},\quad f_6=\{\langle a,1\rangle,\langle b,2\rangle\},

f_7=\{\langle a,2\rangle,\langle b,0\rangle\},\quad f_8=\{\langle a,2\rangle,\langle b,1\rangle\},\quad f_9=\{\langle a,2\rangle,\langle b,2\rangle\}.

5.4 设 f:\mathbf{R}\to\mathbf{R}，f(x)=x^2-3x+2，其中 \mathbf{R} 为实数集，计算以下各小题.

(1) f(5).

(2) f^{-1}(\{-6\}).

(3) f(\{1,3\}).

解答　(1) f(5)=5^2-3\times 5+2=12.

(2) f^{-1}(\{-6\})=\{x\mid f(x)=-6\}，由于 f(x) 的最小值是 -1/4，因此 f^{-1}(\{-6\})=\varnothing.

(3) f(\{1,3\})=\{f(1),f(3)\}=\{0,2\}.

5.5 A=\{a_1,a_2,a_3\}，B=\{b_1,b_2,b_3,b_4\}，\sigma 为从 A 到 B 的函数，\sigma=\{\langle a_1,b_1\rangle,\langle a_2,b_4\rangle,\langle a_3,b_2\rangle\}，说明 \sigma 是否为单射、满射和双射的.

解答　\sigma 是单射，不是满射和双射.

5.6 设 A=\{a,b,c\}，R=\{\langle a,b\rangle,\langle b,a\rangle\}\cup I_A 是 A 上的等价关系，设自然映射 g:A\to A/R，求 g(a).

解答　g(a)=[a]=\{a,b\}.

5.7 设 f:\mathbf{N}\times\mathbf{N}\to\mathbf{N}，f(\langle x,y\rangle)=x+y+1，

(1) 说明 f 是否为单射和满射. 如果不是请说明理由.

(2) 令 A=\{\langle x,y\rangle\mid x,y\in \mathbf{N} 且 f(\langle x,y\rangle)=3\}，求 A.

(3) 令 B=\{f(\langle x,y\rangle)\mid x,y\in\{1,2,3\} 且 x=y\}，求 B.

解答　(1) 不是单射，因为 f(\langle 1,2\rangle)=f(\langle 2,1\rangle)；不是满射，因为 0\notin \mathrm{ran}f.

(2) 对于任意自然数 x,y，\langle x,y\rangle\in A\Leftrightarrow x+y+1=3\Leftrightarrow x+y=2，于是 A=\{\langle 1,1\rangle,\langle 2,0\rangle,\langle 0,2\rangle\}.

(3) 对于任意自然数 x,y，f(\langle x,y\rangle)\in B\Leftrightarrow x=y=1,2,3，B=\{1+1+1,2+2+1,3+3+1\}=\{3,5,7\}.

5.8 指出下列函数中哪些是双射的？其中 \mathbf{R} 是实数集，\mathbf{N} 为自然数集.

(1) f:\mathbf{R}\to\mathbf{R}，f(x)=x^2-x.

(2) f:\mathbf{R}\to\mathbf{R}，f(x)=x^3.

(3) f:\mathbf{N}\to\mathbf{N}，f(x)=x+5.

(4) f:\mathbf{R}\to\mathbf{R}^+，f(x)=2^x，\mathbf{R}^+=\{x\mid x\in \mathbf{R}\wedge x>0\}.

(5) f:\mathbf{N}\to\mathbf{N}，f(x)=2x.

(6) f:\mathbf{N}\to\mathbf{N}，f(x)=|x|.

解答　(2)，(4)和(6)为双射.

说明　对于实数区间上的函数，如果在区间上是单调的，那么该函数是单射的. 例如(2)和(4)中的函数是单调的，因此是单射的；(1)中的函数不是单调的，因此不是单射的. 对于满射性的判断，则需要考虑 \mathrm{ran}f. 例如(3)中的函数，0\notin \mathrm{ran}f，因此不是满射的. 对于(5)中的函数，1\notin \mathrm{ran}f. 5.9 设 f:\mathbf{Z}^2\to\mathbf{Z}，f(\langle n,k\rangle)=n^2k，其中 \mathbf{Z} 为整数集.

(1) f 是满射的吗？为什么？

(2) f 是单射的吗？为什么？

(3) 求 f^{-1}(\{0\}).

(4) 求 f^{-1}(\mathbf{N}).

(5) 求 f(\mathbf{Z}\times\{1\}).

解答　(1) f 是满射，当 n=1 时，f(\langle n,k\rangle)=k，k 可以是任意整数.

(2) f 不是单射，因为 f(\langle 2,1\rangle)=f(\langle -2,1\rangle).

(3) f^{-1}(\{0\})=(\mathbf{Z}\times\{0\})\cup(\{0\}\times\mathbf{Z}).

(4) f^{-1}(\mathbf{N})=\mathbf{Z}\times\mathbf{N}.

(5) f(\mathbf{Z}\times\{1\})=\{n^2\mid n\in\mathbf{N}\}.

5.10 设 f:\mathbf{R}\to\mathbf{R}，\mathbf{R} 为实数集，对下面各个 f，判断它是否为单射、满射或双射的. 如果它不是单射的，给出 x_1 和 x_2，使得 x_1\neq x_2 但 f(x_1)=f(x_2). 如果它不是满射的，计算 f(\mathbf{R}).

(1) f(x)=x^2.

(2) f(x)=E[x]，其中 E[x] 表示小于等于 x 的最大整数.

解答　(1) f 不是单射，因为 f(1)=f(-1)；f 不是满射，\mathrm{ran}f=\mathbf{R}^+\cup\{0\}.

(2) f 不是单射，因为 f(0.2)=f(0.3)=0；不是满射，\mathrm{ran}f=\mathbf{Z}.

5.11 试给出一个单射而非满射的函数.

解答　f:\mathbf{N}\to\mathbf{N}，f(x)=2x.

说明　对于有穷集合 A，任何 A 上的单射函数，同时也是 A 上的满射函数，因此也是双射函数；为了构造集合上的单射而非满射的函数，或者构造集合上的满射而非单射的函数，只能选择无穷集合. 最简单的无穷集合是自然数集合.

5.12 设 f:\mathbf{N}\to\mathbf{N}\times\mathbf{N}，f(n)=\langle n,n+1\rangle.

(1) 说明 f 是否为单射和满射，并说明理由.

(2) f 的反函数是否存在？如果存在，求出这个反函数.

(3) 求 \mathrm{ran} f.

解答　(1) f 是单射，当 m\neq n 时 \langle n,n+1\rangle\neq\langle m,m+1\rangle；f 不是满射，\langle 0,0\rangle\notin\mathrm{ran}f.

(2) f 不存在反函数.

(3) \mathrm{ran}f=\{\langle n,n+1\rangle\mid n\in\mathbf{N}\}.

5.13 设 f:\mathbf{R}\times\mathbf{R}\to\mathbf{C}，f(\langle x,y\rangle)=x+y\mathrm{i},\mathrm{i}^2=-1，说明 f 是否为单射、满射、双射的，计算 f^{-1}(\{4+2\mathrm{i}\}).

解答　f 是双射，且 f^{-1}(\{4+2\mathrm{i}\})=\{\langle 4,2\rangle\}.

5.14 (1) 确定函数 f:\mathbf{N}\times\mathbf{N}\to\mathbf{N}，f(\langle x,y\rangle)=xy 是否为单射、满射、双射的，如果不是请说明理由. 计算 f(\mathbf{N}\times\{1\})，f^{-1}(\{0\}).

(2) 设 f:\mathbf{N}\times\mathbf{N}\to\mathbf{N}，f(\langle x,y\rangle)=|x-y|，说明 f 有什么性质(单射、满射、双射)，计算 f(\mathbf{N}\times\{0\}) 和 f^{-1}(\{0\}).

解答　(1) f 不是单射，因为 f(\langle 1,2\rangle)=f(\langle 2,1\rangle)；是满射，不是双射.

f(\mathbf{N}\times\{1\})=\mathbf{N},\quad f^{-1}(\{0\})=(\mathbf{N}\times\{0\})\cup(\{0\}\times\mathbf{N})

(2) f 不是单射，因为 f(\langle 1,2\rangle)=f(\langle 2,1\rangle)；f 是满射，不是双射.

f(\mathbf{N}\times\{0\})=\mathbf{N},\quad f^{-1}(\{0\})=\{\langle n,n\rangle\mid n\in\mathbf{N}\}

5.15 设 R[t] 为 t 的实系数多项式的集合，R_n[t]\subseteq R[t]，n\in \mathbf{N}，R_n[t] 为 t 的 n 次实系数多项式的集合. 定义函数 f:R[t]\to R[t]，f(g(t))=g^2(t). 求 f(R_0[t])，f^{-1}(\{t^2+2t+1\})，f^{-1}(f(\{t-1,t^2-1\})).

解答　f(R_0[t])=\mathbf{R}^+\cup\{0\}.

f^{-1}(\{t^2+2t+1\})=\{t+1,-t-1\},

f^{-1}(f(\{t-1,t^2-1\}))=\{t-1,1-t,t^2-1,1-t^2\}.

5.16 设 f:\mathbf{N}\times\mathbf{N}\to\mathbf{N}，f(\langle x,y\rangle)=x^2+y^2，说明 f 是否为单射的、满射的. 计算 f^{-1}(\{0\})，f(\{\langle 0,3\rangle,\langle 1,2\rangle\}).

解答　f 不是单射的，f 不是满射的，则

f^{-1}(\{0\})=\{\langle 0,0\rangle\},\quad f(\{\langle 0,3\rangle,\langle 1,2\rangle\})=\{5,9\}

5.17 设 \mathbf{R} 为实数集，f:\mathbf{R}\to\mathbf{R}，f(x)=x^2-x+2，g:\mathbf{R}\to\mathbf{R}，g(x)=x-3.

(1) 求 f\circ g，g\circ f.

(2) 如果 f 和 g 存在反函数，求出它们的反函数.

解答　(1) f\circ g:\mathbf{R}\to\mathbf{R}，f\circ g(x)=x^2-x-1，g\circ f:\mathbf{R}\to\mathbf{R}，g\circ f(x)=x^2-7x+14.

(2) g 存在反函数，g^{-1}:\mathbf{R}\to\mathbf{R}，g^{-1}(x)=x+3.

5.18 设 f:\mathbf{Z}\to\mathbf{Z}，f(x)=x+5，其中 \mathbf{Z} 为整数集.

(1) 说明 f 是否为满射和单射的.

(2) f^{-1} 还是函数吗？若是，写出 f^{-1} 的函数表达式；若不是，请说出理由.

解答　(1) f 是满射的，也是单射的.

(2) f^{-1} 是函数，f^{-1}:\mathbf{Z}\to\mathbf{Z}，f^{-1}(x)=x-5.

5.19 设 \mathbf{R} 为实数集，映射 \sigma,\tau 满足 \sigma:\mathbf{R}\to\mathbf{R}，\sigma(x)=x^2+2x+1，\tau:\mathbf{R}\to\mathbf{R}，\tau(x)=x/2.

(1) 求 \tau\circ\sigma，\sigma\circ\tau.

(2) 对于 \tau,\sigma 中的双射函数求反函数.

解答　(1) \tau\circ\sigma:\mathbf{R}\to\mathbf{R}，\tau\circ\sigma(x)=\dfrac{1}{4}x^2+x+1，\sigma\circ\tau:\mathbf{R}\to\mathbf{R}，\sigma\circ\tau(x)=\dfrac{1}{2}x^2+x+\dfrac{1}{2}.

(2) \tau^{-1}:\mathbf{R}\to\mathbf{R}，\tau^{-1}(x)=2x.

5.20 设 A，B 为有限集，且 |A|=m，|B|=n，如果从 A 到 B 存在单射、满射或双射函数，那么 m 与 n 应该满足的条件是什么？

解答　存在从 A 到 B 的单射函数当且仅当 m\leqslant n；存在从 A 到 B 的满射函数当且仅当 m\geqslant n；存在从 A 到 B 的双射函数当且仅当 m=n.

5.21 设 \sigma:\mathbf{R}\to\mathbf{R}，\sigma(x)=\begin{cases}x^2 & x\geqslant 3\\-2 & x<3\end{cases}，\tau:\mathbf{R}\to\mathbf{R}，\tau(x)=x+2，求 \sigma\circ\tau，\tau\circ\sigma.

解答

\sigma\circ\tau(x)=\begin{cases}x^2+2&x\geqslant 3\\0&x<3\end{cases},\qquad \tau\circ\sigma(x)=\begin{cases}(x+2)^2&x\geqslant 1\\-2&x<1\end{cases}

注意：对于分段函数，在求复合函数时，可能分段点会发生改变，如本题中的 \tau\circ\sigma 的分段点不是 3，而是 1. 5.22 对于以下给定的每组集合 A 和 B，构造从 A 到 B 的双射函数.

(1) A=2\mathbf{Z}=\{2k\mid k\in \mathbf{Z}\}，B=\mathbf{N}，其中 \mathbf{Z} 为整数集，\mathbf{N} 为自然数集.

(2) A=\mathbf{R}，B=(0,+\infty)，其中 \mathbf{R} 为实数集.

(3) A=P(\{a,b\})，B=\{0,1\}^{\{a,b\}}，其中 A 为 \{a,b\} 的幂集，B=\{f\mid f:\{a,b\}\to\{0,1\}\}.

解答　(1) f:2\mathbf{Z}\to\mathbf{N}，

f(x)=\begin{cases}x&x\geqslant 0\\|x|-1&x<0\end{cases}

(2) f:\mathbf{R}\to\mathbf{R}^+，f(x)=\mathrm{e}^x.

(3) f:P(\{a,b\})\to\{0,1\}^{\{a,b\}}，f(T)=\chi_T，其中 \chi_T 为 T 的特征函数.

说明　如果构造两个实数区间之间的双射函数，一般可以选择直线方程或者其他适当的严格单调函数；如果构造一个集合到自然数集合的双射函数，一般将这个集合的元素排成一个线序，然后将最小元与 0 对应，后面的元素顺序与自然数建立对应关系.

5.23 (1)

f\circ g(x)=\begin{cases}x/2&x\geqslant 6,\ x\text{ 为偶数}\\3&x\geqslant 5\text{ 且 }x\text{ 为奇数},x=0,2\\0&x=4\\1&x=1\\2&x=3\end{cases}

f\circ g 不是单射，是满射.

(2) f\circ g(A)=\{g(f(0)),g(f(1)),g(f(2))\}=\{1,3\}

(f\circ g)^{-1}(B)=\{x\mid g(f(x))\in\{0,1,5,6\}\}=\{1,4,10,12\}

\* 5.24 任取 y\in A，必有 x\in A 使得 \langle x,y\rangle\in f，由题设有 \langle x,y\rangle\in f\circ f，因此存在 z\in A 使得 \langle x,z\rangle\in f 且 \langle z,y\rangle\in f. 由于 f(x) 是唯一的，因此 y=z，从而 \langle y,y\rangle\in f. 由于 y 的任意性，知 I_A\subseteq f.

任取 \langle x,y\rangle\in f，根据上面的证明，I_A\subseteq f，有 \langle x,x\rangle\in f，因为 f(x) 是唯一的，从而得到 x=y. 这就证明了 f\subseteq I_A. 综合上述命题得证.

\* 5.25 假设 A_1,A_2\in P(A)，A_1\neq A_2，不妨设存在 x，使得 x\in A_1\wedge x\notin A_2，因此 f(x)\in f(A_1) 且由 f 的单射性知 f(x)\notin f(A_2). 于是 f(A_1)\neq f(A_2). 从而 G(A_1)\neq G(A_2).

\* 5.26 (1) 任取 f\in B^A，\forall x\in A，f(x)=f(x)，由于偏序 \preccurlyeq 的自反性，f(x)\preccurlyeq f(x)，于是 fRf 成立. 对任意 f,g\in B^A，\forall x\in A，则

fRg\wedge gRf\Rightarrow f(x)\preccurlyeq g(x)\wedge g(x)\preccurlyeq f(x)\Rightarrow f(x)=g(x)

于是 f=g. 对任意 f,g,h\in B^A，\forall x\in A，则

fRg\wedge gRh\Rightarrow f(x)\preccurlyeq g(x)\wedge g(x)\preccurlyeq h(x)\Rightarrow f(x)\preccurlyeq h(x)

从而得到 fRh. 综合上述，R 具有自反、反对称、传递性，是偏序关系.

(2) 充要条件是：偏序集 \langle B,\preccurlyeq\rangle 存在最大元. 设 B 的最大元为 b，那么 B^A 上的最大元为 f:A\to B，f(x)=b.

\* 5.27 (1) \forall x,y\in\mathbf{N}，xR_iy\Leftrightarrow f_i(x)=f_i(y)，i=1,2,3,4，于是

xR_1y\Leftrightarrow x=y

xR_2y\Leftrightarrow x\text{ 与 }y\text{ 具有相同的奇偶性}

xR_3y\Leftrightarrow x\equiv y(\mathrm{mod}\ 3)

xR_4y\Leftrightarrow x\equiv y(\mathrm{mod}\ 6)

从而得到

\mathbf{N}/R_1=\{\{n\}\mid n\in\mathbf{N}\}

\mathbf{N}/R_2=\{2\mathbf{N},\mathbf{N}-2\mathbf{N}\}

\mathbf{N}/R_3=\{3\mathbf{N},3\mathbf{N}+1,3\mathbf{N}+2\}

\mathbf{N}/R_4=\{6\mathbf{N},6\mathbf{N}+1,6\mathbf{N}+2,6\mathbf{N}+3,6\mathbf{N}+4,6\mathbf{N}+5\}

其中

k\mathbf{N}=\{kn\mid n\in\mathbf{N}\},k\mathbf{N}+i=\{kn+i\mid n\in\mathbf{N}\}

(2) 哈斯图如图 5.1 所示.

原书图5.1

图 5.1

(3) f_1(H)=H，

f_2(H)=\{0\},

f_3(H)=\{0,1,2\},

f_4(H)=\{0,2,4\}.

\* 5.28 任取 \langle x,y\rangle，则

\langle x,y\rangle\in I_A\circ f\Leftrightarrow\exists t(\langle x,t\rangle\in I_A\wedge\langle t,y\rangle\in f)

\Rightarrow\langle x,x\rangle\in I_A\wedge\langle x,y\rangle\in f\Rightarrow\langle x,y\rangle\in f

任取 \langle x,y\rangle，则

\langle x,y\rangle\in f\Rightarrow\langle x,x\rangle\in I_A\wedge\langle x,y\rangle\in f\Rightarrow\langle x,y\rangle\in I_A\circ f

因此 I_A\circ f=f. 同理可证 f\circ I_B=f.

解读：第 5 章的题几乎都围绕同一个判据展开——单射看「不同自变量是否给出相同函数值」，满射看「值域是否等于陪域」，双射两者兼备；遇到分段函数复合时，一定要重新算分段点，不能沿用原函数的分段点。