离散数学B卷及答案文档格式.docx

资源描述

离散数学B卷及答案文档格式.docx

《离散数学B卷及答案文档格式.docx》由会员分享，可在线阅读，更多相关《离散数学B卷及答案文档格式.docx（13页珍藏版）》请在冰点文库上搜索。

离散数学B卷及答案文档格式.docx

P（a）AP（b）AS（a）VS（b）

下列选项中错误.的是（

』？

€?

-{?

}

€{?

7.设A={a,b,c,d},A上的等价关系R={<

a,b>

b,a>

c,d>

d,c>

}UIa,则对应于R的A的划分是（）

A.{{a},{b,c},{d}}B.{{a,b},{c},{d}}

C.{{a},{b},{c},{d}}D.{{a,b},{c,d}}

8.设R为实数集，函数f:

RfR,f（x）=2x，则f是（）

双射函数

D.非入射非满射

设R为实数集，R+={x|x€RAx＞0},*是数的乘法运算，＜R+,*＞是一个群，则下列集合关于数的乘法运算构成该群的子群的是（

10.

{R坤的有理数}

{R+中的自然数}D.

下列运算中关于整数集不能构成半群的是（

{R坤的无理数}

{1,2,3}

ab=max{a,b}

ab=b

ab=2ab

ab=|a-b|

11.设z是整数集，+,•分别是普通加法和乘法，则（Z,+,）是（

A.域

B.整环和域

C.整环

D.含零因子环

12.设A={a,b,c},R是A上的二元关系，R={<

a,a>

a,c>

c,a>

}，那么R是（

A.反自反的

B.反对称的

C.可传递的

D.不可传递的

13.设D=<

V,E>

为有向图，V={a,b,c,d,e,f},E={<

b,c>

a,d>

d,e>

f,e>

A.强连通图

B.单向连通图

C.弱连通图

D.不连通图

14.在有n个结点的连通图中，其边数（

A.最多有n-1条

B.至少有n-1条

C.最多有n条

D.至少有n条

15.连通图G是一棵树，当且仅当G中

A.有些边不是割边

B.每条边都是割边

C.无割边集

D.每条边都不是割边

二、填空题（本大题共10小题，每小题

2分，共20分）

请在每小题的空格中填上正确答案。

错填、不填均无分。

16.任意两个不同的小项的合取为式，全体小项的析取式必为

式。

17.公式x（P（x）tQ（x,y）VszR（y,z））S（x）中的自由变元为，约束变元

为。

18.设集合M={x|1<

xw12,x被2整除，x€Z},N={x|1<

12,x被3整除，x€Z}，则

MnN=,MUN=。

19.设X={1,2,3},f:

XtX,g:

XtX,f={<

1,2>

2,3>

3,1>

g={<

3,3>

}，则fg=,gf=。

20.设A={a,b,c},R是A上的二元关系，且给定R={<

a,b>

b,c>

c,a>

}，则R的自反闭包

r（R）=，对称闭包s（R）=。

21.设Q为有理数集，笛卡尔集S=QXQ,*是S上的二元运算，-<

x,y>

€S,

ax,y+b>

则*运算的幺元是。

弋<

€S,若a*0,

贝H<

的逆元是。

22.设*是集合S上的二元运算，若运算*满足且存在,

则称<

S,*>

为独异点。

23.

24.如下无向图割点是

令A={a,b,c},<

A,*>

是循环群，a是单位元，则b=,c的阶是

28.给定图G如下所示，

（1）写出G的可达矩阵；

（2）G中长度为4的路有几条?

29.求下列公式的主析取范式和主合取范式：

（P-Q）A（QtR）

30.设A为54的因子构成的集合，R二AXA,-x,y€A,xRyx整除y。

画出偏序集<

A,R>

的哈斯图，并求A中的最大元，最小元，极大元，极小元。

五、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）

31.设R是A上的一个自反关系，证明：

R是一个等价关系，当且仅当若<

€R,<

a,c>

€R,贝U<

€R。

32.设<

G,*>

是一个群，x€G,定义：

ab=a*x*b,-a,b€G。

证明：

G,、也是一个群。

33.设图G是具有6个结点，12条边的无向简单图，证明图G是汉密尔顿图。

五、应用题（本大题共2小题，第34小题8分，第35小题7分，共15分）

34.构造下面推理的证明。

如果今天是星期六，我们就要到颐和园或圆明园去玩。

如果颐和园游人太多，我们

就不去颐和园玩。

今天是星期六，颐和园游人太多，所以我们去圆明园玩。

35.n个城市用k条公路的网络连结。

一条公路定义为两个城市间的一条不穿过任何中间城

市的道路。

任意两个城市之间至多修一条公路。

证明如果-1）（n-2），则人们总能通

过连结的公路，在任何两个城市间旅行。

武汉理工大学《离散数学》考试试题（B卷）答案

一、单顼选择甄（本犬砸共沾小題.誓小题I分■発15分）

l.DTC3A4.C5.B6.07』8,H9A2D

H.CLID13.CBIS.B

二J*空題（本大题共iO小邇,毎小麵2分，共20分〕

畑才感掘言17亠y「丄

18{6,12}1*330.12}

19.{<

L3>

2j<

3,1>

}{<

13>

23>

20.{<

a|hb>

bte>

ftta>

b,b>

e,c>

aTb>

bta>

・<

bFc>

c+b>

c+a>

・>

2t<

1（»

农丄，-h>

22•结合疣幺元23-c3

■3

24.d®

25.G连通带权地小

三』十算甌（本大題共3小题，第恋覆卞小0^5分.第2^29小题各6分、第孔小题S分■扶30分）

26.辭：

的关系矩阵为:

魁J

■1

I）1!

100II

001

000

PQR

IPV^

Q—ft

（1PVQ）A（O-*R）

IKPA1R）

G01

■1

0I0

011

300

—i

J01

110

0「

111

R•但＜bj＞僅乩故FL不具备传递性「不是偏序（35»

U分）

（2）因为电

关赛*

0000]'

10100

28.解

（1）G的邻接矩阵为

00001

.01010-

（1分｝

01010-

■2020

00002

0202

则A2=

01010

A3=

2020

.20200.

0000

F21215'

11Ir

52522

1111

故R'

21215

11II

.25254,

1111.

（2）G中长度为4的路有眈条°

29,解:

原式^（IPVQ）A（IQVR）

00004-

40400

A4=00004

L04040-

{4分）

（1分）

^（lPVQV（RAlR））A（1QVRV（PA1P））

e=>

（lPVQVR）A（lPVQVlR）A（PVIQVR）A（IPVIQVR）^（415t2,6）^ir（214,5l6）（3分）

（1PA1QA1R）V（IPAIQAIQAR）V（lPAQAR）V（PAQAR）n》（0」』,7）（3分）

30*解：

刊的因子集合为｛1,2,3,6,9,1趴27,54｝（1分）

AtR>

的哈斯图如下：

A中最大元54,最小元扱大元54,极小元

（4分）

四、证明題（本大题共3小题•第n、32小题各6分，第33小题8分，其20分）

31.证明:

必要性。

R是等价关系，若<

a（b>

€R,<

a,c>

eR,由R的对称性知:

eR,<

丘R,再由R的传递性知：

eR.,（3分）

充分性。

首先N是為上的自反关系，其次若<

eR,由R的自反性知:

aTa>

eR,再由已知条件知：

bta>

eRt因而R是对称的。

再次若<

atb>

eRt<

b,c>

由R的对称性知：

b,a>

b,c>

wR,由已知条

件知cR,因而R是传递的'

所以R是一个等价关系口（3分）

32.证明:

显然，堤G上的二元运算*要证G咼群*需证明结合律成立，同时存在单位

元和每个元素都有逆元©

藹散数学试題答案及评分参考第2页（共4页）

Vatb,ceG,^（aeb）<

c=（a*R*b）«

it*c=u?

x*（b*x*c）=g<

（btc）可知运算是可结合的n（2分）

其灯円是（g「）的单位元。

事实上，有

aflt"

1=a*x*J£

_1=atx'

l=a=x*]»

x*a=a（2分）

U§

MeG,宀狎"

Y是a在（G八）中的逆元。

寧实上，

ak*ad）t）=a*xxfa中k=x

（1_17"

（讥aSJ5（2分）

由ia±

E明可知是够。

33.证明:

已知一个图是汉密尔顿图的充分条件是:

囹中任总不同两点的度数之和大于

等于％（2分）假设圈中存在测亍结点“,其度数之和不大于尊于6,即dtvj

+dg）w5°

删去这两个点后.至多硼去图C中的5条边。

（3分）由于関G杲具

有6个结点」2条边的无向简单囲，创去结点叫，巾后'

需到的子阴为:

具有4个结

点•至少7条边的无向简单图.但这样的无向简单图不存在，由此证明图C中任意

两个不同结点的度數之和大于等于6,囹心是汉密尔顿图°

（3分）

五、应用題（本大题共2小题，第34小题8分僅35小题7分，共15分）

（2分）

弭解:

令P：

今天是星期六Q：

我们到颐和园玩R；

我们到闊明园折

头颐和园游人太多

前提:

P->

QVR（S->

1Q.PtS

结论:

证明:

①J1Q

P（前提引人）

②S

P（前摄引人）

③1Q

T®

[

④PtQVR

⑤F

@QVR

⑦R

35.证明:

把威市作为结点，城市间的公路作为结点闾的边，宙此构成图GoG有n个

结点花条边©

用反证注证明°

假设G中有两结点ii.w,从v不能疑过边到达-不妨•设®

为G中能劃达>

1的结点集厲为G中不能到达u的结点集。

则有ueV|tvevlo（2分）设G[=<

v（fE,>

tC3=<

vaREa>

为E的子图，显Ivj|+|v,|=nJEj1+1石"

虬

设[%I=m,则|EjWm（E-l）/2f|E3|^（n-m）（n-ni-l）/2■所以It=|&

|Ej|Wm（m-1）/2+（n-m）（n

-m-t）/2=y*（n1

-n-2mn+2mz）

又因为mSd,nMm十打所以山-1）（n-m-1）^Ot故tnn-n?

-n*】鼻0*即*

mn+m2-n+10代人k<

--（n3-n-2nm+2m*），得kn1-n-2n+2）=

离懺数学试題答案及评分参考策3页（共4页）

*（且-1）5-2）,这与题设k>

y（n-l）（n-2）矛倩*

矛盾说明图中任两结点可以相互达到，闖人们总能通过连结的公路在任何葡牛城市间雄行.（2分）

离戳数学试题答案及评分参考第4頁（共4頁）

展开阅读全文