第七章命題邏輯與布爾代數(shù)7.1命題邏輯的基本概念7.1.1命題與真值表定義7.1凡能分辨真、假的語(yǔ)句稱命題命題其實(shí)就是一種敘述，命題的敘述根據(jù)事實(shí)的狀況，該命題有可能是真或是假，但命題不會(huì)同時(shí)為真又同時(shí)為假.在自然語(yǔ)言中有些語(yǔ)句是能分辨真、假的，有些則不能如：浙江省的省會(huì)城市是杭州.第六屆世界合唱節(jié)在紹興舉行.第八屆全國(guó)殘疾人運(yùn)動(dòng)會(huì)在杭州圓滿閉幕今天是星期日.1+1=2以上的語(yǔ)句能分辨真、假，因此是命題.一般而言，自然語(yǔ)言中的陳述句大都能分辨真、假，因此都是命題.而下面的一些語(yǔ)句如：請(qǐng)不要隨地吐痰.明天會(huì)下雨嗎？一路順風(fēng).以上語(yǔ)句不能分辨真、假，因此不是命題.一般而言，自然語(yǔ)言中的祈使句、感嘆句及疑問(wèn)句等都不是命題.命題主要分兩類(lèi)：①簡(jiǎn)單命題；②復(fù)合命題.簡(jiǎn)單命題就是這個(gè)命題不能再細(xì)分成幾個(gè)子命題的合成.例如：花是紅的.天是藍(lán)的.很明顯，上面的命題無(wú)法再細(xì)分成子命題的合成，所以是簡(jiǎn)單命題.如下面的語(yǔ)句不是簡(jiǎn)單命題：花是紅的，天是藍(lán)的.(2)昨天下雨，地面是濕的.以上命題均可以分解成更為簡(jiǎn)單的命題：花是紅的天是藍(lán)的昨天下雨地面是濕的復(fù)合命題就是由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞所構(gòu)成的命題一般常用的聯(lián)結(jié)詞有否定、與、或者、蘊(yùn)含和等價(jià)，其對(duì)應(yīng)的符號(hào)加、A、V、T和f.例如有兩個(gè)如下的簡(jiǎn)單命題：q：下雨r：地濕則：qar:下雨且地濕「qvr:不下雨或地濕上述量份額邏輯命題就是典型的復(fù)合命題.下面我們來(lái)分別介紹一下這五中關(guān)聯(lián)詞.否定否定聯(lián)結(jié)詞是一元聯(lián)結(jié)詞，它的作用對(duì)象僅為一個(gè)命題.否定聯(lián)結(jié)詞作用于一個(gè)命題后使該命題出現(xiàn)相反的語(yǔ)意.如有命題：今天下雨，而加上否定關(guān)聯(lián)詞后即成為：今天不下雨.在命題邏輯中將此聯(lián)結(jié)詞予以符號(hào)化，用「P表示命題P的否定命題.并且并且聯(lián)結(jié)詞是二元聯(lián)結(jié)詞，它的作用對(duì)象為兩個(gè)命題，該聯(lián)結(jié)詞作用于兩個(gè)命題后可將兩個(gè)命題用“并且”聯(lián)結(jié)于一起.如有命題：“今天我聽(tīng)音樂(lè)”和“今天我看電影”，則用聯(lián)結(jié)詞“并且”將其聯(lián)結(jié)為：“今天我聽(tīng)音樂(lè)并且今天我看電影”.在命題邏輯中可將聯(lián)結(jié)詞符號(hào)化，PaQ稱為P與Q的合取式，而P、Q分別叫此合取式的合取項(xiàng).或者或者聯(lián)結(jié)詞是二元聯(lián)結(jié)詞，它的作用對(duì)象為兩個(gè)命題，該聯(lián)結(jié)詞作用于兩個(gè)命題后可將兩個(gè)命題用“或者”聯(lián)結(jié)于一起如有命題“今天我看書(shū)”，“今天我寫(xiě)字”，則聯(lián)結(jié)詞“或者”將其聯(lián)結(jié)為“今天我看書(shū)或今天我寫(xiě)字”.在命題邏輯中可將聯(lián)結(jié)詞符號(hào)化，PvQ稱為命題P與Q的析取式，而P、Q分別叫此析取式的析取項(xiàng).蘊(yùn)含蘊(yùn)含聯(lián)結(jié)詞是二元聯(lián)結(jié)詞，它的作用對(duì)象為兩個(gè)命題.該聯(lián)結(jié)詞作用于兩個(gè)命題后可將兩個(gè)命題用“如果…則…”聯(lián)結(jié)于一起.如有命題：“明天下雨”，“明天取消旅游”，則蘊(yùn)含聯(lián)結(jié)詞將其聯(lián)結(jié)為：“如果明天下雨，則明天取消旅游”.在命題邏輯中可將聯(lián)結(jié)詞符號(hào)化，PTQ稱為命題P與Q的蘊(yùn)含式，或稱P蘊(yùn)含Q.而P稱為PTQ的前件，Q稱為PTQ的后件.在自然語(yǔ)言中蘊(yùn)含式的前件與后件一般具有因果關(guān)系.等價(jià)等價(jià)聯(lián)結(jié)詞是二元聯(lián)結(jié)詞，它的作用對(duì)象為兩個(gè)命題，該聯(lián)結(jié)詞作用于兩個(gè)命題后可將兩個(gè)命題用“等價(jià)”聯(lián)結(jié)于一起.如命題“5+3=8”，“8-5=3”，等價(jià)聯(lián)結(jié)詞將其聯(lián)結(jié)為“5+3=8等價(jià)于8-5=3”.在命題邏輯中可將聯(lián)結(jié)詞符號(hào)化，P?Q稱為命題P與Q的等價(jià)式，而P、Q分別叫此等價(jià)式的兩端.當(dāng)命題q和,均賦真或假值后，我們五個(gè)聯(lián)結(jié)詞為例，表7.1為這些復(fù)合命題的真值表.在表中，1代表該命題為真，0代表該命題為假.表7.1—個(gè)真值表的例子qr「qqarqvrqTr「qvrqIr001001110110111010001000110111117.1.2范式我們有自然語(yǔ)言出發(fā)歸結(jié)出命題于命題聯(lián)結(jié)詞連個(gè)概念，并將其符號(hào)化，從而構(gòu)成初步的符號(hào)體系.而這種系統(tǒng)建立的首要步驟是構(gòu)建形式化的命題公式.定義7.2（命題公式）命題公式（或稱命題邏輯合式公式，簡(jiǎn)稱公式）可按如下規(guī)則生成：（1）命題變?cè)c命題常元是公式（2）如果P是公式則（-P）是公式（3）如果P，Q是公式，則（PVQ），（PaQ），（PTQ）及（PIQ）是公式（4）公式由且僅由有限次應(yīng)用（1）、（2）、⑶而得從形式上看，命題公式是由命題變?cè)⒚}常元、五個(gè)聯(lián)結(jié)詞以及圓括號(hào)按一定規(guī)則所組成的字符串.按照上述定義，下面的字符串是公式：(「(P—Q))(PT(RAQ))((PAQ)T(RAQ))而下面的字符串則不是公式：((「P)「TQ)(PQvR)(PT(AR))為了使表示簡(jiǎn)單化，在公式中的圓括號(hào)是可以省略的，其規(guī)則如下：規(guī)定五個(gè)聯(lián)結(jié)詞的結(jié)合能力的強(qiáng)弱順序?yàn)椋骸?、A、v、T及I，其中「為最強(qiáng)，—為最弱，在公式中凡符合此順序者，括號(hào)均可省去.具有相同結(jié)合能力的聯(lián)結(jié)詞，按其出現(xiàn)的先后順序，先出現(xiàn)者先聯(lián)結(jié)，凡符合此要求者，其括號(hào)均可除去.最外層括號(hào)可省去.例7.1.1將下面的公式省去括號(hào)：「((Pa(「(Q))vR)T((RvP)vR))有了命題公式后可以用它表示自然語(yǔ)言及形式思維的多種形態(tài).下面用一些例子表示.例7.1.2“若明天上午不是雨夾雪，我將去學(xué)校”，在此語(yǔ)句中可以令：P:明天上午下雨Q:明天上午下雪R:我去學(xué)校此語(yǔ)句可以用命題公式表示如下：「(PAQ)TR例7.1.3“明天我將風(fēng)雨無(wú)阻去學(xué)校”，在此語(yǔ)句中可以令：P:明天下雨Q:明天刮風(fēng)R:我去學(xué)校此語(yǔ)句可以用命題公式表示如下：PAQvPA「Qv「PAQv「PA「QTR一般而言，將自然語(yǔ)言轉(zhuǎn)換成為命題公式須經(jīng)過(guò)下列三個(gè)步驟：首先找出語(yǔ)句中的簡(jiǎn)單命題并以命題標(biāo)識(shí)符表示之其次確定命題間的聯(lián)結(jié)詞最后用命題公式的定義規(guī)則組成一個(gè)合式公式.命題公式的形式是多種多樣的，這對(duì)我們的研究帶來(lái)諸多不便，為此須建立一種統(tǒng)一的、標(biāo)準(zhǔn)的公式-范式.定義7.3析取范式是范式的一種，它具有如下之形式：析取范式是一個(gè)析取式析取式中的每個(gè)析取項(xiàng)是一個(gè)合取式這個(gè)合取式只包含命題變?cè)懊}變?cè)穸?下面的公式都是析取范式：(「PaQ)v(Pa「Q)「Pv(PAQ)v(PAR)任意一個(gè)命題公式都可以化歸成為析取范式，其化歸步驟如下：?用AtB=「AvB和A—■B=(AaB)v(「Aa「B)，將公式中出現(xiàn)的一T及—■之處化歸成僅出現(xiàn)有A、v和「?用「(AvB)=「AA「B和「(AAB)=「Av「B將否定符深入至命題變?cè)⑹褂谩浮窤=A減少否定符號(hào)，使命題變?cè)胺穸ǚ?hào)最多為一個(gè)?由分配律Aa(BvC)=(AaB)v(AaC)Av(BaC)=(AvB)a(AvC)Ar(BrC)=(ArB)r(ArC)將公式最終化歸成析取范式.例7.1.4試化歸公式TPvQ)I(PaQ)為析取范式.解：按照前面所規(guī)定的化歸工程：消去聯(lián)結(jié)詞r與1:「(PvQ)I(PaQ)=(「(pvQ)a(PaQ))v((PvQ)a「(PaQ))將否定符深入至命題變?cè)?「(pvQ)a(PaQ))v((PvQ)a「(PaQ))=((「pa「Q)a(PaQ))v((PvQ)a(「Pv「Q))用分配律最后化歸成析取范式：((「pa「Q)a(PaQ))v((PvQ)a(「Pv「Q))=(「Pa「QaPaQ)v(Pa「P)v(「PaQ)v(Pa「Q)v(Qv「Q)因此得到析取范式.析取范式是一種標(biāo)準(zhǔn)公式，它具有形式簡(jiǎn)單、化歸方便的特點(diǎn)，但它也有不足，其中最大的缺點(diǎn)是不唯一性與標(biāo)準(zhǔn)性，因此需要在其基礎(chǔ)上進(jìn)一步化歸成具有相對(duì)唯一性、標(biāo)準(zhǔn)性的公式，這就是主析取范式.定義7.4主析取范式是析取范式的一種，它具有如下具體的形式：主析取范式是一個(gè)析取范式在主析取范式的每個(gè)析取項(xiàng)中，該公式的所有命題變?cè)霈F(xiàn)，它們或以命題變?cè)蛞悦}變?cè)穸ǖ男问匠霈F(xiàn)，且僅出現(xiàn)一次.下面的公式都是主析取范式：(「PaQ)v(Pa「Q)(PaQa「R)v(「PaQaR)任意一個(gè)命題公式均可以化歸為主析取范式，其化歸步驟如下：化歸為析取范式除去所有為假的析取項(xiàng)，即析取項(xiàng)中出現(xiàn)有Pa「P形式的項(xiàng)析取項(xiàng)中用公式「「A=A將出現(xiàn)有多個(gè)相同命題變?cè)?或其否定)化簡(jiǎn)成僅出現(xiàn)一次析取項(xiàng)中若某些命題元沒(méi)有出現(xiàn)，則用公式Pa(Qv「Q)=P在析取項(xiàng)中補(bǔ)充，再用分配律將其展開(kāi)成兩個(gè)析取項(xiàng)并除去相同析取項(xiàng)例7.1.5試化歸公式(Pa(PrQ))vQ為主析取范式.化歸為析取范式：(Pa(PrQ))vQ=(Pa「P)v(PaQ)vQ除去假析取項(xiàng)：(Pa「P)v(PaQ)vQ=(PaQ)vQ在析取項(xiàng)中將多個(gè)相同命題變?cè)瘹w成一個(gè)：無(wú)補(bǔ)充不足命題變?cè)⒊ハ嗤鋈№?xiàng)：(PaQ)vQ=(paQ)v((Pv「P)aQ)=(PaQ)v(PaQ)v(「PaQ)=(PaQ)v(「PaQ)因此得到主析取范式.與析取范式相對(duì)應(yīng)，我們可以定義合取范式：定義7.5合取范式是范式的一種，它具有如下的形式；合取范式是一個(gè)合取式合取式中的每個(gè)合取項(xiàng)是一個(gè)析取式這個(gè)析取式只包含命題變?cè)懊}變?cè)穸ㄏ旅娴墓蕉际呛先》妒剑?「Pv「P)aQ(「PvQ)a(Pv「Q)任意一個(gè)命題都可以化歸為合取范式，其化歸步驟如下：?用ATB—「AvB和A。^B=(AaB)v(「Aa—B)，將公式中出現(xiàn)的一)及之處化歸成僅出現(xiàn)有a、v和—?用「(AvB)—「Aa—B和「(Aab)—「Av—B將否定符深入至命題變兀并使用「「a—A減少否定符號(hào)，使命題變?cè)胺穸ǚ?hào)最多為一個(gè)?由分配律Aa(BvC)=(AaB)v(AaC)Av(BaC)=(AvB)a(AvC)AT(BTC)—(ATB)T(ATC)將公式最終化歸成合取范式.例7.1.6試化歸公式Qv—(PTQ)v—(PvQ)為合取范式.解：消去聯(lián)結(jié)詞Qv「(PTQ)v—(PvQ)—Qv—(—PvQ)v—(PvQ)將否定符號(hào)深入Qv「(PTQ)v「(PvQ)—Qv(Pa「Q)v(—Pa「q)用分配律化歸成合取范式Qv—(PTQ)v—(PvQ)—(QvPv—P)a(Qv—Q)因此得到合取范式.與析取范式類(lèi)似，對(duì)合取范式可進(jìn)一步化歸成相對(duì)唯一性、標(biāo)準(zhǔn)性的公式稱主合取范式.定義7.6主合取范式是合取范式的一種，它具有如下之形式：主合取范式是一個(gè)合取范式在主合取范式的每個(gè)合取項(xiàng)中，該公式的所有命題變?cè)霈F(xiàn)，它們或以命題變?cè)蛞云浞穸ǖ男问匠霈F(xiàn)，且僅出現(xiàn)一次.下面的公式都是主合取范式：(—PvQ)a(PvQ)(—PvQ)任意一個(gè)命題公式都可以化歸為合取范式，其化歸步驟如下：化歸為合取范式除去所有為真的合取項(xiàng)，即合取項(xiàng)中出現(xiàn)有Pv—P形式的項(xiàng)合取項(xiàng)中用公式PvP—P將出現(xiàn)多個(gè)相同命題變?cè)?或其否定)化簡(jiǎn)成僅出現(xiàn)一次合取項(xiàng)中若某些命題變?cè)獩](méi)有出現(xiàn)，則用公式Pv(Qa—Q)=P在合取項(xiàng)中補(bǔ)充，在用分配律將其展開(kāi)成兩個(gè)合取項(xiàng)并除去相同的合取項(xiàng).例7.1.7試化歸公式(—PTRvP)a(qIp)為主合取范式.解：(1)化歸為合取式：(—PTRvP)a(QIP)=(PvRvP)a(—QvP)a(—PvQ)(2)除去為真的合取式：無(wú)(3)消去多余的命題變?cè)?PvRvP)a(—QvP)a(—PvQ)=(PvR)a(—QvP)a(—PvQ)補(bǔ)充不足的命題變?cè)?—PTRvP)a(QiP)=(Pv—QvR)a(Pv—Qv—R)a(PvQvR)a(PvQv—R)a(—PvQvR)a(—PvQv—R)因此得到主合取范式.習(xí)題7.1下列那些語(yǔ)句是命題？合肥是安徽的省會(huì)城市.2+3=5.x+2=11.全體起立.回答這一問(wèn)題.對(duì)每一對(duì)實(shí)數(shù)x、y，都有xyyx.別過(guò)去.幾點(diǎn)了？2是無(wú)理數(shù).令P、Q為如下命題：P：本周我買(mǎi)了一張彩票.Q:星期五我中了百萬(wàn)大獎(jiǎng).把下列各命題表達(dá)為漢語(yǔ)句子：(1)P(2)PQ(3)PQ(4)PQ⑸PQ(6)PQ(7)PQ(8)P(PQ)3.寫(xiě)出1下列公式的真值表⑴P(PQ)⑵(PQ)(PR)⑶(PQ)P⑷(PQ)R4.寫(xiě)出第3題中各小題中命題公式的真值表，并寫(xiě)出命題的主析取范式7.2布爾代數(shù)計(jì)算機(jī)和其他電子設(shè)備中的電路都有輸入和輸出，輸入是0或1,輸出也是0或1.電路可以用任何具有兩個(gè)不同狀態(tài)的基本元件來(lái)構(gòu)造，開(kāi)關(guān)和光學(xué)裝置都是這樣的元件.開(kāi)關(guān)可能處于開(kāi)或關(guān)的位置，光學(xué)設(shè)置可能是點(diǎn)亮或未點(diǎn)亮的1854年，喬治?布爾在《TheLawsofThought》一書(shū)中第一次給出了邏輯的基本規(guī)則.1938年，克勞德?香農(nóng)揭示了怎么用邏輯的基本規(guī)則來(lái)設(shè)計(jì)電路，這些基本規(guī)則形成了布爾代數(shù)的基礎(chǔ).7.2.1布爾邏輯布爾代數(shù)提供的是集合｛°’｝上的運(yùn)算和規(guī)則，這個(gè)集合及布爾代數(shù)的規(guī)則還可以用來(lái)研究電子和光學(xué)開(kāi)關(guān).我們用的最多的三個(gè)布爾代數(shù)運(yùn)算是補(bǔ)、布爾和與布爾積.元素的補(bǔ)用上劃線加以標(biāo)記，其定義為：_°1且1=0.布爾和記為+或OR，它的值如下：1+1=1，1+0=10+1=10+0=0.布爾積記為或and，它的值如下：11=1，10=1，01=0，00=0.在不引起混淆時(shí)，可以刪除“”.除非使用括號(hào)，布爾運(yùn)算的優(yōu)先級(jí)規(guī)則是：首先計(jì)算所有補(bǔ)，然后是布爾積，—然后是布爾和.例7.2.1計(jì)算01+(10)的值.解：根據(jù)補(bǔ)、布爾積與布爾和的定義得：_01+(0)=0+1=0+0=0下面定理匯集了布爾代數(shù)中常用的基本等式：定理7.1在布爾代數(shù)B={{0,1},+,?,一}中下列等式成立：a+b=b+弘加法交換律)，a?b=b?。(乘法交換律)；(a+b)+c=a+(b+c)(加法結(jié)合律)，(a?b)?c=a?(b?c)(乘法結(jié)合律)；a?(b+c)=a?b+a?c)(乘法對(duì)加法的分配律)，a+(b?c)=(a+b)?(a+c)(加法對(duì)乘法的分配律)；a+0=a,a?1=a,a+1=a,a?0=0;a+a=a,a?a=a;a=a;(a+b)=a?b,a?b=a+b;a+a=1,a?a=0補(bǔ)、布爾積和布爾和分別對(duì)應(yīng)于邏輯運(yùn)算「、v和△，且0對(duì)應(yīng)于假，1對(duì)應(yīng)于真.關(guān)于布爾代數(shù)的結(jié)果可以直接翻譯成關(guān)于命題的結(jié)果.相反地，關(guān)于命題的結(jié)果也能翻譯成關(guān)于布爾代數(shù)的命題.例7.2.2化簡(jiǎn)邏輯函數(shù)F=AB+AB+BC+BC.解：由定理7.1得F=AB(C+C)+AB(C+C)+(A+A)BC+(A+A)BC=ABC+ABC+ABC+ABC+ABC+ABC=ab(c+C)+Ac(B+B)+(A+A)BC=ab+Ac+BC7.2.2開(kāi)關(guān)電路開(kāi)關(guān)是一種具有一個(gè)輸入和一個(gè)輸出的器件，我們將若干個(gè)開(kāi)關(guān)的串聯(lián)與并聯(lián)構(gòu)成的電路稱為開(kāi)關(guān)電路.整個(gè)開(kāi)關(guān)電路從功能上可看作是一個(gè)開(kāi)關(guān)，把電路接通記為1，把電路斷開(kāi)記為0.而開(kāi)關(guān)電路中的開(kāi)關(guān)也要么處于接通狀態(tài)，要么處于斷開(kāi)狀態(tài)，這兩種狀態(tài)也可以用二值布爾代數(shù)來(lái)描述.一個(gè)具有n個(gè)獨(dú)立開(kāi)關(guān)組成的開(kāi)關(guān)電路稱為n元開(kāi)關(guān)電路.整個(gè)開(kāi)關(guān)電路是否接通完全取決于這些開(kāi)關(guān)的狀態(tài)以及連接方式(串聯(lián)、并聯(lián)或反相)，因而可以這些開(kāi)關(guān)的函數(shù).稱這樣的函數(shù)為開(kāi)關(guān)函數(shù)，可以寫(xiě)成一個(gè)二值n元布爾式，稱為線路的布爾表達(dá)式.線路布爾式的構(gòu)造原則：串聯(lián)對(duì)應(yīng)布爾式中的積，并聯(lián)對(duì)應(yīng)布爾和，反相對(duì)應(yīng)布爾補(bǔ).接通條件相同的線路稱為等效線路，兩個(gè)開(kāi)關(guān)電路是等效的，當(dāng)且僅當(dāng)它們對(duì)應(yīng)的開(kāi)關(guān)函數(shù)是等價(jià)的.找等效線路的目的是化簡(jiǎn)線路，使線路中包含的接點(diǎn)盡可能地少.利用布爾代數(shù)可設(shè)計(jì)一些具有指定性質(zhì)的節(jié)點(diǎn)線路，數(shù)學(xué)上即是按給定的真值表構(gòu)造相應(yīng)的布爾表達(dá)式(最后經(jīng)過(guò)適當(dāng)?shù)暮?jiǎn)化)，理論上涉及到范式理論，但形式上并不難構(gòu)造.這樣就可以設(shè)計(jì)出符合要求的開(kāi)關(guān)電路.例7.2.3在舉重比賽中，通常設(shè)三名裁判：一名為主裁，另兩名為副裁競(jìng)賽規(guī)則規(guī)定運(yùn)動(dòng)員每次試舉必須獲得主裁及至少一名副裁的認(rèn)可，方算成功裁判員的態(tài)度只能同意和不同意兩種;運(yùn)動(dòng)員的試舉也只有成功與失敗兩種情況.舉重問(wèn)題可用邏輯代數(shù)加以描述:用A、B、C三個(gè)邏輯變量表示主副三裁判：取值1表示同意（成功），取值0表示不同意（失?。?舉重運(yùn)動(dòng)員用L表示，取值1表示成功，0表示失敗.顯然，L由A、B、C決定.L為A、B、C的邏輯函數(shù).列表如下，該表稱為邏輯函數(shù)L的真值表：表7.2L的真值表A00001111B00110011C01010101L00000111從真值表可看出L取值為1只有三項(xiàng)，A、B、C的取值分別為101、110、和111三種情況L才等于1.A?B?C、A?B?C、A?B?C三項(xiàng)與上述三種取值對(duì)應(yīng).由于上述三種情況之一出現(xiàn)就可判定L成功，故L=(A?B?C)+(A?B?C)+(A?B?C)=(A?B?C)+(A?B?C)+(A?B?C)+(A?B?C)=(A?C)+(A?B)=A?(C+B)圖7.1裁判開(kāi)關(guān)電路圖根據(jù)上述布爾式來(lái)設(shè)計(jì)就可以得到舉重裁判的控制電路.其中K1由主裁控制，K2和氣分別由兩個(gè)副裁控制.1237.2.3門(mén)電路門(mén)電路是實(shí)現(xiàn)各種邏輯關(guān)系的基本電路，是組成數(shù)字電路的最基本單元從邏輯功能上看，有與門(mén)、或門(mén)和非門(mén)，還有由它們復(fù)合而成的與非門(mén)、或非門(mén)、與或非門(mén)、異或門(mén)等從生產(chǎn)工藝上看，門(mén)電路又可分為兩大類(lèi)：分立元件門(mén)電路和應(yīng)用集成電路工藝制成的集成門(mén)電路.在學(xué)習(xí)這些邏輯電路時(shí)，不必考慮它的內(nèi)部結(jié)構(gòu)原理，而要著重掌握它們的邏輯功能.一、與門(mén)如圖，兩個(gè)開(kāi)關(guān)A、B串聯(lián)起來(lái)控制同一個(gè)燈泡L.顯然，只有A“與”B同時(shí)閉合時(shí)，燈L才會(huì)亮.在這個(gè)事件中，A、B閉合是條件，燈L亮是結(jié)果.

圖7.2“與”邏輯電路如果一個(gè)事件的幾個(gè)條件都滿足后，該事件才能發(fā)生，這種關(guān)系叫做“與”邏輯關(guān)系如開(kāi)關(guān)斷開(kāi)和燈不亮均用0表示，而開(kāi)關(guān)閉合和燈亮用1表示，則可得表表7.3真值表ABL000010100111能實(shí)現(xiàn)與運(yùn)算的邏輯電路稱為與門(mén)，其邏輯符號(hào)如圖7.3所示B——圖7.3與門(mén)邏輯符號(hào)圖中A、B表示輸入變量，Y表示輸出變量.與門(mén)的輸入變量為兩個(gè)或兩個(gè)以上.二、或門(mén)如下圖，兩個(gè)開(kāi)關(guān)A、B并聯(lián)，控制同一個(gè)燈泡Y.在這個(gè)電路中，A“或”B只要有一個(gè)開(kāi)關(guān)閉合，燈Y就會(huì)亮.圖7.4“或”邏輯電路像這樣的情況：如果幾個(gè)條件中，只要有一個(gè)條件得到滿足，某事件就會(huì)發(fā)生，這種關(guān)系叫做“或”邏輯關(guān)系.具有“或”邏輯關(guān)系的電路稱為“或”門(mén)電路，簡(jiǎn)稱“或”門(mén).或運(yùn)算的功能表和真值表如表7.4功能表?xiàng)l件結(jié)果開(kāi)關(guān)A開(kāi)關(guān)B燈泡L斷斷熄斷通亮通斷亮通通亮表7.5真值表101—1I1I1或門(mén)邏輯符號(hào)如圖7.5所示;二一Y圖7.5“或”門(mén)邏輯符號(hào)圖中A、B表示輸入變量，Y表示輸出變量.或門(mén)的輸入變量為兩個(gè)或兩個(gè)以上.三、非門(mén)如下圖，在這個(gè)電路中，當(dāng)A閉合，燈Y就會(huì)熄滅，當(dāng)A斷開(kāi)，燈Y就會(huì)亮.圖7.6“非”邏輯電路像這樣輸出狀態(tài)和輸入狀態(tài)相反的邏輯關(guān)系，叫做“非”邏輯關(guān)系，具有“非”邏輯關(guān)系的電路叫做“非”門(mén).非運(yùn)算的功能表和真值表如表7.6功能表?xiàng)l件結(jié)果開(kāi)關(guān)A燈泡Y斷亮通熄表7.7真值表?xiàng)l件結(jié)果AY0110非門(mén)邏輯符號(hào)如圖7.8所示圖7.8“非”門(mén)的符號(hào)圖中A、B表示輸入變量，Y表示輸出變量.例7.2.4求給定邏輯函數(shù)F=AB+AC+BC的相應(yīng)門(mén)電路解：注意到邏輯函數(shù)先非門(mén)，再與門(mén)，后或門(mén)的順序，考慮到多輸入、單輸出的結(jié)果，可得到如圖7.9所示的門(mén)電路.圖7.97.2.4卡諾圖一、邏輯函數(shù)的最小項(xiàng)對(duì)于表達(dá)式Y(jié)=ABC+ABC+ABC中，每一個(gè)乘積項(xiàng)（與項(xiàng)）都是標(biāo)準(zhǔn)形式，這種標(biāo)準(zhǔn)形式的與項(xiàng)為最小項(xiàng)，因此上式被稱為標(biāo)準(zhǔn)與或式，也叫最小項(xiàng)表達(dá)式.在式中，ABC.ABC、ABC三個(gè)乘積的共同特點(diǎn)是：（1）每個(gè)與項(xiàng)包含該邏輯函數(shù)的全部輸入變量；（2）每個(gè)變量均以原變量或反變量的形式在乘積項(xiàng)中出現(xiàn)且只出現(xiàn)一次將滿足上述特點(diǎn)的與項(xiàng)稱為邏輯函數(shù)的最小項(xiàng).n個(gè)輸入變量的邏輯函數(shù)共有2〃個(gè)最小項(xiàng)，為了書(shū)寫(xiě)方便，對(duì)最小項(xiàng)采用編號(hào)的形式編號(hào)的方法是：（1）將最小項(xiàng)中的原變量當(dāng)做1，反變量當(dāng)做0，則得到一組對(duì)應(yīng)的二進(jìn)制數(shù)；（2）將二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)；（3）該十進(jìn)制數(shù)就是最小項(xiàng)對(duì)應(yīng)的編號(hào)，記作m..例如，三變量最小項(xiàng)~ABC對(duì)應(yīng)的二進(jìn)制數(shù)為010，相應(yīng)的十進(jìn)制數(shù)為2,所以ABC記作m2，即m2=ABC.二、卡諾圖的畫(huà)法卡諾圖是由美國(guó)工程師卡諾首先提出的一種利用利用表格作圖化簡(jiǎn)邏輯表達(dá)式的方法它是將邏輯函數(shù)的最小項(xiàng)按一定的規(guī)律排列而成的方格矩陣，每個(gè)小方格對(duì)應(yīng)一個(gè)最小項(xiàng)，因此，卡諾圖又叫最小項(xiàng)方格圖.畫(huà)卡諾圖的具體步驟如下：（1）n個(gè)輸入變量的邏輯函數(shù)畫(huà)出2〃個(gè)小方格，每個(gè)小方格對(duì)應(yīng)一個(gè)最小項(xiàng).（2）各變量的取值符合幾何相鄰和邏輯相鄰重合的原則，即變量的取值按循環(huán)碼（也叫格雷碼）的順序排列幾何相鄰：卡諾圖中的幾何位置上下左右相接的最小項(xiàng).每一行或每一列兩端的最小項(xiàng)也具有幾何相鄰性，故卡諾圖可看成一個(gè)上下、左右對(duì)折的立體圖形的展開(kāi)形式邏輯相鄰：只有一個(gè)變量互為反變量，其余變量均為相同的兩個(gè)最小項(xiàng)叫作在邏輯上是相鄰的.如三變量ABC和ABC中只有B和萬(wàn)不同，其余變量相同，所以ABC和ABC是邏輯相鄰的最小項(xiàng).變量、三變量和四變量卡諾圖如圖7.10-7.12所示.BCBCBCBC00011110ABCABCAbc~AbcaBCABCABCABCAm0m1BCBCBCBC00011110ABCABCAbc~AbcaBCABCABCABCAm0m1m3m2mmmm4576圖7.11三變量的卡諾圖ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDCDCDABABABABCDCD013245761213151489111000011110三變量的卡諾圖圖7.12三變量的卡諾圖三、邏輯函數(shù)的卡諾圖表示法采用卡諾圖化簡(jiǎn)邏輯函數(shù)時(shí)，必須先畫(huà)出邏輯函數(shù)對(duì)應(yīng)的卡諾圖.常用的方法有2種:1）真值表法將真值表中每組輸入變量的取值組合所對(duì)應(yīng)的函數(shù)值填入卡諾圖相應(yīng)的小方格中，即函數(shù)值為1的最小項(xiàng)所對(duì)應(yīng)的小方格中填1，函數(shù)值為0的最小項(xiàng)所對(duì)應(yīng)的小方格中填0.例7.2.5畫(huà)出表對(duì)應(yīng)的卡諾圖表7.8真值表ABCY00000011010001111000101111001111解：表中所描述的是3變量的邏輯函數(shù).畫(huà)出3變量的卡諾圖填寫(xiě)卡諾圖.將表中對(duì)應(yīng)變量取值組合001、011、101、111的函數(shù)值為1，故在卡諾圖總相應(yīng)的小方格內(nèi)填1，其余的小方格填0.如圖7.13所示\BC注、、0001111000100111圖7.132)由一般與或式畫(huà)邏輯函數(shù)卡諾圖法首先畫(huà)出輸入變量對(duì)應(yīng)的卡諾圖，然后根據(jù)表達(dá)式中與項(xiàng)的特征將最小項(xiàng)填入卡諾圖，具體如下：與項(xiàng)中的原變量用1表示，非變量用0表示，與項(xiàng)中的變量在卡諾圖中橫向和縱向相交的小方格便為所求的最小項(xiàng)，填入1，其余的小方格填0.例7.2.6畫(huà)出邏輯函數(shù)Y=ACD+BCD+AB對(duì)應(yīng)的卡諾圖.解：表達(dá)式中與項(xiàng)ACD對(duì)應(yīng)的