容斥原理与逻辑运算Rongchi yuanli yu luo jiyunsuan

集合可以用集合内的所有元素共同具有的性质来描述，集合A的所有具有性质p的元素构成的子集合可以记作{X∈A|x具有性质p}。例如，设N表示自然数集合，性质p为小于100，具有性质P的元素所构成的子集 {X∈N|x<100} = {1, 2, …，99}。因为元素的性质是用一个命题来叙述的，集合的运算与逻辑运算之间就有了密不可分的关联， 这种关联可以表述如下：设S= {X∈A|x具有性质P},T={X∈A|x具有性质Q}，则S∪T={X∈A|x具有性质P或具有性质Q},S∩T={X∈A|x具有性质P且具有性质Q},A\\S={X∈A|x不具有性质P}。这里A\\S表示S在A中的补集， 即A中不含于S的所有元素构成的子集。上述的对应关系告诉我们，集合的并、交、补运算分别对应于逻辑命题的“或”、“与”，“非”运算。由于有这样的对应关系，容斥原理也可以通过逻辑运算的方式表述：假定所考虑的对象总数为m, P₁、P₂, …，P_n为n个性质， 那么至少具有n个性质之一的对象数目等于-+…+(-1)^n-1k₁₂ …n这里∑为求和符号， 例如＝k₁₂+k₁₃+…+k₁n++k₂₃+…+k_2n+…+k(_n-₁)n,k_i表示具有性质P_i的对象个数，k_ij表示具有性质p_i且具有性质P1的对象个数，而k₁₂…n表示具有所有n个性质P₁、…，P_n的对象个数。
我们来看下面的例子： 设有五位同学每人准备一张贺年卡互赠，他们先把所有五张贺卡放入一个盒子，然后每人从中摸一张， 问每人拿到的都不是自己准备的贺卡的不同取法有多少种。在这一问题中我们讨论的对象是取法，性质P₁，…，P₅分别表示学生1, …，学生5取到了自己的贺卡。取法总数共有5×4×3×2×1=120种， 具有性质P₁的取法有4×3×2×1=24种，具有性质P₁与P₂的取法有3×2×1种，具有性质P₁、P₂与P₃的取法有2×1=2种，具有4个以上性质的取法只有1种，根据容斥原理，问题的解可由下式求出：120-5×24+10×6-10×2+5×1-1=44，式中第一项为取法总数，第二项中因子24表示满足5个性质中某一个时的取法总数，因有5个性质故乘以5，第3项中因子6表示满足5个性质中某两个时的取法数目， 由于从5个性质中取两个的组合数是10, 故乘以10，以下各项可类似地分析。因此，每人取到的都不是自己的贺卡的不同取法总数为44种。
应用容斥原理分析和解决问题， 首先要弄清所论对象，其次须注意分析各条件之间的逻辑关系，正确地理解和掌握集合的并、交、补运算与逻辑命题的“与”、“或”、“非”运算及它们之间的对应关系。