deMorgan规则解释道

Question

您能否尽可能简单地解释deMorgan规则(例如,对于只有中学数学背景的人)？

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.

我们重复同一过程的所有8个可能的值x,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)就是相当于只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

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

DeMorgan定律指的是有两种相同的方式来编写两种条件的任意组合 - 特别是AND组合(两种条件必须为真)和OR组合(任一种都可以是真的).例如:

德莫根定律的第1部分

声明:爱丽丝有一个兄弟姐妹.
条件:爱丽丝有一个兄弟OR爱丽丝有一个妹妹.
相反:爱丽丝是一个独生子女(确实NOT有兄弟姐妹).
条件:爱丽丝确实NOT有一个兄弟,AND她确实NOT有一个妹妹.

换一种说法: NOT [A OR B] = [NOT A] AND [NOT B]

德莫根定律的第2部分

声明: Bob是一名汽车司机.
条件:鲍勃有车,AND鲍勃有牌照.
相反:鲍勃是NOT一名汽车司机.
条件:鲍勃确实NOT有车,OR鲍勃NOT有许可证.

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

我认为对于一个12岁的孩子来说这会有点混乱.对于所有关于真值表的废话,它肯定不那么令人困惑(即使我对所有这些都感到困惑).

Answer 3

它只是重述真实陈述的一种方式,它可以提供更简单的方法来编写条件来做同样的事情.

用简单的英语:
当某些东西不是这个或那个时,它也不是这个而不是那个.
什么东西不是这个,那也不是这个.

注意:鉴于英语单词'或'的不精确,我使用它来表示非排他性或前面的例子.

例如,下面的伪代码是等价的:
如果不是(A或B)......
如果(不是A)和(不是B)....

如果不是(A和B)......
如果不是(A)或不是(B)......