容斥原理,什么是摩根法则?什么是容斥原理?

  Q1:是摩根法则?
德摩根法则
非(p 且 q)=(非 p)或(非 q)
非(p 或 q)=(非 p)且(非 q)
首先要明白：全称量词和存在量词互为对偶：
“对所有x,P(x)皆成立”等价于“不存在x,使P(x)不成立”容斥；
“存在x,使P(x)成立”等价于“并非对所有x,P(x)都不成立”。
  
非(p 且 q)=(非 p)或(非 q)
左边式子的意思就是,不存在x,使得p（x）和q（x）同时成立,根据全称量词和存在量词互为对偶：
得到对任意x,p（x）不成立或者q（x）不成立,
写成集合语言就是非(p 且 q)=(非 p)或(非 q)
所以就证明了第一个,
第二个根据对偶同理可得
Q2:什么是容斥原理?
在计数时,必须注意无一重复,无一遗漏。
  为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是：先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。

容斥原理就是：在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。
原理是：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终会发现至少可以找到一个抽屉里面至少放两个苹果。这一现象就是抽屉原理。