离散数学高教版屈婉玲.ppt

《离散数学高教版屈婉玲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics7/29/20211DiscreteMath.,huangliujia第六章集合代数6.1集合的基本概念6.2集合的运算6.3有穷集合的计数6.4集合恒等式7/29/20212DiscreteMath.,huangliujia1.集合：将一些事物汇集到一起组成的整体，其中每个事物称为这个集合的元素。注：如果x是集合A的元素，则记为xA。集合的表示方法：列元素法和谓词表示法列元素法：列出集合的所有元素或部分元素，可用于有限集和有一定规律的无限集。如：A={a，b，…，z}Z={0，-1，1，-2，2，…}D={a，{a}，{a，b

2、}}集合中的元素还可以是集合。谓词表示法：用谓词来描述集合中元素的性质。如：B={x

3、x∈R∧(x-1=0)}描述法={x

4、F(x)∧G(x)}谓词描述法设F(x):x∈R,G(x):x-1=0.集合的性质：（1）集合的元素是彼此不同的，相同的元素应该认为是同一个元素。（2）集合的元素是无序的。如：{1，2，3}={2，3，1}§6.1集合的基本概念7/29/20213DiscreteMath.,huangliujia注：元素与集合的关系是属于∈和不属于。本书规定集合的元素都是集合。对任何集合A，都有AA.2.子集合(Def6.1):若集合B中的元素都在集合A中，则称B是

5、A的子集合(简称子集)。这时也称B被A包含，或A包含B。记为BA。如果B不被A包含，则记为BA。注：(1)包含的符号化：BAx(xB→xA)。(2)对任何集合A，都有AA。3.集合的相等(Def6.2):如果AB且BA,则称集合A与B相等，记为A=B。注：相等的符号化：A=BAB∧BA。4.真子集(Def6.3):对符号A,B,若BA且BA,则称B是A的真子集,记为BA。如果B不是A的真子集，则记为BA。注：真子集的符号化：BA(BA)∧(BA)。§6.1集合的基本概念7/29/20214DiscreteMath.,huangliuj

6、ia5.空集(Def6.4)：不含任何元素的集合称为空集，记为Ø注:1.空集的符号化：Ø={x

7、xx}。2.Th6.1空集是一切集合的子集。（证明见教材P85）。3.Cor空集是唯一的。（证明见教材P85）。6.n元集：含有n个元素的集合。它共有2n个子集合。例6.1设A={1,2,3},求A的所有子集合。7.集合A的幂集(Def6.5)：由A的所有子集作为元素形成的集合。记为P(A)或2A。注：幂集的符号化：P(A)={B

8、BA}。续例6.1设A={1,2,3},求P(A)。8.全集(Def6.6)：如果一个问题中所涉及的集合都是某一集合的子集，则称该集合为全集。全集一

9、般记为E。注：不同问题有不同的全集，同一问题也可以取不同的全集。一般总是将全集取得尽可能小，以便描述和处理问题更加简便。§6.1集合的基本概念7/29/20215DiscreteMath.,huangliujia例：求下列集合的幂集合。(1){Ø,{Ø}}(2){Ø{Ø}}(3){{1,2},{2,1,1},{2,1,1,2}}§6.1集合的基本概念解：(1)P({Ø,{Ø}})={Ø,{Ø},{{Ø}},{Ø,{Ø}}}.(2)P({Ø{Ø}})=P({{Ø}})={Ø,{{Ø}}}.(3)P({{1,2},{2,1,1},{2,1,1,2}})=P({{1,2}})=

10、{Ø,{{1,2}}}.例：判断真伪。(1){x}{x}(2){x}∈{x}(3){x}∈{x,{x}}(4){x}{x,{x}}(5){x}{x}x(6)若x∈A,A∈P(B),则x∈P(B)(7)若xA,AP(B),则xP(B)7/29/20216DiscreteMath.,huangliujia一.集合的基本运算设A,B是集合(def6.7~~6.9)1.A与B的并：A∪B={x

11、xA∨xB}2.A与B的交：A∩B={x

12、xA∧xB}3.A与B的差(B对A的相对补)：A–B={x

13、xA∧xB}4.A与B的对称差：A⊕B=(A–B)∪(B–A)=

14、(A∪B)–(A∩B)5.A的补集(或称绝对补)：～A=E–A={x

15、xE∧xA}注:(1)“并”和“交”运算可以推广到有（无）限个集合：§6.2集合的运算7/29/20217DiscreteMath.,huangliujia集合运算的进一步推广定义6.10设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。符号化∪A={x

16、z(z∈A∧x∈z)}若A={A1，A2，…，An}则∪A=A1∪A2∪…∪An。定义6.11设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为∩