德摩根率的证明

德摩根法则

非(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)

所以就证明了第一个，

第二个根据对偶同理可得

这里还有另一种证法

http://www.hi-pda.com/forum/viewthread.php?tid=267943