Hello World
山东大学离散数学复习纲要
数理逻辑：
基本的概念，包括Propositional Logic命题逻辑、Predicates 谓词逻辑
命题逻辑：命题的表达、命题的逻辑等价、命题的有效论证；
公式等价：一类：P(R)Q ?
命题公式的主析取范式和主合取范式
谓词逻辑：命题的谓词、量词表达形式，谓词与Quantifiers量词 "xP(x)，$x P(x)，谓词公式的解释I,谓词逻辑的演绎推证，证明定理的方法；
集合：集合的基本概念和运算（包括幂集power set P(S)、子集等概念，以及集合相等的证明方法）；
函数：函数的基本概念，三种特殊函数（单射（One-to-one function一对一），满射（Onto function映上），双射（One-to-one correspondence一一对应）），函数的运算（复合运算产生复合函数Composition functions、逆运算产生逆函数Inverse function等）。
三类特出函数的符合函数等。
第5章关系Relations 这一章我们主要讨论了关系的基本概念、运算、表示和关系的性质，以及两个比较重要的关系，即等价关系Equivalence relations和偏序关系partialordering。
关系的基本概念、运算，关系是集合笛卡尔乘积的子集，关系的运算除了包括集合间的基本运算以外，还有复合运算、逆运算和闭包运算。特别是闭包运算closures，三种闭包：自反闭包r(R)、对称闭包s(R)、传递闭包t(R)。要求会求关系的闭包。
关系的表示，除了由序对集合的表示形式以外，我们还讨论了关系矩阵和关系图两种表达形式，这两种形式可以借助于计算机进行辅助来讨论有关关系的一些问题。
关系的性质 我们一共讨论了五种关系性质：自反Reflexive、反自反Irreflexive、对称Symmetric、反对称Antisymmetric、传递Transitive。
等价关系Equivalence relations 它是具有自反、对称和传递性的关系，它与集合的划分有着密切的联系，一个等价关系可以确定一个集合上的划分Equivalence classes & Partitions，该划分就是等价关系所确定的商集；同样给定一个集合上的划分，通过划分块间的笛卡尔乘积的并集可以得到一个等价关系，划分块就是该等价关系的等价类。
偏序关系partial ordering 它是具有自反、反对称和传递的关系，表达偏序关系的图的是哈斯图Hasse diagrams（COVA），利用哈斯图可以判定偏序集上的八种特殊元素，即极大、极小元素，最大、最小元素，上界和下界、上确界和下确界。
同时由偏序关系还可以构造元素的字典排序和拓扑排序。
基本概念：无向图，有向图，简单图，多重图，伪图，完全图（Completegraphs），圈图（Cycles），轮图（Wheels），n立方体图（n-Cubes），正则图（regular graph），偶图（二分图bipartite graphs），对偶图（Dual graph），子图（subgraph），生成子图（spanning subgraph），补图（complement graph），强连通，单侧或单向连通图（unilaterally
connected），弱连通图，连通分支（connected components），Euler graphs, Hamilton graphs, Euler circuit(欧拉回路和Hamilton circuit哈密顿回路)，Euler path(欧拉通路和Hamilton哈密顿通路)，带权图（weightedgraphs），平面（性）图（PlanarGraphs），图着色（vertices顶点），色数（用表示），树（Trees），parent,internal vertex,leaf vertex，根树（Rooted
tree），生成树（spanning tree），最小生成树（Minimum spanning trees），
基本问题：图的表示（representing graphs）相邻表（adjacency lists），邻接矩阵（adjacency matrices），关联矩阵（incidence matrix），邻接矩阵与两顶点之间通路的计数，最短通路问题（Shortest-PathProblems），图的同构（Isomorphismof graph），
基本定理：握手定理，无向图有偶数个奇度顶点，，
欧拉图：有两个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点都具有偶度数。
哈密顿图：对的任意非空子集均有，狄拉克定理：如果图是一个具有个顶点的简单图，并且图中每个顶点的度数至少为，那么图是哈密顿图。，奥勒定理：如果图是一个具有个顶点的简单图，并且图中每一对不邻接的顶点和满足，那么图具有哈密顿回路。
欧拉公式（Euler’s Formula）：假设图是具有条边，个顶点的连通、平面化的、简单连通图。是图的面数，则
推论1：假设图是具有个顶点,条边的连通平面化的简单图，其中，则
推论2：如果图是一个连通、平面化的简单图，那么图一定存在一个度数不超过5的顶点。
推论3：若连通平面化的简单图具有个顶点,条边，其中并且没有长度为3的回路，则。
库拉托夫斯基定理：一个图是非平面性的，当且仅当它包含一个同胚于和的子图。
定理及推论：任何树都满足：e=n-1，树有关的定理。
在满m叉树中结点n=m*i+1(e=m*i),e(m*i)=l+i-1等等
要求的算法：Dijkstra算法，Prim算法，Kruskal算法。
本阶段的考试要求
（1）期末考试采用闭卷笔试+平时作业、练习和出勤，其中闭卷笔试成绩占90%，平时作业、练习和出勤占10%
（2）阅卷全部采用密封、流水阅卷。
（3）考题类型：选择题、简答题、基本运算、证明题，形式与我们平时所做的练习、作业以及讲解的例题相同。
（4）题目的比例，根据前面的内容小结可以看出，我们一共讲了三大部分：数理逻辑（30%），集合论及关系（40%），图论（30%）。题目覆盖了我们所讲的80%左右的内容。英语出题是书上的内容，涉及集合和图论两部分。
（5）准备希望大家从最基本的概念、方法和技术入手，不要去做难度较大习题，只要掌握了这些基本的东西，再稍微仔细一点，考个8，9分是没有问题的。
（6）不要作弊，不作弊可以是60、70、80分，但只要作弊就是0分。
没有更多推荐了，文档分类：
离散数学期末考试.doc
下载后只包含 1 个 DOC 格式的文档，没有任何的图纸或源代码，
您的浏览器不支持进度条
下载文档到电脑，查找使用更方便
还剩?页未读，继续阅读
该用户其他文档
下载所得到的文件列表离散数学期末考试.doc
文档介绍：
淮阴工学院课程考试试卷第 1页共 2页班级姓名学号---------------------------- 装-------------------------- 订---------------------- 线----------------------------- 专业: 计科、计算机、软件课程名称: 离散数学学分: 3 试卷编号( A) 课程编号: 41114 60 考试方式:闭卷考试时间: 100 分钟拟卷人: 拟卷日期: 200 9- 12- 20 审核人: 得分统表:题号一二总分得分 1、( 10 分)证明等值式: (
) ( ) ( ) ( ) p
q p q p q p q ?????????? 2、( 10 分) 证明: 如果:
A B g B C ?
?都是双射的,则: f
g A C ??也是双射的。 3、( 10 分) 给定群,G?,则,G?为 Abel 群? 2
)( )( , ( ) ) a
b a b G a b a b ? ? ????
? 4、( 15 分) 给定代数结构,S?,其中 S 中元为实数有序对, ?定义为,
c d a c b d bd ?
????, 试证: ,S?是可交换独异点。一、证明下列各题(本题共 4小题, 满分 45分) 得分淮阴工学院课程考试试卷第 2页共 2页班级姓名学号---------------------------- 装-------------------------- 订---------------------- 线----------------------------- 1、( 10 分)试求下列公式的主析取范式和主合取范式: (
Q P Q ? ????? 2、( 10 分)设?? 1, 2 , 1, 3 , 2, 2 , 2, 4 , 3, 2 R?,求??????????(1)
1 ; (2) 2, 3 ; (3) 1 ; (4) ; (5) 3 R
R R R R ??
?? 3、(20 分) 无向图 G 如右图所示,(1 )求 G 的全部点割集和边割集,并指出其中的割点和桥(割边); (2 )求 G 的点连通度(
) G?和边连通度(
) G?。 4、( 15 分)在自然推理系统 P 中构造下面推理的证明:如果今天是星期六,我们就到颐和园或圆明园去玩。如果颐和园游人太多, 我们就不去颐和园玩。今天是星期六。颐和园游人太多。所以我们去圆明园玩。专业: 计科、计算机、软件课程名称: 离散数学学分:3 试卷编号( A) 二、计算或简答题:(本题共 4小题, 满分 55分) 得分淮阴工学院课程考试试卷第 3页共 2页班级姓名学号---------------------------- 装-------------------------- 订---------------------- 线----------------------------- 一、证明下列各题(本题共 4小题, 满分 45分) 1、(
) ) ( ) ( ) 5 p
p p q q p q q ????????????左边=((分) )
??????((分) )
??????((分)右边 2、(1) :
, , ( ) , , f
c C b B g b c a A ?
???????先证明是满射的。任取则使得又. a
b 使得 F( )= 于是,有)
( ( ) ( ) : 4 f
g a g f a g b c f g A C ?
???()是满射的(分) (2)2 ,
( ) ( ), f
x x A f g x f g x ?
1 2 再证明:是单射的。假设使得(
( ) ( ( ) g
2 即)=)。4 f
2 由于,都是单射的,=(分)。 2 f
??:是双射的(分)。 3、充分性:因为,G?是群,又对任意, a b G ?,有 2
( ) ( ) ( ) ( ) a
b a b a b a b a a b b ?
( ) ( ) ( ) a
b a b a a b b b a b a b b ?
???? ????????? 5 b
?……可见, ?是可交换的,故,G?为 Abel. 必要性: ,G?为 Abel 群,自然,G?是群;又对任意, a b G ?,有 2 (
) ( ) ( ) ( ) ( ) a
a b a b a b a b a a b b ?
????????? 2
a b b a b ??
?? ???…… 4 、首先证明?是可结合的,任给,
, , , , a b c d e f S ?,有: (
, ) , , 2 , ,
2 2( 2 ) ,
2 2 2 4 a b
c d e f a c b d bd e f a
c e b d f bd b d bd a
c e b d f bd bf df bdf ?
????????而,
( , , ) , , 2 ,
2 2 ( 2 ) ,
2 2 2 4 , a b
c d e f a b c d d f df a
c e b e f df b d f df a
c e b d f bd bf df b
内容来自淘豆网www.taodocs.com转载请标明出处.
文件大小：0 KB
下载次数：离散数学复习提纲(完整版)_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
离散数学复习提纲(完整版)
&&浙江理工大学,离散数学复习
阅读已结束，下载本文需要
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩6页未读，
定制HR最喜欢的简历
你可能喜欢离散数学怎么复习?
昨天一晚上搞定了大物，今天模电下来了75，心情还不错。就差明天的离散数学就可以回家啦~先去洗个澡，学长门告诉下我怎么复习，平时概念理解过但是很久了忘了很多，今晚准备把他解决了，求方法。
自挽、、、。。。。。。。。
学了离散1还会有离散2~
发自手机虎扑 m.hupu.com
我们这课全班60过了。。
离散数学学的什么版的？我们当时学的英文版的，貌似那个不是很难，做点典型的题目就可以过了。
发自手机虎扑 m.hupu.com
引用5楼 @ 发表的:
离散数学学的什么版的？我们当时学的英文版的，貌似那个不是很难，做点典型的题目就可以过了。
上海科学技术文献出版社。。1982年9月第一版。。
看看前几年的试卷啊
引用7楼 @ 发表的:
看看前几年的试卷啊
谢了，正在边看题边看书。
范式、推理理论、
幂集、笛卡尔积、关系的性质、闭包、等价关系、偏序关系
幺元零元、群、拉格朗日定理
结点的度、握手定理、欧拉图哈密顿图的判定树
上了4年离散数学的老师
留
毕业两年了 还记得离散补考的一个题目（答案我也不知道）：
求证无10阶整环。
离散数学学的什么版的？我们当时学的英文版的，貌似那个不是很难，做点典型的题目就可以过了。发自手机虎扑 m.hupu.com
引用10楼 @ 发表的:
上了4年离散数学的老师
留
谢谢老师，步行街的都是好老师 \(^o^)/~
您需要登录后才可以回复，请或者
562人参加团购89.00元&269.00元
860人参加团购198.00元&399.00元
263人参加团购269.00元&1099.00元
2499人参加团购84.00元&199.00元
327人参加团购279.00元&569.00元
385人参加团购78.00元&169.00元
505人参加团购289.00元&599.00元
226人参加团购169.00元&399.00元
533人参加团购69.00元&199.00元
221人参加团购95.00元&169.00元
454人参加团购98.00元&599.00元
294人参加团购269.00元&649.00元查看: 4378|回复: 9
听说今年408考了离散数学 16考生要复习离散数学吗？
主题帖子积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
考研年份2015
报考学校武汉大学
本科学校湖北工大
听说今年408考了离散数学 16考生要复习离散数学吗？
主题帖子积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
考研年份2013
报考学校中科院
没有考吧····
主题帖子积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
报考学校buaa beijing
本科学校山东大学
关于图的大题，第2-3问，就是离散数学图论部分的一个定理，呵呵
主题帖子积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
上专业课的时候认真就行了，没必要专门复习。再说今年考的关于离散数学的知识点，貌似王道单科书上都有提到。
主题帖子积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
报考学校北京大学
本科学校中华女子学院
同问，谢谢
主题帖子积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
考研年份2015
报考学校澳门大学
本科学校石河子大学
& &在哪有提到？请告之单科书页数。
主题帖子积分
考研年份2014
报考学校同济大学
本科学校淮北煤炭师范
& &在图那一章的最前面
主题帖子积分
王道论坛初级道友, 积分 28, 距离下一级还需 172 积分
王道论坛初级道友, 积分 28, 距离下一级还需 172 积分
考研年份2015
报考学校复旦大学
本科学校吉林大学
感觉不需要 那四科复习的细一些，那个题思考一下就能做出来，明年408还可能涉及到其他学科的知识，你不可能在有限的时间内都复习过来，那样也不划算，建议认真复习4门的课本+王道单科，足以。
主题帖子积分
考研年份2015
报考学校中山大学
本科学校中山大学
没必要,跨考生如是说.
把单科书吃透,思维灵活一些就能做出来
408作为一个跨专业考研的热门,命题人也要考虑不会出太多大纲之外的东西增加复习难度
主题帖子积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
王道论坛实习道友, 积分 10, 距离下一级还需 10 积分
考研年份2015
报考学校中国科大
本科学校中国科大
那个题的确不用看离散数学也能做出来的，图的邻接矩阵的n次方的意义
我是考完了看离散准备复试才发现的}