匯編考試第2章 邏輯代數(shù)基礎(chǔ)

§2.1概述2.1.1事物的二值性世界上的許多事物都具有完全不同的兩種狀態(tài)，這就是平時所說的事物的矛盾性。我們可以舉出很多這類完全對立的、處于矛盾狀態(tài)的例子，如表2.1所示。

2/19/20251北京理工大學(xué)信息科學(xué)學(xué)院2/19/20252北京理工大學(xué)信息科學(xué)學(xué)院2.1.2布爾代數(shù)“邏輯代數(shù)”是十九世紀(jì)的英國數(shù)學(xué)家喬治·布爾(GeorgeBoole)在1847年首先創(chuàng)立的。

這是一種僅使用數(shù)值“1”和“0”的代數(shù)。注意，這里的“1”和“0”并不代表數(shù)量的大小，而是表示完全對立的兩個矛盾著的方面。

正是由于布爾構(gòu)造出了二值代數(shù)系統(tǒng)，所以很多教科書上又把邏輯代數(shù)稱作“布爾代數(shù)”(BooleanAlgebra)。布爾代數(shù)在創(chuàng)建的初期僅僅是應(yīng)用于研究概率的問題，由于時代和生產(chǎn)力水平的限制，當(dāng)時的人們并沒有認(rèn)識到這一代數(shù)理論的巨大應(yīng)用前景。2/19/20253北京理工大學(xué)信息科學(xué)學(xué)院美國貝爾實(shí)驗(yàn)室的科學(xué)家克勞迪·香農(nóng)(ClaudeShannon)于1938年寫出了他那具有革命性的碩士論文《繼電器和開關(guān)電路的一種符號分析》（“ASymbolicAnalysisofRelayandSwitchingCircuits”）時，人們才真正認(rèn)識到布爾代數(shù)的實(shí)用價(jià)值。香農(nóng)把布爾代數(shù)應(yīng)用到開關(guān)電路的分析和設(shè)計(jì)上，所以還有一些教課書上把“布爾代數(shù)”叫做“開關(guān)代數(shù)”（SwitchingAlgebra）。2/19/20254北京理工大學(xué)信息科學(xué)學(xué)院§2.2邏輯變量和邏輯函數(shù)

2.2.1基本的邏輯運(yùn)算和邏輯變量所謂邏輯就是指事物的因果之間所應(yīng)遵循的規(guī)律,最基本的邏輯關(guān)系可以歸納為“與”邏輯、“或”邏輯和“非”邏輯三種邏輯運(yùn)算。

1.“與”邏輯開關(guān)A、B是串聯(lián)相接的，只有當(dāng)兩個開關(guān)A、B全都閉合時，燈泡F才能點(diǎn)亮。

2/19/20255北京理工大學(xué)信息科學(xué)學(xué)院2.“或”邏輯決定某個事件的所有條件全都具備時，這個事件才會發(fā)生的因果關(guān)系定義為“與”邏輯。開關(guān)A、B是并聯(lián)相接的，所以只要兩個開關(guān)A、B中有任何一個開關(guān)閉合、或者是二者全都閉合時，燈泡F就能點(diǎn)亮。

決定某個事件的所有條件中只要有任意一個條件具備、或者是某幾個條件同時具備、或者是全都具備時，這個事件就會發(fā)生的因果關(guān)系定義為“或”邏輯。2/19/20256北京理工大學(xué)信息科學(xué)學(xué)院3.“非”邏輯當(dāng)開關(guān)A閉合時燈泡F是熄滅的，而在開關(guān)A斷開時，燈泡F才能點(diǎn)亮。

事件的發(fā)生與否和決定這個事件的條件是否具備的狀態(tài)剛好相反的因果關(guān)系定義為“非”邏輯。一個變量X如果僅有兩個可能的取值“0”或“1”，則稱這種僅有0、1兩個取值的變量為邏輯變量（以后簡稱為變量）

。

邏輯變量2/19/20257北京理工大學(xué)信息科學(xué)學(xué)院可把表2.1所列舉的那些完全對立的矛盾狀態(tài)實(shí)例都用一個邏輯變量來描述。

2/19/20258北京理工大學(xué)信息科學(xué)學(xué)院2/19/20259北京理工大學(xué)信息科學(xué)學(xué)院表2.1中對立矛盾的狀態(tài)與邏輯變量取值的對應(yīng)關(guān)系完全是人為定義的?？梢园驯碇小?”和“1”的位置對調(diào)一下而不失所述問題的合理性和一般性

。

開關(guān)A、B的“閉合”作為邏輯“1”，“斷開”作為邏輯“0”。

燈泡F的“點(diǎn)亮”作為邏輯“1”，“熄滅”作為邏輯“0”

。

這種反映因果邏輯關(guān)系的表叫做真值表。

對開關(guān)的“閉合”與“斷開”、燈泡的“點(diǎn)亮”與“熄滅”作如下的邏輯規(guī)定：2/19/202510北京理工大學(xué)信息科學(xué)學(xué)院真值表的結(jié)構(gòu)特點(diǎn)：真值表的左欄列出的是表示條件的邏輯變量以及這些變量取值的所有可能的組合。

真值表的右欄填入的是表示事件的邏輯變量以及它對應(yīng)于各條件變量取值的邏輯運(yùn)算結(jié)果。

2/19/202511北京理工大學(xué)信息科學(xué)學(xué)院最基本的邏輯是“與”、“或”、“非”，與之相對應(yīng)的也有三種基本的邏輯運(yùn)算。

邏輯運(yùn)算：1.“與”運(yùn)算（邏輯乘法）F=A?B

“A?B”叫做邏輯表達(dá)式，它表示邏輯變量A和B做“與”運(yùn)算（也叫邏輯乘法運(yùn)算）

。

運(yùn)算符號“?”叫做“與”運(yùn)算符

。

其他形式的“與”運(yùn)算符有：“∧”、“∩”和“&”

。

2/19/202512北京理工大學(xué)信息科學(xué)學(xué)院“與”運(yùn)算的含義是：只有當(dāng)A、B全為“1”時，F(xiàn)才為“1”；A、B中只要有一個為“0”或者二者都為“0”時，F(xiàn)就為“0”。

“與”運(yùn)算的規(guī)則就是：0?0=0，0?1=0，1?0=0，1?1=1。

“與”運(yùn)算規(guī)則與普通乘法的規(guī)律相同，但是含義卻不同。

我們采用符號“?”作為“與”運(yùn)算符，有時干脆省去“?”而把F=A?B寫成F=AB。

2/19/202513北京理工大學(xué)信息科學(xué)學(xué)院2.“或”運(yùn)算（邏輯加法）F=A+B

“A+B”也是邏輯表達(dá)式，它表示邏輯變量A和B做“或”運(yùn)算(也叫邏輯加法運(yùn)算)。

運(yùn)算符號“+”叫做“或”運(yùn)算符

。

其他形式的“或”運(yùn)算符有：“∨”、“∪”和“|”。

“或”運(yùn)算的含義是：A和B當(dāng)中只要有一個為“1”或者全為“1”時，F(xiàn)就為“1”；只有當(dāng)A、B全為“0”時，F(xiàn)才為“0”

。

我們采用符號“+”作為“或”運(yùn)算符。

2/19/202514北京理工大學(xué)信息科學(xué)學(xué)院“或”運(yùn)算的規(guī)則是：0+0=0，0+1=1，1+0=1，1+1=1

。

“或”運(yùn)算規(guī)則的前3條與普通加法的規(guī)律相同，但是含義不同。

“或”運(yùn)算規(guī)則的最后1條與普通加法的規(guī)律在形式上和含義上均不相同。在這里，1+1≠2，且1+1≠(10)２。

要注意：邏輯運(yùn)算不是數(shù)值運(yùn)算，邏輯運(yùn)算是因果關(guān)系的邏輯判斷。

2/19/202515北京理工大學(xué)信息科學(xué)學(xué)院3.“非”運(yùn)算上式表示邏輯變量F和A的取值相反，即A為“0”時F為“1”；而A為“1”時F為“0”。

“非”運(yùn)算的運(yùn)算規(guī)則就是：“非”運(yùn)算是算術(shù)里所沒有的。讀作“A非”或者“A反”，有時也把“非”運(yùn)算叫做求“補(bǔ)”運(yùn)算，而把讀作“A補(bǔ)”。

在邏輯代數(shù)中，只有“與”運(yùn)算、“或”運(yùn)算和“非”運(yùn)算這三種基本邏輯運(yùn)算，沒有其他的運(yùn)算。邏輯變量的取值也只有“1”和“0”兩種，而不能有其他的取值。這些是和普通代數(shù)不同的。

2/19/202516北京理工大學(xué)信息科學(xué)學(xué)院在邏輯代數(shù)中也有邏輯運(yùn)算的前、后優(yōu)先次序：單變量上的“非”運(yùn)算優(yōu)先級最高。

“與”運(yùn)算（邏輯“乘”）要優(yōu)先于“或”運(yùn)算（邏輯“加”）。

括弧“（）”內(nèi)的運(yùn)算要優(yōu)先于括弧外的運(yùn)算。

多變量上的“非”運(yùn)算相當(dāng)于加括弧。

例如：的運(yùn)算順序是：先做，再做A+，最后再將所得結(jié)果與變量C相“與”。例如：就相當(dāng)于

。2/19/202517北京理工大學(xué)信息科學(xué)學(xué)院“與”、“或”、“非”這三種基本邏輯運(yùn)算可分別由“與”門、“或”門和“非”門三種基本的邏輯門電路來實(shí)現(xiàn)。這三種基本門電路的邏輯符號如下所示：2/19/202518北京理工大學(xué)信息科學(xué)學(xué)院2.2.2邏輯函數(shù)如果把“與”、“或”、“非”這三種基本邏輯運(yùn)算組合成一個較為復(fù)雜的邏輯表達(dá)式，再把該邏輯表達(dá)式的運(yùn)算結(jié)果（只能是“0”或“1”）賦予另一個邏輯變量，比如說F，于是就構(gòu)成了一個邏輯函數(shù)。例如：F叫做邏輯因變量，即：邏輯函數(shù)。F是邏輯自變量A、B、C、D的邏輯函數(shù)。其中A、B、C、D叫做邏輯自變量，叫做邏輯表達(dá)式。2/19/202519北京理工大學(xué)信息科學(xué)學(xué)院無論是邏輯自變量的定義域還是邏輯函數(shù)的值域都只能是“0”或“1”而不能是其它的取值。邏輯函數(shù)是一個四變量的邏輯函數(shù)，可以抽象地記為：

四變量邏輯函數(shù)的四個變量A、B、C、D的取值組合總共有十六組（0000至1111）。對于A、B、C、D四個變量的十六組取值都有一個確定的F取值（只能是“0”或“1”）與之對應(yīng)。

邏輯函數(shù)和邏輯表達(dá)式與普通函數(shù)和算術(shù)表達(dá)式，有著本質(zhì)的區(qū)別

。

2/19/202520北京理工大學(xué)信息科學(xué)學(xué)院一般的多變量邏輯函數(shù)可以記為：邏輯函數(shù)有時也被稱作開關(guān)函數(shù)。三種基本邏輯運(yùn)算,即：就是三個最基本的邏輯函數(shù)。前兩個是兩變量邏輯函數(shù)；而最后一個是單變量邏輯函數(shù)。邏輯函數(shù)的相等：若兩個邏輯函數(shù)F和G的輸入變量相同，而且對于任意的一組變量取值都有相同的函數(shù)值，則這兩個函數(shù)相等，記作：F=G。換句話說，就是任何形式的兩個邏輯函數(shù)，只要它們的真值表相同，則彼此相等。2/19/202521北京理工大學(xué)信息科學(xué)學(xué)院任何一個邏輯操作的過程，都可用一個具有若干個邏輯變量的邏輯函數(shù)來描述，并可用一個與此函數(shù)相對應(yīng)的邏輯電路來實(shí)現(xiàn)。先看一個例子。

LK下K上~220V樓梯照明電路原理圖用邏輯變量F代表電燈L，并規(guī)定F=1表示燈亮，而F=0則表示燈滅；再用邏輯變量A、B分別表示兩個開關(guān)K上、K下的位置，并規(guī)定“1”表示向上扳，而“0”表示向下扳。2/19/202522北京理工大學(xué)信息科學(xué)學(xué)院A、B叫做輸入邏輯變量；F叫做輸出邏輯變量。A、B也叫邏輯自變量，而F也叫邏輯因變量或邏輯函數(shù)。邏輯函數(shù)和真值表各自都能完全地描述一個邏輯操作的過程。一個邏輯函數(shù)對應(yīng)了一張真值表；而一張真值表也對應(yīng)了一個（或若干個）邏輯函數(shù)。邏輯函數(shù)叫做“同或”邏輯函數(shù)。其特點(diǎn)是：當(dāng)A、B相同時，函數(shù)F為“1”，否則F為“0”。通常是把輸入邏輯變量(邏輯自變量)列在真值表的左邊；而把輸出邏輯變量(邏輯函數(shù))列在真值表的右邊。2/19/202523北京理工大學(xué)信息科學(xué)學(xué)院邏輯函數(shù)和邏輯電路是相互對應(yīng)的。邏輯函數(shù)可以由邏輯電路來實(shí)現(xiàn)；而邏輯電路也可以由邏輯函數(shù)來描述。

2.2.3邏輯函數(shù)與邏輯電路的關(guān)系例如，上一節(jié)所提到的“同或”邏輯函數(shù)就可以用下面的邏輯電路來實(shí)現(xiàn)它。FAB“同或”邏輯電路2/19/202524北京理工大學(xué)信息科學(xué)學(xué)院反之，如果給出一個邏輯電路，就可以根據(jù)這個邏輯電路寫出用于描述該邏輯電路輸入信號（變量）和輸出信號（變量）之間關(guān)系的邏輯函數(shù)。

例如，給出下面的邏輯電路圖FAB“異或”邏輯電路可以寫出描述該電路輸出信號F與輸入信號A、B之間關(guān)系的邏輯函數(shù)表達(dá)式為：

2/19/202525北京理工大學(xué)信息科學(xué)學(xué)院邏輯函數(shù)叫做“異或”邏輯函數(shù)。

其特點(diǎn)是：當(dāng)A、B相異時，函數(shù)F為“1”，否則F為“0”?！?.3邏輯代數(shù)的基本運(yùn)算規(guī)律

2.3.1邏輯代數(shù)的基本定律1.邏輯代數(shù)公理邏輯代數(shù)公理（或者叫基本原理）是整個邏輯代數(shù)系統(tǒng)的基石，以這些公理為出發(fā)點(diǎn)，可以證明所有邏輯代數(shù)系統(tǒng)中的各種定律和定理。

2/19/202526北京理工大學(xué)信息科學(xué)學(xué)院邏輯代數(shù)公理實(shí)際上是邏輯常數(shù)“1”和“0”的基本運(yùn)算規(guī)則。這些運(yùn)算規(guī)則可直接由“與”、“或”和“非”的運(yùn)算定義得出。這些公理歸納于下表：

2/19/202527北京理工大學(xué)信息科學(xué)學(xué)院根據(jù)邏輯代數(shù)的公理，可以推導(dǎo)出邏輯代數(shù)運(yùn)算的一些基本定律。下表給出了這些基本定律。

2.邏輯代數(shù)的基本運(yùn)算規(guī)律2/19/202528北京理工大學(xué)信息科學(xué)學(xué)院證明上表所示基本定律的最有效的方法就是使用真值表，即，分別作出等式兩邊邏輯表達(dá)式的真值表，然后檢驗(yàn)其結(jié)果是否相同。

例如：證明上表中的反演律。為此分別作出兩個等式的等號兩邊邏輯表達(dá)式的真值表，如表2.8和表2.9所示。

2/19/202529北京理工大學(xué)信息科學(xué)學(xué)院從表2.8和表2.9知：

這就是著名的狄·摩根(De·Morgan)定理。在邏輯代數(shù)的運(yùn)算中經(jīng)常會用到狄·摩根定理，它是一個非常重要的定理。

也可以用代數(shù)的方法來證明表2.7所列出的邏輯代數(shù)基本定律。

例如：可以用摩根定理、還原律和分配律的6號公式去證明分配律的6＇號公式。證明過程如下：

（還原律）

（摩根定理）（分配律6號）（摩根定理）

2/19/202530北京理工大學(xué)信息科學(xué)學(xué)院作業(yè)1：2-8，2-9的（1）、（2）、（3）、（8）、（9）

（還原律）

2.3.2三個重要規(guī)則1.代入規(guī)則任何一個邏輯等式，如果將等式兩邊所出現(xiàn)的同一個邏輯變量都代之以同一個邏輯函數(shù)，則該邏輯等式仍然成立，這就是代入規(guī)則。代入規(guī)則也叫代入定理。

2/19/202531北京理工大學(xué)信息科學(xué)學(xué)院(結(jié)合律,摩根定理)

這就是三個變量的摩根定理。同理可以證明n個變量的摩根定理，即：

例如:摩根定理是再令：代入后一個等式，于是得到：

現(xiàn)在令：代入前一個等式；(結(jié)合律,摩根定理)

2/19/202532北京理工大學(xué)信息科學(xué)學(xué)院2.反演規(guī)則

若兩個邏輯函數(shù)F和G的輸入變量相同，而且F和G對于任意的一組輸入變量取值都有相反的函數(shù)值，則稱這兩個函數(shù)互反（或叫互補(bǔ)），記作：或。

反演規(guī)則的內(nèi)容如下：

對于任意的邏輯函數(shù)F，如果對其表達(dá)式做下述三種變換：

把原表達(dá)式中所有的“·

”運(yùn)算符換成“+”運(yùn)算符，同時把所有的“+”運(yùn)算符換成“·

”運(yùn)算符；把原表達(dá)式中所有的邏輯常量“0”換成邏輯常量“1”，而把所有的邏輯常量“1”換成邏輯常量“0”；2/19/202533北京理工大學(xué)信息科學(xué)學(xué)院把原表達(dá)式中所有的原變量換成反變量，再把所有的反變量換成原變量。則若則反演規(guī)則實(shí)際上是反演律（摩根定理）在求邏輯函數(shù)F的反（補(bǔ)）函數(shù)時的一種推廣。它提供了一種可以由邏輯函數(shù)F的表達(dá)式（較復(fù)雜時）直接求出其反（補(bǔ)）函數(shù)的方法。

例如：可直接寫出：若于是就得到了函數(shù)F的反函數(shù)F。例如：2/19/202534北京理工大學(xué)信息科學(xué)學(xué)院例如：則而例如：則絕對不能打亂原表達(dá)式的運(yùn)算順序；不屬于單變量上的非號應(yīng)保持不變。在運(yùn)用反演規(guī)則時必須注意以下兩點(diǎn)：

若若是F的反函數(shù)，F(xiàn)也是

的反函數(shù)。F和

互為反函數(shù)。

2/19/202535北京理工大學(xué)信息科學(xué)學(xué)院3.對偶規(guī)則

對偶式的概念：對于任意的邏輯函數(shù)F，如果對其表達(dá)式做下述三種變換：

把原表達(dá)式中所有的“·

”運(yùn)算符換成“+”運(yùn)算符，同時把所有的“+”運(yùn)算符換成“·”運(yùn)算符；

把原表達(dá)式中所有的邏輯常量“0”換成邏輯常量“1”，而把所有的邏輯常量“1”換成邏輯常量“0”；

原表達(dá)式中所有的原變量和反變量均保持不變。

則由此所得到的新邏輯表達(dá)式就是原邏輯函數(shù)F表達(dá)式的對偶式（對偶函數(shù)），記作：F＇。

2/19/202536北京理工大學(xué)信息科學(xué)學(xué)院例如：若：則：若：則：若：則：若：則：F＇是F的對偶式，F(xiàn)也是F＇的對偶式。F和F＇互為對偶式。

在求一個函數(shù)表達(dá)式的對偶式時也不能打亂原表達(dá)式的運(yùn)算順序

。

在一般情況下。

2/19/202537北京理工大學(xué)信息科學(xué)學(xué)院表2.7所列出的基本定律中，右邊帶撇的標(biāo)號所對應(yīng)的公式兩邊的表達(dá)式，都是左邊不帶撇的標(biāo)號所對應(yīng)的公式兩邊表達(dá)式的對偶式。對偶規(guī)則：如果兩個函數(shù)相等，則它們的對偶函數(shù)（對偶式）也相等。即：若則。

運(yùn)用對偶規(guī)則，使需要記憶和證明的公式數(shù)量減少一半。對偶規(guī)則給簡化和變換邏輯函數(shù)帶來方便。2/19/202538北京理工大學(xué)信息科學(xué)學(xué)院2.3.3邏輯代數(shù)的基本定理2/19/202539北京理工大學(xué)信息科學(xué)學(xué)院證明表2.10所列出定理的最根本方法就是利用真值表。在利用邏輯代數(shù)的方法證明表2.10中各定理時要用到邏輯代數(shù)的公理、基本定律、已獲證明的其他定理和三個重要規(guī)則。（1）證明“合并定理”公式1：證明：（分配律）（互補(bǔ)律）（自等律）也可以利用邏輯代數(shù)的方法證明表2.10所列出的各定理。2/19/202540北京理工大學(xué)信息科學(xué)學(xué)院（自等律）（2）證明“吸收定理”的公式2：證明：（自等律、分配律）（0-1律）（互補(bǔ)律）（3）證明“吸收定理”的公式3：證明：（吸收定理公式2）（分配律）（自等律）2/19/202541北京理工大學(xué)信息科學(xué)學(xué)院(交換律、結(jié)合律)（4）證明“添加項(xiàng)定理”的公式4：證明：(互補(bǔ)律、自等律)(分配律)(分配律)(0-1律、自等律)2/19/202542北京理工大學(xué)信息科學(xué)學(xué)院(互補(bǔ)律)（5）證明表2.10的公式6：證明：(摩根定理)(還原律)(分配律)(自等律)(摩根定理)(添加項(xiàng)定理)將“對偶規(guī)則”分別運(yùn)用于表2.10中的公式1~公式6就可以分別證明表2.10中的公式1＇~公式6＇。2/19/202543北京理工大學(xué)信息科學(xué)學(xué)院作業(yè)2：2-9的（4）、（5）、（6）、（7），2-10，2-11

2/19/202544北京理工大學(xué)信息科學(xué)學(xué)院2.3.4復(fù)合邏輯運(yùn)算和復(fù)合邏輯門復(fù)合邏輯運(yùn)算就是將三種基本邏輯運(yùn)算——“與”、“或”、“非”按某種形式進(jìn)行簡單地組合所構(gòu)成的一種新的邏輯運(yùn)算。用于實(shí)現(xiàn)這些復(fù)合邏輯運(yùn)算的邏輯門電路，就叫做復(fù)合邏輯門，簡稱復(fù)合門。1.“與非”、“或非”、“與或非”運(yùn)算“與非”運(yùn)算就是“與”運(yùn)算和“非”運(yùn)算的組合。用邏輯函數(shù)表示就是：ABF“與非”門邏輯符號2/19/202545北京理工大學(xué)信息科學(xué)學(xué)院“或非”運(yùn)算就是“或”運(yùn)算和“非”運(yùn)算的組合。用邏輯函數(shù)表示就是：“或非”門邏輯符號ABCDFABF“與或非”運(yùn)算就是“與”運(yùn)算、“或”運(yùn)算和“非”運(yùn)算的組合。用邏輯函數(shù)表示就是：“與或非”門邏輯符號2/19/202546北京理工大學(xué)信息科學(xué)學(xué)院2.“異或”（“異”）、“同或”（“同”）運(yùn)算“異或”邏輯運(yùn)算（有時簡稱“異”運(yùn)算）和“同或”邏輯運(yùn)算（有時簡稱“同”運(yùn)算）是兩個非常重要的復(fù)合邏輯運(yùn)算。兩個變量“異或”運(yùn)算的定義如下：（1）“異或”運(yùn)算“⊕”是“異或”的運(yùn)算符號。根據(jù)兩變量“異或”定義式，列出其真值表。“異或”運(yùn)算含義：若兩變量A、B的取值相異，則F的取值為“1”；若兩變量A、B的取值相同，則F的取值為“0”。

2/19/202547北京理工大學(xué)信息科學(xué)學(xué)院根據(jù)“異或”運(yùn)算定義，邏輯常數(shù)“1”和“0”的“異或”基本運(yùn)算規(guī)則如下：

3個變量的“異或”運(yùn)算定義如下：n個變量的“異或”運(yùn)算可依此類推。2/19/202548北京理工大學(xué)信息科學(xué)學(xué)院“異或”運(yùn)算具有如下的基本運(yùn)算規(guī)律：“異或”運(yùn)算符合交換律，即：“異或”運(yùn)算符合結(jié)合律，即：“異或”運(yùn)算具有分配律，即：利用真值表，再根據(jù)“異或”的定義，可證明“異或”的這些基本運(yùn)算規(guī)律。2/19/202549北京理工大學(xué)信息科學(xué)學(xué)院“異或”運(yùn)算的兩個重要特性特性1：多變量“異或”運(yùn)算的結(jié)果取決于這些變量中取值為“1”的變量個數(shù)，而與取值為“0”的變量個數(shù)無關(guān)。若取值為“1”的變量個數(shù)是奇數(shù)，則“異或”的結(jié)果為“1”；若取值為“1”的變量個數(shù)是偶數(shù)，則“異或”的結(jié)果為“0”。多個變量相“異或”的本質(zhì)就在于確定取值為“1”的變量個數(shù)是奇數(shù)個還是偶數(shù)個。多個邏輯常量相“異或”，其結(jié)果取決于邏輯“1”的個數(shù)，而與邏輯“0”的個數(shù)無關(guān)。若邏輯“1”的個數(shù)為奇數(shù)，則“異或”的結(jié)果為“1”；若邏輯“1”的個數(shù)為偶數(shù)，則“異或”的結(jié)果為“0”。2/19/202550北京理工大學(xué)信息科學(xué)學(xué)院由特性1可得到如下推論：若（1≤i≤n）則或：n個變量相“異或”的補(bǔ)函數(shù)就等于這n個相“異或”的變量中任意一個變量取反。

2/19/202551北京理工大學(xué)信息科學(xué)學(xué)院特性2：“異或”運(yùn)算具有因果互換的關(guān)系。即，等式兩邊的邏輯變量可以互相交換位置而仍然保持等式的成立。

例如：若成立，則或成立?！爱惢颉边\(yùn)算的這種因果互換關(guān)系還可以推廣到多個邏輯量（包括邏輯變量和邏輯常量）相“異或”的情形。

成立。例如：若成立，則或或或利用“異或”運(yùn)算的特性1，可說明多個邏輯量“異或”運(yùn)算的因果互換關(guān)系。2/19/202552北京理工大學(xué)信息科學(xué)學(xué)院“異或”邏輯門及其邏輯符號“異或”運(yùn)算可以由“異或”邏輯門來實(shí)現(xiàn)。“異或”門的邏輯符號如下圖所示：ABFFABCD多個變量的“異或”，則可根據(jù)“異或”運(yùn)算的結(jié)合律，利用多個“異或”門的級聯(lián)來實(shí)現(xiàn)，如下圖所示。

2/19/202553北京理工大學(xué)信息科學(xué)學(xué)院兩個變量“同或”運(yùn)算的定義如下：（2）“同或”運(yùn)算“⊙”是“同或”的運(yùn)算符號。根據(jù)兩變量“同或”定義式，列出其真值表?！巴颉边\(yùn)算含義：若兩變量A、B的取值相同，則F的取值為“1”；若兩變量A、B的取值相異，則F的取值為“0”。

⊙根據(jù)“同或”運(yùn)算定義，邏輯常數(shù)“1”和“0”的“同或”基本運(yùn)算規(guī)則如下：

0⊙0=1，0⊙1=0，1⊙0=0，1⊙1=12/19/202554北京理工大學(xué)信息科學(xué)學(xué)院3個變量的“同或”運(yùn)算定義如下：F=A⊙B⊙C⊙Cn個變量的“同或”運(yùn)算可依此類推?！巴颉边\(yùn)算具有如下的基本運(yùn)算規(guī)律：A⊙0=；A⊙1=A；A⊙A=1；A⊙=02/19/202555北京理工大學(xué)信息科學(xué)學(xué)院“同或”運(yùn)算符合交換律，即：A⊙B=B⊙A

“同或”運(yùn)算符合結(jié)合律，即：A⊙(B⊙C)=(A⊙B)⊙C“同或”運(yùn)算具有分配律，即：A+(B⊙C)=(A+B)⊙(A+C)

利用真值表，再根據(jù)“同或”的定義，可證明“同或”的這些基本運(yùn)算規(guī)律。2/19/202556北京理工大學(xué)信息科學(xué)學(xué)院2/19/202557北京理工大學(xué)信息科學(xué)學(xué)院“同或”運(yùn)算的兩個重要特性特性1：多變量“同或”運(yùn)算的結(jié)果取決于這些變量中取值為“0”的變量個數(shù)，而與取值為“1”的變量個數(shù)無關(guān)。若取值為“0”的變量個數(shù)是偶數(shù)，則“同或”的結(jié)果為“1”；若取值為“0”的變量個數(shù)是奇數(shù)，則“同或”的結(jié)果為“0”。

多個變量相“同或”的本質(zhì)就在于確定取值為“0”的變量個數(shù)是偶數(shù)個還是奇數(shù)個。

多個邏輯常量相“同或”，其結(jié)果取決于邏輯“0”的個數(shù)，而與邏輯“1”的個數(shù)無關(guān)。若邏輯“0”的個數(shù)為偶數(shù)，則“同或”的結(jié)果為“1”；若邏輯“0”的個數(shù)為奇數(shù)，則“同或”的結(jié)果為“0”。2/19/202558北京理工大學(xué)信息科學(xué)學(xué)院由“同或”運(yùn)算的特性1可得到如下推論：或：n個變量相“同或”的補(bǔ)函數(shù)就等于這n個相“同或”的變量中任意一個變量取反。若F=A1⊙A2⊙……⊙Ai⊙……⊙An，（1≤i≤n）則=A1⊙A2⊙……⊙⊙……⊙An；=A1⊙A2⊙……⊙⊙……⊙An；A1⊙A2⊙……⊙Ai⊙……⊙An2/19/202559北京理工大學(xué)信息科學(xué)學(xué)院特性2：“同或”運(yùn)算具有因果互換的關(guān)系。即，等式兩邊的邏輯變量可以互相交換位置而仍然保持等式的成立。

例如：若A⊙B=C成立，則A⊙C=B“同或”運(yùn)算的這種因果互換關(guān)系也可以推廣到多個邏輯量（包括邏輯變量和邏輯常量）相“同或”的情形。例如：若A⊙B⊙C⊙D=1成立，則A⊙1⊙C⊙D=B或1⊙B⊙C⊙D=A或A⊙B⊙C⊙1=D成立?；駻⊙B⊙1⊙D=C利用“同或”運(yùn)算的特性1，可說明多個邏輯量“同或”運(yùn)算的因果互換關(guān)系。或B⊙C=A成立。2/19/202560北京理工大學(xué)信息科學(xué)學(xué)院“異或”與“同或”之間的關(guān)系設(shè)有n個邏輯變量A1，A2，……，An，若F是將這n個邏輯變量相“異或”而構(gòu)成的邏輯函數(shù)；G是將這n個邏輯變量相“同或”而構(gòu)成的邏輯函數(shù)，即：；G=A1⊙A2⊙，……⊙An

則當(dāng)n為偶數(shù)時：或。也就是說，此時邏輯函數(shù)F和邏輯函數(shù)G互為反函數(shù)（或互為補(bǔ)函數(shù)）；而當(dāng)n為奇數(shù)時：F=G。也就是說，此時邏輯函數(shù)F和邏輯函數(shù)G相同。

兩變量的“同或”函數(shù)是兩變量的“異或”函數(shù)的反函數(shù)。A⊙B==A⊙B或2/19/202561北京理工大學(xué)信息科學(xué)學(xué)院“同或”邏輯門及其邏輯符號“同或”運(yùn)算可以由“同或”邏輯門來實(shí)現(xiàn)?！巴颉遍T的邏輯符號如下圖所示：在兩個變量的“同或”運(yùn)算中，只要有一個變量取反，則“同或”運(yùn)算就變?yōu)椤爱惢颉边\(yùn)算，反之亦然。

A⊙B=或=A⊙

“同或”運(yùn)算亦稱之為“異或”非運(yùn)算。ABFABFABF2/19/202562北京理工大學(xué)信息科學(xué)學(xué)院兩個變量構(gòu)成的“同或”和“異或”函數(shù)是一對特殊的邏輯函數(shù)。它們不僅互為反函數(shù)，而且還互為對偶函數(shù)。即：不但A⊙B==A⊙B或而且=A⊙B或(A⊙B)＇=運(yùn)用對偶規(guī)則，可以從表2.13的左欄所列公式推導(dǎo)出右欄所列公式，反之亦然。在求對偶式時，除了前面提到的三個變換以外，還要加上第四個變換，即：把所有的“”運(yùn)算符換成“⊙”運(yùn)算符，同時把所有的“⊙”運(yùn)算符換成“”運(yùn)算符。在運(yùn)用反演規(guī)則時，除原先的三個變換以外，也需加上第四個變換，即：把所有的“”、“⊙”互換。2/19/202563北京理工大學(xué)信息科學(xué)學(xué)院3.邏輯運(yùn)算符號的完備性“與”、“或”、“非”是三種基本的邏輯運(yùn)算，由它們可以組成任何邏輯函數(shù)。所以說“·”、“+”、“￣”是一組邏輯功能完備的邏輯運(yùn)算符。

“與非”運(yùn)算、“或非”運(yùn)算以及“與或非”運(yùn)算各自都是功能完備的復(fù)合邏輯運(yùn)算符。

“與”、“或”、“非”這三種基本邏輯運(yùn)算均可用“或非”運(yùn)算來單獨(dú)地完成，并可用相應(yīng)的“或非”門來實(shí)現(xiàn)。

2/19/202564北京理工大學(xué)信息科學(xué)學(xué)院“或”“非”ABA+B“與”A“0”BA·B“0”AABA·BB或者A“0”2/19/202565北京理工大學(xué)信息科學(xué)學(xué)院作業(yè)3：2-12的（1）、（3）、（4）、（5）、（8）、（9），2-14，2-17，2-19，2-21同理：“與”、“或”、“非”這三種基本邏輯運(yùn)算均可用“與非”運(yùn)算來單獨(dú)地完成，并可用相應(yīng)的“與非”門來實(shí)現(xiàn)。

同理：“與”、“或”、“非”這三種基本邏輯運(yùn)算均可用“與或非”運(yùn)算來單獨(dú)地完成，并可用相應(yīng)的“與或非”門來實(shí)現(xiàn)。

2/19/202566北京理工大學(xué)信息科學(xué)學(xué)院§2.4邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式一個邏輯函數(shù)可以歸納出五種主要的形式。它們是：①“與或”表達(dá)式（先“與”后“或”的表達(dá)式）；②“或與”表達(dá)式（先“或”后“與”的表達(dá)式）；③“與非-與非”表達(dá)式；④“或非-或非”表達(dá)式；⑤“與或非”表達(dá)式。例如函數(shù)：2/19/202567北京理工大學(xué)信息科學(xué)學(xué)院2/19/202568北京理工大學(xué)信息科學(xué)學(xué)院“與或”式和“或與”式是較為常用的表達(dá)式形式。同一種類型的邏輯表達(dá)式,其形式也不是唯一的。例如F的“與或”表達(dá)式：在一個邏輯函數(shù)的眾多的表達(dá)式中，有兩種標(biāo)準(zhǔn)的表達(dá)式形式。它們實(shí)際上是特殊的“與或”式和“或與”式。

2/19/202569北京理工大學(xué)信息科學(xué)學(xué)院2.4.1最小項(xiàng)和最大項(xiàng)1.最小項(xiàng)（標(biāo)準(zhǔn)積或規(guī)范積）由A、B、C三個邏輯變量所構(gòu)成的乘積項(xiàng)（“與”項(xiàng)）中，有一類特殊的乘積項(xiàng)，它們是：

這8個乘積項(xiàng)（“與”項(xiàng)）有如下三個特點(diǎn)：每一項(xiàng)都是由三個邏輯變量相“與”而構(gòu)成，即每項(xiàng)都有三個“因子”。

每個邏輯變量都是每一項(xiàng)的一個“因子”。2/19/202570北京理工大學(xué)信息科學(xué)學(xué)院在每一個乘積項(xiàng)中，每個邏輯變量或以原變量（A、B、C）的形式、或以反變量（）的形式出現(xiàn)一次。

這8個乘積項(xiàng)（“與”項(xiàng)）就稱為三邏輯變量A、B、C的“最小項(xiàng)”。n個變量的最小項(xiàng)是n個變量相“與”（乘積），其中每一個變量都以原變量的形式或反變量的形式出現(xiàn)、且僅出現(xiàn)一次。

對于n個變量來說，最小項(xiàng)的個數(shù)總共有2n個。當(dāng)n=3（三個變量）時，最小項(xiàng)有23=8個。

2/19/202571北京理工大學(xué)信息科學(xué)學(xué)院2/19/202572北京理工大學(xué)信息科學(xué)學(xué)院最小項(xiàng)的性質(zhì)性質(zhì)1：對于任意的一個最小項(xiàng)，只有一組變量的取值使得它的值為“1”，而在變量取其它各組值時，這個最小項(xiàng)的值都是“0”。最小項(xiàng)不同，使得它的值為“1”的那一組變量的取值也不同。使得某一個最小項(xiàng)的值為“1”的那組變量取值，就是該最小項(xiàng)中的原變量取“1”、反變量取“0”而組成的二進(jìn)制數(shù)。

n代表最小項(xiàng)中變量的個數(shù)，常省略之

通常用符號來表示最小項(xiàng)。

i代表最小項(xiàng)的編號，它是使最小項(xiàng)的值為“1”的變量取值的等效十進(jìn)制數(shù)。2/19/202573北京理工大學(xué)信息科學(xué)學(xué)院性質(zhì)2：任意兩個不同的最小項(xiàng)的乘積（相“與”）恒為“0”。性質(zhì)3：全體最小項(xiàng)之和（相“或”）恒為“1”。例如：2/19/202574北京理工大學(xué)信息科學(xué)學(xué)院n變量最小項(xiàng)也具有同樣的三個性質(zhì):每一個最小項(xiàng)僅和一組變量取值相對應(yīng)，只有在該組取值下這個最小項(xiàng)的值才為“1”，而在其它的取值下它都為“0”。

n個變量的任意兩個不同最小項(xiàng)的乘積（相“與”）恒為“0”，即：

n個變量的全體最小項(xiàng)之和（相“或”）恒為“1”，即：

2/19/202575北京理工大學(xué)信息科學(xué)學(xué)院2.最大項(xiàng)（標(biāo)準(zhǔn)和或規(guī)范和）由A、B、C三個邏輯變量所構(gòu)成的和項(xiàng)（“或”項(xiàng)）中，有一類特殊的和項(xiàng)，它們是：

每一項(xiàng)都是由三個邏輯變量相“或”而構(gòu)成，即每項(xiàng)都有三個“加數(shù)”。

每個邏輯變量都是每一項(xiàng)的一個“加數(shù)”。

這8個和項(xiàng)（“或”項(xiàng)）有如下三個特點(diǎn)：2/19/202576北京理工大學(xué)信息科學(xué)學(xué)院在每一個和項(xiàng)中，每個邏輯變量或以原變量（A、B、C）的形式，或以反變量（）的形式出現(xiàn)一次。

這8個和項(xiàng)（“或”項(xiàng)）就稱為三邏輯變量A、B、C的“最大項(xiàng)”。n個變量的最大項(xiàng)是n個變量相“或”（和），其中每一個變量都以原變量的形式或反變量的形式出現(xiàn)、且僅出現(xiàn)一次。

對于n個變量來說，最大項(xiàng)的個數(shù)總共有2n個。當(dāng)n=3（三個變量）時，最大項(xiàng)有23=8個。

2/19/202577北京理工大學(xué)信息科學(xué)學(xué)院2/19/202578北京理工大學(xué)信息科學(xué)學(xué)院最大項(xiàng)的性質(zhì)性質(zhì)1：對于任意的一個最大項(xiàng)，只有一組變量的取值使得它的值為“0”，而在變量取其它各組值時，這個最大項(xiàng)的值都是“1”。最大項(xiàng)不同，使得它的值為“0”的那一組變量的取值也不同。使得某一個最大項(xiàng)的值為“0”的那組變量取值，就是該最大項(xiàng)中的原變量取“0”、反變量取“1”而組成的二進(jìn)制數(shù)。n代表最大項(xiàng)中變量的個數(shù)，常省略之。

j代表最大項(xiàng)的編號，它是使最大項(xiàng)的值為“0”的變量取值的等效十進(jìn)制數(shù)。通常用符號來表示最大項(xiàng)。

2/19/202579北京理工大學(xué)信息科學(xué)學(xué)院性質(zhì)2：任意兩個不同的最大項(xiàng)的和（相“或”）恒為“1”。性質(zhì)3：全體最大項(xiàng)之積（相“與”）恒為“0”。例如：2/19/202580北京理工大學(xué)信息科學(xué)學(xué)院n變量最大項(xiàng)也具有同樣的三個性質(zhì):每一個最大項(xiàng)僅和一組變量取值相對應(yīng)，只有在該組取值下這個最大項(xiàng)的值才為“0”，而在其它的取值下它都為“1”。

n個變量的任意兩個不同最大項(xiàng)的和（相“或”）恒為“1”，即：

n個變量的全體最大項(xiàng)之積（相“與”）恒為“0”，即：

2/19/202581北京理工大學(xué)信息科學(xué)學(xué)院3.最小項(xiàng)與最大項(xiàng)的關(guān)系變量相同且編號相同的最小項(xiàng)和最大項(xiàng)之間，存在著互補(bǔ)的關(guān)系。即：2/19/202582北京理工大學(xué)信息科學(xué)學(xué)院2/19/202583北京理工大學(xué)信息科學(xué)學(xué)院2.4.2標(biāo)準(zhǔn)表達(dá)式和真值表1.兩種標(biāo)準(zhǔn)表達(dá)式最小項(xiàng)之和式是由若干個最小項(xiàng)相“加”（相“或”）而構(gòu)成，它也叫標(biāo)準(zhǔn)“與或”式。

例如：(1)最小項(xiàng)之和式2/19/202584北京理工大學(xué)信息科學(xué)學(xué)院【例2.1】把展開為最小項(xiàng)之和式。解：任何一個邏輯函數(shù)表達(dá)式都可以被展開成唯一的最小項(xiàng)之和式；換句話說，用最小項(xiàng)之和這種形式可以表達(dá)任何一個邏輯函數(shù)。

2/19/202585北京理工大學(xué)信息科學(xué)學(xué)院解：【例2.2】將展開成最小項(xiàng)之和式。2/19/202586北京理工大學(xué)信息科學(xué)學(xué)院最大項(xiàng)之積式是由若干個最大項(xiàng)相“乘”（相“與”）而構(gòu)成，它也叫標(biāo)準(zhǔn)“或與”式。例如：(2)最大項(xiàng)之積式2/19/202587北京理工大學(xué)信息科學(xué)學(xué)院解：【例2.3】把展開為最大項(xiàng)之積式。2/19/202588北京理工大學(xué)信息科學(xué)學(xué)院解：【例2.4】將展開成最大項(xiàng)之積式。

2/19/202589北京理工大學(xué)信息科學(xué)學(xué)院任何一個邏輯函數(shù)表達(dá)式都可以被展開成唯一的最大項(xiàng)之積式；換句話說，用最大項(xiàng)之積這種形式可以表達(dá)任何一個邏輯函數(shù)。

最小項(xiàng)之和式和最大項(xiàng)之積式是邏輯函數(shù)的兩種標(biāo)準(zhǔn)表達(dá)式。

2/19/202590北京理工大學(xué)信息科學(xué)學(xué)院2.真值表與標(biāo)準(zhǔn)表達(dá)式最小項(xiàng)之和式或者最大項(xiàng)之積式與真值表之間具有一一對應(yīng)的關(guān)系，知道了一個就可以求出另一個。

例如：只有當(dāng)ABC的取值為“011”、“101”和“110”時，函數(shù)F的值才為“1”；而當(dāng)ABC的取值為其它值時，F(xiàn)的值為“0”。列出函數(shù)F的真值表2/19/202591北京理工大學(xué)信息科學(xué)學(xué)院例如：只有當(dāng)ABC的取值為“000”、“011”、“101”和“110”時，函數(shù)G的值才為“0”；而當(dāng)ABC的取值為其它值時，G的值為“1”。列出函數(shù)G的真值表。2/19/202592北京理工大學(xué)信息科學(xué)學(xué)院函數(shù)F的最小項(xiàng)之和式，實(shí)際上就是由真值表中F=1的各行相應(yīng)的變量取值所對應(yīng)的最小項(xiàng)相“或”而構(gòu)成。函數(shù)G

的最大項(xiàng)之積式，實(shí)際上就是由真值表中G=0的各行相應(yīng)的變量取值所對應(yīng)的最大項(xiàng)相“與”而構(gòu)成。

在寫各最小項(xiàng)時，應(yīng)分別將各F=1的那一行所對應(yīng)的變量取值中“1”代以原變量，而“0”代以反變量，再把這些變量（原變量和反變量）相“乘”（相“與”），從而構(gòu)成一個最小項(xiàng)；同樣，在寫各最大項(xiàng)時，應(yīng)分別將各F=0的那一行所對應(yīng)的變量取值中“0”代以原變量，而“1”代以反變量，再把這些變量（原變量和反變量）相“加”（相“或”），從而構(gòu)成一個最大項(xiàng)。2/19/202593北京理工大學(xué)信息科學(xué)學(xué)院解：【例2.5】已知函數(shù)F的真值表如表2.19所示。試寫出F的最小項(xiàng)之和式和最大項(xiàng)之積式。函數(shù)F的最小項(xiàng)之和式為：

函數(shù)F的最大項(xiàng)之積式為：2/19/202594北京理工大學(xué)信息科學(xué)學(xué)院3.兩種標(biāo)準(zhǔn)表達(dá)式之間的關(guān)系某個函數(shù)的最大項(xiàng)之積式中的最大項(xiàng)的編號正好是該函數(shù)的最小項(xiàng)之和式中的最小項(xiàng)編號中未包含的號碼，反之亦然。

設(shè)：任意給定一個n變量的邏輯函數(shù)F，它的最小項(xiàng)之和式為：

因?yàn)槿w最小項(xiàng)之和為“1”，即：2/19/202595北京理工大學(xué)信息科學(xué)學(xué)院所以，邏輯函數(shù)F的最小項(xiàng)之和中所不包含的那些最小項(xiàng)的“和”就構(gòu)成了邏輯函數(shù)F的反函數(shù)的最小項(xiàng)之和式，即：所以：2/19/202596北京理工大學(xué)信息科學(xué)學(xué)院知道了邏輯函數(shù)F的兩種標(biāo)準(zhǔn)表達(dá)式之間“項(xiàng)號互補(bǔ)”的關(guān)系規(guī)律以后，就可以很容易地由一種標(biāo)準(zhǔn)表達(dá)式推出另一種標(biāo)準(zhǔn)表達(dá)式。【例2.6】已知函數(shù),試寫出F的最大項(xiàng)之積式。解：根據(jù)兩種標(biāo)準(zhǔn)表達(dá)式所含項(xiàng)的編號在0

~24-1的范圍內(nèi)互補(bǔ)的規(guī)律知：2/19/202597北京理工大學(xué)信息科學(xué)學(xué)院作業(yè)4：2-25，2-26，思考2-27，2-302/19/202598北京理工大學(xué)信息科學(xué)學(xué)院§2.5邏輯函數(shù)的代數(shù)化簡法2.5.1

化簡邏輯函數(shù)的意義及化簡方法一個邏輯函數(shù)可以歸納出五種主要的形式。例如函數(shù)：2/19/202599北京理工大學(xué)信息科學(xué)學(xué)院實(shí)現(xiàn)“與或”表達(dá)式AABC實(shí)現(xiàn)“或與”表達(dá)式ACBA實(shí)現(xiàn)“與非-與非”表達(dá)式AABC實(shí)現(xiàn)“或非-或非”表達(dá)式ACBA實(shí)現(xiàn)“與或非”表達(dá)式ABAC2/19/2025100北京理工大學(xué)信息科學(xué)學(xué)院(a)AABC(b)ACBCAB(c)ACBCABCAABBC2/19/2025101北京理工大學(xué)信息科學(xué)學(xué)院首先討論如何將一個“與或”表達(dá)式化為最簡“與或”表達(dá)式。這是因?yàn)椋喝魏我粋€邏輯函數(shù)表達(dá)式都能展開成一個“與或”表達(dá)式；從一個最簡“與或”表達(dá)式，可以很容易地得到“與非-與非”、“與或非”等形式的表達(dá)式；只要掌握了“與或”表達(dá)式的化簡方法，利用對偶式，就不難化簡“或與”表達(dá)式。

最簡“與或”表達(dá)式的標(biāo)準(zhǔn)：首先，表達(dá)式中乘積項(xiàng)（“與”項(xiàng)）的個數(shù)應(yīng)該是最少的；其次，在滿足上述條件的前提下，要求每一個乘積項(xiàng)中所含的變量個數(shù)最少。

2/19/2025102北京理工大學(xué)信息科學(xué)學(xué)院乘積項(xiàng)的個數(shù)最少，就意味著電路中所用到的“與”門個數(shù)最少、所用“或”門的輸入端子個數(shù)最少（“或”門的規(guī)模最?。?；每個乘積項(xiàng)中所含的變量個數(shù)最少，就意味著每個“與”門所含輸入端子個數(shù)最少（“與”門的規(guī)模最?。?。

在以后的化簡中，均假定原變量（如A，B，C，……）和反變量（如）都已經(jīng)存在。

化簡邏輯函數(shù)的常用方法:代數(shù)化簡法?？ㄖZ圖化簡法。

系統(tǒng)化簡法：也叫Q-M法，或稱列表法。

2/19/2025103北京理工大學(xué)信息科學(xué)學(xué)院2.5.2代數(shù)化簡法1.“與或”表達(dá)式的化簡例如：(1)并項(xiàng)利用“合并定理”和“互補(bǔ)律”，將兩項(xiàng)合并為一項(xiàng)，同時消去一個“因子”（變量）。

2/19/2025104北京理工大學(xué)信息科學(xué)學(xué)院2/19/2025105北京理工大學(xué)信息科學(xué)學(xué)院(2)消項(xiàng)利用“吸收定理”和“添加項(xiàng)定理”，消去多余的項(xiàng)。

例如：2/19/2025106北京理工大學(xué)信息科學(xué)學(xué)院2/19/2025107北京理工大學(xué)信息科學(xué)學(xué)院(3)消元例如：利用“吸收定理”,消去多余的“因子”。

2/19/2025108北京理工大學(xué)信息科學(xué)學(xué)院(4)配項(xiàng)例如：(1)利用“互補(bǔ)律”，把它代入邏輯函數(shù)式中作配項(xiàng)用，然后再消去更多的項(xiàng)。2/19/2025109北京理工大學(xué)信息科學(xué)學(xué)院例如：(2)利用“重疊律”，在邏輯函數(shù)式中重復(fù)寫一項(xiàng)，有時可以得到更簡單的結(jié)果。2/19/2025110北京理工大學(xué)信息科學(xué)學(xué)院例如：(3)利用“添加項(xiàng)定理”和“重疊律”，在邏輯函數(shù)式中先添項(xiàng)、再消項(xiàng)，有時也能得到更簡單的結(jié)果。

2/19/2025111北京理工大學(xué)信息科學(xué)學(xué)院注意到此處F1的化簡形式與上述(1)中F1的化簡形式不一樣，但它們都是的最簡“與或”式，這可以用真值表加以證明。這也說明“與或”表達(dá)式的最簡形式，在某些情況下是不唯一的。2/19/2025112北京理工大學(xué)信息科學(xué)學(xué)院【例2.7】求的最簡“與或”式。解：2/19/2025113北京理工大學(xué)信息科學(xué)學(xué)院2.“或與”表達(dá)式的化簡最簡“或與”式的標(biāo)準(zhǔn)是“或項(xiàng)”（“和”項(xiàng)）最少、每個“或項(xiàng)”所含的變量個數(shù)最少。

利用對偶式化簡“或與”式會更方便?，F(xiàn)示意如下：F（“或與”式）（“與或”式）F（最簡“或與”式）求對偶式（最簡“與或”式）求對偶式化簡2/19/2025114北京理工大學(xué)信息科學(xué)學(xué)院【例2.9】求邏輯函數(shù)的最簡“或與”式。解：（1）求：（2）化簡：2/19/2025115北京理工大學(xué)信息科學(xué)學(xué)院3.其他類型邏輯表達(dá)式的化簡“與非—與非”表達(dá)式的最簡標(biāo)準(zhǔn)是：表達(dá)式的“非”號最少，（不計(jì)算單個變量上的“非”號，即假定原變量和反變量都已存在）；其次，每個“非”號下的變量個數(shù)最少（單個變量除外）。

用“求反加非”和反演律將已化簡的最簡“與或”式變換為最簡“與非—與非”表達(dá)式。（3）求，即F：（1）最簡“與非—與非”表達(dá)式2/19/2025116北京理工大學(xué)信息科學(xué)學(xué)院解：（1）求函數(shù)F之最簡“與或”式：【例2.10】用最少的“與非”門實(shí)現(xiàn)。

（2）把F之最簡“與或”式“求反加非”變換為最簡“與非—與非”式：BDAD2/19/2025117北京理工大學(xué)信息科學(xué)學(xué)院（2）最簡“或非—或非”表達(dá)式“或非—或非”表達(dá)式的最簡標(biāo)準(zhǔn)是：表達(dá)式的“非”號最少，（不計(jì)算單個變量上的“非”號，即假定原變量和反變量都已存在）；每個“非”號下的變量個數(shù)最少（單個變量除外）。用“求反加非”和反演律將已化簡的最簡“或與”式變換為最簡“或非—或非”表達(dá)式。解：【例2.11】用最少的“或非”門實(shí)現(xiàn)。

（1）求函數(shù)F之反函數(shù)F：2/19/2025118北京理工大學(xué)信息科學(xué)學(xué)院（2）求函數(shù)F之最簡“與或”式：（3）求函數(shù)F之最簡“或與”式：（4）求函數(shù)F之最簡“或非—或非”式：DBAD2/19/2025119北京理工大學(xué)信息科學(xué)學(xué)院（3）最簡“與或非”表達(dá)式“與或非”表達(dá)式的最簡標(biāo)準(zhǔn)和“與或”表達(dá)式的最簡標(biāo)準(zhǔn)完全一樣。即，“與”項(xiàng)的個數(shù)最少；每個“與”項(xiàng)所含變量的個數(shù)最少。

對F之最簡“與或”式“求反”，即可得到F之最簡“與或非”式。2/19/2025120北京理工大學(xué)信息科學(xué)學(xué)院邏輯函數(shù)表達(dá)式的常用變換方法：F之最簡“與或”式F之最簡“與非—與非”式求反加非F之最簡“與或”式F之最簡“或與”式反演F之最簡“或與”式F之最簡“或非—或非”式求反加非F之最簡“或與”式F之最簡“與或”式反演F之最簡“與或”式F之最簡“與或非”式加一非2/19/2025121北京理工大學(xué)信息科學(xué)學(xué)院作業(yè)5：2-31，2-33的（2）、（4），2-34的（1）、（3），2-35的（2），（3）2/19/2025122北京理工大學(xué)信息科學(xué)學(xué)院§2.6邏輯函數(shù)的卡諾圖化簡法2.6.1

卡諾圖（K圖）“邏輯相鄰”項(xiàng)：例如：AB+AB=A，

ABCD+ABCD=ABC。

任意兩個變量個數(shù)相同的最小項(xiàng)，如果組成它們的各個變量（原變量或反變量）中,只有一個變量互補(bǔ)（互反）而其余變量均相同（同為原變量或反變量）時，就稱這兩個最小項(xiàng)是邏輯相鄰的最小項(xiàng)，簡稱“邏輯相鄰項(xiàng)”或“相鄰項(xiàng)”。

ABC+ABC=BC，

2/19/2025123北京理工大學(xué)信息科學(xué)學(xué)院1.卡諾圖的構(gòu)成與特點(diǎn)把邏輯相鄰的最小項(xiàng)所對應(yīng)的小方塊按幾何位置相鄰排列在一起，就得到了一個n變量最小項(xiàng)的方塊圖表示。這種最小項(xiàng)的方塊圖表示方法是由美國人卡諾（Karnaugh）首先提出的，所以稱之為卡諾圖（KarnaughMap），簡稱K圖。

2/19/2025124北京理工大學(xué)信息科學(xué)學(xué)院三變量卡諾圖的構(gòu)成2/19/2025125北京理工大學(xué)信息科學(xué)學(xué)院二變量卡諾圖；四變量卡諾圖；五變量卡諾圖

2/19/2025126北京理工大學(xué)信息科學(xué)學(xué)院K圖具有如下特點(diǎn)：

n變量的K圖有2n個小方格，每個小方格代表一個最小項(xiàng)。變量按行、列分成兩組，每組變量的取值（編碼）不是按自然二進(jìn)制數(shù)碼順序排列而是按格雷碼（循環(huán)碼）的順序排列。K圖上位于水平方向中心軸或垂直方向中心軸兩側(cè)對稱的小格所代表的最小項(xiàng)在邏輯上是相鄰的。所以位于K圖上任何一行或一列兩端上的小方格所代表的最小項(xiàng)是邏輯相鄰的，即它們相互之間僅有一個變量互補(bǔ)。對于五變量的情形，要把“A=1”的卡諾圖看成是重疊在“A=0”的卡諾圖上。2/19/2025127北京理工大學(xué)信息科學(xué)學(xué)院三變量卡諾圖的幾種畫法（形式）2/19/2025128北京理工大學(xué)信息科學(xué)學(xué)院變量次序?qū)ㄖZ圖小格標(biāo)號的影響2/19/2025129北京理工大學(xué)信息科學(xué)學(xué)院2.邏輯函數(shù)的卡諾圖表示將所有最小項(xiàng)所對應(yīng)的小方格里都填寫“1”，而其余的小方格里都填寫“0”。任何一個邏輯函數(shù)都等于其卡諾圖上填“1”的那些小方格所對應(yīng)的最小項(xiàng)之和。

（1）邏輯函數(shù)為最小項(xiàng)之和式2/19/2025130北京理工大學(xué)信息科學(xué)學(xué)院由函數(shù)的最大項(xiàng)之積式填寫K圖時，應(yīng)將卡諾圖上編號與表達(dá)式中最大項(xiàng)編號相同的小方格里都填寫“0”，而其余的小方格里都填寫“1”。任何一個邏輯函數(shù)都等于編號與其卡諾圖上填“0”的那些小方格的編號相同的最大項(xiàng)之積。

（2）邏輯函數(shù)為最大項(xiàng)之積式2/19/2025131北京理工大學(xué)信息科學(xué)學(xué)院最小項(xiàng)與最大項(xiàng)的名稱來源相對于填“1”來講，m7只占了編號為7的一個小格；而M7卻占據(jù)了除7號小格以外的所有小方格。這就是最小項(xiàng)和最大項(xiàng)名稱的由來。

卡諾圖也證明了最小項(xiàng)和最大項(xiàng)的互補(bǔ)關(guān)系。

2/19/2025132北京理工大學(xué)信息科學(xué)學(xué)院若卡諾圖上的某個小方格所代表的最小項(xiàng)，在真值表里所對應(yīng)的函數(shù)F取值為“1”，則該小方格里填“1”;否則就填“0”。（3）邏輯函數(shù)為真值表的形式2/19/2025133北京理工大學(xué)信息科學(xué)學(xué)院將“與或”式中所有“與項(xiàng)”在卡諾圖中所覆蓋的區(qū)域內(nèi)的所有小方格都填“1”（已經(jīng)填過“1”的小格除外），其余都填“0”。（4）邏輯函數(shù)為一般“與或”式2/19/2025134北京理工大學(xué)信息科學(xué)學(xué)院將“或與”式中所有“或項(xiàng)”在卡諾圖中所覆蓋的區(qū)域內(nèi)的所有小方格都填“0”（已經(jīng)填過“0”的小格除外），其余都填“1”。

（5）邏輯函數(shù)為一般“或與”式2/19/2025135北京理工大學(xué)信息科學(xué)學(xué)院先將這些表達(dá)式變換為“與或”式或者“或與”式（根據(jù)實(shí)際情況而定），然后再填寫卡諾圖。（6）邏輯函數(shù)為其他形式的邏輯表達(dá)式【例2.14】求函數(shù)之K圖。

解:2/19/2025136北京理工大學(xué)信息科學(xué)學(xué)院3.卡諾圖的性質(zhì)與運(yùn)算卡諾圖具有如下性質(zhì)：若F之K圖中所有的小格都填“1”，則F=1。

（最小項(xiàng)的性質(zhì)）2/19/2025137北京理工大學(xué)信息科學(xué)學(xué)院若F之K圖中所有的小格都填“0”，則F=0。

（最大項(xiàng)的性質(zhì)）2/19/2025138北京理工大學(xué)信息科學(xué)學(xué)院卡諾圖反演（非運(yùn)算）。若將F之K圖中，所有小格內(nèi)的“0”都換成“1”、“1”都換成“0”，則得到之K圖。求反2/19/2025139北京理工大學(xué)信息科學(xué)學(xué)院卡諾圖的運(yùn)算：

若函數(shù)F為某兩個函數(shù)F1和F2相“與”而構(gòu)成，則F之K圖等于F1之K圖和F2之K圖的“與”。=?F1之K圖F2之K圖F

之K圖所謂兩張K圖相“與”，是指這兩張K圖中所有相應(yīng)位置的小格內(nèi)容（“0”或“1”）分別相“與”。2/19/2025140北京理工大學(xué)信息科學(xué)學(xué)院兩個函數(shù)相“或”之K圖等于這兩個函數(shù)各自的K圖相“或”。=+兩個K圖相“或”，是指這兩個K圖中所有相應(yīng)位置的小格內(nèi)容（“0”或“1”）分別相“或”。

2/19/2025141北京理工大學(xué)信息科學(xué)學(xué)院兩個函數(shù)相“異或”，其K圖等于這兩個函數(shù)各自的K圖相“異或”。=兩個K圖相“異或”，是指這兩個K圖中所有相應(yīng)位置的小格內(nèi)容（“0”或“1”）分別相“異或”。

＋2/19/2025142北京理工大學(xué)信息科學(xué)學(xué)院2.6.2最小項(xiàng)的合并規(guī)律卡諾圖恰恰是把“邏輯”上相鄰的最小項(xiàng)，用“幾何位置相鄰”的小格直觀地表示出來。

把兩個邏輯相鄰的最小項(xiàng)合并（相“或”）在一起，結(jié)果將產(chǎn)生一個“與項(xiàng)”，并消去一個邏輯變量。例如：

2/19/2025143北京理工大學(xué)信息科學(xué)學(xué)院2/19/2025144北京理工大學(xué)信息科學(xué)學(xué)院K圖上四個相鄰的最小項(xiàng)可以合并為一個“與項(xiàng)”，同時消去兩個變量。例如：

2/19/2025145北京理工大學(xué)信息科學(xué)學(xué)院2/19/2025146北京理工大學(xué)信息科學(xué)學(xué)院最小項(xiàng)的合并規(guī)則為：

對于n變量的邏輯函數(shù)，在其K圖中，只能按2i個（i=0，1，2，……，n）相鄰的最小項(xiàng)（小格）圈組合并，合并后消去i個變量保留n-i個變量，這n-i個變量是這些相鄰最小項(xiàng)的公共因子，它們構(gòu)成一個“與項(xiàng)”。這2i個最小項(xiàng)必須是邏輯相鄰。在K圖上，就是代表最小項(xiàng)的小格在幾何位置上的相鄰。不但“緊挨著”的小格是“相鄰”的；而且位于行、列兩端以及四角和兩邊，即完全呈軸對稱的小格，也應(yīng)視為“相鄰”。2/19/2025147北京理工大學(xué)信息科學(xué)學(xué)院2/19/2025148北京理工大學(xué)信息科學(xué)學(xué)院2.6.3用卡諾圖化簡邏輯函數(shù)利用卡諾圖化簡邏輯函數(shù)的一般步驟如下：（1）根據(jù)邏輯函數(shù)的變量個數(shù)畫出相應(yīng)的卡諾圖框。

（2）按給定的邏輯函數(shù)形式填寫卡諾圖框。

（3）對K圖上相鄰的填“1”小格（最小項(xiàng)）進(jìn)行圈組合并（不相鄰的填“1”小格不能圈在一起）,合并的原則是：K圖上的每一個填“1”小格都要被卡諾圈所覆蓋，也就是說，每一個“1”都至少被圈組合并一次。

1.求邏輯函數(shù)的最簡“與或”式在滿足上一條件情況下,K圖上卡諾圈的個數(shù)要盡量地少。

2/19/2025149北京理工大學(xué)信息科學(xué)學(xué)院為了做到上述兩點(diǎn)，要求每個卡諾圈所包含的填“1”小格的個數(shù)要盡量地多，但必須是2i(i

=0,1,2,…,n)個。

每個卡諾圈都至少包含一個其它所有卡諾圈所不包含的填“1”小格（最小項(xiàng)）。換句話說，每個卡諾圈都必須至少有一個獨(dú)屬于它自己的填“1”小格。上述這四點(diǎn)要求就是所謂的最小覆蓋原則。（4）按“圈”寫“與或”式。每個卡諾圈對應(yīng)一個“與”項(xiàng)，再把各“與”項(xiàng)相“或”，從而構(gòu)成“與或”式。寫“與”項(xiàng)時，應(yīng)消去“圈”內(nèi)取值發(fā)生變化的變量，保留取值相同的變量。取值為“1”的變量寫成原變量；取值為“0”的變量寫成反變量。

2/19/2025150北京理工大學(xué)信息科學(xué)學(xué)院【例2.16】用卡諾圖化簡如下邏輯函數(shù)：①②④③CD

AB

00

01

11

10

00

1

1

1

1

01

1

0

0

0

11

0

0

1

1

10

1

0

1

1

圖2.37

利用卡諾圖化簡函數(shù)

),,,(DCBAF

解：2/19/2025151北京理工大學(xué)信息科學(xué)學(xué)院①畫卡諾圈時，要求“圈”的個數(shù)盡可能地少。

2/19/2025152北京理工大學(xué)信息科學(xué)學(xué)院②在畫卡諾圈時，要求被圈的小格盡可能地多些。

CD

AB

00

01

11

10

00

1

1

1

1

01

1

1

1

1

11

0

0

1

1

10

0

0

0

0

(a)圈法不恰當(dāng)

ABCAF+=

CD

AB

00

01

11

10

00

1

1

1

1

01

1

1

1

1

11

0

0

1

1

10

0

0

0

0

(b)圈法正確

BCAF+=

圖2.39卡諾圈的畫法②

2/19/2025153北京理工大學(xué)信息科學(xué)學(xué)院③卡諾圈中所圍小格的個數(shù)必須符合2i的形式。

④圈組合并的順序一般是“先多后少”。2.求邏輯函數(shù)的最簡“或與”式（1）利用函數(shù)F的反函數(shù)求最簡“或與”式在函數(shù)F的K圖上圈“0”寫“與”項(xiàng)，即，把“0”當(dāng)成“1”來圈組合并。然后，再把各“與”項(xiàng)相“或”從而得到F的最簡“與或”式。對F進(jìn)行反演運(yùn)算，就得到了函數(shù)F的最簡“或與”式。2/19/2025154北京理工大學(xué)信息科學(xué)學(xué)院

CD

AB

00

01

11

10

00

0

0

0

0

01

0

1

1

1

11

0

1

1

1

10

0

1

1

1

圖2.42例2.19函數(shù)之K圖

【例2.19】求下列函數(shù)的最簡“或與”式。解：（1）由給定函數(shù)F，畫出其K圖（2）圈組合并“0”，寫出“與”項(xiàng)，得到F

的最簡“與或”式。

（3）對F進(jìn)行反演運(yùn)算得到F的最簡“或與”式。

2/19/2025155北京理工大學(xué)信息科學(xué)學(xué)院（2）直接圈“0”寫“或”項(xiàng)得到函數(shù)F的最簡“或與”式在函數(shù)F的K圖上圈“0”寫“或”項(xiàng)，再把各“或”項(xiàng)相“與”，從而直接得到F的最簡“或與”式。寫“或”項(xiàng)時要注意，取值為“0”的變量，對應(yīng)原變量；取值為“1”的變量，對應(yīng)反變量。

CD

AB

00

01

11

10

00

0

0

0

0

01

0

1

1

1

11

0

1

1

1

10

0

1

1

1

圖2.42例2.19函數(shù)之K圖

圈組合并“0”，寫出“或”項(xiàng)，從而得到F的最簡“或與”式。

2/19/2025156北京理工大學(xué)信息科學(xué)學(xué)院2.6.4多輸出邏輯函數(shù)的卡諾圖化簡法【例2.21】化簡如下兩個邏輯函數(shù)：解：(1)用卡諾圖分別化簡F1和F2后得到：

BC

A

00

01

11

10

0

0

0

1

0

1

0

0

1

1

F1之K圖

BC

A

00

01

11

10

0

1

0

1

1

1

0

0

0

0

F2之K圖

2/19/2025157