《离散数学》习题集(7)

{A1B,A2B,,AmB}是AB的划分。

,?k是A上划分序列，使?i?1真细分?i，找

54. 设A是n个元素的有限集，假设?1,?2,出最大可能的序列长度。

55. 设A?I，定义A上的R1,R2,R3如下：

aR1b?a?b(mod3)，aR2b?a?b(mod5)，aR3b?a?b(mod6)，

(a) 对偏序集合?{A/R1,A/R2,A/R3},细分?画出哈斯图； (b) 描述一下各式所诱导的等价关系，它们的秩是什么？

A/R1A/R2，A/R1A/R3，A/R1?A/R2，A/R1?A/R3。

56. 设Rj表示I上模j等价，设Rk表示I上模k等价， (a) 证明I/Rk细分I/Rj当且仅当k是j的整数倍； (b) 描述划分I/Rk?I/Rj； (c) 描述划分I/RkI/Rj。 57. 证明如果?1细分?2，那么?1?2??1和?1??2??2。

58. 设P表示非空集合A的所有划分的集合，考虑偏序集合?P,细分?，设?1和?2是P的

成员， (a) 证明?1?2是集合{?1,?2}的最大下界；

(b) 证明?1??2是集合{?1,?2}的最小上界。

59. 设R是集合A上的二元关系，如果R是自反的和对称的，则称R是相容关系。设

A?{316,347,204,678}，R?{?x,y?|x?A?y?A?x和y有相同的数字}，

(a) R是相容关系吗？ (b) 画出R的关系图。

(c) 所有等价关系都是相容关系吗？

(d) 相容关系的关系图和等价关系的关系图有何不同？

第31页 共53页

补充习题：

1设A={a,b}，B={1,2}，求A上的恒等关系IA和A到B的全域关系A×B。 2设A={a1,a2,a3,a4}，B={b1,b2,b3}，R是A到B的二元关系，定义为：

R={,,,,,,} 写出R的关系矩阵。

3设A={1,2,3,4}，R是A的二元关系，定义为：

R={<1,1>,<1,2>,<2,1>,<3,2>,<3,1>,<4,3>,<4,2>,<4,1>} 写出A上二元关系R的关系矩阵。

4设X={1,2,3,4}，X上的二元关系H和S定义如下：

x?y是整数} 2x?yS={ |是正整数}

3H={ |

试求H∪S，H∩S，~H，S-H。

5X={1,2,3,4,5}，X上的二元关系R和S定义如下：

R={<1,2>,<3,4>,<2,2} S={<4,2>,<2,5>,<3,1>,<1,3>}

试求R°S，S°R，R°(S°R)，(R°S)°R，R°R，S°S，R°R°R 。 6A={ 1,2,3,4}，A上的二元关系R定义如下：

R={<1,2>,<2,1>,<2,3>,<3,4>} 求二元关系R的各次幂。

7A={1,2,3,4,5}，A上的二元关系R和S定义如下：

R={<1,2>,<2,2>,<3,4>} S={<1,3>,<2,5>,<3,1>,<4,2>} 试求MR °

S和

MR ° MS，它们是否相等 ?

8设X={1,2,3,4}，Y={a,b,c}，X到Y二元关系

R={<1,a>,<2,b>,<4,c>}，

⑴试求RC，写出MR和MRC，验证MRC=MRT

⑵画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。 9设R是实数集合，

第32页 共53页

＞={| x?R∧y?R∧x＞y}

是实数集合上的大于关系。证明实数集合上的大于关系是反自反的。 10设A={1,2,3}，定义A上的二元关系如下：

R={<1,1>,<2,2>,<3,3>,<1,3>} S={<1,3>} T={<1,1>}

试说明R，S，T是否是A上的自反关系或反自反关系。 11设A={1,3,5,7}，定义A上的二元关系如下：

R={|(a－b)/2是整数} 试证明R在A上是自反的和对称的。 12设A={1,2,3}，定义A上的二元关系如下：

R={<1,1>,<2,2>} S={<1,1>,<1,2>,<2,1>} T={<1,2>,<1,3>} U={<1,3>,<1,2>,<2,1>}

试说明R，S，T，U是否是A上的对称关系和反对称关系。 13设R是实数集合，

S={|x?R∧y?R∧x=y}

是实数集合上的等于关系。证明实数集合上的等于关系是传递的。 14设R，S是X上的二元关系，证明

⑴若R，S是自反的，则R∪S和R∩S也是自反的。 ⑵若R，S是对称的，则R∪S和R∩S也是对称的。 ⑶若R，S是传递的，则R∩S也是传递的。 15设A={1,2,3}，定义A上的二元关系R为：

R={<1,2>,<2,3>,<3,1>} 试求：r(R)，s(R)，t(R)。

16设A={1,2,3}，定义A上的二元关系R为：

R={<1,2>,<2,3>,<3,1>} 试用关系矩阵求传递闭包t(R)。

217设集合 A?{a,b,c,d}， A上的二元关系 R?{(a,a),(a,c),(b,d)}，求R。

第33页 共53页

18设A={1,2,3,4,5}，R是A上的二元关系，

R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,4>,<4,3>,<4,4>,<5,5>} 证明R是A上的等价关系。

19设R={ | x?I∧y?I∧x ≡ y mod k}是整数集合I上的二元关系。证明R是等价关系。 20设X={1,2,3,4}，X的划分S={{1}，{2,3}，{4}}，试写出S导出的等价关系R。 21设X={1,2,3}，写出集合X上的所有等价关系。 22R是集合M?{1,2,3,4,5,6}上的关系，其中：

R???1,1?,?1,3?,?1,6?,?2,2?,?2,5?,?3,1?,?3,3?,?3,6?,?4,4?,?5,2?,?5,5?,?6,1?,?6,3?,?6,6??，

（1）验证R是等价关系； （2）给出R的关系图．

23设A={316,347,204,678,770}，A上的二元关系R定义为：R={| x?A∧y?A∧x和y有相同数码}，证明R是A上的相容关系。写出关系矩阵和关系图。用关系矩阵和关系图验证R是A上的相容关系。

24设X={1,2,3,4}，S1={{1,2,3},{3,4}}，S2={{1,2},{2,3},{1,3},{3,4}}是X的两个覆盖。试写出S1和S2 导出的相容关系R1和R2。

25设A是集合，P (A)是A的幂集合，P (A)上的包含关系?定义如下：

?={ | x?P (A)∧y?P (A)∧x?y }

试证明?是P (A)上偏序关系。

26设A={2,5,6,10,15,30}，A上的整除关系R定义如下：

R={ | x?A∧y?A∧x整除y }

验证R是A上的偏序关系，分析哪些元素盖住了另一些元素，哪些元素没有盖住了另一些元素。

27设A={a,b,c,d,e,f,g,h}，A上的二元关系

R={,,,,,,,,}∪IA

验证R是A上的偏序关系。写出盖住关系COV A，画出哈斯图。找出集合A的极大元和极小元。

28设A={2,3,6,12,24,36}，其上的整除关系

R={ | a?A∧b?A∧a能整除b}

是A上的偏序关系，试求盖住关系COV A，画出哈斯图，确定下列集合的上界和下界。

第34页 共53页

⑴ B1={2,3,6} ⑵ B2={12,24,36}

29设N为自然数集合，N上的大于等于关系定义为

R≥={ | x?N∧y?N∧x≥y } 证明R≥是全序关系。

30设P={?,{a},{a,b},{a,b,c}}，P上的包含关系

R?={ | x?P∧y?P∧x?y}

验证R?是全序关系。

第35页 共53页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《离散数学》习题集(7)在线全文阅读。