离散数学课件(第3章).ppt

《离散数学课件(第3章).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《离散数学》教案计算机科学与技术学院课程学时：64主讲：宋成河南理工大学电子教案第二篇：集合论集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。在现代数学中，每个对象（如数，函数等）本质上都是集合，都可以用某种集合来定义。数学的各个分支本质上都是在研究这种或那种对象集合的性质。集合论已经称为全部现代数学的理论基础。第二篇：集合论集合论的特点是研究对象的广泛性。它总结出由各种对象组成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛应用于各个科学和技术领域中。由于集合论的语言适合描述和研究离散对象及其关系，所以也是计算机科学

2、与工程的理论基础，在程序设计、关系数据库、排队论、开关理论、形式语言和自动机理论等学科领域中都有重要的应用。本篇主要介绍：集合、二元关系和函数第三章：集合与关系§3.1集合的概念与表示§3.2集合的运算§3.3序偶与笛卡尔积§3.4关系及其表示§3.5关系的性质§3.6复合关系和逆关系§3.7关系的闭包运算§3.8集合的划分和覆盖§3.9等价关系与等价类§3.10相容关系§3.11序关系第三章：集合与关系教学目的及要求：深刻理解和掌握有关集合和关系的基本概念和基本运算。教学类容：集合的概念和表示方法、集合的运算、序偶与笛卡尔积、关系及其表示、关系的性质、复合关系

3、和逆关系、关系的闭包运算、集合的划分和覆盖、等价关系与等价类、相容关系、序关系。教学重点：关系及关系的运算、等价关系、序关系教学难点：关系的闭包运算、等价关系、等价类。第三章：集合与关系§3.1集合的概念与表示1、集合的基本概念【定义】具有某种特定性质的事物（客体）的总体。这里的“事物”可以是人，物品，也可以是数学元素。定义的讨论：符号表示：通常用大写的英文字母表示，如A、B、C等。组成集合的对象叫做集合的元素或成员，常用小写的英文字母表示。第三章：集合与关系集合的性质确定性：所谓确定的，是指任何一个对象是不是集合的元素是明确的、确定的，不能模棱两可。每一个对象

4、都能确定是不是某一集合的元素，没有确定性就不能成为集合，例如“个子高的同学”“很小的数”都不能构成集合。这个性质主要用于判断一个集合是否能形成集合。互异性：集合的元素又是能区分的，能区分的是指集合中的元素是互不相同的。如果一个集合中有几个元素相同，算做一个。例如集合1,2,3,3和1,2,3是同一集合。无序性：集合的元素又是无序的，即1,2,3和3,1,2是同一集合第三章：集合与关系集合与元素的关系：设S是集合，a是S的一个元素，记为aS，读做“a属于S”，也可读做“a在S中”。如果a不是S的元素，记为aS，读做“a不属于S”，也可读做“a不

5、在S中”。例如：①26个英文字母组成一个集合，任一英文字母是该集合的元素。②河南理工大学全体学生组成一个集合，该校的每一个学生是这个集合的元素。集合的基数（势）：集合中元素的个数，假设集合为S，则集合S的基数为

6、S

7、，根据集合的基数（元素）是否为有限个，又分为有限集合和无限集合第三章：集合与关系2、集合的表示方法集合有三种表示法。列举法：在花括号“”中列举出该集合的元素，元素之间用逗号隔开。例如：I5=1,2,3,4,5I+=1,2,3,…I=0,1,-1,2,-2,…S=T,F第二种表示法是描述法：用谓词界定集合的元素。例如：Q=x

8、x是

9、有理数R=x

10、x是实数C=x

11、x是复数A=x

12、xI∧0＜x∧x＜5文氏图法：用一条封闭的曲线的内部来表示一个集合的方法，人们常用文氏图描述集合运算和它们之间的关系。如图3.1（形象，直观）。第三章：集合与关系3、集合间的关系【定义】设A，B是任意的集合，当A的每一元素都是B的元素时，则称A是B的子集，也称A包含在B内或B包含A。记为AB或BA。当A不是B的子集时，记为A⊈B。AB用谓词公式表示为：AB(x)(xA→xB)A⊈B用谓词公式表示为：A⊈B(x)(xA∧xB)例如：设A=1，B=1,2，C=1,2,3

13、则AAAB，BC，ACC⊈B可以证明，集合的包含有下列性质：①自反性。即对任意集合A，AA。②传递性。即对任意集合A、B、C，当AB和BC时，AC。第三章：集合与关系【定义】设A，B是集合，如果AB且BA，则称A与B相等。记为A=B。如果A与B不相等，记为A≠B。集合相等也可用谓词公式表示为：A=BAB∧BA(x)(xA→xB)∧(x)(xB→xA)(x)(xA↔xB)例如：设A=1,2，B=1,2，C=2,1则A=C，A≠B由集合相等的定义可以看出，集合相等有下列性质：①自反性:即对任意集合A，A

14、=A。②对称性:即对任意