包含與排除原理及應(yīng)用

【摘要】從集合的角度，引入一個(gè)有限或無(wú)窮的集合U及U的子集A，子集A的特征函數(shù)A（x）根據(jù)U中變?cè)獂屬于或不屬于A，定義A（x）=1或0，在此基礎(chǔ)上證明了包含與排除原理的兩個(gè)定理，并且通過(guò)實(shí)例對(duì)這兩個(gè)原理進(jìn)行了應(yīng)用.

【關(guān)鍵詞】集合；子集；特征函數(shù)；包含與排除

為了證明本原理的定理，我們事先要做一些引導(dǎo)，我們討論一個(gè)有限或無(wú)窮的集合U.U的子集A的特征函數(shù)A（x）是U中變?cè)獂的函數(shù).根據(jù)x屬于或不屬于A定義

A（x）=1或0.

U的特征函數(shù)為常數(shù)1（因此U也表示單位數(shù)），空集的特征函數(shù)是常數(shù)0，U的子集A，B，C，…的特征函數(shù)分別用A（x），B（x），C（x），…表示，如果不致發(fā)生誤解的話(huà)，也可以把A（x），B（x），C（x），…簡(jiǎn)寫(xiě)成A，B，C，…即用同樣的符號(hào)表示U的子集和它的特征函數(shù).

A是B的一個(gè)子集的充要條件是對(duì)所有x成立A（x）≤B（x）或簡(jiǎn)寫(xiě)成A≤B.

如果U是一個(gè)有限集，那么子集A中元素的個(gè)數(shù)是∑A（x），其中和式取遍U中所有元素.

定理1 設(shè)有N個(gè)對(duì)象，令Nα，Nβ，…，Nμ，Nλ分別表示這些對(duì)象中具有某種性質(zhì)α，β，…，μ和λ的對(duì)象的個(gè)數(shù).類(lèi)似的，令Nαβ，Nαγ，…，Nαβλ，…，Nαβγ…μλ分別表示同時(shí)具有性質(zhì)α和β，α和γ，…，α，β和γ，…，α，β，γ，…，μ和λ的對(duì)象的個(gè)數(shù).那么不具有性質(zhì)α，β，γ，…，μ，λ中任一性質(zhì)的對(duì)象個(gè)數(shù)N0等于

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

證明 設(shè)A，B，C，…分別為具有性質(zhì)α，β，γ…的對(duì)象所組成的子集，則A，B，C，…的余集的交集表示不具有性質(zhì)α，β，γ…中的任何一個(gè)性質(zhì)的對(duì)象所組成的集合.我們需要找出它所含元素的個(gè)數(shù)，令N0是它所含元素的個(gè)數(shù)，N是對(duì)象的個(gè)數(shù)，其他Nα，Nβ，…的含義同定理.由上可得A，B，C，…的余集的交集的特征函數(shù)是：

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

所以它的元素個(gè)數(shù)N0等于

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

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

即求出所需求元素的個(gè)數(shù)，定理即證.

定理2 假定有N個(gè)對(duì)象，像在定理1中那樣，它們能夠具有性質(zhì)α，β，…，μ，λ，給每個(gè)對(duì)象帶上一個(gè)權(quán)數(shù).用Wα表示具有性質(zhì)α的所有對(duì)象所帶的權(quán)數(shù)總值（那些對(duì)象所帶權(quán)數(shù)數(shù)值的和），用Wβ表示具有性質(zhì)β的所有對(duì)象所帶的權(quán)數(shù)總值等等.類(lèi)似的，令Wαβ，Wαγ，…，Wαβλ，…，Wαβγ…μλ分別表示同時(shí)具有性質(zhì)α和β，α和γ，…，α，β和γ，…，α，β，γ，…，μ和λ的對(duì)象所帶權(quán)數(shù)總值.如果W是所有對(duì)象所帶的權(quán)數(shù)總值，那么不具有性質(zhì)α，β，γ，…，μ，λ中任一性質(zhì)的那些對(duì)象所帶的權(quán)數(shù)總值等于W-Wα-Wβ-Wγ-…-Wμ-Wλ+Wαβ+Wαγ+…+ Wμλ- Wαβλ-…±Wαβγ…μλ.

證明 設(shè)A，B，C，…分別為具有性質(zhì)α，β，γ，…的對(duì)象所組成的子集，則不具有性質(zhì)α，β，γ，…中的任何一個(gè)性質(zhì)的對(duì)象所組成的集合是A，B，C，…的余集的交集，則有∑xA是具有性質(zhì)α的所有對(duì)象的權(quán)數(shù)總值，類(lèi)似的∑xB表示具有性質(zhì)β的所有對(duì)象的權(quán)數(shù)總值……我們需要找出A，B，C，…的余集的交集中對(duì)象所帶的權(quán)數(shù)總值，由此可得，它的特征函數(shù)是：

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

那么，不具有性質(zhì)α，β，γ，…中任一性質(zhì)的那些對(duì)象所帶的權(quán)數(shù)總值W0等于

a+b+c+…+k+l-min（a，b）-min（a，c）-…-min（k，l）+min（a，b，c）+…±m(xù)in（a，b，c，…，k，l）.

證 令N=max（a，b，c，…，k，l）.當(dāng)N=0時(shí)，結(jié)論顯然成立.當(dāng)N>0時(shí)，將數(shù)1，2，…，N看作對(duì)象，并對(duì)它們應(yīng)用定理1.如果一個(gè)數(shù)≤a，則稱(chēng)該數(shù)具有性質(zhì)α，若≤b，則稱(chēng)具有性質(zhì)β，等等，既沒(méi)有性質(zhì)α也沒(méi)有性質(zhì)β…的對(duì)象的個(gè)數(shù)顯然等于0.于是

N-[a+b+c+…+k+l-min（a，b）-min（a，c）-…-min（k，l）+min（a，b，c）+…±m(xù)in（a，b，c，…，k，l）]=0，即證.

在這里我們從集合的角度，證明了包含與排除原理的兩個(gè)定理，其中定理2是定理1的推廣，而定理1是定理2的特殊情況.并通過(guò)例題對(duì)所證明的定理進(jìn)行了應(yīng)用，在實(shí)際的運(yùn)用過(guò)程中通常應(yīng)用定理2即可.

【參考文獻(xiàn)】

[1]劉玉翹，陳漢卿.集合初步知識(shí)[M].天津：天津科學(xué)技術(shù)出版社，1980.

[2]同濟(jì)大學(xué)數(shù)學(xué)系.高等數(shù)學(xué).高等教育出版社，2007.

[3]潘東，金以慧.可拓控制的探索與研究[J].控制理論與應(yīng)用，1996，13（3）：305-311.

[4]崔明榮.現(xiàn)代數(shù)學(xué)的集合論思想[J].延安教育學(xué)院學(xué)報(bào)，1998（1）.