例 例：A⊕B=A⊕C→B=C 证明Vx∈B希望证明x∈C。分两种情况： (1)X∈A。所以有x∈A⌒B,所以XEA⊕B。 由已知而得xEA⊕C。由此有x∈C(否则若xC,得x∈A C→x∈A⊕C,矛盾)。 ∴.BsC (2)XEA。所以X∈B-A→X∈A⊕B,由已知A⊕B=A⊕C,所以 X∈A⊕C→X∈A-C或X∈C-A 因xEA,∴.XEA-C,于是X∈C-A→x∈C。.BcC 同理，x∈C,类似可证x∈B,.CcB 因此B=C。 2025/5/13 计算机与信息工程学院 16
2025/5/13 计算机与信息工程学院 16 例 例: AB= AC B=C 证明 xB希望证明xC。分两种情况： (1) xA。所以有xAB，所以 xAB。 由已知而得xAC。由此有xC (否则若xC,得xACxAC，矛盾)。 BC (2) xA。所以xB-AxAB，由已知AB=AC,所以 xAC xA-C或xC-A 因xA,xA-C,于是xC-AxC。BC 同理，xC，类似可证xB，CB 因此B=C
例 已知AUB=AUC,AOB=AOC,求证B=C。 证明B=B∩(AUB) (吸收律) B∩(AUC) (替换) (B∩A)U(BAC) (分配律) (AOC(BOC) (替换) (AUB)⌒C (分配律) (AUC)∩C (替换) (吸收律) 2025/5/13 计算机与信息工程学院 17
2025/5/13 计算机与信息工程学院 17 例 已知AB=AC，AB=AC，求证B=C。 证明 B= B(AB) (吸收律) = B(AC) (替换) = (BA)(BC) (分配律) = (AC)(BC) (替换) = (AB)C (分配律) = (AC)C (替换) = C (吸收律)
容斥原理 (principle of inclusion-exclusion) 设A1,A2,.,An是n个集合，则 心4=立4-n4+g4n4n .+(-1)”A∩A,∩.∩An 称为包含排斥原理，简称容斥原理。 2025/5/13 计算机与信息工程学院 18
2025/5/13 计算机与信息工程学院 18 设A1，A2，.，An是n个集合，则 容斥原理 (principle of inclusion-exclusion) n n i j k i j k i j i j n i i n i i A A A A A A A A A A 1 2 1 1 1 ( 1) − = = + − = − + 称为包含排斥原理，简称容斥原理
例 对100名技术人员的调查结果表明，有32人学过日 语，20人学过法语，45人学过英语。又其中有15人既 学过日语又学过英语，7人既学过日语又学过法语，0 人既学过法语又学过英语。30人没学过这3门语言的任 何一种。 1)3种语言都学过的人数为多少？ 2)只学过日语，只学过法语，只学过英语的人数各为多 少？ 3)至少学过以上3种语言中的两种语言的人数为多少？ 4)只学过日语和法语，只学过日语和英语，只学过法语 和英语的人数各为多少？ 2025/5/13 计算机与信息工程学院 19
2025/5/13 计算机与信息工程学院 19 例 对100名技术人员的调查结果表明，有32人学过日 语，20人学过法语，45人学过英语。又其中有15人既 学过日语又学过英语，7人既学过日语又学过法语，10 人既学过法语又学过英语。30人没学过这3门语言的任 何一种。 1)3种语言都学过的人数为多少？ 2)只学过日语，只学过法语，只学过英语的人数各为多 少？ 3)至少学过以上3种语言中的两种语言的人数为多少？ 4)只学过日语和法语，只学过日语和英语，只学过法语 和英语的人数各为多少？
解设A={化学过日语，B=学过法语，C={化学过英语 由题目中数据可知：A=32,B=20,C=45,AnB=7,AnC=I5, BnC=10,AUBUC=100-30=70 ①)由包含排拆原理的第一式可知 AUBUC=(A+B+C)-(AnB+AnC+BnC)+AnBnc 即 70=32+20+4-(7+15+10)+AnBoC 于是，3种语言都学过的人数为 4oBoC=70-97+32=5 2025/5/13 计算机与信息工程学院 20
2025/5/13 计算机与信息工程学院 20