北邮离散数学期末复习题[1]1 南京廖华答案网

北邮离散数学期末复习题[1]1 下载本文

文章发布时间 : 2024/5/19 19:41:25星期日

离散数学期末复习题

第一章集合论

一、判断题

（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?} （错）

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

系．（对）解 2?{?,{0},{1},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的双射

（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}，

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的各元素的等价类。

解（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,?,??是格．（对）

二、单项选择题

（1）在整数集Z上，下列哪种运算是可结合的（ B ）

a,b} A. a?b?a?b B．a?b?max{C. a?b?a?2b D. a?b?|a?b|

（2）下列定义的实数集R上的运算 * 中可结合的是. （ C ）

A．a?b?a?a?b B．a?b?a?2a?b C．a?b?b

D．a?b?a?b

其中，+，·，︱︱分别为实数的加法、乘法和取绝对值运算.

（3）设集合A??1,2,3,4,?,10?，下面定义的哪种运算关于集合A不是封闭的

（ D ）

A. x?y?max{x,y} B． x?y?min{x,y}

C. x?y?GCD{x,y}，即x,y的最大公约数 D. x?y?LCM{x,y}，即x,y的最小公倍数

（4）下列哪个集关于减法运算是封闭的（ B ） A. N（自然数集）； B．{2x|x?Z(整数集)}； C. {2x?1|x?Z}； D. {x|x是质数}.

（5）设Q是有理数集，在Q定义运算?为a?b?a?b?ab，则Q,?的单位元为（ D ） A. a； B．b； C. 1； D. 0

（6）设代数系统?A，·?，则下面结论成立的是. （ C ） A．如果?A，·?是群，则?A，·?是阿贝尔群 B．如果?A，·?是阿贝尔群，则?A，·?是循环群 C．如果?A，·?是循环群，则?A，·?是阿贝尔群 D．如果?A，·?是阿贝尔群，则?A，·?必不是循环群

（7）循环群Z,?的所有生成元为（ D ） A. 1，0 B．-1，2 C. 1，2 D. 1，-1 三、填空题

1. 设A为非空有限集，代数系统?2A,??中，2对运算?的单位元为，零元

为 .填?,A

2.代数系统?Z,??中（其中Z为整数集合，+为普通加法），对任意的x?I，其

x?1? .填?x

3.在整数集合Z上定义?运算为a?b?a?2?b，则?Z,??的单位元为 . 解设单位元为e，a?e?a?2?e?a，所以e??2，

又a?(?2)?a?2?(?2)?a,(?2)?a?(?2)?2?a?a，所以单位元为e??2

4.在整数集合Z上定义?运算为a?b?a?b?ab，则?Z,??的单位元为 . 解设单位元为e，a?e?a?e?ae?a，(1?a)e?0，所以e?0

5.设G,?是群，对任意a,b,c?G，如果a?b?a?c,，则 .填b?c 6.设G,?是群，e为单位元，若G元素a满足a?a，则a? .填e 四、解答题

1.设?为实数集R上的二元运算，其定义为

2?:R2?R,a?b?a?b?2ab，对于任意a,b?R

求运算?的单位元和零元。

解：设单位元为e，则对任意a?R，有a?e?a?e?2ae?a，即 e(1?2a)?0，由a的任意性知 e?0，

又对任意a?R，a?0?a?0?0?a；0?a?0?a?0?a

所以单位元为0 设零元为?，则对任意a?R，有a???a???2a???，即 a(1?2?)?0，由a的任意性知 ???又对任意a?R，a?(?)?a?所以零元为 ?1 21211111?a??，(?)?a???a?a?? 222221 22. 设?为集合I5?{0,1,2,3,4}上的二元运算，其定义为

?:I5?I5,a?b?(ab)mod5，对于任意a,b?I5

（1）写出运算?的运算表；

（2）说明运算?是否满足交换律、结合律，是否有单位元和零元、如果有请指出；（3）写出所有可逆元的逆元解：（1）运算表为

? 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1

（2）运算?满足交换律、结合律，有单位元，单位元为1，有零元，零元为0；（3）1的逆元为1，2的逆元为3，3的逆元为2，4的逆元4，0没有逆元

五、证明题

1. 设 ?G,?? 是一个群，试证 G 是交换群当且仅当对任意的a,b?G ,有 a2?b2?(a?b)2 . 证明：充分性

若在群?G,??中，对任意的a,b?G ,有a2?b2?(a?b)2 . 则 (a?a)?(b?b)?(a?b)?(a?b) a?(a?b)?b?a?(b?a)?b

a?b?b?a 从而 ?G,?? 是一个交换群。必要性

若?G,?? 是一个交换群，对任意的a,b?G ,有a?b?b?a，则 a?(a?b)?b?a?(b?a)?b (a?a)?(b?b)?(a?b)?(a?b) 即a?b?(a?b).

2. 证明代数系统?Z,??是群，其中二元运算?定义如下：

?：Z?Z，x?y?x?y?3 （这里，+，－分别是整数的加法与减法运算.）证明（1）运算满足交换律对任意x,y,z?Z，由

2222(x?y)?z?(x?y?3)?z?x?y?z?6,

x?(y?z)?x?(y?z?3)?x?y?z?6

得(x?y)?z?x?(y?z),即?满足结合律；

（2）有单位元 3是单位元；（3）任意元素有逆元对任意x?Z，x?1?6?x.所以,?Z，??是群.

第三章图论

一、判断题

（1）n阶完全图的任意两个不同结点的距离都为1. （对）（2）图G的两个不同结点vi,vj连接时一定邻接. （错）（3）图G中连接结点vi,vj的初级通路为vi,vj之间的短程. （错）（4）在有向图中，结点vi到结点vj的有向短程即为vj到vi的有向短程．（错）（5）强连通有向图一定是单向连通的．（对）（6）不论无向图或有向图，初级回路一定是简单回路．（对）（7）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的．

（对）

（8）有生成树的无向图是连通的．（对）（9）下图所示的图是欧拉图. （错）

（10）下图所示的图有哈密尔顿回路. （对）

二、单项选择题

（1）仅由孤立点组成的图称为（ A ） A. 零图； B．平凡图； C. 完全图； D. 多重图.

（2）仅由一个孤立点组成的图称为（ B ） A. 零图； B．平凡图； C.多重图； D. 子图.

（3）在任何图G中必有偶数个（ B ） A. 度数为偶数的结点； B．度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点.

（4）设G为有n个结点的无向完全图，则G的边数为（ C ） A. n(n?1) B．n(n?1) C. n(n?1)2 D. (n?1)2

（5）在有n个结点的连通图G中，其边数（ B ） A. 最多n?1条； B．至少n?1条；

C. 最多n条； D. 至少n条.

（6）任何无向图G中结点间的连通关系是（ B ） A. 偏序关系； B．等价关系；

C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系.

（7）对于无向图，下列说法中正确的是. （ B ） A．不含平行边及环的图称为完全图

B．任何两个不同结点都有边相连且无平行边及环的图称为完全图 C．具有经过每条边一次且仅一次回路的图称为哈密尔顿图 D．具有经过每个结点一次且仅一次回路的图称为欧拉图

（8）设D是有向图，则D强连通的充分必要条件为. ( C ) A．略去D中各边方向后所得到的无向图是连通的

B．D是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图 C．D的任意两个不同的结点都可以相互到达 D．D是完全图

（9）对于无向图G，以下结论中不正确的是. （ A ） A．如果G的两个不同结点是连接的，则这两个结点之间有初级回路 B．如果G的两个不同结点是连接的，则这两个结点之间至少有一条短程 C．如果G是树，则任何两个不同结点之间有且仅有一条初级通路

D．如果G是欧拉图，则G有欧拉回路

三、填空题

1. 设树T中有7片树叶，3个3度结点，其余都是4度结点，则T中有个4度结点. 解用握手定理和树的性质列出方程求解，设有x个4度结点，

7?9?4x?2(7?3?x?1)，x?1

2.设T??V,E?为树，T中有4度，3度，2度分支点各1个，问T中有片树叶。解与上题解法相同，设有x片树叶，4?3?2?x?2(3?x?1)，x?5 3.n阶完全图的任意两个不同结点的距离都为．1 4.图G为n阶无向完全图，则G共有条边。n(n?1)/2 5.设G为(n,m)图，则图中结点度数的总和为。2m

6. 图G为欧拉图的充分必要条件是_____________________. G为无奇度结点的连通图四、解答题

1. 对下图所示的图G，求（1）G的邻接矩阵A；

（2）G的结点v1,v3之间长度为3的通路；（3）G的连接矩阵C；（4）G的关联矩阵M。

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中，回答下列问题

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

（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

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没有欧

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

第四章数理逻辑

一、判断题（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．如果雪不是白的，则太阳从东边出来

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

Word文档下载：北邮离散数学期末复习题[1]1.doc

搜索更多:北邮离散数学期末复习题[1]1