抽象代数/布尔代数

布尔代数

布尔代数是一种演绎数学系统，在零和一（假和真）的值上封闭。定义在这个值集上的二元运算符接受两个布尔输入并产生单个布尔输出。

对于任何给定的代数系统，都有一些初始假设或公理，该系统遵循。您可以从这组基本公理中推导出系统的附加规则、定理和其他属性

封闭性： 如果对于每对布尔值，布尔系统相对于二元运算符是封闭的，那么它将产生一个布尔结果。例如，逻辑AND在布尔系统中是封闭的，因为它只接受布尔操作数并只产生布尔结果。
交换性： 如果对于所有可能的布尔值 A 和 B，A # B = B # A，则二元运算符“#”被称为是交换的。
结合性： 如果对于所有布尔值 A、B 和 C，(A # B) # C = A # (B # C)，则二元运算符“#”被称为是结合的。
分配性： 如果对于所有布尔值 A、B 和 C，A # (B % C) = (A # B) % (A # C)，则两个二元运算符“#”和“%”是分配的。
单位元： 如果 A # I = A，则布尔值 I 被称为相对于某个二元运算符“#”的单位元
逆元： 如果 A # I = B 且 B ≠ A（即，B 是 A 的相反值），则布尔值 I 被称为相对于某个二元运算符“#”的逆元。

为了我们的目的，我们将基于以下运算符和值的集合来建立布尔代数

布尔系统中两个可能的值是零和一。通常我们会将这些值称为假和真（分别）。
符号“∧”表示逻辑AND运算（合取）；例如，A ∧ B 是逻辑AND布尔值 A 和 B 的结果。当使用单个字母变量名时，本文字将省略“∧”符号；因此，AB 也表示变量 A 和 B 的逻辑AND（我们也将其称为 A 和 B 的乘积）。
符号“∨”表示逻辑OR运算（析取）；例如，A ∨ B 是逻辑OR布尔值 A 和 B 的结果。（我们也将其称为 A 和 B 的和）。
逻辑补码、否定或NOT是一种一元运算符。本文字将使用素数符号（'）来表示逻辑否定。例如，A' 表示 A 的逻辑NOT。
如果在一个布尔表达式中出现多个不同的运算符，则表达式的结果取决于运算符的优先级。我们将使用以下布尔运算符的优先级（从最高到最低）：括号、逻辑NOT、逻辑AND，然后是逻辑OR。逻辑AND和OR运算符是左结合的。逻辑NOT操作是右结合的，尽管它使用左结合或右结合会产生相同的结果，因为它是一元运算符。

我们还将使用以下公理集

布尔代数在AND、OR和NOT运算下是封闭的。
相对于∧的单位元是一，∨是零。相对于逻辑NOT，没有单位元。
∧和∨运算符是交换的。
∧和∨相对于彼此是分配的。也就是说，A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) 且 A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)。
对于每个值 A，都存在一个值 A'，使得 A ∧ A' = 0 且 A ∨ A' = 1。这个值是 A 的逻辑补码（或NOT）。
∧和∨都是结合的。也就是说，(A ∧ B) ∧ C = A ∧ (B ∧ C) 且 (A ∨ B) ∨ C = A ∨ (B ∨ C)。

您可以使用这些公理证明布尔代数中的所有其他定理。本文字不会深入研究这些定理的正式证明，但是，熟悉布尔代数中一些重要定理是一个好主意。示例包括

A ∨ A = A
A ∧ A = A
A ∨ 0 = A
A ∧ 1 = A
A ∧ 0 = 0
A ∨ 1 = 1
(A ∨ B)' = A' ∧ B'
(A ∧ B)' = A' ∨ B'
A ∨ A ∧ B = A
A ∧ (A ∨ B) = A
A ∨ A'B = A ∨ B
A' ∧ (A ∨ B') = A' B'
AB ∨ AB' = A
(A' ∨ B') ∧ (A' ∨ B) = A'
A ∨ A' = 1
A ∧ A' = 0

以上第七和第八条定理被称为德摩根定律，以发现它们的数学家命名。

上面的定理成对出现。每对（例如 1 & 2、3 & 4 等）形成一个对偶。布尔代数系统中的一个重要原则是对偶性。您可以使用布尔代数的公理和定理创建的任何有效表达式，如果交换表达式中出现的运算符和常量，则该表达式仍然有效。具体来说，如果您交换∧和∨运算符并交换表达式中的 0 和 1 值，您将最终得到一个服从布尔代数所有规则的表达式。这并不意味着对偶表达式计算相同的值，它只意味着这两个表达式在布尔代数系统中都是合法的。因此，这是一种在布尔代数系统中证明的任何事实生成第二个定理的简单方法。

虽然为了布尔代数的目的，我们不会在本文字中证明任何定理，但我们将使用这些定理来证明两个布尔方程是相同的。当试图产生布尔表达式的规范表示或简化布尔表达式时，这是一个重要的操作。

布尔函数和真值表

布尔表达式是一系列零、一和文字，由布尔运算符隔开。文字是带素数（否定）或不带素数的变量名。为了我们的目的，所有变量名都将是一个单字母字符。布尔函数是一个特定的布尔表达式；我们通常会将布尔函数命名为“F”，并带有一个可能的下标。例如，考虑以下函数

F₀ = AB ∨ C

此函数计算 A 和 B 的逻辑AND，然后将此结果逻辑OR到 C。如果 A=1、B=0 且 C=1，则 F₀ 返回值一 (1 ∧ 0 ∨ 1 = 1)。

表示布尔函数的另一种方法是通过真值表。上一章使用真值表来表示AND和OR函数。这些真值表采用以下形式

与真值表

AND	0	1
0	0	0
1	0	1

或真值表

OR	0	1
0	0	1
1	1	1

对于具有两个输入变量的二元运算符，这种真值表形式非常自然和方便。但是，重新考虑上面的布尔函数F₀。该函数具有三个输入变量，而不是两个。因此，无法使用上面给出的真值表格式。幸运的是，为三个或更多变量构建真值表仍然非常容易。以下示例展示了一种针对三个变量函数执行此操作的方法

A	B	C	AB	AB ∨ C
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1