离散数学第1章集合及其运算.ppt

离 散 数 学 第1篇 集 合 论 第1章 集合及其运算 1.1 集合的概念与表示 一、集合的概念 一些确定的、可以区别于其它个体的对象的 总 和称为集合。 集合中的个体对象称为集合的元素，常用a、b 等 小写字母表示。 集合通常用A、B等大写字母表示。一些特定的 字母表示特定的集合，如 N、Z、Q、R、C。 元素与集合的关系称为属于关系。 元素a是集合A中的元素，记作 ，元素a不是 集 合A中的元素，记作 。 在集合的概念中需要强调指出三点： 1。集合中相同的元素，不论出现多少次，都 被 看作为一个元素。 2。集合中的元素是没有排列顺序的。例如集 合 A中的元素是a、b、c，集合B中的元素是c、a、b ， 那么，它们表示的是同一个集合。 3。集合中的元素可以是数、点、事物，还可 以 是集合。 根据集合中元素的个数，集合可分为有限集 合 和无限集合。 有限集合A中所包含的元素的个数以|A|表示 。 二、集合的表示方法 1列举法 列出集合中的所有元素，用大括号括起来。 例如，A=a,b,c,d,N=0,1,2,3,。 2。描述法 在大括号中，先说明元素怎样表示，再描述元素 具有的共同属性， 例如，N=x|x是非负整数,D=(x,y)| 3。图示法文氏图 用一个简单的平面区域(通常用圆)表示一个集合， 不同的集合用不同的平面区域表示。区域内的点表示 集合中的元素。 三、集合之间的关系 若集合A中的每一个元素都是集合B中的元素， 称 集合A是集合B的子集，记作 。 如 ，则 。 说明： 1。包含关系只适用于集合与集合之间。 2。若 ，则A=B。 3。若 ，且B中包含不属于A的元素，则称A是 B的真子集，记作 。 4。集合的包含关系具有： 自反性， 。 反对称性， 。 传递性， 。 四、特殊集合 1。空集：不包含任何元素的集合，记作 。 空集是任何集合的子集。 与是不同的。 2。全集：研究对象的全体组成的集合，用E表示。 任何集合都是全集的子集。 3。幂集：一个集合的所有子集组成的集合，记作 P(A) 如A=a,b，P(A)=,a,b,a,b 说明：幂集中所有的元素都是集合。 与P()是不同的，中没有元素，P()中有 一个元素 ，P()=。 若A中有n个元素，则P(A)中有2n个元素。 例1 设A=1,2,3，则P(A)= 。 解： P(A)= ,1,2, 3,1,2),1,3,2,3,A 例2 设A= ,a，则P(A)= 。 解： P(A)= ,a, ,a 例3 设A=a ,a，下列命题中不正确的是 。 (1) (2) (3) (4) 解: P(A)= ,a,a, a,a ,不正确的是(2) 1.2 集合的运算及其性质 一、集合的运算 集合的运算有并、交、差、补和对称差。 1。集合的并 由所有属于A或属于B的元素组成的集合称为 集 合A与B的并集，记作 。 例如A=1,2,3,4，B=2,4,6， 2。集合的交 由所有既属于A又属于B的元素组成的集合称 为 集合A与B的交集，记作 。 例如A=1,2,3,4，B=2,4,6， 集合的并、交与集合之间有如下关系： 1。对于任意集合A、B 2。如果 AB A B 例4，证明 证明集合命题的第一种方法是通过在集合中任 取 一个元素，利用集合的定义进行证明。 证明： 3。集合的差 由所有属于A但不属于B的元素组成的集合称 为 集合A与B的差，记作 AB 。 集合A与B的差AB与集合B与A的差BA是不同 的 例如A=1,2,3,4，B=2,4,6， AB=1,3， BA=6 4。补集 由全集E中所有不属于A的元素组成的集合称 为 集合A的补集，记作A。 E 故有 A-B B-A A A 例5 设A,B,C是整数集Z的子集，其中A=1,2,4 求 解： A=1,2,4，B=-3,-2,-1,0,1,2,3，C=0,3,6,9 5。集合的对称差 集合 称为集合A、B的对称差 ， 记作 。 从右边的文氏图中可以看出: 例如A=1,2,3,4，B=2,4,6， 例6 设E=1,2,3,4,5,A=1,4,B=1,2,5,C=2,4 求 解: A-B B-A 例7 设集合 ， 求 。 解： 二、集合运算的性质 集合的运算满足如下运算律。 1交换律 2结合律 3分配律 4幂等律 5同一律 6零律 7补余律 8吸收律 9摩根律 10双补律 对称差的性质类似并集，有: 交换律 结合律 分配律 零一律 消去律 例8 设A,B,C为任意集合，下列命题为真的是 。 A）如果 C） B）如果 D） 例9，若 ，证明B=C 证明集合恒等式的第二种方法是利用上面所述的运 算律进行证明。 证明： D 例10 试证明对于任意集合A、B、C、D，有 证明： 例11 化简下列集合表示式： 解：(1)错误做法: 正确做法是: (2)错误做法: 正确做法是: 1.3 有限集合的计数 一、有限集合的计数定理(容斥定理) (1) (2) (3) (4) (5) 二、文氏图是有限集合计数的有效工具，图 形区域的面积就表示集合中元素的个数。 例13 在20名青年中有10名是公务员，有12名是女 性，其中女公务员有5名，问不是公务员的男性 有多少名？ 解: 设E=全体青年，A=公务员，B=女性 则 |E|=20，|A|=10，|B|=12， 用文氏图解答的情况如右： 例14 求