算法导论B.3 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 960 阅读时长 ≈ 1 分钟

B.3-1

a

由于函数\(f\)是单射的，那么对于\(a\neq a',f(a)\neq f(a')\)均成立。因此\(|A|=|f(A)|\)，\(f(A)\)是值域。对于陪域\(B\)，

  • 如果\(\exists y\in B,\nexists x\in A\)使得\(y=f(x)\)，那么说明\(|f(A)|<|B|\)。
  • 否则，说明\(|f(A)|=|B|\)。

最终有\(|A|\le |B|\)。

b

由于函数\(f\)是满射的，那么对于\(\forall y \in B,\exists x \in A,y=f(x)\)成立。因此\(|B|=|f(A)|\)。对于定义域\(A\)，

  • 如果\(\exists x,x'\in A,x'\neq x,f(x)=f(x')\)，那么说明\(|A|>|f(A)|\)。
  • 否则，说明\(|A|=|f(A)|\)。

最终有\(|A|\ge |B|\)。

B.3-2

\(f(x)=x+1\)不是从\(\mathbb{N}\)到\(\mathbb{N}\)的满射，因为存在\(0\in \mathbb{N}\)，无法找到\(x\in \mathbb{N}\)使得\(x+1=0\)。但它是从\(\mathbb{Z}\)到\(\mathbb{Z}\)的满射。

B.3-3

给定一个二元关系\(R\)，那么可以定义\((a,b)\in R^{-1}\)当且仅当\((b,a)\in R\)。并且二元关系\(R,R'\)的定义域和值域恰好是交换后的。

\(\star\) B.3-4

考虑将\(\mathbb{Z\times Z}\)视为平面直角坐标系上的点，那么可以如下设计映射\(f:\mathbb{Z\rightarrow Z\times Z}\)。

假设\(f(0)=(0,0)\)。那么一开始先往上走\(1\)步，再往右走\(1\)步，接下来往下走\(3\)步，再往左走\(3\)步，再往上走\(5\)步……那么\(\mathbb{Z}\)对应的是步数，\(\mathbb{Z\times Z}\)则是走到的顶点。

如果对应的步数是负数，那么仅需要将点\((x,y)\)中心对称到\((-x,-y)\)则是所求的点。

通过这个过程不难发现，映射\(f\)中，点和步数是一一对应的，也就是双射的。