离散数学二元关系习题及答案

离散数学二元关系习题及答案

【篇一：离散数学关系部分经典练习及答案】

t>一、单项选择题

1．设集合a = {1, a }，则a的幂集p(a) = ( )． a．{{1}, {a}}b．{?,{1}, {a}}

c．{?,{1}, {a}, {1, a }}d．{{1}, {a}, {1, a }}

2．若集合a的元素个数为10，则其幂集的元素个数为（ ）．

a．1024 b．10c．100d．1 7．集合a={1, 2, 3, 4, 5, 6, 7, 8}上的关系r={x，y|x+y=10且x, y?a}，则r的性质为（ ）． a．自反的b．对称的

c．传递且对称的d．反自反且传递的

8．设集合a = {1，2，3，4，5，6 }上的二元关系r ={?a , b??a , b?a , 且a +b = 8}，则r具有的性质为（ ）． a．自反的 b．对称的

c．对称和传递的d．反自反和传递的

9．如果r1和r2是a上的自反关系，则r1∪r2，r1∩r2，r1-r2中自反关系有（ ）个． a．0 b．2c．1d．3

10．设集合a={1 , 2 , 3 , 4}上的二元关系 r = {?1 , 1?，?2 , 2?，?2 , 3?，?4 , 4?}，

s = {?1 , 1?，?2 , 2?，?2 , 3?，?3 , 2?，?4 , 4?}， 则s是r的（ ）闭包．

a．自反b．传递 c．对称 d．以上都不对

11．设集合a = {1 , 2 , 3 , 4 , 5}上的偏序关系 的哈斯图如图一所示，若a的子集b = {3 , 4 , 5}， 则元素3为b的（ ）．

a．下界 b．最大下界 5 图一 c．最小上界 d．以上答案都不对

12．设a={1, 2, 3, 4, 5, 6, 7, 8}，r是a上的整除关系，b={2, 4, 6}，则集合b的最大元、最小元、上界、下界依次为 ( )． a．8、2、8、2 b．无、2、无、2 c．6、2、6、2 d．8、1、6、1

13．设a={a, b}，b={1, 2}，r1，r2，r3是a到b的二元关系，且r1={a，2, b，2}，r2={a，1, a，2, b，1}，r3={a，1, b，2}，则（ ）不是从a到b的函数．

a．r1和r2 b．r2 c．r3d．r1和r3 二、填空题

1．设集合a有n个元素，那么a的幂集合p(a)的元素个数为． 2．设集合a＝{a，b}，那么集合a的幂集是 应该填写：{?,{a,b},{a},{b }}

3．设集合a={0, 1, 2, 3}，b={2, 3, 4, 5}，r是a到b的二元关系， r?{?x,y?x?a且y?b且x,y?a?b} 则r的有序对集合为 ．

4．设集合a={0, 1, 2}，b={0, 2, 4},r是a到b的二元关系， r?{?x,y?x?a且y?b且x,y?a?b} 则r的关系矩阵mr＝ ．

5．设集合a={a,b,c}，a上的二元关系 r={a, b,c. a}，s={a, a,a, b,c, c} 则(r?s)－1=．

6．设集合a=｛a,b,c｝，a上的二元关系r={a, b, b, a, b, c, c, d}，则二元关系r具有的性质是．

7．若a={1,2}，r={x, y|x?a, y?a, x+y=10}，则r的自反闭包 为 ．

8．设a={a，b，c}，b={1，2}，作f：a→b，则不同的函数个数为 三、判断说明题（判断下列各题，并说明理由．） 2．如果r1和r2是a上的自反关系，判断 结论：“r-11、r1∪r2、r1?r2是自反的” 是否 成立？并说明理由．

3． 若偏序集a，r的哈斯图如图一所示， 则集合a的最大元为a，最小元不存在． 4．若偏序集a，r的哈斯图如图二所示，

则集合a的最大元为a，最小元不存在． 图一 四、计算题 图二

x，y|x?a， 4．设a={0，1，2，3，4}，r={x，y|x?a，y?a且x+y0}，s={

y?a且x+y?3}，试求r，s，r?s，r-1，s-1，r(r)．

5．设a={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，r是a上的整除关系，b={2, 4, 6}．

（1）写出关系r的表示式； （2）画出关系r的哈斯图； （3）求出集合b的最大元、最小元．

6．设集合a＝{a, b, c, d}上的二元关系r的关系图 如图三所示．

（1）写出r的表达式； （2）写出r的关系矩阵； （3）求出r2．

7．设集合a={1，2，3，4}，r={x, y|x, y?a；|x?y|=1或x?y=0}，试

（1）写出r的有序对表示；（2）画出r的关系图； （3）说明r满足自反性，不满足传递性． 五、证明题

3．设r是集合a上的对称关系和传递关系，试证明：若对任意a?a，存在b?a，使得a, b?r，则r是等价关系．

4．若非空集合a上的二元关系r和s是偏序关系，试证明：r?s也是a上的偏序关系． 参考解答

一、单项选择题

1．a 2．a 7．b 8．b

9．b 10．c 11．c 12．b 13．b 二、填空题 1．2n

2．{?,{a,b},{a},{b }}

3．{2, 2，2, 3，3, 2}，3, 3 ?110?? 0004．?????110?? 5．{a. c, b, c} 6．反自反的 7．{1, 1, 2, 2} 8．8

三、判断说明题（判断下列各题，并说明理由．） 2．解：成立．

因为r1和r2是a上的自反关系，即ia?r1，ia?r2。 由逆关系定义和ia?r1，得ia? r1-1；

由ia?r1，ia?r2，得ia? r1∪r2，ia? r1?r2。 所以，r11、r1∪r2、r1?r2是自反的。

3．解：正确．

对于集合a的任意元素x，均有x, a?r

（或xra），所以a是集合a中的最大元． 按照最小元的定义，在集合a中不存在最 小元．

4．解：错误．

集合a的最大元不存在，a是极大元． 四、计算题 4．解：r=?,

s={0,0,0,1,0,2,0,3,1,0,1,1,1,2,2,0,2,1,3,0}r?s=?， r-1=?，

s-1= s，r(r)=ia．

5．解：（1）r=i?{1,2, 1,3, ?, 1,12 , 2,4, 2,6, 2,8, 2,10, 2,12, 3,6, 3,9 , 3,12, 4,8, 4,12, 5,10, 6,12}

（2）关系r的哈斯图如图四 （3）集合b没有最大元，最小元是：2 -11 图四：关系r的哈 斯图

6．解：r＝{a, a, a, c, b, c, d,d} 0?

0?? 0??1?

r2 = {a, a, a, c, b, c, d, d}?{a, a, a, c, b, c, d, d} ={a, a, a, c, d,d}

7．解：（1）r={1,1,2,2,3,3,4,4, 1 1,2,2,1,2,3,3,2,3,4,4,3} （2）关系图如图五 （3）因为1,1,2,2,3,3,4,4均属于r， 即a的每个元素构成的有序对均在r中，故r在 a上是自反的。 因有

2,3与3,4属于r，但2,4不属于r， 所以r在a上不是传递的。 五、证明题

3．设r是集合a上的对称关系和传递关系，试证明：若对任意a?a，存在b?a，使得a, b?r，则r是等价关系．

证明：已知r是对称关系和传递关系，只需证明r是自反关系． ?1?0mr???0??000001100

?a?a，?b?a，使得a, b?r，因为r是对称的，故b, a?r；又r是传递的，即当a, b?r，b, a?r ?a, a?r；

由元素a的任意性，知r是自反的． 所以，r是等价关系．

4．若非空集合a上的二元关系r和s是偏序关系，试证明：r?s也是a上的偏序关系．

证明：.① ?x?a,?x,x??r,?x,x??s??x,x??r?s，所以r?s有自反性； ②?x,y?a,因为r，s是反对称的，

?x,y?r?s??y,x?r?s?(?x,y??r??x,y??s)?(?y,x??r??y,x??s)?(?x,y??r??y,x??r)?(?x,y??s??y,x??s)?x?y?y?x?x?y

所以，r?s有反对称性． ③ ?x,y,z?a，因为r，s是传递

的， ?x,y??r?s??y,z??r?s ??x,y??r??x,y??s??y,z??r??y,z??s ??x,y??r??y,z??r??x,y??s??y,z??s ??x,z??r??x,z??s??x,z??r?s

所以，r?s有传递性． 总之，r是偏序关系．

【篇二：离散数学第二部分测试题-有答案2】

>一、 填空题

1．d={?}，则幂集?(d)?{?,{?}}.

2. b={1，{2，3}}，则幂集?(b)?{?,{1},{{2,3}},{1,{2,3}}} 3. 若集合a，b的元素个数分别为a?m,b?n，则a到b有 2种不同的二元关系。 4. a={?，a，{b}}，b={?}，则a?b????,??,?a,??,?{b},??? 5. 设a={1，2，3}，则在a上有5个不同的划分。

6.设p={1, 2, 1, 4, 2, 3, 4, 4}和q={ 1, 2, 2, 3,4, 2} 则dom(p∪q)= {1,2,4} ，ran(p∪q) = { 2,3,4}

7. ia是集合a上的恒等关系，a上的关系r具有性当且仅当 r?r?1?ia m?n

8. ia是集合a上的恒等关系，a上的关系r具有性当且仅当 ia?r??

9. 设r为a上的关系，r在a上具有 传递 当且仅当r?r?r。 10．设r为a上的关系，r在a上自反的当且仅当 ia?r11.设r为a上的关系，r在a上对称的当且仅当r?r?1 二、 选择题

1．集合a={全班同学}上的同龄关系r为（ b ）

a．对称关系b．等价关系c．偏序关系d．三个都不是 2．在由3

个元素组成的集合上，可以有（ d ）种不同的关系。 a． 3；b．8； c．9 ； d．512

3．设集合a??a,b,c?,a上的二元关系r???a,a?,?b,b??不具备关系( d )性质

a．传递性b．反对称性 c．对称性 d．自反性 三、 计算题

1.设集合a={1，2，3}，a上的关系r={1，1，1，2，2，2，3，2，3，3}

（1） 画出r的关系图； （2） 写出r的关系矩阵

问r具有关系的哪几些特殊性质（自反、对称、传递等） 解 （1） ?110?

? 010（2）m???? ??011??

该关系是自反的但不是反自反的，因为每个顶点都有个环；它是反对称的

但不是对称的，因为图中只有单向边；它也是传递的，因为不存在顶点x,y,z，使得x到y有边，y到z有边，但x到z没边，其中x,y,z?{1,2,3}。

2.设a={0，1，2，3}，r是a上的关系，且 ，0，0，3，2，0，2，1，2，3，3，2}

用矩阵运算求r的自反闭包r(r)，对称闭包s(r)和传递闭包t(r)。 解 r(r)?{?0,3?,?2,0?,?2,1?,?2,3?,?3,2?}?ia

s(r)?{?0,3?,?3,0?,?2,0?,?0,2?,?1,2?,?2,1?,?2,3?,?3,2?}?ia t(r)?r?r2?r3?r4

r2?{?0,0?,?0,3?,?0,2?,?2,0?,?2,3?,?2,2?,?3,0?,?3,1?,?3,3?}

r3?r2?r?{?0,0?,?0,3?,?0,2?,?2,0?,?2,3?,?2,2?,?3,0?,?3,2?,?3,3?,?0,1?,?2,1?}t(r)?r?r2?r3?r4

?{?0,0?,?0,3?,?0,2?,?2,0?,?2,3?,?2,2?,?3,0?,?3,2?,?3,3?,?0,1?,?2,1?,?3,1?}

3.设a={2,3,4,5,6,7,8,9,10,12,20}，r为整除关系，求下列各题： （1） 画出偏序集a,r的哈斯图； （2） 求该偏序集的极大元和极小元。 解：

（1）哈斯图如下：

r4?r3?r?{?0,0?,?0,3?,?0,2?,?2,0?,?2,3?,?2,2?,?3,0?,?3,2?,?3,3?,?0,1?,?2,1?,?3,1?

（2）极大元为7，8，9，12，20；极小元为2，3，5，7。 4.a={1，2，…，12}， ∈a∧2≤x≤4} 在偏序集a，

中求b的上界，下界，最小上界和最大下界。 为整除关系，

答案：b的上界：12；下界：1；最小上界：12；最大下界：1 5. 设a={1,2,3,4,5}，a上的偏序关系如图所示，

求a的子集合{3，4，5}和{1，2，3}的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界,填写下列表格： 四、 证明题

1.证明: (a－b)－c＝a－(b∪c) 证明：对任意的x x?(a?b)?c?x?(a?b)?x?c……1分

?x?a?x?b?x?c……1分 ?x?a??x?b??x?c……1分 ?x?a???x?b?x?c?……1分 ?x?a?x??b?c?……1分 ?x?a??b?c?……1分

或者 (a－b)－c＝(a∩～b) ∩～c……2分 ＝a∩～b∩～c……1分 ＝a∩～(b∪c)……2分 ＝a－(b∪c)……1分

2.设n是自然数集合，定义n上的二元关系r：r?证明r是一个等价关系。

证明：（1）对任意x??，x?x是偶数，有?x,x??r，所以r是自反；……2分

??x,y?x,y??,x?y是偶数?，

（2）对任意x,y??，若?x,y??r,即x?y是偶数，则y?x是偶数，有 ?y,x??r，所以r是对称的；……2分

（3）对任意x,y,z??，若?x,y??r且若?y,z??r，即x?y是偶数，y?z是偶数，则x?z??x?y???y?z??2y是偶数，有?x,z??r，所以r是可传递的；……2分

由（1）（2）（3）知r是等价关系。……1分

【篇三：国防科大版离散数学习题答案】

.1 1.

a) {0, 1, 2, 3, 4} b) {11, 13, 17, 19}

c) {12, 24, 36, 48, 64} 2.

a) {x | x ? n 且x ? 100}

b) ev = {x | x ? n 且2整除x } od = {x | x ? n 且2不能整除x } c) {y | 存在x ? i 使得 y = 10 ? x } 或 {x | x/10 ? i } 3. 极小化步骤省略 a) ① ② 或 ① ② 或 ①

② {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ? a ； 若?, ? ? a，则??? ? a 。 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ? a ； 若? ? a 且 a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a?? ? a 。 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ? a ； 若? ? a 且 a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则??a ? a 。 b)

① {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ? a ； ② 若?, ? ? a 且 ? ? 0，则 ??? ? a 。

c) ① 若a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则 a. ? a ；

② 若? ? a 且 a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则??a ? a ； 若? ? a 且 a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a?? ? a 。 或

① {0., 1., 2., 3., 4., 5., 6., 7., 8., 9.} ? a ；

② 若? ? a 且 a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则??a ? a ； 若? ? a 且 a ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a?? ? a 。 d) ① {0, 10} ? a ；

② 若? ? a，则1?? ? a ；

若?, ? ? a 且 ? ? 0，则 ??? ? a 。 e) ev定义如下：

① {0} ? ev 或0 ? ev ；

② 若? ? ev，则?+2 ? ev 。 od定义如下：

① {1} ? od 或1 ? od ；

② 若? ? od，则?+2 ? od 。 ① {0} ? a 或 0 ? a ；

② 若? ? a，则(f) ?1)2 ? a 。 4. a = g；c = f；b = e。 5. 题号是否正确 a)?

b)? （空集不含任何元素） c)? d)? e)? 6. 7. 8. a) b) c) d) e) f) g) 9. a) b) c)

d)f) g) h) 题号a) b) c) d)? ? ?是否正确 ? （ 反例：a = {a}；b

= ?；c = {{a}} ） ? （ 反例：a = ?；b = {?}；c = {?} ） ? （ 反例：a = ?；b = {a}；c = {?} ） ? （ 反例：a = ?；b = {?}；c = {{?}} ） 能。例如：b = a ? {a} 。 ?；{1}；{2}；{3}；{1, 2}；{1, 3}；{2, 3}；{1, 2, 3}； ?；{1}；{{2, 3}}；{1, {2, 3}}； ?；{{1, {2, 3}}}； ?；{?}； ?；{?}；{{?}}；{?, {?}}； ?；{{1, 2}}； ?；{{?, 2}}；{{2}}；{{?, 2}, {2}}； {?，{a}，{{b}}，{a, {b}}}； {?，{1}，{?}，{1, ?}}； {?，{x}，{y}，{z}，{x, y}，{x, z}，{y, z}，{x, y, z}}； {?，{?}，{a}，{{a}}，{?, a}，{?, {a}}，{a, {a}}，{?, a, {a}}}。 习题1.2 1. a) b) c) d)

e) f) g) h) 2. a) b) c) d) e)

a ? ~b = {4}； (a ? b) ? ~c = {1, 3, 5}； ~ (a ? b) = {2, 3, 4, 5}； ~a ? ~b = {2, 3, 4, 5}； (a – b) – c = ?； a – (b – c) = {4}； (a ? b) ? c = {5}； (a ? b) ? (b ? c) = {1, 2}。 b ? c 或 b – e ； a ? d ； (a – b) ? c ； c – b 或c – a ； (a ? c) ? (e – b) 或 (a – e) ? (e – b)； 3.

a) 证明：对于任意x ? a ? c，

因为x ? a ? c，所以x ? a或x ? c。 若x ? a，则由于a ? b，因此x ? b； 若x ? c，则由于c ? d，因此x ? d。 所以，x ? b或x ? d，即x ? b ? d。 所以，a ? c ? b ? d。 类似可证a ? c ? b ? d。 d) f) 4.

a) a – (b ? c) = a ? ~ (b ? c) = a ? (~ b ? ~c) = (a ? a) ? (~ b ? ~c) = (a ? ~b) ? (a ? ~c) = (a – b) ? (a – c) a – (a – b) = a ? ~ (a – b) = a ? ~ (a ? ~b) = a ? (~ a ? b) = (a ? ~a) ? (a ? b) = ? ? (a ? b) = a ? b ?) 若a = b，则a ? b = a且 a ? b = a。 因此，a ? b = (a ? b) – (a ? b) = a – a = ?。 ?) 若a ? b = ?，则a ? b = a ? b。

又因为a ? b ? a ? a ? b且a ? b ? b ? a ? b，所以 a ? b = a = b = a ? b。 所以a = b。 5. 证明略。 a) b) c)

本文来源：https://www.bwwdw.com/article/4dud.html