离散数学基础

离散数学基础一、什么是离散数学？

离散数学是现代数学的一个重要分支，是计算机专业的一门重要的专业基础课程。它是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。

概述2二、为什么要学离散数学？1、离散数学是计算机专业的一门核心基础课程，离散数学为计算机专业的后继课程如数据结构、操作系统、数据库、编译原理、网络和算法设计等课程提供必要的数学基础。

2、为学生今后从事计算机科学和技术各方面的工作提供有力的工具。3、离散数学是现代数学的一个重要分支，通过该课程的学习可以提高学生的抽象思维、严格推理以及综合归纳分析能力，培养出高素质的人才。

3

三、如何学好离散数学？

1、熟读教材。准确理解各个概念和定理的含义（结合多个例子来理解），必要的推理过程要看懂、理解（它可以帮助你熟悉和深刻理解定理的含义）。

2、独立思考，大量练习。仅靠熟读教材并不能将书本上的知识变成你自己的知识，在熟读教材的基础上，必须通过大量练习，独立思考来真正获取知识。

3、注重抽象思维能力的培养。数学与其他学科相比较具有

较高的抽象性，而离散数学的抽象性特点更为显著，它有着大量抽象的概念和抽象的推理，要学好这门课程必须具有较好的

抽象思维能力，才能深入地掌握课程内容。“常思考，多做题”4第四部分数理逻辑。包括命题逻辑和谓词逻辑。四、离散数学的主要内容有哪些？离散数学的主要内容可以分为四个部分：第一部分集合论。包括集合、关系和函数。第二部分代数系统。包括代数系统的一般概念，几类典型的代数系统。第三部分图论。包括图的基本概念，几种特殊的图。5第一部分集合论

集合论包括集合、二元关系和函数，它们之间的关系是：二元关系是一种特殊的集合，集合中的元素都是有序对；函数是一种特殊的二元关系。一、内容提要1、集合的两种表示方法：列举法和描述法。2、特殊的集合：空集、全集、子集和幂集。3、集合的运算：并、交、差和对称差，各种运算的性质。4、集合运算的基本定律：交换律，结合律，分配律，吸收律，德.摩根律等。5、有序n元组、n维笛卡尔积。6、关系的定义：笛卡尔积的子集。67、关系的表示方法：集合、矩阵和关系图。8、关系的性质：自反性、反自反性、对称性、反对称性和传递性。9、关系的运算：复合运算、逆运算和闭包运算。10、特殊的二元关系及其相关特性：等价关系（自反性、对称性、传递性）、偏序关系（自反性、反对称性、传递性）、等价类、偏序关系中的特殊元素（极大元、上界等）。11、函数的定义、函数的定义域和值域。12、函数的性质：单射、满射和双射。13、函数的运算：复合函数、逆函数。14、集合的基数。7二、重点和难点1、掌握元素与集合之间的关系，集合与集合之间的关系。2、运用集合运算的基本定律去化简集合表达式或证明集合等式。3、掌握二元关系的五个性质和二元关系的运算。4、等价关系的证明、等价类的求解，偏序关系的特定元素的求解。5、函数的性质，求复合函数和逆函数。8大家学习辛苦了，还是要坚持继续保持安静9三、例题1、

这两个关系是否正确？答：正确。在

中

表示元素；在

中

表示空集。2、求R={<1,2>,<2,3>,<3,4>}的传递闭包。解：R的传递闭包={<1,2>,<2,3>,<3,4>,<1,3>,<2,4>,<1,4>}。注意：求传递闭包是一个不断重复合并有序对的过程。有序对<1,4>往往被漏掉。3、化简集合表达式：((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B))解：((A∩B)∪A)⊕((B∩~B)⊕A⊕(B∪~B))(吸收律和零律)=A⊕⊕A⊕U(同一律)=A⊕A⊕U(零律)=⊕U=U104、设集合A＝{a,b,c,d,e}，偏序关系R的哈斯图如图所示，若A的子集B={c,d,e}，求：（1）用列举法写出偏序关系R的集合表达式；（2）写出集合B的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。

解：（1）R=IA

{<d,b>,<d,c>,<d,a>,<b,a>,<c,a>,<e,c>,<e,a>}（2）集合B的极大元：c，极小元：d、e，最大元：c，最小元：无，上界：c、a，上确界：c，下界：无，下确界：无。

115、已知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)f°g:RR，且f°g(x)=g(f(x))=3*((x+4)^3-2)+5=3*(x+4)^3-1f°g(3)=3*(3+4)^3-1=1028(2)因为g与f都是双射函数；那么，g与f的合成函数也是双射函数。故g与f的合成函数存在逆函数。g°f:RR，且g°f(x)=f(g(x))=3*(3*x+5)^3-2(g°f)-1:RR，且(g°f)-1(x)=(((x+2)/3)^(1/3)-5)/312第二部分图论一、内容提要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(n≥2)阶简单图，G有m条边，则G的补图有______个结点，有_______条边。

答：G的补图的结点个数等于G的结点个数，等于n。G的补图的边数等于n阶完全图的边数减去G的边数，等于n(n-1)/2-m。153、下列命题正确的是（）（a）G为n阶无向连通图，如果G的边数m≥n-1，则G中必有圈（b）二部图的顶点个数一定是偶数（c）若无向图G的任何两个不相同的顶点均相邻，则G为哈密尔顿图（d）3-正则图的顶点个数可以是奇数，也可以是偶数

解：c正确，因为无向图G为完全图。a不正确，当G是无向树时，m=n-1，但G中没有圈。b不正确，二部图要求结点能够分成两部分，每部分中的任何两个结点无边，并没有要求二部图的顶点个数是偶数.d不正确，3-正则图的所有结点的度数均为3，根据握手定理可得，所有顶点的度数之和是偶数。所以3-正则图的顶点个数必为偶数。164、已知有向图D的顶点集合V(D)={v1,v2,v3,v4}，其邻接矩阵如右图所示。求从v1到v3长度小于等于3的通路个数。从v1到v3长度小于等于3的通路个数==0+1+4=5A2==A3==解：175、设n阶无向树G=<V,E>中有m条边，证明m=n-1。

证：用数学归纳法进行证明。(1)初始化：当n=1时，无向树G是平凡树，即G为平凡图。则m=0=n-1。(2)假设归纳：假设当n

k时，结论成立，即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=<V,E>中有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正确。213、证明推理：(

x)(P(x)

(Q(x)

R(x))),(

x)P(x)

(

x)(P(x)

R(x))证：①(

x)P(x)P②P(c)ES,①③(

x)(P(x)

(Q(x)

R(x)))P④P(c)

(Q(c)

R(c))US,③⑤Q