容斥原理

　　在计数时,为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是：先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理.

　　容斥原理（1）

　　如果被计数的事物有a、b两类,那么,a类或b类元素个数=a类元素个数+

　　b类元素个数—既是a类又是b类的元素个数.

　　例1

　　一次期末考试,某班有15人数学得满分,有12人语文得满分,并且有4人语、数都是满分,那么这个班至少有一门得满分的同学有多少人?

　　分析：依题意,被计数的事物有语、数得满分两类,“数学得满分”称为“a类元素”,“语文得满分”称为“b类元素”,“语、数都是满分”称为“既是a类又是b类的元素”,“至少有一门得满分的同学”称为“a类或b类元素个数”的总和.

　　试一试：某班学生每人家里至少有空调和电脑两种电器中的一种,已知家中有空调的有41人,有电脑的有34人,二者都有的有27人,这个班有学生多少人?（并说一说你的想法.）

　　容斥原理（2）

　　如果被计数的事物有a、b、c三类,那么,a类或b类或c类元素个数=a类元素个数+

　　b类元素个数+c类元素个数—既是a类又是b类的元素个数—既是a类又是c类的元素个数—既是b类又是c类的元素个数+既是a类又是b类而且是c类的元素个数.

　　例2某校六（1）班有学生54人,每人在暑假里都参加体育训练队,其中参加足球队的有25人,参加排球队的有22人,参加游泳队的有34人,足球、排球都参加的有12人,足球、游泳都参加的有18人,排球、游泳都参加的有14人,问：三项都参加的有多少人?

　　分析：仿照例1的分析,你能先说一说吗?

　　例3在1到1000的自然数中,能被3或5整除的数共有多少个?不能被3或5整除的数共有多少个?

　　分析：显然,这是一个重复计数问题（当然,如果不怕麻烦你可以分别去数3的倍数,5的倍数）.我们可以把“能被3或5整除的数”分别看成a类元素和b类元素,能“同时被3或5整除的数（15的倍数）”就是被重复计算的数,即“既是a类又是b类的元素”.求的是“a类或b类元素个数”.现在我们还不能直接计算,必须先求出所需条件.1000÷3=333……1,能被3整除的数有333个（想一想,这是为什么?）同理,可以求出其他的条件.

　　例4分母是1001的最简分数一共有多少个?

　　分析：这一题实际上就是找分子中不能整除1001的数.由于1001=7×11×13,所以就是找不能被7,11,13整除的数.

　　例5

　　某个班的全体学生在进行了短跑、游泳、投掷三个项目的测试后,有4名学生在这三个项目上都没有达到优秀,其余每人至少有一项达到了优秀,达到了优秀的这部分学生情况如下表：

　　短跑游泳投掷短跑、游泳短跑、投掷游泳、投掷短路、游泳、投掷

　　1718156652

　　求这个班的学生共有多少人?

　　分析：这个班的学生数,应包括达到优秀和没有达到优秀的.

　　试一试：一个班有42人,参加合唱队的有30人,参加美术组的有25人,有5人什么都没有参加,求两种都参加的有多少人?

　　例6

　　在一根长的木棍上有三种刻度线,第一种刻度线将木棍分成10等份,第二种将木棍分成12等份,第三种将木棍分成15等份.如果沿每条刻度线将木棍锯断,木棍总共被锯成多少段?

　　分析：很显然,要计算木棍被锯成多少段,只需要计算出木棍上共有多少条不同的刻度线,在此基础上加1就是段数了.

　　若按将木棍分成10等份的刻度线锯开,木棍有9条刻度线.在此木棍上加上将木棍分成12等份的11条刻度线,显然刻度线有重复的,如5/10和6/12都是1/2.同样再加上将木棍分成15等份的刻度线,也是如此.所以,我们应该按容斥原理的方法来解决此问题.用容斥原理的那一个呢?想一想,被计数的事物有那几类?每一类的元素个数是多少?

　　德摩根定律-表达形式形式逻辑中此定律表达形式：

　　neg(PwedgeQ)=(negP)vee(negQ)

　　neg(PveeQ)=(negP)wedge(negQ)

　　在集合论中：

　　(AcapB)^C=A^CcupB^C

　　(AcupB)^C=A^CcapB^C.

　　在经典命题逻辑的外延中,此二元性依然有效(即对于任意的逻辑运算符,我们都能找他它的对偶),由于存在于调节否定关系的恒等式中,人们总会引入作为一个算符的德·摩根对偶的另一个算符.这导致了基于传统逻辑的逻辑学的一个重要性质,即否定范式的存在性：任何公式等价于另外一个公式,其中否定仅出现在作用于公式中非逻辑的原子时.否定常型的存在推进了许多应用,例如在数字电路设计中该性质用于操纵逻辑门,以及在形式逻辑中该性质是寻找一个公式的合取范式和析取范式的必要条件；电脑程序员们则用它们将一个类似于IF...AND(...OR...)THEN...这样的复杂语句转变为其对等形式；它们也同样经常用于初等概率论中的计算.

　　我们将基于基本命题p,q的任意命题算符P(p,q,...)的对偶定义为：

　　negmbox^d(negp,negq,...).

　　该概念可以推广到逻辑量词上,例如全称量词和存在量词互为对偶：

　　forallx,P(x)equivnegexistsx,negP(x),

　　“对所有x,P(x)皆成立”等价于“不存在x,使P(x)不成立”；

　　existsx,P(x)equivnegforallx,negP(x).

　　“存在x,使P(x)成立”等价于“并非对所有x,P(x)都不成立”.

　　为对德·摩根定律叙述这些量词的二元性,设置一个在其域D中具有少量元素的模型,例如

　　D={a,b,c}.

　　则

　　forallx,P(x)equivP(a)wedgeP(b)wedgeP(c)

　　“对所有x,P(x)成立”等价于“P(a)成立”且“P(b)成立”且“P(c)成立”

　　以及

　　existsx,P(x)equivP(a)veeP(b)veeP(c).

　　“存在x,使P(x)成立”等价于“P(a)成立”或“P(b)成立”或“P(c)成立”

　　但,应用德·摩根定律,

　　P(a)wedgeP(b)wedgeP(c)equivneg(ne