邏輯代數

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

邏輯代數是喬治·布爾（George Boole）在他的第一部著作《邏輯的數學分析》（1847年）中引入，並在他的《思想規律的研究》（1854年）中全面闡述了邏輯代數。^[1] 根據Huntington的說法，「布爾代數」術語最初是由Sheffer於1913年提出。^[2]

邏輯代數一直是數字電路設計的基礎，所有現代程式語言都提供支持。它還用於集合論和統計學。 ^[3]

邏輯代數中的幾個概念

參與邏輯運算的變量叫邏輯變量，用字母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 或 Kxy），在 x = y = 1 情況下，滿足 x∧y = 1；其他情況下 x∧y = 0。
或（析取）, 記作 x∨y（有時記作 x OR y 或 Axy），在 x = y = 0 情況下，滿足 x∨y = 0；其他情況下 x∨y = 1。
非（否定）, 記作 ¬x（有時記作 NOT x, Nx 或 !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 的值：

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

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

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

給定兩個操作數，每個具有兩個可能的值，共有 2² = 4 種可能的輸入組合。由於每種輸出有兩種可能值，一共有 2⁴ = 16種可能的二元邏輯運算（英語：Boolean algebras canonically defined#Truth tables）。

運算律

兩個主要的二元運算的符號定義為 $\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$		對合律

布爾運算的各種表示

邏輯代數的基本規則

代入規則

任何一個含有變量 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個叫做比特的布爾值序列，比如011010001101001010101001010111100000010101001011。當使用機器語言、匯編語言和某些高級語言時，程式設計師可以操作寄存器的數字結構。在寄存器中0電壓表示邏輯0，參考電壓（通常是+5伏或+3.3伏^[4]）表示邏輯1。這些語言同時支持數值操作和邏輯操作。這裏的「數值操作」指計算機把比特序列當作二進制數字進行加減乘除等運算。「邏輯操作」指2個比特序列之間的與或非運算，序列中每一位都與另一序列中對應位進行運算。這兩種操作之間的關鍵不同是前者有進位而後者沒有。

參見

參考文獻

^ Boole, George. An Investigation of the Laws of Thought. Prometheus Books. 2003 [1854]. ISBN 978-1-59102-089-9.
^ "The name Boolean algebra (or Boolean 'algebras') for the calculus originated by Boole, extended by Schröder, and perfected by Whitehead seems to have been first suggested by Sheffer, in 1913." E. V. Huntington, "New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia mathematica （頁面存檔備份，存於互聯網檔案館）", in Trans. Amer. Math. Soc. 35 (1933), 274-304; footnote, page 278.
^ Givant, Steven; Halmos, Paul. Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer. 2009. ISBN 978-0-387-40293-2.
^ Logic Levels - learn.sparkfun.com. learn.sparkfun.com. [2016-12-12]. （原始內容存檔於2021-05-07）.

[1] Boole, George. An Investigation of the Laws of Thought. Prometheus Books. 2003 [1854]. ISBN 978-1-59102-089-9.

[2] "The name Boolean algebra (or Boolean 'algebras') for the calculus originated by Boole, extended by Schröder, and perfected by Whitehead seems to have been first suggested by Sheffer, in 1913." E. V. Huntington, "New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia mathematica （頁面存檔備份，存於互聯網檔案館）", in Trans. Amer. Math. Soc. 35 (1933), 274-304; footnote, page 278.

[givhal-3] Givant, Steven; Halmos, Paul. Introduction to Boolean Algebras. Undergraduate Texts in Mathematics, Springer. 2009. ISBN 978-0-387-40293-2.

[4] Logic Levels - learn.sparkfun.com. learn.sparkfun.com. [2016-12-12]. （原始內容存檔於2021-05-07）.

[1]

[2]

[3]

[4]