2023年离散数学形成性考核全部答案

本文格式为Word版，下载可任意编辑——2023年离散数学形成性考核全部答案离散数学形成性考核作业（一）

参考答案

第1章集合及其运算

1．用列举法表示“大于2而小于等于9的整数〞集合．{3,4,5,6,7,8,9}。

2．用描述法表示“小于5的非负整数集合〞集合．{x∣x∈Z∧0≤x≤5}。

3．写出集合B={1,{2,3}}的全部子集．{}，{1}，{{2,3}}，{1,{2,3}}。

4．求集合A={?,{?}}的幂集．Φ，{Φ}，{{Φ}}，{Φ，{Φ}}。

5．设集合A={{a},a}，命题：{a}?P(A)是否正确，说明理由．

错误。P(A)中无元素a。6．设A?{1,2,3},B?{1,3,5},C?{2,4,6},求

(1)A?B(2)A?B?C(3)C-A(4)A?B

（1）{3}；（2）{1，2，3，4，5，6}；（3）{4，6}；（4）{2，5}。

7．化简集合表示式：((A?B)?B)-A?B．

((A∪B)∩B)-A∪B=（B-A）∪B=（B∩～A）∪B=B。

1

8．设A,B,C是三个任意集合，试证：A-(B?C)=(A-B)-C．

A-(B∪C)=A∩～(B∪C)=A∩～B∩～C=(A-B)–C。9．填写集合{4,9}?{9,10,4}之间的关系．

10．设集合A={2,a,{3},4}，那么以下命题中错误的是（A）．A．{a}?AB．{a,4,{3}}?AC．{a}?AD．??

A

11．设B={{a},3,4,2}，那么以下命题中错误的是（B）．A．{a}?BB．{2,{a},3,4}?BC．{a}?BD．{?}?B

第2章关系与函数

1．设集合A={a,b}，B={1,2,3}，C={3,4}，求A?(B?C)，(A?B)?(A?C)，并验证A?(B?C)=(A?B)?(A?C)．A×(B∩C)={a,b}×{3}={,}；

（A×B）∩（A×C）={,,,,,}∩

{,,}={,}

验证了A×(B∩C)=（A×B）∩（A×C）。

2

2．对任意三个集合A,B和C，若A?B?A?C，是否一定有B?C？为什么？

当A是空集时，不一定有B?C。当A不是空集时，一定有B?C。

x∈A，y∈B，∈A×B，∈A×C，y∈C。即B?C。3．对任意三个集合A,B和C，试证若A?B=A?C，且A?则B=C．

x∈A，y∈B，∈A×B，∈A×C，y∈C。即B?C；同理：C?B，B=C。

4．写出从集合A={a，b，c}到集合B={1}的所有二元关系．Φ，{}，{}，{}，{,}，{,},

{,}{,,}。

5．设集合A={1，2，3，4，5，6}，R是A上的二元关系，R={?a,

?，

b??a,b?A,且a+b=6}写出R的集合表示式．

{,,,,}。

6．设R从集合A={a，b，c，d}到B={1，2，3}的二元关系，写出关系

R={?a,1?，?a,3?，?b,2?，?c,2?，?c,3?}的关系矩

阵，并画出关系图．

?1?0MR=??0??0

01101??0?1??0?

3

7．设集合A={a,b,c,d}，A上的二元关系

R={?a,b?，?b,d?，?c,c?，?c,d?}，S={?a,c?，?b,d?，?d,b?，?d,d?}．

求R?S，R?S，R-S，~（R?S），R?S．

R∪S={，，，，，，}；

R∩S={}；

R-S={，，，}；

～(R∪S)={，，，，，，，

，}；

R?S={，，，，，}；8．设集合A={1,2}，B={a,b,c}，C={?,?}，R是从A到B的二元关系，S是从B到C的二元关系，且R={，，}，S={，}，用关系矩阵求出复合关系R·S．MR·S=MR·MS=??1?010?00????01???01???01????00??1??；0?R·S={}

9．设集合A={1,2,3,4}上的二元关系

R={?1,1?，?1,3?，?2,2?，?3,1?，?3,3?，?3,4?，

?4,3?，?4,4?}，

4

判断R具有哪几种性质？自反性、对称性、传递性。

10．设集合A={a,b,c,d}上的二元关系

R={?a,a?，?a,b?，?b,b?，?c,d?}，

求r(R)，s(R)，t(R)．

r（R）={〈a，a〉，〈a，b〉，〈b，b〉〈c，c〉，〈c，d〉，〈d，d〉}；

s（R）={〈a，a〉，〈a，b〉，〈b，a〉〈b，b〉，〈c，d〉，〈d，c〉}；t（R）={〈a，a〉，〈a，b〉，〈b，b〉〈c，d〉}。

11．设集合A={a,b,c,d}，R，S是A上的二元关系，且R={,,,,,,,}

S={,,,,,,,,}

试画出R和S的关系图，并判断它们是否为等价关系，若是等价关系，则求出A中各元素的等价类及商集．

R是等价关系，A/R={[a]，[c]}。S不是等价关系。12．图1.1所示两个偏序集?A，R?的哈斯图，试分别写出集合

A和偏序关系R的集合表达式．

dba(1)

图1.1题12哈斯图

efcg

bcfda(2)

eg5

A={a，b，c，d，e，f，g}。

R={，，，，，，

，，，}∪IA。

S={，，，，，，}∪IA。

13．画出各偏序集?A，?1?的哈斯图，并指出集合A的最大元、最小元、极大元和微小元．其中：A={a,b,c,d,e}，

?1={?a,b?，?a,c?，?a,d?，?a,e?，?b,e?,?c,e?，

?d,e?}?IA；

集合A的最大元e、最小元a、极大元e和微小元a。14．以下函数中，哪些是满射的？那些是单射的？那些是双射的？

(1)f1：R?R，f(a)=a3+1；

?0,(2)f4：N?{0,1}，f(a)=??1,a为奇数a为偶数．

（1）双射；（2）满射。

15．设集合A={1,2}，B={a,b,c}，则B?A={，，，

，，}．

16．设集合A={1，2，3，4}，A上的二元关系

6

R={?1,2?，?1,4?，?2,4?，?3,3?}，S={?1,4?，?2,3?，?2,4?，?3,2?}，

则关系（B）={?1,4?，?2,4?}．

A．R?SB．R?SC．R-SD．S-R

17．设集合A={1,2,3,4}上的二元关系R={?1,1?，?2,

a3?，?2,4?，?3,4?}，则R具有（）．A．自反性B．传递性C．对称性D．反自反性

bced图1.2题18哈斯图

18．设集合A={a,b,c,d,e}上的偏序关系的哈斯图如图1.2所示．则A的极大元为a，微小元为c、d．

19．设R为实数集，函数f：R?R，f(a)=-a2+2a-1，则f是（D）．

A．单射而非满射B．满射而非单射C．双射D．既不是单射也不是满射

作业2三、四章无答案

第3章图的基本概念与性质

{0m2w;R1w

1．计算出下图2.1的结点数与边数，并说明其满足握手定理．5

7

H}5X%J*b;t4Z9|;}

9{-A:{Z5V;J

图2.1习题1的图

解：共有6个结点，6条边，图中从左上至右下的结点的度数分别为3、2、0、2、3、2，显然度数之和为12，即为边数的两倍，满足握

手定理．

7m%y8?@.D5d%w;u!D,H3．找出下图2.3中的路、通路与圈．

4]8x5E3b1q7F

图2.3习题3的图

解：对图2.3中的结点作标记如下：\

其中路有aca、acdc、bedc等，通路ac、acd、bedc等，圈有bedcb、

8

edcbe等．1\4．有n个结点的无向完全图的边数为1@3|%a2Q9b0r,n

．

5．图中度数为奇数的结点为数个．

6．已知图G的邻接矩阵为,?s;c*Z/\

，

则G有（）．A．5点，8边

B．6点，7边)U8T(_0T2o2]3l

C．5点，7边3m)i!Z[)@*n7g8D%i/`7N7S

D．6点，8边k:j:t8J$r!\

第4章几种特别图

1．如图2.8是否为欧拉图？试说明理由．

$A(K$e'l;L/Y+D4I:J

图2.8

判断是否为欧拉图'P/E!h2a+e!_3L'K:m7I解：图[font=?]2.8不是欧拉图，由于结点[font=?]2、v3、v4、v6的度数均不为偶数．9?4p;^7m8e*G

+l/u'm,S9Vv*Y5P

9

5;]v[font=?I(\

判断是否为平面图解：4.3（a）为平面图，可画为#l5^1n!?)r.@/h$W,]:o

（b）为平面图，可画为)g+c'u9v!y9o-d#J(b(O

（c）为平面图，可画为5?9r%o3y.w7r7k-r+r

4．若G是一个汉密尔顿图，则G一定是(c)．

A．欧拉图B．平面图C．连通图

10

5．设G是有n个结点m条边的连通平面图，且有k个面，则k等于(b)．;i6@1]*w%[7^4Y:s3p;G6A

A．m-n+2\

B．n-m-24J:u%j/h*Q4}$BC．n+m-2$F6g!@1X!R,M1u,e

D．m+n+2

:O7r+S.~/m1j/h,Z|)_

6．现有一个具有个奇数度结点的图，若要使图中有一条欧拉回路，

最少要向图中添加____k/2___条边．

第5章树及其应用

1．试指出图2.13中那些是树，那些是森林，并说明理由．

*M%N\

图2.13

习题1的图\

解：图中（a）、（c）是树，因（a）与（c）均为无回路的连通图．（b）是森林，因其包含两棵子树．（c）不是树也不是森林，因其包含回路．

2．试画出图2.14中的一个生成树，并说明其中的树枝、弦，以及对

应生成树的补．1R%i;U8vL-f7@6a/{)Ee0b;ia:H*n%?*b%z(_:x2p!p'w7n:f4g

3．给定一组权值为1，2，2，3，6，7，9，12，是求出相应的一个

最优树．

解：相应的一个最优树如下：

作业3

一、单项选择题

1．若集合A＝{2，a，{a}，4}，则以下表述正确的是()．A．{a，{a}}?AB．{a}?AC．{2}?AD．??A正确答案：B

2．若集合A={a，b，{1，2}}，B={1，2}，则（）．A．B?A，且B?AB．B?A，但B?A

12

C．B?A，但B?AD．B?A，且B?A正确答案：B

3．设集合A={1,a}，则P(A)=()．

A．{{1},{a}}B．{?,{1},{a}}C．{?,{1},{a},{1,a}}D．{{1},{a},{1,a}}正确答案：C

注意：若A是n元集，则幂集P(A)有2n个元素．

4．设集合A={1，2，3，4，5，6}上的二元关系R={?a,b??a,

b?A,且a+b=8}，则R具有的性质为（）．

A．自反的B．对称的

C．对称和传递的D．反自反和传递的正确答案：B

由于写出二元关系R的集合表达式为

R={?2,6?，?6,2?，?3,5?，?5,3?，?4,4?}

显然，R是对称的，不是自反的、反自反的、传递的．要求大家能熟练地写出二元关系R的集合表达式．5．设集合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．以上都不对

13

正确答案：C

想一想：R的自反闭包是什么？

假使集合A={1,2,3}，A上的二元关系R={|x?A，y?A，

x+y=8}，那么R的自反闭包是什么？请写出．

16．设集合A={1,2,3,4,5}上的偏序关系的哈斯图如右图所示，若A的子集B={3,4,5}，4235

则元素3为B的（）．

A．下界B．最大下界C．最小上界D．以上答案都不对正确答案：C?

二、填空题

1．设集合A有n个元素，那么A的幂集合P(A)的元素个数为．应当填写：2n

假使n=5,n=8，那么A的幂集合P(A)的元素个数分别是多少？

2．设集合A={1，2，3，4，5}，B={1，2，3}，R从A到B的二元关系，

R={?a,b??a?A，b?B且2?a+b?4}

则R的集合表示式为．

应当填写：R={?1,1?，?1,2?，?1,3?，?2,1?，?2,2?，

?3,1?}

14

3．设集合A={0,1,2}，B={0,2,4},R是A到B的二元关系，

R?{?x,y?x?A且y?B且x,y?A?B}

则R的关系矩阵MR＝．

?10应当填写：????11010??0?0??

由于R={,,,}，由此可以写出R的关系矩阵．

4．设集合A={a,b,c}，A上的二元关系

R={,}，S={,,}

则(R?S)－1=．应当填写：{,}

由于R?S={,}，所以(R?S)－1={,}．

5．设集合A=｛a,b,c,d｝，A上的二元关系R={,,,}，则二元关系R具有的性质是．应当填写：反自反的

6．设集合A={1,2}，B={a,b}，那么集合A到B的双射函数是．

应当填写：{,}，{,}

想一想：集合A到B的不同函数的个数有几个？

三、判断说明题（判断以下各题，并说明理由．）

15

1．设A、B、C为任意的三个集合，假使A∪B=A∪C，判断结论

B=C是否成立？并说明理由．

解：结论不成立．

设A={1,2}，B={1}，C={2}，则A∪B=A∪C，但B?C．

2．假使R1和R2是A上的自反关系，判断结论：“R-11、R1∪R2、R1?R2是自反的〞是否成立？并说明理由．解：结论成立．

由于R1和R2是A上的自反关系，即IA?R1，IA?R2．由逆关系定义和IA?R1，得IA?R1-1；由IA?R1，IA?R2，得IA?R1∪R2，IA?R1?R2．

所以，R1-1、R1∪R2、R1?R2是自反的．

3．判断“若偏序集??，R?的哈斯图如右图所示，则集合A的极大元为a，f；最大元不存在．〞是否正确，并说明理由．

a

解：正确

依照极大元定义：“若对任意a?B，且b?a，都有

fbdcea=b，则称b为B的极大元〞，可知a，f是A的极大元，

且最大元不存在．

想一想：“若偏序集??，R?的哈斯图如右图所示，则集合

A的最大元为a；最小元不存在．〞是否正确？

再给出一个判断说明题，大家要重视的。

想一想：“设N、R分别为自然数集与实数集，f：N→R，f(x)=x+6，

16

则f是单射．〞是否成立？并说明理由．

四、计算题

1．设集合A＝{a,b,c}，B={b,d,e}，求

（1）B?A；（2）A?B；（3）A－B；（4）B?A．解：（1）B?A={a,b,c}?{b,d,e}={b}（2）A?B={a,b,c}?{b,d,e}={a,b,c,d,e}（3）A－B={a,b,c}－{b,d,e}={a,c}

（4）B?A=A?B－B?A={a,b,c,d,e}－{b}={a,c,d,e}

2．设集合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的最大元、最小元．

解：（1）R=IA?{,,?,,,,,

12,,,,,,,,8}

10542639711

（2）

1关系R的哈斯图

17

（3）集合B没有最大元，最小元是：2

3．设集合A＝{a,b,c,d}上的二元关系R的ad关系图如右图所示．

bc（1）写出R的表达式；（2）写出R的关系矩阵；（3）求出R2．

解：（1）R＝{,,,}?1010??（2）M??0010?R??0000?

??0001??（3）R2={,,,}?{,,}

={,,}

五、证明题

1．试证明集合等式：A?(B?C)=(A?B)?(A?C)．

证：若x∈A?(B?C)，则x∈A或x∈B?C，即x∈A或x∈B且x∈A或x∈C．即x∈A?B且x∈A?C，即x∈(A?B)?(A?C)，

18

>,c所以A?(B?C)?(A?B)?(A?C)．

反之，若x∈(A?B)?(A?C)，则x∈A?B且x∈A?C，即x∈A或x∈B且x∈A或x∈C，

即x∈A或x∈B?C，即x∈A?(B?C)，

所以(A?B)?(A?C)?A?(B?C)．因此A?(B?C)=(A?B)?(A?C)．

想一想：等式A?(B?C)=(A?B)?(A?C)如何证明？

2．设R是集合A上的对称关系和传递关系，试证明：若对任意

a?A，存在b?A，使得?R，则R是等价关系．

证明：已知R是对称关系和传递关系，只需证明R是自反关系．任意a?A，存在b?A，使得?R，由于R是对称的，故?R；

又R是传递的，即当?R，?R，可以得到?R；

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

3．若非空集合A上的二元关系R和S是偏序关系，试证明：R?S也是A上的偏序关系．

证明：①任意x?A,?R,?S??R?S，所以R?S有自反性；

②对任意x,y?A，由于R，S是反对称的，由

?R?S且?R?S

?(?R且?S)且(?R且?S)?(?R且?R)且(?S且?S)

19

?x=y且y=x，

即x=y．所以，R?S有反对称性．

③对任意x,y,z?A，由于R，S是传递的，由?R?S且?R?S??R且?S且?R且?S

??R且?R且?S且?S??R且?S??R?S

所以，R?S有传递性．

总之，R?S是偏序关系.456题无答案作业4

第6章命题规律

1．判断以下语句是否为命题，若是命题请指出是简单命题还是复

合命题．（1）8能被4整除．

（2）今天温度高吗？!O2d8r'@6o4E2O(]

（3）今每日气真好呀！

（4）6是整数当且仅当四边形有4条边．\（5）小王是学生，但小李是工人．6d/{,U.Y$J2u1O8~

（6）除非下雨，否则他不会去．

解：（1）是简单命题，（4）（5）（6）是复合命题．

2．翻译成命题公式

（1）他不会做此事．5[(h0C/]'e;F(_

（2）他去旅游，仅当他有时间．\（3）小王或小李都会解这个题．!Te*b&B!j1V0H5t

20

（4）假使你来，他就不回去．（5）没有人去看展览．/I4b0C.TS/X

（5）设P：有人去看展览，公式为P．

（6）设P：他去看电影Q：他去观看了体育比赛，公式为PQ．1L;f\k-k'],ZH9p

3．设P，Q的真值为1；R，S的真值为0，求命题公式(P∨Q)∧R

∨S∧Q的真值．-T;D#p,n)\

解：(P∨Q)∧R∨S∧Q

(1∨1)∧0∨0∧1(p+],{3?|,v!Y#m/z#P

1）P→QP2w9s%\2）Q→RP)VJ!Y)D#q4S:^3）┐RP9|'t7m/F2[(Z

4）┐QT2）3）I5）┐PT1）4）I5．试求以下命题公式的主析取范式，主合取范式．（1）（P∨(Q∧R)）→(P∧Q)0mz;_2z)r,b-EG;`

解：┐(P→Q)∧Q┐(┐P∨Q)∧QP∧┐Q∧Q

F#l%h8~7?3S8Q+^)d3|0，1，2，3，4，5，6，7

6．利用求公式的范式的方法，判断以下公式是否永真或永假．7n.L1H6|8g3S%[7u

（2）（P∨Q）→R*\解：（P∨Q）→R.S1R(?)X1S4B8r7I

23

┐（P∨Q）∨R

（┐P∧┐Q）∨R6v*u+[)y*g1r8x

（┐P∧┐Q）∨R为析取范式，析取的两个合取式不会永真或永假，

所以此公式不是永真或永假式．

对其他一些公式也可以通过求主范式进行类似地判断．9i(Q8H%i.o8?)b

7．设P：昨每日晴，Q：前天下雨，则命题\昨每日晴，但前天下

雨\可符号化为（A）．

A．P∧QB．P→

QC．P∨QD．Q→P

8．可以确定下述推理的步骤（D）是正确的．A．（1）┐P∧QP

（2）PT（1）I

B．（1）P→QP

（2）QT（1）IC．（1）P∨QP(z\X^+o.M,q-a

D．（1）P∧QP

（2）PT（1）I(S+V7e_5P(v!d.D)[v5T+F4H(6)所有人都需要不断地努力学习，争取进步。+v

解：(1)设P（x）：x是人，Q（x）：x会来，2M1c7X:Y)v)m%b8y#x)W\

公式为（x）（P（x）→┐Q（x））．(2)设P（x）：x是人，Q（x）：x能做这件事，

公式为┐（x）（P（x）∧Q（x））．+t0ZB5S5Sm2p,d

(3)设P（x）：x是人，Q（x）：x能去，

公式为（x）（P（x）∧Q（x））∧┐（x）（P（x）→Q（x））．q;R+l.A(^.b

(4)设P（x）：x是人，Q（x）：x这样做，R（x）：x是事，S（x,y）：x能做y事，#B.A+z)z:x8g-C1d;s7U公式为（x）（P（x）→Q（x））→（y）（x）（R（y）→P（x）∧┐S（x,y））．4d9t,m)\(5)设P（x）：x

是人，Q（x）：x愿意做这件事，

25

公式为┐（x）（P（x）→Q（x））．

(6)设P（x）：x是人，Q（x）：x需要不断地努力学习，争取进

步，*{!E2P#]2u9@'`

公式为（x）（P（x）→Q（x））．B0X-L4P)i3_/|+S2\

2．设谓词A(x)：x是偶数，B(x)：x是奇数，x的取值为1至10

之间的正整数，试求出以下谓词公式的值．（1）（#x）A（x）∧（#x）B（x）．

解：（x）A（x）∧（x）B（x）$E+q%Q5b2w7H,b7u6l（A（1）∨A（2）∨A（3）∨A（4）∨A（5）∨A（6）∨A（7）∨A（8）∨A（9）∨A（10））∧（B（1）∨B（2）∨B（3）∨B（4）∨B（5）∨B（6）∨B（7）∨B（8）∨B（9）∨B（10））（0∨1∨0∨1∨0∨1∨0∨1∨0∨1）∧（1∨0∨1∨0∨1∨0∨1∨0

∨1∨0）

（1）∧（1）$L3E0h5a\

1．

（2）（x）（A（x）B（x））．*~'[8I2H)|)i)M!h1z:s6U类似可求

3．试证明以下公式#P%n:W(J7p3[8G%b*T1`%P（2）（x）（P（x）∧