南京邮电大学《离散数学》考试复习重点精讲.ppt

《南京邮电大学《离散数学》考试复习重点精讲.ppt》由会员分享，可在线阅读，更多相关《南京邮电大学《离散数学》考试复习重点精讲.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学考试复习指南考试复习指南南京邮电大学南京邮电大学南京邮电大学南京邮电大学 计算机学院计算机学院计算机学院计算机学院离散数学离散数学离散数学离散数学课程组课程组课程组课程组1 1 1 1、填空题（、填空题（、填空题（、填空题（10101010空，空，空，空，20202020分）分）分）分）2 2 2 2、判断题（、判断题（、判断题（、判断题（10101010小题，小题，小题，小题，20202020分）分）分）分）3 3 3 3、简答题（、简答题（、简答题（、简答题（5 5 5 5小题，小题，小题，小题，40404040分）分）分）分）4 4 4 4、证明题（、证明题（、证明题（、

2、证明题（2 2 2 2小题，小题，小题，小题，20202020分）分）分）分）考试题型考试题型命题的概念、命题的表示法命题的概念、命题的表示法五个基本联结词的含义五个基本联结词的含义命题公式与命题翻译。命题公式与命题翻译。命题公式的真值表（万能的真值表！）命题公式的真值表（万能的真值表！）重言式与蕴含式的证明重言式与蕴含式的证明主析取范式主析取范式/主合取范式主合取范式命命题题公公式式的的推推理理（真真值值表表法法、直直接接证证法法、间间接证法（反证法接证法（反证法+CP+CP规则）规则）第一章第一章 命题逻辑命题逻辑 典型例题典型例题1-11-1求公式(PQ)(QR)的主析取范式典型例题典型

3、例题1-21-2 (P P Q Q)(Q QR R)F FT TF FF FF FT TT TT T法二：真值表如下：法二：真值表如下：所以主析取范式为：所以主析取范式为：(P PQ QR R)(P PQ Q R R)(P P Q QR R)(P P Q QR R)典型例题典型例题1-21-2谓词的概念与表示谓词的概念与表示量词的含义量词的含义谓词公式与翻译谓词公式与翻译判断谓词公式的真值判断谓词公式的真值谓词演算的等价式与蕴含式证明谓词演算的等价式与蕴含式证明谓词演算的推理谓词演算的推理第二章第二章 谓词逻辑谓词逻辑第二章第二章 作业作业 符符号号化化下下列列命命题题并并推推证证其其结结论论

4、：任任何何人人如如果果他他喜喜欢欢步步行行，他他就就不不喜喜欢欢乘乘汽汽车车；每每一一个个人人或或者者喜喜欢欢乘乘汽汽车车或或者者喜喜欢欢骑骑自自行行车车；有有的的人人不不爱爱骑骑自自行行车车。因因而而有有的的人人不不爱爱步步行行。（请请假假设设 P(x):P(x):x x喜喜欢欢步步行行,Q(x):Q(x):x x喜喜欢欢乘乘汽汽车车，R(x):R(x):x x喜欢骑自行车喜欢骑自行车.）典型例题典型例题2-12-1集合、关系、笛卡尔积、幂集的概念集合、关系、笛卡尔积、幂集的概念集集合合的的四四种种基基本本运运算算（交交、并并、相相对对补补与与绝绝对对补补、对对称称差）差）关系的表示方法（直

5、积、关系矩阵、关系图）关系的表示方法（直积、关系矩阵、关系图）关系的五种基本性质及其判定关系的五种基本性质及其判定关系的三种运算（复合、逆、闭包、关系的三种运算（复合、逆、闭包、WarshallWarshall算法）算法）等价关系的定义等价关系的定义第三章第三章 集合与关系集合与关系第三章第三章 集合与关系集合与关系等价类、商集的概念等价类、商集的概念偏序关系偏序关系偏序关系的哈斯图画法偏序关系的哈斯图画法偏偏序序集集中中一一些些元元素素的的判判别别（最最大大最最小小元元、极极大大极极小小元元、上下确界）上下确界）第三章第三章 作业作业典型例题典型例题3-13-1设A=-1,0,1,R=,是A

6、上的二元关系，求关系的三种闭包运算自反闭包：r(R)=,，,；对称闭包：s(R)=,；传递闭包：t(R)=,。第五章第五章 代数系统代数系统代数系统的基本性质代数系统的基本性质半群、独异点、子群、群的概念半群、独异点、子群、群的概念群的判定群的判定循环群、交换群、有限循环群循环群、交换群、有限循环群同态、同构、环与域同态、同构、环与域如何求解运算的幺元、零元如何求解运算的幺元、零元代数系统中幺元与零元的关系代数系统中幺元与零元的关系第五章第五章 作业作业典型例题典型例题5-15-1运算*的单位元是 0，零元是 -1，元素2的逆元是则运算*的单位元是？，零元是？，元素2的逆元是？第五章第五章 作

7、业作业典型例题典型例题5-25-2设设是一个代数系统，是一个代数系统，a*b=a+b+1，试证明，试证明是群是群第六章第六章 格和布尔代数格和布尔代数格的定义格的定义格同构格同构子格的判别子格的判别分配格（五元及五元以上分配格的判别）分配格（五元及五元以上分配格的判别）有界格、补元、有补格有界格、补元、有补格布尔格、布尔代数的基本概念布尔格、布尔代数的基本概念偏序集偏序集偏序集偏序集格格格格分配格分配格分配格分配格有界格有界格有界格有界格有补格有补格有补格有补格布尔格布尔格布尔格布尔格第六章第六章 格与布尔代数格与布尔代数第六章第六章 格与布尔代数格与布尔代数第六章第六章 作业作业典型例题典型

8、例题6-16-11 12 23 34 46 6121224249 9极小元极小元3 3，4 4最小元最小元无无上确界上确界1212第七章第七章 图论图论图的基本概念（如简单图、完全图、欧拉图）图的基本概念（如简单图、完全图、欧拉图）图的基本性质（如关于结点度数的三个基本定理）图的基本性质（如关于结点度数的三个基本定理）图的同构图的同构点割集、边割集、点点割集、边割集、点/边连通度、距离边连通度、距离图的连通性图的连通性图的矩阵表示（邻接矩阵、可达性矩阵）图的矩阵表示（邻接矩阵、可达性矩阵）欧拉图（一笔画问题）欧拉图（一笔画问题）哈密尔顿图的判定哈密尔顿图的判定第七章第七章 作业作业典型例题典型例题7-17-1设有向图G=，如右图所示，求：（1）的邻接矩阵。（2）的可达矩阵。答疑时间安排答疑时间：元月答疑时间：元月1010号中午号中午12:00-13:2012:00-13:20答疑地点：行政南楼答疑地点：行政南楼432432计科系办公室计科系办公室