内容发布更新时间 : 2024/12/22 17:25:38星期一 下面是文章的全部内容请认真阅读。
精品文档
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}
.