布林表示式與函式

---

---

布林代數是邏輯代數。它處理可以具有兩個離散值0（假）和1（真）的變數；以及具有邏輯意義的運算。操縱符號邏輯的最早方法是由喬治·布林發明的，後來被稱為布林代數。

布林代數由於其在開關理論、構建基本電子電路和數字計算機設計中的廣泛應用，現已成為計算機科學中不可或缺的工具。

布林函式

布林函式是一種特殊的數學函式$f: X^n \rightarrow X$，其中$X = \lbrace {0, 1} \rbrace$是布林域，n是非負整數。它描述瞭如何從布林輸入推匯出布林輸出的方法。

示例 − 令$F(A, B) = A’B’$。這是一個從布林變數有序對集合到集合$\lbrace {0, 1} \rbrace$的2次函式，其中$F(0, 0) = 1, F(0, 1) = 0, F(1, 0) = 0$和$F(1, 1) = 0$

布林表示式

布林表示式總是產生布爾值。布林表示式由布林常量（真或假）、布林變數和邏輯連線詞組合而成。每個布林表示式都代表一個布林函式。

示例 − $AB’C$是一個布林表示式。

布林恆等式

雙重補元律

$\sim(\sim A) = A$

補元律

$A + \sim A = 1$ (或運算)

$A . \sim A = 0$ (與運算)

冪等律

$A + A = A$ (或運算)

$A . A = A$ (與運算)

同一律

$A + 0 = A$ (或運算)

$A . 1 = A$ (與運算)

支配律

$A + 1 = 1$ (或運算)

$A . 0 = 0$ (與運算)

交換律

$A + B = B + A$ (或運算)

$A. B = B . A$ (與運算)

結合律

$A + (B + C) = (A + B) + C$ (或運算)

$A. (B . C) = (A . B) . C$ (與運算)

吸收律

$A. (A + B) = A$

$A + (A . B) = A$

簡化律

$A . (\sim A + B) = A . B$

$A + (\sim A . B) = A + B$

分配律

$A + (B . C) = (A + B) . (A + C)$

$A . (B + C) = (A . B) + (A . C)$

德摩根律

$\sim (A . B) = \sim A + \sim B$

$\sim (A+ B) = \sim A . \sim B$

規範形式

對於布林表示式，有兩種規範形式：

• 最小項之和 (SOM) 形式
• 最大項之積 (POM) 形式

最小項之和 (SOM) 或積之和 (SOP) 形式

最小項是所有變數的乘積，這些變數以其直接形式或補形式出現。任何布林函式都可以表示為其1-最小項的和，而函式的反函式可以表示為其0-最小項的和。因此，

F（變數列表）= ∑（1-最小項索引列表）

和

F'（變數列表）= ∑（0-最小項索引列表）

示例

令 $F(x, y, z) = x' y' z' + x y' z + x y z' + x y z $

或者，$F(x, y, z) = m_0 + m_5 + m_6 + m_7$

因此，

$F(x, y, z) = \sum (0, 5, 6, 7)$

現在我們將找到$F(x, y, z)$的補集

$F' (x, y, z) = x' y z + x' y' z + x' y z' + x y' z'$

或者，$F'(x, y, z) = m_3 + m_1 + m_2 + m_4$

因此，

$F'(x, y, z) = \sum (3, 1, 2, 4) = \sum (1, 2, 3, 4)$

最大項之積 (POM) 或和之積 (POS) 形式

最大項是所有變數的加法，這些變數以其直接形式或補形式出現。任何布林函式都可以表示為其0-最大項的乘積，而函式的反函式可以表示為其1-最大項的乘積。因此，

F（變數列表）= $\pi$（0-最大項索引列表）。

和

F'（變數列表）= $\pi$（1-最大項索引列表）。

示例

令 $F(x, y, z) = (x + y + z) . (x+y+z') . (x+y'+z) . (x'+y+z)$

或者，$F(x, y, z) = M_0 . M_1 . M_2 . M_4$

因此，

$F (x, y, z) = \pi (0, 1, 2, 4)$

$F''(x, y, z) = (x+y'+z') . (x'+y+z') . (x'+y'+z) . (x'+y'+z')$

或者，$F(x, y, z) = M_3 . M_5 . M_6 . M_7$

因此，

$F '(x, y, z) = \pi (3, 5, 6, 7)$

邏輯閘

布林函式是使用邏輯閘實現的。以下是邏輯閘：

非門

非門將單個位元輸入反轉為單個位元輸出。

與門

與門是一種邏輯閘，只有當所有輸入都為高電平時才輸出高電平，否則輸出低電平。點(.) 用於表示與運算。

或門

或門是一種邏輯閘，如果至少一個輸入為高電平，則輸出高電平。加號(+) 用於表示或運算。

與非門

與非門是一種邏輯閘，只有當所有輸入都為高電平時才輸出低電平，否則輸出高電平。

或非門

或非門是一種邏輯閘，只有當兩個輸入都為低電平時才輸出高電平，否則輸出低電平。

異或 (XOR) 門

異或門是一種邏輯閘，如果輸入不同，則輸出高電平，否則輸出低電平。

異或非 (X-NOR) 門

異或非門是一種邏輯閘，如果輸入相同，則輸出高電平，否則輸出低電平。