布尔代数概述

我们有两个值：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仅当其参数(真值表中x和y的值)均为T时为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、y和z的全部8个可能值(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。

德摩根规则

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

• 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)

应用规则，这是另一种表示您不在这里或不在那里的方式。&q；

练习：您如何用浅显的英语表达第二条规则？

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

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