抽象代數/布林代數

布林代數

布林代數是一種演繹數學系統，在零和一（假和真）的值上封閉。定義在這個值集上的二元運算子接受兩個布林輸入併產生單個布林輸出。

對於任何給定的代數系統，都有一些初始假設或公理，該系統遵循。您可以從這組基本公理中推匯出系統的附加規則、定理和其他屬性

封閉性： 如果對於每對布林值，布林系統相對於二元運算子是封閉的，那麼它將產生一個布林結果。例如，邏輯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