离散数学（第三版）陈建明，刘国荣课后习题答案(10)

R1关系图 R2关系图 R1∪R2关系图

而且|A|不可能再少了。因为任何少于3个元素的集合上的自反，对称关系一定是传递的！

26．设R是A上的等价关系，将A的元素按R的等价类顺序排列，请指出此等价关

系R的关系矩阵MR有何特征？

[解] 将A的元素按其上的等价关系R的等价类顺序排列，这样产生的等价关系R的

关系矩阵MR，经过适当的矩阵分块，MR的分块矩阵将成为准对角阵，准对角阵的对角线上的每一块都是一个全1方阵，它正好对应于等价关系R的一个等价块。

27．设A是n个元素的有限集合，请回答下列问题，并阐明理由。

1） 有多少个元素在A上的最大的等价关系中？ 2） A上的最大的等价关系的秩是多少？ 3） 有多少个元素在A上的最小的等价关系中？ 4） A上的最小的等价关系的秩是多少？

[答] 1）A上最大的等价关系是全关系R1=A3A={（a，b）|a∈A∧b∈A}因此有n2

个元素在A上的最大的等价关系R1中，因为所有n2个二元组都在R1=A3A中。

2）A上的最大的等价关系R1的秩是1。这是因为A中任何两个元素都有全关系R1=A3A，因此R1的等价块包含了A的所有元素，A的所有元素都在同一个等价块中。

3）A上的最小的等价关系是么关系R2=IA={（a，a）a∈A}因此它中有n个元素，即n自反对。

4）A上的最小的等价关系的秩是n，因为么关系的每一个元素都自成一个等价

块，每一等价块中也只有一个元素。

28．设R1和R2是非容集合A上的等价关系，对下列各种情况，指出哪些是A上的

等价关系；若不是，用例子说明。 1) A3A\\R1 2) R1\\R2 3) R1

4）r（R1\\R2） （R1\\R2的自反闭包） 5）R1?R2

2 31

[解] 1）不是。设A={a}，并且R1={（a，a）}，则R1是A上的等价关系，但A3

A\\R1={（a，a）\\（a，a）}=?就不是A上的等价关系，因为空关系不是自反的。

2）不是。设A={（a，b）}并且R1={（a，a），（b，b），（a，b），（b，a）}，

R2={（a，a），（b，b）}，则R1，R2都是A上的等价关系，但是，R1\\R2={（a，b），（b，a）}就不是A上的等价关系，因为R1\\R2不自反。 3）是。

证法一：因R1是等价关系，因而R1是传递的，故此由第12题之5）有R1= R1?R1?R1。另一方面，结任何（a，b）∈R1，由于R1是自反的，故此（b，b）∈R1，从而由复合关系之定义，有（a，b）∈R1?R1，所以R1?R1，从而R1=R1，因此由R1是等价关系，知R1也是等价关系。 证法二：

一方面，对任何a，b?A，(a,b)?R1

?(?c?A)((a,c)?R1?(c,b)?R1)

?(?c?A)((a,b)?R1) (R1是传递的) ?(a,b)?R1(带量词的基本逻辑等价式：(?x)p?p)

所以，R1?R1 ；

另一方面，对任何a，b?A，(a,b)?R1

?(a,b)?R1?(b,b)?R1) (R1是自反的) ?(a,b)?R1

所以，R1?R1 ；

综合这两方面，就有R1=R1 ；

4）是。设A={a，b，c}，R1={（a，a），（b，b），（c，c），（a，b），（b，a），（a，c）（c，a），（b，c），（c，b）}。R1={（a，a），（b，b）（c，c）（a，a）（c，a）}，则R1，R2都是A上的等价关系。 R1\\R2={（a，b），（b，a），（b，c），（c，b）}

r（R1\\R2）={（a，a），（b，b），（c，c），（a，b），（b，a），（b，c），（c，b）}因此r（R1\\R2）不是A上的等价关系，因为r（R1\\R2）不是传递的，（a，b）∈r（R1\\R2）且（b，c）∈r（R1\\R2），但是（a，c）?r（R1\\R2）。

5）不是。令A={a，b，c}，R1={（a，a），（b，b），（c，c），（a，b），（b，a）}，R2={（a，a），（b，b），（c，c），（a，b），（b，a），（b，c），（c，b），（a，c）}不上的等价关系，因为R1?R2不对称，（a，c）∈R1?R2，但（c，a）?R1?R2。

222222222 32

29．设A={1，2，3，4}，请指出A上所有等价关系是多少？并阐明理由。

[解] A上的等价关系共有14个。根据A上的划分与A上的等价关系一一对应的原理，

我们只需求出A上有多少个划分就行了。

{{a}，{b}，{c}，{d}}型划分，一个； {{a，b}，{c}，{d}}型划分，六个； {{a，b，}，{c，d}}型划分，三个； {{a，b，c}，{d}}型划分，四个； {{a，b，c，d}}型划分，一个。 总计：1+6+3+4+1=15 。

30．设A={1，2，3，4，5，6}，确定A上的等价关系R，使此R能产生划分{{1，2，

3，}，{4}，{5，6}}

[解] 这样的R={（1，1），（2，2），（3，3），（1，2），（2，1），（1，3），（3，1），（2，3），（3，2），（4，4），（5，5），（6，6），（5，6），（6，5）}

1 4 5 6 2 3

R的关系图 31．设R是集合A上的关系

R是循环∷＝（?a∈A）（?b∈A）（?c∈A）（aRb∧bRc?cRa） 证明：R是自反的和循环的，当且仅当R是等价关系。 [证] 证法一：

必要性

若R是自反的和循环的，我们来证R是等价关系，为此证明 （a）R是自反的。

必要性条件所给。 （b）R是对称的

对任何（a，b）∈R，由于R是自反的，所以（b，b）∈R，再根据R是循环的可得（b，a）∈R。 （c）R是传递的

对任何（a，b）∈R，（b，c）∈R，由于R是循环的，所以（c，a）∈R，

33

利用R是对称的，就得到（a，c）∈R。 充分性

若R是等价关系，我们来证R是自反的和循环的。 1）R是自反的。

因R是等价关系，故R是自反的。 2）R是循环的

对任何（a，b）∈R，（b，c）∈R，由于R是传递的，所以（a，c）∈R。 由于R是对称的，（c，a）∈R。 证法二： ?)：

（a）R是自反的：已知； （b）R是对称的： 对任何a，b?A，(a,b)?R

?(a,b)?R?(b,b)?R (R是自反的) ?(b,a)?R (R是循环的)

所以，R是对称的； （c）R是传递的：

对任何a，b，c?A，(a,b)?R?(b,c)?R

?(c,a)?R (R是循环的) ?(a,c)?R (R是对称的) …… 此处隐藏：815字，全部文档内容请下载后查看。喜欢就下载吧 ……