主讲人杨凤杰

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

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

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

4、方法。 1、列举法：这种方法把集合中的所 有元素置于花括号内，元素之间用 逗号隔开。如：A=1,2,3,4,5,6。 2、特征法：用小写的英文字母来统一表示该集合的元素，并指出这类元素的共同特征。如A=x|x是正整数且x7。 有限个元素a1,an做成的集合,称为有 穷集（有限集）,记以 a1,an ;无 限个元素做成的集合,称为无穷集。有 穷集中元素的个数称为该集合的元素数， 记为A。 特别,不含元素的集合称为空集,记以。 定义定义1.1.11.1.1 当A,B两个集合的元素完全一样,即A,B两个集合实际上是同一集合时,则称集合A,B相等,记以A=B。 定义定义1.1.21.1.2 设A,B是

5、两个集合。若A的元素都是B的元素,则称B包含A,或称A是B的子集,记以AB。若AB,且AB,则称A是B的真子集,记以AB。 例如：A=1,2,3,4,5， B=x|x是正整数， C=x|x是正整数且x6， 则A是有穷集合，B是无穷集合， A=C，AB，AB。 显然,空集是任何集合的子集且空集 唯一。 当我们所讨论的集合都是某一集合的子集时，这个集合就称为全集，记以E。 由定义，下面的结论是显然的： 对于任意两个集合A，B，A=B的充要条件是AB且BA。 这一结论是我们证明两个集合相等的最常用的方法。定义定义1.1.31.1.3 设A 是集合，A的所有子集为元素做成的集合称为A的幂集，记以（A）

6、或A。显然，若A为有穷集，元素数为n，则A的元素数为 nnnnnccc210幂集具有以下性质:(1) 设A,B是两个集合,AB当且仅当(A)(B)；(2) x(A)当且仅当xA。 定义定义1.1.41.1.4 设C是一个集合。若C的 元素都是集合,则称C为集合族。 若集合族C可表示为C=SddD， 则称D为集合族C的标志（索引）集。 显然，A是一个集合族。设A1，A2，A3， ，是集合的序列，且两两之间互不相同，则集合 A1，A2，A3， 是一个集合族，可表示为Ai|iZ，其中的Z是自然数集合，是该集合的标志集合。 定义定义1.1.51.1.5 设A,B是两个集合。属于 集合A而不属于集合B的

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

8、集。 定义定义1.1.8 1.1.8 设A,B是两个集合，所有序偶 (x,y)做成的集合（其中xA,yB）,称为A,B的直乘积(笛卡儿积)，记以AB。 即AB=(x,y)xA且yB。 例如，令A是直角坐标系中x轴上的点集，B是y轴上的点集，于是AB就和平面点集一一对应。 由排列组合的基本常识不难证明,如果集合A的元数A=m,集合B的元数B=n,则AB中有mn个元素。 直乘积运算有以下性质: (1) 对任意集合A,根据定义有A=,A=； (2) 一般地说,直乘积运算不满足交换律, 即ABBA(当A,B且AB时)； (3)直乘积运算不满足结合律,即 (AB)CA(BC)(当A,B且C时)； (4)

9、 直乘积运算对并和交运算满足分配律,即 A(BC)=(AB)(AC),(BC)A=(BA)(CA), A(BC)=(AB)(AC),(BC)A=(BA)(CA)； (5) 设A,B,C,D是集合,则有: 若AC且BD,则ABCD。 定义定义1.1.91.1.9 设A是一个集合，全集E 与A 的差集称为A的余集或补集,记以 。 例如，令E=a,b,c,d,e,f,A=b,c,于是 =a,d,e,f。 定义定义1.1.101.1.10 设A,B是两个集合。则A与B的环和（对称差）定义为 AB=(A-B)(B-A)。 A与B的对称差还有一个等价的定义，即AB=(AB)-(AB)。 AA 不难证明，对于任意集合A,B,C有如下算律： 1.AA=A,AA=A。 (等幂律) .AB=BA,AB=BA。（交换律） .(AB