说明
该笔记写给自己之后复习理解,文中用词不一定很标准,很多东西是我想到了就写上去的,意会即可。
德摩根定律
简介
简而言之,该定律描述了命题逻辑中的两个关系:
若设现有两个命题A和B,那么必然有
对引理2也可以用同样的方式进行理解,此处不再赘述,接下来就用数学推导不那么严格(😀)地证明和理解一下一般形式下的德摩根定律。
首先,列出德摩根定律两个引理的一般形式,此处的推导和符号标记都参考了这篇文献。
引理1
( ⋂ i = 1 n S i ) c = ⋃ i = 1 n S n c \quad (\bigcap_{i=1}^{n} S_i)^c = \bigcup_{i=1}^{n}S_n^c (i=1⋂nSi)c=i=1⋃nSnc
引理2
( ⋃ i = 1 n S i ) c = ⋂ i = 1 n S n c \quad (\bigcup_{i=1}^{n} S_i)^c = \bigcap_{i=1}^{n}S_n^c (i=1⋃nSi)c=i=1⋂nSnc
式中, S i S_{i} Si 表示第 i i i 个集合, n n n 表示集合的总个数, c c c 代表补集,此处也可以理解为“非”。
证明
证明的思路
我们知道,两个集合相等的充分必要条件是两个集合互为子集,即
A = B ⇌ ( A ⊂ B ) ∩ ( B ⊂ A ) A=B \rightleftharpoons (A \subset B) \cap (B\subset A) A=B⇌(A⊂B)∩(B⊂A)
基于这个前提,我们只需要证明摩根定律中等式两端的对应集合互为子集即能证得德摩根定律,明白了这一点,我们就可以具体推导并解释德摩根定律的证明过程。
引理1的证明过程
在这里重申一下引理1:
( ⋂ i = 1 n S i ) c = ⋃ i = 1 n S n c \quad (\bigcap_{i=1}^{n} S_i)^c = \bigcup_{i=1}^{n}S_n^c (i=1⋂nSi)c=i=1⋃nSnc
①证明等式左边集合是等式右边集合的子集
首先看引理1的等式左边的表达式,若以 x x x 来表示集合中的任意元素,可以知道以下命题
x ∈ ( ⋂ i = 1 n S i ) c = x ∉ ⋂ i = 1 n S i x\in (\bigcap_{i=1}^{n} S_i)^c = x\notin \bigcap_{i=1}^{n} S_i x∈(i=1⋂nSi)c=x∈/i=1⋂nSi
这是显然的,因为一个集合和其补集是对立的,即一个集合和它的补集之并为全集,两者之交为空集。那么
x
x
x 若属于一个集合
A
A
A 的补集,那么它必然不属于集合
A
A
A。
然后我们仔细解读一下上式中,等式右边表达式的含义,它的意思是说(一定要反复理解这个地方,这是推导问题的关键),
x
x
x 不会同时属于所有
S
i
S_{i}
Si 集合,也就是说,
x
x
x 至少会不属于
S
i
S_{i}
Si 中的某一个集合,翻译成表达式的形式即
∃ i ∈ { 1 , 2 , . . . , n } , x ∉ S i \exists i \in \{1,2, ..., n\}, x \notin S_i ∃i∈{1,2,...,n},x∈/Si
用中文念一下上面的表达式:“至少存在一个集合
S
i
S_i
Si,使得
x
x
x 不属于它,其中
i
i
i 的取值范围是从1到
n
n
n”
而我们已经解释过,一个元素
x
x
x 不属于一个集合
A
A
A ,等价于这个元素
x
x
x 属于集合
A
A
A 的补集,那么前式可以进一步写为
∃ i ∈ { 1 , 2 , . . . , n } , x ∈ S i c \exists i \in \{1,2, ..., n\}, x \in S_i^c ∃i∈{1,2,...,n},x∈Sic
用中文念一下上面的表达式:“至少存在一个集合 S i c S_i^c Sic,使得 x x x 属于它”,此时我们需要重点理解一下“至少存在”这个概念,而实际上,上述命题就表示“ x x x 属于任意一个或多个 S i c S_i^c Sic 集合”,因为“ x x x 至少属于一个集合 S i c S_i^c Sic”呀,那么用表达式写出这个命题即有
x ∈ ⋃ i = 1 n S i c x \in \bigcup_{i=1}^nS_i^c x∈i=1⋃nSic
上式就表示, x x x 可能属于 S 1 c S_1^c S1c,或者也可能属于 S 2 c S_2^c S2c,…,当然, x x x 也可能同时属于多个 S i c S_i^c Sic,然后我们就发现,上式的集合实际上就是德摩根定律引理1中,等式右边的表达式,所以可以推得
( ⋂ i = 1 n S i ) c ⊂ ⋃ i = 1 n S n c \quad (\bigcap_{i=1}^{n} S_i)^c \subset \bigcup_{i=1}^{n}S_n^c (i=1⋂nSi)c⊂i=1⋃nSnc
这里也稍作解释,如果由 x ∈ x \in x∈ A A A 可以推出 x ∈ x \in x∈ B B B ,那么集合 A A A 一定是集合 B B B 的子集。所有包含集合内容的数学课都会先讲这个内容,这里就不赘述了。
②证明等式右边集合是等式左边集合的子集
写到这里,我们不妨引出一个规律:
x ∈ ⋃ i = 1 n S i e q u a l s ∃ i ∈ { 1 , 2 , . . . , n } , x ∈ S i x \in \bigcup_{i=1}^nS_i \ \ equals \ \ \exists i \in \{1,2, ..., n\}, x \in S_i x∈i=1⋃nSi equals ∃i∈{1,2,...,n},x∈Si
这个规律是显然的,它只是对同一个命题的不同表达方法,同样的规律还有
x ∈ ⋂ i = 1 n S i e q u a l s ∀ i ∈ { 1 , 2 , . . . , n } , x ∈ S i x \in \bigcap_{i=1}^nS_i \ \ equals \ \ \forall i \in \{1,2, ..., n\}, x \in S_i x∈i=1⋂nSi equals ∀i∈{1,2,...,n},x∈Si
再次重申引理1
( ⋂ i = 1 n S i ) c = ⋃ i = 1 n S n c \quad (\bigcap_{i=1}^{n} S_i)^c = \bigcup_{i=1}^{n}S_n^c (i=1⋂nSi)c=i=1⋃nSnc
此时看到等式右边的表达式,直接利用我们刚刚得到的规律,可以推得
x ∈ ⋃ i = 1 n S n c = ∃ i ∈ { 1 , 2 , . . . , n } , x ∈ S i c x \in \bigcup_{i=1}^{n}S_n^c = \exists i \in \{1,2, ..., n\}, x \in S_i^c x∈i=1⋃nSnc=∃i∈{1,2,...,n},x∈Sic
去掉等式右边表达式的补集关系,将属于符号改为不属于得到(前面已经解释过这样做的依据)
∃ i ∈ { 1 , 2 , . . . , n } , x ∉ S i \exists i \in \{1,2, ..., n\}, x \notin S_i ∃i∈{1,2,...,n},x∈/Si
上式表达的意思是“ x x x 至少不属于 S i S_i Si 中的某一个”,那么容易推知“ x x x 必然不同时属于所有 S i S_i Si”,即
x ∉ ⋂ i = 1 n S i x \notin \bigcap_{i=1}^n S_i x∈/i=1⋂nSi
进一步推知
x ∈ ( ⋂ i = 1 n S i ) c x \in (\bigcap_{i=1}^n S_i)^c x∈(i=1⋂nSi)c
上式中的集合就是引理1中左边的表达式,那么得到
⋃ i = 1 n S n c ⊂ ( ⋂ i = 1 n S i ) c \bigcup_{i=1}^{n}S_n^c \subset (\bigcap_{i=1}^{n} S_i)^c i=1⋃nSnc⊂(i=1⋂nSi)c
此时,已经证到了引理等式两端的集合互为子集,即证到德摩根定律的引理1,即
⋃
i
=
1
n
S
n
c
=
(
⋂
i
=
1
n
S
i
)
c
\bigcup_{i=1}^{n}S_n^c = (\bigcap_{i=1}^{n} S_i)^c
i=1⋃nSnc=(i=1⋂nSi)c文章来源:https://www.toymoban.com/news/detail-655853.html
引理2的证明过程
写得好麻烦啊哈哈哈哈,不想写了,直接去看原文吧,虽然没有解释,但是结合引理1的证明过程应该很容易理解。文章来源地址https://www.toymoban.com/news/detail-655853.html
参考文章
- https://www.cnblogs.com/taoqc/p/16253507.html
到了这里,关于大白话理解德摩根定律(De Morgan‘s Laws)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!