离散数学0743440

1、第三章第三章 集合集合今天先学习本章的第二个知识点：今天先学习本章的第二个知识点：1 1、集合的基本概念；、集合的基本概念；2 2、集合的运算；、集合的运算；3 3、基本集合恒等式；、基本集合恒等式；4 4、容斥原理；、容斥原理；5 5、集合的笛卡尔积。、集合的笛卡尔积。3.2 集合的运算集合的运算一、并、交、差、补一、并、交、差、补定义定义3.2.1 设设 A 和和 B 是集合，则它们的是集合，则它们的并 、交 、差 和和 A 的的补 分别定义如下：分别定义如下：BABABAA;AxxAUABxAxxBABxAxxBABxAxxBA若若 ，则称，则称A 与与 B 是是不相交的。的。 又又称为

2、称为相对补， 又称为又称为绝对补。BABAA例例3.2.1 设全集设全集529, 5, 4, 18, 6, 5, 4, 2,90 xxIxxCBAxxIxxU求求 。BCBAABBAABAB),()( ,解：解： 3, 29, 8, 7, 6, 5, 4, 1, 09, 5, 4, 19, 8, 7, 6, 5, 1, 0,8, 6, 28, 6, 28, 7, 6, 5, 4, 3, 2, 0)(,8, 6, 2,8, 7, 6, 5, 4, 3, 2, 0,9, 1BCBAABBAABAB例题讲解：例题讲解：P.62，例例3.2.2定理定理3.2.1 设设 A、B 和和 C 是集合，则是集

3、合，则。则则，若若则则，若若则则，若若ABBACBACABACBACBCABABAABABBAABABABBAA)7(;,)6(;,)5(;)4(;) 3(;,)2(;,) 1 (二、广义交和广义并二、广义交和广义并1 1、集类的概念、集类的概念2、广义并和广义交的定义及标记方法、广义并和广义交的定义及标记方法广义并和广义交的常用记号：广义并和广义交的常用记号：例例3.2.3 )5()4()3(56, 5,5, 4, 3,5, 2, 1)2(6, 5, 4, 3, 2, 16, 5,5, 4, 3,5, 2, 1) 1 (例例3.2.4 例例3.2.5 3、性质、性质三、环和与环积三、环和与环

4、积定义定义3.2.3 设设 A 和和 B 是集合，则是集合，则 A与与 B 的的环环和 及环积 的定义如下：的定义如下：BABABABAABBABA)()(例例3.2.6 已知已知fedcbaUebaBdaA, UAAAAAAAAfcaedbfedcbaBAUBABAedbebdABBABA)()(,)()(则则四、幂四、幂1 1、幂集的定义、幂集的定义定义定义3.2.4 设设 A 是集合，则称是集合，则称 为为 A 的幂集，的幂集，记为记为 或或 。Axx)(AA2 该定义的含义是：该定义的含义是：A的幂集是由的幂集是由A的的所有子所有子集集组成的组成的集合集合。例例3.2.7 .,),(;

5、,)(;,)(;)(bababa定理定理3.2.3 设设 A、B 是任意集合，则是任意集合，则);()(,)4();()(,) 3();()2();() 1 (BABABABAAAA则则若若则则若若2、幂集的性质、幂集的性质请同学们请同学们读读 P.64 的证明过程。的证明过程。3、幂集元素的数量、幂集元素的数量AA2)(定理定理3.2.4 设设 A 是有限集，则是有限集，则 。 通常可对集合中的元素编定一种次序，在集通常可对集合中的元素编定一种次序，在集合与二进制数之间建立对应关系。合与二进制数之间建立对应关系。例例3.2.2 设设 ，规定元素的次序为，规定元素的次序为a、b、c。 若给定若

6、给定集合集合，则有则有 。 若给定若给定二进制数二进制数，则：则： 。cbaU,011,101,cbca，baU,110,111,000本节习题本节习题P.65，习题，习题3.2 1.(1)、(2) 、(4) 、(6) 、(7) 4.(1)、(4) 5.(3)下面我们学习第三个知识点：下面我们学习第三个知识点：1 1、集合的基本概念；、集合的基本概念；2 2、集合的运算；、集合的运算；3 3、基本集合恒等式；、基本集合恒等式；4 4、容斥原理；、容斥原理；5 5、集合的笛卡尔积。、集合的笛卡尔积。3.3 基本集合恒等式基本集合恒等式1、并、交、差、补的基本恒等式（1）等幂律（2）结合律（3）交

7、换律（4）分配律);()()(),()()(;,);()(),()(;,CABACBACABACBAABBAABBACBACBACBACBAAAAAAA（5）同一律（6）零 律（7）排中律（8）矛盾律（9）吸收律 (10) 德.摩根定律 (11) 余补律 (12) 双重否定律AAUUBABABABAABAAABAAAAUAAAUUAAUAAA;,;,;)(,)(;,;,定律（定律（4）的证明：）的证明： )()()()()()()()(CABAxCAxBAxCxAxBxAxCxBxAxCBxAxCBAx例例3.3.1 设设 A、B 和和 C 是集合，且是集合，且 ，则，则 CABACABA,。

8、CB CACCCACBACBCACCBCACBBACBABCABBABABBB)()()()()()()()()()()()()()(证明：例例3.3.2 设设 A 和和 B 是任意集合。证明是任意集合。证明 BABA证明：必要性BxBxAxxBxAxBAxBxAxBxAxBxAxBxBxAxBBxAxAx)()(2、环和与环积的基本恒等式);()()(),()()()16();()(),()()15(;,)14(;,)13(CABACBACABACBACBACBACBACBAABBAABBAUAAAA3、幂的基本恒等式).()()()19();()()()18();()()17(BABABA

9、BABABA本节习题本节习题P.68，习题，习题3.3 1.(3)、(5) 3. 4.(2) 5.(5)下面我们学习第四个知识点：下面我们学习第四个知识点：1 1、集合的基本概念；、集合的基本概念；2 2、集合的运算；、集合的运算；3 3、基本集合恒等式；、基本集合恒等式；4 4、容斥原理；、容斥原理；5 5、集合的笛卡尔积。、集合的笛卡尔积。3.4 容斥原理容斥原理容斥原理 设设 是有限集，是有限集，)2(,21nAAAnnnnkjikjinjijiniinAAAAAAAAAAAA21111121) 1(则则例如：例如：当当 n = 3 时，时，321323121321321AAAAAAAA

10、AAAAAAA当当 n = 4 时呢时呢？请大家写一下！？请大家写一下！答案：答案：432143243142132143423241312143214321AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA例例3.4.1解：设 A = 选 C 语言的学生， B = 选 Pascal 语言的学生， C = 选 Basic 语言的学生。 依题义，有：.150,3062,48,76,160,208,260CBACBACBCABACBA（1）学生的总数为：62215030624876160208260)()(CBACBACBCABACBACBACBACBACBAU（2）选 C 语

11、言和 Pascal 语言但不选 Basic 语言的学生人数为：CBA463076)()()()()(CBABACBACBACBACBACBACBACBABACBACBACCBABA同理可得：同理可得：CBA183048CBACACBA（3）选 C 语言和 Basic 语言但不选 Pascal 语言的学生人数为：（4）选 Pascal 语言和 Basic 语言但不选 C 语言的学生人数为：323062CBACBCBACBA（5）只选 C 语言而不选 Pascal 和 Basic 语言的学生人数为：CBA166184630260)()()()()()()()()()(CBACBACBAACBACB

12、ACBACBACBAACBACBACBACBACBCBCBCBACCBBAA（6）只选 Pascal 语言而不选 C 和 Basic 语言的学生人数为：CBA100324630208CBACBACBABCBA（7）只选 Basic 语言而不选 C 和 Pascal 语言的学生人数为：CBA80321830160CBACBACBACCBA同理可得：同理可得：本节习题本节习题P.71，习题，习题3.4 2. 3.课堂小测验课堂小测验1、设、设 ：x 具有性质具有性质 F， ：y 具有性质具有性质G。命题。命题“若若存在存在 x 具有性质具有性质 F，则所有的，则所有的 y 都具有性质都具有性质G。”的符号化的符号化形