Ch01集合论培训资料.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 厦门大学信息科学与技术学院智能科学系 2008--* 1.4.2 容斥原理 定义1.18　所谓容斥，是指我们计算某类物的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿，这种原理称为容斥原理，又称为包含排斥原理。 * 厦门大学信息科学与技术学院智能科学系 2008--* 定理1.7 设A和B是任意有限集合，有? |A∪B|＝|A|＋|B|－|A∩B|。 证明: A∪B＝(A-B)∪(A∩B)∪(B-A)， A＝(A-B)∪(A∩B)， B＝(A∩B)∪(B-A)， 故:|A|＝|A-B|+|A∩B|， |B|＝|A∩B|+|B-A|， |A|＋|B|=|A-B|+2*|A∩B|+|B-A| |A∪B|＝|A-B|+|A∩B|+|B-A| ＝|A|＋|B|－|A∩B| A B * 厦门大学信息科学与技术学院智能科学系 2008--* 推论1.1 设U为全集，A和B是任意有限集合，则? ＝|U|－(|A|＋|B|)＋|A∩B| 证明： ＝ ＝|U-(A∪B)| ＝|U|－|A∪B|＝|U|－(|A|＋|B|)＋|A∩B|。 * 厦门大学信息科学与技术学院智能科学系 2008--* 例1.30 某软件公司的程序员都熟悉C++或VB，其中熟悉C++的共47人，熟悉VB的共35人，C++和VB都熟悉的共23人，问该公司共有多少程序员？ 解：设A、B分别表示熟悉C++和VB的程序员集合，则该公司的程序员集合为A∪B，利用容斥原理得： |A∪B|＝|A|＋|B|－|A∩B| ＝47＋35－23＝59 故该公司共有59名程序员。 * 厦门大学信息科学与技术学院智能科学系 2008--* 定理1.8 设A1,A2,…,An是任意有限集合，有: * 厦门大学信息科学与技术学院智能科学系 2008--* 推论1.2 设U为全集，A1,A2,…,An是任意有限集合，有 * 厦门大学信息科学与技术学院智能科学系 2008--* 例1.31 对24名科技人员进行掌握外语情况的调查，其统计资料如下：会英、日、德、法语的人数分别为13、5、10和9。其中同时会英语、日语的人数为2；同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的人数均为4；会日语的人既不会法语也不会德语。试求只会一种语言的人数各为多少？又同时会英、德、法语的人数为多少？? * 厦门大学信息科学与技术学院智能科学系 2008--* 解： 设A、B、C、D分别为会英、日、德、法语的人的集合，由已知条件可知：? |A|＝13，|B|＝5，|C|＝10，|D|＝9， |A∩B|＝2，|A∩C|＝|A∩D|＝|C∩D|＝4，|B∩C|＝|B∩D|＝0, |A∩B∩C|＝|A∩B∩D|＝|B∩C∩D|＝0， |A∩B∩C∩D|＝0， |A∪B∪C∪D|＝24， * 厦门大学信息科学与技术学院智能科学系 2008--* 解(续) 利用容斥原理，并代入已知条件得 24＝13＋5＋10＋9－2－4－4－4－0－0＋0＋0＋0 ＋|A∩C∩D|－0。 得:|A∩C∩D|＝1，即同时会英、德、法语的只有1人。 设只会英、日、德、法语的人数分别为x1,x2,x3,x4，则 x1＝|A|－|(B∪C∪D)∩A|＝|A|－|(B∩A)∪(C∩A)∪(D∩A)| 对B∩A、C∩A、D∩A应用容斥原理，得 |(B∩A)∪(C∩A)∪(D∩A)|＝2＋4＋4－0－0－1＋0＝9 故，x1＝13-9＝4。 类似地可求出：x2＝3，x3＝3，x4＝2。 * 厦门大学信息科学与技术学院智能科学系 2008--* 习题 王元元 张桂芸：《离散数学》 第2版。 P 4-6： 1,3,5,6,9 P 13-15： 1,5,8,9,13 P28-29： 1,3,7 * * * * * * * * * * * * * * * * * * * * * * * 厦门大学信息科学与技术学院智能科学系 2008--* 定义1.13 设U是全集，A是U的子集，则 ＝U-A＝{x|x?U并且x?A} 仍是一个集合，称它为集合A的补集(也可记为Ａ＇，～Ａ，AC等），“￣”称为补运算（Complement Operation）。用文氏图可表示如下： 补集 U A * 厦门大学信息科学与技术学院智能科学系 2008--* 例1.24 设U＝Z，则 ＝Z-E＝O， ＝Z-O＝E （其中