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

《离散数学》教案 计算机科学与技术学院 课程学时：64 主 讲：宋 成 第二篇：集合论 集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。 在现代数学中，每个对象（如数，函数等）本质上都是集合，都可以用某种集合来定义。数学的各个分支本质上都是在研究这种或那种对象集合的性质。集合论已经称为全部现代数学的理论基础。 第二篇：集合论 集合论的特点是研究对象的广泛性。它总结出由各种对象组成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛应用于各个科学和技术领域中。 由于集合论的语言适合描述和研究离散对象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数据库、排队论、开关理论、形式语言和自动机理论等学科领域中都有重要的应用。 本篇主要介绍：集合、二元关系和函数 第三章：集合与关系 §3.1集合的概念与表示 §3.2集合的运算 §3.3序偶与笛卡尔积 §3.4关系及其表示 §3.5关系的性质 §3.6复合关系和逆关系 §3.7关系的闭包运算 §3.8集合的划分和覆盖 §3.9等价关系与等价类 §3.10相容关系 §3.11序关系 第三章：集合与关系 第三章：集合与关系 §3.1 集合的概念与表示 1、集合的基本概念 【定义】具有某种特定性质的事物（客体）的总体。 这里的“事物”可以是人，物品，也可以是数学元素。 定义的讨论： 符号表示： 通常用大写的英文字母表示，如A、B、C等。组成集合的对象叫做集合的元素或成员，常用小写的英文字母表示。 第三章：集合与关系 集合的性质 确定性：所谓确定的，是指任何一个对象是不是集合的元素是明确的、确定的，不能模棱两可。每一个对象都能确定是不是某一集合的元素，没有确定性就不能成为集合，例如“个子高的同学”“很小的数”都不能构成集合。这个性质主要用于判断一个集合是否能形成集合。 互异性：集合的元素又是能区分的，能区分的是指集合中的元素是互不相同的。如果一个集合中有几个元素相同，算做一个。例如集合?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不在S中”。例如：①26个英文字母组成一个集合，任一英文字母是该集合的元素。②河南理工大学全体学生组成一个集合，该校的每一个学生是这个集合的元素。 集合的基数（势）： 集合中元素的个数，假设集合为S，则集合S的基数为|S|，根据集合的基数（元素）是否为有限个，又分为有限集合和无限集合 第三章：集合与关系 2、集合的表示方法 集合有三种表示法。 列举法：在花括号“??”中列举出该集合的元素，元素之间用逗号隔开。 例如：I5=?1,2,3,4,5? I+=?1,2,3, …? I =?0,1,-1,2,-2, …? S=?T,F? 第二种表示法是描述法：用谓词界定集合的元素。 例如： Q=?x | x是有理数? R=?x | x是实数? C=?x | x是复数? A=?x | 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? 则 A?A A?B，B?C，A?C C?B 可以证明，集合的包含有下列性质： ①自反性。即对任意集合A，A?A。 ②传递性。即对任意集合A、B、C，当A?B和B?C时，A?C。 第