离散数学4.docx
《离散数学4.docx》由会员分享，可在线阅读，更多相关《离散数学4.docx（27页珍藏版）》请在冰点文库上搜索。
离散数学4
一、单项选择题共8道试题共80分。
得分0
1.本课程的教学内容分为三个单元其中第三单元的名称是
A.数理逻辑
B.集合论
C.图论
D.谓词逻辑
正确答案A满分10分
2.本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合
其中第2章关系与函数中的第3个知识点的名称是
A.函数
B.关系的概念及其运算
C.关系的性质与闭包运算
D.几个重要关系
正确答案D满分10分
3.本课程所有教学内容的电视视频讲解集中在VOD点播版块中VOD点播
版块中共有讲
A.18
B.20
C.19
D.17
正确答案B满分10分
4.本课程安排了7次形成性考核作业第3次形成性考核作业的名称是
A.集合恒等式与等价关系的判定
B.图论部分书面作业
C.集合论部分书面作业
D.网上学习问答
正确答案C满分10分
5.课程学习平台左侧第1个版块名称是
A.课程导学
B.课程公告
C.课程信息
D.使用帮助
正确答案C满分10分
6.课程学习平台右侧第5个版块名称是
A.典型例题
B.视频课堂
C.VOD点播
D.常见问题
正确答案D满分10分
7.“教学活动资料”版块是课程学习平台右侧的第个版块
A.6
B.7
C.8
D.9
正确答案A满分10分
8.课程学习平台中“课程复习”版块下放有本课程历年考试试卷的栏目名
称是
A.复习指导
B.视频
C.课件
D.自测
正确答案D满分10分
二、作品题共1道试题共20分。
得分10
1.请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自
己的学习计划学习计划应该包括课程性质和目标参考教学大纲、学习内
容、考核方式以及自己的学习安排字数要求在100—500字完成后在下列
文本框中提交
学习离散数学有两项最基本的任务其一是通过学习离散数学使学生了解和掌握在后续课程中
要直接用到的一些数学概念和基本原理掌握计算机中常用的科学论证方法为后续课程的学习
奠定一个良好的数学基础其二是在离散数学的学习过程中培训自学能力、抽象思维能力和逻
辑推理能力以提高专业理论水平。
因此学习离散数学对于计算机、通信等专业后续课程的学习
和今后从事计算机科学等工作是至关重要的。
但是由于离散数学的离散性、知识的分散性和处理
问题的特殊性使部分学生在刚刚接触离散数学时对其中的一些概念和处理问题的方法往往感
到困惑特别是在做证明题时感到无从下手找不到正确的解题思路。
因此对离散数学的学习
方法给予适当的指导和对学习过程中遇到的一些问题分析是十分必要的。
一、认知离散数学
离散数学是计算机科学基础理论的核心课程之一是计算机及应用、通信等专业的一门重要的基
础课。
它以研究量的结构和相互关系为主要目标其研究对象一般是有限个或可数个元素充分
体现了计算机科学离散性的特点。
1定义和定理多
离散数学是建立在大量定义、定理之上的逻辑推理学科因此对概念的理解是学习这门课程的核
心。
在学习这些概念的基础上要特别注意概念之间的联系而描述这些联系的实体则是大量的
定理和性质。
在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用因此要真正
理解离散数学中所给出的每个基本概念的真正的含义。
2.方法性强
在离散数学的学习过程中一定要注重和掌握离散数学处理问题的方法在做题时找到一个合
适的解题思路和方法是极为重要的。
如果知道了一道题用怎样的方法去做或证明就能很容易地
做或证出来。
反之则事倍功半。
在离散数学中虽然各种各样的题种类繁多但每类题的解法
均有规律可循。
3.抽象性强
离散数学的特点是知识点集中对抽象思维能力的要求较高。
由于这些定义的抽象性使初学者
往往不能在脑海中直接建立起它们与现实世界中客观事物的联系。
不管是哪本离散数学教材都
会在每一章中首先列出若干个定义和定理接着就是这些定义和定理的直接应用如果没有较好
的抽象思维能力学习离散数学确实具有一定的困难。
在学习离散数学中所遇到的这些困难可以通过多学、多看、认真分析讲课中所给出的典型例题
的解题过程再加上多练从而逐步得到解决。
二、认知解题规范
一般来说离散数学的考试要求分为了解、理解和掌握。
了解是能正确判别有关概念和方法
理解是能正确表达有关概念和方法的含义掌握是在理解的基础上加以灵活应用。
总体评价
一、单项选择题共10道试题共100分。
得分100
1.设集合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.自反和传递
满分10分
2.设函数fNNf（n）n+1下列表述正确的是
A.f存在反函数
B.f是双射的
C.f是满射的
D.f是单射函数
满分10分
3.若集合A{2a{a}4}则下列表述正确的是（）
A.{a{a}}A
B.
ØA
C.{2}A
D.{a}A
满分10分
4.
设集合A={1,2,3,4,5}上的偏序关系的哈斯图如右图所示若A的子集B={3,
4,5}则元素3为B的
A.下界
B.最小上界
C.最大下界
D.最小元
满分10分
5.设A、B是两个任意集合侧A-B=Ø⇔（）
A.A=B
B.AB
C.AB
D.BØ
满分10分
6.若集合A{a{a}{12}}则下列表述正确的是（）
A.{a{a}}A
B.{12}A
C.{a}A
D.A
满分10分
7.设集合A={1,a}则P（A）=（）
A.{{1},{a}}
B.{,{1},{a}}
C.{{1},{a},{1,a}}
D.{,{1},{a},{1,a}}
满分10分
8.设A={a,b}B={1,2}R1R2R3是A到B的二元关系且R1={,
}R2={,,}R3={,}则不
是从A到B的函数
A.
R1
B.
R2
C.
R3
D.R1和R3
满分10分
9.设集合A={a}则A的幂集为（）
A.{{a}}
B.{a{a}}
C.{{a}}
D.{a}
满分10分
10.设A={abc}B={12}作fA→B则不同的函数个数
为
A.2
B.3
C.6
D.8
满分10分
一、单项选择题共10道试题共100分。
得分100
1.
设有向图a、b、c与d如图四所示则下列结论成立的是（）
图四
A.a是强连通的
B.b是强连通的
C.c是强连通的
D.d是强连通的
满分10分
2.
设无向图G的邻接矩阵为
则G的边数为（）
A.1
B.6
C.7
D.14
满分10分
3.无向树T有8个结点则T的边数为（）
A.6
B.7
C.8
D.9
满分10分
4.
如图所示以下说法正确的是（）
A.e是割点
B.{a,e}是点割集
C.{b,e}是点割集
D.{d}是点割集
满分10分
5.若G是一个欧拉图则G一定是（）
A.平面图
B.汉密尔顿图
C.连通图
D.对偶图
满分10分
6.设G是连通平面图有v个结点e条边r个面则r=（）
A.ev2
B.ve2
C.ev2
D.ev2
满分10分
7.设无向图G的邻接矩阵为则G的边数为（）
A.6
B.5
C.4
D.3
满分10分
8.
如图一所示以下说法正确的是（）
A.{（a,e）}是割边
B.{（a,e）}是边割集
C.{（a,e）,（b,c）}是边割集
D.{（d,e）}是边割集
满分10分
9.
设有向图a、b、c与d如图所示则下列结论成立的是（）
A.a只是弱连通的
B.b只是弱连通的
C.c只是弱连通的
D.d只是弱连通的
满分10分
10.无向完全图K4是
A.欧拉图
B.汉密尔顿图
C.非平面图
D.树
满分10分
一、单项选择题共10道试题共100分。
得分100
1.设C（x）x是国家级运动员G（x）x是健壮的则命题“没有一个国家级运
动员不是健壮的”可符号化为（）
A.
B.
C.
D.
满分10分
2.命题公式PQ的合取范式是（）
A.PQ
B.PQPQ
C.PQ
D.PQ
满分10分
3.设P我将去打球Q我有时间命题“我将去打球仅当我有时间时”
符号化为（）
A.
B.
C.
D.
满分10分
4.设个体域D={a,b,c}那么谓词公式消去量词后的等值式
为
A.（A（a）A（b）A（c））（B（a）B（b）B（b））
B.（A（a）A（b）A（c））（B（a）B（b）B（b））
C.（A（a）A（b）A（c））（B（a）B（b）B（b））
D.（A（a）A（b）A（c））（B（a）B（b）B（b））
满分10分
5.命题公式（PQ）Q为（）
A.矛盾式
B.可满足式
C.重言式
D.合取范式
满分10分
6.命题公式PQ的主合取范式是（）
A.（PQ）
B.PQ
C.PQ
D.
PQ
满分10分
7.命题公式的析取范式是（）
A.
B.
C.
D.
满分10分
8.下列公式（）为重言式
A.PQPQ
B.（Q（PQ））（Q（PQ））
C.（P（QP））（P（PQ））
D.（P（PQ））Q
满分10分
9.命题公式（PQ）R的析取范式是（）
A.（PQ）R
B.（PQ）R
C.（PQ）R
D.（PQ）R
满分10分
10.下列等价公式成立的为（）
A.PQPQ
B.P（QP）P（PQ）
C.Q（PQ）Q（PQ）
D.P（PQ）Q
满分10分
一、填空题
1．命题公式（）PQP的真值是1．
2．设P：
他生病了，Q：
他出差了．R：
我同意他不参加学习.则命题“如
果他生病或出差了，我就同意他不参加学习”符号化的结果为（P∨Q）→R．
3．含有三个命题变项P，Q，R的命题公式PQ的主析取范式是
（PQR）∨（PQ┐R）．
4．设P（x）：
x是人，Q（x）：
x去上课，则命题“有人去上课．”可符号化为
））（）（（xQxPx
．
5．设个体域D＝{a,b},那么谓词公式）（）（yyBxxA消去量词后的等值式为
））（）（（）（）（bBaBbAaA
．
6．设个体域D＝{1,2,3}，A（x）为“x大于3”，则谓词公式（x）A（x）的真值
为0．
7．谓词命题公式（x）（（A（x）B（x））C（y））中的自由变元为y．
8．谓词命题公式（x）（P（x）Q（x）R（x，y））中的约束变元为x．
三、公式翻译题
1．请将语句“今天是天晴”翻译成命题公式．
解：
设P：
今天是晴天，
命题“今天是晴天”翻译成命题公式为P。
2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．
解：
设P：
小王去旅游，Q：
小李去旅游．
命题“小王去旅游，小李也去旅游”翻译成命题公式为P∧Q。
3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式．
解：
设P：
明天天下雪，Q：
我就去滑雪．
命题“如果明天天下雪，我就去滑雪”翻译成命题公式为P→Q。
4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．
★形成性考核作业★
2
解：
设P：
他去旅游，Q：
他有时间．
命题“他去旅游，仅当他有时间”翻译成命题公式为P→Q。
5．请将语句“有人不去工作”翻译成谓词公式．
解：
设P（x）：
x是人，Q（x）：
x去工作．
命题“有人不去工作”翻译成谓词公式为
））（）（（xQxPx
。
6．请将语句“所有人都努力工作．”翻译成谓词公式．
解：
设P（x）：
x是人，Q（x）：
x努力工作．
命题“所有人都努力工作．”翻译成谓词公式为
））（）（（xQxPx
四、判断说明题（判断下列各题，并说明理由．）
1．命题公式PP的真值是1．
答：
不正确。
因为当P是真命题时，┐P是假命题，当P是假命题时，┐P是真
命题，所以┐P∧P是假命题，真值是0。
2．命题公式P（PQ）P为永真式．
答：
正确。
因为┐P∧（P→┐Q）
PQPP）（
，┐P∨P
1
，所
以命题公式是永真式。
3．谓词公式））（）,（（）（xxPyxyGxxP是永真式．
答：
正确。
因为
））（）,（（）（xxPyxyGxxP））（）,（（）（xxPyxyGxxP
）（）,（）（））（）,（（）（xxPyxyGxxPxxPyxyGxxP
1）,
（1）,（））（）（（yxyGyxyGxxPxxP
。
所以命题公式是永真式。
4．下面的推理是否正确，请给予说明．
（1）（x）A（x）B（x）前提引入
（2）A（y）B（y）US
（1）
★形成性考核作业★
3
答：
不正确。
因为
x的辖域是
）（xA，不包含）（xB，所以根据全称量词消去规则，
只能得到）（）（xByA，而不能得到）（）（yByA。
四．计算题
1．求PQR的析取范式，合取范式、主析取范式，主合取范式．
解：
4
MRQPRQP
所以PQR的析取范式为RQP，
合取范式为）（RQP，
主合取范式为）（RQP，即
4
M。
则主析取范式为
7653210mmmmmmm
，
2．求命题公式（PQ）（RQ）的主析取范式、主合取范式．
解：
）（）（）（）（）（）（QRQPQRQPQRQP
1）（）1（）（）（）（RQPRQRPQRQQRP
4
MRQP
所以（PQ）（RQ）的主合取范式为）（RQP，即
4
M。
则主析取范式为
7653210
mmmmmmm，
3．设谓词公式（）（（,）（）（,,））（）（,）xPxyzQyxzyRyz．
（1）试写出量词的辖域；
（2）指出该公式的自由变元和约束变元．
解：
（1）量词）（x的辖域为）,,（）（）,（zxyQzyxP，量词）（z的辖域为）,,（zxyQ，
量词）（y的辖域为）,（zyR；
（2）该公式的自由变元为zy,，y自由出现2次，z自由出现1次，约束变
元为zyx,,，x约束出现2次，zy,各约束出现1次。
4．设个体域为D={a1,a2}，求谓词公式yxP（x,y）消去量词后的等值式；
★形成性考核作业★
4
解：
谓词公式yxP（x,y）消去量词后的等值式为：
）,（）,（
21
axxPaxxP
））,（）,（（））,（）,（（
22211211
aaPaaPaaPaaP
五、证明题
1．试证明（P（QR））PQ与（PQ）等价．
证明：
QPRQPQPRQP））（（））（（
）（）））（（（QPQPQPRQP
所以，（P（QR））PQ与（PQ）等价
2．试证明（x）（P（x）R（x））（x）P（x）（x）R（x）．
证明：
（1）（x）（P（x）R（x））P
（2）P（c）R（c）ES
（1）
（3）P（c）T
（2）E
（4）R（c）T
（2）E
（5）（x）P（x）EG（3）
（6）（x）R（x）EG（4）
（7）（x）P（x）（x）R（x）T（5）（6）E
离散数学综合练习书面作业
要求：
学生提交作业有以下三种方式可供选择：
1.可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．
2.在线提交word文档．
3.自备答题纸张，将答题过程手工书写，并拍照上传．
一、公式翻译题
1．请将语句“小王去上课，小李也去上课．”翻译成命题公式．
设P：
小王去上课。
Q:
小李去上课。
则P^Q
2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．
设P：
他去旅游。
Q:
他有时间。
则P→Q
3．请将语句“有人不去工作”翻译成谓词公式．
设A（x）:
x是人
B（x）:
去工作
x（A（x）^
B（x））
4．请将语句“所有人都努力学习．”翻译成谓词公式．
设A（x）:
x是人
B（x）:
努力工作
x（A（x）^B（x））
二、计算题
1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算
（1）（AB）；
（2）（A∩B）；（3）A×B．
解：
（1）（AB）={{1},{2}}
（2）（A∩B）={1,2}
（3）A×B{<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1,2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>}
2．设A={1，2，3，4，5}，R={|xA，yA且x+y4}，S={|xA，yA且x+y<0}，试求R，S，RS，SR，R-1，S-1，r（S），s（R）．
解：
R={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}
S=Φ
RS=Φ
SR=Φ
R-1={<1,1>,<2,1>,<3,1>,<1,2>,<2,2>,<1,3>}
S-1=Φ
r（S）={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}
s（R）={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}
3．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}．
（1）写出关系R的表示式；
（2）画出关系R的哈斯图；
（3）求出集合B的最大元、最小元．
解：
（1）R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>}
（2）
（3）集合B没有最大元，最小元是2
4．设G=，V={v1，v2，v3，v4，v5}，E={（v1,v3），（v2,v3），（v2,v4），（v3,v4），（v3,v5），（v4,v5）}，试
（1）给出G的图形表示；
（2）写出其邻接矩阵；
（3）求出每个结点的度数；（4）画出其补图的图形．
解：
（1）
°
°°
°°
（2）
（3）
1、
2、
4、
3、
2
（4）°
°°
°°
5．图G=，其中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权最小的生成树及其权值．
bc
解：
（1）。
。
21
a。
64
213
。
。
e5d
（2）
（3）bc
。
。
21a。
1
3
。
。
ed
其权值为：
7
6．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．
解：
65
1748
512
1731
2357
权值为65。
升级会员 