北邮离散数学期末复习题1

离散数学期末复习题

第一章集合论

一、判断题

（1）空集是任何集合的真子集． （ 错 ） （2）???是空集． （ 错 ） （3）?a???{a},a? （ 对 ） （4）设集合A???,则??1,2???2A. ( 对 ） 1,2,?1,2?（5）如果a?A?B，则a?A或a?B． （ 错 ） 解 a?A?B则a?A?B?A?B，即a?A且a?B，所以a?A且a?B （6）如果A∪B?B,则A?B. （ 对 ） （7）设集合A?{a1,a2,a3}，B?{b1,b2,b3}，则

A?B?{?a1,b1?,?a2,b2?,?a3,b3?} （ 错 ）

A

（8）设集合A?{0,1}，则??{??,0?,??,1?,?{0},0?,?{0},1?}是2到A的关

系． （ 对 ） 解 2?{?,{0},{1},A}，

A

2A?A?{??,0?,??,1?,?{0},0?,?{0},1?,?{1},0?,?{1},1?,?A,0?,?A,1?}

（9）关系的复合运算满足交换律． （ 错 ） （10）?????是集合A上的关系?具有传递性的充分必要条件. （ 错 ）

~也是A上的传递关系（11）设?是集合A上的传递关系,则?. ( 对 )

（12）集合A上的对称关系必不是反对称的. （ 错 ） （13）设?1,?2为集合A上的等价关系, 则?1??2也是集合A上的等价关系( 对 ) （14）设?是集合A上的等价关系, 则当?a,b???时， [a]??[b]? ( 对 )

（15）设?1,?2为集合 A 上的等价关系, 则

( 错 )

二、单项选择题

（1）设R为实数集合，下列集合中哪一个不是空集 （ A ） A. x|x?1?0,且x?R B．x|x?9?0,且x?R C. ?x|x?x?1,且x?R? D. x|x??1,且x?R

2?2??2???1

（2）设A,B为集合，若A\\B??，则一定有 （ C ） A. B?? B．B?? C. A?B D. A?B

（3）下列各式中不正确的是 （ C ） A. ??? B．????? C. ??? D. ????,{?}?

（4）设A??a,{a}?，则下列各式中错误的是 （ B ） A. ?a??2A B．?a??2A C. ?{a}??2A D. ?{a}??2A （5）设A??1,2?，B??a,b,c?，C??c,d?，则A?(B?C)为 （ B ） A. ??c,1?,?2,c?? B．??1,c?,?2,c?? C. ??1,c?,?c,2?? D. ??c,1?,?c,2??

（6）设A??0,b?，B??1,b,3?，则A?B的恒等关系为 （ A ） A. ??0,0?,?1,1?,?b,b?,?3,3?? B．??0,0?,?1,1?,?3,3?? C. ??0,0?,?b,b?,?3,3?? D. ??0,1?,?1,b?,?b,3?,?3,0?? （7）设A??a,b,c?上的二元关系如下，则具有传递性的为 （ D ） A. ?1???a,c?,?c,a?,?a,b?,?b,a?? B． ?2???a,c?,?c,a??

C. ?3???a,b?,?c,c?,?b,a?,?b,c?? D. ?4???a,a??

（8）设?为集合A上的等价关系，对任意a?A，其等价类?a??为 （ B ） A. 空集； B．非空集； C. 是否为空集不能确定； D. {x|x?A}. （9）映射的复合运算满足 （ B ） A. 交换律 B．结合律 C. 幂等律 D. 分配律 （10）设A，B是集合，则下列说法中（ C ）是正确的. A．A到B的关系都是A到B的映射 B．A到B的映射都是可逆的 C．A到B的双射都是可逆的

D．A?B时必不存在A到B的双射

2

（11）设A是集合，则（ B ）成立. A．#2?2AA#A

B．X?2?X?A C．????2A D．?A??2A

（12）设A是有限集（#A?n），则A上既是?又是～的关系共有（ B ）. A．0个 B．1个 C．2个 D．n个 三、填空题

1. 设A?{1,2,{1,2}}，则2?____________.

填2A?{?,{1},{2},{{1,2}},{1,2},{1,{1,2}},{2,{1,2}},A}

2.设A?{?,{?}}，则2= . 填2A?{?,{?},{{?}},A} 3.设集合A,B中元素的个数分别为#A?5，#B?7，且#(A?B)?9， 则集合A?B中元素的个数#(A?B)? .3 4.设集合A?{x|1?x?100,x是4的倍数，x?Z}，

A

AB?{x|1?x?100,x是5的倍数，x?Z}，则A?B中元素的个数为 .40 5.设 A?{a,b}, ? 是 2 上的包含于关系，,则有

?= .

{??,??,??,{a}?,??,{b}?,??,A?,?{a},{a}?,?{a},A?,?{b},{b}?,?{b},A?,?A,A?} 6.设?1,?2为集合 A 上的二元关系, 则?1??2? .?2??1 7.集合A上的二元关系?为传递的充分必要条件是 ．????? 8. 设集合A??0,1,2?上的关系?1???0,2?,?2,0??及集合A到集合B??0,2,4?的关系?2?｛?a,b?|?a,b??A?B且a,b?A∩B?,则?1??2?___________________. 填 {?0,0?,?0,2?,?2,0?,?2,2?} 四、解答题

1. 设 A?{a,b,c,d},A上的关系

~~A

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

（1）写出?的关系矩阵； （2）验证?是A上的等价关系； （3）求出A的各元素的等价类。

3

解 （1）?的关系矩阵为

?1??1 M???0??0?又由于

110000110??0? ?1?1??（2）从?的关系矩阵可知：?是自反的和对称的。

?1100??1100??1100????????1100??1100??1100? M??M????????M? ???001100110011???????0011??0011??0011???????或?????满足????? 所以?是传递的。

因为?是自反的、对称的和传递的，所以?是A上的等价关系。 （3） [a]?[b]?{a,b}，[c]?[d]?{c,d}

2. 设集合A?{1,2,3,6,8,12,24,36}，?是A上的整除关系， （1） 写出?的关系矩阵M?； （2） 画出偏序集?A,??的哈斯图；

（3） 求出A的子集B?{2,3,6}的最小上界和最大下界。

?1??0?0??0解：（1）M????0?0??0?0?（2）

1100000010100000111100001100100011110100111111101??1?1??1? ?0?1??0?1??4

（3）lubB=6, glbB=1

五、证明题

1. 设?1,?2为集合A上的等价关系, 试证?1??2也是集合A上的等价关系。 证明：由于?1,?2是自反的，所以对任意a?A,?a,a???1,?a,a???2, 因而

?a,a???1??2，即?1??2是自反的。

若?a,b???1??2，则?a,b???1,?a,b???2,由于?1,?2是对称的，所以?b,a???1,?b,a???2, 从而?b,a???1??2，即?1??2是对称的。 若，则 ?a,b?,?b,c???1??2?a,b?,?b,c???1,?a,b?,?b,c???2,由于?1,?2是传递的，所以?a,c???1,?a,c???2, 从而?a,c???1??2，即?1??2是传递的。 由于?1??2是自反的、对称的和传递的，所以?1??2是等价关系。

第二章 代数系统

一、判断题

（1）集合A上的任一运算对A是封闭的． （ 对 ） （2）代数系统的零元是可逆元. （ 错 ） （3）设A是集合，?:A?A?A，a?b?b，则?是可结合的． （ 对 ） （4）设a,b是代数系统?A,??的元素，如果a?b?b?a?e(e是该代数系统的单位元），则

a?1?b. ( 对 )

（5）设a,b是群?G,??的元素,则(a?b)?1?a?1?b?1. （ 错 ） （6）设?G,??是群．如果对于任意a,b?G，有 (a?b)?a?b，则?G,??是阿贝尔群． （ 对 ）

222. （ 对 ） （7）设?L,?,??是格,则运算?满足幂等律（8）设集合A?{a,b}，则?{?,{a},{b},A},?,??是格． （ 对 ） （9）设?B,?,?,?是布尔代数，则?B,?,??是格． （ 对 ）

5

v1v2v3v4v5v1?01110?解 （1） A=

v?2?10101??v3?1011?v?14?10100?. ?v5??01100??（2） 因为

??31212???7??13221????????? A2=??22411?, 3

????12121? A=???????????21112????????所以，结点v1,v3之间长度为3的通路共有7条，它们是

v1v3v1v3,v1v2v5v3,v1v2v1v3,v1v4v1v3,v1v3v5v3,v1v3v2v3,v1v3v

4v3.（3）由于图G是连通的，所以

v1v2v3v4v5

v1?11111?v?2?11111?? C=v?311111?. v?4?11111??v5??11111??（4） e1e2e3e4e5e6e7

v1?1011000?v?2?1100001?? M=v?110110?v3?04?0001100?. ?v5??0000011??2. 在下面的有向图D中，回答下列问题

11

???????,??????

（1）写出图D的邻接矩阵A；

（2）写出结点v1到结点v3的长度为3的所有有向通路； （3）写出结点v5到自身的长度为3的所有有向回路；

?0??1解：（1）A??0??0?0??0??02（2）A??0??0?1?0001??0100?0110?

?0001?1010??1010??10??0111??010111? A3??01??1010??10?010101???101??121?121?

?101?121??所以结点v1到结点v3的长度为3的所有有向通路只有一条: v1v5v2v3

（3）结点v5到自身的长度为3的所有有向回路只有一条：v5v2v1v5

3.在下面的无向图G中，回答下列问题

a e

d

b c

（1）写出a,d之间的所有初级通路； （2）写出a,d之间的所有短程，并求d(a,d)； （3）判断无向图G是否为欧拉图并说明理由。 解（1）a,d之间的所有初级通路共有7条，分别为

aed，aecd，aebcd，abed，abcd，abecd，abced （2）a,d之间的长度最短的通路只有1条，即aed，因而它是a,d之间

唯一的短程，d(a,d)?2 （3）由于无向图G中有两个奇度顶点deg(b)?3,deg(c)?3，所以无向图G没有欧

12

拉回路，因而不是欧拉图。

第四章 数理逻辑

一、判断题 （1）“如果8＋7＞2，则三角形有四条边”是命题． （ 对 ） （2）设P,Q都是命题公式，则P?Q也是命题公式． （ 错 ） （3）命题公式P,Q的真值分别为0，1，则P?Q的真值为0

（以上是在对P,Q所包含的命题变元的某个赋值下）． （ 错 ） （4）设p:他生于1963年,q:他生于1964年，则命题“他生于1963年或1964年”可以符号化为p?q. （ 对 ） （5）设P，Q都是命题公式，则P?Q的充分必要条件为P?Q?1.（ 对 ） （6）逻辑结论是正确结论． （ 错 ） （9）设A,B,C都是命题公式，则

(A?B??C)?(A?C)

也是命题公式． （ 对 ） （10）命题公式P,Q的真值分别为0，1，则P?Q的真值为0

（以上是在对P,Q所包含的命题变元的某个赋值下）． （ 对 ） 二、单项选择题

（1）下面哪个联结词不可交换 （ B ） A. ?； B．?； C.?； D.? .

（2）命题公式(p?(p?q))?q是 （ C ） A. 永假式； B．非永真式的可满足式； C. 永真式； D. 等价式.

（3）记p:他懂法律，q:他犯法，则命题“他只有懂法律，才不会犯法”可符号化为（ B ）. A．p??q B．?q?p C．q??p D．p?q

（4）下列命题中假命题是（ B ）. A．如果雪不是白的，则太阳从西边出来 B．如果雪是白的，则太阳从西边出来 C．如果雪不是白的，则太阳从东边出来

13

D．只要雪不是白的，太阳就从西边出来

（5）设A，B都是命题公式，则A→B为可满足式是A?B的（ B ）. A．充分而非必要条件 B．必要而非充分条件 C．充分必要条件

D．既非充分又非必要条件 三、填空题

1.设p: 天气很冷，q:老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 .p?q

2.设p:天下雨，q: 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 .?p?q

3. 设p,q的真值为0，r,s的真值为1，则命题公式(p?r)?(?q?s)的真值为 .0 4.设p,q的真值为0，r的真值为1，则命题公式p?(q?r)的真值为 .0

14

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