离散数学高教版屈婉玲06.pptVIP

Discrete Math. , huang liujia 离散数学 Discrete Mathematics 1.集合：将一些事物汇集到一起组成的整体，其中每个事物称为这个集合的元素。 注：如果x是集合A的元素，则记为x?A 。 集合的表示方法：列元素法和谓词表示法 列元素法：列出集合的所有元素或部分元素，可用于有限集和有一定规律的无限集。如： A={a，b，…，z} Z={0，-1，1，-2，2，…} D={a，{a}，{a，b}}集合中的元素还可以是集合。 谓词表示法：用谓词来描述集合中元素的性质。 如：B={x | x∈R ∧(x-1=0)} 描述法 ={x | F(x)∧G(x)} 谓词描述法 设F(x):x∈R ,G(x):x-1=0 . 集合的性质： （1）集合的元素是彼此不同的，相同的元素应该认为是同一个元素。 （2）集合的元素是无序的。如：{1，2，3}={2，3，1} 注：元素与集合的关系是属于∈和不属于? 。 本书规定集合的元素都是集合。对任何集合A，都有A?A . 2.子集合(Def 6.1):若集合B中的元素都在集合A中，则称B是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)。 5.空集(Def6.4)：不含任何元素的集合称为空集，记为? 注: 1. 空集的符号化：? ={x|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 | B ? A}。 续例 6.1 设A={1,2,3},求P(A)。 8.全集(Def6.6)：如果一个问题中所涉及的集合都是某一集合的子集，则称该集合为全集。全集一般记为E。 注：不同问题有不同的全集，同一问题也可以取不同的全集。一般 总是将全集取得尽可能小，以便描述和处理问题更加简便。 例：求下列集合的幂集合。 (1){?,{?}} (2){? ? {?}} (3){{1,2},{2,1,1},{2,1,1,2}} 一. 集合的基本运算 设A,B是集合(def6.7~~6.9) 1.A与B的并：A∪B = { x | x ?A∨ x ?B } 2.A与B的交：A∩B = { x | x ?A ∧ x ?B } 3.A与B的差(B对A的相对补)：A – B = { x | x ?A∧ x ?B } 4.A与B的对称差：A⊕B=(A – B)∪(B–A)=(A∪B) – (A∩B) 5.A的补集(或称绝对补)：～A = E – A = { x | x ?E∧ x ?A } 注: (1)“并”和“交”运算可以推广到有（无）限个集合： 集合运算的进一步推广 定义6.10 设A为集合，A的元素的元素构成的集合称为A的广义并，记为∪A。 符号化 ∪A={x| ?z ( z∈A∧x∈z ) } 若A={A1，A2，…，An} 则∪A=A1∪A2∪…∪An。 定义6.11 设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为∩A。 符号化 ∩A={x| ? z（z∈A→x∈z）} 若A={A1，A2，…，An} 则∩A=A1∩A2∩…∩An。 集合运算的进一步推