复习要点及练习题市公开课特等奖市赛课微课一等奖课件

离散数学复习及练习题第1页第1章集合1、集合表示及其运算掌握集合表示法；掌握集合相关概念、相关运算和相关性质。重点掌握利用集合运算相关性质化简集合表示式。2、自然数和归纳法掌握两种（第一、第二）数学归纳法特点；能够熟练利用两种归纳法进行问题求解。3、笛卡尔乘积掌握笛卡尔乘积相关概念。第2页第2章二元关系1、二元关系定义及相关概念2、二元关系3种表示方式：序偶集合；关系矩阵；关系图3、3种特殊二元关系：相容关系；等价关系；序关系重点掌握等价关系4、关系4类运算：求补运算；求逆运算；合成运算；闭包运算重点掌握关系闭包运算。5、关系5个性质：自反性；反自反性；对称性；反对称性；传递性第3页第3章函数1、部分函数掌握函数及其相关定义：部分函数，全函数，定义域，值域。掌握满射、内射和双射概念。2、基数

集合基数定义，无穷集合之间等势定义，无穷基数分级，以及集合基数必定小于其幂集基数。重点掌握“抽屉原理”应用。第4页《集合论》填空题1、设A={1,2}，B={1,2,3,4,5},则B–A=(),A

B=()。2、设A={1,2,3,4}，A上二元关系R={<1,2>,<3,4>}，S={<2,4>,<3,1>}，则R-1oS-1=(),

S-1oR-1=(),domR=(),ranS=().

3.设A={a,b}，则P(A)×A=().4.设集合A={

,a}，则A幂集P(A)=().5.设A={x｜x∈N且2≤x≤12}，R为A上整除关系。若取S={2,4,9}，则对半序结构〈A,R〉来说，S上界为(),下界为(),上确界为(),下确界为().S极大元为(),极小元为();最大元为(),最小元为().6.设A是由4个元素组成集合，则A上能够定义()个不一样二元关系；()个不一样自反关系；()个不一样反自反关系；()个不一样对称关系；()个不一样反对称关系。7.

设A={a,b,c},则A上能够定义（）个不一样等价关系。8.等价关系性质为()。9.等价关系关系矩阵有哪些特点？（）

第5页《集合论》选择题1.空集幂集()基数为（）A.0B.1C.2.D.32.设R是非空集合A上二元关系，则R对称闭包s(R)=().A.R∪IAB.R∪R-1C.R∪IAD.R∩

R-13.关系R传递闭包t(R)能够由()来定义。

A.t(R)是包含R二元关系B.t(R)是包含R最小传递关系

C.t(R)是包含R一个传递关系D.任何包含R传递关系4.设集合A={{1},{2,3,4},{5}}，则下式为真是()A.1

AB.{2,3,4}

AC.{{5}}

AD.

A5.设

是一个空集，则以下之一哪一个不成立（）A.

B.

C.

+ D.

+第6页《集合论》计算或证实题1.求{1,

,{1}}幂集：2.设A={a,b,c,d}RA×A,且R={<a,a>,<b,b>,<a,b>,<c,d>}求：（1）r(R)(2)s(R)(3)t(R)并画出它们关系图。3.设｜A｜=3,｜

(B)｜=16,｜

(A∪B)｜=64,试求｜B｜,｜A∩B｜,｜A-B｜,｜A

B｜.4.设A={x｜x为54因子}，RA×A,且对任意x,yA,xRyiffx整除y.

（1）画出半序集<A,R>哈斯图；（2）取A子集B={2,3,9},求出B最小元、极大元和上确界。5.任给52个整数，证实其中必定有两数之差或者两数之和能够被100整除。第7页第4章命题逻辑1、命题和逻辑词掌握命题逻辑相关概念，熟悉逻辑联接词真值表。重点掌握命题符号化。

2、合式公式掌握合式公式定义方法，掌握永真式、永假式以及公式可满足定义。重点掌握合式公式真值表结构方法。

3、等价与蕴含掌握等价、对偶式和蕴含概念。重点掌握等价式、蕴含式证实。掌握一些实际应用问题推理。

4、范式和判定问题掌握命题公式极大项、极小项、主合取（析取）范式定义。重点掌握主范式求法。第8页第5章谓词逻辑

1.变元、谓词和量词掌握一阶谓词逻辑中新引入语法语义概念。重点是掌握将自然语言表示符号化。

2.合式公式掌握一阶谓词逻辑中合式公式归纳定义方法；掌握一阶逻辑公式语义解释方法；能够区分变元约束出现和自由出现。

3.永真式及其判定掌握一阶谓词逻辑代入定理、置换定理；掌握一些主要等价式和蕴含式；重点掌握求公式前束范式方法。第9页《数理逻辑》填空题1、给定以下命题：

P:天在下雪Q:我进城R:我有时间使用逻辑联接词将以下复合命题符号化（1）假如天不下雪且我有时间，我就进城；（2）我进城必要条件是我有时间；（3）天不在下雪；（4）我进城当且仅当我有时间且天不下雪；（5）天下雪，那么我不进城。

2、合式公式┐Q∧(P→Q)与┐P关系是______。(等价、蕴含)

3、合式公式(Q∨┐Q)→((P∧┐R)∧┐P)是永_______式。4、n个命题变元可生成（）个不等价合式公式。

第10页《数理逻辑》填空题（续）5.设论域为{1,2}，命题(

x)(

y)(x+y=4)真值为（）。

6.若论域为非负整数集，A(x,y)表示x+y=y则(

x)(

y)A(x,y)真值为（）。

7.设论域D＝{4,5},那么谓词公式(

x)P(x)∧(y)Q(y)消去量词后等值式为（）。8.

(

x)F(x)→(y)G(x,y)前束范式为（）。

9.A,B为集合，命题A–B=

↔A=B真值为（）。第11页《数理逻辑》选择题1、以下命题中，不是真命题是（）A.假如2*2=5,则雪是白。B.不存在最大质数。C.若太阳从西边落下，则9+5小于10。D.离散数学是计算机科学系一门必修课。

2、以下式子中，（）是永真。

A.Q→(P∧Q)B.P→(P∧Q)C.(P∧Q)→PD.(P∧Q)→Q3.下面”P→Q”等价说法中，不正确为

()

A.P是Q充分条件B.Q是P必要条件C.Q仅当PD.只有Q才P4.以下各式中，（）是析取范式。A.┐P∧QB.┐P∧(Q∨R)C.P∧(┐Q∨R)D.┐P∧(Q∨┐R)第12页《数理逻辑》计算题和推理题1.一个命题公式A(P,Q,R)成真指派为FFF,FFT,FTF,TFF,TTF,求其主范式。

2.教材上习题4.4第1题b),d),3.教材上习题4.3第2题a)4.在谓词逻辑中将以下命题符号化：

(1)有些大学生不是运动员；（2）会叫狗未必会咬人（3）对于每个实数都存在比它大有理数。5.求公式前束范式:教材上习题5.4第1题a)6.三人预计比赛结果，甲说“A第一，B第二”。乙说“C第二，D第四”.丙说“A第二，D第四”。结果三人预计得都不全对，但都对了一个，问A,B,C.D名次。第13页首先要依据题设条件，把原题表示为一个合取范式，然后将合取范式化为主析取范式，每一个极小项就是一个可能结果。在主析取范式中，删除不符题意极小项，其剩下即为所求可能结果。解：设P:A第一Q:B第二R:C第二S:D第四W:A第二由题意应有:(P

Q)∧(R

S)∧(W

S)

T（

表示异或）

将左边合式公式化为析取范式：

(P∧

Q∧R∧S∧W)∨(P∧

Q∧

R∧S∧

W)∨(P∧Q∧R∧

S∧W)∨(P∧Q∧

R∧S∧

W)因为Q、R、W矛盾故

P∧

Q∧R∧S∧W

F,P∧Q∧R∧

S∧W

F.

又因为P∧

Q∧

R∧S∧

W表示A第一,B不是第二,C不是第二,D第四,A不是第二.由此可知A,B,C,D都不是第二，矛盾.所以原式

P∧Q∧

R∧S∧

W

T即A不是第一,B是第二,C不是第二,D第四,A不是第二由此可得：C第一B第二A第三D第四。第14页第7章图论1．基本概念：

(1)掌握有向图、无向图及其相关要素（节点、边、出度、入度、度）数学定义及记号;

(2)掌握完全图、连通图、补图、子图、同构图等基本概念；

(3)掌握和应用握手定理；2．图矩阵表示方法：

熟悉了解图邻接矩阵表示法3．树与有向树：

(1)掌握树几个等价定义；(2)熟悉了解完全二叉树结构和性质；(3)掌握哈夫曼树算法；(4)掌握用“避圈法”结构加权图最小生成树。4．欧拉图、哈米尔顿图、二部图与平面图：

掌握上述各特殊图定义、性质和判断方法第15页《图论》填空题1、设G是n个结点简单无向连通图，那么其边最少条数为（）;边最多条数为（）。2、无向图G是由k(k≥2)棵树组成森林，最少要添加（）条边才能使G成为一棵树。3、设用G是由4棵树组成一个树林，G有15个结点，则G有()条边。

4、一颗完全二叉树高为4，则它最少有（）片树叶，至多有()片树叶。

5、设G是一棵二叉树，G有10个点，其中6个叶点，则G总度数为（），分枝点数为().

6、给定一个图G邻结矩阵X，求vi至vj长度为3路径条数（）。7、无向连通图G是欧拉图，当且仅当G中每一个顶点度数为().

第16页《图论》选择题

1、一个无向图有4个结点，其中3个度数为2,3,3,则第4个结点度数不可能为（）。A.

0B.1C).2D.42、设无向图中有8条边，有两个3度顶点和一个4度顶点，其余顶点度为2，则该图顶点数是()。A．3 B．4C．5D．63、在有5个结点图中,奇结点个数不可能为（）。(A)0(B)1(C)2(D)44、二部图K2,3是（）。A.欧拉图B.哈密顿图C.非平面图D.平面图

5、以下命题正确是（）。

A.欧拉图子图一定是欧拉图B.哈密顿图子图一定是哈密顿图

C.平面图子图一定是平面图D.树子树图一定是树

第17页《图论》计算或证实题三、计算或证实题1、给定权1,4,9,16,25,36,49,64,81,100,试结构一棵最优二叉树，并求其叶加权长度。2、用“避圈法”对教材P137图7.3.8求出其一棵最小生成树。3、证实：一棵多于一个顶点树最少有两片树叶。4、画出二部图K3,4问该图是平面图吗？为何？5、平时布置作业题（略）。第18页教材上习题答案：可参看：

/p-17019984.html第19页开复寄语：我学我成长

（1）练内功。不要只花功夫学习各种流行编程语言和工具，以及一些企业招聘广告上要求科目。要把数据结构、算法、数据库、操作系统原理、计算机体系结构、计算机网络，离散数学等基础课程学好。

（2）多实战。经过编程实战积累经验、巩固知识。很多中国大学毕业生缺乏编程和调试经验；学习C语言，考试过关就算学会了；课题项目中，只要程序能够编译，运行，而且输入输出满足要求就算了事。这些做法是不行。写程序时候，大家必须多想想怎样把程序写得愈加精炼、高效、高质量。提议大家争取在大学四年中积累编写十万行代码经验。我们必须明白是：好程序员是写出来，不是学出来。（3）求实干。不要轻视任何实际工作，比如一些看似简单编码或测试。要不懈追求对细节一丝不苟实干作风与敬业精神。我发觉不少程序员