离散数学第一章第1节.ppt

《离散数学第一章第1节.ppt》由会员分享，可在线阅读，更多相关《离散数学第一章第1节.ppt（74页珍藏版）》请在三一办公上搜索。

1、第一章 集合论基础,1.1 集合的基本概念1.2 关 系 1.3 映 射,集合论发展史,集合论(Set Theory)是现代数学的基础它的起源可追溯到16世纪末，主要是对数集进行卓有成效的研究集合论实际发展是由 19世纪 70年代德国数学家康托尔(G Cantor)在无穷序列和分析的有关课题的理论研究中创立的Cantor对具有任意特性的无穷集合进行了深入的探讨，提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深厚基础因此，Cantor被誉为集合论的创始人他创立的集合论是实数理论，以至整个微积分理论体系的基础。,集合论创始人 康托尔 德国数学家(Georg Cantor 1845191

2、8),随着集合论的发展，以及它与数学哲学密切联系所作的讨论，1900年前后，出现了许多悖论，有力冲击了或者说动摇了集合论的发展（数学史上的三次危机无理数的发现第一次数学危机 无穷小是零吗？第二次数学危机 悖论的产生第三次数学危机）,1.1 集合的基本概念,一、基本概念什么是集合(Set)？“所要讨论的一类对象的整体”；“具有同一性质单元的集体”“所谓集合，是指我们无意中或思想中将一些确定的，彼此完全不同的客体的总和而考虑为的一个整体。这些客体叫做该集合的元素”通常，用大写的英文字母A,B,C,表示集合；,1、二十六个英文字母可以看成是一个集合；2、这间教室中的所有座位可以看成是一个集合。又如：

3、平面上的所有点的整体构成平面点集；所有连续函数的整体构成连续函数集等。,例如:,集合的元素(member或element),组成一个集合的那些对象或单元称为这个集合的元素。通常，用小写的英文字母a,b,c,表示集合中的元素,设A是一个集合，a是集合A中的元素，记以aA，读作a属于A；若a不是集合A中的元素，则记以aA，读作a不属于A。例如：A是正偶数集合，则2A，8A，36A；而 3A，9A，17A,属于(belong to),约定：存在一个没有任何元素的集合，称为空集(empty set)，记为，有时也用来表示。约定，所讨论的对象的全体称为全集(universal set)，记作E或U，我们

4、所讨论的集合都是全集的子集。全集是相对的。,空集、全集,有限个元素a1,a2,an 构成的集合，称为有限集或有穷集(finite set),记为a1,a2,an；无限个元素构成的集合，称为无穷集(infinite set)。例：空集是有限集，所有英文字母组成的集合是有限集，整数集合是无限集。,有限集、无限集,设A是有穷集合，A中元素的个数称为集合A的元素数，记为A。例如，设A是所有小写英文字母组成的集合，则A=26。特别，|=0，|=1,集合的元素数（基数）,列举法；将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V=a,e,i,o,u 或B=1,4,9,16,25,3

5、6。描述法；通过描述集合中元素的共同特征来表示集合，例如：V=x|x是英语元音字母，B=x|x=a2,a是非零整数,常用的集合表示法,文氏图(Venn Diagram)英国数学家John Venn提出用一个大的矩形表示全集，在矩形内画一些圆或其它简单封闭曲线，用其内部来表示集合，可以用一些点来表示集合中的特定元素。,E,V,a,u,注意：文氏图只是示意图，虽然直观、有助于记忆，但不用于证明。,例如：集合V=a,u，用文氏图表示:,常用的数集合N：自然数(natural numbers)集合 N=0,1,2,3,Z：整数(integers)集合 Z=0,1,2,=,-2,-1,0,1,2,Q：有

6、理数(rational numbers)集合R：实数(real numbers)集合C：复数(complex numbers)集合,递归指定集合,通过计算规则定义集合中的元素,例如:设a0=1,a1=1,an+1=an+an-1,于是A=a0,a1,a2,=ak|k0.巴科斯范式BNF表示法 BNF常常用来定义高级程序设计语言的标识符或表达式集合.,确定性；互异性；无序性；多样性；,集合的特征,任何一个对象，或者是这个集合的元素，或者不是，二者必居其一；例如：A=x|x是自然数，且x100B=x|x是年轻人,确定性,集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。例如：集合A=a,

7、b,c,c,b,d，实际上，应该是A=a,b,c,d,互异性,集合与其中的元素的顺序无关，集合中的元素是没有顺序的，或者说，我们不考虑集合中元素的顺序。例如：集合a,b,c,d,e、d,c,e,a,b、e,c,d,b,a，都是表示同一个集合。,无序性,集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。例如：A=a,a,a,b,a,1B=1,a,*,-3,a,b,x|x是汽车,地球,板儿砖,多样性,当A,B两个集合的元素完全一样，即A，B两个集合实际上是同一个集合时，则称集合A，B相等，记以A=B。例：设A=x|x是偶数，且0 x10，B=2,4,6,8，则A=B。1，3，

8、51，3，5,【定义】集合相等,设A，B是两个集合，若A的元素都是B的元素，则称B包含A，或称A是B的子集，记以A B。若AB，且AB，则称A是B的真子集(proper subset)，记以AB。,【定义】子集(subset),设A=2,4,6,8，B=x|x是正偶数，C=x|x是整数,则有A B，B C，AC,并且A B，B C，A C。x A 当且仅当 x A。,例：,对任意集合A,有A A。若AB，BC，则AC。对于任意两个集合A、B，A=B 当且仅当 AB且BA。这一结论是证明两个集合相等时最常用的方法。空集是任意集合的子集，是任意非空集合的真子集，且空集是唯一的。（，）,重要结论,是

9、否存在集合A和B,使得AB 且A B？若存在，请举一例。设A=a，B=a,a,b,c，则有:AB 且A B 再例如：且,讨论：,设A 是集合，A的所有子集为元素构成的集合称为A的幂集，记以(A)或 2A。(A)=S|S A例：A=a,b,c，则(A)=,a,b,c,a,b,a,c,b,c,a,b,c,【定义1.1.3】幂集(power set),注意：,幂集合仍然是集合。例如，用枚举法写出集合a,b的幂集合：正确的写法：(A)=,a,b,a,b 错误的写法：(A)=,a,b,a,b？写出()，()，(),若A为有穷集，元素数|A|=n，则|2A|=Cn0+Cn1+Cnn=2n。证明：首先，集合

10、A的子集的元素个数在0到n之间，基于这个事实，我们可以从A中取0个元素构成A的子集，有Cn0 个，从A中取1个元素构成A的子集，有Cn1 个，以此类推，从A中取n个元素构成A的子集，有Cnn 个。而且取的元素个数不同，肯定得到不同的子集，根据加法原理，集合A一共有Cn0+Cn1+Cnn 个子集。,幂集的性质：,其次，要获取集合A的一个子集，那么，A中每个元素都有两种取法，要么在这个子集中，要么不在。而且每个元素的取法之间是相互独立的，互不影响，这样，我们根据乘法原理，可以很容易的得出集合A一共有：222=2n 个子集。这样，我们就证明了若A为有穷集，|A|=n，则|2A|=Cn0+Cn1+Cn

11、n=2n。,幂集的性质,1.设A、B是两个集合,AB 当且仅当(A)(B)。证明：必要性，任取C(A)，则CA，又由AB知，CB，即，C(B)，故(A)(B)。充分性，任取xA，则x A，即x(A)，而(A)(B)，故x(B)，即x B，故xB。因此AB。（如果(A)(B)，那么A的所有子集都是B的子集，容易知道AA，则AB。）,幂集的性质,2.x(A)当且仅当 xA。证明：必要性，从x(A)推出xA。如果x(A)，那么x是属于A的幂集合的，从而x是A的一个子集，即xA。充分性，从xA推出x(A)。如果xA，那么x是A的子集，而(A)是以A的所有子集为元素的，这样，就有x(A)。,设C是一个集

12、合。若C的元素都是集合，则称C为集合族。若集合族C可表示为C=SddD，则称D为集合族C的标志（索引）集。,【定义】集合族、标志集,显然，2A是一个集合族。设A1,A2,A3,是集合的序列，且两两之间互不相同，则集合A1,A2,A3,是一个集合族，可表示为 Ai|iN+，其中,N是自然数集合(除去0)，是该集合的标志集合。,二、集合的运算及性质,设A，B是两个集合。由属于集合A而不属于集合B的所有元素组成的集合，称为A与B的差集，记以A-B，或AB。即A-B=x|xA且xB例.令A=a，b，c，d，B=c，d，e，f，于是 A-B=a，b。,【定义1.1.5】集合的差集(Difference)

13、,差集的文氏图,A,B,AB,E,设A，B是两个集合。所有属于A或者属于B的元素构成的集合，称为A和B的并集，记以AB。即AB=x|xA或xB例如，令A=a，b，c，d，B=c，d，e，f，于是 AB=a，b，c，d，e，f。,【定义1.1.6】集合的并集(Union),并集的文氏图,A,B,AB,设A，B是两个集合。由属于A且属于B的元素组成的集合，称为A和B的交集，记以AB。即AB=x|xA且xB例如，令A=a，b，c，d，B=c，d，e，f，于是 AB=c，d。,【定义1.1.7】集合的交集(Intersection),交集的文氏图,A,B,AB,设A1，A2，An是n个集合，则，A1A

14、2An，简记为 A1A2An，简记为,并集和交集的推广(满足结合律),【定义1.1.8】集合的补集(Complement),设A是一个集合，全集E与A的差集称为A的余集或补集，记以。即例如，令E=a，b，c，d，e，f，A=b，c，于是=a，d，e，f。特别，,补集的文氏图,A,A的补集,E,设A，B是两个集合。则A与B的环和(对称差),记以AB,定义为 AB=(A-B)(B-A)。A与B的对称差还有一个等价的定义，即AB=(AB)-(AB)。例：令A=a，b，c，d，B=c，d，e，f，于是 AB=a，b，e，f。,【定义9】集合的环和（对称差）,环和（对称差）的文氏图,A,B,AB,E,设

15、A，B是两个集合，则A与B的环积定义为 A B=ABA B（AB）（AB）,【定义10】集合的环积,环积的文氏图,A,B,A B=（AB）（AB）,E,将(a1,a2,an)称为有序n元组，其中，a1是其第一个元素，a2是其第二个元素，an是其第n个元素。两个有序n元组(a1,a2,an)和(b1,b2,bn)相等 当且仅当 ai=bi,i=1,2,n,【定义11】有序n元组(ordered n-tuple),对于有序n元组，当n=2 时，将其称作有序二元组，也称作有序对，或序偶。有序对的特点：若ab,则（a，b）（b，a）两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d,【定义12

16、】有序对(ordered pairs),设A，B是两个集合，所有有序对(x,y)构成的集合(其中xA，yB)，称为A，B的直乘积(笛卡儿积)，记以AB。AB=(x，y)xA且yB。,【定义13】笛卡儿积(Cartesian product),笛卡儿(RenDescartes，15961650)在数学史上，笛卡儿因与费马共同创立解析几何而闻名于世。与此同时，笛卡儿还是一位 哲学家、物理学家、生物学家，尤其在哲学上的杰出贡献使他成为当之无愧的一代哲学大师。,设A1,A2,An是n个集合，由所有有序n元组(a1,a2,an)做成的集合(其中aiAi，i=1,2,n)，称为A1,A2,An的直乘积(笛

17、卡儿积)，记以A1A2 An。A1A2 An=(a1,a2,an)aiAi，i=1,2,n。,【定义14】笛卡儿积的推广,设A=1,2，B=a,b,c,则AB=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)；BA=(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)；,例如：,|AB|=A B；对任意集合A，有A=，A=；直乘积运算不满足交换律，即ABBA(当A,B 且AB时)；直乘积运算不满足结合律，即(AB)CA(BC)(当A,B,C 时),直乘积的性质,5.直乘积运算对并和交运算满足分配律，即:A(BC)=(AB)(AC)，(BC)A=(BA)(

18、CA)，A(BC)=(AB)(AC)，(BC)A=(BA)(CA)；6.设A，B，C，D是集合，若AC且BD，则AB CD。,等幂律：AA=A，AA=A。交换律：AB=BA，AB=BA。结合律：(AB)C=A(BC)，(AB)C=A(BC)。分配律：A(BC)=(AB)(AC)，A(BC)=(AB)(AC)。5.吸收律：A(AB)=A，A(AB)=A。,对于任意集合A,B,C有如下算律：,互补律：De Morgan律：同一律：EA=A，A=A。零一律：A=，EA=E。双重否定律：,证明：A(BC)=(AB)(AC),证明：先证A(BC)（AB）（AC）。任取 aA(BC)，则aA 并且 a B

19、C。由a BC知，aB或a C。若aB，则aAB；若aC，则aAC。因此，aAB或aAC,即 a(AB)(AC)。再证(AB)(AC)A(BC)。任取 a(AB)(AC),则aAB或aAC。若aAB，则aA且a B；若aAC，则aA且a C。总之，aA，且aB或aC，即aA且 a BC，亦即 aA(BC)。综上：(AB)(AC)=A(BC)。,证明：任取，即aAB，亦即aA且aB，于是 且，故 所以任取，即 且，亦即aA且aB，于是aAB，故，所以综上，得证。,证明：,结论1 设A1，A2是有限集，且不相交，则|A1 A2|=|A1|+|A2|。结论2 设A1，A2是任意有限集，则|A1 A2

20、|=|A1|+|A2|-|A1 A2|。证明：A1A2可表为不相交的A1 和A2A1的并，于是，|A1 A2|=|A1|+|A2 A1|。A2 可表为不相交的A2 A1和A1 A2的并，于是|A2|=|A2 A1|+|A1 A2|。由此得：|A1 A2|=|A1|+|A2|-|A1 A2|。,容斥原理(principle of inclusion-exclusion),结论3 设A1，A2，A3是任意有限集，则|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|证明：|A1A2A3|=|（A1A2）A3|=|A1A2|+|A3|-|(A1A

21、2)A3|=|A1|+|A2|-|A1A2|+|A3|-|(A1A3)(A2A3)|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|。,设A1，A2，An是n个有限集合，则,容斥原理(principle of inclusion-exclusion),称为包含排斥原理，简称容斥原理。,容斥原理(举例)例1:在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少?解 设E=xN|1x10000,|E|=10000A=xE|x=k2k Z,|A|=100 B=x E|x=k3 k Z,|B|=21则|(AB)|=|E|-|AB|=|E|-

22、(|A|+|B|-|AB|)=10000-100-21+4=9883注意AB=xE|x=k6k Z,|A B|=4.#,其它算律：,例，证明：,从而有：,小结：证明集合的包含关系的常用方法,令A,B是两个集合，证AB的常用方法：方法1 利用定义来证明集合的包含关系。要证明AB，首先任取xA，再演绎地证出x B成立。特别，当A是无限集时，因为我们不能对x A，逐一地证明x B成立，所以证明时“x是任取的”就特别重要。例.证明若AB,则,方法2 设法找到一个集合T,满足AT且TB,由包含关系的传递性有AB.例.证明A-CAB,方法3 利用AB的等价定义,即AB=B,AB=A或A-B=来证.例.证明

23、 AC且BC 当且仅当 ABC.证明:必要性.(AB)C=(AC)(BC)=CC=C,所以ABC.充分性.AC(AC)B=(AB)C=C 所以AC,同理可证BC.,方法4 利用已知包含式的并、交等运算得到新的包含式例.证明若ACBC且A-CB-C，则AB.证明：（AC)(A-C)(BC)(B-C)（AC)(A)(BC)(B)A(C)B(C)AEBE，所以AB。,方法5 反证法 如上例(证明ACBC且A-CB-C则AB.)，若不然，则有xA 且xB.若xC,在xAC但xBC，与ACBC矛盾；若xC，则xAC但xB-C，与A-CB-C矛盾。,方法1 若A，B 是有限集，证明A=B可通过逐一比较两集

24、合所有元素均一一对应相等，若A，B 是无限集，通过证明集合包含关系的方法证A B，B A即可。方法2 反证法.方法3 通过集合的基本算律以及已证明的集合等式，通过相等变换将待证明的等式左（右）边的集合化到右（左）边的集合，或者两边同时相等变换到同一集合。,证明集合相等的常用方法,例 设A，B，C是三个集合，已知AB=AC，AB=AC，求证B=C。用方法2：使用反证法。假设BC，则必存在x，满足x B，且x C，或者x B，且x C。不妨设x B，且x C，若x A，则x AB，但x AC，与AB=AC矛盾。若x A，则x AB，但x AC，与AB=AC矛盾。所以原假设不对，B=C。用方法3：利用已知以及集合运算的交换律、分配律与吸收律，有 B=B(AB)=B(AC)=(BA)(BC)=(CA)(BC)=C(AB)=C(AC)=C,作业,p6:2,3,5,