精品文档
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,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是自反的)
222222.
精品文档
?(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。
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 2224 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,利用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是对称的)
所以,R是传递的;
综合(a),(b),(c)可知R是等价关系; ?):
(a)R是自反的:
因为R是等价关系,所以R是自反的; (b)R是循环的:
对任何a,b,c?A,(a,b)?R?(b,c)?R
?(a,c)?R (R是传递的) ?(c,a)?R (R是对称的)
所以,R是循环的;
32.设∏1和∏2是非空集合A的划分,说明下面各种情况哪些是A的划分?哪些不
是A的划分?哪些可能是A的划分?并阐明理由。 1)∏1∪∏2 2)∏1∩∏2 3)∏1\\∏2
4)(∏1∩(∏2\\∏1))∪∏1
[解] 1)可能。如果∏1=∏2,则∏1∪∏2是A的划分;如果,∏1≠∏2,则∏1∪∏2
不是A的划分;例如A={a,b},∏1={{a},{b}},∏2={{a,b}},但∏1∪∏
2={{a},{b},{a,b}}就不是
A的划分,因为{a}∩{a,b}={a}≠?,就不是
A的划分,因为{a}∩{a,b}={a}≠?。
2)可能。如果∏1=∏2,则∏1∩∏2是A的划分;如果,∏1≠∏2,则∏1∩∏2
不是A的划分;例如A={a,b},∏1={{a},{b}},∏2={{a,b}},∏1∩∏2=?,就不是A的划分。
3)可能。如果∏1∩∏2=?,则∏1\\∏2=∏1是A的划分;如果∏1∩∏2≠?,则
∏1\\∏2不是A的划分;例如A={a,b,c},∏1={{a},{b},{c}},∏2={{a},{b,c}},∏1∩∏2={{a}}因此∏1\\∏2={{b},{c}}就不是A的划分。因为{b}∪{c}={b,c}≠A。
4)是。因为(∏1∩(∏2\\∏1))∪∏1=?∪∏1=∏1,是A的划分。
33.对下列集合上的整除关系画出哈斯图,并对3)中的子集{2,3,6},{2,4,6},
{4,8,12}找出最大元素,最小元素,极大元素,极小元素,上确界,下确界。 1){1,2,3,4}
.