《离散数学》习题集

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

联系客服:779662525#qq.com(#替换为@)