电大离散数学形成性考核作业集合.docx

资源描述

电大离散数学形成性考核作业集合.docx

《电大离散数学形成性考核作业集合.docx》由会员分享，可在线阅读，更多相关《电大离散数学形成性考核作业集合.docx（29页珍藏版）》请在冰点文库上搜索。

电大离散数学形成性考核作业集合.docx

电大离散数学形成性考核作业集合

离散数学形成性考核作业

（一）

集合论部分

分校学号姓名分数

本课程形成性考核作业共4次,内容由中央电大确定、统一布置。

本次形考作业是第一次作业,大家要认真及时地完成集合论部分的形考作业,字迹工整,抄写题目,解答题有解答过程。

第1章集合及其运算

1．用列举法表示”大于2而小于等于9的整数”集合．

2．用描述法表示”小于5的非负整数集合”集合．

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

4．求集合A={,{}}的幂集．

5．设集合A={{a},a},命题:

{a}P（A）是否正确,说明理由．

6．设A{1,2,3},B{1,3,5},C{2,4,6},求

（1）AB

（2）ABC

（3）C-A（4）AB

7．化简集合表示式:

（（AB）B）-AB．

8.设ABC是三个任意集合

试证：

A-（BC）=（A-B）-C.

.填写集合{4,9}

{9,10,4}

之间的关系.

.设集合A={2,

a,{3},4},

那么下列命题中错误的是（）

.{a}AB.

{a,4,{3}}

AC.{a}AD.

11.设B={{a},3,4,2},那么下列命题中错误的是（）

第2章关系与函数

并验证A（BC）=（AB）（AC）.

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

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

bA,且a+b=6}写出R的集合表示式.

R={a,1,a,3,b,2,c,2,c,3}的关系矩阵，并画出关

系图.

.设集合

A={a,

b,c,

d},

A上的二元关系

R={

a,b,

d,c,c,

c,d},

S={

a,c,

d,d,b,

d,d}.

求R

S,RS,

R-S

8.设集合A={1,2},B={a,b,c},C={,},R是从A到B的二

元关系，S是从B到C的二元关系，且R={<1,a>,<1,b>,<2,c>},S={

>,},

用关系矩阵求出复合关系R-S.

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

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

={<

a,a>,<

b>,<

a>,<

b>,<

c>,<

d>,<

c>,<

d>}

={<

a,b>,<

a>,<

c>,<

a>,<

c>,<

b>,<

a>,<

b>,

c>}

试画出R和S的关系图，并判断它们是否为等价关系，若是等价关系，则求出A中

各元素的等价类及商集.

R的集合表示式.

i={a,b,a,c,a,d,a,e,b,e,c,e,d,e}Ia；

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

3,4},

则R具有（

）.

.自反性

.传递性

.对称性

.反自反性

.设集合

A={a,b,

c,d,e}

上的偏序关系的哈斯

图如图1.2所示.贝SA的极大元为,

极小元为

离散数学形成性考核作业

（二）

图论部分

本课程形成性考核作业共4次，内容由中央电大确定、统一布置。

本次形考作业是第二次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目,解答题有解答过程。

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

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

试分别画出下列图2.2（a）、（b）、（c）的补图.

3.找出下图2.3中的路、通路与圈.

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

7”

图2.3习题3的图

4.设G为无向图，|G=9,且G每个结点的度数为5或6,试证明G中至少有5个6度结点或至少有6个5度结点.

设有向图D=如图2.4所示，

试问图中是否存在长度分别为3,4,5,6的回路，如存在，试找出.

6.若无向图G有10条边，3度与4度结点均2个，其余结点的度数均小于3,试问G中至少有几个结点？

若无向图G中有6条边,3度与5度结点均有一个，其余结点的度数均是2,试问G中有几个结点？

7.试求图2.5中有向图的强分图，单侧分图和弱分图.

图2.5习题7的图

8试说明图2.6中G和G同构.

图2.6习题8的图

试求图2.7中的邻接矩阵与可达矩阵.

10.有n个结点的无向完全图的边数为

11.图中度数为奇数的结点为数个.

12.已知图G的邻接矩阵为

Io1r

I000I000111010111110

则G有（）.

A.5点,8边

C.5点,7边

第4章几种特殊图

1.试分别构造满足下列条件的无向欧拉图

（1）

有偶数个结点，

奇数条边.

（2）

有偶数个结点，

偶数条边.

（3）

有奇数个结点，

偶数条边.

（4）

有奇数个结点，

奇数条边.

2.分别构造满足下列条件的四个汉密尔顿图

（1）

偶数个结点，

奇数条边.

（2）

有偶数个结点

偶数条边.

（3）

有奇数个结点

偶数条边.

（4）

有奇数个结点

奇数条边.

3.试画出一个没有一条欧拉回路，但有一条汉密尔顿回路的图.

4.如图2.8是否为欧拉图？

试说明理由.

判断是否为汉密尔顿图

4.3（a）、（b）与（c）是否为平面图.

图2.10判断是否为平面图

8.试利用韦尔奇•鲍威尔算法分别对图2.12（a）、（b）与（c）着色.

图2.12图的着色

9.若G是一个汉密尔顿图，则G一定是（）.

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

10.设G是有n个结点m条边的连通平面图，且有k个面，则k等于（）

A.mn+2B.n-m2C.n+m2D.m+n+2

11.无向连通图G是欧拉图的充分必要条件是

12.设G是具有n个结点的简单图，若在G中每一对结点度数之和大于等于

则在G中存在一条汉密尔顿路.

13.现有一个具有k个奇数度结点的图，若要使图中有一条欧拉回路，最少要

向图中添加条边.

第5章树及其应用

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

的补.

3.试画出如图2.15的完全图&的所有不同构的生成树.

图2.15习题3的图

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

4.试求出图2.16中的最小生成树及其权值.

图2.16习题4的图

5.给定一组权值为1,2,2,3,6,7,9,12,是求出相应的一个最优树.

6.无向树T有7片树叶，3个3度结点，其余的都是4度结点，则T有（）个4度结点？

A.1B.2C.3D.4

7.无向树T有3个3度结点,2个4度结点，其余的都是树叶，则T有（）片树叶？

A.3B.7C.9D.11

8.无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点，其余的都是树叶，则T有（）片树叶？

B.14

C.16D

.20

无向树

T有9片树叶,5

个3度结点，其余的都是

4度结点，则T有几个4度

结占?

^1—1八、、・

B.1

C.2D

离散数学形成性考核作业（三）

集合论与图论综合练习

本课程形成性考核作业共4次,内容由中央电大确定、统一布置。

本次形考作业是第三次作业,大家要认真及时地完成图论部分的形考作业,字迹工整,抄写题目,解答题有解答过程。

一、单项选择题

1.若集合A={2,a,{

a},4},

则下列表述正确的是（）．

A.{a,{a}}?

.{a}iA

C.{2}?

．?

2.设B={{2},3,4,2},

那么下列命题中错误的是（）．

A.{2}B

．{2,{2},3,4}iB

C.{2}iB

．{2,{2}}iB

3．若集合A={a,b,{

1,2}},

B={1,2},则（）．

A．BiA,且B?

．B?

A,但B?

C．BiA,但B?

．B?

A,且B?

4．设集合A={1,a},

则P（A）

=（）．

A．{{1},{a}}

．{,{1},{a}}

C．{,{1},{a},{1,

a}}

D．{{1},{a},{1,a}}

5.设集合A={1,2,3,4,5,6}上的二元关系R={a,baa,bA,且

a+b=8},则R具有的性质为（）

.对称的

A.自反的

C.对称和传递的

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

.反自反和传递的

闭包.

R={a,

则R具有的性质为（）

C.反自反性，反对称性和传递性D.自反性，反对称性和传递性

9.设集合A={a,b},则A上的二元关系R={,}是A上的（）关系.

A.是等价关系但不是偏序关系B.是偏序关系但不是等价关系

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

10.设集合A

={1,2,3,4,5}

上的偏序关系独、

的哈斯图如右图所示

若A的子集B=

{3,4,5},45

则元素3为B的（

）.

A.下界B

.最大下界C

.最小上界D.以上答案都不对

11.设函数f:

RRf（a）=2

a+1;g:

RRg（a）=a2.则（）有

反函数.

A.g•f

•g

D.g

12.设图G的

【勺邻接矩阵「

为

则G的边数为（

）.

A.5B

13.

下列数组中，

能构成无向图的度数列的数组是

（）.

（1,1,2,3）

.（1,2,3,4,5）C

.（2,2,2,2）D.（1,

3,3）

.设图d

E>,

则下列结论成立的是（）

deg（V）=2?

B.deg（V）：

deg（v）2E

deg（v）

D.vV

15.

有向完全图D=

E>,则图D的边数是（

）.

A.?

（?

—1）/2B.?

（?

—1）/2

C.?

（?

—1）D.?

（?

16.给定无向图G如右图所示，下面给出的结点b集子集中，不是点割集的为（）

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

C.{a,c}D.{g,e}

A.e—v+2B.v+e—2C.e—v—2D.e+v+2

18.无向图G存在欧拉通路，当且仅当（）

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

A.G中所有结点的度数全为偶数

B.G中至多有两个奇数度结点

C.G连通且所有结点的度数全为偶数

D.G连通且至多有两个奇数度结点

19.设G是有n个结点，m条边的连通图，必须删去G的（）条边，才能确定

G的一棵生成树.

A.mnlB.mnC.mnlD.nm1

20.已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的

树叶数为.

A.8B.5

C.4

D.3

二、填空题

1.设集合A{1,2,2},B{1,2},

则AB=

AB=,A-B=

P（A）-P（B）=

2.设AB为任意集合，命题A-B=?

的条件是.

3.设集合A有n个元素，那么A的幕集合P（A）的元素个数为.

4.设集合A={1,2,3,4,5,6},A上的二元关系R{a，ba，bA且ab1},

则R的集合表示式为.

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

R={a,baaAbB且2a+b4}

则R的集合表示式为.

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

则R的关系矩阵Mt=

7.设集合A={1,2,3,4},B={6,8,12},A到B的二元关系

R={x,yy2x,xA,yB}

那么R1=

8.设集合A={a,b,c},A上的二元关系

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

则（R■S）_1=.

9.设集合A={a,b,c},A上的二元关系R={,,,},

贝廿二元关系R具有的性质是.

11.设集合A={1,2,3,4}上的等价关系

R={1,2,2,1,3,4,4,3}Ia.

那么A中各元素的等价类为.

11.设AB为有限集，且|A=m|B|=n,那末A与B间存在双射，当且仅

当.

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

13.

已知图G中有1个1度结点，2个2度结点,

G的边数是.

14.设给定图q如由图所示）,则图G的点

割集是.

15.设G=V,E＞是具有n个结点的简单图，若在G中每一对结点度数之和大于

等于，

则在G中存在一条汉密尔顿路.

16.设无向图G=＜VE＞是哈密顿图，则V的任意非空子集Vi,都有

17.设有向图D为欧拉图，则图D中每个结点的入度

18.

设完全图Kn有n个结点（n＞2）,m条

边，当时，Kn中存在欧拉回路.

19.图q如右图所示）带权图中最小生

成树的权是

20.连通无向图G有6个顶点9条边，从

G中删去条边才有可能得到G的一棵生成树T.

二、判断说明题

1.设A、B、C为任意的三个集合，如果AUB=AUC,判断结论B=C是否成立？

并说明理由.

2.如果R和R是A上的自反关系，判断结论：

”RS、RU艮、R?

R是自反

是否成立？

并说明理由.

3.设RS是集合A上传递的关系，判断

S是否具有传递性，并说明理由.

7.判断下图的树是否同构？

说明理由.

并说明理由.

.判别图q如下图所示）是不是平面图，并说明理由.

10.在有6个结点，12条边的简单平面连通图中，每个面有几条边围成？

为什

么？

四、计算题

[.设E{1,2,3,4,5},A{1,4},B{1,2,5},C{2,4},求：

（1）（A?

B）

（2）P（A）—RC）;（3）A?

（1）B?

（2）A出；（3）A-B;（4）B?

3.设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的最大元、最小元.

4.设集合A={a,b,c,d}上的二元关系：

貝的

关系图如右图所示.c

（1）写出R的表示式；

（2）写出R的关系矩阵；

（3）求出氏.

5.设A={0,1,2,3,4},R={vx,y>|x?

Ay?

A且x+y<0},S={|x?

Ay?

且x+y<=3},试求RS,RoS,R1,S1,r（F）,s（R）,t（R）,r（S）,s（S）,t（S）.

6.设图G=,其中V={a1,a2,a3,a%as},

E={,,,,}

（1）试给出G的图形表示；

（2）求G的邻接矩阵；

（3）判断图D是强连通图、单侧连通图还是弱连通图？

7.设图G=,V={V1,V2,V3,V4,Vs},E={（V1,V2）,（V1,V3）,（V2,V3）,（V2,V4）,

（V3,V4）,（

V3,Vs）,（V4,Vs）}.

（1）

试给出G的图形表示；

（2）

写出其邻接矩阵；

（3）

求出每个结点的度数

（4）画出图G的补图的图形.

8图G=,其中V={a,b,c,d,e,f},E={（a,b）,（a,c）,（a,e）,

（b,d）,（b,e）,（c,e）,（d,e）,（d,f）,（e,f）},对应边的权值依次为5,2,1,2,6,1,9,3及8.

（1）画出G的图形；

（2）

写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值.

9.已知带权图G如右图所示.试

（1）求图G的最小生成树；

（2）计算该生成树的权值.

10.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试

（1）画出相应的最优二叉树；

（2）计算它们的权值.

五、证明题

1.试证明集合等式：

Ae（B?

C）=（A出）?

（A£）.

2.证明对任意集合AB,C,有A（BC）ABAC.

3.设R是集合A上的对称关系和传递关系，试证明：

若对任意a?

A,存在b?

A使得?

R则R是等价关系.

4.若非空集合A上的二元关系R和S是偏序关系，试证明：

RS也是A上的偏序关系.

5.若无向图G中只有两个奇数度结点，则这两个结点一定是连通的.

6.设G是连通简单平面图，则它一定有一个度数不超过5的结点.（提示：

用

反证法）

7.设连通图G有k个奇数度的结点，证明在图G中至少要添加2条边才能使其成为欧拉图.

8.证明任何非平凡树至少有2片树叶.

离散数学形成性考核作业（四）

数理逻辑部分

本课程形成性考核作业共4次，内容由中央电大确定、统一布置。

本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整，抄写题目，解答题有解答过程。

第6章命题逻辑

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

（1）8能被4整除.

（2）今天温度高吗？

（3）今天天气真好呀！

（4）6是整数当且仅当四边形有4条边.

（5）地球是行星.

（6）小王是学生，但小李是工人.

（7）除非下雨，否则她不会去.

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

（8）如果她不来，那么会议就不能准时开始.

2.翻译成命题公式

（1）她不会做此事.

（2）她去旅游，仅当她有时间.

（3）小王或小李都会解这个题.

（4）如果你来，她就不回去.

（5）没有人去看展览.

（6）她们都是学生.

（7）她没有去看电影，而是去观看了体育比赛.

（8）如果下雨，那么她就会带伞.

3.设P,Q的真值为1;RS的真值为0,求命题公式（PVQARVSAQ的真值.

4.试证明如下逻辑公式

（1）n（AAqB）A（门BVC）AqC门（AVC）

（2）（PtQ）A（Q^R）AqRP

5.试求下列命题公式的主析取范式，主合取范式.

（1）（PV（QAR））paQ）

（2）q（PtQ）AQ

6.利用求公式的范式的方法，判断下列公式是否永真或永假.

（2）（PVQ）tR

7.试证明CVD（CVD）TqhqHH（AAnB）,（AAqB）t（rvS）｝蕴含RVS.

8设P昨天天晴，Q前天下雨，则命题”昨天天晴，但前天下雨”可符号化为（）

A.PAQB.PtQC.PVQD.Qtp

9.能够确定下述推理的步骤（）是正确的.

（1）qPAQP

（2）PT

（1）I

（1）PtQP

（2）QT

（1）I

展开阅读全文