天津理工大学：《离散数学》课程教学资源（PPT课件）第三章 集合论（集合的基本概念和运算）3.3 集合中元素的计数、第四章 二元关系与函数 4.1 集合的笛卡尔积与二元关系

3.3集合中元素的计数4.1集合的笛卡尔积与二元关系

3.3集合中元素的计数 4.1集合的笛卡尔积与 二元关系

3.3集合中元素的计数集合的基数与有穷集合1包含排斥原理1有穷集的计数

◼ 集合的基数与有穷集合 ◼ 包含排斥原理 ◼ 有穷集的计数 3.3 集合中元素的计数

集合的基数与有穷集合集合A的基数：集合A中的元素数，记作cardA有穷集A：总存在n,使cardA=A|=n，n为自然数有穷集的实例：A={ a,b,cf, cardA=A|=3;B={x|x2+1=0,xER)}, cardB=|B=0无穷集的实例：N, Z, Q, R,C 等

集合 A 的基数：集合A中的元素数，记作 cardA 有穷集 A：总存在n,使 cardA=|A|=n，n为自然数. 有穷集的实例： A={ a,b,c}, cardA=|A|=3； B={ x | x 2+1=0, xR}, cardB=|B|=0 无穷集的实例： N, Z, Q, R, C 等 集合的基数与有穷集合

例子3.9有100名程序员，其中47名熟悉FORTRAN语言，35名熟悉PASCAL语言，23名熟悉这两种语言。问有多少人对这两种语言都不熟悉？

◼例子3.9 有100名程序员，其中47名熟悉 FORTRAN语言，35名熟悉 PASCAL语言，23名熟悉这两种 语言。问有多少人对这两种语言都 不熟悉？

包含排斥原理（容斥原理）ANA|= Isl -(|A|+|A2l )+ [ANAA1A2

包含排斥原理（容斥原理） A1  A2 s A1 = -( + A2 )+ A1  A2 A1 A2

包含排斥原理（容斥原理）定理设S为有穷集，Pi,P2，.,Pm是m种性质，A,是S中具有性质P,的元素构成的子集，1,2.……,m.则S中不具有性质Pi,P2，.,Pm的元素数为AnAn...nAmIm=ISI-ZIA, I+ ZIA, nA,I-ZIA,nA,AI+..i=11<i<j≤m1<i<j<k≤m+(-1)mA,0A, ...0Am l

包含排斥原理（容斥原理） 定理 设 S 为有穷集，P1 , P2 , ., Pm 是 m 种性质， Ai 是 S 中具有性质 Pi 的元素构成的子集，i=1, 2, ., m.则 S 中不具有性质 P1 , P2 , ., Pm 的元素数为 ( 1) | . | | | | | | | | | . | . | 1 2 1 1 1 1 2 m m i j k m i j k m i i j m i i j m A A A S A A A A A A A A A + −    = − +  −   +       =       

证明证明要点：任何元素x，如果不具有任何性质则对等式右边计数贡献为1，否则为0证设x不具有性质Pi,P2，…，Pmx &Ai,i=1, 2, ... , mx @A;A;,1≤i<j≤mx AinA,N...NAmx对右边计数贡献为1-0+0-0+...+(-1)m.0=1

证明 证 设 x不具有性质 P1 , P2 , . , Pm , x Ai , i = 1, 2, . , m x Ai  Aj , 1 i < j  m . x A1  A2 . Am , x 对右边计数贡献为 1 − 0 + 0 − 0 + . + (−1)m · 0 = 1 证明要点：任何元素 x，如果不具有任何性质， 则对等式右边计数贡献为１，否则为０

证明 (续)设x具有 n条性质，1≤n≤mx对ISI贡献为1C,x对ZIA4,贡献为.C,x 对ZIA,nA,I贡献为1i<jSmx 对IAiA2. Aml贡献为cmx对右边计数贡献为1-C, +C, -..+(-1)"C" -Zc, - 0i=0

证明（续） = m i Ai 1 | |      i j m Ai Aj 1 | | 1 Cn 2 Cn m Cn 1 . ( 1) 0 0 1 2 − + − + − =  = = n i i n m n m Cn Cn C C 设 x具有 n 条性质，1nm x 对 |S| 贡献为 1 x 对 贡献为 x 对 贡献为 . x 对 | A1  A2  .  Am| 贡献为 x 对右边计数贡献为

推论S中至少具有一条性质的元素数为IA, UA, U..UAm Im=ZIA,I- ZIA, nA,I+ZIA, nA, nAr I+.i=11<i<j≤m1≤i<j<k≤m+(-1)m-1 I A A, D...nAm I证明 IA, UA, U...UAmI=ISI-IA, UA, U...UAm=ISI-IA DA,D...DAm将定理 1代入即可

( 1) | . | | | | | | | . | . | 1 2 1 1 1 1 1 2 m m i j k m i j k m i i j m i i j m A A A A A A A A A A A A + −    = −  +   +    − =           S中至少具有一条性质的元素数为 证明 | | | . | | | | . | | . | 1 2 1 2 1 2 m m m S A A A S A A A A A A = −    = −       将定理 1 代入即可 推论

假设某班有20名学生，其中有10人英语成绩为优，有8人数学成绩为优，又知有6人英语和数学成绩都为优。问两门课都不为优的学生有几名？解设英语成绩是优的学生组成的集合是A，数学成绩是优的学生组成的集合是B，因此两门课成绩都是优的学生组成的集合是AB。由题意可知IA/=10[ANB|=6由包含排斥原理可[B|=8得:[AUB|=|A|+|B|-|AnB|=10+8-6=12所以，两门课都不是优的学生数为：20-[AUB|=8

◼ 假设某班有20名学生，其中有10人英语成绩 为优，有8人数学成绩为优，又知有6人英语 和数学成绩都为优。问两门课都不为优的学 生有几名？ ◼ 解 设英语成绩是优的学生组成的集合是A，数学 成绩是优的学生组成的集合是B，因此两门课成绩 都是优的学生组成的集合是A∩B。由题意可知 |A|＝10 |B|＝8 |A∩B|＝6由包含排斥原理可 得： |A∪B|＝|A|+|B|-|A∩B| ＝10+8-6 = 12 所以，两门课都不是优的学生数为：20-|A∪B|＝8