集合代数

1主要内容集合的基本概念属于、包含幂集、空集文氏图等集合的基本运算并、交、补、差等集合恒等式集合运算的算律、恒等式的证明方法第二部分集合论第六章集合代数26.1集合的基本概念1.集合定义集合没有精确的数学定义理解：由离散个体构成的整体称为集合，称这些个体为集合的元素约定：大写字母表示集合，小写字母表示元素，|A|表示集合A中元素的数量(集合A的基数)常见的数集：N,Z,Q,R,C等分别表示自然数、整数、有理数、实数、复数集合2.集合表示法枚举法----通过列出全体元素来表示集合谓词表示法----通过谓词概括集合元素的性质实例：枚举法自然数集合N={0,1,2,3,…}谓词法S={x|x是实数，x21=0}3元素与集合1.集合的元素具有的性质无序性：元素列出的顺序无关{a,b,c}={b,c,a}相异性：集合的每个元素只计数一次{a,b,a,c,a}＝{a,b,c}确定性：对任何元素和集合都能确定这个元素是否为该集合的元素任意性：集合的元素也可以是集合a{1,2}p{q}{1,2}S{q}S1S2SqSS={a,{1,2},p,{q}}S中共4个元素，分别为：4集合与集合集合与集合之间的关系：,=,⊈,,,定义6.1ABx(xAxB)定义6.2A=BABBA定义6.3ABABABA⊈Bx(xAxB)思考：和的定义注意和是不同层次的问题5空集、全集和幂集1．定义6.4空集：不含有任何元素的集合实例：{x|xRx2+1=0}定理6.1空集是任何集合的子集。证对于任意集合A，Ax(xxA)T(恒真命题)推论是惟一的3.定义6.6全集E：包含了所有集合的集合全集具有相对性：与问题有关，不存在绝对的全集2.定义6.5幂集：P(A)={x|xA}实例：P()={},P({})={,{}}计数：如果|A|=n，则|P(A)|=2n.6索引集合4.索引集合为了在计算机上表示集合，必须给每一个集合的元素加上标记，以用来表示元素在集合中的位置。例：S1={a，b}假设集合S1中，a,b的位置已经固定。则用二进制下标法来表示S的所有子集：={}=B00，{a}=B10，{b}=B01，{a，b}=B11这样P(S1)={B00，B01，B10，B11}={Bi|iJ}而其中J={00，01，10，11}（索引集合或指标集合）例：已知集合S={a1，a2，a3，a4，a5，a6}，S的子集有26个,可以分别表示成B0，B1……B(26-1)则B7=B000111={a4，a5，a6}B15=B001111={a3，a4，a5，a6}B22=B010110={a2，a4，a5}等等76.2集合的运算初级运算集合的基本运算有定义6.7并AB={x|xAxB}交AB={x|xAxB}相对补AB={x|xAxB}定义6.8对称差AB=(AB)(BA)定义6.9绝对补A=EA8文氏图(VennDiagram)集合运算的表示ABABABABABABABA–BAB~A9几点说明并和交运算可以推广到有穷个集合上，即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=A10广义运算1.集合的广义并与广义交定义6.10广义并A={x|z(zAxz)}广义交A={x|z(zAxz)}实例{{1},{1,2},{1,2,3}}={1,2,3}{{1},{1,2},{1,2,3}}={1}{{a}}={a}，{{a}}={a}{a}=a，{a}=a11关于广义运算的说明2.广义运算的性质(1)=，无意义(2)单元集{x}的广义并和广义交都等于x(3)广义运算减少集合的层次（括弧减少一层）(4)广义运算的计算：一般情况下可以转变成初级运算{A1,A2,…,An}=A1A2…An{A1,A2,…,An}=A1A2…An3.引入广义运算的意义可以表示无数个集合的并、交运算，例如{{x}|xR}=R这里的R代表实数集合.12运算的优先权规定1类运算：初级运算,,,，优先顺序由括号确定2类运算：广义运算和运算，运算由右向左进行混合运算：2类运算优先于1类运算例1A={{a},{a,b}}，计算A(AA).解：A(AA)={a,b}({a,b}{a})=(ab)((ab)a)=b=b13有穷集合元素的计数例2求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)=600容斥原理(包含排斥原理)：对任意两个有限集A和B，有|A∪B|=|A|+|B||A∩B||•|：集合的基数(元素个数)EAB|A∪B∪C||A||B||C||A∩B||A∩C||B∩C||A∩B∩C|推广kjiininkjinijijiiini|A||AAA|A|A||AA1111)1(|∩∩∪∩∩SABC容斥原理例3一个班里有50个学生，在第一次考试中有26人得100分，在第二次考试中有21人得100分。如果两次考试中都没得100分的有17人，那么在两次考试都得100分的有多少人？容斥原理解：设A、B分别表示第一和第二次考试中得100分学生的集合，那么有||50,E又因为|A∪B|=|A|+|B||A∩B|所以|A∩B|=|A|+|B||A∪B|=26+2133=14BABA首先由知∩∪∩17||BA||21,B||26,A=33||||BAUBA∪∪E∩|U|BAE17容斥原理考虑例2的方法二|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186.3集合恒等式集合算律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=A19集合算律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)=A20集合算律3．涉及补运算的算律：DM律，双重否定律D.M律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否定A=A21集合算律4．涉及全集和空集的算律：补元律、零律、同一律、否定律E补元律AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=22集合证明题证明方法：命题演算法、等式置换法命题演算证明法的书写规范(以下的X和Y代表集合公式)(1)证XY任取x，xX…xY(2)证X=Y方法一分别证明XY和YX方法二任取x，xX…xY注意：在使用方法二的格式时，必须保证每步推理都是充分必要的23集合等式的证明方法一：命题演算法例3证明A(AB)=A（吸收律）证任取x,xA(AB)xAxABxA(xAxB)xA因此得A(AB)=A.例4证明AB=AB证任取x,xABxAxBxAxBxAB因此得AB=AB24等式代入法方法二：等式置换法例5假设交换律、分配律、同一律、零律已经成立，证明吸收律.证A(AB)=(AE)(AB)（同一律）=A(EB)（分配律）=A(BE)（交换律）=AE（零律）=A（同一律）25包含等价条件的证明例6证明ABAB=BAB=AAB=①②③④证明思路：确定问题中含有的命题：本题含有命题①,②,③,④确定命题间的关系（哪些命题是已知条件、哪些命题是要证明的结论）：本题中每个命题都可以作为已知条件，每个命题都是要证明的结论确定证明顺序：①②，②③，③④，④①按照顺序依次完成每个证明（证明集合相等或者包含）26证明证明ABAB=BAB=AAB=①②③④证①②显然BAB，下面证明ABB.任取x，xABxAxBxBxBxB因此有ABB.综合上述②得证.②③A=A(AB)A=AB(由②知AB=B，将AB用B代入)27证明ABAB=BAB=AAB=①②③④③④假设AB,即xAB，那么知道xA且xB.而xBxAB从而与AB=A矛盾.④①假设AB不成立，那么x(xAxB)xABAB与条件④矛盾.证明28本章小结熟练掌握集合的两种表示法能够判别元素是否属于给定的集合能够判别两个集合之间是否存在包含、相等、真包含等关系熟练掌握集合的基本运算（普通运算和广义运算）掌握证明集合等式或者包含关系的基本方法29习题课主要内容集合的两种表示法集合与元素之间的隶属关系、集合之间的包含关系的区别与联系特殊集合：空集、全集、幂集文氏图及有穷集合的计数集合的,,,,等运算以及广义,运算集合运算的算律及其应用30练习11．判断下列命题是否为真(1)(2)(3){}(4){}(5){a,b}{a,b,c,{a,b,c}}(6){a,b}{a,b,c,{a,b}}(7){a,b}{a,b,{{a,b}}}(8){a,b}{a,b,{{a,b}}}解(1)、(3)、(4)、(5)、(6)、(7)为真，其余为假.31方法分析(1)判断元素a与集合A的隶属关系是否成立基本方法：把a作为整体检查它在A中是否出现，注意这里的a可能是集合表达式.(2)判断AB的四种方法若A,B是用枚举方式定义的，依次检查A的每个元素是否在B中出现.若A,B是谓词法定义的，且A,B中元素性质分别为P和Q,那么“若P则Q”意味AB，“P当且仅当Q”意味Ａ=Ｂ．通过集合运算判断AB，即AB=B,AB=A,AB=三个等式中有一个为真.通过文氏图判断集合的包含（注意这里是判断，而不是证明32练习22．设S1={1,2,…,8,9}，S2={2,4,6,8}S3={1,3,5,7,9}S4={3,4,5}S5={3,5}确定在以下条件下X是否与S1,…,S5中某个集合相等？如果是，又与哪个集合相等？（1）若XS5=（2）若XS4但XS2=（3）若XS1且X⊈S3（4）若XS3=（5）若XS3且X⊈S133解答解(1)和S5不交的子集不含有3和5，因此X=S2.(2)S4的子集只能是S4和S5.由于与S2不交，不能含有偶数，因此X=S5.(3)S1,S2,S3,S4和S5都是S1的子集，不包含在S3的子集含有偶数，因此X=S1,S2