數(shù)字邏輯第2章布爾代數(shù)基礎(chǔ)

1、第2章 布爾代數(shù)基礎(chǔ)2.1 邏輯代數(shù)基礎(chǔ) 2.1.1 邏輯代數(shù)的基本概念 2.1.2 基本邏輯運(yùn)算 2.1.3 IEEE邏輯符號(hào) 2.1.4 邏輯代數(shù)的公理、定理和規(guī)則2.2邏輯函數(shù) 2.2.1 邏輯函數(shù)表達(dá)式的基本形式 2.2.2 邏輯函數(shù)的標(biāo)準(zhǔn)形式 2.2.3 邏輯函數(shù)表達(dá)式的轉(zhuǎn)換2.3 邏輯函數(shù)的化簡(jiǎn) 2.3.1 代數(shù)化簡(jiǎn)法 2.3.2 卡諾圖化簡(jiǎn)法 研究數(shù)字系統(tǒng)中邏輯電路設(shè)計(jì)和分析的數(shù)學(xué)工具是布爾代數(shù)。 布爾代數(shù)是由邏輯變量集K(A、B、C、)，常量“0”、“1”以及“與”、“或”、“非”3種基本邏輯運(yùn)算構(gòu)成的代數(shù)系統(tǒng)。 邏輯變量集K是布爾代數(shù)中變量的集合，它可以用任何字母表示，每個(gè)變

2、量的取值只能為常量“0”或“1”。 在數(shù)字系統(tǒng)中使用布爾變量表示開關(guān)電路的輸入或輸出。這些變量的每一個(gè)取值是“0”或“1”兩個(gè)不相同的值?！?”可以代表低電壓，“1”可以代表高電壓。F( False )和T( True )也可以用于表示“0”或“1”。 布爾代數(shù)把矛盾的一方假設(shè)為“1”，另一方假設(shè)為“0”，使之?dāng)?shù)學(xué)化。 這樣可以使用布爾代數(shù)中的公理和定理對(duì)物理現(xiàn)象作數(shù)學(xué)演算，達(dá)到邏輯推理的目的。 幸運(yùn)的是，數(shù)字系統(tǒng)中采用的是“0”和“1”兩個(gè)不同的值。因此布爾代數(shù)可以用來作為分析和設(shè)計(jì)邏輯電路的數(shù)學(xué)工具。 從應(yīng)用的角度，布爾代數(shù)應(yīng)用于邏輯電路領(lǐng)域稱其為邏輯代數(shù)。 本章介紹邏輯代數(shù)的基本理論和運(yùn)

3、算方法，其中包括邏輯代數(shù)基本概念，邏輯函數(shù)的定義，邏輯代數(shù)的公理、定理和規(guī)則，小項(xiàng)與大項(xiàng)的概念以及使用小項(xiàng)和大項(xiàng)表達(dá)邏輯函數(shù)的標(biāo)準(zhǔn)形式。 在此基礎(chǔ)上，介紹應(yīng)用邏輯代數(shù)法和卡諾圖法化簡(jiǎn)邏輯函數(shù)的原理與方法。2.1.1 邏輯代數(shù)的基本概念 邏輯代數(shù)包含邏輯變量集K(A、B、C、)，每個(gè)變量的取值只可能為常量“0”或“1”。這里的“0”和“1”沒有量的概念，是用來表達(dá)矛盾雙方，是一種形式上的符號(hào)。 邏輯代數(shù)中邏輯變量之間是邏輯關(guān)系。邏輯關(guān)系用邏輯運(yùn)算符表示。使用邏輯運(yùn)算符連接邏輯變量及常量“0”或“1”構(gòu)成邏輯代數(shù)表達(dá)式。 采用邏輯代數(shù)表示邏輯電路的輸入與輸出之間的邏輯關(guān)系，稱邏輯函數(shù)。這種電路稱數(shù)

4、字邏輯電路。 邏輯函數(shù)除了使用邏輯代數(shù)表示以外，還可以使用一種稱為“真值表”的表格表示。 真值表是由輸入變量所有可能取值的組合與這些組合值對(duì)應(yīng)的輸出變量的值構(gòu)成的表格。真值表分為左、右兩個(gè)部分。 左邊部分每一列是輸入變量的名字。右邊部分的每一列是輸出變量的名字。左邊部分是輸入變量所有的取值的組合。 如果一個(gè)邏輯函數(shù)有n個(gè)變量，則輸入變量所有的取值有2n個(gè)組合。右邊部分是把左邊每一行輸入變量的取值帶到邏輯函數(shù)中去運(yùn)算，把運(yùn)算的結(jié)果“0”或者“1”填進(jìn)來。這樣就完成了把邏輯函數(shù)用真值表表示。邏輯函數(shù)有的比較簡(jiǎn)單，有的相當(dāng)復(fù)雜。但是它們都是由“與”、“或”、“非”三種最基本的邏輯運(yùn)算構(gòu)成。下面分別介

5、紹這三種邏輯運(yùn)算符、邏輯表達(dá)式、邏輯函數(shù)和邏輯函數(shù)符號(hào)。2.1.2基本邏輯運(yùn)算1.“與”運(yùn)算“與”運(yùn)算的運(yùn)算符是“”、“*”、“”或是空。在本書中使用“”表示“與”運(yùn)算符。2.1.2基本邏輯運(yùn)算2“或”運(yùn)算“或”運(yùn)算的運(yùn)算符是“+”、“”。本書中使用“+”表示“或”運(yùn)算符。2.1.2基本邏輯運(yùn)算3“非”運(yùn)算“非”運(yùn)算的運(yùn)算符是“ ”或“ ” ，本書中使用“ ” 表示“非”運(yùn)算符。2.1.2基本邏輯運(yùn)算4. “與非”運(yùn)算“與非”函數(shù)是由“非”函數(shù)和“與”函數(shù)導(dǎo)出。 2.1.2基本邏輯運(yùn)算5. “或非”運(yùn)算“或非”函數(shù)是由“非”函數(shù)和“或”函數(shù)導(dǎo)出。2.1.2基本邏輯運(yùn)算6“異或”運(yùn)算“異或”運(yùn)算

6、的運(yùn)算符是“”。2.1.2基本邏輯運(yùn)算7“同或”運(yùn)算“同或”運(yùn)算也可以稱為“異或非”運(yùn)算，其運(yùn)算符是“”?！爱惢颉边\(yùn)算表達(dá)式與“同或”運(yùn)算表達(dá)式有如下關(guān)系： A B A B，A B A B2.1.3 IEEE邏輯符號(hào)如前所述，邏輯函數(shù)是由“與”、“或”、“非”三種最基本的邏輯運(yùn)算構(gòu)成。為了象表示電阻、電容和三極管一樣，用圖形化的方式表示不同的邏輯函數(shù)，美國(guó)國(guó)家標(biāo)準(zhǔn)學(xué)會(huì)( the American National Standards Institute, ANSI )和美國(guó)電氣與電子工程師協(xié)會(huì)(the Institute of Electrical and Electronic Enginee

7、rs, IEEE) 在1984年制定了一個(gè)邏輯函數(shù)符號(hào)標(biāo)準(zhǔn)。如圖2-1所示。圖2-2是IEEE標(biāo)準(zhǔn)的“與”、“或”、“非”、“與非”、“或非”、“異或”、“異或非( 同或)”邏輯函數(shù)符號(hào)。11基本邏輯運(yùn)算復(fù)合邏輯運(yùn)算2.1.4 邏輯代數(shù)的公理、定理和規(guī)則邏輯代數(shù)系統(tǒng)有它的公理系統(tǒng)，公理系統(tǒng)不需要證明。邏輯代數(shù)系統(tǒng)的公理為邏輯代數(shù)的定理提供證明的依據(jù)。公理和定理也為邏輯代數(shù)證明提供演繹的數(shù)學(xué)基礎(chǔ)。1、公理系統(tǒng)公理1 0 - 1律 對(duì)于任意的邏輯變量A，有 A + 0 = AA 1 = AA + 1 = 1A 0 = 0公理2互補(bǔ)律 對(duì)于任意的邏輯變量A，存在唯一的A,使得 A + A = 1A

8、A = 0公理3交換律 對(duì)于任意的邏輯變量A和B，有 A + B = B + A A B = B A公理4結(jié)合律 對(duì)于任意的邏輯變量A、B和C，有 ( A + B ) + C = A + ( B + C ) ( A B ) C = A ( B C )公理5分配律 對(duì)于任意的邏輯變量A、B和C，有 A + ( B C ) = ( A + B )( A + C ) A ( B + C ) = A B + A C2、基本定理根據(jù)邏輯代數(shù)的公理，推導(dǎo)出邏輯代數(shù)的基本定理。定理1 0 + 0 = 01 + 0 = 1 0 + 1 = 11 + 1 = 1 00 = 010 = 0 01 = 011 =

9、13、邏輯代數(shù)的重要規(guī)則： 邏輯代數(shù)有三條重要規(guī)則，它們是代入規(guī)則、反演規(guī)則和對(duì)偶規(guī)則。這三條規(guī)則常常使用在邏輯表達(dá)式的運(yùn)算和變換中1 ) 邏輯函數(shù)的相等邏輯函數(shù)的相等 如果兩個(gè)邏輯函數(shù)： F1 = f1 (A1,A2,，An), F2 = f2 ( A1,A2,An) 對(duì)于邏輯變量A1，A2，An的任何一組取值，分別代入到邏輯函數(shù)F1、F2中去。邏輯函數(shù)F1、F2如果都同時(shí)為“0”或者同時(shí)為“1”，則稱邏輯函數(shù)F1與F2相等。2）代入規(guī)則 任何一個(gè)含有邏輯變量A的邏輯等式，如果將所有出現(xiàn)邏輯變量A的地方都用一個(gè)邏輯函數(shù)F代入，則該邏輯等式仍然成立，這個(gè)規(guī)則稱為代入規(guī)則。 根據(jù)上面邏輯函數(shù)的定

10、義，對(duì)于某一個(gè)具體的邏輯電路，輸出變量F的值取決于由輸入變量A1, A2, ，An構(gòu)成的2n個(gè)組合的取值。 另外，輸出邏輯變量F的值還取決于邏輯電路的結(jié)構(gòu)。 也就是，輸出邏輯變量F的值取決于：1、輸入變量A1A2，An的取值，2、邏輯電路的結(jié)構(gòu)，3、邏輯電路使用的門電路類型。 邏輯函數(shù)的定義說明一個(gè)邏輯電路能夠用一個(gè)邏輯函數(shù)F = f ( A1, A2, ，An )表示，即： 一個(gè)邏輯電路對(duì)應(yīng)一個(gè)邏輯函數(shù)。 討論邏輯函數(shù)也就是討論這個(gè)邏輯函數(shù)對(duì)應(yīng)的邏輯電路。 邏輯函數(shù)的定義實(shí)現(xiàn)了將一個(gè)具體的邏輯電路采用抽象的邏輯函數(shù)表示，這樣可以使用數(shù)學(xué)工具來研究邏輯電路。 在數(shù)字邏輯中使用邏輯函數(shù)研究邏輯電

11、路從兩個(gè)方面： 1、對(duì)某一個(gè)具體的邏輯電路進(jìn)行分析，使用邏輯函數(shù)寫出它的表達(dá)式，分析邏輯函數(shù)即分析相應(yīng)的邏輯電路； 2、使用邏輯函數(shù)進(jìn)行邏輯電路的設(shè)計(jì)。 邏輯電路的設(shè)計(jì)：一般是用文字表述的。根據(jù)文字表述，使用設(shè)計(jì)方法進(jìn)行邏輯電路設(shè)計(jì)，得到的是按要求設(shè)計(jì)的邏輯電路的邏輯函數(shù)。最后根據(jù)邏輯函數(shù)畫出按要求設(shè)計(jì)的邏輯電路。 因此，邏輯函數(shù)是邏輯電路分析和設(shè)計(jì)的重要數(shù)學(xué)工具。2.2.1邏輯函數(shù)表達(dá)式的基本形式1.“積之和”表達(dá)式“積之和”表達(dá)式是指表達(dá)式中的項(xiàng)是“與項(xiàng)”，項(xiàng)之間是“或”運(yùn)算。一個(gè)“與項(xiàng)”可以是由多個(gè)原變量或者反變量通過“與”運(yùn)算組成。在特殊的情況下“與項(xiàng)”是單個(gè)原變量或者反變量。例如，A

12、 B、A B C、C都是“與項(xiàng)”。A B + A B C + C是“積之和”表達(dá)式。2.“和之積”表達(dá)式“和之積”表達(dá)式是指表達(dá)式中的項(xiàng)是“或項(xiàng)”，項(xiàng)之間是“與”運(yùn)算。一個(gè)“或項(xiàng)”可以是由多個(gè)原變量或者反變量通過“或”運(yùn)算組成。例如，(A + B )、(A + B + C )都是“或項(xiàng)”。(A + B )(A + B + C )是“和之積”表達(dá)式。2.2.2 邏輯函數(shù)的標(biāo)準(zhǔn)形式 在邏輯函數(shù)的“與項(xiàng)”或者“或項(xiàng)”中，有些邏輯變量的個(gè)數(shù)與邏輯函數(shù)的變量個(gè)數(shù)相同，有些缺少其中的某些變量。另外在“與項(xiàng)”、“或項(xiàng)”中有些邏輯變量全部以原變量出現(xiàn)，有些全部以反變量出現(xiàn)，還有一些以原變量和反變量混合出現(xiàn)。

13、邏輯函數(shù)的標(biāo)準(zhǔn)形式是在邏輯函數(shù)表達(dá)式中全部的“與項(xiàng)”用“小項(xiàng)”組成。邏輯函數(shù)的另一種標(biāo)準(zhǔn)形式是在邏輯函數(shù)中全部的“或項(xiàng)”用“大項(xiàng)”組成。在邏輯電路的分析和設(shè)計(jì)中，邏輯函數(shù)時(shí)常用小項(xiàng)或者大項(xiàng)表示。 另外，邏輯函數(shù)有時(shí)也需要用小項(xiàng)或者大項(xiàng)表示。下面分別介紹小項(xiàng)與大項(xiàng)的概念，以及用小項(xiàng)或者大項(xiàng)表示的邏輯函數(shù)，即邏輯函數(shù)的標(biāo)準(zhǔn)形式。1.小項(xiàng)的定義和性質(zhì) 一個(gè)有n個(gè)變量的邏輯函數(shù)F，它的一個(gè)“與項(xiàng)”包含有n個(gè)變量，每個(gè)變量以原變量或者反變量的形式出現(xiàn)在這個(gè)“與項(xiàng)”中，且僅出現(xiàn)一次，則這個(gè)“與項(xiàng)”稱為該邏輯函數(shù)F的一個(gè)小項(xiàng)。 一個(gè)邏輯函數(shù)完全用小項(xiàng)表示，則稱該邏輯函數(shù)是小項(xiàng)標(biāo)準(zhǔn)形式。2.2.3邏輯函數(shù)表達(dá)

14、式的轉(zhuǎn)換 邏輯函數(shù)表達(dá)式的轉(zhuǎn)換是把邏輯函數(shù)表達(dá)式的基本形式轉(zhuǎn)換成標(biāo)準(zhǔn)形式。轉(zhuǎn)換方法是采用邏輯代數(shù)方法。在轉(zhuǎn)換中使用邏輯代數(shù)中的公理、定理和規(guī)則。1. “積之和”表達(dá)式轉(zhuǎn)換成小項(xiàng)表達(dá)式 “積之和”表達(dá)式轉(zhuǎn)換成用小項(xiàng)表示的標(biāo)準(zhǔn)形式，首先要將被轉(zhuǎn)換的邏輯函數(shù)轉(zhuǎn)換成“積之和”表達(dá)式。然后，在“積之和”表達(dá)式中使用X = X(Y + Y)，用以擴(kuò)充被轉(zhuǎn)換表達(dá)式中每一個(gè)“與項(xiàng)”中缺少的邏輯變量，使得每一個(gè)“與項(xiàng)”是小項(xiàng)。式中的X是某個(gè)“與項(xiàng)”中已有的邏輯變量，Y是擴(kuò)充的邏輯變量。在擴(kuò)充中如果有相同的小項(xiàng)產(chǎn)生出來，進(jìn)行合并。被轉(zhuǎn)換的表達(dá)式就是用小項(xiàng)表示的標(biāo)準(zhǔn)形式。 如果被轉(zhuǎn)換的邏輯函數(shù)是“和之積”表達(dá)式，則

15、需要首先把“和之積”表達(dá)式轉(zhuǎn)換成“積之和”表達(dá)式，然后再使用上述方法進(jìn)行轉(zhuǎn)換。2. “和之積”表達(dá)式轉(zhuǎn)換成大項(xiàng)表達(dá)式 “和之積”表達(dá)式轉(zhuǎn)換成大項(xiàng)的標(biāo)準(zhǔn)形式，首先要將被轉(zhuǎn)換的邏輯函數(shù)轉(zhuǎn)換成“和之積”表達(dá)式，然后在“和之積”表達(dá)式中使用X =(X + Y) ( X + Y )，用以擴(kuò)充被轉(zhuǎn)換表達(dá)式中的每一個(gè)“和之積”項(xiàng)中缺少的邏輯變量，使得每一個(gè)“和之積”是大項(xiàng)。式中X是某個(gè)“和之積”項(xiàng)中已有的變量，Y是擴(kuò)充的邏輯變量。在擴(kuò)充中如果有相同大項(xiàng)產(chǎn)生進(jìn)行合并。被轉(zhuǎn)換的表達(dá)式就是用大項(xiàng)表示的標(biāo)準(zhǔn)形式。 如前所述，一個(gè)邏輯函數(shù)的表達(dá)式有不同的形式。由于一個(gè)邏輯函數(shù)對(duì)應(yīng)一個(gè)邏輯電路，邏輯函數(shù)表達(dá)式的形式不同

16、，它們所代表的邏輯電路的結(jié)構(gòu)就不相同，但是在功能上又是相同的。邏輯函數(shù)表達(dá)式的形式越簡(jiǎn)單，它所對(duì)應(yīng)的邏輯電路就越簡(jiǎn)單。這是邏輯電路設(shè)計(jì)中要考慮的問題。為了減少邏輯電路的復(fù)雜性，降低成本，對(duì)邏輯函數(shù)表達(dá)式存在化簡(jiǎn)的問題。邏輯函數(shù)的化簡(jiǎn)是去掉表達(dá)式中多余的“與項(xiàng)”或者是“或項(xiàng)”，求得最簡(jiǎn)的邏輯函數(shù)。所謂最簡(jiǎn)的邏輯函數(shù)，一是邏輯函數(shù)表達(dá)式中的“與項(xiàng)”、“或項(xiàng)”個(gè)數(shù)最少，二是“與項(xiàng)”、“或項(xiàng)”中的邏輯變量的個(gè)數(shù)最少。 對(duì)邏輯函數(shù)化簡(jiǎn)目前使用最多的方法是代數(shù)化簡(jiǎn)法和卡諾圖化簡(jiǎn)法，下面分別進(jìn)行介紹。 2.2.1代數(shù)化簡(jiǎn)法 使用代數(shù)化簡(jiǎn)邏輯函數(shù)，需要熟記和靈活運(yùn)用邏輯代數(shù)中的公理、定理和規(guī)則。采用代數(shù)化簡(jiǎn)邏

17、輯函數(shù)的過程無一定的規(guī)律可循，化簡(jiǎn)過程中每一步的進(jìn)展取決于對(duì)公理、定理和規(guī)則熟練使用的程度。1.“積之和”表達(dá)式的化簡(jiǎn)；下面歸納了幾種化簡(jiǎn) “積之和”表達(dá)式的方法，可以在邏輯函數(shù)化簡(jiǎn)中參考。2.3.2卡諾圖化簡(jiǎn)法3.卡諾圖化簡(jiǎn)原理 使用卡諾圖化簡(jiǎn)邏輯函數(shù)，關(guān)鍵是如何把卡諾圖中的小項(xiàng)，即填“1”的方格進(jìn)行化簡(jiǎn)，直到把邏輯函數(shù)轉(zhuǎn)換成最簡(jiǎn)的“與或”表達(dá)式。因此，在卡諾圖上對(duì)邏輯函數(shù)進(jìn)行化簡(jiǎn)是找出一種方法對(duì)卡諾圖中的小項(xiàng)進(jìn)行化簡(jiǎn)。對(duì)卡諾圖中小項(xiàng)進(jìn)行化簡(jiǎn)使用到前面介紹的小方格相鄰的概念。 下面以三變量（A，B，C）為例說明卡諾圖化簡(jiǎn)的原理。5.卡諾圖化簡(jiǎn)邏輯函數(shù)舉例 例2-7 用卡諾圖將邏輯函數(shù)F（A,

18、 B, C, D） = m(0, 3, 5, 6, 7, 9, 11, 13, 15) 化簡(jiǎn)為最簡(jiǎn)“積之和”表達(dá)式。 解：第1步，畫出該邏輯函數(shù)的卡諾圖，把邏輯函數(shù)表示在卡諾圖上，如圖2-13所示。第2步，根據(jù)圖2-13把盡量滿足相鄰關(guān)系的2m個(gè)小方格作為一個(gè)卡諾圈。該邏輯函數(shù)有5個(gè)卡諾圈，它們都是質(zhì)蘊(yùn)涵項(xiàng)。然后檢查每一個(gè)質(zhì)蘊(yùn)涵項(xiàng)是不是首要蘊(yùn)涵項(xiàng)。對(duì)于是首要蘊(yùn)涵項(xiàng)。對(duì)于，它有一個(gè)m3不被覆蓋，因此是首要蘊(yùn)涵項(xiàng)。對(duì)于它有一個(gè)m6不被任何其他的質(zhì)蘊(yùn)涵項(xiàng)覆蓋，因此是首要蘊(yùn)涵項(xiàng)。同理也是首要蘊(yùn)涵項(xiàng)。因此，所求的最簡(jiǎn)邏輯函數(shù)為例2-8 用卡諾將圖邏輯函數(shù)F（A，B，C，D）= m(0,2,4,10,11

19、,14,15) 化簡(jiǎn)為最簡(jiǎn)“積之和”表達(dá)式。 解：第1步，畫出該函數(shù)的卡諾圖，把邏輯函數(shù)表示在卡諾圖上，如圖2-14所示。 解：這是一個(gè)用大項(xiàng)表示的邏輯函數(shù)。對(duì)于一個(gè)用大項(xiàng)表示的邏輯函數(shù)，它化簡(jiǎn)的結(jié)果應(yīng)當(dāng)是最簡(jiǎn)“和之積”式。為了在卡諾圖上把用大項(xiàng)表示的邏輯函數(shù)化簡(jiǎn)成最簡(jiǎn)“和之積”式，首先把用大項(xiàng)表示的邏輯函數(shù)轉(zhuǎn)換成用小項(xiàng)表示，即F（A, B, C, D）= m (1, 3, 5, 7, 8, 10, 11, 13,15)，將其表示在卡諾圖中，如圖2-15所示。然后在卡諾圖上對(duì)填“0”的小方格進(jìn)行化簡(jiǎn)，求出最簡(jiǎn)反函數(shù)F。再對(duì)最簡(jiǎn)反函數(shù)F使用反演規(guī)則，得到由“和之積”形式的最簡(jiǎn)邏輯函數(shù)。ABCD00 01 11 10000111101111111110000000 例2-9 使用卡諾圖將邏輯函數(shù)F（A，B，C，D）= M（0，2，4