主讲人杨凤杰

《主讲人杨凤杰》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、主讲人:杨凤杰学时：64(第一讲)离散数学吉林大学远程教育课件离散数学离散数学在教给学生离散问题建模、数学理论、计算机求解方法和技术知识的同时，培养学生的数学抽象能力与严密的逻辑推理能力。通过本课程的学习，能使学生掌握进一步学习其它课程所必需的离散数学知识，并增强学生使用离散数学知识分析问题与解决问题的能力。本书分为九章，主要内容为第一章介绍集合论基础知识，包括映射、关系、基数等知识。第二章和第三章属于数理逻辑部分，主要介绍经典命题逻辑和谓词逻辑的基础知识。第四章介绍图论方面的基本知识，包括图，有向图与Euler路，无向图与Hamilton路，平面图与二部图。第五章讨

2、论数论基础知识，包括整除性，质因数分解，合同，一次同余式。第六章和第七章是抽象代数的群、环和域的基本内容。第八章介绍格论和布尔代数方面的基础知识。第九章介绍了计算模型中的三种类型的结构，即语法、有限状态机和图灵机。阐述了它们在语言识别方面的应用。第一章集合论基础§1.1集合的基本概念集合是数学中最基本的概念。既然是最基本的概念，它就不是很好定义，一般只是说明。最基本的东西就是大家都知道的东西。要说明什么是集合，有多种描述方法：“所要讨论的一类对象的整体”；“具有同一性质单元的集体”等。当我们讨论某一类对象的时候，就把这一类对象的整体称为集合。而集合中的对象就称为该集合

3、中的元素。Cantor是这样描述集合的：所谓集合，是指我们无意中或思想中将一些确定的，彼此完全不同的客体的总和考虑为一个整体。这些客体叫做该集合的元素。设A是一个集合，a是集合A中的元素，今后将这一事实记以aA，读做a属于A；若a不是集合A中的元素，则记以aA,读做a不属于A。例如，这间教室里所有桌子的整体就做成一个桌子集合。每个桌子都属于这个集合,每个椅子都不属于这个集合。又如,世界上所有哺乳动物的整体做成一个哺乳动物集合。每一条狗每一只猫都属于这个集合,而每一只鸡都不属于这个集合。集合有多种表示方法，这里给出常用的两种方法。1、列举法：这种方法把集合中的所有元

4、素置于花括号内，元素之间用逗号隔开。如：A={1,2,3,4,5,6}。2、特征法：用小写的英文字母来统一表示该集合的元素，并指出这类元素的共同特征。如A={x

5、x是正整数且x<7}。有限个元素a1,…,an做成的集合,称为有穷集（有限集）,记以{a1,…,an};无限个元素做成的集合,称为无穷集。有穷集中元素的个数称为该集合的元素数，记为A。特别,不含元素的集合称为空集,记以。定义1.1.1当A,B两个集合的元素完全一样,即A,B两个集合实际上是同一集合时,则称集合A,B相等,记以A=B。定义1.1.2设A,B是两个集合。若A的元素都是B的元素,则称B包含A,

6、或称A是B的子集,记以AB。若AB,且AB,则称A是B的真子集,记以AB。例如：A={1,2,3,4,5}，B={x

7、x是正整数}，C={x

8、x是正整数且x<6}，则A是有穷集合，B是无穷集合，A=C，AB，AB。显然,空集是任何集合的子集且空集唯一。当我们所讨论的集合都是某一集合的子集时，这个集合就称为全集，记以E。由定义，下面的结论是显然的：对于任意两个集合A，B，A=B的充要条件是AB且BA。这一结论是我们证明两个集合相等的最常用的方法。定义1.1.3设A是集合，A的所有子集为元素做成的集合称为A的幂集，记以（A）或２A。显然，若A为有穷集，元

9、素数为n，则２A的元素数为幂集具有以下性质:(1) 设A,B是两个集合,AB当且仅当(A)(B)；(2) x(A)当且仅当xA。定义1.1.4设C是一个集合。若C的元素都是集合,则称C为集合族。若集合族C可表示为C={SddD}，则称D为集合族C的标志（索引）集。显然，２A是一个集合族。设A1，A2，A3，…，是集合的序列，且两两之间互不相同，则集合{A1，A2，A3，…}是一个集合族，可表示为{Ai

10、iZ}，其中的Z是自然数集合，是该集合的标志集合。定义1.1.5设A,B是两个集合。属于集合A而不属于集合B的所有元素组成的集合，称为A与B的差集，

11、记以A-B。例如，令A={a,b,c,d},B={b,c,e,f}，于是A-B={a,d},B-A={e,f}。定义1.1.6设A,B是两个集合。所有属于A或者属于B的元素做成的集合，称为A和B的并集，记以AB。例如，令A={a,b,c,d},B={b,d,e,f},于是AB={a,b,c,d,e,f}。我们可以把定义1.1.6推广到多个集合的并集。定义1.1.7设A,B是两个集合。由属于A又属于B的元素做成的集合，称为A和B的交集，记以AB。例如，上面集合A和B的AB={b,d}。同样，我们可以把定义1.1.7推广到多个集合的交集。定义1.