集合论完整

一、本部分的主要内容集合代数----集合的概念和基本运算关系----二元关系的表示、运算、性质、特殊的关系函数----函数定义、性质、运算二、本部分的基本要求掌握集合及其相关的基本概念熟练掌握集合以及关系、函数的基本运算了解和使用基本的证明方法第二部分集合论主要内容集合的基本概念----属于、包含、幂集、空集、文氏图等集合的基本运算----并、交、补、差等集合恒等式----集合运算的算律、恒等式的证明方法与后面各章的关系是集合论后面各章的基础是典型的布尔代数系统第六章集合代数一、集合的定义集合没有精确的数学定义直观理解：由离散个体构成的整体称为集合，称这些个体为集合的元素常见的数集：N,Z,Q,R,C等分别表示自然数、整数、有理数、实数、复数集合二、集合的表示法1．枚举法----通过列出全体元素来表示集合2．谓词法----通过谓词概括集合元素的性质实例：枚举法自然数集合N={0,1,2,3,…}谓词法S={x|x是实数，x21=0}第一节集合的基本概念三、元素与集合1．集合的元素具有的性质无序性——元素列出的顺序无关相异性——集合的每个元素只计数一次确定性——对于任何元素和集合，都能确定这个元素是否为该集合的元素任意性——集合的元素也可以是集合2．元素与集合的关系——隶属关系：或者3．集合的树型层次结构dA,aA图1四、集合与集合1．集合与集合之间的关系：,=,⊈,,,ABx(xAxB)A=BABBAABABABA⊈Bx(xAxB)思考：和的定义2．注意和是不同层次的问题五、空集和全集1．空集：不含有任何元素的集合实例：{x|xRx2+1=0}定理6.1空集是任何集合的子集。证对于任意集合A，Ax(xxA)T(恒真命题)推论是惟一的2．全集E：包含了所有集合的集合全集具有相对性：与问题有关，不存在绝对的全集六、幂集1．定义：P(A)={x|xA}2．实例：P()={},P({})={,{}}3．计数：如果|A|=n，则|P(A)|=2n.一、初级运算1．定义6.1并AB={x|xAxB}交AB={x|xAxB}相对补AB={x|xAxB}对称差AB=(AB)(BA)绝对补A=EA第二节集合的运算2．文氏图表示图2ABABABABABABABA–BAB~A3．几点说明：并和交运算可以推广到有穷个集合上，即A1A2…An={x|xA1xA2…xAn}A1A2…An={x|xA1xA2…xAn}ABAABAB=（后面证明）AB=AB=A二、有穷集合元素的计数1．计数方法（1）文氏图法（2）公式法——包含排斥原理设集合S上定义了n条性质，其中具有第i条性质的元素构成子集Ai,那么集合中不具有任何性质的元素数为|...|)1(...|||||||||...|2111121nnnkjikjnjijiniinAAAAAAAAASAAAi2．计数实例例求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？解方法一图333方法二令S={x|xZ1x1000},A={x|xSx0(mod5)}B={x|xSx0(mod6)},C={x|xSx0(mod8)}则|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一、集合算律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=A2．涉及两个运算的算律与与分配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第三节集合恒等式3．涉及补运算的算律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=A4．涉及全集和空集的算律E补元律AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=二、集合等式或包含关系的证明方法一：命题演算法例证明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.例证明AB=AB证任取x,xABxAxBxAxBxAB方法二：等式代入法(假设交换律、分配律、同一律、零律已经成立)例证明吸收律A(AB)=(AE)(AB)=A(EB)=A(BE)=AE=A命题演算证明法的书写规范(以下的X和Y代表集合公式)（1）证XY任取x，xX…xY（2）证X=Y方法一分别证明XY和YX方法二任取x，xX…xY注意：在使用方法二的格式时，必须保证每步推理都是充分必要的证明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代入)③④假设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与条件④矛盾.要求熟练掌握集合的两种表示法能够判别元素是否属于给定的集合能够判别两个集合之间是否存在包含、相等、真包含等关系熟练掌握集合的基本运算（普通运算）掌握证明集合等式或者包含关系的基本方法第六章习题课一、练习题1．判断下列命题是否为真。（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）为真，其余为假.2．设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⋢S1（1）和S5不交的子集不含有3和5，因此X=S2.（2）S4的子集只能是S4和S5.由于与S2不交，不能含有偶数，因此X=S5.（3）S1,S2,S3,S4和S5都是S1的子集，不包含在S3的子集含有偶数，因此X=S1,S2或S4.（4）XS3=意味着X是S3的子集，因此X=S3或S5.（5）由于S3是S1的子集，因此这样的X不存在.解3.判断以下命题的真假，并说明理由.（1）AB=AB=（2）A(BC)=(AB)(AC)（3）AA=A（4）如果AB=B，则A=E.（5）A={x}x，则xA且xA.（1）B=是AB=A的充分条件，但不是必要条件.当B不空但是与A不交时也有AB=A.（2）这是DM律，命题为真.（3）不符合算律，反例如下：A={1}，AA=，但是A.（4）命题不为真.AB=B的充分必要条件是BA，不是A=E.（5）命题为真，因为x既是A的元素，也是A的子集.解主要内容有序对与笛卡儿积二元关系的定义与表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系本章与后面各章的关系是函数的基础是图论的基础第七章二元关系一、有序对1．定义7.1由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作x,y.2．有序对性质（1）有序性x,yy,x（当xy时）（2）x,y与u,v相等的充分必要条件是x,y=u,vx=uy=v.第一节有序对与笛卡儿积一、笛卡儿积1．定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且AB={x,y|xAyB}.实例：A={1,2,3},B={a,b,c}AB={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}BA={a,1,b,1,c,1,a,2,b,2,c,2,a,3,b,3,c,3}A={},B=P(A)A={,,{},}P(A)B=2.笛卡儿积的性质（1）不适合交换律ABBA(AB,A,B)（2）不适合结合律(AB)CA(BC)(A,B,C)（3）对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)（4）若A或B中有一个为空集，则AB就是空集.A=B=（5）若|A|=m,|B|=n,则|AB|=mn性质的证明方法证明A(BC)=(AB)(AC)证任取x,yx,y∈A×(B∪C)x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)x,y∈A×B∨x,y∈A×Cx,y∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).例1（1)证明A=B,C=DAC=BD（2）AC=BD是否推出A=B,C=D?为什么？解（1）任取x,yx,yACxAyCxByDx,yBD（2)不一定.反例如下：A={1}，B={2},C=D=,则AC=BD但是AB.第二节二元关系一、二元关系的定义1．定义7.3如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果x,y∈R,可记作xRy；如果x,yR,则记作xy2．实例：R={1,2,a,b},S={1,2,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.二、从A到B的关系与A上的关系1．定义7.4设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例A={0,1},B={1,2,3},那么R1={0,2},R2=A×B,R3=,R4={0,1}R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.2.计数|A|=n,|A×A|=n2,A×A的子集有22n个.所以A上有22n个不同的二元关系.例如|A|=3,则A上有232=512个不同的二元关系.3.A上重要关系的实例定义7.5设A为任意集合是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系EA={x,y|x∈A∧y∈A}=A×AIA={x,x|x∈A}例如,A={1,2},则EA={1,1,1,2,2,1,2,2}IA={1,1