2023年7月19日发(作者：)

离散数学期末复习题

第一章集合论

一、判断题

（1）空集是任何集合的真子集． （ 错 ）

是空集． （ 错 ） （2）{a},a （ 对 ） （3）a1,2,1,2,则1,22. ( 对 ） （4）设集合AA（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}，

AA2A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为集合，若AB，则一定有 （ C ）

A.

B B．B C.

AB D.

AB

（3）下列各式中不正确的是 （ C ）

 C.

 D.

,{} A.

 B．（4）设Aa,{a}，则下列各式中错误的是 （ B ）

{a}2

{a}2A D.

A.

a2 B．a2 C.

AAA1,2，Ba,b,c，Cc,d，则A(BC)为 （ B ） （5）设AA.

c,1,2,c B．1,c,2,c

C.

1,c,c,2 D.

c,1,c,2

1,b,3，则AB的恒等关系为 （ A ） （6）设A0,b，B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．#2A2#A

B．X2XA

A2 C．AD．A2

A（12）设A是有限集（#An），则A上既是又是～的关系共有（ B ）.

A．0个

B．1个

C．2个

D．n个

三、填空题

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

填2{,{1},{2},{{1,2}},{1,2},{1,{1,2}},{2,{1,2}},A}

A2.设A{,{}}，则2= . 填2{,{},{{}},A}

AAA3.设集合A,B中元素的个数分别为#A5，#B7，且#(AB)9，

则集合AB中元素的个数#(AB) .3

4.设集合A{x|1x100,x是4的倍数，xZ}，

B{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又由于

100100

011011（2）从的关系矩阵可知：是自反的和对称的。

1100111001

MM0011000110或满足

所以是传递的。

1001100101100110100100M

011011 因为是自反的、对称的和传递的，所以是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）

1111111101111101101110010111

0001010000011100000100000001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. （ 错 ）

222（6）设G,是群．如果对于任意a,bG，有

(ab)ab，则G,是阿贝尔群． （ 对 ）

（7）设L,,是格,则运算满足幂等律. （ 对 ）

（8）设集合A{a,b}，则{,{a},{b},A},,是格． （ 对 ）

（11）<{0，1，2，3，4}，max，min>是格． （ 对 ）

5 （9）设B,,,是布尔代数，则B,,是格． （ 对 ）

（10）设B,,,是布尔代数，则对任意a,bB，有

abab． （ 对 ）

二、单项选择题

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

A.

abab B．abmax{a,b}

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

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

1,2,3,4,,10，下面定义的哪种运算关于集合A不是封闭的 （3）设集合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，·是阿贝尔群

6 D．如果A，·是阿贝尔群，则A，·必不是循环群

（7）循环群Z,的所有生成元为 （ D ）

A. 1，0 B．-1，2 C. 1，2 D. 1，-1

三、填空题

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

2.代数系统Z,中（其中Z为整数集合，+为普通加法），对任意的xI，其Ax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

26.设G,是群，e为单位元，若G元素a满足aa，则a .填e

四、解答题

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

: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） 说明运算是否满足交换律、结合律，是否有单位元和零元、如果有请指出；

7

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 ,有

ab(ab) .

证明：充分性

若在群G,中，对任意的a,bG ,有ab(ab) .

则

(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，由

2222222222(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是单位元；

8 （3）任意元素有逆元

对任意xZ，x

第三章 图论

一、判断题

（1）n阶完全图的任意两个不同结点的距离都为1. （ 对 ）

（2）图G的两个不同结点vi,vj连接时一定邻接. （ 错 ）

（3）图G中连接结点vi,vj的初级通路为vi,vj之间的短程. （ 错 ）

（4）在有向图中，结点vi到结点vj的有向短程即为vj到vi的有向短程．

（ 错 ）

（5）强连通有向图一定是单向连通的． （ 对 ）

（6）不论无向图或有向图，初级回路一定是简单回路． （ 对 ）

（7）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的．

（ 对 ）

（8）设A是某个无向图的邻接矩阵，则AAT(AT是A的转置矩阵)．

（ 对 ）

（9）设有向图D的可达矩阵为

16x.所以,Z，是群.

10

P00111111

011001则G是单向连通的． （ 对 ）

（10）有生成树的无向图是连通的． （对）

（11）下图所示的图是欧拉图. （ 错 ）

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

二、单项选择题

9 （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有欧拉回路

（10）设简单无向图G的邻接矩阵为A(aij)nn,记A(aij)nn(l1,2,），则正确的是. （ C ）

A．当vi,vj是G的两个不同结点时,aij为vi,vj之间长度为l的初级通路条数

B．当vi,vj是G的两个不同结点时,aij为vi,vj之间长度为l的简单通路条数

C．当vi,vj是G的两个不同结点时,aij为vi,vj之间长度为l的的通路条数

(l)D．当vi是G的结点时,aii为通过vi的长度为l的初级回路条数

l(l)(l)(l)(l)（11）

MmijnmviV是G中的孤立点，是无向图GV,E的关联矩阵，则（ A ）

A.

vi对应的一行元素全为0； B．vi对应的一行元素全为1；

10 C.

vi对应的一列元素全为0； D.

vi对应的一列元素全为1.

三、填空题

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有6结点，若各结点的度数分别为：1，4，4，3，5，5，则G共有 条边。

用握手定理

222m，m=11

7. 图G为欧拉图的充分必要条件是_____________________. G为无奇度结点的连通图

四、解答题

1.

对下图所示的图G，求

（1）G的邻接矩阵A；

（2）G的结点v1,v3之间长度为3的通路；

（3）G的连接矩阵C；

（4）G的关联矩阵M。

v1v10v21解 （1） A=v31v41v50（2） 因为

v2v3v4v510001

1.007,

31 A2=212121232212411, A3=21211112所以，结点v1,v3之间长度为3的通路共有7条，它们是

11

v1v3v1v3,v1v2v5v3,v1v2v1v3,v1v4v1v3,v1v3v5v3,v1v3v2v3,v1v3v4v3.

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

v1v2v3v4v5

v11v21 C=v31v41v51（4）

e111111e211111e311111e4111.

11e5e6e7

v11v21 M=v30v40v501010.

012. 在下面的有向图D中，回答下列问题

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

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

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

01解：（1）A000000101000110

0001101012 00（2）A2001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没有欧拉回路，因而不是欧拉图。

第四章 数理逻辑

一、判断题

（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都是命题公式，则

13

(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

14