布林運算

**布林運算**（英語：Boolean algebra）得名於喬治・布爾，他是愛爾蘭科克的皇后學院的英國數學家，他在十九世紀中葉首次定義了邏輯的代數系統。現在，布林運算在電子學、電腦硬體和軟體中有很多應用。在 1937 年，克勞德・艾爾伍德・夏農展示了布林運算如何在電子學中使用。

使用集合代數作為介紹布林運算的一種方式。還使用文氏圖來展示各種布林運算陳述所描述的集合聯絡。

## 術語

設 _X_ 是一個集合：

* **元素**是一個集合的成員。表示為 $\in $ 。如果它不是這個集合的元素，表示為 $\notin $ 。
* **全集**是集合 _X_，有時表示為 1。注意使用全集這個詞意味著「慮及的所有元素」，不必然的同「現有的所有元素」一樣。
* **空集**或 **null 集合**是沒有元素的集合，表示為 $\varnothing $ ，有時表示為 0。
* **一元算符**應用於一個單一的集合。有一個一元算符叫做邏輯**非**（NOT）。它的作用是採用補集。
* **二元算符**應用於兩個集合。基本的二元算符是邏輯**或**（OR）和邏輯**與**（AND）。它們進行集合的聯集和交集。還有其他衍生的二元算符，比如邏輯**互斥或**（XOR，排他的或）。
* **子集**表示為 A $\subseteq $ B，意味這在集合 A 中所有元素都在集合 B 中。
* **真子集**表示為 A $\subset $ B，意味著在集合 A 中的所有元素都在集合 B 中，並且兩個集合不等同。
* **超集**表示為 A $\supseteq $ B，意味著在集合 B 中的所有元素都在集合 A 中。
* **真超集**表示為 A $\supset $ B，意味著在集合 B 中的所有元素都在集合 A 中，並且兩個集合不等同。

## 例子

設圖像為集合 A 包含 "全集" 中所有偶數（二的倍數），集合 B 包含 "全集" 中所有三的倍數。則兩個集合的**交集**（在集合 A AND B 中所有的元素）將是 "全集" 中所有六的倍數。

集合 A 的補集（所有不在集合 A 中的元素）是 "全集" 中所有的奇數。

## 把運算連接起來

儘管在任何布林運算中都最多有兩個集合參與，從這個運算所形成的新集合可以接著與其他集合聯合起來實現另外的布林運算。使用前面的例子，我們可以定義一個新集合 C 作為 "全集" 中所有五的倍數的集合。所以 "集合 A AND B AND C" 將是 "全集" 中所有 30 的倍數。如果為了更方便，我們可以把集合 AB 當作集合 A 和 B 的交集，或者說 "全集" 中所有六的倍數的集合。那麼我們可以稱 "集合 AB AND C" 是 "全集" 中所有 30 的倍數的集合。我們接著進一步的把這個結果叫做集合 ABC。

### 使用圓括號

儘管任何數目的邏輯 AND（或任何數目的邏輯 OR）可以被連接在一起而沒有歧義，AND 和 OR 和 NOT 的組合可以導致歧義的情況。在這種情況下，可以使用圓括號來分清運算的次序。永遠是最內的括號內的運算先進行，隨後是外層的括號以此類推，直到在所有的括號內運算都完成。接著進行括號外的運算。

## 性質

為兩個主要的二元運算的符號定義為 $\land /\cap $ (邏輯與 / 交集）和 $\lor /\cup $ (邏輯或 / 聯集），把單一的一元運算的符號定義為 $\lnot $ / ~(邏輯非 / 補集）。我們還使用值 0（邏輯假 / 空集）和 1（邏輯真 / 全集）。下列性質適用於布林代數和布林運算二者：

　
:

## 真值表

布林運算只使用兩個值 0 和 1，這兩個值的交集和聯集可以使用真值表定義如下：

* 也可以建立涉及多個輸入和其他布林運算的更複雜的真值表。
* 真值表應用在邏輯中，解釋 0 為假，1 為真， $\cap $ 為與， $\cup $ 為或，而 ¬ 為非。

## 其他記號

可以使用各種樣式的基本算符來表達布林運算。AND（與）、OR（或）、NOT（非）是最直覺的。數學家、工程師和程式設計師經常使用 + 表示或， $\cdot $ 表示與（因為在某些方面這些運算類似於在其他代數結構中的加法和乘法，並且這種記號使熟悉普通代數的人易於得到積之和範式）。非也表示為在要否定的表達式頂上的一個橫線。

另一種記號使用 "交" 表示與使用 "並" 表示或。但是這會導致混淆，因為術語 "並" 也經常用於合併集合的另一個布林運算，它包括了與和或二者。

## 布林術語的基本數學使用

* 在聯立方程式的情況下，被聯立的方程式暗含邏輯**與**：

　
: : x + y = 2

　
: : AND

　
: : x - y = 2

同樣適用於聯立不等式：

　
: : x + y < 2

　
: : AND

　
: : x - y < 2

* 大於等於號（ $\geq $ ）和小於等於號（ $\leq $ ），可以認為是暗含邏輯**或**的一對等式與不等式的聯立：

　
: : X < 2

　
: : OR

　
: : X = 2

* 加 / 減號（ $\pm $ ），在表示「平方根的解」情況下，可以被看作暗含邏輯**或**的一對聯立等式：

　
: : WIDTH = 3

　
: : OR

　
: : WIDTH = -3

## 布林術語的英語使用

在把英語句子轉換成形式的布林語句的時候要小心。很多英語詞語不精確的意義可能導致多種邏輯結果，例如英語單詞 NOT（非）：「所有閃光的東西不是金子。」可以解析為以下不同的邏輯表達：

* 「沒有閃光的東西是金子」
* 「有些閃光的東西不是金子」

作為英語單詞的 AND（與）和 OR（或）在特定情況下是可以互換使用的：

* " 在下雨**與**下雪的時候我總是帶傘。"
* " 在下雨**或**下雪的時候我總是帶傘。"

還要注意在英語中單詞 OR（或）可以分別對應於邏輯表達中的**或（OR）** （此亦彼亦）和**互斥或（XOR）** （此即彼非），具體意思要依賴於上下文進行判斷：

* " 我在潮濕**或**高溫的時候出汗。"（此亦彼亦，判定為邏輯**或**）
* " 我午飯打算吃雞肉**或**牛肉。"（此即彼非，判定為邏輯**互斥或**）

在規定電腦程式或者電子電路時，如何使用英語準確描述其功能邏輯是個關鍵問題。例如，對於功能「程式應校驗申請者已經選擇取了男性**或**女性單選框」，應當被當作一個**互斥或**（非此即彼）邏輯（即「程式應校驗申請者已經選擇取了男性或女性選項，並且此二選項互相排他」），則程式語句須特別限定「二者之間只有一個能被選擇」來確保校驗功能的實現；假如將其混為**或**邏輯（此亦彼亦），則該校驗功能有可能被錯誤地實現，造成申請者同時選擇兩個選項、而校驗依然通過。

在其他非技術語言的情況下，對於一段英語文字的解釋可能包含更多的不確定性，可能需要深入探討、以確保明晰該段文字背後所含的邏輯意義的多種可能性。

## 應用

### 數位電子電路設計

布林運算還在電子工程中的電路設計中使用；這裡的 0 和 1 表示在數位電路中某一個位的不同狀態，典型的是高和低電壓。使用包含變數的表達式描述電路，並且對於這些變數的所有的值兩個這種表達式是等價的，若且唯若對應的電路有相同的輸入 - 輸出行為。進一步的說，每種可能的輸入 - 輸出行為都被建模為適合的布林表達式。

基本的邏輯閘比如與閘、或閘、非閘可以單獨使用，或者聯合成與非閘、或非閘和互斥或閘來控制數位電子和電路。這些閘的串聯或並聯控制了運算的優先級。

### 資料庫應用

關聯式資料庫使用 SQL 語言，或者其他特定於資料庫的語言，來進行查詢，它可以包含布林運算。對於這種應用，在表中每個記錄都可以被當作 "集合" 的 "元素"。例如，在 SQL 中，下列 SELECT 語句被用來從在資料庫中的表格中檢索資料：

* SELECT \* FROM EMPLOYEES WHERE LAST\_NAME = 'Smith' AND FIRST\_NAME = 'John' ;
* SELECT \* FROM EMPLOYEES WHERE LAST\_NAME = 'Smith' OR FIRST\_NAME = 'John' ;
* SELECT \* FROM EMPLOYEES WHERE NOT LAST\_NAME = 'Smith' ;

在有多個運算出現的時候，可以使用圓括號來明確的指定布林運算發生的次序：

* SELECT \* FROM EMPLOYEES WHERE（NOT LAST\_NAME = 'Smith'）AND（FIRST\_NAME = 'John' OR FIRST\_NAME = 'Mary'）;

在需要的時候可以使用巢狀的圓括號。

聯合兩個（或更多）表格的任何布林運算在關聯式資料庫術語中都被稱為**連接**。

### 搜尋引擎查詢

對於這種應用，在網際網路上的每個 web 頁面都被當作是 "集合" 的 "元素"。各種線上搜尋引擎使用各自不同的語法。下面描述 Google 使用的語法。

* 邏輯與不使用符號。所以，它是連接兩個搜尋項的預設方式：

　
: : "搜尋項 1" "搜尋項 2"

* 使用關鍵字 OR 表示邏輯或：

　
: : "搜尋項 1" OR "搜尋項 2"

* 使用減號表示邏輯非：

　
: : -"搜尋項 1"

* 不支援使用圓括號來明確指定運算的次序。

## 參見

* 布林代數主題列表
* 布林代數
* 布林函數
* 命題邏輯
* 邏輯閘
* 文氏圖
* 聯集
* 補集
* 交集

## 外部連結

* 邏輯的演算 （頁面存檔備份，存於網際網路檔案館）, George Boole 著，Cambridge and Dublin Mathematical Journal Vol. III (1848), pp. 183-98.
* Logical Formula Evaluator （頁面存檔備份，存於網際網路檔案館）（for Windows）, a software which calculates all possible values of a logical formula
* How Stuff Works - Boolean Logic （頁面存檔備份，存於網際網路檔案館）
* Maiki & Boaz BDD-PROJECT, a Web Application for BDD reduction and visualization.