《离散数学》习题集

＞={| 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页

第三章 二元关系

3.1 基本概念

1. 用列举法表示下列A?B上的二元关系S：

(a) A?{0,1,2}，B?{0,2,4}，S?{?x,y?|x,y?AB}；

(b) A?{1,2,3,4,5}，B?{1,2,3}，S?{?x,y?|x?y2?x?A?y?B}。 2. 设A?{0,1,2,3,4}，试用列举法表达由下列谓词确定的A上的n元关系，如果是二元关

系，画出其关系图。 (a) P(x)?x?1； (b) P(x)?3?2； (c) P(x)?2?3； (d) P(x,y)?x?y?4；

(e) P(x,y)??k(x?ky?k?2)； (f) P(x,y,z)?x2?y?z。 3. 对下列关系R，求出关系矩阵MR：

(a) A?{1,2,3}，R?{?2,2?,?1,2?,?3,1?}； (b) A?{0,1,2,3}，R?{?x,y?|x?2?y?1}；

(c) A?{5,6,7,8}，B?{1,2,3}，R?{?x,y?|x?A?y?B?3?x?y?y}； (d) A?{0,1,2,3,4,5,6}，R?{?x,y?|x?y?x是质数}。 4. 对下列每一个N上关系R给出一归纳定义，用你的定义证明x?R。 (a) R?{?a,b?|a?b}，x??3,1?； (b) R?{?a,b?|a?2b}，x??6,3?； (c) R?{?a,b,c?|a?b?c}，x??1,1,2?。

第36页 共53页