集合代数.ppt
- 文档编号:18071243
- 上传时间:2023-08-10
- 格式:PPT
- 页数:80
- 大小:928KB
集合代数.ppt
《集合代数.ppt》由会员分享,可在线阅读,更多相关《集合代数.ppt(80页珍藏版)》请在冰点文库上搜索。
第6章集合代数,离散数学,中国地质大学本科生课程,本章说明,本章的主要内容集合的基本概念集合、相等、(真)包含、子集、空集、全集、幂集集合运算交、并、(相对和绝对)补、对称差、广义交、广义并文氏图有穷集计数问题集合恒等式本章与后续各章的关系是集合论后面各章的基础是典型的布尔代数系统,引言集合论,集合论是现代数学的基础,几乎与现代数学的各个分支都有着密切联系,并且渗透到所有科技领域,是不可缺少的数学工具和表达语言。
集合论的起源可以追溯到16世纪末期,为了追寻微积分的坚实基础,开始时,人们仅进行了有关数集的研究。
19761983年,康托尔(GeorgCantor)发表了一系列有关集合论研究的文章,奠定了集合论的深厚基础,以后策墨罗(Zermelo)在19041908年列出了第一个集合论的公理系统,并逐步形成公理化集合论。
集合论,我们这里学习集合论,更是因为计算机科学及其应用的研究也和集合论有着极其密切的关系。
集合不仅可以表示数、而且还可以象数一样进行运算,更可以用于非数值信息的表示和处理,如数据的增加、删除、排序以及数据间关系的描述;有些很难用传统的数值计算来处理,但可以用集合运算来处理。
因此,集合论在程序语言、数据结构、编译原理、数据库与知识库、形式语言和人工智能等领域都得到了广泛的应用,并且还得到了发展。
本章对集合论本身及其公理化系统不作深入探讨,主要是介绍集合、子集的基本概念及相关性质;集合间的各种运算和它们满足的运算性质;,内容提要,本章学习要求,6.1集合的基本概念,集合(Set)是不能精确定义的基本概念。
所谓集合,是指我们无意中或思想中将一些确定的、彼此完全不同的客体的总和而考虑为一个整体。
这些客体叫做该集合的元素。
(康托)直观地说,把一些事物汇集到一起组成一个整体就叫集合,而这些事物就是这个集合的元素或成员。
例如:
方程x210的实数解集合:
26个英文字母的集合;坐标平面上所有点的集合;集合通常用大写的英文字母来标记。
指定范围,特定对象,常见的数的集合(固定的符号),集合的表示方法,表示一个集合的方法主要有两种:
列元素法和谓词表示法。
列元素法(roster)是列出集合的所有元素,元素之间用逗号隔开,并把它们用花括号括起来。
Aa,b,c,zZ0,1,2,C桌子,灯泡,老虎,自然数谓词表示法(definingpredicate)是用谓词来概括集合中元素的属性。
Ax|P(x)Bx|xRx210许多集合可以用两种方法来表示,如B也可以写成-1,1。
但是有些集合不可以用列元素法表示,如实数集合。
代表元,X所具有的性质p,集合的元素,集合的元素是彼此不同的,如果同一个元素在集合中多次出现应该认为是一个元素。
例如:
1,1,2,2,31,2,3集合的元素是无序的。
例如:
1,2,33,1,2在本书所采用的体系中规定:
集合的元素都是集合。
元素和集合之间的关系,元素和集合之间的关系是隶属关系,即属于或不属于,属于记作,不属于记作。
例如:
Aa,b,c,d,daA,b,cA,dA,dA,bA,dA。
b和d是A的元素的元素。
可以用一种树形图表示集合与元素的隶属关系。
说明,隶属关系可以看作是处在不同层次上的集合之间的关系。
规定:
对任何集合A都有AA。
A,子集(subset),定义6.1设A,B为集合,如果B中的每个元素都是A中的元素,则称B是A的子集合,简称子集。
这时也称B被A包含,或A包含B,记作BA。
包含的符号化表示为BAx(xBxA),显然对任何集合A都有AA。
隶属和包含的说明,隶属关系和包含关系都是两个集合之间的关系,对于某些集合可以同时成立这两种关系。
例如Aa,a和a既有aA,又有aA。
前者把它们看成是不同层次上的两个集合,后者把它们看成是同一层次上的两个集合。
集合相等(equal),定义6.2设A,B为集合,如果AB且BA,则称A与B相等,记作AB。
相等的符号化表示为:
ABABBA如果A与B不相等,则记作AB。
真子集,定义6.3设A,B为集合,如果BA且BA,则称B是A的真子集,记作BA。
真子集的符号化表示为BABABA如果B不是A的真子集,则记作BA。
例如:
NN,空集(emptyset),定义6.4不含任何元素的集合叫做空集,记作。
空集的符号化表示为:
x|xx。
例如:
x|xRx2+1=0是方程x2+1=0的实数解集,因为该方程无实数解,所以是空集。
空集的性质,推论空集是唯一的。
证明:
假设存在空集1和2,由定理6.1有12,21。
根据集合相等的定义,有12。
定理6.1空集是一切集合的子集。
证明:
任给集合A,由子集定义有Ax(xxA)右边的蕴涵式因前件假而为真命题,所以A也为真。
集合A中元素的数目称为集合A的基数(basenumber),记为|A|。
如|A|是有限的,则称集合A为有限集,如|A|是无限的,则称集合A为无限集。
求下列集合的基数。
(1)A=;
(2)B=;(3)C=a,b,c;(4)D=a,b,c。
解|A|=0,,有限集和无限集,|B|=1,,|C|=3,,|D|=2。
n元集,含有n个元素的集合简称n元集,它的含有m(mn)个元素的子集叫做它的m元子集。
例6.1A1,2,3,将A的子集分类:
0元子集(空集),1元子集(单元集),1,2,3,2元子集,1,2,1,3,2,3,3元子集,1,2,3,幂集(powerset),一般地说,对于n元集A,它的0元子集有个,1元子集有个,m元子集有个,n元子集有个。
子集总数为,定义6.5设A为集合,把A的全部子集构成的集合叫做A的幂集,记作P(A)(或PA,2A)。
幂集的符号化表示为P(A)x|xA若A是n元集,则P(A)有2n个元素。
全集,定义6.6在一个具体问题中,如果所涉及的集合都是某个集合的子集,则称这个集合为全集,记作E。
说明,全集是有相对性的,不同的问题有不同的全集,即使是同一个问题也可以取不同的全集。
例如,在研究平面上直线的相互关系时,可以把整个平面(平面上所有点的集合)取作全集,也可以把整个空间(空间上所有点的集合)取作全集。
一般地说,全集取得小一些,问题的描述和处理会简单些。
文氏图(VennDiagram),集合之间的关系和运算可以用文氏图给予形象的描述。
文氏图的构造方法如下:
画一个大矩形表示全集E(有时为简单起见可将全集省略)。
在矩形内画一些圆(或任何其它的适当的闭曲线),用圆的内部表示集合。
不同的圆代表不同的集合。
如果没有关于集合不交的说明,任何两个圆彼此相交。
图中阴影的区域表示新组成的集合。
可以用实心点代表集合中的元素。
6.2集合的运算,定义6.7设A,B为集合,A与B的并集AB,交集AB,B对A的相对补集AB分别定义如下:
ABx|xAxB(unionset)ABx|xAxB(intersectionset)ABx|xAxB(differenceset),举例,设Aa,b,c,Ba,Cb,d则有ABa,b,c,ABa,ABb,c,BA,BC,说明,如果两个集合的交集为,则称这两个集合是不相交的。
例如B和C是不相交的。
n个集合的并和交,两个集合的并和交运算可以推广成n个集合的并和交:
A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn上述的并和交可以简记为:
A1A2An,A1A2An,两个集合的并和交运算可以推广到无穷多个集合的情况:
A1A2,A1A2,对称差集,定义6.8设A,B为集合,A与B的对称差集AB定义为:
AB(AB)(BA)对称差运算的另一种定义是AB(AB)(AB)例如:
Aa,b,c,Bb,d,则ABa,c,d,绝对补集,定义6.9AEAx|xExA因为E是全集,xE是真命题,所以A可以定义为:
Ax|xA例如:
Ea,b,c,d,Aa,b,cAd,文氏图的实例,集合的应用,例1.4.1用H代表硬币正面,T代表硬币反面。
试写出当扔出三个硬币时可能出现的结果所组成的集合。
解:
8种可能:
HHH,HHT,HTH,HTT,THH,THT,TTH,TTT。
但这三个硬币没有顺序之分,即HHT和HTH是同一个元素,所以A=HHH,HHT,HTT,TTT。
例,一个正三角形被均分为三个小三角形,如下图所示。
现用黑、白二色对其小三角形着色,假设经旋转能使之重合的图像算一种。
试写出由不同图像构成的集合。
解,因为每个小三角形均可着色,三个小三角形共有222=8种着色方案,所以可得8种不同的图像。
又因为经旋转能使之重合的图像算一种,如图1.4,所以共有4种不同的着色方案。
因此由不同图像构成的集合为1,2,5,8。
广义并和广义交,定义6.10设A为集合,A的元素的元素构成的集合称为A的广义并,记为A。
符号化表示为Ax|z(zAxz)定义6.11设A为非空集合,A的所有元素的公共元素构成的集合称为A的广义交,记为A。
符号化表示为Ax|z(zAxz),例6.2,例6.2设Aa,b,c,a,c,d,a,e,fBaCa,c,d则Aa,b,c,d,e,fBaCac,dAaBaCac,d,广义并与广义交的说明,若AA1,A2,An,则AA1A2An若AA1,A2,An,则AA1A2An在后面的叙述中,若只说并或交,则这都是指集合的初级并或初级交;如果在并或交前边冠以“广义”两个字,则指集合的广义并或广义交。
为了使得集合表达式更为简洁,我们对集合运算的优先顺序做如下规定:
称广义并、广义交、幂集、绝对补运算为一类运算并、交、相对补、对称差运算为二类运算。
一类运算优先于二类运算一类运算之间由右向左顺序进行二类运算之间由括号决定先后顺序。
例6.3,例6.3设Aa,a,b计算A,A,A(AA)解答Aa,bAaAabAaA(AA)(ab)(aba)(ab)(b-a)b,6.3有穷集的计数,使用文氏图可以很方便地解决有穷集的计数问题。
首先根据已知条件把对应的文氏图画出来。
一般地说,每一条性质决定一个集合。
有多少条性质,就有多少个集合。
如果没有特殊说明,任何两个集合都画成相交的然后将已知集合的元素数填入表示该集合的区域内。
通常从n个集合的交集填起,根据计算的结果将数字逐步填入所有的空白区域。
如果交集的数字是未知的,可以设为x。
根据题目中的条件,列出一次方程或方程组,就可以求得所需要的结果。
例6.4,例6.4对24名会外语的科技人员进行掌握外语情况的调查。
其统计结果如下:
会英、日、德和法语的人分别为13,5,10和9人,其中同时会英语和日语的有2人,会英、德和法语中任两种语言的都是4人。
已知会日语的人既不懂法语也不懂德语,分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。
解:
令A,B,C,D分别表示会英、法、德、日语的人的集合。
根据题意画出文氏图。
设同时会三种语言的有x人,只会英、法或德语一种语言的分别为y1,y2和y3人。
将x和y1,y2,y3填入图中相应的区域,然后依次填入其它区域的人数。
例6.4,2,5-2,y1+2(4-x)+x+213y2+2(4-x)+x9y3+2(4-x)+x10y1+y2+y3+3(4-x)+x24-5,补充容斥原理与鸽笼原理,容斥原理是研究若干有限集合交与并的计数问题鸽笼原理则是研究某些特定对象的存在性问题。
容斥原理,定义所谓容斥,是指我们计算某类物体的数目时,要排斥那些不应包含在这个计数中的数目,但同时要包容那些被错误地排斥了的数目,以此补偿。
这种原理称为容斥原理(ThePrincipleofInclusion-exclusion),又称为包含排斥原理。
定理6.3.1,设A和B是任意有限集合,有|AB|=|A|B|AB|。
分析由图容易看出,AB=(A-B)(AB)(B-A),A=(A-B)(AB)B=(AB)(B-A),AB,A-B,B-A,推论6.3.2设U为全集,A和B是任意有限集合,则,例1,对所给的集合验证定理6.3.1。
(1)A=1,2,3,4,B=2,3,5,6,8;
(2)A=1,2,3,4,B=5,6,7,8。
根据定理6.3.1,需先计算AB和AB,再计算|A|,|B|和|AB|,然后代入公式(6.3.1)两端,验证等式即可。
分析,解
(1)AB=1,2,3,4,5,6,8,AB=2,3|AB|=7,|AB|=2。
又|A|=4,|B|=5,|A|B|AB|=452=7=|AB|即定理6.3.1成立;
(2)略。
三个集合的情形,定理6.3.3设A,B和C是任意三个有限集合,有推论6.3.4设U为全集,A,B和C是任意有限集合,则,例2,调查260个大学生,获得如下数据:
64人选修数学课程,94人选修计算机课程,58人选修商贸课程,28人同时选修数学课程和商贸课程,26人同时选修数学课程和计算机课程,22人同时选修计算机课程和商贸课程,14人对三种课程都选修。
问
(1)调查中三种课程都不选的学生有多少?
(2)调查中只选修计算机科学课程的学生有多少?
例2解,设A、B、C分别表示选修数学课程,计算机课程和商贸课程的人构成的集合,则三种课程都不选的学生集合为,只选修计算机科学课程学生的集合为。
例2解(续),
(1)|U|=260,|A|=64,|B|=94,|C|=58,|AC|=28,|AB|=26,|BC|=22,|ABC|=14,所以利用容斥原理得=106
(2),容斥原理的推广,定理6.3.5设A1,A2,An是任意n个有限集合,则推论6.3.6设S为全集,A1,A2,An是任意n个有限集合,则,包含排斥原理,定理6.2设S为有穷集,P1,P2,Pm是m个性质。
S中的任何元素x或者具有性质Pi,或者不具有性质Pi(i=1,2,m),两种情况必居其一。
令Ai表示S中具有性质Pk的元素构成的子集,则S中不具有性质P1,P2,Pm的元素为,推论,S中至少具有一条性质的元素数为,例6.5,例6.5求1到1000之间(包含1和1000在内)既不能被5和6,也不能被8整除的数有多少个。
解答设Sx|xZ1x1000Ax|xSx可被5整除Bx|xSx可被6整除Cx|xSx可被8整除|T|表示有穷集T中的元素数x表示小于等于x的最大整数lcm(x1,x2,xn)表示x1,x2,xn的最小公倍数,例6.5,|A|1000/5200|B|1000/6166|C|1000/8125|AB|1000/lcm(5,6)33|AC|1000/lcm(5,8)25|BC|1000/lcm(6,8)41|ABC|1000/lcm(5,6,8)8将这些数字依次填入文氏图,得到,例6.5,根据包含排斥原理,所求不能被5,6和8整除的数应为,由文氏图也可得知,不能被5,6和8整除的数有1000(200+1003367)600个。
6.3.2鸽笼原理,鸽笼原理(PigeonholePrinciple)又称为抽屉原理、鸽舍原理,是指如下定理。
定理6.3.7(鸽笼原理)若有n+1只鸽子住进n个鸽笼,则有一个鸽笼至少住进2只鸽子。
证明(反证法)假设每个鸽笼至多住进1只鸽子,则n个鸽笼至多住进n只鸽子,这与有n+1只鸽子矛盾。
故存在一个鸽笼至少住进2只鸽子。
注意:
(1)鸽笼原理仅提供了存在性证明;
(2)使用鸽笼原理,必须能够正确识别鸽子(对象)和鸽巢(某类要求的特征),并且能够计算出鸽子数和鸽巢数。
例3,抽屉里有3双手套,问从中至少取多少只,才能保证配成一双?
答:
4只。
例4,设1到10中任意选出六个数,那么其中有两个数的和是11。
证明
(1)构造5个鸽笼:
A1=1,10,A2=2,9,A3=3,8,A4=4,7,A5=5,6
(2)选出的6个数为鸽子.根据鸽笼原理,所选出的6个数中一定有两个数属于同一个集合,这两个数的和为11。
定理6.3.8,若有n只鸽子住进m(mn)个鸽笼,则存在一个鸽笼至少住进只鸽子。
这里,表示小于等于x的最大整数。
例5,如果一个图书馆里30本离散数学书共有1203页,那么必然有一本离散数学书至少有41页。
证明设页是鸽子,离散数学书是鸽笼,把每页分配到它所出现的离散数学书中,根据定理2.4.5,则存在一个鸽笼至少住进=41,即结论得证。
6.4集合恒等式,下面的恒等式给出了集合运算的主要算律,其中A,B,C代表任意集合。
幂等律AAA(6.1)AAA(6.2)结合律(AB)CA(BC)(6.3)(AB)CA(BC)(6.4)交换律ABBA(6.5)ABBA(6.6)分配律A(BC)(AB)(AC)(6.7)A(BC)(AB)(AC)(6.8)同一律AA(6.9)AEA(6.10),6.4集合恒等式,零律AEE(6.11)A(6.12)排中律AAE(6.13)矛盾律AA(6.14)吸收律A(AB)A(6.15)A(AB)A(6.16)德摩根律A(BC)(AB)(AC)(6.17)A(BC)(AB)(AC)(6.18)(BC)BC(6.19)(BC)BC(6.20)E(6.21)E(6.22)双重否定律(A)A(6.23),集合运算性质的一些重要结果,ABA,ABB(6.24)AAB,BAB(6.25)ABA(6.26)ABAB(6.27)ABBABABAAB(6.28)ABBA(6.29)(AB)CA(BC)(6.30)AA(6.31)AA(6.32)ABACBC(6.33),集合恒等式的证明方法,逻辑演算法利用逻辑等值式和推理规则集合演算法利用集合恒等式和已知结论,逻辑演算法的格式,题目:
AB证明:
x,xAxB所以AB或证PQQP,题目:
AB证明:
x,xAxB所以AB,集合演算法的格式,题目:
AB证明:
AB所以AB,题目:
AB证明:
AB所以AB,例6.8,例6.8证明式6.17,即A(BC)(AB)(AC)证明对任意的x,有xA(BC)xAxBCxA(xBxC)xA(xBxC)xA(xBxC)(xAxB)(xAxC)xABxACx(AB)(AC)所以A(BC)(AB)(AC),例6.9,例6.9证明式6.10,即AEA证明对任意的x,有xAExAxExA(因为xE是恒真命题)所以AEA,例6.10,例6.10假设已知等式6.16.14,试证等式6.15,即A(AB)A。
证明A(AB)(AE)(AB)(由等式6.10)A(EB)(由等式6.8)A(BE)(由等式6.5)AE(由等式6.11)A(由等式6.10),例6.11,例6.11证明等式6.27,即ABAB证明对于任意的x,有xABxAxBxAxBxAB所以ABAB。
说明,等式6.27把相对补运算转换成交运算,这在证明有关相对补的恒等式中是很有用的。
例6.12,例6.12证明(AB)BAB证明(AB)B(AB)B(AB)(BB)(AB)EAB,例6.13,例6.13证明命题6.28是真命题。
ABBABABAAB说明式6.28给出了AB的另外三种等价的定义,这不仅为证明两个集合之间的包含关系提供了新方法,同时也可以用于集合公式的化简。
证明思路ABBABABAABABB,例6.13,证明ABBAB对于任意的x,有xAxAxBxABxB(因为ABB)所以AB。
例6.13,证明ABABA显然有ABA,下面证AAB。
对于任意的x,有xAxAxAxAxB(因为AB)xAB所以AAB由集合相等的定义有ABA。
例6.13,证明ABAABABAB(AB)B(因为ABA)A(BB)A,例6.13,证明ABABB。
由例6.10(AB)BAB及AB有ABB(AB)BB,例6.14,例6.14化简(ABC)(AB)(A(BC)A)解答因为ABABC,AA(BC),由式6.28有:
(ABC)(AB)(A(BC)A)(AB)ABA,例6.15,例6.15已知ABAC,证明BC。
证明已知ABAC,所以有A(AB)A(AC)(AA)B(AA)C(由式6.30)BC(由式6.32)BC(由式6.29)BC(由式6.31),学习要求,熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示熟练掌握集合的交、并、(相对和绝对)补、对称差、广义交、广义并的定义及其性质掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法牢记基本的集合恒等式(等幂律、交换律、结合律、分配律、德摩根律、收律、零律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律)准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式,作业,习题六5,6,7,8,17,23,25,28,典型题,判断元素与集合的隶属关系以及集合之间的包含关系集合的基本运算题有关集合运算性质的分析题集合相等或者包含的证明题有穷集合的计数问题,典型例题一,判断下列命题是否为真
(1)xx
(2)xx(3)xx,x(4)xx,x(5)xxx(6)xxx(7)若xA,AP(B),则xP(B)(8)若xA,AP(B),则xP(B),答案
(1)真
(2)假(3)真(4)真(5)真(6)真(7)假(8)真,分析,典型例题一的分析,判断元素a与集合A的隶属关系是否成立的基本方法:
把a作为一个整体,检查它在A中是否出现,注意这里的a可能是集合表达式。
判断集合包含AB一般可以使用以下四种方法:
若A、B是用枚举方式定义的,依次检查A的每个元素是否在B中出现。
若A、B是用谓词法定义的,且A、B中元素性质分别为P和Q,那么“如果P则Q”意味着AB,“P当且仅当Q”意味着AB。
通过集合运算判断AB,即ABB,ABA,AB3个等式中有一个为真,则AB。
可以通过文氏图判断集合的包含(不是证明)。
典型例题二,判断以下命题的真假
(1)A(BC)(A)(AC)
(2)(AB)(BA)(3)A(BC)(AB)C(4)(AB)(BA)(5)(AB)A(6)(AB)(BA)A(7)ABAB,答案
(1)真
(2)真(3)假(4)假(5)假(6)假(7)假,分析,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 集合 代数