language-agnostic - 德摩根的规则解释

Question

您能否尽可能简单地解释一下德摩根的规则（例如，对只有中学数学背景的人）？

Answer 1

布尔代数概述

我们有两个值：T和F。

我们可以通过三种方式组合这些值：NOT、AND和OR。

不是

NOT是最简单的：

• NOT T = F
• NOT F = T

我们可以把它写成一个真值表：

when given.. | results in...
============================
           T | F
           F | T

为了简洁

x | NOT x
=========
T | F
F | T

将NOT其视为补码，也就是说，它将一个值转换为另一个值。

和

AND适用于两个值：

x y | x AND y
=============
T T | T
T F | F
F T | F
F F | F

AND仅T当它的参数（真值表的值x和y真值表中的值）都T为时，F否则。

或者

OR是T当它的至少一个论点是T：

x y | x OR y
=============
T T | T
T F | T
F T | T
F F | F

结合

我们可以定义更复杂的组合。例如，我们可以为 写一个真值表x AND (y OR z)，第一行如下。

x y z | x AND (y OR z)
======================
T T T | ?

一旦我们知道如何评估x AND (y OR z)，我们就可以填写表格的其余部分。

要评估组合，请评估各个部分并从那里开始工作。括号显示首先评估哪些部分。你从普通算术中所知道的将帮助你解决它。说你有10 - (3 + 5)。首先，您评估括号中的部分以获得

10 - 8

并像往常一样评估它以获得答案，2。

评估这些表达式的工作方式类似。我们知道OR上面的工作原理，所以我们可以稍微扩展我们的表格：

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | ?

现在几乎就像我们回到了x AND y桌面。我们只是简单地替换y OR z和评估的值。在第一行，我们有

T AND (T OR T)

这与

T AND T

这很简单T。

x我们对、的所有 8 个可能值y和z（2 个可能值x乘以 2 个可能值y乘以 2 个可能值）重复相同的过程，z以得到

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | T
T T F | T      | T
T F T | T      | T
T F F | F      | F
F T T | T      | F
F T F | T      | F
F F T | T      | F
F F F | F      | F

有些表达式可能比它们需要的更复杂。例如，

x | NOT (NOT x)
===============
T | T
F | F

换句话说，NOT (NOT x)等价于just x。

德摩根规则

DeMorgan 规则是一种方便的技巧，可以让我们在适合特定模式的等价表达式之间进行转换：

• NOT (x AND y) = (NOT x) OR (NOT y)
• NOT (x OR y) = (NOT x) AND (NOT y)

（您可能会认为这是NOT通过简单的AND和OR表达式进行分布的方式。）

您的常识可能已经了解这些规则！例如，想想民间智慧“你不能同时在两个地方”。我们可以使它符合第一条规则的第一部分：

NOT (here AND there)

应用规则，这是另一种说法“你不在这里或你不在那里”。

练习：你如何用简单的英语表达第二条规则？

对于第一条规则，让我们看一下等号左侧表达式的真值表。

x y | x AND y | NOT (x AND y)
=============================
T T | T       | F
T F | F       | T
F T | F       | T
F F | F       | T

现在右手边：

x y | NOT X | NOT Y | (NOT x) or (NOT y)
========================================
T T | F     | F     | F
T F | F     | T     | T
F T | T     | F     | T
F F | T     | T     | T

两个表中的最终值相同。这证明了表达式是等价的。

练习：证明表达式NOT (x OR y)和(NOT x) AND (NOT y)是等价的。

Answer 2

回顾一些答案，我想我可以通过使用实际上彼此相关的条件来更好地解释它。

德摩根定律是指这样一个事实，即有两种相同的方式来编写两个条件的任意组合——具体来说，AND组合（两个条件都必须为真）和OR组合（任何一个都可以为真）。例子是：

德摩根定律第 1 部分

陈述：爱丽丝有一个兄弟姐妹。
条件：爱丽丝有一个弟弟OR爱丽丝有一个妹妹。
对面：爱丽丝是独生子女（NOT有兄弟姐妹）。
条件：爱丽丝确实NOT有一个兄弟，AND她确实NOT有一个妹妹。

换句话说： NOT [A OR B] = [NOT A] AND [NOT B]

德摩根定律的第 2 部分

声明：鲍勃是一名汽车司机。
条件： Bob 有车ANDBob 有驾照。
对面： Bob 是NOT一名汽车司机。
条件： Bob 确实NOT有车，ORBob 确实NOT有执照。

换句话说： NOT [A AND B] = [NOT A] OR [NOT B] .

我认为这对 12 岁的孩子来说不会那么混乱。它肯定比所有这些关于真值表的废话更令人困惑（即使我看着所有这些都感到困惑）。

Answer 3

这只是一种重述真值陈述的方法，它可以提供更简单的编写条件来做同样事情的方法。

用简单的英语：
当某物不是这个或那个时，它也不是这个也不是那个。
当某物不是这个和那个时，它也不是这个或不是那个。

注意：鉴于英语对“或”一词的不精确性，我在前面的示例中使用它来表示非排他性或。

例如下面的伪代码是等价的：
If NOT(A OR B)...
IF (NOT A) AND (NOT B)....

如果不是（A 和 B）...
如果不是（A）或不是（B）...

Answer 4

“他既没有汽车，也没有公共汽车。” 与“他没有汽车，也没有公共汽车”的意思相同。

“他没有汽车和公共汽车。” 意思是“他要么没有车，要么没有公共汽车，我不确定是哪个，也许他都没有”。

当然，用简单的英语“他没有汽车和公共汽车”。强烈暗示他至少拥有这两件事中的一件。但是，严格来说，从逻辑的角度来看，如果他没有其中任何一个，该陈述也是正确的。

正式地：

• 不是（汽车或公共汽车）=（不是汽车）和（不是公共汽车）
• 不是（汽车和公共汽车）=（不是汽车）或（不是公共汽车）

在英语中，“或”往往意味着一个选择，你没有两样东西。在逻辑上，“或”总是与英语中的“和/或”含义相同。

这是一个真值表，显示了它是如何工作的：

第一种情况：not (cor or bus) = (not car) and (not bus)

 c | b || c or b | not (c or b) || (not c) | (not b) | (not c) and (not b)
---+---++--------+--------------++---------+---------+--------------------
 T | T ||    T   |      F       ||    F    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 T | F ||    T   |      F       ||    F    |    T    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | T ||    T   |      F       ||    T    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | F ||    F   |      T       ||    T    |    T    |        T
---+---++--------+--------------++---------+---------+--------------------

第二种情况：not (car and bus) = (not car) or (not bus)

 c | b || c and b | not (c and b) || (not c) | (not b) | (not c) or (not b)
---+---++---------+---------------++---------+---------+--------------------
 T | T ||    T    |       F       ||    F    |    F    |        F
---+---++---------+---------------++---------+---------+--------------------
 T | F ||    F    |       T       ||    F    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | T ||    F    |       T       ||    T    |    F    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | F ||    F    |       T       ||    T    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------

Answer 5

如果您是一名警官，正在寻找未成年饮酒者，您可以执行以下操作之一，而德摩根的法律规定它们等同于同一件事：

配方 1（A 和 B）

如果他们未满年龄并饮用酒精 饮料，请逮捕他们。

配方 2（非（非 A 或非 B））

如果他们超过 年龄限制或饮用 非酒精饮料，让他们离开。

顺便说一句，这不是我的例子。据我所知，这是一项科学实验的一部分，其中相同的规则以不同的方式表达，以了解它对人们理解它们的能力有多大影响。

Answer 6

画一个简单的维恩图，两个相交的圆。把A放在左边，B放在右边。现在（A 和 B）显然是相交的位。所以 NOT(A and B) 是不在相交位中的所有内容，两个圆圈的其余部分。把它涂上颜色。

像以前一样画另外两个圆，A和B，相交。现在 NOT(A) 是右圆 (B) 中的所有内容，但不是交点，因为这显然是 A 和 B。将其着色。类似地，NOT(B) 是左圆圈中的所有内容，但不是交点，因为那是 B 和 A。把它涂上颜色。

两张图看起来一样。您已经证明了 NOT(A and B) = NOT(A) 或 NOT(B)。T'other case 留给学生作为练习。

Answer 7

德摩根定律允许您以不同的方式陈述一串逻辑运算。它适用于逻辑和集合论，在集合论中，您对非使用补码，对与使用交集，对或使用并集。

德摩根定律允许您简化逻辑表达式，执行与乘法的分配属性非常相似的操作。

因此，如果您在类似 C 的语言中具有以下内容

if !(x || y || z) { /* do something */ }

它在逻辑上等价于：

if (!x && !y && !z)

它也可以这样工作：

if !(x && !y && z)

变成

if (!x || y || !z)

当然，你也可以反过来。

使用称为真值表的东西很容易看出这些陈述的等价性。在真值表中，您只需列出变量（x、y、z）并列出这些变量的所有输入组合。然后，您拥有每个谓词或逻辑表达式的列，并为给定的输入确定表达式的值。任何有关计算机科学、计算机工程或电气工程的大学课程都可能会让您对必须构建的真值表的数量和大小感到疯狂。

那么为什么要学习它们呢？我认为计算中最大的原因是它可以提高更大逻辑表达式的可读性。有些人不喜欢!在表达式前面使用逻辑非，因为他们认为如果错过它会混淆某人。然而，使用德摩根定律对芯片门级的影响是有用的，因为某些门类型更快、更便宜，或者您已经为它们使用了整个集成电路，因此您可以减少所需的芯片封装数量。结果。

Answer 8

不知道为什么这些年来我一直保留它，但它在很多场合都被证明是有用的。感谢我 10 年级的数学老师 Bailey 先生。他称之为德摩根定理。

!(A || B) <==> (!A && !B)
!(A && B) <==> (!A || !B)

当您将否定移入或移出括号时，逻辑运算符（AND、OR）会发生变化。