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

第一级,第二级,第三级,第四级,第五级,第一级,第二级,第三级,第四级,第五级,*,离散数学,考试复习指南,南京邮电大学 计算机学院,离散数学,课程组,1,、填空题（,10,空，,20,分）,2,、判断题（,10,小题，,20,分）,3,、简答题（,5,小题，,40,分）,4,、证明题（,2,小题，,20,分）,考试题型,命题的概念、命题的表示法,五个基本联结词的含义,命题公式与命题翻译。,命题公式的真值表（万能的真值表！）,重言式与蕴含式的证明,主析取范式,/,主合取范式,命题公式的推理（真值表法、直接证法、间接证法（反证法,+CP,规则）,第一章 命题逻辑,典型例题,1-1,求公式,(,P,Q,),(,Q,R,),的主析取范式,典型例题,1-2,(,P,Q,),(,Q,R,),F,T,F,F,F,T,T,T,法二：真值表如下：,所以主析取范式为：,(,P,Q,R,)(,P,Q,R,)(,P,Q,R,)(,P,Q,R,),典型例题,1-2,谓词的概念与表示,量词的含义,谓词公式与翻译,判断谓词公式的真值,谓词演算的等价式与蕴含式证明,谓词演算的推理,第二章 谓词逻辑,第二章 作业,符号化下列命题并推证其结论：,任何人如果他喜欢步行，他就不喜欢乘汽车；每一个人或者喜欢乘汽车或者喜欢骑自行车；有的人不爱骑自行车。因而有的人不爱步行。（,请假设,P(x):x,喜欢步行,Q(x):x,喜欢乘汽车，,R(x):x,喜欢骑自行车,.,）,典型例题,2-1,集合、关系、笛卡尔积、幂集的概念,集合的四种基本运算（交、并、相对补与绝对补、对称差）,关系的表示方法（直积、关系矩阵、关系图）,关系的五种基本性质及其判定,关系的三种运算（复合、逆、闭包、,Warshall,算法）,等价关系的定义,第三章 集合与关系,第三章 集合与关系,等价类、商集的概念,偏序关系,偏序关系的哈斯图画法,偏序集中一些元素的判别（最大最小元、极大极小元、上下确界）,第三章 作业,典型例题,3-1,设,A=-1,0,1,R=,是,A,上的二元关系，求关系的三种闭包运算,自反闭包,：,r(R)=,，,；,对称闭包,：,s(R)=,；,传递闭包,：,t(R)=,。,第五章 代数系统,代数系统的基本性质,半群、独异点、子群、群的概念,群的判定,循环群、交换群、有限循环群,同态、同构、环与域,如何求解运算的幺元、零元,代数系统中幺元与零元的关系,第五章 作业,典型例题,5-1,运算*的单位元是,0,，零元是,-1,，元素,2,的逆元是,则运算*的单位元是？，零元是？，元素,2,的逆元是？,第五章 作业,典型例题,5-2,设,是一个代数系统，,a*b=a+b+1,，试证明,是群,第六章,格和布尔代数,格的定义,格同构,子格的判别,分配格（五元及五元以上分配格的判别）,有界格、补元、有补格,布尔格、布尔代数的基本概念,偏序集,格,分配格,有界格,有补格,布尔格,第六章,格与布尔代数,第六章,格与布尔代数,第六章 作业,典型例题,6-1,1,2,3,4,6,12,24,9,极小元,3,，,4,最小元,无,上确界,12,第七章 图论,图的基本概念（如简单图、完全图、欧拉图）,图的基本性质（如关于结点度数的三个基本定理）,图的同构,点割集、边割集、点,/,边连通度、距离,图的连通性,图的矩阵表示（邻接矩阵、可达性矩阵）,欧拉图（一笔画问题）,哈密尔顿图的判定,第七章 作业,典型例题,7-1,设有向图,G=,，如右图所示，求：,（,1,）的邻接矩阵。,（,2,）的可达矩阵。,答疑时间安排,答疑时间：元月,10,号中午,12:00-13:20,答疑地点：行政南楼,432,计科系办公室,祝考试顺利，,新年快乐！,