内容发布更新时间 : 2025/7/8 3:48:53星期一 下面是文章的全部内容请认真阅读。
精品文档
2)两个自反的(对称的)关系的并将是自反的(对称的),但是,两个传递关系的并却未必是传递的。我们就从破坏传递性出发来构造反例: 令R1={(a,a),(b,b),(c,c),(a,b),(b,a)} R2={(a,a),(b,b),(c,c),(b,c),(c,b)} 当A={a,b,c}时,R1,R2显然都是等价关系。但是
R1∪R2={(a,a),(b,b),(c,c),(a,b),(b,a)(b,c),(c,b)}都不是A上的等价关系,因为R1∪R2不传递:(a,b)∈R1∪R2且(bc,但(a,c)?R1∪R2;同样(c,b)∈R1∪R2且(b,a)∈R1∪R2,但(c,a)?R1∪R2。
a a
c
b
b c b c
a
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=A×A={(a,b)|a∈A∧b∈A}因此有n2
个元素在A上的最大的等价关系R1中,因为所有n2个二元组都在R1=A×A中。
2)A上的最大的等价关系R1的秩是1。这是因为A中任何两个元素都有全关系
.
精品文档
R1=A×A,因此R1的等价块包含了A的所有元素,A的所有元素都在同一个等价块中。
3)A上的最小的等价关系是么关系R2=IA={(a,a)a∈A}因此它中有n个元素,即n自反对。
4)A上的最小的等价关系的秩是n,因为么关系的每一个元素都自成一个等价
块,每一等价块中也只有一个元素。
28.设R1和R2是非容集合A上的等价关系,对下列各种情况,指出哪些是A上的
等价关系;若不是,用例子说明。 1) A×A\\R1 2) R1\\R2
23) R1
4)r(R1\\R2) (R1\\R2的自反闭包) 5)R1?R2
[解] 1)不是。设A={a},并且R1={(a,a)},则R1是A上的等价关系,但A×
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