离散数学-第六章的课件

1主要内容集合的基本概念属于、包含幂集、空集文氏图等集合的运算有穷集的计数集合恒等式集合运算的算律、恒等式的证明方法第二部分集合论第六章集合代数26.1集合的基本概念1.集合定义集合没有精确的数学定义理解：由离散个体构成的整体称为集合，称这些个体为集合的元素常见的数集：N,Z,Q,R,C等分别表示自然数、整数、有理数、实数、复数集合2.集合表示法列元素法----列出集合的所有元素，所有元素之间用逗号隔开，并把它们用花括号括起来谓词表示法----用谓词来概括集合中元素的性质实例：列元素法自然数集合N={0,1,2,3,…}谓词表示法S={x|xRx21=0}3元素与集合1.集合的元素具有的性质无序性：元素列出的顺序无关相异性：集合的每个元素只计数一次确定性：对任何元素和集合都能确定这个元素是否为该集合的元素任意性：集合的元素也可以是集合2．元素与集合的关系隶属关系：或者3．集合的树型层次结构例如：集合A={a,{b,c},d,{{d}}}规定：AA4集合与集合集合与集合之间的关系：,⊈,=,,,,定义6.1设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作BA。如果B不被A包含，则记作B⊈A。符号化表示为：BAx(xBxA)B⊈Ax(xBxA)例如NZQRC，但Z⊈N。显然对任何集合A都有AA。定义6.2设A，B为集合，如果AB且BA，则称A与B相等，记作A＝B。如果A与B不相等，则记作A≠B。符号化表示为：A=BABBA定义6.3设A，B为集合，如果BA且B≠A，则称B是A的真子集，记作BA。如果B不是A的真子集，则记作BA。符号化表示为：BABABA例如NZQRC，但NN。注意：和是不同层次的问题，如A={a,{a}}和{a}5空集、全集和幂集定义6.4空集：不含有任何元素的集合符号化表示为：={x|x≠x}实例：{x|xRx2+1=0}定理6.1空集是任何集合的子集。证对于任意集合A，Ax(xxA)1(恒真命题)推论是惟一的证明：假设存在空集1和2，由定理6.1有：12和21根据集合相等的定义，有1=2所以得出结论：是惟一的。6空集、全集和幂集含有n个元素的集合简称n元集，它的含有m（m≤n）个元素的子集叫做它的m元子集。任给一个n元集，怎样求出它的全部子集呢？例6.1A＝{1,2,3}，将A的子集分类：解：0元子集，也就是空集，只有一个：；1元子集，即单元集：{1}，{2}，{3}；2元子集：{1,2}，{1,3}，{2,3}；3元子集：{1,2,3}。7空集、全集和幂集定义6.5幂集：设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或PA，2A)。符号化表示为：P(A)={x|xA}实例：P()={},P({})={,{}}计数：如果|A|=n，则|P(A)|=2n.定义6.6全集E：包含了所有集合的集合全集具有相对性：与问题有关，不存在绝对的全集86.2集合的运算初级运算集合的基本运算有并，交，相对补和对称差定义6.7设A，B为集合，A与B的并集A∪B，交集A∩B，B对A的相对补集A－B分别定义如下：并AB={x|xAxB}交AB={x|xAxB}相对补AB={x|xAxB}例如：A={a,b,c}，B={a}，C={b,d}AB={a,b,c},AB={a},AB={b,c},B-A=,BC=若两个集合的交集为，则称这两个集合是不交的96.2集合的运算定义6.8设A，B为集合，A与B的对称差集AB定义为：对称差AB=(AB)(BA)另一种定义是：AB=(AB)(AB)例如：A={a,b,c}，B={b,d},AB={a,c,d}定义6.9在给定全集E以后，AE，A的绝对补集～A定义如下：绝对补A=EA={x|x∈E∧xA}={x|xA}例如：E＝{a，b，c，d}，A＝{a，b，c}，则～A＝{d}。10文氏图集合运算的表示ABABABABAEABABA–BAB~A11几点说明并和交运算可以推广到有穷个集合上，即A1A2…An={x|xA1xA2…xAn}A1A2…An={x|xA1xA2…xAn}ABAB=AB=AB=A12广义运算1.集合的广义并与广义交定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。符号化表示为广义并A={x|z(zAxz)}定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为∩A。符号化表示为广义交A={x|z(zAxz)}例6.2设A＝{{a,b,c},{a,c,d},{a,e,f}}B＝{{a}}C＝{a,{c,d}}则∪A＝{a,b,c,d,e,f},∪B＝{a}，C＝a∪{c,d}∩A＝{a}，∩B＝{a}，∩C＝a∩{c,d}13广义运算1.集合的广义并与广义交定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。符号化表示为广义并A={x|z(zAxz)}定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为∩A。符号化表示为广义交A={x|z(zAxz)}练习:A={{1},{1,2},{1,2,3}},B={{a}},C={a}解:A={1,2,3},A={1}B={a}，B={a}C=a，C=a14关于广义运算的说明2.广义运算的性质(1)=，无意义(2)单元集{x}的广义并和广义交都等于x(3)广义运算减少集合的层次（括弧减少一层）(4)广义运算的计算：一般情况下可以转变成初级运算A={A1,A2,…,An}=A1A2…AnA={A1,A2,…,An}=A1A2…An3.引入广义运算的意义可以表示无数个集合的并、交运算，例如{{x}|xR}=R这里的R代表实数集合.15运算的优先权规定一类运算：广义并，广义交，幂集，绝对补运算运算由右向左顺序进行(右结合)二类运算：并，交，相对补，对称差优先顺序由括号确定混合运算：一类运算优先于二类运算。例A={{a},{a,b}}，计算A(AA).解：A(AA)={a,b}({a,b}{a})=(ab)((ab)a)=(ab)(ba)=b16例6.5设A＝{{a},{a,b}}计算∪∪A，∩∩A和∩∪A∪(∪∪A－∪∩A)。解:∪A＝{a,b}∩A＝{a}∪∪A＝a∪b∩∩A＝a∩∪A＝a∩b∪∩A＝a∩∪A∪(∪∪A－∪∩A)＝(a∩b)∪((a∪b)－a)＝(a∩b)∪(b－a)＝b所以∪∪A＝a∪b，∩∩A＝a，∩∪A∪(∪∪A－∪∩A)＝b。17作业书本97页第8题的第（4）小题第9题的第（1）、（3）、（5）三个小题书本98页第18题的第（1）、（3）两个小题18有穷集合元素的计数1.文氏图法2.包含排斥原理定理6.2设集合S上定义了n条性质，其中具有第i条性质的元素构成子集Ai,那么集合中不具有任何性质的元素数为|...|)1(...|||||||||...|2111121nnnkjikjnjijiniinAAAAAAAAASAAAi推论S中至少具有一条性质的元素数为||)1(||||||||21111121nmnkjikjinjijiniinAAAAAAAAAAAA19实例例6.5求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？解方法一：文氏图定义以下集合：S={x|xZ1x1000}A={x|xSx可被5整除}B={x|xSx可被6整除}C={x|xSx可被8整除}画出文氏图，然后填入相应的数字，解得N=1000－(200+100+33+67)=60020实例方法二|S|=1000|A|=1000/5=200,|B|=1000/6=166,|C|=1000/8=125|AB|=1000/lcm(5,6)=1000/33=33|AC|=1000/lcm(5,8)=1000/40=25|BC|=1000/lcm(6,8)=1000/24=41|ABC|=1000/lcm(5,6,8)=1000/120=8=1000(200+166+125)+(33+25+41)8=600||CBA216.3集合恒等式下面的恒等式给出了集合运算的主要算律，其中A，B，C代表任意集合。幂等律A∪A＝AA∩A＝A结合律(A∪B)∪C＝A∪(B∪C)(A∩B)∩C＝A∩(B∩C)交换律A∪B＝B∪AA∩B＝B∩A分配律A∪(B∩C)＝(A∪B)∩(A∪C)A∩(B∪C)＝(A∩B)∪(A∩C)同一律A∪＝AA∩E＝A零律A∪E＝EA∩＝排中律A∪～A＝E矛盾律A∩～A＝吸收律A∪(A∩B)＝AA∩(A∪B)＝A德摩根律A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)～(B∪C)=～B∩～C～(B∩C)=～B∪～C～＝E～E＝双重否定律～(～A)＝A22除了以上算律以外，还有一些关于集合运算性质的重要结果。例如：A∩BA，A∩BB(6.24)AA∪B，BA∪B(6.25)A－BA(6.26)A－B＝A∩～B(6.27)A∪B＝BABA∩B＝AA－B＝(6.28)AB＝BA(6.29)(AB)C＝A(BC)(6.30)A＝A(6.31)AA＝(6.32)AB＝ACB＝C(6.33)23书本88页例6.5设A＝{{a},{a,b}}计算∪∪A，∩∩A和∩∪A∪(∪∪A－∪∩A)。解:∪A＝{a,b}∩A＝{a}∪∪A＝a∪b∩∩A＝a∩∪A＝a∩b∪∩A＝a∩∪A∪(∪∪A－∪∩A)＝(a∩b)∪((a∪b)－a)＝(a∩b)∪(b－a)＝b所以∪∪A＝a∪b，∩∩A＝a，∩∪A∪(∪∪A－∪∩A)＝b。246.4集合恒等式（P92）集合算律1．只涉及一个运算的算律：交换律、结合律、幂等律交换AB=BAAB=BAAB=BA结合(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)幂等AA=AAA=A25集合算律2．涉及两个不同运算的算律：分配律、吸收律与与分配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)=A26集合算律3．涉及补运算的算律：德摩根律，双重否定律德摩根律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否定律A=A27集合算律4．涉及全集和空集的算律：补元律、零律、同一律、否定律E补元律AA=AA=E零律A=AE=E同一律A=AAE=A否定律=EE=28集合证明题证明方法：命题演算法、等式置换法命题演算证明法的书写规范(以下的X和Y代表集合公式)(1)证XY任取x，xX…xY(2)证X=Y方法一分别证明XY和YX都为真。方法二任取x，xX…xY注意：在使用方法二的格式时，必须保证每步推理都是充分必要的（等值）29集合等式的证明方法一：命题演算法例1证明A(AB)=A（吸收律）证任取x,xA(AB)xAxABxA(xAxB)xA因此得A