算法导论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)\)关系都存在。