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

《离散数学》考试复习指南南京邮电大学计算机学院《离散数学》课程组1、填空题（10空，20分）2、判断题（10小题，20分）3、简答题（5小题，40分）4、证明题（2小题，20分）考试题型命题的概念、命题的表示法五个基本联结词的含义命题公式与命题翻译。命题公式的真值表（万能的真值表！）重言式与蕴含式的证明主析取范式/主合取范式命题公式的推理（真值表法、直接证法、间接证法（反证法+CP规则））第一章命题逻辑PQRab设表示命题“天下雪”，表示命题“我将去镇上”，表示命题“我有时间”。以符号形式写出下列命题：)如果天不下雪和我有时间，那么我将去镇上。)我将去镇上，仅当我有时间。aPRQ(b)1QR2RQ3RQ解：()()()仅当表示必要条件，有：（本题正确答案）()当表示充分条件，有：()当且仅当表示充要条件，有：典型例题1-1求公式(P∨Q)∧(Q∨R)的主析取范式解：法一：(P∨Q)∧(Q∨R)=(P∧Q)∨(P∧R)∨(Q∧Q)∨(Q∧R)=(P∧Q∧(R∨R))∨(P∧(Q∨Q)∧R)∨((P∨P)∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)典型例题1-2P,Q,R(P∨Q)∧(Q∨R)F,F,FFF,F,TTF,T,FFF,T,TFT,F,FFT,F,TTT,T,FTT,T,TT法二：真值表如下：所以主析取范式为：(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)典型例题1-2谓词的概念与表示量词的含义谓词公式与翻译判断谓词公式的真值谓词演算的等价式与蕴含式证明谓词演算的推理第二章谓词逻辑第二章作业符号化下列命题并推证其结论：任何人如果他喜欢步行，他就不喜欢乘汽车；每一个人或者喜欢乘汽车或者喜欢骑自行车；有的人不爱骑自行车。因而有的人不爱步行。（请假设P(x):x喜欢步行,Q(x):x喜欢乘汽车，R(x):x喜欢骑自行车.）(()()),(()()),()xPxQxxQxRxxRx前提:()xPx结论:典型例题2-1(()()),(()()),()()xPxQxxQxRxxRxxPx证明：1(1)()(2)()(1)(3)(()())(4)()()(3)(5)()()(4)(6)()(2)(5)(7)(()xRxPRcESxQxRxPQcRcUSRcQcTQcTxPx证法：())(8)()()(7)(9)()()(8)(10)()(6)(9)(11)()(10)QxPPcQcUSQcPcTPcTxPxEG集合、关系、笛卡尔积、幂集的概念集合的四种基本运算（交、并、相对补与绝对补、对称差）关系的表示方法（直积、关系矩阵、关系图）关系的五种基本性质及其判定关系的三种运算（复合、逆、闭包、Warshall算法）等价关系的定义第三章集合与关系第三章集合与关系等价类、商集的概念偏序关系偏序关系的哈斯图画法偏序集中一些元素的判别（最大最小元、极大极小元、上下确界）第三章作业典型例题3-1设A={-1,0,1},R={-1,0,1,0}是A上的二元关系，求关系的三种闭包运算自反闭包：r(R)={-1,0,1,0，-1,-1,0,0,1,1}；对称闭包：s(R)={-1,0,1,0,0,-1,0,1}；传递闭包：t(R)={-1,0,1,0}。第五章代数系统代数系统的基本性质半群、独异点、子群、群的概念群的判定循环群、交换群、有限循环群同态、同构、环与域如何求解运算的幺元、零元代数系统中幺元与零元的关系第五章作业典型例题5-1运算*的单位元是0，零元是-1，元素2的逆元是,*abababab设，定义上的运算：则运算*的单位元是？，零元是？，元素2的逆元是？第五章作业典型例题5-2设R,*是一个代数系统，a*b=a+b+1，试证明R,*是群证明：1）∵a*b=a+b+1，而+在R中封闭，所以*在R中封闭2）(a*b)*c=(a+b+1)*c=a+b+1+c+1=a+b+c+2;a*(b*c)=a*(b+c+1)=a+b+c+1+1=a+b+c+2;∵(a*b)*c=a*(b*c)，所以*运算可结合3）对任意a∈R，有a*(-1)=a-1+1=a，(-1)*a=-1+a+1=a，即a*(-1)=(-1)*a=a，故-1是R,*的幺元4）对任意a∈R，有a*(-2-a)=a-2-a+1=-1，(-2-a)*a=-2-a+a+1=-1，即a*(-2-a)=(-2-a)*a=-1，故a-1=-2-a综上可知，R,*是群第六章格和布尔代数格的定义格同构子格的判别分配格（五元及五元以上分配格的判别）有界格、补元、有补格布尔格、布尔代数的基本概念偏序集格分配格有界格有补格布尔格第六章格与布尔代数abcdeabcde(a)钻石格(b)五角格第六章格与布尔代数第六章作业典型例题6-11、集合A={1，2，3，4，6，9，12，24}，R为A上的整除关系。（1）画出偏序集A，R的哈斯图。（4分）（2）子集B={3，4，6}，求B的最小元、极小元、上确界。（6分）1234612249极小元3，4最小元无上确界12第七章图论图的基本概念（如简单图、完全图、欧拉图）图的基本性质（如关于结点度数的三个基本定理）图的同构点割集、边割集、点/边连通度、距离图的连通性图的矩阵表示（邻接矩阵、可达性矩阵）欧拉图（一笔画问题）哈密尔顿图的判定第七章作业典型例题7-1设有向图G=V,E，如右图所示，求：（1）Ｇ的邻接矩阵。（2）Ｇ的可达矩阵。邻接矩阵0010010110()000100010000000AG可达矩阵0011010110001100011000000P答疑时间安排答疑时间：元月10号中午12:00-13:20答疑地点：行政南楼432计科系办公室