离散集合的概念交并补差幂集演示文稿

离散集合的概念交并补差幂集演示文稿当前第1页\共有35页\编于星期一\8点（优选）离散集合的概念交并补差幂集当前第2页\共有35页\编于星期一\8点PowerPointTemplate_Sub1.1集合的概念与表示1.2集合运算1.3集合的归纳定义当前第3页\共有35页\编于星期一\8点PowerPointTemplate_Sub

集合论是一门研究数学基础的学科，产生于16世纪末德国数学家康托（GeorgCantor,1845~1918）通过集合的直观定义开创了朴素集合论，被公认为集合理论的创始人1902年英国数学家罗素（Russell,1872~1970）证明朴素集合论导致悖论，随后为弥补这一缺陷出现了各种公理化集合论体系集合不仅可以表示数及其运算，更可以用于非数值信息及离散结构的表示和处理。集合论的原理和方法作为数学基本技术广泛地应用于计算机科学的基础研究和实际应用中当前第4页\共有35页\编于星期一\8点集合的概念、表示与基本运算Page1to7《离散数学》第1讲当前第5页\共有35页\编于星期一\8点-6-ξ第一讲集合的概念、表示与基本运算内容提要基础知识集合、元素的概念怎样表示一个集合（列举、描述…）空集、全集、有限集、无限集外延性公理集合相等、子集、若干定理集合的基本运算并、交、差、补幂集运算当前第6页\共有35页\编于星期一\8点-7-ξ第一讲集合的概念、表示与基本运算何为集合？何为元素？集合(sets)：指确定的、互相区别的、作整体识别的一些事物（对象）的全体。简称集。集合中的对象称为集合的元素(members)，或称为元、成员。当某一个对象a是集合A的成员时，就说“a属于A”，记成aA，当a不是集合A的成员时，就说“a不属于A”，记成aA。对于任何对象a和任何集合A，a要么属于A，要么不属于A，二者必居其一。当前第7页\共有35页\编于星期一\8点-8-ξ第一讲集合的概念、表示与基本运算集合举例师范大学全体学生师范大学所有班级全体正整数1，2，3，4，…偶质数的全体09计算机1班和他们本学期选修的所有课程所有长得像张三的人中国所有著名导演方程x2-2x+1=0的根方程x2+x+1=0的根当前第8页\共有35页\编于星期一\8点-9-ξ第一讲集合的概念、表示与基本运算集合与元素集合中的元素可以是任何具体或抽象的个体，也可以是集合A={1，2，{1，2}}集合与其成员是两个截然不同的概念1≠{1}{{a}}≠{a}通常用大写字母A,B,C表示集合，用小写字母a,b,c表示集合的元素（并非绝对）当前第9页\共有35页\编于星期一\8点-10-ξ第一讲集合的概念、表示与基本运算集合的表示方法列举法（枚举法）{a,b,c},{秦始皇，汉武帝}{1,2,3,4,…},{2,4,6,8,…}{1,2,4,7,11,…}描述法A={x|P(x)}（A中的元素均满足性质P，而A以外的元素一个也不满足性质P）

xAP(x){x|x是整数且x>0}、{x|x2-2x+1=0}{x|x出生于大连}、{x|x是0到1区间的实数}当前第10页\共有35页\编于星期一\8点-11-ξ第一讲集合的概念、表示与基本运算集合的表示方法归纳法（以后介绍）文氏图（常用于表示集合之间的关系）ABU当前第11页\共有35页\编于星期一\8点-12-ξ第一讲集合的概念、表示与基本运算常用集合及其表示{0,1}={x|x=0或x=1}自然数集合（或非负整数的集合）N={0,1,2,3,…}整数集合I={…,-2,-1,0,1,2,…}正整数集合I+

={1,2,3,…}={x|xI且x>0}当前第12页\共有35页\编于星期一\8点-13-ξ第一讲集合的概念、表示与基本运算常用集合及其表示偶数集合E={…,-4,-2,0,2,4,…}={x|x是偶数}={x|xI且2|x}前n个自然数的集合Nn={0，1，2，…,n-1}={x|xN且x<n}当前第13页\共有35页\编于星期一\8点-14-ξ第一讲集合的概念、表示与基本运算常用集合及其表示P：全体素数的集合Q：全体有理数的集合Q＋：全体正有理数的集合R：全体实数的集合R＋：全体正实数的集合C：全体复数的集合当前第14页\共有35页\编于星期一\8点-15-ξ第一讲集合的概念、表示与基本运算空集、有限集和无限集定义1.1：没有任何元素的集合称为空集，记为，={}。由全体对象组成的集合称为全集，记为U。定义1.2：只含有限多个元素的集合称为有限集；不是有限集的集合称为无限集。空集是有限集有限集合A中元素的个数称为A的基数(cardinality)，记为|A|空集的基数是0，即||=0当前第15页\共有35页\编于星期一\8点-16-ξ第一讲集合的概念、表示与基本运算空集、有限集和无限集举例{x|x=0或x=1}自然数集合N正整数集合A={1，2，{1，2}}{}师范大学全体学生方程x2+x+1=0的根当前第16页\共有35页\编于星期一\8点-17-ξ第一讲集合的概念、表示与基本运算外延性公理（extensionalityaxiom）

外延性公理：两个集合相等当且仅当这两个集合具有完全相同的成员。即对任意的集合A和B：A=B当且仅当对任意元素x，x属于A则一定有x属于B；反之，x属于B也一定有x属于A。也就是说，集合A中的所有元素均是集合B中的元素，反之，B中的所有元素均是A中的元素例1.4{0,1}={1,0}={0,1,0}={x|x(x2-2x+1)=0}外延性公理事实上刻画了集合元素的无序性、相异性及集合表示形式的不唯一性当前第17页\共有35页\编于星期一\8点-18-ξ第一讲集合的概念、表示与基本运算子集合(subsets)定义1.3：设A，B为集合，若A中每一个元素都同时是B的元素，则称A是B的子集。即对于任意元素x，当x属于A时一定有x属于B。表示为AB，读成A包含于B，或B包含A。任意集合A均是自己的子集，即：AA若要说明A不是B的子集，只须在A中找到某一个元素x，使得xB即可定义1.4：设A、B为集合，当AB且AB时，称A为B的真子集，记成AB。读做A真包含于B，或B真包含A当前第18页\共有35页\编于星期一\8点-19-ξ第一讲集合的概念、表示与基本运算包含关系vs.隶属关系包含——集合与集合之间的关系{1,2}{1,2,3,4}{1,2}{1,2,3,4}{a}{a}隶属——元素与集合之间的关系1{1,2,3,4}5{1,2,3,4}{a}{{a}}当前第19页\共有35页\编于星期一\8点-20-ξ第一讲集合的概念、表示与基本运算关于子集的若干定理定理1.1：对任何集合A，B，A=B当且仅当AB且BA。对任何集合A，AA定理1.3：对于任何集合A，B，C，若AB，BC，则AC。证明：设x为A中任一元素，

因为AB，所以xB；又因为BC，所以xC

这就是说，A中所有元素均属于C，所以有AC。当前第20页\共有35页\编于星期一\8点-21-ξ第一讲集合的概念、表示与基本运算关于子集的若干定理定理1.2，1.4：对任意集合A，AU，A定理1.5：空集是唯一的证明：假设1,2都是空集，根据定理3，应该有1

2

且2

1

，从而由定理1知1=2。当前第21页\共有35页\编于星期一\8点-22-ξ第一讲集合的概念、表示与基本运算关于子集的若干定理定理1.6：设A为一个有限集，且|A|=n，则A的子集个数为2n证明：集合A的子集最多有n个元素，最少有0个元素。

0个元素的子集共有C(n,0)个；

1个元素的子集共有C(n,1)个；

……n个元素的子集共有C(n,n)个.

因此，集合A共有子集C(n,0)+C(n,1)+…C(n,n)=2n个。当前第22页\共有35页\编于星期一\8点-23-ξ第一讲集合的概念、表示与基本运算集合的运算集合运算——以集合作为运算对象，运算结果仍为集合的运算算术运算：3+5=84×6=24集合运算：{1,2}{2,3}={2}{1,2}{2,3}={1,2,3}有哪些集合运算交、并、差、补求幂运算广义并、交求笛卡尔积运算当前第23页\共有35页\编于星期一\8点-24-ξ第一讲集合的概念、表示与基本运算集合的并运算union

（∪）定义1.5：(1)设A、B为任意集合，则由A、B的所有元素合在一起所组成的集合称为A与B的并集，记成A∪B。即：A∪B={x|xA或xB}

xA∪BxA或xB例1.6U={0,1,2,…,9}A={2,4},B={4,5,6,7},C={0,8,9},D={1,2,3}A∪B，A∪C，C∪D，B∪D当前第24页\共有35页\编于星期一\8点-25-ξ第一讲集合的概念、表示与基本运算集合的交运算intersection（∩）定义1.5：(2)设A、B为任意集合，则由A、B的公共元素所组成的集合称为A与B的交集，记成A∩B。即：A∩B={x|xA并且xB}xA∩BxA并且xB例1.6U={0,1,2,…,9}A={2,4},B={4,5,6,7},C={0,8,9},D={1,2,3}A∩B，A∩C，C∩D，B∩D当前第25页\共有35页\编于星期一\8点-26-ξ第一讲集合的概念、表示与基本运算集合的差运算difference（–）定义1.5：(3)设A、B为任意集合，则由在A中而不在B中的元素所组成的集合称为A对B的差，记成A–B。即：A–B={x|xA且xB}xA–BxA并且x

B

例1.6U={0,1,2,…,9}A={2,4},B={4,5,6,7},C={0,8,9},D={1,2,3}A－B，A－C，C－D，B－D当前第26页\共有35页\编于星期一\8点-27-ξ第一讲集合的概念、表示与基本运算集合的补运算complement（–）定义1.5：(4)设U为全集，A为任意集合，则所有在全集U中但不属于A的元素所组成的集合称为A的补集，记成A¯。即：A¯={x|xU且xA}xA¯x

A例1.6U={0,1,2,…,9}A={2,4},B={4,5,6,7},C={0,8,9},D={1,2,3}A¯

，B¯，C¯，D¯当前第27页\共有35页\编于星期一\8点-28-ξ第一讲集合的概念、表示与基本运算文氏图表示的集合并、交、差、补运算UAAUAA¯A∩BUABA∪BUABA－BUAB(A∪B)¯∩CUABC当前第28页\共有35页\编于星期一\8点-29-ξ第一讲集合的概念、表示与基本运算关于并、交、差、补运算的一些直观结论A∪A=A，A∪=A，A∪U=UA∩A=A，A∩=，A∩U=AA–A=，A–=A，A–U=，

–A=

A¯=U–A，¯=U，U¯=，A¯¯=AA∩A¯=，A∪A¯=UAA∪B，BA∪B，A∩BA，A∩BBA–BA若AB，则A∪B=B，A∩B=A，A–B=若A∩B=，则A–B=A当前第29页\共有35页\编于星期一\8点-30-ξ第一讲集合的概念、表示与基本运算关于交换律和结合律交换律2+3=3+2，a×b=b×aA∪B=B∪A，A∩B=B∩A一般而言，A–B≠B–A结合律2+(3+5)=(2+3)+5，a×(b×c)=(a×b)×cA∪(B∪C)=(A∪B)∪CA∩(B∩C)=(A∩B)∩C一般而言，

A–(B–C)≠(A–B)–C当前第30页\共有35页\编于星期一\8点-31-ξ第一讲集合的概念、表示与基本运算关于分配律和吸收率分配律a×(b+c)=a×b+a×cA∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)A∩(B－C)=

(A∩B)－(A∩C)一般而言，A∪(B－C)≠(A∪B)－(A∪C)

吸收律A∩(A∪B)=AA∪(A∩B)=A当前第31页\共有35页\编于星期一\8点-32-ξ第一讲集合的概念、表示与基本运算关于并、交、差、补运算的几个定理

定理1.6：A–(B∪C)=(A–B)∩(A–C)A–(B∩C)=(A–B)∪(A–C)定理1.8：(A∪B)¯=A¯∩B¯(A∩B)¯=A¯∪B¯A–B=A∩B¯证明A–(B∩C)=(A–B)∪(A–C)对任意x，xA–(B∩C)xA且xB∩C

xA且(xB或者xC)

(xA且xB)或者(xA且xC)xA–B或者xA–C

x(A–B)∪(A–C)当前第32页\共有35页\编于星期一\8点-33-ξ第一讲集合的概念、表示与基本运算关于并、交、差、补运算的几个定理

定理1.10：AB，A–B=，A∪B=B，A∩B=A四命题等价定理1.11：对任意集合A、B，若它们满足1)

A∪B=U