布林代数之基本定理课件.ppt

1、第 4 章 布林代數及第摩根定理 4-1 布林代數之特質4-2 布林代數之基本運算4-3 布林代數之基本定理4-4 第摩根定理4-5 邏輯閘之互換節目錄節目錄.4-1布林代數之特質 基本的布林代數式可簡單的表示成：Ff（A，B，C ），下圖為其示意圖。F的輸出是輸入變數 A、B、C等的函數，亦即 F 的值是由輸入變數的值所決定。.4-2布林代數之基本運算 布林代數雖然只有 0 與 1 兩種數值，但其基本運算有三種，分別為 OR 運算，又稱邏輯的加法運算；AND 運算，又稱邏輯的乘法運算；NOT 運算，又稱邏輯的補數運算，現針對這三種基本運算之特性說明如下：1.OR 運算(1)若 A 和 B 為

2、兩個輸入變數，則當 A 和 B 以 OR 加法組合時，其輸出 F表示為 FAB。節目錄節目錄(2)FAB 之運算結果為只要 A 或 B 是1，其結果 F 就是 1。(3)除了 AB1 情形外，OR 運算與二進制加法運算相同。2.AND 運算(1)若 A 和 B 為兩個輸入變數，則當 A 和 B 以 AND 乘法組合時，其輸出 F表示為 FAB。(2)FAB 之運算結果為只有 A是1且且B也是 1，其結果 F才是 1。(3)AND運算與二進制乘法運算相同。節目錄節目錄3.NOT 運算(1)若 A 為一個輸入變數，則當A做NOT補數運算時，其輸出 。(2)之運算結果為將變數A反轉，即為其結果F，如

3、A=1，則F=0，又如A=0，則F=1。(3)NOT運算與二進制取1的補數運算相同。F=AF=A節目錄節目錄節目錄節目錄.4-3布林代數之基本定理一、布林代數之假設一、布林代數之假設1.封閉性 (1)(2)2.單位元素 (1)(2)X+YBX+0=XX YBX 1=X3.交換律 (1)(2)4.分配律 (1)(2)X+Y=Y+X X+Y ZX+YX+ZX Y=Y X XY+ZX YX Z節目錄節目錄5.補數元素 (1)(2)6.結合律 (1)(2)X+X=1X+YZX+YZX X=0XY ZX YZ節目錄節目錄7.對偶性 任何布林代數式，必有其相對的對偶式，對偶性之互換原則為 (1)將+運算改

4、為，運算改為 +。(2)將常數項0改為1，1改為 0。(3)變數符號不加以改變。節目錄節目錄二、布林代數之基本定理二、布林代數之基本定理 有了布林代數的假設，我們可以以此假設為基礎，發展出下列之基本定理：1.全等性 (1)X+X=X (2)XX=X 2.同一性 (1)X+1=1 (2)X0=0 3.自補性 4.消去性 (1)X+XY=X (2)X(X+Y)=XX=X節目錄節目錄節目錄節目錄.4-4第摩根定理一、第摩根第一定理一、第摩根第一定理 各變數 OR 運算後之反相，等於各變數先反相後再做 AND 之運算，即 。接著，我們將第摩根第一定理應用在兩輸入的邏輯閘上，可以發現，一個反或閘，可視為

5、輸入端先經過反相閘，再輸入及閘，無論輸入端有多少之邏輯閘，此定理均成立，A+B+CN=A B CN如下圖所示，故第摩根第一定理可將OR運算轉換成AND運算。若將下圖之左右兩邊邏輯閘之輸出端各加一反相閘，則可形成如下圖之等效或閘。節目錄節目錄二、第摩根第二定理二、第摩根第二定理 第摩根第二定理也就是在表示這個功能性，定理敘述如下：各變數 AND 運算後之反相，等於各變數先反相後再做 OR 之運算，即 。A B CN=A+B+C+N 節目錄節目錄 接著，我們將第摩根第二定理應用在兩輸入的邏輯閘上，可以發現，一個反及閘，可視為輸入端先經過反相閘，再輸入或閘，無論輸入端有多少之邏輯閘，此定理均成立，如

6、下圖所示，故第摩根第二定理可將AND運算轉換成OR運算。若將下圖之左右兩邊邏輯閘之輸出端各加一反相閘，則可形成如下圖之等效及閘。節目錄節目錄.4-5邏輯閘之互換 在許多布林代數化簡中，第摩根定理常被應用到，而且常是第一定理與第二定理相互搭配使用，是化簡布林代數不可或缺的工具，在練習例題之前，我們再將第摩根第一定理與第二定理陳述一遍。第摩根第一定理第摩根第二定理A+B+CN=A B CNA B CN=ABCN節目錄節目錄應用上述之第摩根定理，很容易將布林代數轉換成完全由通用閘（NAND Gate 或 NOR Gate）所組成的邏輯電路，具有容易設計、製造成本低（因使用的 IC 數較少）之優點。下

7、列為針對全部由 NANDGate 或 NOR Gate 的邏輯電路化簡方法。節目錄節目錄1.多層 NAND Gate 邏輯電路分析邏輯電路若是由多層的 NAND Gate 所組成，則將標示為奇數層的 NAND Gate，全部轉換成具反相輸入的 OR Gate；而標示為偶數層的 NAND Gate，則保持不變。2.多層 NOR Gate 邏輯電路分析簡化的方法與多層的 NAND Gate 邏輯電路分析類似，所不同的，只是將標為奇數層的NOR Gate，全部換成具反相輸入的 AND Gate。節目錄節目錄節目錄節目錄節目錄節目錄布林代數的基本定理節目錄節目錄邏輯閘的互換節目錄節目錄邏輯閘的互換節目錄節目錄