算法导论B.2 Exercises 答案

B.2-1

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

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

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

传递性：假设现在有集合$A,B,C$满足$A\subseteq B,B\subseteq C$，根据子集的定义，$\forall x\in A,x\in B$均成立，同时$\forall x\in B,x\in C$成立。由于$A$是$B$的一部分，因此有$\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)$关系都存在。