布爾邏輯

布爾邏輯

布爾邏輯得名於 George Boole,他是考克大學(現愛爾蘭國立考克大學)的英國數學家,他在十九世紀中葉首次定義了邏輯的代數系統。現在,布爾邏輯在電子學、計算機硬體和軟體中有很多套用。在 1937 年,Claude Shannon 展示了布爾邏輯如何在電子學中使用。

邏輯-集合代數和文氏圖

使用集合代數作為介紹布爾邏輯的一種方式。還使用文氏圖來展示各種布爾邏輯陳述所描述的集合聯繫。

布爾邏輯布爾邏輯

設 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 (邏輯真/全集)。下列性質適用於布爾代數和布爾邏輯二者:

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 = aa \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 de Morgan 定律

\lnot \lnot a = a 卷繞律(involution

真值表

布爾邏輯只使用兩個值 0 和 1,這兩個值的交集和並集可以使用真值表定義如下:

\cap 0 1

0 0 0

1.0 1

\cup 0 1

0 0 1

1.1 1

也可以建立涉及多個輸入和其他布爾運算的更複雜的真值表。

真值表套用在邏輯中,解釋 0 為假,1 為真,\cap 為與,\cup 為或,而 ¬ 為非。

其他記號

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

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

布爾術語的基本數學使用

在聯立方程的情況下,它們是用暗含的邏輯與連線的:

x + y = 2 AND x - y = 2

同樣適用於聯立不等式:

x + y < 2 AND x - y < 2

大於等於號(\ge)和小於等於號(\le)可以假定包含了一個邏輯或:

X < 2 OR X = 2

加/減號(\pm),在平方根的解的情況下,可以被看作是邏輯或:

WIDTH = 3 OR WIDTH = -3

在計算機中布爾邏輯定義若干布爾邏輯函式,有時候稱為操作符。每個函式根據一個或者更多的輸入,用一個邏輯算法來計算輸出值。該算法根據輸入所取真和假的組合來決定什麼時候輸出真(0真1假;1真0假。相對的)。每個邏輯函式類似於一個現實世界的邏輯運算,可以用來定義各種邏輯的情況。

1 非(NOT)

函式:NOT 僅是一個否定;輸出與輸入的相反。(NOT函式僅有一個輸入,故稱為一元函式或者一元操作符)。當輸入為假,輸出是真,反之亦然。NOT函式邏輯上表達一個條件的反面。

2 與 ( AND)

函式:AND 可以有任意多個輸入,但最少是兩個。僅當AND函式的第一個、第二個和第三個輸入等都是真,它的輸出才是真。

3 或 (OR)

函式:OR可以有任意多個輸入,但最少是兩個。OR函式無論何時只要一個輸入中出現了真,輸出就是真。

4 異或 (XOR)

布爾邏輯布爾邏輯

函式:XOR是OR的變體。僅當一個輸入或者另一個輸入是真,但不是兩者都為真(既如果輸入是不同的),它的輸出才為真。

相關搜尋

熱門詞條

聯絡我們