电大《离散数学》任务1、3、5、7题库

一、单项选择题（共 8 道试题，共 80 分。）

1. 本课程的教学内容分为三个单元，其中第三单元的名称是（）． A. 数理逻辑

B. 集合论

C. 图论

D. 谓词逻辑

2. 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（）． A. 函数

B. 关系的概念及其运算

C. 关系的性质与闭包运算

D. 几个重要关系

3. 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（）讲． A. 18

B. 20

C. 19

D. 17

4. 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（）． A. 集合恒等式与等价关系的判定

B. 图论部分书面作业

C. 集合论部分书面作业

D. 网上学习问答

5. 课程学习平台左侧第1个版块名称是：（）． A. 课程导学

B. 课程公告

C. 课程信息

D. 使用帮助

6. 课程学习平台右侧第5个版块名称是：（）． A. 典型例题

B. 视频课堂

C. VOD点播

D. 常见问题

7. “教学活动资料”版块是课程学习平台右侧的第（）个版块． A. 6

B. 7

C. 8

D. 9

8. 课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（）． A. 复习指导

B. 视频

C. 课件

D. 自测

二、作品题（共 1 道试题，共 20 分。）

1. 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交．

参考答案：

一、填空题

1．设集合，则P（A）-P（B ）= ，A´ B= ．

2．设集合A有10个元素，那么A的幂集合P（A）的元素个数为 ．

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

则R的有序对集合为　 　　　　　　．

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

R＝

那么R－1＝ ．

5．设集合A=｛a， b， c， d｝，A上的二元关系R={<；a， b>；， <；b， a>；， <；b， c>；， <；c， d>；}，则R具有的性质是　　　　　　　　　．

6．设集合A=｛a， b， c， d｝，A上的二元关系R={<；a， a >；， <；b， b>；， <；b， c>；， <；c， d>；}，若在R中再增加两个元素　　　　　　　　　，则新得到的关系就具有对称性．

7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 个．

8．设A={1， 2}上的二元关系为R={<；x， y>；|xÎA，yÎA， x+y =10}，则R的自反闭包为 ．

9．设R是集合A上的等价关系，且1 ， 2 ， 3是A中的元素，则R中至少包含 等元素．

10．设A={1，2}，B={a，b}，C={3，4，5}，从A到B的函数f ={<；1， a>；， <；2， b>；}，从B到C的函数g={<； a，4>；， <； b，3>；}，则Ran（g° f）= ．

二、判断说明题（判断下列各题，并说明理由．）

1．若集合A = {1，2，3}上的二元关系R={<；1， 1>；，<；2， 2>；，<；1， 2>；}，则

（1） R是自反的关系； （2） R是对称的关系．

2．设A={1，2，3}，R={<；1，1>；， <；2，2>；， <；1，2>； ，<；2，1>；}，则R是等价关系．

3．若偏序集<；A，R>；的哈斯图如图一所示，

则集合A的最大元为a，最小元不存在．

4．设集合A={1， 2， 3， 4}，B={2， 4， 6， 8}，，判断下列关系f是否构成函数f：，并说明理由．

（1） f={<；1， 4>；， <；2， 2，>；， <；4， 6>；， <；1， 8>；}； （2） f={<；1， 6>；， <；3， 4>；， <；2， 2>；}；

（3） f={<；1， 8>；， <；2， 6>；， <；3， 4>；， <；4， 2，>；}．

三、计算题

1．设，求：

（1） （AÇB）È~C； （2） （AÈB）- （BÇA） （3） P（A）－P（C）； （4） AÅB．

2．设A={{1}，{2}，1，2}，B={1，2，{1，2}}，试计算

（1）（A-B）； （2）（A∩B）； （3）A×B．

3．设A={1，2，3，4，5}，R={<；x，y>；|xÎA，yÎA且x+y£4}，S={<；x，y>；|xÎA，yÎA且x+y<；0}，试求R，S，R·S，S·R，R-1，S-1，r（S），s（R）．

4．设A={1， 2， 3， 4， 5， 6， 7， 8}，R是A上的整除关系，B={2， 4， 6}．

（1） 写出关系R的表示式； （2 ）画出关系R的哈斯图；

（3） 求出集合B的最大元、最小元．

四、证明题

1．试证明集合等式：AÈ （BÇC）=（AÈB） Ç （AÈC）．

2．试证明集合等式AÇ （BÈC）=（AÇB） È （AÇC）．

3．对任意三个集合A， B和C，试证明：若AB = AC，且A，则B = C．

4．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

一、填空题

1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 ．

2．设给定图G（如右由图所示），则图G的点割集是

．

3．设G是一个图，结点集合为V，边集合为E，则

G的结点 等于边数的两倍．

4．无向图G存在欧拉回路，当且仅当G连通且 ．

5．设G=<；V，E>；是具有n个结点的简单图，若在G中每一对结点度数之和大于等于 ，则在G中存在一条汉密尔顿路．

6．若图G=<；V， E>；中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 ．

7．设完全图K有n个结点（n³2），m条边，当 时，K中存在欧拉回路．

8．结点数v与边数e满足 关系的无向连通图就是树．

9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去

条边后使之变成树．

10．设正则5叉树的树叶数为17，则分支数为i = ．

二、判断说明题（判断下列各题，并说明理由．）

1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．

2．如下图所示的图G存在一条欧拉回路．

3．如下图所示的图G不是欧拉图而是汉密尔顿图．

4．设G是一个有7个结点16条边的连通图，则G为平面图．

5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．

三、计算题

1．设G=<；V，E>；，V={ v1，v2，v3，v4，v5}，E={ （v1，v3），（v2，v3），（v2，v4），（v3，v4），（v3，v5），（v4，v5） }，试

（1） 给出G的图形表示； （2） 写出其邻接矩阵；

（3） 求出每个结点的度数； （4） 画出其补图的图形．

2．图G=<；V， E>；，其中V={ a， b， c， d， e}，E={ （a， b）， （a， c）， （a， e）， （b， d）， （b， e）， （c， e）， （c， d）， （d， e） }，对应边的权值依次为2、1、2、3、6、1、4及5，试

（1）画出G的图形； （2）写出G的邻接矩阵；

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

3．已知带权图G如右图所示．

（1） 求图G的最小生成树； （2）计算该生成树的权值．

4．设有一组权为2， 3， 5， 7， 17， 31，试画出相应的最优二叉树，计算该最优二叉树的权．

四、证明题

1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图中的奇数度顶点个数相等．

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

一、填空题

1．命题公式的真值是　 　．

2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为

．

3．含有三个命题变项P，Q，R的命题公式PÙQ的主析取范式是

．

4．设P（x）：x是人，Q（x）：x去上课，则命题“有人去上课．” 可符号化为

．

5．设个体域D＝{a， b}，那么谓词公式消去量词后的等值式为 ．

6．设个体域D＝{1， 2， 3}，A（x）为“x大于3”，则谓词公式（$x）A（x） 的真值为 ．

7．谓词命题公式（"x）（（A（x）ÙB（x）） ÚC（y））中的自由变元为 ．

8．谓词命题公式（"x）（P（x） ®Q（x） ÚR（x，y））中的约束变元为 ．

三、公式翻译题

1．请将语句“今天是天晴”翻译成命题公式．

2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．

3．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．

4．将语句“41次列车下午五点开或者六点开．”翻译成命题公式．

5．请将语句 “有人不去工作”翻译成谓词公式．

6．请将语句“所有人都努力工作．”翻译成谓词公式．

四、判断说明题（判断下列各题，并说明理由．）

1．命题公式ØPÙP的真值是1．

2．（$x）（P（x）→Q（y）∧R（z））中的约束变元为y．

3．谓词公式中$x量词的辖域为．

4．下面的推理是否正确，请给予说明．

（1） （"x）A（x）® B（x） 前提引入

（2） A（y） ®B（y） US （1）

四．计算题

1． 求P®QÚR的析取范式，合取范式、主析取范式，主合取范式．

2．求命题公式（PÚQ）®（RÚQ） 的主析取范式、主合取范式．

3．设谓词公式．

（1）试写出量词的辖域；

（2）指出该公式的自由变元和约束变元．

4．设个体域为D={a1， a2}，求谓词公式"y$xP（x，y）消去量词后的等值式；

五、证明题

1．试证明 （P®（QÚØR））ÙØPÙQ与Ø （PÚØQ）等价．

2．试证明：┐（A∧┐B）∧（┐B∨C）∧┐C Þ ┐A．