《离散数学资料》PPT课件.ppt

2023/7/28,离散数学,1,第三章 集合的基本概念和运算 3.1 集合的基本概念 3.2 集合的基本运算 3.3 集合中元素的计数,2023/7/28,离散数学,2,一、集合,集 合：一些可确定的可分辨的事物构成的整体。用大写字母A,B,C,标记。,3.1 集合的基本概念,集合的元素：一个集合的每一个特定的事物。用小 写字母a,b,c,标记。,如:(1)26个英文字母的集合；(2)坐标平面上所有点的集合。,规定：集合的元素之间彼此相异，无次序关系。,2023/7/28,离散数学,3,二、常用的集合,常用的集合记号：N:自然数集合(包括0)Z:整数集合 Q:有理数集合 R:实数集合 C:复数集合:空集(不含任何元素)E:全集,2023/7/28,离散数学,4,三、集合的表示方法,列出集合的所有元素，元素之间用逗号 隔开。如A=a,b,c,用谓词概括该集合中元素的属性。即：A=x|P(x)如：A=x|xZ 3 x 6,1、列举法：2、描述法：,元素与集合之间的关系(属于):若A=a,a,b,a,b,则aA,a A,2023/7/28,离散数学,5,3、真子集：如果B A且A B，则B是A的真子集。记作B A。,四、集合之间的关系,1、子 集：集合B中的每个元素都是集合A中的元素，则B是A的子集，记作B A。符号化为 B A x(xB xA),2、相等集：如果A B且B A，则A与B相等。记作 A=B。符号化为A=B A B B A,显然：A A，A,2023/7/28,离散数学,6,解：0元子集：，,四、集合之间的关系（续）,4、幂 集：集合A的全体子集构成的集合，记作P(A)。符号化为P(A)=x|x A,例1：A=a,b,c，求A的幂集P(A)。,n 元集A的幂集P(A)含有2n个元素。,1元子集：a,b,c，,2元子集：a,b,a,c,b,c，,P(A)=,a,b,c,a,b,a,c,b,c,a,b,c,3元子集：a,b,c,2023/7/28,离散数学,7,四、集合之间的关系（续）,例2：计算以下幂集。(1)P()；(2)P(,)；(3)P(1,2,3)。,解：(1)P()=,(2)P(,)=,(3)P(1,2,3)=,1,2,3,1,2,3,2023/7/28,离散数学,8,1、并：AB=x|xA xB,一、几种常见的运算,3.2 集合的基本运算,2、交：AB=x|xA xB，若AB=，则称A与B不交。,3、相对补：A B=x|xA xB（B对A的）,4、绝对补：A对全集E的相对补集，记作：A A=E A=x|xE xA,5、对称差：A B=(AB)(BA)=(AB)(AB),2023/7/28,离散数学,9,二、文氏图,2023/7/28,离散数学,10,三、集合算律,(1)幂等律：,AA=A,AA=A,(2)结合律：,(3)交换律：,(4)分配律：,(AB)C=A(BC),(AB)C=A(BC),AB=BA,AB=BA,A(BC)=(AB)(AC),A(BC)=(AB)(AC),2023/7/28,离散数学,11,三、集合算律（续）,(5)同一律：,A=A,AE=A,(6)零 律：,(7)排中律：,(8)矛盾律：,AE=E,A=,A A=E,A A=,A(AB)=A,A(AB)=A,(9)吸收律：,2023/7/28,离散数学,12,三、集合算律（续）,(10)德 摩根律：,A(BC)=(A B)(A C),A(BC)=(A B)(A C),(BC)=B C,(BC)=B C,=E,E=,(A)=A,(11)双重否定律：,2023/7/28,离散数学,13,四、集合算律（续）,以上恒等式的证明主要通过命题演算等值式。,P Q Q P,即证xP xQ和 xQ xP 成立，,即证xP xQ,证明的基本思想是：欲证P=Q，即证：,2023/7/28,离散数学,14,四、集合算律（续）,例3：证明A(BC)=(A B)(A C),x A x BC,x A(x BC),证明：,x A(BC),x A(x B x C),x A(x B)(x C),x A(x B x C),(xA x B)(xA xC),(xA B)(xA C),故：A(BC)=(A B)(A C),x(A B)(A C),2023/7/28,离散数学,15,四、常用运算性质,(1)AB A AB B,(2)A AB B AB,(3)A B A,(4)A B=A B,(5)AB=B A B AB=A A B=,(6)A B=B A,(7)(A B)C=A(B C),2023/7/28,离散数学,16,四、常用运算性质（续）,(8)A=A,(9)A A=,(10)A B=A C B=C,证明两个集合相等，除了采用命题演算等值式外，还可以采用集合运算性质。集合运算性质也可用于证明两个集合之间的包含关系。,2023/7/28,离散数学,17,四、常用运算性质（续）,证明：(A B)B=(A B)B,=(AB)(BB),例4：证明(A B)B=AB,=(AB)E,=AB,2023/7/28,离散数学,18,四、常用运算性质（续）,例3：化简(ABC)(AB)(A(B C)A),解：AB ABC 和 A A(B C),(ABC)(AB)=AB,原式=(AB)A=(AB)A=B A,(A(B C)A=A,2023/7/28,离散数学,19,3.3 集合中元素的计数,基数：集合中元素的个数，用|A|表示。,容斥原理：对任意两个有限集A和B，有|AB|=|A|+|B|AB|,一、理论,推广1：|ABC|=|A|+|B|+|C|AB|AC|BC|+|ABC|,|=|E|ABC|,推广2：,2023/7/28,离散数学,20,例4：某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，2人会打这三种球，而6个会打网球的人都会打另外一种球(指篮球或排球)，求不会打这三种球的人数？,二、应用,解：分别用A,B,C表示会打篮球、排球、网球的学 生集合。,依题意有：|A|=14，|B|=12，|C|=6，|AB|=6，|AC|=5，|ABC|=2，且有C AB，求|,2023/7/28,离散数学,21,二、应用（续）,于是 C=C(AB)=(CA)(CB),|=|E|ABC|=25 20=5,从而|ABC|=|A|+|B|+|C|AB|AC|BC|+|ABC|=14+12+6 6 5 3+2=20,得|BC|=3,6=5+|BC|2,|C|=|AC|+|BC|ABC|,2023/7/28,离散数学,22,例5：一个班有50个学生，第一次考试有26人得5分，第二次考试有21人得5分。如果两次考试都没得5分的有17人，那么在两次考试都得5分的有多少人？,二、应用（续）,解：分别用A,B表示第一次考试得5分和第二次考试得5分的学生集合。,依题意有：|A|=26，|B|=21，|=17,=|A|+|B|(|E|),=26+21 50+17=14,则|AB|=|A|+|B|AB|,