离散数学集合论部分PPT课件.ppt

第二部分集合与关系对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如程序设计语言、数据结构、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。本部分从集合的直观概念出发，介绍了集合论中的一些基本概念和基本理论。集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。集合论的特点是研究对象的广泛性，集合是各种不同对象的抽象，这些对象可以是数或图形，也可以使任意其它事务。1.二十六个英文字母可以看成是一个集合；2.所有的自然数看成是一个集合；3.重庆邮电大学计算机学院2010级的本科学生可以看成是一个集合；4.这间教室中的所有座位可以看成是一个集合。组成一个集合的那些对象或单元称为这个集合的元素。通常，用小写的英文字母a,b,c,…表示集合中的元素。元素可以是单个的数字也可以是字母，还可以是集合。如：A={a,c,b};B={{a},{b},{c}}元素与集合的属于关系：特别注意：①集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不改变，即{a,a,b,c,d,c}={a,b,c,d}。②集合的元素可以是具体事物，可以是抽象概念，也可以是集体，如一本书，一支笔；集合{1,2,3}可以是集合B={一本书，一支笔，{1,2,3}}的元素。特别地，以集合为元素的集合称为集合族或集合类如A={{1,2,3},{8,9,6}}。③集合中元素之间可以有某种关联，也可以彼此毫无关系。有限集A中所含元素的个数称为集合的元数。记作：|A|如：A={1,3,2,4,5,9}则|A|=6；设A是所有英文字母组成的集合，则A=26。特别，||=0列举法(列元素法)：将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V={a,b,c,d,e}或B={1,2,3,4,5,6,……}。描述法(谓词表示法):将集合元素的条件或性质用文字或符号在花括号内竖线后面表示出来。A={x|关于x的一个命题P};如：B={x|0<x<10};B={x|x=a2,a是自然数}。几类特殊集合:N={0,1,2,3,···}，即自然数集合。Z={···,-2,-1,0,1,2,3,···}，即整数集合。Z+={1,2,3,···}，即正整数集合。Q=有理数集合。R=实数集合。C=复数集合。确定性；互异性；无序性；多样性；任何一个对象，或者是这个集合的元素，或者不是，二者必居其一；例如：A={x|x是自然数，且x<100}；B={x|x+1=3}；C={x|x是大学生}。集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。例如：集合A={a,b,c,c,b,d}，实际上，应该是A={a,b,c,d}。再如{1,2,3,2,4}={1,2,3,4}。集合与其中的元素的顺序无关；例如：集合{a,b,c,d,e}、{d,c,e,a,b}、{e,c,d,b,a}，都是表示同一个集合。集合{4,2,1,3}={1,2,3,4}。集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。例如：A={a,{a},{{a},b},{{a}},1}；A={1,a,*,-3,{a,b},{x|x是汽车},地球}注意:对于任何集合A,都有AA。设A，B是两个集合，若B的元素都是A的元素，则称B是A的子集，也称A包含B，或B被A包含，记以BA，或AB。若BA，且AB，则称B是A的真子集，也称A真包含B，或B真包含于A，记以AB，或BA。当两个集合A和B的元素完全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记为A=B。符号化表示为：A=BAB∧BA例：设A={x|x是偶数，且0<x<10}，B={2,4,6,8}，则A=B。注：说明两个集合A、B相等，需说明两个问题：1、A是集合B的子集（AB）（任意元素a∈A，有a∈B）2、B是集合A的子集（AB）（任意元素a∈B，有a∈A）集合的包含关系也可表成AB(x)(xAxB)这表明，要证明AB，只需对任意元素x，有下式xAxB成立即可。空集注意：与{}是不同的。{}是以为元素的集合，而没有任何元素，能用构成集合的无限序列：，{}，{{}}，···该序列除第一项外，每项均以前一项为元素的集合。定理：空集是一切集合的子集。证明：对于任何集合A，由子集定义有,φAx(x∈φx∈A)右边的蕴涵式中前件为x∈φ为假，所以整个蕴涵式对一切x为真，所以φA为真推论：空集是唯一的。证明:如不唯一,设存在空集φ1和φ2,由空集是一切集合的子集得φ1φ2和φ2φ1。根据集