布林運算
「布林運算」的各地常用名稱 | |
---|---|
中國大陸 | 布爾邏輯 |
臺灣 | 布林運算 |
布林運算(英語:Boolean algebra)得名於喬治·布爾,他是愛爾蘭科克的皇后學院的英國數學家,他在十九世紀中葉首次定義了邏輯的代數系統。現在,布林運算在電子學、電腦硬體和軟體中有很多應用。在1937年,克勞德·艾爾伍德·夏農展示了布林運算如何在電子學中使用。
使用集合代數作為介紹布林運算的一種方式。還使用文氏圖來展示各種布林運算陳述所描述的集合聯絡。
術語
[編輯]設X是一個集合:
- 元素是一個集合的成員。表示為。如果它不是這個集合的元素,表示為。
- 全集是集合X,有時表示為1。注意使用全集這個詞意味著「慮及的所有元素」,不必然的同「現有的所有元素」一樣。
- 空集或null集合是沒有元素的集合,表示為,有時表示為0。
- 一元算符應用於一個單一的集合。有一個一元算符叫做邏輯非(NOT)。它的作用是採用補集。
- 子集表示為A B,意味這在集合A中所有元素都在集合B中。
- 真子集表示為A B,意味著在集合A中的所有元素都在集合B中,並且兩個集合不等同。
- 超集表示為A B,意味著在集合B中的所有元素都在集合A中。
- 真超集表示為A 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的組合可以導致歧義的情況。在這種情況下,可以使用圓括號來分清運算的次序。永遠是最內的括號內的運算先進行,隨後是外層的括號以此類推,直到在所有的括號內運算都完成。接著進行括號外的運算。
性質
[編輯]為兩個主要的二元運算的符號定義為(邏輯與/交集)和(邏輯或/聯集),把單一的一元運算的符號定義為 / ~(邏輯非/補集)。我們還使用值0(邏輯假/空集)和1(邏輯真/全集)。下列性質適用於布林代數和布林運算二者:
真值表
[編輯]布林運算只使用兩個值0和1,這兩個值的交集和聯集可以使用真值表定義如下:
|
|
- 也可以建立涉及多個輸入和其他布林運算的更複雜的真值表。
- 真值表應用在邏輯中,解釋0為假,1為真,為與,為或,而¬為非。
其他記號
[編輯]可以使用各種樣式的基本算符來表達布林運算。AND(與)、OR(或)、NOT(非)是最直覺的。數學家、工程師和程式設計師經常使用 +表示或,表示與(因為在某些方面這些運算類似於在其他代數結構中的加法和乘法,並且這種記號使熟悉普通代數的人易於得到積之和範式)。非也表示為在要否定的表達式頂上的一個橫線。
另一種記號使用"交"表示與使用"並"表示或。但是這會導致混淆,因為術語"並"也經常用於合併集合的另一個布林運算,它包括了與和或二者。
布林術語的基本數學使用
[編輯]- 在聯立方程式的情況下,被聯立的方程式暗含邏輯與:
- x + y = 2
- AND
- x - y = 2
同樣適用於聯立不等式:
- x + y < 2
- AND
- x - y < 2
- 大於等於號()和小於等於號(),可以認為是暗含邏輯或的一對等式與不等式的聯立:
- X < 2
- OR
- X = 2
- 加/減號(),在表示「平方根的解」情況下,可以被看作暗含邏輯或的一對聯立等式:
- 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.
|