1、第二章 邏輯代數(shù)基礎(chǔ),邏輯代數(shù)(布爾代數(shù))是按一定的邏輯關(guān)系進(jìn)行運(yùn)算的代數(shù)，是分析和設(shè)計(jì)數(shù)字電路的數(shù)學(xué)工具。在邏輯代數(shù)，只有和兩種邏輯值，有與、或、非三種基本邏輯運(yùn)算，還有與或、與非、與或非、異或幾種導(dǎo)出邏輯運(yùn)算。,2.1 概述,基本概念 邏輯：事物的因果關(guān)系 邏輯運(yùn)算的數(shù)學(xué)基礎(chǔ)：邏輯代數(shù) 在二值邏輯中的變量取值： 0/1,2.2 邏輯代數(shù)中的三種基本運(yùn)算,與（AND） 或（OR） 非（NOT）,以A=1表示開(kāi)關(guān)A合上，A=0表示開(kāi)關(guān)A斷開(kāi)；以Y=1表示燈亮，Y=0表示燈不亮；三種電路的因果關(guān)系不同：,1、與邏輯（與運(yùn)算）,與邏輯的定義：僅當(dāng)決定事件（Y）發(fā)生的所有條件（A，B，C，）均滿(mǎn)足時(shí)

2、，事件（Y）才能發(fā)生。表達(dá)式為：,如：開(kāi)關(guān)A，B串聯(lián)控制燈泡Y,兩個(gè)開(kāi)關(guān)必須同時(shí)接通，燈才亮。邏輯表達(dá)式為：,A、B都斷開(kāi)，燈不亮。,A斷開(kāi)、B接通，燈不亮。,A接通、B斷開(kāi)，燈不亮。,A、B都接通，燈亮。,這種把所有可能的條件組合及其對(duì)應(yīng)結(jié)果一一列出來(lái)的表格叫做真值表。,將開(kāi)關(guān)接通記作1，斷開(kāi)記作0；燈亮記作1，燈滅記作0?？梢宰鞒鋈缦卤砀駚?lái)描述與邏輯關(guān)系：,功能表,實(shí)現(xiàn)與邏輯的電路稱(chēng)為與門(mén)。與門(mén)的邏輯符號(hào)：,真值表,邏輯符號(hào),一般表示方式,與,條件同時(shí)具備，結(jié)果發(fā)生 Y=A AND B = A&B=AB=AB,2、或邏輯（或運(yùn)算）,或邏輯的定義：當(dāng)決定事件（Y）發(fā)生的各種條件（A，B，C，

3、)中，只要有一個(gè)或多個(gè)條件具備，事件（Y）就發(fā)生。表達(dá)式為：,如：開(kāi)關(guān)A，B并聯(lián)控制燈泡Y,兩個(gè)開(kāi)關(guān)只要有一個(gè)接通，燈就會(huì)亮。邏輯表達(dá)式為：,+,A、B都斷開(kāi)，燈不亮。,A斷開(kāi)、B接通，燈亮。,A接通、B斷開(kāi)，燈亮。,A、B都接通，燈亮。,實(shí)現(xiàn)或邏輯的電路稱(chēng)為或門(mén)?；蜷T(mén)的邏輯符號(hào)：,Y=A+B,真值表,功能表,邏輯符號(hào),或,條件之一具備，結(jié)果發(fā)生 Y= A OR B = A+B,3、非邏輯（非運(yùn)算）,非邏輯指的是邏輯的否定。當(dāng)決定事件（Y）發(fā)生的條件（A）滿(mǎn)足時(shí)，事件不發(fā)生；條件不滿(mǎn)足，事件反而發(fā)生。表達(dá)式為：,開(kāi)關(guān)A控制燈泡Y,實(shí)現(xiàn)非邏輯的電路稱(chēng)為非門(mén)。非門(mén)的邏輯符號(hào)：,Y=A ,A斷開(kāi)，燈

4、亮。,A接通，燈滅。,真值表,功能表,邏輯符號(hào),非,條件不具備，結(jié)果發(fā)生,幾種常用的復(fù)合邏輯運(yùn)算,與非 或非 與或非,幾種常用的復(fù)合邏輯運(yùn)算,異或 Y= A B,幾種常用的復(fù)合邏輯運(yùn)算,同或 Y= A B,2.3.1 基本公式 2.3.2 常用公式,2.3 邏輯代數(shù)的基本公式和常用公式,2.3.1 基本公式,根據(jù)與、或、非的定義，得表2.3.1的布爾恒等式,證明方法：推演 真值表,公式（17）的證明（公式推演法）：,公式（17）的證明（真值表法）：,1、邏輯代數(shù)的公式和定理,（1）常量之間的關(guān)系,（2）基本公式,分別令A(yù)=0及A=1代入這些公式，即可證明它們的正確性。,與,或,（3）基本定律,

5、利用真值表很容易證明這些公式的正確性。如證明AB=BA,(A+B)(A+C)=AA+AB+AC+BC,分配率A(B+C)=AB+AC,=A+AB+AC+BC,等冪率AA=A,=A(1+B+C)+BC,分配率A(B+C)=AB+AC,=A+BC,0-1率A+1=1,證明分配率：A+BC=(A+B)(A+C),證明：,2.3.2 若干常用公式,（4）常用公式,分配率A+BC=(A+B)(A+C),互補(bǔ)率A+A=1,0-1率A1=1,吸收公式：A+AB=A 并項(xiàng)公式：AB+AB=A，(A+B)(A+B)=A 消冗余因子：A+AB=A+B 消冗余項(xiàng)：AB+AC+BC=AB+AC 推論：AB+AC+BC

6、D=AB+AC,2.4 邏輯代數(shù)的基本定理,2.4.1 代入定理 -在任何一個(gè)包含A的邏輯等式中，若以另外一個(gè)邏輯式代入式中A的位置，則等式依然成立。,2.4.1 代入定理,應(yīng)用舉例： 式（17） A+BC = (A+B)(A+C) A+B(CD) = (A+B)(A+CD) = (A+B)(A+C)(A+D),2.4.1 代入定理,應(yīng)用舉例： 式 （8）,2.4 邏輯代數(shù)的基本定理,2.4.2 反演定理 -對(duì)任一邏輯式,變換順序 先括號(hào)，然后乘，最后加,不屬于單個(gè)變量的上的反號(hào)保留不變,2.4.2 反演定理,應(yīng)用舉例：,2.4.3 對(duì)偶定理,對(duì)偶規(guī)則：對(duì)于任何一個(gè)邏輯表達(dá)式Y(jié)，如果將表達(dá)式中

7、的所有“”換成“”，“”換成“”，“0”換成“1”，“1”換成“0”，而變量保持不變，則可得到的一個(gè)新的函數(shù)表達(dá)式Y(jié)D，YD稱(chēng)為函Y的對(duì)偶函數(shù)。這個(gè)規(guī)則稱(chēng)為對(duì)偶規(guī)則。,例如：,對(duì)偶規(guī)則的意義在于：如果兩個(gè)函數(shù)相等，則它們的對(duì)偶函數(shù)也相等。利用對(duì)偶規(guī)則,可以使要證明及要記憶的公式數(shù)目減少一半。例如：,注意：在運(yùn)用反演規(guī)則和對(duì)偶規(guī)則時(shí)，必須按照邏輯運(yùn)算的優(yōu)先順序進(jìn)行：先算括號(hào)，接著與運(yùn)算，然后或運(yùn)算，最后非運(yùn)算，否則容易出錯(cuò)。,2.5.1 邏輯函數(shù) Y=F(A,B,C,) -若以邏輯變量為輸入，運(yùn)算結(jié)果為輸出，則輸入變量值確定以后，輸出的取值也隨之而定。輸入/輸出之間是一種函數(shù)關(guān)系。 注：在二值邏

8、輯中， 輸入/輸出都只有兩種取值0/1。,2.5 邏輯函數(shù)及其表示方法,2.5.2 邏輯函數(shù)的表示方法,真值表 邏輯式 邏輯圖 波形圖 卡諾圖 計(jì)算機(jī)軟件中的描述方式 各種表示方法之間可以相互轉(zhuǎn)換,真值表,真值表：是由變量的所有可能取值組合及其對(duì)應(yīng)的函數(shù)值所構(gòu)成的表格。,真值表列寫(xiě)方法：每一個(gè)變量均有0、1兩種取值，n個(gè)變量共有2n種不同的取值，將這2n種不同的取值按順序（一般按二進(jìn)制遞增規(guī)律）排列起來(lái)，同時(shí)在相應(yīng)位置上填入函數(shù)的值，便可得到邏輯函數(shù)的真值表。,例如：當(dāng)A=B=1、或則B=C=1時(shí)，函數(shù)Y=1；否則Y=0。,邏輯式 將輸入/輸出之間的邏輯關(guān)系用與/或/非的運(yùn)算式表示就得到邏輯式

9、。,函數(shù)的標(biāo)準(zhǔn)與或表達(dá)式的列寫(xiě)方法：將函數(shù)的真值表中那些使函數(shù)值為1的最小項(xiàng)相加，便得到函數(shù)的標(biāo)準(zhǔn)與或表達(dá)式。,邏輯圖,邏輯圖：是由表示邏輯運(yùn)算的邏輯符號(hào)所構(gòu)成的圖形。 此表示方法更接近工程實(shí)際。,波形圖 將輸入變量所有取值可能與對(duì)應(yīng)輸出按時(shí)間順序排列起來(lái)畫(huà)成時(shí)間波形。,如：,1,1,1,卡諾圖,卡諾圖：是由表示變量的所有可能取值組合的小方格所構(gòu)成的圖形。,邏輯函數(shù)卡諾圖的填寫(xiě)方法：在那些使函數(shù)值為1的變量取值組合所對(duì)應(yīng)的小方格內(nèi)填入1，其余的方格內(nèi)填入0，便得到該函數(shù)的卡諾圖。,EDA中的描述方式 HDL (Hardware Description Language) VHDL (Very

10、High Speed Integrated Circuit ) Verilog HDL EDIF DTIF 。,P4501,舉例：舉重裁判電路,各種表現(xiàn)形式的相互轉(zhuǎn)換：,真值表 邏輯式 例：奇偶判別函數(shù)的真值表 A=0,B=1,C=1使 ABC=1 A=1,B=0,C=1使 ABC=1 A=1,B=1,C=0使 ABC =1 這三種取值的任何一種都使Y=1, 所以 Y= ?,真值表 邏輯式： 找出真值表中使 Y=1 的輸入變量取值組合。 每組輸入變量取值對(duì)應(yīng)一個(gè)乘積項(xiàng)，其中取值為1的寫(xiě)原變量，取值為0的寫(xiě)反變量。 將這些變量相加即得 Y。 把輸入變量取值的所有組合逐個(gè)代入邏輯式中求出Y，列表,

11、邏輯式 邏輯圖 1. 用圖形符號(hào)代替邏輯式中的邏輯運(yùn)算符。,邏輯式 邏輯圖 1. 用圖形符號(hào)代替邏輯式中的邏輯運(yùn)算符。 2. 從輸入到輸出逐級(jí)寫(xiě)出每個(gè)圖形符號(hào)對(duì)應(yīng)的邏輯運(yùn)算式。,波形圖 真值表,練習(xí)：列寫(xiě)真值表,最小項(xiàng) m： m是乘積項(xiàng) 包含n個(gè)因子 n個(gè)變量均以原變量和反變量的形式在m中出現(xiàn)一次,對(duì)于n變量函數(shù) 有2n個(gè)最小項(xiàng),2.5.3 邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式 最小項(xiàng)之和 最大項(xiàng)之積,最小項(xiàng)舉例：,兩變量A, B的最小項(xiàng) 三變量A,B,C的最小項(xiàng),最大項(xiàng)：,M是相加項(xiàng)； 包含n個(gè)因子。 n個(gè)變量均以原變量和反變量的形式在M中出現(xiàn)一次。 如：兩變量A, B的最大項(xiàng),對(duì)于n變量函數(shù) 2n個(gè),邏

12、輯函數(shù)最小項(xiàng)之和的形式：,例：,2.6 邏輯函數(shù)的化簡(jiǎn)法,邏輯函數(shù)的最簡(jiǎn)形式 最簡(jiǎn)與或 -包含的乘積項(xiàng)已經(jīng)最少，每個(gè)乘積項(xiàng)的因子也最少，稱(chēng)為最簡(jiǎn)的與-或邏輯式。,2.6.1公式化簡(jiǎn)法 反復(fù)應(yīng)用基本公式和常用公式，消去多余的乘積項(xiàng)和多余的因子。 例：,2.6.1公式化簡(jiǎn)法 反復(fù)應(yīng)用基本公式和常用公式，消去多余的乘積項(xiàng)和多余的因子。 例：,2.6.1公式化簡(jiǎn)法 反復(fù)應(yīng)用基本公式和常用公式，消去多余的乘積項(xiàng)和多余的因子。 例：,2.6.1公式化簡(jiǎn)法 反復(fù)應(yīng)用基本公式和常用公式，消去多余的乘積項(xiàng)和多余的因子。 例：,2.6.1公式化簡(jiǎn)法 反復(fù)應(yīng)用基本公式和常用公式，消去多余的乘積項(xiàng)和多余的因子。 例：

13、,2.6.2 卡諾圖化簡(jiǎn)法,邏輯函數(shù)的卡諾圖表示法 實(shí)質(zhì)：將邏輯函數(shù)的最小項(xiàng)之和的以圖形的方式表示出來(lái) 以2n個(gè)小方塊分別代表 n 變量的所有最小項(xiàng)，并將它們排列成矩陣，而且使幾何位置相鄰的兩個(gè)最小項(xiàng)在邏輯上也是相鄰的（只有一個(gè)變量不同），就得到表示n變量全部最小項(xiàng)的卡諾圖。,最小項(xiàng) m： m是乘積項(xiàng) 包含n個(gè)因子 n個(gè)變量均以原變量和反變量的形式在m中出現(xiàn)一次,對(duì)于n變量函數(shù) 有2n個(gè)最小項(xiàng),2.5.3 邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式 最小項(xiàng)之和 最大項(xiàng)之積,最小項(xiàng)的編號(hào)：,最小項(xiàng)舉例：,兩變量A, B的最小項(xiàng) 三變量A,B,C的最小項(xiàng),最小項(xiàng)的性質(zhì),在輸入變量任一取值下，有且僅有一個(gè)最小項(xiàng)的值為1

14、。 任何兩個(gè)最小項(xiàng)之積為0 。 全體最小項(xiàng)之和為1 。 兩個(gè)相鄰的最小項(xiàng)之和可以合并，消去一對(duì)因子，只留下公共因子。 -相鄰：僅一個(gè)變量不同的最小項(xiàng) 如,（3）最小項(xiàng)的性質(zhì)：,任意一個(gè)最小項(xiàng)，只有一組變量取值使其值為1。,全部最小項(xiàng)的和必為1。,ABC,ABC,任意兩個(gè)不同的最小項(xiàng)的乘積必為0。,邏輯函數(shù)最小項(xiàng)之和的形式：,例：,利用公式 可將任何一個(gè)函數(shù)化為,邏輯函數(shù)最小項(xiàng)之和的形式：,例：,利用公式 可將任何一個(gè)函數(shù)化為,邏輯函數(shù)最小項(xiàng)之和的形式：,例：,利用公式 可將任何一個(gè)函數(shù)化為,邏輯函數(shù)最小項(xiàng)之和的形式：,例：,邏輯函數(shù)最小項(xiàng)之和的形式：,例：,邏輯函數(shù)最小項(xiàng)之和的形式：,例：,表

15、示最小項(xiàng)的卡諾圖,二變量卡諾圖 三變量的卡諾圖,4變量的卡諾圖,表示最小項(xiàng)的卡諾圖,二變量卡諾圖 三變量的卡諾圖,4變量的卡諾圖,表示最小項(xiàng)的卡諾圖,2變量卡諾圖 3變量的卡諾圖,4變量的卡諾圖,5變量的卡諾圖,用卡諾圖表示邏輯函數(shù),將函數(shù)表示為最小項(xiàng)之和的形式 在卡諾圖上與這些最小項(xiàng)對(duì)應(yīng)的位置上添入1，其余地方添0。,2.3.4 邏輯函數(shù)在卡諾圖中的表示,（1）邏輯函數(shù)是以真值表或者以最小項(xiàng)表達(dá)式給出：在卡諾圖上那些與給定邏輯函數(shù)的最小項(xiàng)相對(duì)應(yīng)的方格內(nèi)填入1，其余的方格內(nèi)填入0。,m1,m3,m4,m7,m6,m11,m15,m14,用卡諾圖表示邏輯函數(shù),例：,用卡諾圖表示邏輯函數(shù),用卡諾圖

16、化簡(jiǎn)函數(shù),依據(jù)：具有相鄰性的最小項(xiàng)可合并，消去不同因子。 在卡諾圖中，最小項(xiàng)的相鄰性可以從圖形中直觀地反映出來(lái)。,一、卡諾圖的性質(zhì),（1）任何兩個(gè)（21個(gè)）標(biāo)1的相鄰最小項(xiàng)，可以合并為一項(xiàng)，并消去一個(gè)變量（消去互為反變量的因子，保留公因子）。,（2）任何4個(gè)（22個(gè)）標(biāo)1的相鄰最小項(xiàng)，可以合并為一項(xiàng)，并消去2個(gè)變量。,BD,（3）任何8個(gè)（23個(gè)）標(biāo)1的相鄰最小項(xiàng)，可以合并為一項(xiàng)，并消去3個(gè)變量。,B,卡諾圖化簡(jiǎn)的原則,化簡(jiǎn)后的乘積項(xiàng)應(yīng)包含函數(shù)式的所有最小項(xiàng)，即覆蓋圖中所有的1。 乘積項(xiàng)的數(shù)目最少，即圈成的矩形最少。 每個(gè)乘積項(xiàng)因子最少，即圈成的矩形最大。,卡諾圖化簡(jiǎn)的基本步驟,邏輯表達(dá)式或真

17、值表,卡諾圖,1,1,合并最小項(xiàng),圈越大越好，但每個(gè)圈中標(biāo)的方格數(shù)目必須為個(gè)。同一個(gè)方格可同時(shí)畫(huà)在幾個(gè)圈內(nèi)，但每個(gè)圈都要有新的方格，否則它就是多余的。不能漏掉任何一個(gè)標(biāo)的方格。,最簡(jiǎn)與或表達(dá)式,C D,冗余項(xiàng),2,2,3,3,將代表每個(gè)圈的乘積項(xiàng)相加,例：,A,BC,例：,A,BC,例：,A,BC,例：,化 簡(jiǎn) 結(jié) 果 不 唯 一,例：,AB,CD,例：,AB,CD,兩點(diǎn)說(shuō)明：, 在有些情況下，最小項(xiàng)的圈法不只一種，得到的各個(gè)乘積項(xiàng)組成的與或表達(dá)式各不相同，哪個(gè)是最簡(jiǎn)的，要經(jīng)過(guò)比較、檢查才能確定。,不是最簡(jiǎn),最簡(jiǎn), 在有些情況下，不同圈法得到的與或表達(dá)式都是最簡(jiǎn)形式。即一個(gè)函數(shù)的最簡(jiǎn)與或表達(dá)式

18、不是唯一的。,最簡(jiǎn),最簡(jiǎn),約束項(xiàng) 任意項(xiàng) 邏輯函數(shù)中的無(wú)關(guān)項(xiàng)：約束項(xiàng)和任意項(xiàng)可以寫(xiě)入函數(shù)式，也可不包含在函數(shù)式中，因此統(tǒng)稱(chēng)為無(wú)關(guān)項(xiàng)。,在邏輯函數(shù)中，對(duì)輸入變量取值的限制，在這些取值下為1的最小項(xiàng)稱(chēng)為約束項(xiàng),在輸入變量某些取值下，函數(shù)值為1或?yàn)?不影響邏輯電路的功能，在這些取值下為1的最小項(xiàng)稱(chēng)為任意項(xiàng),2.7具有無(wú)關(guān)項(xiàng)的邏輯函數(shù)及其化簡(jiǎn)2.7.1 約束項(xiàng)、任意項(xiàng)和邏輯函數(shù)式中的無(wú)關(guān)項(xiàng),2.7.2 無(wú)關(guān)項(xiàng)在化簡(jiǎn)邏輯函數(shù)中的應(yīng)用,合理地利用無(wú)關(guān)項(xiàng)，可得更簡(jiǎn)單的化簡(jiǎn)結(jié)果。 加入（或去掉）無(wú)關(guān)項(xiàng)，應(yīng)使化簡(jiǎn)后的項(xiàng)數(shù)最少，每項(xiàng)因子最少 從卡諾圖上直觀地看，加入無(wú)關(guān)項(xiàng)的目的是為矩形圈最大，矩形組合數(shù)最少。,1

19、、含隨意項(xiàng)的邏輯函數(shù),例如：判斷一位十進(jìn)制數(shù)是否為偶數(shù)。,說(shuō) 明,0,0 1 1 1,1,0 1 1 0,0,0 1 0 1,1,0 1 0 0,0,0 0 1 1,1,0 0 1 0,0,1 0 0 1,0,0 0 0 1,1,1 0 0 0,1,0 0 0 0,Y,A B C D,Y,A B C D,不會(huì)出現(xiàn),不會(huì)出現(xiàn),不會(huì)出現(xiàn),不會(huì)出現(xiàn),不會(huì)出現(xiàn),不會(huì)出現(xiàn),1 1 1 1,1 1 1 0,1 1 0 1,1 1 0 0,1 0 1 1,1 0 1 0,輸入變量A，B，C，D取值為00001001時(shí)，邏輯函數(shù)Y有確定的值，根據(jù)題意，偶數(shù)時(shí)為1，奇數(shù)時(shí)為0。,A，B，C，D取值為1010 1111的情況不會(huì)出現(xiàn)或不允許出現(xiàn)，對(duì)應(yīng)的最小項(xiàng)屬于隨意項(xiàng)。用符號(hào)“”、“”或“d”表示。,隨意項(xiàng)之和構(gòu)成的邏輯表達(dá)式叫做 隨意條件或約束條件，用一個(gè)值恒為 0 的條件等式表示。,含有隨意條件的邏輯函數(shù)可以表示成如下形式：,2、含隨意項(xiàng)的邏輯函數(shù)的化簡(jiǎn),在邏輯函數(shù)的化簡(jiǎn)中，充分利用隨意項(xiàng)可以得到更加簡(jiǎn)單的邏輯表達(dá)式，因而其相應(yīng)的邏輯電路也更簡(jiǎn)單。在化簡(jiǎn)過(guò)程中，