大白话理解德摩根定律(De Morgan‘s Laws)

这篇具有很好参考价值的文章主要介绍了大白话理解德摩根定律(De Morgan‘s Laws)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

说明

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

德摩根定律

简介

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

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

  对引理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=1nSi)c=i=1nSnc

引理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=1nSi)c=i=1nSnc

式中, 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(AB)(BA)

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

引理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=1nSi)c=i=1nSnc

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

  首先看引理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=1nSi)c=x/i=1nSi

这是显然的,因为一个集合和其补集是对立的,即一个集合和它的补集之并为全集,两者之交为空集。那么 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},xSic

用中文念一下上面的表达式:“至少存在一个集合 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 xi=1nSic

上式就表示, 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=1nSi)ci=1nSnc

这里也稍作解释,如果由 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 xi=1nSi  equals  i{1,2,...,n},xSi

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

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 xi=1nSi  equals  i{1,2,...,n},xSi

  再次重申引理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=1nSi)c=i=1nSnc

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

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 xi=1nSnc=i{1,2,...,n},xSic

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

∃ 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=1nSi

进一步推知

x ∈ ( ⋂ i = 1 n S i ) c x \in (\bigcap_{i=1}^n S_i)^c x(i=1nSi)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=1nSnc(i=1nSi)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=1nSnc=(i=1nSi)c

引理2的证明过程

  写得好麻烦啊哈哈哈哈,不想写了,直接去看原文吧,虽然没有解释,但是结合引理1的证明过程应该很容易理解。文章来源地址https://www.toymoban.com/news/detail-655853.html

参考文章

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

到了这里,关于大白话理解德摩根定律(De Morgan‘s Laws)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 设计模式大白话——命令模式

    ​ 顾名思义,命令模式其实和现实生活中直接下 命令 的动作类似,怎么理解这个 命令 是理解命令模式的关键!!!直接说结论是很不负责的行为,因此我将会结合之后的例子来向你介绍它,来帮助你更好的理解,而不是仅仅死记硬背它。这样你会在以后需要的时候想起它

    2024年02月11日
    浏览(46)
  • 设计模式大白话——策略模式

    一、概述 ​ 从名字上来看,此设计模式的核心是 策略 二字,所谓策略,说白了就是能够针对不同的情况随机应变。接下来我将带你领略策略模式的魅力 二、场景举例 场景描述 ​ 现在有一个游戏,游戏中有各种各样的鸭子,有些鸭子是呱呱叫会用翅膀飞,有些鸭子是嘎嘎

    2024年02月16日
    浏览(44)
  • 大白话聊聊“深度学习”和“大模型”

    1950年图灵发表论文《计算机器与智能》( Computing Machinery and Intelligence),提出了“机器智能”(Machine Intelligent)的概念,并且提出了著名的“图灵测试”的方法来判断机器是否有智能。 1956年,达特茅斯会议,“人工智能”(Artificial Intelligent)概念被首次提出,人工智能作

    2024年02月02日
    浏览(61)
  • 用大白话举例子讲明白云计算

    前几天王坚院士在2023云栖大会上发表了关于云计算的演讲,听得我是热血沸腾,王院士称AI和云计算的结合是“云计算的第三次浪潮”,对此我深表认同。但是身边的很多朋友还不知道云计算是什么意思,有些人还认为百度云和百度云盘是一个东西,下面我用大白话举例说明

    2024年02月04日
    浏览(52)
  • 设计模式大白话——适配器模式

    ​ 适配器其实非常好理解,放到生活中来,我们身边处处都有这样的例子,最常见的是用的比较多的各种转接线(如:USB 转 Type-C),有了这个“适配器”,我们就能够将电脑和手机等设备相进行连接,而不需要改动电脑/手机的原有接口。 ​ 回到编程的世界中,假设我们的

    2024年02月10日
    浏览(49)
  • React底层原理分析(简单大白话版本)

    react包 react-dom包 react-reconciler包 scheduler包 Fiber对象 diff算法 深度优先遍历  堆排序 链表,栈操作 react合成事件

    2024年01月20日
    浏览(48)
  • Lighting Network(闪电网络)大白话解析

    通道(Channel),通过在主网宣布通道建立,而后交易双方转至链下交易,把多次交易在链下完成,不占用主网资源,交易完成后在主网广播最终交易结果,无需更改主网机制即可实现吞吐量的提高。 “通道”是一个逻辑上的概念,实际使用过程中并没有“通道”,即使在数据传

    2024年02月04日
    浏览(44)
  • 用大白话举例子讲明白区块链

    什么是区块链?网上这么说: 区块链是一种分布式数据库技术,它以块的形式记录和存储交易数据,并使用密码学算法保证数据的安全性和不可篡改性。每个块都包含了前一个块的哈希值和自身的交易数据,形成了一个不断增长的链条。 区块链的特点包括: 分布式:区块链

    2024年02月04日
    浏览(57)
  • 别样的git学习--大白话学git

    希望用更加口语化的语言向大家讲述git 的魅力 1、Git-stash (贮存) 想象一下,你正在写一封重要的邮件,但突然你的老板告诉你需要立即处理另一个紧急任务。你还没完成邮件,不想丢失已写的内容,但你也需要一个干净的工作空间来处理新的任务。在这种情况下,Git 的

    2024年01月24日
    浏览(51)
  • 用大白话来讲讲多线程的知识架构

    感觉多线程的知识又多又杂,自从接触java,就在一遍一遍捋脉络和深入学习。现在将这次的学习成果展示如下。 什么是多线程? 操作系统运行一个程序,就是一个线程。同时运行多个程序,就是多线程。即在同一时间,并行做多件事。 “并行”是相对于我们这些用户来说的

    2024年02月11日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包