計算機~~概論

2013年6月6日星期四

卡諾圖

卡諾圖是真值表的變形，它可以將有n個變數的邏輯函數的 $2^n$ 個最小項組織在給定的長方形表格中，同時為相鄰最小項（相鄰與項）運用鄰接律化簡提供了直觀的圖形工具。但是，如果需要處理的邏輯函數的自變數較多，那麼卡諾圖的行列數將迅速增加，使圖形更加複雜；此外，卡諾圖的圖形化表示方法不適合直接用於演算法的設計，因此計算機輔助工程工具一般不會使用卡諾圖來進行邏輯函數的優化。卡諾圖是貝爾實驗室的電信工程師，莫里斯·卡諾在1953年發明的

圈選二個１的範例：

上下兩列亦屬於相鄰的方格

　　左右兩列亦屬於相鄰的方格

圈選四個１的範例：

第摩根定理

第摩根第一定理：F＝A＋B＝A‧B

當有三輸入端時，第摩根定理可寫成：A＋B＋C＝A‧B‧C

當有四輸入端時，第摩根定理可寫成：A＋B＋C＋D＝A‧B‧C‧D

第摩根第二定理：F＝A‧B＝A＋B

當有三輸入端時，第摩根定理可寫成：A‧B‧C＝A＋B＋C

當有四輸入端時，第摩根定理可寫成：A‧B‧C‧D＝A＋B＋C＋D

第摩根定理的互換

1. 利用第摩根定律化簡：

原則：①長Bar變短Bar。

②短Bar變長Bar。

③「加」的變「乘」的。

④「乘」的變「加」的。

2. 公式：①A＋B＝A‧B

②A‧B＝A＋B

布林代數

在抽象代數中，布林代數是捕獲了集合運算和邏輯運算二者的根本性質的一個代數結構（就是說一組元素和服從定義的公理的在這些元素上運算）。特別是，它處理集合運算交集、並集、補集；和邏輯運算與、或、非

布林代數也叫做布爾格。關聯於格（特殊的偏序集合）是在集合包含A ⊆ B和次序 a ≤ b之間的相似所預示的。考慮{x,y,z}的所有子集按照包含排序的格。這個布爾格是偏序集合，在其中{x} ≤ {x,y}。任何兩個格的元素，比如p = {x,y}和q = {y,z}，都有一個最小上界，這裡是{x,y,z}，和一個最大下界，這裡是{y}。這預示了最小上界（並或上確界）被表示為同邏輯OR一樣的符號p∨q；而最大下界（交或下確界）被表示為同邏輯AND一樣的符號p∧q。

這種格釋義有助於一般化為海廷代數，它是免除要麼一個陳述要麼它的否定必須為真的限制的布林代數。海廷代數對應於直覺邏輯，而布林代數對應於經典邏輯。

布林代數又譯為布爾代數，然而布林代數得名於喬治·布爾，他是愛爾蘭科克的皇后學院的英國數學家。布林（boolean）在英文中的意思是「布爾的」，這是為了表彰布爾的貢獻，而「布林」只是一種音譯

布林代數的基本運算有三種：如下表所示。

運算類型運算符號運算式簡稱

加法邏輯 “＋” Y＝A＋B OR

乘法邏輯 “．” Y＝A．B AND

布林代數的基本公設：
(1)封閉性：這種性質可由真值表看出，因為每一個運算結果，不是1即是0。
(2)單位元素：
①X＋0＝X
②X．1＝X
③X＋1＝1
④X．0＝0
(3)補數元素：X＝X
(4)結合律：
①(X＋Y)＋Z＝X＋(Y＋Z)
②(X．Y)．Z＝X．(Y．Z)
(5)交換律：
①X＋Y＝Y＋X
②X．Y＝Y．X
(6)分配律：
①X．(Y＋Z)＝X．Y＋X．Z
②X＋(Y．Z)＝(X＋Y)(X＋Z)