邏輯代數

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

邏輯代數是喬治·布爾（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 \text{、} B \text{、} C \text{、} D)$

## 邏輯運算

### 基本運算

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

- 與（合取），記作 $x \land y$（有時記作 $x$ AND $y$ 或 K$xy$），在 $x=y=1$ 情況下，滿足 $x \land y=1$；其他情況下 $x \land y=0$。
- 或（析取）, 記作 $x \lor y$（有時記作 $x$ OR $y$ 或 A$xy$），在 $x=y=0$ 情況下，滿足 $x \lor y=0$；其他情況下 $x \lor y=1$。
- 非 （否定）, 記作 $\neg x$（有時記作 NOT $x$, N$x$ 或 !$x$），在 $x=1$ 情況下，滿足 $\neg x=0$；而在 $\neg x=1$ 情況下，$x=0$。

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

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

此外可以用製作真值表來表示 $x \land y$, $x \lor y$ 和 $\neg x$ 的值：

$x$｜$y$｜$x \wedge y$｜$x \vee y$ 0｜0｜0｜0 1｜0｜0｜1 0｜1｜0｜1 1｜1｜1｜1 ｜$x$｜$\neg x$ 0｜1 1｜0

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

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

### 衍生運算

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

$$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$｜$x \rightarrow y$｜$x \oplus y$｜$x \equiv y$

0｜0｜1｜0｜1

1｜0｜0｜1｜0

0｜1｜1｜1｜0

1｜1｜1｜0｜1

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

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

第三種運算，異或的互補運算，是同或或邏輯等價：$x \equiv y$ 或 E$xy$，當 $x$ 與 $y$ 值相同時為真。因此作為其互補運算，$x \oplus y$ 可以理解為 $x \neq y$，當 $x$ 和 $y$ 不同時為真。它對應的 $\bmod 2$ 算術為 $x+y+1$。

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

## 運算律

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

$a \lor (b \lor c) = (a \lor b) \lor c$｜$a \land (b \land c) = (a \land b) \land c$｜結合律

$a \lor b = b \lor a$｜$a \land b = b \land a$｜交換律

$a \lor (a \land b) = a$｜$a \land (a \lor b) = a$｜吸收律

$a \lor (b \land c) = (a \lor b) \land (a \lor c)$｜$a \land (b \lor c) = (a \land b) \lor (a \land c)$｜分配律

$a \lor \lnot a = 1$｜$a \land \lnot a = 0$｜互補律

$a \lor a = a$｜$a \land a = a$｜冪等律

$a \lor 0 = a$｜$a \land 1 = a$｜有界律

$a \lor 1 = 1$｜$a \land 0 = 0$

$\lnot 0 = 1$｜$\lnot 1 = 0$｜0 和 1 是互補的

$\lnot (a \lor b) = \lnot a \land \lnot b$｜$\lnot (a \land b) = \lnot a \lor \lnot b$｜對偶律

$\lnot \lnot a = a$｜對合律

<image>

## 邏輯代數的基本規則

### 代入規則

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

### 對偶規則

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

### 反演規則

當已知一個邏輯函數 $F$，要求 $\neg F$ 時，只要把 $F$ 中的所有 * 變成 +，+ 變成 *，0 變成 1，1 變成 0，原變量變成反變量，反變量變成原變量，即得 $\neg F$。

使用反演規則時要注意保持原函數中邏輯運算的優先順序。

## 邏輯函數的標準形式

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

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

### 最小項

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

### 最大項

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

## 邏輯函數的化簡

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

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

## 應用

### 電腦

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

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

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

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