德摩根规则解释

Question

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

Answer 1

布尔代数概述

我们有两个值：T 和 F。

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

NOT

NOT 是最简单的：

• NOT T = F
• NOT F = T

我们可以将其写成一个真值表 ：

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

为了简洁

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

起见，将NOT视为补码，即将一个值转换为另一个值。

AND

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

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)

which 与which 相同，

T AND T

只是T。

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

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)等价只是x。

DeMorgan 规则

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 部分

声明：爱丽丝有一个兄弟姐妹。
条件：爱丽丝有一个兄弟或爱丽丝有一个姐妹。
相反：爱丽丝是独生子（没有有兄弟姐妹）。
条件：爱丽丝没有有兄弟，并且她没有有姐妹。

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

德摩根定律第 2 部分

声明： Bob 是一名汽车司机。
条件：鲍勃有一辆车并且鲍勃有驾照。
相反：鲍勃不是汽车司机。
条件：鲍勃没有有汽车，或鲍勃没有有驾照。

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

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

Answer 3

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

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

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

例如，以下伪代码是等效的：
如果不是（A 或 B）...
如果（非 A）且（非 B）...

如果非（A 且 B）...
如果不是（A）或不是（B）...

Answer 4

如果您是一名正在寻找未成年饮酒者的警察，您可以执行以下操作之一，德摩根定律表示它们的作用相同：

公式 1（A 和 B）

如果他们低于年龄
限制并饮酒酒精
饮料，逮捕他们。

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

如果他们结束了
年龄限制或饮酒
非酒精饮料，放开它们。

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

Answer 5

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

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

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

形式上：

• not（汽车或公共汽车）=（非汽车）和（非公共汽车）
• not（汽车和公共汽车）=（非汽车）或（非公共汽车）

在英语中，“或”往往意味着一种选择，你不这样做两者兼而有之。在逻辑中，“或”始终与英语中的“和/或”含义相同。

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

第一种情况：not（cor或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（汽车和公共汽车）=（非汽车）或（非公共汽车）

 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 6

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

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

两幅图看起来一样。您已经证明 NOT(A 和 B) = NOT(A) 或 NOT(B)。另一个案例留给学生作为练习。

Answer 7

德摩根定律允许您以不同的方式陈述一系列逻辑运算。它适用于逻辑和集合论，在集合论中，您可以使用补集来表示“非”，使用交集来表示“与”，使用并集来表示“或”。

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

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

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

那么它在逻辑上等同于：

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

它也可以像这样工作：

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

变成

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

当然，您可以反向进行。

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

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

Answer 8

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

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

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