离散数学基础PPT课件

1,离散数学总复习,2,一、什么是离散数学？,离散数学是现代数学的一个重要分支，是计算机专业的一门重要的专业基础课程。它是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。,概述,3,二、为什么要学离散数学？,1、离散数学是计算机专业的一门核心基础课程，离散数学为计算机专业的后继课程如数据结构、操作系统、数据库、编译原理、网络和算法设计等课程提供必要的数学基础。,2、为学生今后从事计算机科学和技术各方面的工作提供有力的工具。,3、离散数学是现代数学的一个重要分支，通过该课程的学习可以提高学生的抽象思维、严格推理以及综合归纳分析能力，培养出高素质的人才。,4,三、如何学好离散数学？,1、熟读教材。准确理解各个概念和定理的含义（结合多个例子来理解），必要的推理过程要看懂、理解（它可以帮助你熟悉和深刻理解定理的含义）。,2、独立思考，大量练习。仅靠熟读教材并不能将书本上的知识变成你自己的知识，在熟读教材的基础上，必须通过大量练习，独立思考来真正获取知识。,3、注重抽象思维能力的培养。数学与其他学科相比较具有较高的抽象性，而离散数学的抽象性特点更为显著，它有着大量抽象的概念和抽象的推理，要学好这门课程必须具有较好的抽象思维能力，才能深入地掌握课程内容。,“常思考，多做题”,5,第四部分数理逻辑。包括命题逻辑和谓词逻辑。,四、离散数学的主要内容有哪些？,离散数学的主要内容可以分为四个部分：,第一部分集合论。包括集合、关系和函数。,第二部分代数系统。包括代数系统的一般概念，几类典型的代数系统。,第三部分图论。包括图的基本概念，几种特殊的图。,6,第一部分集合论,集合论包括集合、二元关系和函数，它们之间的关系是：二元关系是一种特殊的集合，集合中的元素都是有序对；函数是一种特殊的二元关系。,一、内容提要1、集合的两种表示方法：列举法和描述法。2、特殊的集合：空集、全集、子集和幂集。3、集合的运算：并、交、差和对称差，各种运算的性质。4、集合运算的基本定律：交换律，结合律，分配律，吸收律，德.摩根律等。5、有序n元组、n维笛卡尔积。6、关系的定义：笛卡尔积的子集。,7,7、关系的表示方法：集合、矩阵和关系图。8、关系的性质：自反性、反自反性、对称性、反对称性和传递性。9、关系的运算：复合运算、逆运算和闭包运算。10、特殊的二元关系及其相关特性：等价关系（自反性、对称性、传递性）、偏序关系（自反性、反对称性、传递性）、等价类、偏序关系中的特殊元素（极大元、上界等）。11、函数的定义、函数的定义域和值域。12、函数的性质：单射、满射和双射。13、函数的运算：复合函数、逆函数。14、集合的基数。,8,二、重点和难点1、掌握元素与集合之间的关系，集合与集合之间的关系。2、运用集合运算的基本定律去化简集合表达式或证明集合等式。3、掌握二元关系的五个性质和二元关系的运算。4、等价关系的证明、等价类的求解，偏序关系的特定元素的求解。5、函数的性质，求复合函数和逆函数。,9,三、例题1、这两个关系是否正确？答：正确。在中表示元素；在中表示空集。2、求R=,的传递闭包。解：R的传递闭包=,。注意：求传递闭包是一个不断重复合并有序对的过程。有序对往往被漏掉。3、化简集合表达式：(AB)A)(BB)A(BB)解：(AB)A)(BB)A(BB)(吸收律和零律)=AAU(同一律)=AAU(零律)=U=U,10,4、设集合Aa,b,c,d,e，偏序关系R的哈斯图如图所示，若A的子集B=c,d,e，求：（1）用列举法写出偏序关系R的集合表达式；（2）写出集合B的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。,解：（1）R=IA,（2）集合B的极大元：c，极小元：d、e，最大元：c，最小元：无，上界：c、a，上确界：c，下界：无，下确界：无。,11,5、已知f：RR且f(x)=(x+4)3-2，已知g：RR且g(x)=3*x+5，求:(1)f与g的合成函数，并求3在f与g的合成函数下的函数值。(2)g与f的合成函数是否存在逆函数？为什么？如果有，求它的逆函数。解:(1)fg:RR，且fg(x)=g(f(x)=3*(x+4)3-2)+5=3*(x+4)3-1fg(3)=3*(3+4)3-1=1028(2)因为g与f都是双射函数；那么，g与f的合成函数也是双射函数。故g与f的合成函数存在逆函数。gf:RR，且gf(x)=f(g(x)=3*(3*x+5)3-2(gf)-1:RR，且(gf)-1(x)=(x+2)/3)(1/3)-5)/3,12,第二部分图论,一、内容提要1、图的基本概念：无向图、有向图、简单图、结点的度数、子图、补图、图的同构。2、握手定理：所有结点的度数之和等于边数的2倍。3、图的连通性：割边、割点、边割集、点割集。通路、回路、连通分支。4、图的矩阵表示：邻接矩阵、关联矩阵。5、欧拉图和哈密尔顿图的定义和判定条件。6、树的定义、性质、判定条件和遍历。7、二部图和平面图的定义、性质和判定条件,13,二、重点和难点1、掌握图的基本概念。2、运用握手定理解题。3、利用图的矩阵求两个结点间的通路条数。4、欧拉图和哈密尔顿图的判定。5、树的遍历方法。,14,三、例题1、设T是2叉正则树，有t片树叶，i个分支点，证明T的边数m=2t-2。证：设T有m条边，根据握手定理可得：t+3i-1=2m(1)因为T是2叉正则树，根据树的性质可得：m=t+i-1.(2)解由(1)，(2)构成的方程组得：m=2t-2。故结论成立。2、已知无向图G为n(n2)阶简单图，G有m条边，则G的补图有_个结点，有_条边。答：G的补图的结点个数等于G的结点个数，等于n。G的补图的边数等于n阶完全图的边数减去G的边数，等于n(n-1)/2-m。,15,3、下列命题正确的是（）（a）G为n阶无向连通图，如果G的边数mn-1，则G中必有圈（b）二部图的顶点个数一定是偶数（c）若无向图G的任何两个不相同的顶点均相邻，则G为哈密尔顿图（d）3-正则图的顶点个数可以是奇数，也可以是偶数解：c正确，因为无向图G为完全图。a不正确，当G是无向树时，m=n-1，但G中没有圈。b不正确，二部图要求结点能够分成两部分，每部分中的任何两个结点无边，并没有要求二部图的顶点个数是偶数.d不正确，3-正则图的所有结点的度数均为3，根据握手定理可得，所有顶点的度数之和是偶数。所以3-正则图的顶点个数必为偶数。,16,4、已知有向图D的顶点集合V(D)=v1,v2,v3,v4，其邻接矩阵如右图所示。求从v1到v3长度小于等于3的通路个数。,从v1到v3长度小于等于3的通路个数=0+1+4=5,A2=,=,A3=,=,解：,17,5、设n阶无向树G=中有m条边，证明m=n-1。证：用数学归纳法进行证明。(1)初始化：当n=1时，无向树G是平凡树，即G为平凡图。则m=0=n-1。(2)假设归纳：假设当nk时，结论成立，即m=n-1。当n=k+1时，从无向树G中删除某个结点v，如果结点v的度数为i，则有i条边与结点v相关联，且每条边均为桥。因此，从无向树G中删除结点v后得到i颗无向树，分别为：G1、G2、Gi，且对于所有的j(1ji)，均有|Gj|k。根据假设可得：无向树Gj的边mj=nj-1。无向树G的结点个数n=n1+n2+ni+1，无向树G的边数m=m1+m2+mi+i=(n1-1)+(n2-1)+(ni-1)+i=n1+n2+ni=n-1。因此，当n=k+1时，结论也成立。综合(1)、(2)可得：若n阶无向树G=中有m条边，则m=n-1。,18,第三部分数理逻辑,一、内容提要1、命题及其联结词（非、与、或、蕴含、等价）。2、命题公式的析取范式和合取范式。3、命题公式间的等价关系和蕴含关系。4、命题演算的推理理论。5、谓词公式的有关概念（量词、谓词、变元、指派等）6、谓词公式间的等价关系和蕴含关系。7、谓词演算的推理理论。,19,二、重点和难点1、命题公式间的等价关系和蕴含关系。2、命题演算的推理理论。3、谓词公式间的等价关系和蕴含关系。4、谓词演算的推理理论。,20,三、例题1、下列语句为命题的是（）（a）看球赛去（b）离散数学是计算机系的一门必修课（c）计算机有空吗？（d）今天天气多好啊！解：命题是可以判定真假的陈述句，故b正确。2、对于公式(x)(P(x)(y)Q(x,y)，下列说法正确的是（）（a）x和y都是自由变元（b）x和y都不是自由变元（c）x是自由变元，y不是自由变元（d）x不是自由变元，y是自由变元解：b正确。,21,3、证明推理：(x)(P(x)(Q(x)R(x),(x)P(x)(x)(