布林代數

3.3　布林代數的基本定理與定律

布林代數是處理邏輯的運算，運算時必然有一些基本規則可循，我們稱之為定理，這些定理都是根據三個邏輯基本運算關係所定出，並不是布林代數還有新的運算因子，初學者只要把握住邏輯的思維方式，以下的幾個定理是不難理解的。

　

3.3-1　基本定理

定理(1) X．0 = 0

說明：AND的運算，在變數條件均為1時結果方為1 ，此定理中的一個變數已經固定為0，所以不管X為1或0其結果必為0。

定理(2) X．1 = X

說明：AND的運算，在變數條件均為1時結果方為1 ，此定理中的一個變數已經固定為1，若X為1則結果為1，若X為0則結果為0，所以X．1 = X。

定理(3) X．X = X

說明：AND的運算，在變數條件均為1時結果方為1 ，若X為1則1．1 = 1，若X為0則0．0 =0，所以X．X = X。

定理(4) X．X’= 0

說明：AND的運算，在變數條件均為1時結果方為1 ，而X與X’總是相反的，亦即1．0 = 0或0．1 =0，所以X．X’= 0。

定理(5) X + 0 = X

說明：OR的運算，在變數條件任何一者為1時結果為1 ，若X為1則1+0 = 1，若X為0則0 + 0 =0，所以X + 0 = X。

定理(6) X + 1 = 1

說明：OR的運算，在變數條件任何一者為1時結果為1 ，此定理中的一個變數已經固定為1，所以X+1 = 1。

定理(7) X + X = X

說明：OR的運算，在變數條件任何一者為1時結果為1 ，若X為1則1+1 = 1，若X為0則0 + 0 =0，所以X + X = X。

定理(8) X + X’= 1

說明：OR的運算，在變數條件任何一者為1時結果為1 ，而X與X’總是相反的，亦即1 + 0 = 1或0 + 1 = 1，所以X + X’= 1。

布林代數除了以上的定理可以作為運算時的法則之外，在多變數的運算式中尚有一些定律可以運用。

　

3.3-2　基本定律

定律(1) 交換律：

a. X+Y = Y+X

b. X．Y = Y．X

定律(2) 結合律：

a. (X+Y)+Z＝X+(Y+Z)

b. (X．Y)．Z＝X．(Y．Z)

定律(3) 分配律：

a. X．(Y+Z)＝XY+XZ

b. X+(Y．Z)＝(X+Y)．(X+Z)

c. (W+X)．(Y+Z)＝WY+WZ+XY+XZ

定律(4) 吸收律：

a. X+XY＝X

b. X+X’Y＝X+Y

証明：X+XY＝X

X+XY＝X(1+Y)                                                         (分配律)

　　　　＝X．1                                                       (∵1+Y＝1)

　　　　＝X

証明：X+X’Y＝X+Y

X+X’Y＝X (1+Y) +X’Y　　                                ( ∵1+Y＝1)

　　　　＝X+XY+X’Y　　　 　                         (分配律)

　　　　＝X+ ( X+X’)Y                                        (分配律)

　　　　＝X+Y                                                        (∵X+X’＝1)

             

布林代數只有三種基本運算如表3.1。至於基本邏輯閘與布林代數的對應關係如表3.2，其中NAND、NOR、XOR、XNOR運算是NOT、AND、OR的混合運算。 表3.2.1 布林代數基本運算 運算方式 簡稱 運算符號 運算式 邏輯補數 NOT X= 邏輯乘法 AND ． X=A．B 邏輯加法 OR + X=A+B 表3.2.2 基本邏輯閘與布林代數關係 邏輯閘 簡稱 布林代數 運算式 反向閘 NOT NOT X= 及閘 AND AND X=A．B 或閘 OR OR X=A+B 反及閘 NAND NOT-AND X= 反或閘 NOR NOT-OR X= 互斥或閘 XOR EX-OR X= 互斥反或閘 XNOR EX-NOR X=

卡諾圖

以布林定理化簡布林函數時，常常不知如何著手，甚至在函數中那一項需要分解，那一項需要合併，也難一眼看出，而且最後結果是否為最簡式往往無法確定，所以使用者期望能有一種化簡方法是有程序可循的，有一定規則的，”卡諾圖”滿足了上述要求。　　卡諾圖是由美國貝爾實驗室，一位名叫卡諾的電機工程師發展出來的，它是利用真值表透過圖形的操作來達到簡化的目的，雖然使用卡諾圖化簡法簡單容易，但只限於五個元素以下的卡諾圖結構，因為五個元素以上太複雜，若真有需要，可使用電腦程式來化簡。

卡諾圖化簡的要點： 如果布林函數有幾個變數,卡諾圖就必須有個方格。 任意相鄰的兩格，亦即相鄰的兩項，其對應的變數字母只有一個是不同的。 下圖分別代表(a)二變數卡諾圖 (b)二變數卡諾圖 (c)四變數卡諾圖。

二個相鄰的１可消去一個互補的變數，四個相鄰的１可消去二個互補的變數，八個相鄰的１可消去三個互補的變數，十六個相鄰的１可消去四個互補的變數。 使用卡諾圖化簡時，由於所圈選的１越多，所能消除的變數越多，因此在圈選時應儘可能以能圈出最多個相鄰的１為優先考量，若遇到獨立的空格其內值為１時，只好個別獨立選出不可遺漏。

化簡的步驟： 將在真值表中可產生１的每個基礎乘積項，對應的填入卡諾圖的空格中，並標記為１，其他的空格則填入０。 依序圈出相鄰的８個１、相鄰的４個１、相鄰的２個１，空格中的１可被重複圈選，以便消除最多的變數。 如果還留下獨立的１，也要個別圈選。 觀察圈選的狀況，要讓所有１的空格都被圈到，而圈選的組數要愈少愈好。 每一個圈選的結果是一個乘積項，將所有的乘積項OR起來即是化簡後的布林代數式。

圈選二個１的範例： 上下兩列亦屬於相鄰的方格 　　左右兩列亦屬於相鄰的方格

圈選四個１的範例：

圈選八個１的範例：

圈選十六個１的範例：

重複圈選的範例：

<例一>

<例二> 利用卡諾圖化簡之布林代數式

隨意條件：         在邏輯電路的應用中，主要是處理輸入與輸出的關係，但並非所有的輸入狀況皆會發生，對這些輸入狀態而言，其對應的輸出是０或１整體而言是無關緊要的，我們稱這種輸出為隨意狀態或未確定狀態(Don't   Care)通常在卡諾圖中可以視化簡的須要將它當成０或１。

<例四>

第摩根定理

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

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

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

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

第摩根第二定理：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

RFID原理與應用

作者：陳啟煌 / 臺灣大學計算機及資訊網路中心程式設計組副組長

---

被稱為本世紀最重要的前十大技術之一的「RFID」(無線射頻辨識系統)，生活中「無所不在」的便利通ING。未來舉凡到商場或便利店購物、圖書館借書、搭乘交通工具、繳停車費、洗車、高速公路的電子收費「ETC」、郵寄、識別證或到醫院掛號領藥…，無一不如影隨形地和「你」一起生活著。

前言相信大家對RFID這個名詞應該是既熟悉又陌生，熟悉的是它已經悄悄的散佈在你我身邊，常有機會看到或聽到這個名詞；陌生的是不知道它背後的運作原理與技術，希望透過本文的介紹，能讓大家對這個號稱是『本世紀十大重要技術項目』之一的科技產物能有更深一層的認識。

RFID 是「Radio Frequency Identification」的縮寫，中文可以稱為「無線射頻識別系統」。 通常是由感應器(Reader)和RFID標籤(Tag)所組成的系統，其運作的原理是利用感應器發射無線電波，觸動感應範圍內的RFID標籤，藉由電磁感應產生電流，供應RFID標籤上的晶片運作並發出電磁波回應感應器。以驅動能量來源區別，RFID標籤可分為主動式及被動式兩種：被動式的標籤本身沒有電池的裝置，所需電流全靠感應器的無線電波電磁感應產生，所以只有在接收到感應器發出的訊號才會被動的回應感應器；而主動式的標籤內置有電池，可以主動傳送訊號供感應器讀取，訊號傳送範圍也相對的比被動式廣。

其實RFID早已存在你我日常生活環境中，出門搭乘捷運會用到的『悠遊卡』，開車上高速公路不用停下車來繳回數票所使用的『ETC』儲值卡，去7-11買個飲料用到的”VISA WAVE”信用卡，心愛的寵物身上的植入的『寵物晶片』，商店或圖書館內的防盜晶片，回到家裡開啟大門門禁所用的”MiFare”晶片卡，這些都是RFID的實際應用。RFID的特性特別適合用來作為人或物品在通路上的管控追蹤及識別。所以RFID廣泛應用在門禁控制、流程管控以及電子票券等方面。加上RFID已制定全球統一的ISO規範，同時看好RFID所帶來的商機，已有不少廠商投入相關產業的研發，近幾年在國內外推出不少與RFID相關的應用如：

全球最大的連鎖通路商 Wal-Mart 要求其前100大上游供應商在貨品的包裝或棧板上裝置RFID標籤，以便追蹤貨品在供應鏈上的即時資訊，可降低成本及提高產品資訊的透明度；國內的裕隆汽車將RFID技術應用在汽車保養維修流程控管，車主在休息室可以清楚掌握愛車即時的處理情況及進度；三總將RFID用於病人的識別，避免給藥錯誤，大幅的提高備藥與給藥的正確性。

在電子票券的應用方面，因為RFID標籤內置的記憶體可以存放相關的識別資料，加上加密的機制即可把票券的內容安全地記錄在電子晶片中，故可廣泛應用在小額消費，以免除付現找零或信用卡簽名等麻煩。如「2006 FIFA世界盃足球賽」主辦單位與飛利浦公司合作，捨棄傳統門票，改採RFID晶片卡，此舉，除了讓球迷能快速驗證入場外，這張RFID電子門票也可以用來支付球場內其他如停車、餐飲等消費；而在國內，大部分台北人手上持有的悠遊卡所採用的MiFare晶片也是一種RFID卡。除了可以用來搭捷運、公車、貓纜及付停車費外，技術上應可用於其他生活上的小額消費。受限於國內的金融法令，悠遊卡僅能用於交通事業，未能進行小額消費的業務；但去年國內四家銀行與台北智慧卡票證公司簽約發行悠遊聯名卡，並且結合『VISA國際組織』推出的VISA WAVE功能，讓持卡人除了可以搭乘大眾運輸系統外，亦可用於便利超商消費，帶來更多方便的服務。

介紹完各種RFID實際應用，在此預告一個好消息，本校今年(96)九月新學期開始，會將校園卡換發成MiFare晶片卡，包含學生證、教職員證、校友證等校園卡都會升級成為RFID晶片卡。原有的校園卡為傳統接觸式的磁條卡，由於在使用時與讀卡機接觸多少會有磨損，且校園卡經常用於館舍的門禁控制，不少人會因為卡片無法辨識而有「卡門」的不愉快經驗，這個問題拜RFID卡非接觸的特性而不復存在。這一次除了換發卡片之外，並整合全校各館舍的門禁系統，屆時全校師生可以一卡通行全校，皮包內也可以少帶幾張卡片。除此之外，也將台北人常用的悠遊卡功能結合在校園卡內，使校園卡可以走出校園，搭乘大眾交通工具。加上與校園卡片結合，使得這張悠遊卡具有掛失的機制，卡片內的儲值的金額不會因為卡片遺失而不見，還有後續的校內外應用還在規劃中，期待能讓校園卡發揮最大的功能。

拜科技之賜，RFID讓生活更方便、更安全，想像一下去超級市場買一車的商品，只要購物車一經過感應器購物清單，帳單立即產生，不用像現在排隊等店員一一點清結帳；還有一回到家裡，周遭溫度、燈光及家電馬上變成你喜歡的設定，不用東找西找遙控器與開關；家裡的冰箱食物飲料不夠時，會自動下訂單宅配到府，不用打開冰箱發現最喜歡的可樂沒有了，這真是個方便的未來，而且這個未來已經不遠了。

文章來自:http://www.cc.ntu.edu.tw/chinese/epaper/0002/20070920_2005.htm

當我們與網路已經不可分離-網路未來五千天

網路拓樸影音教學(吳惠涓.南福君共同製作)

slideshare版本:http://www.slideshare.net/ssusera2399d/ss-22505450