1、离散数学DISCRETE MATHEMATICS,教师:石兵Email:,二零一三,本次课重点,集合定义集合运算幂集和笛卡儿乘集,1873年12月7日,德国数学家Cantor(18451918)给出集合的描述定义,翻译如下:“把在我们直观或思维中的某些确定的、彼此区别的对象作为一个整体来考虑，称其为集合，而称这些对象为该集合的元素。”1889年，意大利数学家G.Peano（18581932）引入了元素和集合关系的符号和，以及集合之间子集关系的符号,第三章 集合及其运算,一、基本概念 集合的表示法 外延法：列举出构成集合的全部元素。 例：A=1，2，3，a，b，c 内含法：用谓词描述集合元素应满
2、足的条件。 例：B=xx 2 x 3, 几个关系符,成员关系符：“ ”和“” 例：3 A， 2.5 B， d A， 1.5 B 子集关系符：“”和“” 例：A A， 1，3，c A 相等关系符：“=” X=Y当且仅当X Y且Y X。, 几个常用的集合符号,：空集符 U：全集符 N：自然数集符 I：整数集符 R：实数集符,1. 补运算,定义：A =xxU x A 例:设A=1，2，3， B=xx是12的正因子是全集， 则 A =4，6，12,二、集合间的运算,A,U,A,集合运算的Venn图表示,二、集合间的运算,2. 并运算 定义：A B=xxA x B 性质： 交换律： A B= B A 结
3、合律： (A B) C= A (B C) 幂等律： A A= A 如果A B，则A C B C,3.交运算 ,定义：A B=xxA x B 性质： 交换律： A B= B A 结合律： (A B) C= A (B C) 幂等律： A A= A 如果A B，则A C B C,A,B,A,A B,A B,B,集合运算的Venn 图表示, 和 之间的分配律： A (B C)= (A B) (A C) A (B C)= (A B) (A C) 吸收律 A (A C) = A A (A C) = A,4. 差运算 ,定义：A B=xxA x B 例:设A=1，2，3，5，7，10 B=xx是12的正因子
4、 则 A B=5，7，10 B A=4，6，12 性质： A B= A （A B）= A B,B,A,A B,集合运算的Venn图表示,补运算,定义：A =xxU x A 例:设A=1，2，3， B=xx是12的正因子是全集， 则 A =4，6，12 性质： 德. 摩根律: A B = A B A B = A B 如果 A B ，则 B A。, 对称差运算,定义：A B=xxAB x AB 例:设A=1，2，3，a，b，c， B=x x是12的正因子， 则 A B =a，b，c，4，6，12 性质： 交换律: A B = B A 结合律：( A B) C = A (B C),A B,A,B,三
5、、幂集,1、定义：设A是集合，2A =XX A，称 2A为集合A的幂集合。换句话说，由A的 全部子集构成的集合称为A的幂集合。 例：当A=1, 2, a时， 2A =, 1, 2, a, 1, 2, 1, a, 2, a, 1, 2, a 2、如果A含n个元素，则2A含2 n个元素。,四、笛卡尔集,1、定义：集合A和B的笛卡尔集是 A B= (a, b) aA b B， 其中 称为笛卡尔积或直积。 例：设A=1，2，B=a，b，c，则A B= (1, a), (1, b) , (1, c), (2, a), (2, b), (2, c) ，BA= (a, 1), (b, 1) , (c, 1)
6、, (a, 2), (b, 2), (c, 2) 。 可见，一般A B不等于 BA。,2、n个集合D1，D2，Dn 的笛卡尔集 记为D1D2 Dn =(d1, d2, dn) d1D1 d2D2 dnDn， 例：设A=1, 2， 则 AAA= (1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2) 。,证题举例,在集合论的证明题中，既可按定义推证， 也可以利用已知公式等价变换。可以充 分利用逻辑等价与蕴含的知识。例 1、证明：如果A B A B，则A=B 。证明：由A B A
7、B和德.摩根律得到 A B A B,于是，A A B A (A B) 即 B A , 由此 A B。 同理可得B A ，这就证明了结论。 例2、证明：如果集合A和 B之间不存在 子集关系，则2A 2B 2 A B。 证明：X 2A 2B X 2A X 2B X A X B, X A B X 2 A B 这就证明了 2A 2B 2 A B 。剩下只 需证明等号不成立。 由已知条件，必有a A B和 b B A， 使a, b 2 A B ，但a, b 2A 2B 。 至此，我们证明了题目的结论。,例3、证明：如果A、B、C、D都不是 空集，则A B C D当且仅当 A C B D。 证明：当A B C D时，(a, b) A B (a, b) C D，由此 a A a C b B b D。即推出 A C B D。,反过来，当A C B D时，由直积 定义，必然 (a, b)A B (a, b)C D， 也就是A B C D。 本章作业：习题三 4, 习题三 9（3）（5），10习题三 16，17习题3.1 4 , 习题3.2 3(3)(5), 4, 习题3. 3 4, 5 *(3.4 2,3)附加题：证明 ( A B) C = A (B C),
