1、2.1 概述2.1.1 事物的二值性 世界上的許多事物都具有完全不同的兩種狀態，這就是平時所說的事物的矛盾性。我們可以舉出很多這類完全對立的、處于矛盾狀態的例子，如表2.1所示。 7/17/20221北京理工大學 信息科學學院7/17/20222北京理工大學 信息科學學院2.1.2 布爾代數 “邏輯代數”是十九世紀的英國數學家喬治布爾(George Boole)在1847年首先創立的。 這是一種僅使用數值“1”和“0”的代數。注意，這里的“1”和“0”并不代表數量的大小，而是表示完全對立的兩個矛盾著的方面。 正是由于布爾構造出了二值代數系統，所以很多教科書上又把邏輯代數稱作“布爾代數”(Boo

2、lean Algebra)。 布爾代數在創建的初期僅僅是應用于研究概率的問題，由于時代和生產力水平的限制，當時的人們并沒有認識到這一代數理論的巨大應用前景。 7/17/20223北京理工大學 信息科學學院美國貝爾實驗室的科學家克勞迪香農(Claude Shannon)于1938年寫出了他那具有革命性的碩士論文繼電器和開關電路的一種符號分析（“A Symbolic Analysis of Relay and Switching Circuits”）時，人們才真正認識到布爾代數的實用價值。 香農把布爾代數應用到開關電路的分析和設計上，所以還有一些教課書上把“布爾代數”叫做“開關代數”（Switch

3、ing Algebra）。 7/17/20224北京理工大學 信息科學學院2.2 邏輯變量和邏輯函數 2.2.1 基本的邏輯運算和邏輯變量 所謂邏輯就是指事物的因果之間所應遵循的規律,最基本的邏輯關系可以歸納為“與”邏輯、“或”邏輯和“非”邏輯三種邏輯運算。 1.“與”邏輯開關A、B是串聯相接的，只有當兩個開關A、B全都閉合時，燈泡 F 才能點亮。 7/17/20225北京理工大學 信息科學學院2.“或”邏輯決定某個事件的所有條件全都具備時，這個事件才會發生的因果關系定義為“與”邏輯。開關A、B是并聯相接的，所以只要兩個開關A、B中有任何一個開關閉合、或者是二者全都閉合時，燈泡F就能點亮。 決

4、定某個事件的所有條件中只要有任意一個條件具備、或者是某幾個條件同時具備、或者是全都具備時，這個事件就會發生的因果關系定義為“或”邏輯。7/17/20226北京理工大學 信息科學學院3.“非”邏輯當開關A閉合時燈泡F是熄滅的，而在開關A斷開時，燈泡F才能點亮。 事件的發生與否和決定這個事件的條件是否具備的狀態剛好相反的因果關系定義為“非”邏輯。一個變量X如果僅有兩個可能的取值“0”或“1”，則稱這種僅有0、1兩個取值的變量為邏輯變量（以后簡稱為變量） 。 邏輯變量7/17/20227北京理工大學 信息科學學院可把表2.1所列舉的那些完全對立的矛盾狀態實例都用一個邏輯變量來描述。 7/17/202

5、28北京理工大學 信息科學學院7/17/20229北京理工大學 信息科學學院表2.1中對立矛盾的狀態與邏輯變量取值的對應關系完全是人為定義的。可以把表中“0”和“1”的位置對調一下而不失所述問題的合理性和一般性 。 開關A、B的“閉合”作為邏輯“1”，“斷開”作為邏輯“0”。 燈泡F的“點亮”作為邏輯“1”，“熄滅”作為邏輯“0” 。 這種反映因果邏輯關系的表叫做真值表。 對開關的“閉合”與“斷開”、燈泡的“點亮”與“熄滅”作如下的邏輯規定：7/17/202210北京理工大學 信息科學學院真值表的結構特點：真值表的左欄列出的是表示條件的邏輯變量以及這些變量取值的所有可能的組合。 真值表的右欄填

6、入的是表示事件的邏輯變量以及它對應于各條件變量取值的邏輯運算結果。 7/17/202211北京理工大學 信息科學學院最基本的邏輯是“與”、“或”、“非”，與之相對應的也有三種基本的邏輯運算。 邏輯運算：1.“與”運算（邏輯乘法）F = AB “AB”叫做邏輯表達式，它表示邏輯變量A和B做“與”運算（也叫邏輯乘法運算） 。 運算符號“ ”叫做“與”運算符 。 其他形式的“與”運算符有：“”、“”和“&” 。 7/17/202212北京理工大學 信息科學學院“與”運算的含義是：只有當A、B全為“1”時，F 才為“1”；A、B中只要有一個為“0”或者二者都為“0”時，F 就為“0”。 “與”運算的規

7、則就是：00=0， 01=0， 10=0， 11=1。 “與”運算規則與普通乘法的規律相同，但是含義卻不同。 我們采用符號“ ”作為“與”運算符，有時干脆省去“ ”而把 F = AB 寫成 F = AB。 7/17/202213北京理工大學 信息科學學院2.“或”運算（邏輯加法）F = A+B “A+B”也是邏輯表達式，它表示邏輯變量A和B做“或”運算(也叫邏輯加法運算)。 運算符號“+ ”叫做“或”運算符 。 其他形式的“或”運算符有：“”、“”和“|”。 “或”運算的含義是：A和B當中只要有一個為“1”或者全為“1”時，F 就為“1”；只有當A、B全為“0”時，F 才為“0” 。 我們采用

8、符號“+ ”作為“或”運算符。 7/17/202214北京理工大學 信息科學學院“或”運算的規則是：0+0=0， 0+1=1， 1+0=1， 1+1=1 。 “或”運算規則的前3條與普通加法的規律相同，但是含義不同。 “或”運算規則的最后1條與普通加法的規律在形式上和含義上均不相同。在這里，1+12，且1+1(10)。 要注意：邏輯運算不是數值運算，邏輯運算是因果關系的邏輯判斷。 7/17/202215北京理工大學 信息科學學院3.“非”運算上式表示邏輯變量F和A的取值相反，即A為“0”時F為“1”；而A為“1”時F為“0”。 “非”運算的運算規則就是：“非”運算是算術里所沒有的。 讀作“A非

9、”或者“A反”，有時也把“非”運算叫做求“補”運算，而把 讀作“A補”。 在邏輯代數中，只有“與”運算、“或”運算和“非”運算這三種基本邏輯運算，沒有其他的運算。邏輯變量的取值也只有“1”和“0”兩種，而不能有其他的取值。這些是和普通代數不同的。 7/17/202216北京理工大學 信息科學學院在邏輯代數中也有邏輯運算的前、后優先次序：單變量上的“非”運算優先級最高。 “與”運算（邏輯“乘”）要優先于“或”運算（邏輯“加”）。 括弧“（ ）”內的運算要優先于括弧外的運算。 多變量上的“非”運算相當于加括弧。 例如： 的運算順序是：先做 ，再做A+ ，最后再將所得結果與變量C相“與”。例如： 就

10、相當于 。7/17/202217北京理工大學 信息科學學院“與”、“或”、“非”這三種基本邏輯運算可分別由“與”門、“或”門和“非”門三種基本的邏輯門電路來實現。這三種基本門電路的邏輯符號如下所示 ：7/17/202218北京理工大學 信息科學學院2.2.2 邏輯函數 如果把“與”、“或”、“非”這三種基本邏輯運算組合成一個較為復雜的邏輯表達式，再把該邏輯表達式的運算結果（只能是“0”或“1”）賦予另一個邏輯變量，比如說F，于是就構成了一個邏輯函數。例如： F叫做邏輯因變量，即：邏輯函數。 F是邏輯自變量A、B、C、D的邏輯函數。 其中A、B、C、D叫做邏輯自變量，叫做邏輯表達式。7/17/2

11、02219北京理工大學 信息科學學院無論是邏輯自變量的定義域還是邏輯函數的值域都只能是“0”或“1”而不能是其它的取值。 邏輯函數是一個四變量的邏輯函數，可以抽象地記為： 四變量邏輯函數的四個變量A、B、C、D的取值組合總共有十六組（0000至1111）。 對于A、B、C、D四個變量的十六組取值都有一個確定的F取值（只能是“0”或“1”）與之對應。 邏輯函數和邏輯表達式與普通函數和算術表達式，有著本質的區別 。 7/17/202220北京理工大學 信息科學學院一般的多變量邏輯函數可以記為： 邏輯函數有時也被稱作開關函數。 三種基本邏輯運算,即： 就是三個最基本的邏輯函數。前兩個是兩變量邏輯函數

12、；而最后一個是單變量邏輯函數。 邏輯函數的相等：若兩個邏輯函數F和G的輸入變量相同，而且對于任意的一組變量取值都有相同的函數值，則這兩個函數相等，記作：F=G。換句話說，就是任何形式的兩個邏輯函數，只要它們的真值表相同，則彼此相等。 7/17/202221北京理工大學 信息科學學院任何一個邏輯操作的過程，都可用一個具有若干個邏輯變量的邏輯函數來描述，并可用一個與此函數相對應的邏輯電路來實現。先看一個例子。 LK下K上220V 樓梯照明電路原理圖用邏輯變量F代表電燈L，并規定F=1表示燈亮，而F=0則表示燈滅；再用邏輯變量A、B分別表示兩個開關K上、K下的位置，并規定“1”表示向上扳，而“0”表

13、示向下扳。 7/17/202222北京理工大學 信息科學學院A、B叫做輸入邏輯變量；F叫做輸出邏輯變量。 A、B也叫邏輯自變量，而F也叫邏輯因變量或邏輯函數。 邏輯函數和真值表各自都能完全地描述一個邏輯操作的過程。 一個邏輯函數對應了一張真值表；而一張真值表也對應了一個（或若干個）邏輯函數。 邏輯函數叫做“同或”邏輯函數。 其特點是：當A、B相同時，函數F為“1”，否則F為“0”。通常是把輸入邏輯變量(邏輯自變量)列在真值表的左邊；而把輸出邏輯變量(邏輯函數)列在真值表的右邊。 7/17/202223北京理工大學 信息科學學院邏輯函數和邏輯電路是相互對應的。邏輯函數可以由邏輯電路來實現；而邏輯

14、電路也可以由邏輯函數來描述。 2.2.3 邏輯函數與邏輯電路的關系例如，上一節所提到的“同或”邏輯函數就可以用下面的邏輯電路來實現它。 FAB “同或”邏輯電路7/17/202224北京理工大學 信息科學學院反之，如果給出一個邏輯電路，就可以根據這個邏輯電路寫出用于描述該邏輯電路輸入信號（變量）和輸出信號（變量）之間關系的邏輯函數。 例如，給出下面的邏輯電路圖FAB “異或”邏輯電路可以寫出描述該電路輸出信號F與輸入信號A、B之間關系的邏輯函數表達式為： 7/17/202225北京理工大學 信息科學學院邏輯函數叫做“異或”邏輯函數。 其特點是：當A、B相異時，函數F為“1”，否則F為“0”。2

15、.3 邏輯代數的基本運算規律 2.3.1 邏輯代數的基本定律1.邏輯代數公理邏輯代數公理（或者叫基本原理）是整個邏輯代數系統的基石，以這些公理為出發點，可以證明所有邏輯代數系統中的各種定律和定理。 7/17/202226北京理工大學 信息科學學院邏輯代數公理實際上是邏輯常數“1”和“0”的基本運算規則。這些運算規則可直接由“與”、“或”和“非”的運算定義得出。這些公理歸納于下表： 7/17/202227北京理工大學 信息科學學院根據邏輯代數的公理，可以推導出邏輯代數運算的一些基本定律。下表給出了這些基本定律。 2.邏輯代數的基本運算規律7/17/202228北京理工大學 信息科學學院證明上表所

16、示基本定律的最有效的方法就是使用真值表，即，分別作出等式兩邊邏輯表達式的真值表，然后檢驗其結果是否相同。 例如：證明上表中的反演律。為此分別作出兩個等式的等號兩邊邏輯表達式的真值表，如表2.8和表2.9所示。 7/17/202229北京理工大學 信息科學學院從表2.8和表2.9知： 這就是著名的狄摩根(DeMorgan)定理。在邏輯代數的運算中經常會用到狄摩根定理，它是一個非常重要的定理。 也可以用代數的方法來證明表2.7所列出的邏輯代數基本定律。 例如：可以用摩根定理、還原律和分配律的6號公式去證明分配律的6號公式。證明過程如下： （還原律） （摩根定理） （分配律6號） （摩根定理） 7/

17、17/202230北京理工大學 信息科學學院作業1：2-8，2-9的（1）、（2）、（3）、（8）、（9）（還原律） 2.3.2 三個重要規則1.代入規則任何一個邏輯等式，如果將等式兩邊所出現的同一個邏輯變量都代之以同一個邏輯函數，則該邏輯等式仍然成立，這就是代入規則。代入規則也叫代入定理。 7/17/202231北京理工大學 信息科學學院(結合律,摩根定理) 這就是三個變量的摩根定理。同理可以證明n個變量的摩根定理，即： 例如:摩根定理是再令：代入后一個等式，于是得到： 現在令：代入前一個等式；(結合律,摩根定理) 7/17/202232北京理工大學 信息科學學院2. 反演規則 若兩個邏輯函

18、數F和G的輸入變量相同，而且F和G對于任意的一組輸入變量取值都有相反的函數值，則稱這兩個函數互反（或叫互補），記作： 或 。 反演規則的內容如下： 對于任意的邏輯函數F，如果對其表達式做下述三種變換： 把原表達式中所有的“ ”運算符換成“+”運算符，同時把所有的“+”運算符換成“ ”運算符；把原表達式中所有的邏輯常量“0”換成邏輯常量“1”，而把所有的邏輯常量“1”換成邏輯常量“0”； 7/17/202233北京理工大學 信息科學學院把原表達式中所有的原變量換成反變量，再把所有的反變量換成原變量。 則若則反演規則實際上是反演律（摩根定理）在求邏輯函數F的反（補）函數時的一種推廣。它提供了一種可

19、以由邏輯函數F的表達式（較復雜時）直接求出其反（補）函數的方法。 例如：可直接寫出：若于是就得到了函數F的反函數F。例如：7/17/202234北京理工大學 信息科學學院例如：則而例如：則絕對不能打亂原表達式的運算順序；不屬于單變量上的非號應保持不變。在運用反演規則時必須注意以下兩點： 若若 是F 的反函數，F 也是 的反函數。F和 互為反函數。 7/17/202235北京理工大學 信息科學學院3. 對偶規則 對偶式的概念：對于任意的邏輯函數F，如果對其表達式做下述三種變換： 把原表達式中所有的“ ”運算符換成“+”運算符，同時把所有的“+”運算符換成“ ”運算符； 把原表達式中所有的邏輯常量

20、“0”換成邏輯常量“1”，而把所有的邏輯常量“1”換成邏輯常量“0”； 原表達式中所有的原變量和反變量均保持不變。 則由此所得到的新邏輯表達式就是原邏輯函數F表達式的對偶式（對偶函數），記作：F。 7/17/202236北京理工大學 信息科學學院例如：若：則：若：則：若：則：若：則：F是F 的對偶式，F 也是F的對偶式。F 和F互為對偶式。 在求一個函數表達式的對偶式時也不能打亂原表達式的運算順序 。 在一般情況下 。 7/17/202237北京理工大學 信息科學學院表2.7所列出的基本定律中，右邊帶撇的標號所對應的公式兩邊的表達式，都是左邊不帶撇的標號所對應的公式兩邊表達式的對偶式。 對偶規

21、則：如果兩個函數相等，則它們的對偶函數（對偶式）也相等。即：若 則 。 運用對偶規則，使需要記憶和證明的公式數量減少一半。對偶規則給簡化和變換邏輯函數帶來方便。 7/17/202238北京理工大學 信息科學學院2.3.3 邏輯代數的基本定理7/17/202239北京理工大學 信息科學學院證明表2.10所列出定理的最根本方法就是利用真值表。 在利用邏輯代數的方法證明表2.10中各定理時要用到邏輯代數的公理、基本定律、已獲證明的其他定理和三個重要規則。 （1）證明“合并定理”公式1：證明： （分配律）（互補律）（自等律）也可以利用邏輯代數的方法證明表2.10所列出的各定理。 7/17/202240

22、北京理工大學 信息科學學院（自等律）（2）證明“吸收定理”的公式2：證明： （自等律、分配律）（0-1律）（互補律）（3）證明“吸收定理”的公式3：證明： （吸收定理公式2）（分配律）（自等律）7/17/202241北京理工大學 信息科學學院(交換律、結合律)（4）證明“添加項定理”的公式4：證明： (互補律、自等律)(分配律)(分配律)(0-1律、自等律) 7/17/202242北京理工大學 信息科學學院(互補律)（5）證明表2.10的公式6：證明： (摩根定理)(還原律)(分配律)(自等律) (摩根定理)(添加項定理)將“對偶規則”分別運用于表2.10中的公式1公式6就可以分別證明表2.1

23、0中的公式1公式6。 7/17/202243北京理工大學 信息科學學院作業2：2-9的（4）、（5）、（6）、（7），2-10，2-117/17/202244北京理工大學 信息科學學院2.3.4 復合邏輯運算和復合邏輯門 復合邏輯運算就是將三種基本邏輯運算“與”、“或”、“非”按某種形式進行簡單地組合所構成的一種新的邏輯運算。 用于實現這些復合邏輯運算的邏輯門電路，就叫做復合邏輯門，簡稱復合門。1.“與非”、“或非”、“與或非”運算 “與非”運算就是“與”運算和“非”運算的組合。用邏輯函數表示就是： ABF“與非”門邏輯符號7/17/202245北京理工大學 信息科學學院“或非”運算就是“或”

24、運算和“非”運算的組合。用邏輯函數表示就是： “或非”門邏輯符號ABCDFABF“與或非”運算就是“與”運算、“或”運算和“非”運算的組合。用邏輯函數表示就是： “與或非”門邏輯符號7/17/202246北京理工大學 信息科學學院2. “異或”（“異”）、“同或”（“同”）運算“異或”邏輯運算（有時簡稱“異”運算）和“同或”邏輯運算（有時簡稱“同”運算）是兩個非常重要的復合邏輯運算。兩個變量 “異或”運算的定義如下：（1）“異或”運算“”是“異或”的運算符號。根據兩變量“異或”定義式，列出其真值表。“異或”運算含義：若兩變量A、B的取值相異，則F 的取值為“1”；若兩變量A、B的取值相同，則F

25、的取值為“0”。 7/17/202247北京理工大學 信息科學學院根據“異或”運算定義，邏輯常數“1”和“0”的“異或”基本運算規則如下： 3個變量的“異或”運算定義如下：n個變量的“異或”運算可依此類推。7/17/202248北京理工大學 信息科學學院“異或”運算具有如下的基本運算規律：“異或”運算符合交換律，即：“異或”運算符合結合律，即：“異或”運算具有分配律，即：利用真值表，再根據“異或”的定義，可證明“異或”的這些基本運算規律。 7/17/202249北京理工大學 信息科學學院“異或”運算的兩個重要特性特性1：多變量“異或”運算的結果取決于這些變量中取值為“1”的變量個數，而與取值為

26、“0”的變量個數無關。若取值為“1”的變量個數是奇數，則“異或”的結果為“1”；若取值為“1”的變量個數是偶數，則“異或”的結果為“0”。多個變量相“異或”的本質就在于確定取值為“1”的變量個數是奇數個還是偶數個。多個邏輯常量相“異或”，其結果取決于邏輯“1”的個數，而與邏輯“0”的個數無關。若邏輯“1”的個數為奇數，則“異或”的結果為“1”；若邏輯“1”的個數為偶數，則“異或”的結果為“0”。7/17/202250北京理工大學 信息科學學院由特性1可得到如下推論：若（1 i n）則或：n個變量相“異或”的補函數就等于這n個相“異或”的變量中任意一個變量取反。 7/17/202251北京理工大

27、學 信息科學學院特性2：“異或”運算具有因果互換的關系。即，等式兩邊的邏輯變量可以互相交換位置而仍然保持等式的成立。 例如：若成立，則或成立。“異或”運算的這種因果互換關系還可以推廣到多個邏輯量（包括邏輯變量和邏輯常量）相“異或”的情形。 成立。例如：若成立，則或或或利用“異或”運算的特性1，可說明多個邏輯量“異或”運算的因果互換關系。7/17/202252北京理工大學 信息科學學院“異或”邏輯門及其邏輯符號“異或”運算可以由“異或”邏輯門來實現。“異或”門的邏輯符號如下圖所示：ABFFABCD多個變量的“異或”，則可根據“異或”運算的結合律，利用多個“異或”門的級聯來實現，如下圖所示。 7/

28、17/202253北京理工大學 信息科學學院兩個變量 “同或”運算的定義如下：（2）“同或”運算“”是“同或”的運算符號。根據兩變量“同或”定義式，列出其真值表。“同或”運算含義：若兩變量A、B的取值相同，則F 的取值為“1”；若兩變量A、B的取值相異，則F的取值為“0”。 根據“同或”運算定義，邏輯常數“1”和“0”的“同或”基本運算規則如下： 00=1， 01=0， 10=0， 11=17/17/202254北京理工大學 信息科學學院3個變量的“同或”運算定義如下：F = ABCCn個變量的“同或”運算可依此類推。“同或”運算具有如下的基本運算規律：A0=；A1=A；AA=1；A=07/1

29、7/202255北京理工大學 信息科學學院“同或”運算符合交換律，即：AB=BA “同或”運算符合結合律，即：A(BC)=( AB)C“同或”運算具有分配律，即：A+(BC)=( A+B)( A+C) 利用真值表，再根據“同或”的定義，可證明“同或”的這些基本運算規律。 7/17/202256北京理工大學 信息科學學院7/17/202257北京理工大學 信息科學學院“同或”運算的兩個重要特性特性1：多變量“同或”運算的結果取決于這些變量中取值為“0”的變量個數，而與取值為“1”的變量個數無關。若取值為“0”的變量個數是偶數，則“同或”的結果為“1”；若取值為“0”的變量個數是奇數，則“同或”的

30、結果為“0”。 多個變量相“同或”的本質就在于確定取值為“0”的變量個數是偶數個還是奇數個。 多個邏輯常量相“同或”，其結果取決于邏輯“0”的個數，而與邏輯“1”的個數無關。若邏輯“0”的個數為偶數，則“同或”的結果為“1”；若邏輯“0”的個數為奇數，則“同或”的結果為“0”。 7/17/202258北京理工大學 信息科學學院由“同或”運算的特性1可得到如下推論：或：n個變量相“同或”的補函數就等于這n個相“同或”的變量中任意一個變量取反。若F = A1A2AiAn， （1 i n）則= A1A2An；= A1A2An；A1A2AiAn7/17/202259北京理工大學 信息科學學院特性2：“

31、同或”運算具有因果互換的關系。即，等式兩邊的邏輯變量可以互相交換位置而仍然保持等式的成立。 例如：若 AB=C 成立，則 AC=B“同或”運算的這種因果互換關系也可以推廣到多個邏輯量（包括邏輯變量和邏輯常量）相“同或”的情形。 例如：若 ABCD=1 成立，則 A1CD=B或 1BCD=A或 ABC1=D 成立。或 AB1D=C利用“同或”運算的特性1，可說明多個邏輯量“同或”運算的因果互換關系。或 BC=A 成立。7/17/202260北京理工大學 信息科學學院“異或”與“同或”之間的關系設有n個邏輯變量A1，A2，An，若F是將這n個邏輯變量相“異或”而構成的邏輯函數；G是將這n個邏輯變量

32、相“同或”而構成的邏輯函數，即： ； G= A1A2，An 則當n為偶數時： 或 。也就是說，此時邏輯函數F 和邏輯函數G 互為反函數（或互為補函數）；而當n為奇數時：F = G。也就是說，此時邏輯函數F 和邏輯函數G 相同。 兩變量的“同或”函數是兩變量的“異或”函數的反函數。AB = AB或7/17/202261北京理工大學 信息科學學院“同或”邏輯門及其邏輯符號“同或”運算可以由“同或”邏輯門來實現。“同或”門的邏輯符號如下圖所示：在兩個變量的“同或”運算中，只要有一個變量取反，則“同或”運算就變為“異或”運算，反之亦然。 AB =或= A “同或”運算亦稱之為“異或”非運算。ABFAB

33、FABF7/17/202262北京理工大學 信息科學學院兩個變量構成的“同或”和“異或”函數是一對特殊的邏輯函數。它們不僅互為反函數，而且還互為對偶函數。即： 不但 AB = AB或而且 = AB 或 (AB)= 運用對偶規則，可以從表2.13的左欄所列公式推導出右欄所列公式，反之亦然。 在求對偶式時，除了前面提到的三個變換以外，還要加上第四個變換，即：把所有的“ ”運算符換成“”運算符，同時把所有的“”運算符換成“ ”運算符。 在運用反演規則時，除原先的三個變換以外，也需加上第四個變換，即：把所有的“ ”、“”互換。 7/17/202263北京理工大學 信息科學學院3.邏輯運算符號的完備性

34、“與”、“或”、“非”是三種基本的邏輯運算，由它們可以組成任何邏輯函數。所以說“”、“+”、“”是一組邏輯功能完備的邏輯運算符。 “與非”運算、“或非”運算以及“與或非”運算各自都是功能完備的復合邏輯運算符。 “與”、“或”、“非”這三種基本邏輯運算均可用“或非” 運算來單獨地完成，并可用相應的“或非”門來實現。 7/17/202264北京理工大學 信息科學學院“或”“非”ABA+B“與”A“0”BAB“0”A ABAB B或者A“0”7/17/202265北京理工大學 信息科學學院作業3：2-12的（1）、（3）、（4）、（5）、（8）、（9），2-14，2-17，2-19，2-21同理：“

35、與”、“或”、“非”這三種基本邏輯運算均可用“與非” 運算來單獨地完成，并可用相應的“與非”門來實現。 同理：“與”、“或”、“非”這三種基本邏輯運算均可用“與或非” 運算來單獨地完成，并可用相應的“與或非”門來實現。 7/17/202266北京理工大學 信息科學學院2.4 邏輯函數的兩種標準形式一個邏輯函數可以歸納出五種主要的形式。它們是：“與或”表達式（先“與”后“或”的表達式）；“或與”表達式（先“或”后“與”的表達式）；“與非-與非”表達式；“或非-或非”表達式；“與或非”表達式。例如函數：7/17/202267北京理工大學 信息科學學院7/17/202268北京理工大學 信息科學學院

36、“與或”式和“或與”式是較為常用的表達式形式。同一種類型的邏輯表達式, 其形式也不是唯一的。例如F 的“與或”表達式： 在一個邏輯函數的眾多的表達式中，有兩種標準的表達式形式。它們實際上是特殊的“與或”式和“或與”式。 7/17/202269北京理工大學 信息科學學院2.4.1 最小項和最大項1.最小項（標準積或規范積）由A、B、C 三個邏輯變量所構成的乘積項（“與”項）中，有一類特殊的乘積項，它們是： 這8個乘積項（“與”項）有如下三個特點：每一項都是由三個邏輯變量相“與”而構成，即每項都有三個“因子”。 每個邏輯變量都是每一項的一個“因子”。7/17/202270北京理工大學 信息科學學院

37、在每一個乘積項中，每個邏輯變量或以原變量（A、B、C）的形式、或以反變量（ ）的形式出現一次。 這8個乘積項（“與”項）就稱為三邏輯變量A、B、C的“最小項”。 n個變量的最小項是n個變量相“與”（乘積），其中每一個變量都以原變量的形式或反變量的形式出現、且僅出現一次。 對于n個變量來說，最小項的個數總共有2n個。當n=3（三個變量）時，最小項有23=8個。 7/17/202271北京理工大學 信息科學學院7/17/202272北京理工大學 信息科學學院最小項的性質性質1：對于任意的一個最小項，只有一組變量的取值使得它的值為“1”，而在變量取其它各組值時，這個最小項的值都是“0”。最小項不同，

38、使得它的值為“1”的那一組變量的取值也不同。使得某一個最小項的值為“1”的那組變量取值，就是該最小項中的原變量取“1”、反變量取“0”而組成的二進制數。 n代表最小項中變量的個數，常省略之 通常用符號 來表示最小項。 i代表最小項的編號，它是使最小項的值為“1”的變量取值的等效十進制數。 7/17/202273北京理工大學 信息科學學院性質2：任意兩個不同的最小項的乘積（相“與”）恒為“0”。 性質3：全體最小項之和（相“或”）恒為“1”。 例如：7/17/202274北京理工大學 信息科學學院n變量最小項也具有同樣的三個性質: 每一個最小項僅和一組變量取值相對應，只有在該組取值下這個最小項的

39、值才為“1”，而在其它的取值下它都為“0”。 n個變量的任意兩個不同最小項的乘積（相“與”）恒為“0”，即： n個變量的全體最小項之和（相“或”）恒為“1”，即： 7/17/202275北京理工大學 信息科學學院2.最大項（標準和或規范和）由A、B、C 三個邏輯變量所構成的和項（“或”項）中，有一類特殊的和項，它們是： 每一項都是由三個邏輯變量相“或”而構成，即每項都有三個“加數”。 每個邏輯變量都是每一項的一個“加數”。 這8個和項（“或”項）有如下三個特點：7/17/202276北京理工大學 信息科學學院在每一個和項中，每個邏輯變量或以原變量（A、B、C）的形式，或以反變量（ ）的形式出現

40、一次。 這8個和項（“或”項）就稱為三邏輯變量A、B、C的“最大項”。 n個變量的最大項是n個變量相“或”（和），其中每一個變量都以原變量的形式或反變量的形式出現、且僅出現一次。 對于n個變量來說，最大項的個數總共有2n個。當n=3（三個變量）時，最大項有23=8個。 7/17/202277北京理工大學 信息科學學院7/17/202278北京理工大學 信息科學學院最大項的性質性質1：對于任意的一個最大項，只有一組變量的取值使得它的值為“0”，而在變量取其它各組值時，這個最大項的值都是“1”。最大項不同，使得它的值為“0”的那一組變量的取值也不同。使得某一個最大項的值為“0”的那組變量取值，就是

41、該最大項中的原變量取“0”、反變量取“1”而組成的二進制數。n代表最大項中變量的個數，常省略之。 j代表最大項的編號，它是使最大項的值為“0”的變量取值的等效十進制數。 通常用符號 來表示最大項。 7/17/202279北京理工大學 信息科學學院性質2：任意兩個不同的最大項的和（相“或”）恒為“1”。 性質3：全體最大項之積（相“與”）恒為“0”。 例如：7/17/202280北京理工大學 信息科學學院n變量最大項也具有同樣的三個性質: 每一個最大項僅和一組變量取值相對應，只有在該組取值下這個最大項的值才為“0”，而在其它的取值下它都為“1”。 n個變量的任意兩個不同最大項的和（相“或”）恒為

42、“1”，即： n個變量的全體最大項之積（相“與”）恒為“0”，即： 7/17/202281北京理工大學 信息科學學院3.最小項與最大項的關系 變量相同且編號相同的最小項和最大項之間，存在著互補的關系。即： 7/17/202282北京理工大學 信息科學學院7/17/202283北京理工大學 信息科學學院2.4.2 標準表達式和真值表1.兩種標準表達式最小項之和式是由若干個最小項相“加”（相“或”）而構成，它也叫標準“與或”式。 例如：(1)最小項之和式7/17/202284北京理工大學 信息科學學院【例2.1】 把 展開為最小項之和式。 解：任何一個邏輯函數表達式都可以被展開成唯一的最小項之和式

43、；換句話說，用最小項之和這種形式可以表達任何一個邏輯函數。 7/17/202285北京理工大學 信息科學學院解：【例2.2】將 展開成最 小項之和式。 7/17/202286北京理工大學 信息科學學院最大項之積式是由若干個最大項相“乘”（相“與”）而構成，它也叫標準“或與”式。例如：(2)最大項之積式7/17/202287北京理工大學 信息科學學院解：【例2.3】把 展開為最大項之積式。 7/17/202288北京理工大學 信息科學學院解：【例2.4】將 展開成最大項之積式。 7/17/202289北京理工大學 信息科學學院任何一個邏輯函數表達式都可以被展開成唯一的最大項之積式；換句話說，用最

44、大項之積這種形式可以表達任何一個邏輯函數。 最小項之和式和最大項之積式是邏輯函數的兩種標準表達式。 7/17/202290北京理工大學 信息科學學院2.真值表與標準表達式最小項之和式或者最大項之積式與真值表之間具有一一對應的關系，知道了一個就可以求出另一個。 例如：只有當ABC的取值為“011”、“101”和“110”時，函數F 的值才為“1”；而當ABC的取值為其它值時，F 的值為“0”。列出函數F 的真值表7/17/202291北京理工大學 信息科學學院例如：只有當ABC的取值為“000”、“011”、“101”和“110”時，函數G的值才為“0”；而當ABC的取值為其它值時，G的值為“1

45、”。列出函數G 的真值表。7/17/202292北京理工大學 信息科學學院函數F 的最小項之和式，實際上就是由真值表中F =1的各行相應的變量取值所對應的最小項相“或”而構成。 函數G 的最大項之積式，實際上就是由真值表中G =0的各行相應的變量取值所對應的最大項相“與”而構成。 在寫各最小項時，應分別將各F =1的那一行所對應的變量取值中“1”代以原變量，而“0”代以反變量，再把這些變量（原變量和反變量）相“乘”（相“與”），從而構成一個最小項；同樣，在寫各最大項時，應分別將各F =0的那一行所對應的變量取值中“0”代以原變量，而“1”代以反變量，再把這些變量（原變量和反變量）相“加”（相“

46、或”），從而構成一個最大項。 7/17/202293北京理工大學 信息科學學院解：【例2.5】已知函數F 的真值表如表2.19所示。試寫出F 的最小項之和式和最大項之積式。 函數F 的最小項之和式為： 函數F的最大項之積式為：7/17/202294北京理工大學 信息科學學院3.兩種標準表達式之間的關系某個函數的最大項之積式中的最大項的編號正好是該函數的最小項之和式中的最小項編號中未包含的號碼，反之亦然。 設：任意給定一個n變量的邏輯函數F，它的最小項之和式為： 因為全體最小項之和為“1”，即：7/17/202295北京理工大學 信息科學學院所以，邏輯函數F 的最小項之和 中所不包含的那些最小項

47、的 “和”就構成了邏輯函數F 的反函數 的最小項之和式，即：所以：7/17/202296北京理工大學 信息科學學院知道了邏輯函數F 的兩種標準表達式之間“項號互補”的關系規律以后，就可以很容易地由一種標準表達式推出另一種標準表達式。 【例2.6】已知函數 ,試寫出F 的最大項之積式。解：根據兩種標準表達式所含項的編號在0 24-1的范圍內互補的規律知： 7/17/202297北京理工大學 信息科學學院作業4：2-25，2-26，思考2-27，2-307/17/202298北京理工大學 信息科學學院2.5 邏輯函數的代數化簡法2.5.1 化簡邏輯函數的意義及化簡方法一個邏輯函數可以歸納出五種主要

48、的形式。例如函數：7/17/202299北京理工大學 信息科學學院實現“與或”表達式AABC實現“或與”表達式ACBA實現“與非-與非”表達式AABC實現“或非-或非”表達式ACBA實現“與或非”表達式ABAC7/17/2022100北京理工大學 信息科學學院(a)AABC(b)ACBCAB(c)ACBCABCAABBC7/17/2022101北京理工大學 信息科學學院首先討論如何將一個“與或”表達式化為最簡“與或”表達式。這是因為：任何一個邏輯函數表達式都能展開成一個“與或”表達式；從一個最簡“與或”表達式，可以很容易地得到“與非-與非”、“與或非”等形式的表達式；只要掌握了“與或”表達式的

49、化簡方法，利用對偶式，就不難化簡“或與”表達式。 最簡“與或”表達式的標準：首先，表達式中乘積項（“與”項）的個數應該是最少的；其次，在滿足上述條件的前提下，要求每一個乘積項中所含的變量個數最少。 7/17/2022102北京理工大學 信息科學學院乘積項的個數最少，就意味著電路中所用到的“與”門個數最少、所用“或”門的輸入端子個數最少（“或”門的規模最小）； 每個乘積項中所含的變量個數最少，就意味著每個“與”門所含輸入端子個數最少（“與”門的規模最小）。 在以后的化簡中，均假定原變量（如A，B，C，）和反變量（如 ）都已經存在。 化簡邏輯函數的常用方法:代數化簡法。卡諾圖化簡法。 系統化簡法：

50、也叫Q-M法，或稱列表法。 7/17/2022103北京理工大學 信息科學學院2.5.2 代數化簡法1.“與或”表達式的化簡例如：(1)并項利用 “合并定理” 和“互補律” ，將兩項合并為一項，同時消去一個“因子”（變量）。 7/17/2022104北京理工大學 信息科學學院7/17/2022105北京理工大學 信息科學學院(2)消項利用 “吸收定理” 和“添加項定理” ，消去多余的項。 例如：7/17/2022106北京理工大學 信息科學學院7/17/2022107北京理工大學 信息科學學院(3)消元例如：利用 “吸收定理” ,消去多余的“因子”。 7/17/2022108北京理工大學 信息

51、科學學院(4)配項例如：(1)利用 “互補律” ，把它代入邏輯函數式中作配項用，然后再消去更多的項。 7/17/2022109北京理工大學 信息科學學院例如：(2)利用 “重疊律” ，在邏輯函數式中重復寫一項，有時可以得到更簡單的結果。 7/17/2022110北京理工大學 信息科學學院例如：(3)利用“添加項定理” 和“重疊律” ，在邏輯函數式中先添項、再消項，有時也能得到更簡單的結果。 7/17/2022111北京理工大學 信息科學學院注意到此處F1的化簡形式與上述(1)中F1的化簡形式不一樣，但它們都是的最簡“與或”式，這可以用真值表加以證明。這也說明“與或”表達式的最簡形式，在某些情況

52、下是不唯一的。7/17/2022112北京理工大學 信息科學學院【例2.7】求 的最簡“與或”式。 解：7/17/2022113北京理工大學 信息科學學院2.“或與”表達式的化簡最簡“或與”式的標準是“或項”（“和”項）最少、每個“或項”所含的變量個數最少。 利用對偶式化簡“或與”式會更方便。現示意如下： F（“或與”式）（“與或”式）F（最簡“或與”式）求對偶式（最簡“與或”式）求對偶式化簡7/17/2022114北京理工大學 信息科學學院【例2.9】求邏輯函數的最簡“或與”式。解：（1）求 ： （2）化簡 ： 7/17/2022115北京理工大學 信息科學學院3.其他類型邏輯表達式的化簡“

53、與非與非”表達式的最簡標準是：表達式的“非”號最少，（不計算單個變量上的“非”號，即假定原變量和反變量都已存在）；其次，每個“非”號下的變量個數最少（單個變量除外）。 用“求反加非”和反演律將已化簡的最簡“與或”式變換為最簡“與非與非”表達式。 （3）求 ，即F： （1）最簡“與非與非”表達式 7/17/2022116北京理工大學 信息科學學院解：（1）求函數F之最簡“與或”式： 【例2.10】用最少的“與非”門實現 。 （2）把F之最簡“與或”式“求反加非”變換為最簡“與非與非”式： BDAD7/17/2022117北京理工大學 信息科學學院（2）最簡“或非或非”表達式 “或非或非”表達式的

54、最簡標準是：表達式的“非”號最少，（不計算單個變量上的“非”號，即假定原變量和反變量都已存在）；每個“非”號下的變量個數最少（單個變量除外）。 用“求反加非”和反演律將已化簡的最簡“或與”式變換為最簡“或非或非”表達式。 解：【例2.11】用最少的“或非”門實現 。 （1）求函數F之反函數F ： 7/17/2022118北京理工大學 信息科學學院（2）求函數F之最簡“與或”式：（3）求函數F之最簡“或與”式：（4）求函數F之最簡“或非或非”式：DBAD7/17/2022119北京理工大學 信息科學學院（3）最簡“與或非”表達式 “與或非”表達式的最簡標準和“與或”表達式的最簡標準完全一樣。即，

55、“與”項的個數最少；每個“與”項所含變量的個數最少。 對F 之最簡“與或”式“求反”，即可得到F 之最簡“與或非”式。 7/17/2022120北京理工大學 信息科學學院邏輯函數表達式的常用變換方法：F 之最簡“與或”式 F 之最簡“與非與非”式 求反加非F 之最簡“與或”式 F 之最簡“或與”式 反演F 之最簡“或與”式 F 之最簡“或非或非”式 求反加非F 之最簡“或與”式 F 之最簡“與或”式 反演F 之最簡“與或”式 F 之最簡“與或非”式 加一非7/17/2022121北京理工大學 信息科學學院作業5：2-31，2-33的（2）、（4），2-34的（1）、（3），2-35的（2），（

56、3）7/17/2022122北京理工大學 信息科學學院2.6 邏輯函數的卡諾圖化簡法2.6.1 卡諾圖（K圖）“邏輯相鄰” 項：例如：AB+AB=A， ABCD+ABCD=ABC。 任意兩個變量個數相同的最小項，如果組成它們的各個變量（原變量或反變量）中,只有一個變量互補（互反）而其余變量均相同（同為原變量或反變量）時，就稱這兩個最小項是邏輯相鄰的最小項，簡稱“邏輯相鄰項”或“相鄰項”。 ABC+ABC=BC， 7/17/2022123北京理工大學 信息科學學院1.卡諾圖的構成與特點把邏輯相鄰的最小項所對應的小方塊按幾何位置相鄰排列在一起，就得到了一個n變量最小項的方塊圖表示。這種最小項的方塊

57、圖表示方法是由美國人卡諾（Karnaugh）首先提出的，所以稱之為卡諾圖（Karnaugh Map），簡稱K圖。 7/17/2022124北京理工大學 信息科學學院三變量卡諾圖的構成7/17/2022125北京理工大學 信息科學學院二變量卡諾圖 ；四變量卡諾圖；五變量卡諾圖 7/17/2022126北京理工大學 信息科學學院K圖具有如下特點： n變量的K 圖有2n個小方格，每個小方格代表一個最小項。 變量按行、列分成兩組，每組變量的取值（編碼）不是按自然二進制數碼順序排列而是按格雷碼（循環碼）的順序排列。K 圖上位于水平方向中心軸或垂直方向中心軸兩側對稱的小格所代表的最小項在邏輯上是相鄰的。所

58、以位于K 圖上任何一行或一列兩端上的小方格所代表的最小項是邏輯相鄰的，即它們相互之間僅有一個變量互補。對于五變量的情形，要把“A=1”的卡諾圖看成是重疊在“A=0”的卡諾圖上。7/17/2022127北京理工大學 信息科學學院三變量卡諾圖的幾種畫法（形式）7/17/2022128北京理工大學 信息科學學院變量次序對卡諾圖小格標號的影響7/17/2022129北京理工大學 信息科學學院2.邏輯函數的卡諾圖表示將所有最小項所對應的小方格里都填寫“1”，而其余的小方格里都填寫“0”。任何一個邏輯函數都等于其卡諾圖上填“1”的那些小方格所對應的最小項之和。 （1）邏輯函數為最小項之和式7/17/202

59、2130北京理工大學 信息科學學院由函數的最大項之積式填寫K圖時，應將卡諾圖上編號與表達式中最大項編號相同的小方格里都填寫“0”，而其余的小方格里都填寫“1”。任何一個邏輯函數都等于編號與其卡諾圖上填“0”的那些小方格的編號相同的最大項之積。 （2）邏輯函數為最大項之積式7/17/2022131北京理工大學 信息科學學院最小項與最大項的名稱來源相對于填“1”來講，m7只占了編號為7的一個小格；而M7卻占據了除7號小格以外的所有小方格。這就是最小項和最大項名稱的由來。 卡諾圖也證明了最小項和最大項的互補關系。 7/17/2022132北京理工大學 信息科學學院若卡諾圖上的某個小方格所代表的最小項

60、，在真值表里所對應的函數F 取值為“1”，則該小方格里填“1”;否則就填“0”。（3）邏輯函數為真值表的形式7/17/2022133北京理工大學 信息科學學院將“與或”式中所有“與項”在卡諾圖中所覆蓋的區域內的所有小方格都填“1”（已經填過“1”的小格除外），其余都填“0”。（4）邏輯函數為一般“與或”式7/17/2022134北京理工大學 信息科學學院將“或與”式中所有“或項”在卡諾圖中所覆蓋的區域內的所有小方格都填“0”（已經填過“0”的小格除外），其余都填“1”。 （5）邏輯函數為一般“或與”式7/17/2022135北京理工大學 信息科學學院先將這些表達式變換為“與或”式或者“或與”式