邏輯代數

在數學和數理邏輯中，**邏輯代數**（有時也稱**開關代數**、**布爾代數**）是代數的一個分支，其變量的值僅為_真_和_假_兩種真值（通常記作 1 和 0）。初等代數中變量的值是數字，而且主要的運算是加法、乘法和乘方（以及它們的逆運算），而邏輯代數的主要運算有合取_與_，記為∧；析取_或_ ，記為∨；否定_非_ ，記為 ¬ 。因此，它是以普通代數描述數字關係相同的方式來描述邏輯關係的形式主義。

邏輯代數是喬治・布爾（George Boole）在他的第一本書《邏輯的數學分析》（1847 年）中引入的，並在他的《思想規律的研究》（1854 年）中更充分的提出了邏輯代數。
根據 Huntington「布爾代數」這個術語，最初是由 Sheffer 於 1913 年提出。

邏輯代數一直是數字電路設計的基礎，並且所有現代程式語言提供支持。它也用在集合論和統計學中。 

## 邏輯代數中的幾個概念

參與邏輯運算的變量叫**邏輯變量**，用字母 A，B…… 表示。每個變量的取值非 0 即 1。 0、1 不表示數的大小，而是代表兩種不同的邏輯狀態。

正、負邏輯規定：

* 正邏輯體制規定：高電平為邏輯 1，低電平為邏輯 0。
* 負邏輯體制規定：低電平為邏輯 1，高電平為邏輯 0。

**邏輯函數**：如果有若干個邏輯變量（如 A、B、C、D）按與、或、非三種基本運算組合在一起，得到一個表達式 L。對邏輯變量的任意一組取值（如 0000、0001、0010）L 有唯一的值與之對應，則稱 L 為邏輯函數。邏輯變量 A、B、C、D 的邏輯函數記為：L=f (A、B、C、D)

## 邏輯運算

### 基本運算

邏輯代數的基本運算如下。

* 與（合取），記作 _x_∧_y_（有時記作 _x_ AND _y_ 或 K_xy_），在 _x_ = _y_ = 1 情況下，滿足 _x_∧_y_ = 1；其他情況下 _x_∧_y_ = 0。
* 或（析取）, 記作 _x_∨_y_（有時記作 _x_ OR _y_ 或 A_xy_），在 _x_ = _y_ = 0 情況下，滿足 _x_∨_y_ = 0；其他情況下 _x_∨_y_ = 1。
* 非 （否定）, 記作 ¬_x_（有時記作 NOT _x_, N_x_ 或 !_x_），在 _x_ = 1 情況下，滿足 ¬_x_ = 0；而在 ¬_x_ = 1 情況下，_x_ = 0。

如果把真值 0 和 1 解釋為整數，這些運算可以表示為普通算數運算：

　
: ${\begin{aligned}x\wedge y&=x\times y\\x\vee y&=x+y-(x\times y)\\\neg x&=1-x\end{aligned}}$

此外可以用製作真值表來表示 _x_∧_y_, _x_∨_y_ 和 ¬_x_ 的值：

　
:

有人可能會認為，只有否定和另外兩種運算之一是基本的，因為用下列性質可以用邏輯否和邏輯或來定義邏輯與，反之亦然：

　
: ${\begin{aligned}x\wedge y&=\neg (\neg x\vee \neg y)\\x\vee y&=\neg (\neg x\wedge \neg y)\end{aligned}}$

### 衍生運算

上述三個邏輯運算被稱為基本的，這意味著其他邏輯運算可以以它們為基礎，由他們的**複合**來建立，即將這些運算組合或結合。下面是由基本運算構成的運算的例子：

　
: $x\rightarrow y=\neg {x}\vee y$

　
: $x\oplus y=(x\vee y)\wedge \neg {(x\wedge y)}$

　
: $x\equiv y=\neg {(x\oplus y)}$

這些定義產生以下真值表，其中給出了對所有四個可能的輸入，這些運算的值。

　
:

第一種運算，_x_ → _y_ 或 C_xy_，叫做**實質蘊涵**。如果 _x_ 為真，則 _x_ → _y_ 的值就取自 _y_ 的值。但如果 _x_ 為假，則 _y_ 可以忽略；然而此運算必須返回_某種_真值，而且只有兩種選擇，所以返回蘊含較小的值，即_真_。（相干邏輯通過看作非真非假的假前提的蘊含來處理這件事。）

第二種運算，_x_ ⊕ _y_ 或 J_xy_，叫做**異或**（通常縮寫為 XOR）與邏輯或的區別在於邏輯或包含其類型。它排除了 _x_ 和 _y_ 同時為真的情形。用算術來定義就是加和之後 mod 2，就如 1 + 1 = 0.

第三種運算，異或的互補運算，是**同或**或邏輯等價：_x_ ≡ _y_ 或 E_xy_，當 _x_ 與 _y_ 值相同時為真。因此作為其互補運算，_x_ ⊕ _y_ 可以理解為 _x_ ≠ _y_，當 _x_ 和 _y_ 不同時為真。它對應的 mod 2 算術為 _x_ + _y_ + 1。

給定兩個操作數，每個具有兩個可能的值，共有 22 = 4 種可能的輸入組合。由於每種輸出有兩種可能值，一共有 24 = 16 種可能的二元邏輯運算。

## 運算律

兩個主要的二元運算的符號定義為 $\land $ (邏輯與) 和 $\lor $ (邏輯或)，把單一的一元運算的符號定義為 $\lnot $ (邏輯非)。我們還使用值 0 (邏輯假) 和 1 (邏輯真)。邏輯代數有下列性質:

　
:

## 邏輯代數的基本規則

### 代入規則

任何一個含有變量 X 的等式，如果將所有出現 X 的位置，都代之以一個邏輯函數 F，此等式仍然成立。

### 對偶規則

設 F 是一個邏輯函數式，如果將 F 中的所有的 \* 變成 +，+ 變成 \*，0 變成 1，1 變成 0，而變量保持不變。那麼就的得到了一個邏輯函數式 F'，這個 F' 就稱為 F 的對偶式。如果兩個邏輯函數 F 和 G 相等，則它們各自的對偶式 F' 和 G' 也相等。

### 反演規則

當已知一個邏輯函數 F，要求 ¬F 時，只要把 F 中的所有 \* 變成 +，+ 變成 \*，0 變成 1，1 變成 0，原變量變成反變量，反變量變成原變量，即得 ¬F。
使用反演規則時要注意保持原函數中邏輯運算的優先順序。

## 邏輯函數的標準形式

邏輯變量的邏輯**與運算**叫做**與項**，與項的邏輯或運算構成了邏輯函數的與或式，也叫做**積之和式**(SP form)。

邏輯變量的邏輯**或運算**叫做**或項**，或項的邏輯與運算構成了邏輯函數的或與式，也叫做**和之積式**(PS form)。

### 最小項

對於 n 個變量的邏輯函數而言，它的與項如果包含全部 n 個變量，即每個變量以原變量或反變量的形式出現一次且只出現一次，那麼這個與項就稱為該邏輯函數的最小項。

### 最大項

對於 n 個變量的邏輯函數而言，它的或項如果包含 全部 n 個變量，即每個變量以原變量或反變量的形式出現一次且只出現一次，那麼這個或項就稱為該邏輯函數的最大項。

## 邏輯函數的化簡

運用邏輯代數的基本公式及規則可以對邏輯函數進行變換，從而得到表達式的最簡形式。這裡所謂的最簡形式是指最簡與或式或者是最簡或與式，它們的判別標準有兩條：(1) 項數最少；(2) 在項數最少的條件下，項內的文字最少。

卡諾圖是遵循一定規律構成的。由於這些規律，使邏輯代數的許多特性在圖形上得到形象而直觀的體現，從而使它成為公式證明、函數化簡的有力工具。

## 應用

### 計算機

20 世紀早期，一些電子工程師領悟到邏輯代數很像某種電子電路的行為。香農在它 1937 年的論文中證明了這種行為與邏輯代數等價。

幾乎所有現代通用計算機都用二值布爾邏輯做運算；也就是說它們的電路是二值布爾邏輯的物理表示。幾種表示方式：導線上電壓的高低，磁性存儲設備中磁疇的方向，打孔卡或紙帶上的洞，等等（但有些早期的計算機用了十進位電路或者機械，而不是二值邏輯電路）

當然，也可能在任意介質中編碼進 2 個以上的符號。比如在導線上用 0，1，2，3 伏特去編碼一種有 4 個符號的字符集，或者利用打孔卡的洞的不同大小。但實踐上，在一個很小的、高速的、低功耗的電路中噪聲是個關鍵因素。它使分辨多個可能出現的符號變得困難。所以電路設計者們選擇了高、低 2 種電壓而不是 4 種。

由於上面的原因計算機使用二值邏輯電路。最常見的計算機架構使用 32 或 64 個叫做比特的布爾值序列，比如 01101000110101100101010101001011。當使用機器語言、彙編語言和某些高級語言時，程式設計師可以操作暫存器的數字結構。在暫存器中 0 電壓表示邏輯 0，參考電壓（通常是 + 5 伏或 + 3.3 伏）表示邏輯 1。這些語言同時支持數值操作和邏輯操作。這裡的「數值操作」指計算機把比特序列當作二進位數字進行加減乘除等運算。「邏輯操作」指 2 個比特序列之間的與或非運算，序列中每一位都與另一序列中對應位進行運算。這兩種操作之間的關鍵不同是前者有進位而後者沒有。

## 參見

* 數字邏輯 (數位邏輯)
* 邏輯函數 (交換函數)
* 規範形式 (布爾代數)
* 邏輯閘
* 卡諾圖

## 參考文獻