说明

该笔记写给自己之后复习理解，文中用词不一定很标准，很多东西是我想到了就写上去的，意会即可。

德摩根定律

简介

简而言之，该定律描述了命题逻辑中的两个关系：
若设现有两个命题A和B，那么必然有

非（A 且 B）=（非 A）或（非 B）非（A 或 B）=（非 A）且（非 B）如今天我要出门买水果，设此时有两个命题A：买西瓜B：买苹果如果应用德摩根定律的引理1，此时必然有非（买西瓜 且 买苹果）=（非 买西瓜）或（非 买苹果）翻译一下上面的等式，等式左边的命题表示：“不会既买西瓜也买苹果”，即非（买西瓜 且 买苹果）= 西瓜和苹果中至少有一个不买同理，等式右边的命题表示：要么“不买西瓜”，要么“不买苹果”（当然，逻辑关系中的或可以表达两者均成立，即“西瓜苹果均不买”），那么容易理解，这句话的意思也同样表示“西瓜和苹果中至少有一个不买”，那么显然，德摩根定律所表述的等式左右两端其实表达的是同一个意思。

对引理2也可以用同样的方式进行理解，此处不再赘述，接下来就用数学推导不那么严格（?）地证明和理解一下一般形式下的德摩根定律。
首先，列出德摩根定律两个引理的一般形式，此处的推导和符号标记都参考了这篇文献。

引理1

$$(\bigcap _{i=1}^n{S}_i{)}^c=\bigcup _{i=1}^n{S}_n^c$$

引理2

$$(\bigcup _{i=1}^n{S}_i{)}^c=\bigcap _{i=1}^n{S}_n^c$$

式中，$S_i$ 表示第 $i$ 个集合，$n$ 表示集合的总个数，$c$ 代表补集，此处也可以理解为“非”。

证明

证明的思路

我们知道，两个集合相等的充分必要条件是两个集合互为子集，即

$$A=B\rightleftharpoons (A\subset B)\cap (B\subset A)$$

基于这个前提，我们只需要证明摩根定律中等式两端的对应集合互为子集即能证得德摩根定律，明白了这一点，我们就可以具体推导并解释德摩根定律的证明过程。

引理1的证明过程

在这里重申一下引理1：

$$(\bigcap _{i=1}^n{S}_i{)}^c=\bigcup _{i=1}^n{S}_n^c$$

①证明等式左边集合是等式右边集合的子集

首先看引理1的等式左边的表达式，若以$x$ 来表示集合中的任意元素，可以知道以下命题

$$x\in (\bigcap _{i=1}^n{S}_i{)}^c=x\notin \bigcap _{i=1}^n{S}_i$$

这是显然的，因为一个集合和其补集是对立的，即一个集合和它的补集之并为全集，两者之交为空集。那么 $x$ 若属于一个集合 $A$ 的补集，那么它必然不属于集合 $A$。
然后我们仔细解读一下上式中，等式右边表达式的含义，它的意思是说（一定要反复理解这个地方，这是推导问题的关键），$x$ 不会同时属于所有 $S_i$ 集合，也就是说，$x$ 至少会不属于 $S_i$ 中的某一个集合，翻译成表达式的形式即

$$\exists i\in \{1,2,...,n\},x\notin S_i$$

用中文念一下上面的表达式：“至少存在一个集合 $S_i$，使得 $x$ 不属于它，其中 $i$ 的取值范围是从1到 $n$”
而我们已经解释过，一个元素 $x$ 不属于一个集合 $A$ ，等价于这个元素 $x$ 属于集合 $A$ 的补集，那么前式可以进一步写为

$$\exists i\in \{1,2,...,n\},x\in S_i^c$$

用中文念一下上面的表达式：“至少存在一个集合 $S_i^c$，使得 $x$ 属于它”，此时我们需要重点理解一下“至少存在”这个概念，而实际上，上述命题就表示“$x$ 属于任意一个或多个 $S_i^c$ 集合”，因为“$x$ 至少属于一个集合 $S_i^c$”呀，那么用表达式写出这个命题即有

$$x\in \bigcup _{i=1}^n{S}_i^c$$

上式就表示，$x$ 可能属于 $S_1^c$，或者也可能属于 $S_2^c$，…，当然，$x$ 也可能同时属于多个 $S_i^c$，然后我们就发现，上式的集合实际上就是德摩根定律引理1中，等式右边的表达式，所以可以推得

$$(\bigcap _{i=1}^n{S}_i{)}^c\subset \bigcup _{i=1}^n{S}_n^c$$

这里也稍作解释，如果由 $x\in$ $A$ 可以推出 $x\in$ $B$ ，那么集合 $A$ 一定是集合 $B$ 的子集。所有包含集合内容的数学课都会先讲这个内容，这里就不赘述了。

②证明等式右边集合是等式左边集合的子集

写到这里，我们不妨引出一个规律：

$$x\in \bigcup _{i=1}^n{S}_{i}equals\exists i\in \{1,2,...,n\},x\in S_i$$

这个规律是显然的，它只是对同一个命题的不同表达方法，同样的规律还有

$$x\in \bigcap _{i=1}^n{S}_{i}equals\forall i\in \{1,2,...,n\},x\in S_i$$

再次重申引理1

$$(\bigcap _{i=1}^n{S}_i{)}^c=\bigcup _{i=1}^n{S}_n^c$$

此时看到等式右边的表达式，直接利用我们刚刚得到的规律，可以推得

$$x\in \bigcup _{i=1}^n{S}_n^c=\exists i\in \{1,2,...,n\},x\in S_i^c$$

去掉等式右边表达式的补集关系，将属于符号改为不属于得到（前面已经解释过这样做的依据）

$$\exists i\in \{1,2,...,n\},x\notin S_i$$

上式表达的意思是“ $x$ 至少不属于 $S_i$ 中的某一个”，那么容易推知“$x$ 必然不同时属于所有 $S_i$”，即

$$x\notin \bigcap _{i=1}^n{S}_i$$

进一步推知

$$x\in (\bigcap _{i=1}^n{S}_i{)}^c$$

上式中的集合就是引理1中左边的表达式，那么得到

$$\bigcup _{i=1}^n{S}_n^c\subset (\bigcap _{i=1}^n{S}_i{)}^c$$

此时，已经证到了引理等式两端的集合互为子集，即证到德摩根定律的引理1，即
$$\bigcup _{i=1}^n{S}_n^c=(\bigcap _{i=1}^n{S}_i{)}^c$$

引理2的证明过程

写得好麻烦啊哈哈哈哈，不想写了，直接去看原文吧，虽然没有解释，但是结合引理1的证明过程应该很容易理解。

参考文章

1. https://www.cnblogs.com/taoqc/p/16253507.html