离散数学第五版第三章(耿素云、屈婉玲、张立昂编著).ppt

离散数学,第三章集合代数,1.集合的基本概念2.集合的运算3.集合恒等式,1.集合的基本概念,定义,一、集合、元素（成员）,集合是不能精确定义的概念。直观的说，将一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。,例如：26个英文字母的集合；C语言中关键字的集合；方程x*x-1=0的实数解集合；坐标平面上所有点的集合；全体中国人的集合；,1.集合的基本概念,集合的标记方法,集合通常用大写的英文字母来标记。,数学中常见集合的标记方法：自然数集合N；整数集合Z；有理数集合Q；实数集合R；复数集合C；,1.集合的基本概念,集合的表示方法,（1）列元素法:列出集合中的所有元素，元素之间用逗号分隔，并用花括号将他们括起来。,例如：A=1,2,3,4,7；B=A,B,C,Z；N=0,1,2,；,（2）谓词表示法：用谓词来概括集合中元素的属性B=x|P(x),例如：B=x|xRx*x-1=0B=x|xZ6=x=3,1.集合的基本概念,集合的特点,（1）无重复性：集合中的元素是彼此不同的，如果同一元素在集合中出现多次应该认为是一个元素。,例如：1,2,3,4,7=1,1,2,2,3,4,7；,（2）无序性：集合中的元素是无序的。,例如：1,2,3=2,3,1,集合中的元素本身也可以是一个集合，在本书中规定集合的元素都是集合。,1.集合的基本概念,二、元素与集合的关系（属于或不属于）,元素和集合之间的关系是隶属关系，即属于或不属于，属于记作，不属于记作。,例如：A=a,b,c,d,d,注意：对任何集合A都有AA。,1.集合的基本概念,包含（子集）定义,二、集合之间关系,设A,B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作BA。,BAx(xBxA),注意：对任何集合A都有AA。,例如：NZQRCa,a与a的关系？,1.集合的基本概念,相等定义,二、集合之间关系,设A,B为集合，如果AB且BA，则称A与B相等，记作A=B。如果A与B不相等，则记作AB。,A=BABBA,例如：A=x|x是小于等于3的素数B=x|x=2x=3则A=B,1.集合的基本概念,真子集定义,二、集合之间关系,设A,B为集合，如果BA且BA，则称B是A的真子集，记作BA。如果B不是A的真子集，则记作BA。,BABABA,例如：NZQRCAA,1.集合的基本概念,定义,三、空集,不含任何元素的集合叫做空集，记作。,=x|xx,例如：x|xRx*x+1=0=,定理,空集是一切集合的子集。,1.集合的基本概念,三、空集,例1：判断下列命题是否为真,(3)(4),真,真,真,真,1.集合的基本概念,问题：含有n个元素的集合简称n元集，它的含有m(m=n)个元素的子集叫做它的m元子集。任何一个n元集，如何求出它的全部子集？,例2：A=a,b,c，求A的全部子集。,0元子集，即空集，只有1个:。,1元子集，即单元集，有个：a、b、c。,2元子集，有个：a,b、a,c、b,c。,3元子集，有个：a,b,c。,所以：共有个子集，即个子集。,1.集合的基本概念,四、幂集,设A为集合，把A的全体子集构成的集合叫做A的幂集，记作P(A)。,符号化为：P(A)=x|xA,所以例2的幂集为：、a、b、c、a,b、a,c、b,c、a,b,c,注意：集合A的幂集中元素的个数为。,1.集合的基本概念,例3：计算以下幂集：,（1）P(),（2）P(),（3）P(,),（4）P(1,2,3),1,2,3,1,2,3,1.集合的基本概念,五、全集,在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E。,第三章集合代数,1.集合的基本概念2.集合的运算3.集合恒等式,2.集合的运算,交、并、相对补,设A，B为集合，A与B的并集AB，交集AB，B对A的相对补集A-B分别定义如下：,（1）AB=x|xAxB,（2）AB=x|xAxB,（3）A-B=x|xAxB,例4：A=1,2,3,B=1,4,C=3求：AB、AB、A-B、B-A、C-A、CB,2.集合的运算,对称差,设A，B为集合，A与B的对称差集AB定义如下：,AB=(A-B)(B-A),例5：A=0,1,2,B=2,3求：AB,AB=(AB)-(AB),2.集合的运算,绝对补,A=E-A=x|xExA,例6：E=a,b,c,d,A=a,b,c求：A,例7：对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13、5、10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言的人数和会三种语言的人数。,2.集合的运算,例7：对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13、5、10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言的人数和会三种语言的人数。,文氏图,可以使用文氏图来描述集合的关系、运算以及计数。,2.集合的运算,例8：求11000之间（包含1和1000在内）既不能被5和6，也不能被8整除的数有多少个。,S=x|xZ1=x=1000A=x|xSx可被5整除B=x|xSx可被6整除C=x|xSx可被8整除,|S|=1000|A|=1000/5=200|B|=1000/6=166|C|=1000/8=125|AB|=1000/lcm(5,6)=33|AC|=1000/lcm(5,8)=25|BC|=1000/lcm(6,8)=41|ABC|=1000/lcm(5,6,8)=8,2.集合的运算,例8：求11000之间（包含1和1000在内）既不能被5和6，也不能被8整除的数有多少个。,所以既不能被5、6，也不能被8整数的数有：1000-(100+200+33+67)=600,2.集合的运算,包含排斥定理,设S为有穷集，P1，P2Pm是m个性质。S中的任何元素x或者具有性质Pi，或者不具有性质Pi，两种情况必居其一。令Ai表示S中具有性质Pi的元素构成的子集，则S中不具有性质P1，P2，Pm的元素为,2.集合的运算,推论：S中至少具有一条性质的元素为,2.集合的运算,例9：某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球（指篮球或排球），求不会打这三种球的人数。,S：班级的25个学生集合A：会打篮球的学生集合B：会打网球的学生集合C：会打排球的学生集合,2.集合的运算,例10：一个班有50个学生，在第一次考试中有26个人得5分，在第二次考试中有21人得5分。如果两次考试中都没得5分的有17人，那么两次考试都得5分的有多少人？,S：50个学生集合A：第一次考试中得5分的学生集合B：第二次考试得5分的学生集合,2.集合的运算,广义并,设A为集合，A的元素的元素构成的集合称为A的广义并，记为A。符号化表示为：A=x|z(zAxz),例11：A=a,b,c,a,c,d,a,e,fB=aC=a,c,d则求A、B、C、,2.集合的运算,广义交,设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为A。符号化表示为：A=x|z(zAxz),例12：A=a,b,c,a,c,d,a,e,fB=aC=a,c,d则求A、B、C,2.集合的运算,集合运算的优先级,称广义并、广义交、幂集、绝对补运算为一类运算；并、交、相对补、对称差运算为二类运算；一类运算优先于二类运算；一类运算之间由右向左顺序进行；二类运算之间由括号决定先后顺序。,例13：A=a,a,b请计算A、A、A(A-A),第三章集合代数,1.集合的基本概念2.集合的运算3.集合恒等式,3.集合恒等式,集合恒等式（33条）,证明：对任意的x，x(AA)xAxAxA所以：AA=A,3.集合恒等式,证明：对任意的x，x(AB)Cx(AB)xC(xAxB)xCxA(xBxC)xA(BC)所以：(AB)C=A(BC),3.集合恒等式,交换律,分配律,同一律,同一律,3.集合恒等式,3.集合恒等式,例13A-(BC)=(A-B)(A-C),证明：对任意的x，xA-(BC)xAA(BC)xA(ABAC)xAABAC)(xAAB)(xAAC)x(A-B)x(A-C)x(A-B)(A-C),3.集合恒等式,排中律,ABA,ABB,AAB,BAB,A-BA,AB=BABAB=AA-B=,AB=BA,(AB)C=A(BC),A=A,AA=,AB=ACB=C,3.集合恒等式,例14(A-B)B=AB,证明：(A-