包含与排除原理及应用

【摘要】从集合的角度，引入一个有限或无穷的集合U及U的子集A，子集A的特征函数A（x）根据U中变元x属于或不属于A，定义A（x）=1或0，在此基础上证明了包含与排除原理的两个定理，并且通过实例对这两个原理进行了应用.

【关键词】集合；子集；特征函数；包含与排除

为了证明本原理的定理，我们事先要做一些引导，我们讨论一个有限或无穷的集合U.U的子集A的特征函数A（x）是U中变元x的函数.根据x属于或不属于A定义

A（x）=1或0.

U的特征函数为常数1（因此U也表示单位数），空集的特征函数是常数0，U的子集A，B，C，…的特征函数分别用A（x），B（x），C（x），…表示，如果不致发生误解的话，也可以把A（x），B（x），C（x），…简写成A，B，C，…即用同样的符号表示U的子集和它的特征函数.

A是B的一个子集的充要条件是对所有x成立A（x）≤B（x）或简写成A≤B.

如果U是一个有限集，那么子集A中元素的个数是∑A（x），其中和式取遍U中所有元素.

定理1 设有N个对象，令Nα，Nβ，…，Nμ，Nλ分别表示这些对象中具有某种性质α，β，…，μ和λ的对象的个数.类似的，令Nαβ，Nαγ，…，Nαβλ，…，Nαβγ…μλ分别表示同时具有性质α和β，α和γ，…，α，β和γ，…，α，β，γ，…，μ和λ的对象的个数.那么不具有性质α，β，γ，…，μ，λ中任一性质的对象个数N0等于

N-Nα-Nβ-Nγ-…-Nμ-Nλ+Nαβ+Nαγ+…+ Nμλ-Nαβλ-…±Nαβγ…μλ.

证明 设A，B，C，…分别为具有性质α，β，γ…的对象所组成的子集，则A，B，C，…的余集的交集表示不具有性质α，β，γ…中的任何一个性质的对象所组成的集合.我们需要找出它所含元素的个数，令N0是它所含元素的个数，N是对象的个数，其他Nα，Nβ，…的含义同定理.由上可得A，B，C，…的余集的交集的特征函数是：

（1-A）（1-B）（1-C）…=1-A-B-C-…+AB+AC+BC+…-ABC-…

所以它的元素个数N0等于

∑[（1-A）（1-B）（1-C）…]= ∑1-∑A-∑B-∑C-…+∑（AB）+∑（AC）+∑（BC）+…-

∑（ABC）-…= N-Nα-Nβ- Nγ-…+Nαβ+Nαγ+ Nβγ-…-Nαβγ-….

即求出所需求元素的个数，定理即证.

定理2 假定有N个对象，像在定理1中那样，它们能够具有性质α，β，…，μ，λ，给每个对象带上一个权数.用Wα表示具有性质α的所有对象所带的权数总值（那些对象所带权数数值的和），用Wβ表示具有性质β的所有对象所带的权数总值等等.类似的，令Wαβ，Wαγ，…，Wαβλ，…，Wαβγ…μλ分别表示同时具有性质α和β，α和γ，…，α，β和γ，…，α，β，γ，…，μ和λ的对象所带权数总值.如果W是所有对象所带的权数总值，那么不具有性质α，β，γ，…，μ，λ中任一性质的那些对象所带的权数总值等于W-Wα-Wβ-Wγ-…-Wμ-Wλ+Wαβ+Wαγ+…+ Wμλ- Wαβλ-…±Wαβγ…μλ.

证明 设A，B，C，…分别为具有性质α，β，γ，…的对象所组成的子集，则不具有性质α，β，γ，…中的任何一个性质的对象所组成的集合是A，B，C，…的余集的交集，则有∑xA是具有性质α的所有对象的权数总值，类似的∑xB表示具有性质β的所有对象的权数总值……我们需要找出A，B，C，…的余集的交集中对象所带的权数总值，由此可得，它的特征函数是：

（1-A）（1-B）（1-C）…=1-A-B-C-…+AB+AC+BC+…-ABC-….

那么，不具有性质α，β，γ，…中任一性质的那些对象所带的权数总值W0等于

a+b+c+…+k+l-min（a，b）-min（a，c）-…-min（k，l）+min（a，b，c）+…±min（a，b，c，…，k，l）.

证 令N=max（a，b，c，…，k，l）.当N=0时，结论显然成立.当N>0时，将数1，2，…，N看作对象，并对它们应用定理1.如果一个数≤a，则称该数具有性质α，若≤b，则称具有性质β，等等，既没有性质α也没有性质β…的对象的个数显然等于0.于是

N-[a+b+c+…+k+l-min（a，b）-min（a，c）-…-min（k，l）+min（a，b，c）+…±min（a，b，c，…，k，l）]=0，即证.

在这里我们从集合的角度，证明了包含与排除原理的两个定理，其中定理2是定理1的推广，而定理1是定理2的特殊情况.并通过例题对所证明的定理进行了应用，在实际的运用过程中通常应用定理2即可.

【参考文献】

[1]刘玉翘，陈汉卿.集合初步知识[M].天津：天津科学技术出版社，1980.

[2]同济大学数学系.高等数学.高等教育出版社，2007.

[3]潘东，金以慧.可拓控制的探索与研究[J].控制理论与应用，1996，13（3）：305-311.

[4]崔明荣.现代数学的集合论思想[J].延安教育学院学报，1998（1）.