离散数学-集合及其运算

离散数学（一）上海大学谢江离散数学（第3版）屈婉玲耿素云张立昂编著清华大学出版社出版第1章数学语言与证明方法3第1章数学语言与证明方法•1.1常用的数学符号•1.2集合及其运算•1.3证明方法概述41.2集合及其运算•集合及其表示法•包含(子集)与相等•空集与全集•集合运算(,,-,~,)•基本集合恒等式•包含与相等的证明方法5集合的概念朴素集合论(康托,G.Cantor),集合是数学中最基本的概念,没有严格的定义满足某条性质的个体放在一起组成集合元素:集合中的个体隐含的矛盾：罗素(Russell)悖论•1901年提出；•第三次数学危机公理集合论体系：属于数理逻辑范畴.透过建立一阶逻辑的严谨重整，使用明确的公理列表，以解决朴素集合论中的悖论1.2.1集合及其表示法6集合的记法集合：常用大写英文字母A,B,C等表示元素：小写英文字母x,y,z,…元素与集合的关系：xA(x属于A):x是A的元素xA(x不属于A):x不是A的元素无穷集:元素个数无限的集合有穷集(有限集):元素个数有限的集合.|A|:A中元素个数k元集:k个元素的集合,k01.2.1集合及其表示法7集合的表示法列举法：列出集合中的全体元素－－｛，，，｝如A={a,b,c,d},N={0,1,2,…}描述法（元素性质法）{x|P(x)}－－具有性质P的x的全体如N={x|x是自然数}说明:(1)集合中的元素各不相同.如,{1,2,3}={1,1,2,3}(2)集合中的元素没有次序.如,{1,2,3}={3,1,2}={1,3,1,2,2}(3)有时两种方法都适用,可根据需要选用.1.2.1集合及其表示法8常用集合的表示法自然数集N,N={x|x是自然数}={0，1，2，……}整数集Z,Z={x|x是整数}={……,2,1,0,1,2,……}正整数集Z+,Z+={x|xZx0}={1,2,3,……}有理数集Q,Q={x|x是有理数}非零有理数集Q*,Q*={x|xQx0}实数集R,R={x|x是实数}非零实数集R*,R*={x|xRx0}复数集C,C={x|x是复数}区间[a,b],[a,b]={x|xRaxb}区间(a,b),(a,b)={x|xRaxb}……1.2.1集合及其表示法9隶属关系的层次结构例A={a,{b,c},d,{{d}}}{b,c}A？bA？bA？{{d}}A？{d}A？{d}A？dA？1.2.1集合及其表示法10包含(子集)ABx(xAxB)不包含A⊈Bx(xAxB)性质(1)对于任意集合A，均有AA(2)对于任意三个集合，ABBCAC(3)如果AB且B⊈A，称A真包含于B，记AB：真包含(真子集)ABABAB1.2.2集合之间的包含与相等定义1.1设A，B为两个集合，若B中的元素都是A中的元素，则称B是A的子集，也称A包含B，或B包含于A，记作BA，若B中至少有一个元素不是A的元素，称A不包含B，B不包含于A，并用B⊈A表示，表示B不是A的子集BA11定义1.2设A，B为两个集合，若AB且BA，则称A与B相等，记作A=B.即相等A=BABBA不相等ABA⊈BB⊈A1.2.2集合之间的包含与相等12例如,A={1,2,3},B={x|xR|x|1},C={x|xRx2=1},D={-1,1},则：CB？CB？C⊈A？A⊈B？B⊈A？C=D？1.2.2集合之间的包含与相等BA13定义1.3设A，B为两个集合，若AB且AB，则称A为B的真子集，记作AB.即ABx(xAxB)x(xBxA)例NZQR.1.2.2集合之间的包含与相等14空集与全集空集:不含任何元素的集合例如,{x|x20xR}=定理1.1空集是任何集合的子集证要证对于任意的集合A，均有A.采用归谬法.假设存在集合A,使得⊈A,即存在x,x且xA,但x与空集的定义相矛盾.得证。1.2.2集合之间的包含与相等15空集与全集推论空集是唯一的.证采用归谬法证明。假设空集不是唯一的，则存在两个空集1和2，且12.由定理1.1可知，12且21，再由定义1.2可知，1=2，这与12相矛盾.得证。空集为一切集合的子集：是“最小”的集合.有没有最大的集合？1.2.2集合之间的包含与相等16空集与全集全集E:限定所讨论的集合都是E的子集.相对性例讨论我们全校的问题时，全校师生就是一个全集.注意：不同的实际问题可以定义不同的全集，因而无统一的全集，这与空集的唯一性是完全不同的.例讨论我们计算机学院的问题时，全体计算机学院的师生就是一个全集.此时，全校师生也可作为一个全集.1.2.2集合之间的包含与相等17幂集定义1.6设A为一个集合，称由A的所有子集组成的集合为A的幂集，记作P(A)，即P(A)={x|xA}例如,设A={a,b,c}A的0元子集:A的1元子集:。A的2元子集：A的3元子集:。P(A)=。设|A|=n，求A的幂集：求0元子集：个，即；求1元子集：个；求2元子集：个，……，求n元子集：个将上述子集集合在一起，即得A的幂集.1.2.3集合的运算{a},{b},{c}{a,b},{a,c},{b,c}{a,b,c}{,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}0nC0nC0nC𝑪𝒏𝟎=1𝑪𝒏𝟏𝑪𝒏𝟐𝑪𝒏𝒏18幂集定理1.2如果|A|=n，则|P(A)|=2n证：方法一：方法二：子集编码法A={a1,a2,a3,…,an}子集B={a3,a5,…,ak}子集B中，出现A中元素的位为1，否则为0全为1：A；全为0：所有可能性有2𝑛种。1.2.3集合的运算|𝑷(𝑨)|=𝑪𝒏𝟎+𝑪𝒏𝟏+⋯+𝑪𝒏𝒏=(𝟏+𝟏)𝒏=𝟐𝒏19并：称由A与B的全体元素组成的集合为A与B的并集，记作AB，即AB={x|xAxB}例如设A={0,1,2,3},B={1,3,5,7,9},则AB={0,1,2,3,5,7,9}集合之间的关系与运算可用文氏图表示：a.用矩形内部的点表示全集E；b.用矩形内部的圆或其他简单闭合曲线的内部的点表示E的子集；c.用阴影区域表示集合之间运算的结果.1.2.3集合的运算20交：称由A与B的公共元素组成的集合为A与B的交集，记作AB，即AB={x|xAxB}例如设A={0,1,2,3},B={1,3,5,7,9},则AB={1,3}文氏图：1.2.3集合的运算相对补：称属于A而不属于B的元素组成的集合为B对A的相对补集，记作AB，即AB={x|xAxB}绝对补：设E为全集，AE，称EA为A的绝对补集，记作A，即A=EA={x|xA}例如设E={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9},则A-B={0,2},B-A={5,7,9}A={4,5,6,7,8,9},B={0,2,4,6,8}文氏图：1.2.3集合的运算22对称差：称属于A而不属于B，或属于B而不属于A的元素组成的集合为A与B的对称差集，记作AB，即AB={x|(xAxB)(xBxA)}=(AB)(BA)=(AB)(AB)例如设E={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9},则AB={0,2,5,7,9}文氏图：说明（集合的运算）:1.只使用圆括号2.运算顺序:优先级别为(1)括号,(2)和幂集,(3)其他.同级别的按从左到右运算1.2.3集合的运算与交/并运算的关系？与补集的关系？23实例例1设E={x|x是北京某大学学生},A,B,C,D是E的子集,A={x|x是北京人},B={x|x是走读生},C={x|x是数学系学生},D={x|x是喜欢听音乐的学生}.试描述下列各集合中学生的特征:(AD)~C=~AB=(A-B)D=~D~B={x|x是北京人或喜欢听音乐,但不是数学系学生}{x|x是外地走读生}{x|x是北京住校生,并且喜欢听音乐}{x|x是不喜欢听音乐的住校生}1.2.3集合的运算24文氏图表示1.2.3集合的运算25定义1.8设A，B为两个集合，若A∩B=，则称A与B是不交的.例设A={x|x是男生}，B={x|x是女生}，则A与B是不交的.注意：空集与任何集合都是不交的.1.2.3集合的运算AB=26设A1，A2，…An为n个集合，并和交运算可以推广到有穷个集合上∪𝑖=1𝑛𝐴𝑖=A1A2…An={x|xA1xA2…xAn}∩𝑖=1𝑛𝐴𝑖=A1A2…An={x|xA1xA2…xAn}并和交运算还可以推广到无穷个集合上∪𝑖=1∞𝐴𝑖=A1A2…={x|i(i=1,2,…)xAi}∩𝑖=1∞𝐴𝑖=A1A2…={x|i(i=1,2,…)xAi}1.2.3集合的运算27实例例2设Ai=[0,1/i),Bi=(0,i),i=1,2,…,则[0,1)[0,1)[0,1/n){0}(0,n)(0,+∞)(0,1)(0,1)1.2.3集合的运算∪𝑖=1𝑛𝐴𝑖=∩𝑖=1𝑛𝐴𝑖=∪𝑖=1𝑛𝐵𝑖=∩𝑖=1𝑛𝐁𝑖=∪𝑖=1∞𝐴𝑖=∩𝑖=1∞𝐴𝑖=∪𝑖=1∞𝐵𝑖=∩𝑖=1∞𝐵𝑖=28基本集合恒等式1.幂等律AA=A,AA=A2.交换律AB=BA,AB=BA3.结合律(AB)C=A(BC)(AB)C=A(BC)4.分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)5.德摩根律绝对形式(BC)=BC,(BC)=BC相对形式A(BC)=(AB)(AC)A(BC)=(AB)(AC)1.2.4基本集合恒等式及其应用29基本集合恒等式(续)6.吸收律A(AB)=A,A(AB)=A7.零律AE=E,A=8.同一律A=A,AE=A9.排中律AA=E10.矛盾律AA=11.余补律=E,E=12.双重否定律A=A13.补交转换律A-B=AB1.2.4基本集合恒等式及其应用30基本集合恒等式(续)14.关于对称差的恒等式(1)交换律AB=BA(2)结合律(AB)C=A(BC)(3)对的分配律A(BC)=(AB)(AC)(4)A=A,AE=~A(5)AA=,A~A=E注意:对没有分配律,举反例A={a,b,c},B={b,c,d},C={c,d,e}A(BC)={a,b,c}{b,e}={a,b,c,e}(AB)(AC)={a,b,c,d}{a,b,c,d,e}={e},两者不等1.2.4基本集合恒等式及其应用31基本集合恒等式(续)15.AAB,BAB.16.ABA,ABB.17.A-BA.18.AB=BABABAA-B=.19.AB=ACA=B,即有消去律.1.2.4基本集合恒等式及其应用由已知的集合恒等式推演新的集合等式或包含式的过程称为集合演算.在集合演算中经常使用上述的各组集合恒等式。32证明集合包含或相等方法一.根据定义证明，例如证明集合A=B：如果∀𝒙∈𝑨⇒𝒙∈𝑩,则𝑨⊆𝑩如果∀𝒙∈𝑩⇒𝒙∈𝑨,则𝑩⊆𝑨方法二.利用已知集合等式或包含式,通过集合演算证明例3用定义证明:(1)AB=BA(交换律)证xxABxA或xB,自然有xB或xAxBA得证ABBA.同理可证BAAB.根据定义得证AB=BA1.2.4基本集合恒等式及其应用=A=B33例3(续)(2)A(BC)=(AB)(AC)(分配律)证xxA