离散数学 ( 第1次 )

离散数学(第1次)离散数学(第1次)离散数学(第1次)资料仅供参考文件编号：2022年4月离散数学(第1次)版本号：A修改号：1页次：1.0审核：批准:发布日期：第1次作业

一、单项选择题（本大题共30分，共15小题，每小题2分）1.图G所示平面图deg(R3)为A.4B.5C.6D.32.在完全m叉树中，若树叶数为t，分枝点数为i，则有（）。A.(m-1)i<t-1

B.(m-1)i>t-1

C.(m-1)i=t-1D.(m-1)i≤t-13.命题a）：如果天下雨，我不去。写出命题a）的逆换式

。A.如果我不去，天下雨。B.如果我去，天下雨。C.如果天下雨，我去。D.如果天不下雨，我去。4.设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点（）A.5B.4C.2D.65.假设A={a,b,c,d},考虑子集S={{a,b},{b,c},{d}}，则下列选项正确的是（）。A.S是A的覆盖B.S是A的划分C.S既不是划分也不是覆盖D.以上选项都不正确6.没有不犯错误的人。M(x)：x为人。F（x）：x犯错误。则命题可表示为（）。A.(∀x)(M(x)→F(x)B.(∃x)(M(x)⋀F(x)C.（∀x）(M(x)⋀F(x))

D.(∃x)(M(x)→F(x)7.命题逻辑演绎的CP规则为（）A.在推演过程中可随便使用前提B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果C.如果要演绎出的公式为B→C形式，那么将B作为前提，演绎出CD.设∅(A)是含公式A的命题公式，B<=>A，则可以用B替换∅(A)中的A8.设G是有6个结点的完全图，从G中删去（）条边，则得到树。A.6B.9C.10D.159.设A、B两个集合，当（）时A-B=B。A.A=B

B.A⊆BC.B⊆AD.A=B=ϕ10.设U={1，2，3，4，5}，A={2，4}，B={4，3，5}，C={2，5，3}，确定集合(A-C)-B=（）。A.{1,4}

B.{2,3,4,5}

C.{4}D.ϕ

11.下图的最小生成树的权为（）。A.40

B.44C.48D.5212.对偶式为P↑Q表达式是

。A.P∧QB.P↓QC.P∨QD.P→Q13.下列语句是命题，并且真值为0的是（）A.雪式白的。B.1+2>4。C.天气真好啊！D.我正在说谎。14.如果有限个数的乘积为零，那么至少有一个因子等于零。N(x)：x是有限个数的乘积。Z(y)：y为0。P（x）：x的乘积为0。F（y）：y为乘积中的一个因子则命题可表示为（）。A.(∃x)(N(x)→P(x)∧(∃y)(F(y)⋀(Z(y)))B.(∃x)(N(x)⋀P(x))→(∃y)(F(y)⋀(Z(y)))C.(∃x)(N(x)→P(x)∧(∃y)(F(y)→(Z(y)))D.(∀x)(N(x)→P(x)∧(∃y)(F(y)⋀(Z(y)))15.设A、B、C是任意集合，判断下述论断是否正确，并将正确的题号填入括号内（）。A.若A∪B=A∪C，则B=C

B.若A∩B=A∩C，则B=CC.若A-B=A-C，则B=C

D.若∼A=∼B，则A=B

二、多项选择题（本大题共20分，共5小题，每小题4分）1.两个命题变元P和Q生成的4个小项为：

。A.P∧QB.┐P∧QC.P∧┐QD.┐P∧┐Q2.下图是（）。A.是强连通的

B.是弱连通的C.是单侧连通的

D.是不连通的3.

下列说法正确的是（）A.设<Z,+>是整数加法群，令f:n→-n,∀n∈Z，则f是Z的一个自同构映射。B.设G是一个Abel群，令f:a〖→a〗^(-1)(∀a∈G)，则f是G的一个自同构映射。C.设<R^,∙>是实数乘法群，<R,+>是实数加法群，令f:x→5x，则f是R的一个满同态映射D.A、B、C都是正确的。4.函数f：R×R→R×R,f(<x，y>)=<x+y，x-y>是(

)函数。A.入射B.满射

C.双射

D.以上答案都不对5.设A={1,2,3}，则集合A上的关系R={<1,1>,<1,3>,<2,1>,<2,3>}是（

）关系；A.自反B.反自反C.不是自反D.不是反自反

三、判断题（本大题共20分，共10小题，每小题2分）

1.判断对错：集合{2,3,4，•••}是无限集（）。

2.设G是一个联结词的集合，若任意一个命题公式都可用G中联结词构成的公式来表示，则称G为最小联结词组。

3.公式∀xP(x)→∃yQ(x,y)的前束范式是∀x∀y(P(x)→Q(x,y)。

4.判断对错。一个谓词公式wffA,如果在一种赋值下为假，则称该wffA为不可满足的。

5.下图中（c）和（d）是根树

6.设f∶{x,y}→{1,3,5}定义为f(x)=1,f(y)=5，则这个函数是入射函数。

7.设集合A={216，243，357，648}.定义A上的关系R={〈x,y〉|x,y∈A，且x与y中至少有一个相同数字}。则R是A上的一个相容关系，R不是等价关系。

8.自反（对称、传递）闭包是包含R的最小自反（对称、传递）关系。（）

9.设X={1,2,3,4},Y={1,2,3,4,5},Z={1,2,3},f:X→Y,f={,,,},g:Y→Z,g={,,,,}，则g°f={,,,}。

10.设R是由A={1,2,3,4}到B={2,3,4}的关系，S是由B到C={3,5,6}的关系，分别定义为：R={│a+b=6}={,,}S={│b整除c}={,,}于是复合关系R°S={,,}。

四、计算题（本大题共20分，共4小题，每小题5分）1.

设f,g均为实函数，f(x)=2x+1,

g(x)=x^2+1。求f°g

,

g°f

,

f°f

,

g°g

。

2.设集合A={1,2,3,4}，A上的二元关系R={(x,y)|x,y∈A,且x≥y},求R的关系图与关系矩阵3.

试将公式P∧（P→Q）化为析取范式和合取范式：4.设全集合E={a，b，c，d，e}，A={a，d}，B={a，b，e}，C={b，d}，求下列集合：(1)A∩～B；

（2）（A∩B）∪～C；（3）～A∪（B－C）；（4）ρ(A)∩ρ(B)

五、证明题（本大题共10分，共2小题，每小题5分）1.符号化下列命题并推证其结论：科学家都是勤奋的。每个勤奋又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以存在着事业获得成功的人或事业半途而废的人。2.设整数集Z上的二元关系R定义如下：R={<x,y>|x,y∈Z,(x-y)/2是整数，证明R在Z上是自反的。

答案：

一、单项选择题（30分，共15题，每小题2分）

1.B2.C3.A4.B5.A6.A7.C8.C9.D10.D11.C12.B13.B14.B15.D

二、多项选择题（20分，共5题，每小题4分）

1.ABCD2.BC3.AB4.ABC5.CD

三、判断题（20分，共10题，每小题2分）

1.√2.×3.×4.×5.√6.√7.√8.√9.√10.√

四、计算题（20分，共4题，每小题5分）

1.

参考答案：f°g(x)=2(x^2+1)=2x^2+3

g°f(x)=〖(x^2+1)〗^2+1=4x^2+4x+2

f°f(x)=2(2x+1)+1=4x+3

g°g(x)=〖(x^2+1)〗^2+1=x^4+2x^2+2所以f°g={<x,2x^2+3>|x∈R}g°f={<x,4x^2+4x+2>|x∈Rf°f={<x,4x+3>│x∈R}g°g={<x,x^4+2x^2+2>|x∈R}

解题方案：

评分标准：

2.

参考答案：R={(x,y)│x,y∈A,且x≥y}={(1,1),(2,1),(3,1),(4,1),(2,2),(3,2),(4,2),(3,3),(4,3),(4,4)

R的关系图如图3-1所示。

解题方案：

评分标准：

3.

参考答案：

┐（P∨Q）↔（P∧Q）=(﹁（P∨Q）→（P∧Q）)∧(（P∧Q）→┐（P∨Q）)(等值律)=(（P∨Q）∨（P∧Q）)∧(┐（P∧Q）∨┐（P∨Q）)

(蕴涵律)

=（P∨Q）∧(┐P∨┐Q)

(分配律)合取范式=(┐P∨P)∨(┐P∨Q)∨(┐Q∧P)∨(┐Q∧Q)

(分配律)析取范式

解题方案：

评分标准：

4.

参考答案：（1）A∩～B={a，d}∩{c，d}={d}.(2)（A∩B）∪～C={a}∪{a,c,e}={a,c,e}.（3）～A∪（B－C）={b,c,e}∪{a,e}={a,b,c,e}.