算法导论 B.2 Exercises 答案

B.2-1

首先需要证明 $\subseteq$ 满足自反性，反对称性和传递性。

自反性：根据子集的定义，集合 $S$ 的子集可以是自身，即 $S\subseteq S$，因此自反性成立。

反对称性：假设现在有两个集合 $A,B$。关系 $A\subseteq B$ 意味着 $\mathrm{\forall }x\in A,x\in B$ 成立。关系 $B\subseteq A$ 意味着 $\mathrm{\forall }x\in B,x\in A$ 成立。如果 $A\subseteq B,B\subseteq A$ 成立，那么说明 $A=B$，因此反对称性成立。

传递性：假设现在有集合 $A,B,C$ 满足 $A\subseteq B,B\subseteq C$，根据子集的定义，$\mathrm{\forall }x\in A,x\in B$ 均成立，同时 $\mathrm{\forall }x\in B,x\in C$ 成立。由于 $A$ 是 $B$ 的一部分，因此有 $\mathrm{\forall }x\in A,x\in C$ 成立，即 $A\subseteq C$。因此传递性成立。

因此 $\subseteq$ 是偏序。

考虑 $\mathbb{Z}$ 上的两个子集 $A=\{0,1\},B\{1,2\}$。根据子集的定义，$A\subseteq B,B\subseteq A$ 均不成立。也是就说在 $\subseteq$ 运算上没有定义，因此 $\subseteq$ 不是全序。

B.2-2

首先需要证明这种运算满足自反性，对称性和传递性。

自反性：对于所有正整数 $a,n,a-a=0\cdot n$ 必定成立，因此自反性成立。

对称性：对于所有正整数 $a,b,n$，如果存在 $p$ 使得 $a-b=pn$ 成立，那么就有 $b-a=(-p)n$，因此对称性成立。

传递性：对于所有正整数 $a,b,c,n$，如果存在 $p,q$ 使得 $a-b=pn,b-c=qn$ 成立，那么有 $a-c=(p+q)n$ 成立，由此构造出了一个新整数 $p+q$。因此传递性成立。

这一种划分，将 $\mathbb{Z}$ 划分成了 $n$ 个等价类。每个等价类中的数两两都关于模 $n$ 同余，即差值都是 $n$ 的倍数。

B.2-3

a

$S=\{1,2,3\},R=\{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)\}$

b

$S=\{1,2,3\},R=\{(1,1),(2,2),(3,3),(1,2),(1,3),(2,3)\}$

c

$S=\{1,2,3\},R=\varnothing$

B.2-4

$R$ 是 $S\times S$ 上的一个等价关系，说明 $R$ 具有对称性。

对称性说明，对于所有关系 $(a,b)\in R$，都有 $(b,a)\in R$。

现在 $R$ 同时具有反对称性，说明对于关系 $(a,b)\in R$，都有 $a=b$。

这说明 $S$ 关于 $R$ 划分出的等价类只能是单元集。

B.2-5

不正确。如题目 B-2.3c 构造出的一组关系。因为传递性和对称性的定义都是：如果 $(?,?)$ 存在，那么 $(?,?)$ 存在。而自反性则是确认 $(x,x)$ 关系都存在。