上海第二工業大學楊潔 數字電路基礎 第5章邏輯代數基礎 學習要點 二進制 二進制與十進制的相互轉換邏輯代數的基本概念邏輯代數的公式與定理 邏輯函數化簡 第5章邏輯代數基礎 5 1數制與編碼 5 2邏輯函數 5 3布爾代數 5 4具有約束的邏輯函數 5 1數制與編碼 5 1 1進位計數制 5 1 2進位計數制轉換 5 1 3二進制編碼 退出 1 進位制 表示數時 僅用一位數碼往往不夠用 必須用進位計數的方法組成多位數碼 多位數碼每一位的構成以及從低位到高位的進位規則稱為進位計數制 簡稱進位制 數制 2 基數 進位制的基數 就是在該進位制中可能用到的數碼個數 3 位權 位的權數 在某一進位制的數中 每一位的大小都對應著該位上的數碼乘上一個固定的數 這個固定的數就是這一位的權數 權數是一個冪 數碼為 0 9 基數是10 Decimal 十進制運算規律 逢十進一 即 9 1 10 十進制數的權展開式 1 十進制 103 102 101 100稱為十進制的權 各數位的權是10的冪 同樣的數碼在不同的數位上代表的數值不同 任意一個十進制數都可以表示為各個數位上的數碼與其對應的權的乘積之和 稱權展開式 即 5555 D 5 103 5 102 5 101 5 100 又如 209 04 10 2 102 0 101 9 100 0 10 1 4 10 2 2 二進制 數碼為 0 1 基數是2 Binary 二進制運算規律 逢二進一 即 1 1 10 二進制數的權展開式 如 101 01 B 1 22 0 21 1 20 0 2 1 1 2 2 5 25 10 加法規則 0 0 0 0 1 1 1 0 1 1 1 10乘法規則 0 0 0 0 1 0 1 0 0 1 1 1 運算規則 各數位的權是 的冪 二進制數只有0和1兩個數碼 它的每一位都可以用電子元件來實現 且運算規則簡單 相應的運算電路也容易實現 數碼為 0 7 基數是8 O 八進制運算規律 逢八進一 即 7 1 10 八進制數的權展開式 如 207 04 8 2 82 0 81 7 80 0 8 1 4 8 2 135 0625 10 3 八進制 4 十六進制 數碼為 0 9 A F 基數是16 Hexadecimal 十六進制運算規律 逢十六進一 即 F 1 10 十六進制數的權展開式 如 D8 A H 13 161 8 160 10 16 1 216 625 10 各數位的權是8的冪 各數位的權是16的冪 結論 一般地 N進制需要用到N個數碼 基數是N 運算規律為逢N進一 如果一個N進制數M包含 位整數和 位小數 即 an 1an 2 a1a0 a 1a 2 a m N則該數的權展開式為 M N an 1 Nn 1 an 2 Nn 2 a1 N1 a0 N0 a 1 N 1 a 2 N 2 a m N m 由權展開式很容易將一個N進制數轉換為十進制數 數制轉換 1 二進制數轉換為八進制數 將二進制數由小數點開始 整數部分向左 小數部分向右 每3位分成一組 不夠3位補零 則每組二進制數便是一位八進制數 將N進制數按權展開 即可以轉換為十進制數 1 二進制數與八進制數的相互轉換 1101010 01 00 0 152 2 8 2 八進制數轉換為二進制數 將每位八進制數用3位二進制數表示 011111100 010110 374 26 8 2 二進制數與十六進制數的相互轉換 111010100 011 000 0 1D4 6 16 101011110100 01110110 AF4 76 16 二進制數與十六進制數的相互轉換 按照每4位二進制數對應于一位十六進制數進行轉換 3 十進制數轉換為二進制數 采用的方法 基數連除 連乘法原理 將整數部分和小數部分分別進行轉換 整數部分采用基數連除法 小數部分采用基數連乘法 轉換后再合并 整數部分采用基數連除法 先得到的余數為低位 后得到的余數為高位 小數部分采用基數連乘法 先得到的整數為高位 后得到的整數為低位 所以 0 375 10 0 011 2 采用基數連除 連乘法 可將十進制數轉換為任意的N進制數 25 D 11001 B 用一定位數的二進制數來表示十進制數碼 字母 符號等信息稱為編碼 用以表示十進制數碼 字母 符號等信息的一定位數的二進制數稱為代碼 編碼 數字系統只能識別0和1 怎樣才能表示更多的數碼 符號 字母呢 用編碼可以解決此問題 二 十進制代碼 用4位二進制數b3b2b1b0來表示十進制數中的0 9十個數碼 簡稱BCD碼 8421碼的權值依次為8 4 2 1 余3碼由8421碼加0011得到 格雷碼是一種循環碼 其特點是任何相鄰的兩個碼字 僅有一位代碼不同 其它位相同 用四位自然二進制碼中的前十個碼字來表示十進制數碼 因各位的權值依次為8 4 2 1 故稱8421BCD碼 本節小結 日常生活中使用十進制 但在計算機中基本上使用二進制 有時也使用八進制或十六進制 利用權展開式可將任意進制數轉換為十進制數 將十進制數轉換為其它進制數時 整數部分采用基數除法 小數部分采用基數乘法 利用1位八進制數由3位二進制數構成 1位十六進制數由4位二進制數構成 可以實現二進制數與八進制數以及二進制數與十六進制數之間的相互轉換 二進制代碼不僅可以表示數值 而且可以表示符號及文字 使信息交換靈活方便 BCD碼是用4位二進制代碼代表1位十進制數的編碼 有多種BCD碼形式 最常用的是8421BCD碼 5 2邏輯函數 5 2 1邏輯函數的基本概念 5 2 2邏輯代數的公式 定理和規則 5 2 3邏輯函數的表達式 事物往往存在兩種對立的狀態 在邏輯代數中可以抽象地表示為0和1 稱為邏輯0狀態和邏輯1狀態 邏輯函數是按一定的邏輯關系進行運算的函數 是分析和設計數字電路的數學工具 在邏輯代數 只有 和 兩種邏輯值 有與 或 非三種基本邏輯運算 還有與或 與非 與或非 異或幾種導出邏輯運算 邏輯代數中的變量稱為邏輯變量 用大寫字母表示 邏輯變量的取值只有兩種 即邏輯0和邏輯1 0和1稱為邏輯常量 并不表示數量的大小 而是表示兩種對立的邏輯狀態 邏輯是指事物的因果關系 或者說條件和結果的關系 這些因果關系可以用邏輯運算來表示 也就是用邏輯代數來描述 1 與邏輯 與運算 與邏輯的定義 僅當決定事件 Y 發生的所有條件 A B C 均滿足時 事件 Y 才能發生 表達式為 開關A B串聯控制燈泡Y 兩個開關必須同時接通 燈才亮 邏輯表達式為 A B都斷開 燈不亮 A斷開 B接通 燈不亮 A接通 B斷開 燈不亮 A B都接通 燈亮 這種把所有可能的條件組合及其對應結果一一列出來的表格叫做真值表 將開關接通記作1 斷開記作0 燈亮記作1 燈滅記作0 可以作出如下表格來描述與邏輯關系 功能表 實現與邏輯的電路稱為與門 與門的邏輯符號 真值表 邏輯符號 2 或邏輯 或運算 或邏輯的定義 當決定事件 Y 發生的各種條件 A B C 中 只要有一個或多個條件具備 事件 Y 就發生 表達式為 開關A B并聯控制燈泡Y 兩個開關只要有一個接通 燈就會亮 邏輯表達式為 A B都斷開 燈不亮 A斷開 B接通 燈亮 A接通 B斷開 燈亮 A B都接通 燈亮 實現或邏輯的電路稱為或門 或門的邏輯符號 Y A B 真值表 功能表 邏輯符號 3 非邏輯 非運算 非邏輯指的是邏輯的否定 當決定事件 Y 發生的條件 A 滿足時 事件不發生 條件不滿足 事件反而發生 表達式為 開關A控制燈泡Y 實現非邏輯的電路稱為非門 非門的邏輯符號 A斷開 燈亮 A接通 燈滅 真值表 功能表 邏輯符號 4 常用的邏輯運算 1 與非運算 邏輯表達式為 2 或非運算 邏輯表達式為 3 異或運算 邏輯表達式為 4 與或非運算 邏輯表達式為 基本邏輯關系小結 5 邏輯函數及其相等概念 1 邏輯表達式 由邏輯變量和與 或 非3種運算符連接起來所構成的式子 在邏輯表達式中 等式右邊的字母A B C D等稱為輸入邏輯變量 等式左邊的字母Y稱為輸出邏輯變量 字母上面沒有非運算符的叫做原變量 有非運算符的叫做反變量 2 邏輯函數 如果對應于輸入邏輯變量A B C 的每一組確定值 輸出邏輯變量Y就有唯一確定的值 則稱Y是A B C 的邏輯函數 記為 注意 與普通代數不同的是 在邏輯代數中 不管是變量還是函數 其取值都只能是0或1 并且這里的0和1只表示兩種不同的狀態 沒有數量的含義 3 邏輯函數相等的概念 設有兩個邏輯函數 它們的變量都是A B C 如果對應于變量A B C 的任何一組變量取值 Y1和Y2的值都相同 則稱Y1和Y2是相等的 記為Y1 Y2 若兩個邏輯函數相等 則它們的真值表一定相同 反之 若兩個函數的真值表完全相同 則這兩個函數一定相等 因此 要證明兩個邏輯函數是否相等 只要分別列出它們的真值表 看看它們的真值表是否相同即可 證明等式 邏輯函數的表示方法 1 真值表 真值表 是由變量的所有可能取值組合及其對應的函數值所構成的表格 真值表列寫方法 每一個變量均有0 1兩種取值 n個變量共有2i種不同的取值 將這2i種不同的取值按順序 一般按二進制遞增規律 排列起來 同時在相應位置上填入函數的值 便可得到邏輯函數的真值表 例如 當A B 1 或則B C 1時 函數Y 1 否則Y 0 2 邏輯表達式 邏輯表達式 是由邏輯變量和與 或 非3種運算符連接起來所構成的式子 函數的標準與或表達式的列寫方法 將函數的真值表中那些使函數值為1的最小項相加 便得到函數的標準與或表達式 3 卡諾圖 卡諾圖 是由表示變量的所有可能取值組合的小方格所構成的圖形 邏輯函數卡諾圖的填寫方法 在那些使函數值為1的變量取值組合所對應的小方格內填入1 其余的方格內填入0 便得到該函數的卡諾圖 4 邏輯圖 邏輯圖 是由表示邏輯運算的邏輯符號所構成的圖形 波形圖 波形圖 是由輸入變量的所有可能取值組合的高 低電平及其對應的輸出函數值的高 低電平所構成的圖形 邏輯函數表示方法之間的轉換 1 由真值表到邏輯圖的轉換 真值表 邏輯表達式或卡諾圖 1 1 最簡與或表達式 化簡 2 或 2 畫邏輯圖 3 最簡與或表達式 B A A C AC Y B A A C Y 若用與非門實現 將最簡與或表達式變換乘最簡與非 與非表達式 3 2 由邏輯圖到真值表的轉換 邏輯圖 邏輯表達式 1 1 最簡與或表達式 化簡 2 2 從輸入到輸出逐級寫出 最簡與或表達式 3 真值表 3 本節小結 邏輯函數可用真值表 邏輯表達式 卡諾圖 邏輯圖和波形圖5種方式表示 它們各具特點 但本質相通 可以互相轉換 對于一個具體的邏輯函數 究竟采用哪種表示方式應視實際需要而定 在使用時應充分利用每一種表示方式的優點 由于由真值表到邏輯圖和由邏輯圖到真值表的轉換 直接涉及到數字電路的分析和設計問題 因此顯得更為重要 正負邏輯的概念 1 基本概念正邏輯 用高電平表示邏輯1 低電平表示邏輯0 負邏輯 用高電平表示邏輯0 低電平表示邏輯1 2 正邏輯與負邏輯的關系 按正邏輯規定 可得到表3 5所示真值表 由真值表可知 該電路是一個正邏輯的 與 門 按負邏輯規定 可得到表3 6所示真值表 由真值表可知 該電路是一個負邏輯的 或 門 即正邏輯與門等價于負邏輯或門 前面討論各種邏輯門電路時 都是按照正邏輯規定來定義其邏輯功能的 在本課程中 若無特殊說明 約定按正邏輯討論問題 所有門電路的符號均按正邏輯表示 布爾代數邏輯代數最初是由英國數學家布爾 G Boole 首先提出來的 被稱為布爾代數 邏輯代數的變量稱為邏輯變量 邏輯變量與一般代數變量不同 邏輯變量的取值只有0和1 就是說邏輯電路中只有兩種邏輯狀態 這里的1和0可以由數字系統中的電平的高低 開關的斷通和信號的有無來表示 1 布爾代數的公式和定理 1 常量之間的關系 2 基本公式 分別令A 0及A 1代入這些公式 即可證明它們的正確性 3 基本定理 利用真值表很容易證明這些公式的正確性 如證明A B B A A B A C AA BA 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 證明 4 常用公式 分配率A BC A B A C 0 1率A 1 1 吸收規則 1 原變量的吸收 A AB A 證明 A AB A 1 B A 1 A 利用運算規則可以對邏輯式進行化簡 例如 吸收是指吸收多余 冗余 項 多余 冗余 因子被取消 去掉 被消化了 長中含短 留下短 2 反變量的吸收 證明 例如 長中含反 去掉反 3 混合變量的吸收 證明 例如 正負相對 余全完 分配率A B C AB AC 0 1率A 1 1 例如 已知等式 用函數Y AC代替等式中的A 根據代入規則 等式仍然成立 即有 2 布爾代數運算的基本規則 1 代入規則 任何一個含有變量A的等式 如果將所有出現A的位置都用同一個邏輯函數代替 則等式仍然成立 這個規則稱為代入規則 2 反演規則 對于任何一個邏輯表達式Y 如果將表達式中的所有 換成 換成 0 換成 1 1 換成 0 原變量換成反變量 反變量換成原變量 那么所得到的表達式就是函數Y的反函數Y 或稱補函數 這個規則稱為反演規則 例如 反演定理內容 將函數式F中所有的 變量與常數均取反 互補運算 2 不是一個變量上的反號不動 注意 用處 實現互補運算 求反運算 新表達式 F 顯然 變換時 原函數運算的先后順序不變 例1 與或式 注意括號 注意括號 例2 與或式 反號不動 反號不動 3 對偶規則 對于任何一個邏輯表達式Y 如果將表達式中的所有 換成 換成 0 換成 1 1 換成 0 而變量保持不變 則可得到的一個新的函數表達式Y Y 稱為函Y的對偶函數 這個規則稱為對偶規則 例如 對偶規則的意義在于 如果兩個函數相等 則它們的對偶函數也相等 利用對偶規則 可以使要證明及要記憶的公式數目減少一半 例如 注意 在運用反演規則和對偶規則時 必須按照邏輯運算的優先順序進行 先算括號 接著與運算 然后或運算 最后非運算 否則容易出錯 邏輯函數的表達式 一個邏輯函數的表達式可以有與或表達式 或與表達式 與非 與非表達式 或非 或非表達式 與或非表達式5種表示形式 一種形式的函數表達式相應于一種邏輯電路 盡管一個邏輯函數表達式的各種表示形式不同 但邏輯功能是相同的 1 邏輯函數的最小項及其性質 1 最小項 如果一個函數的某個乘積項包含了函數的全部變量 其中每個變量都以原變量或反變量的形式出現 且僅出現一次 則這個乘積項稱為該函數的一個標準積項 通常稱為最小項 3個變量A B C可組成8個最小項 2 最小項的表示方法 通常用符號mi來表示最小項 下標i的確定 把最小項中的原變量記為1 反變量記為0 當變量順序確定后 可以按順序排列成一個二進制數 則與這個二進制數相對應的十進制數 就是這個最小項的下標i 3個變量A B C的8個最小項可以分別表示為 3 最小項的性質 任意一個最小項 只有一組變量取值使其值為1 全部最小項的和必為1 任意兩個不同的最小項的乘積必為0 2 邏輯函數的最小項表達式 任何一個邏輯函數都可以表示成唯一的一組最小項之和 稱為標準與或表達式 也稱為最小項表達式 如果列出了函數的真值表 則只要將函數值為1的那些最小項相加 便是函數的最小項表達式 將真值表中函數值為0的那些最小項相加 便可得到反函數的最小項表達式 邏輯相鄰 若兩個最小項只有一個變量以原 反區別 其他變量均相同 則稱這兩個最小項邏輯相鄰 邏輯相鄰的項可以合并 消去一個因子 本節小結 邏輯代數是分析和設計數字電路的重要工具 利用邏輯代數 可以把實際邏輯問題抽象為邏輯函數來描述 并且可以用邏輯運算的方法 解決邏輯電路的分析和設計問題 與 或 非是3種基本邏輯關系 也是3種基本邏輯運算 與非 或非 與或非 異或則是由與 或 非3種基本邏輯運算復合而成的4種常用邏輯運算 邏輯代數的公式和定理是推演 變換及化簡邏輯函數的依據 邏輯函數的化簡 邏輯函數的最簡表達式 邏輯函數的公式化簡法 邏輯函數的圖形化簡法 含隨意項的邏輯函數的化簡 邏輯函數化簡的意義 邏輯表達式越簡單 實現它的電路越簡單 電路工作越穩定可靠 邏輯函數的最簡表達式 1 最簡與或表達式 乘積項最少 并且每個乘積項中的變量也最少的與或表達式 最簡與或表達式 2 最簡與非 與非表達式 非號最少 并且每個非號下面乘積項中的變量也最少的與非 與非表達式 在最簡與或表達式的基礎上兩次取反 用摩根定律去掉下面的非號 3 最簡或與表達式 括號最少 并且每個括號內相加的變量也最少的或與表達式 求出反函數的最簡與或表達式 利用反演規則寫出函數的最簡或與表達式 4 最簡或非 或非表達式 非號最少 并且每個非號下面相加的變量也最少的或非 或非表達式 求最簡或非 或非表達式 兩次取反 最簡與或非表達式 非號下面相加的乘積項最少 并且每個乘積項中相乘的變量也最少的與或非表達式 求最簡或非 或非表達式 用摩根定律去掉下面的非號 用摩根定律去掉大非號下面的非號 邏輯函數的公式化簡法 1 并項法 邏輯函數的公式化簡法就是運用邏輯代數的基本公式 定理和規則來化簡邏輯函數 若兩個乘積項中分別包含同一個因子的原變量和反變量 而其他因子都相同時 則這兩項可以合并成一項 并消去互為反變量的因子 運用摩根定律 運用分配律 運用分配律 2 吸收法 如果乘積項是另外一個乘積項的因子 則這另外一個乘積項是多余的 運用摩根定律 利用公式 消去多余的項 如果一個乘積項的反是另一個乘積項的因子 則這個因子是多余的 配項法 利用公式 為某項配上其所能合并的項 消去冗余項法 例 化簡函數 解 先求出Y的對偶函數Y 并對其進行化簡 求Y 的對偶函數 便得 的最簡或與表達式 例1 例2 反演 結論 異或門可以用4個與非門實現 例3 證明 AB A B 展開 例4 化簡為最簡邏輯代數式 例5 將Y化簡為最簡邏輯代數式 利用反演定理 邏輯函數的圖形化簡法 卡諾圖 1 卡諾圖的構成 邏輯函數的圖形化簡法是將邏輯函數用卡諾圖來表示 利用卡諾圖來化簡邏輯函數 將邏輯函數真值表中的最小項重新排列成矩陣形式 并且使矩陣的橫方向和縱方向的邏輯變量的取值按照格雷碼的順序排列 這樣構成的圖形就是卡諾圖 卡諾圖的特點是任意兩個相鄰的最小項在圖中也是相鄰的 相鄰項是指兩個最小項只有一個因子互為反變量 其余因子均相同 又稱為邏輯相鄰項 每個2變量的最小項有兩個最小項與它相鄰 每個3變量的最小項有3個最小項與它相鄰 每個4變量的最小項有4個最小項與它相鄰 最左列的最小項與最右列的相應最小項也是相鄰的 最上面一行的最小項與最下面一行的相應最小項也是相鄰的 兩個相鄰最小項可以合并消去一個變量 邏輯函數化簡的實質就是相鄰最小項的合并 2 邏輯函數在卡諾圖中的表示 1 邏輯函數是以真值表或者以最小項表達式給出 在卡諾圖上那些與給定邏輯函數的最小項相對應的方格內填入1 其余的方格內填入0 m1 m3 m4 m6 m7 m11 m14 m15 2 邏輯函數以一般的邏輯表達式給出 先將函數變換為與或表達式 不必變換為最小項之和的形式 然后在卡諾圖上與每一個乘積項所包含的那些最小項 該乘積項就是這些最小項的公因子 相對應的方格內填入1 其余的方格內填入0 變換為與或表達式 3 卡諾圖的性質 1 任何兩個 21個 標1的相鄰最小項 可以合并為一項 并消去一個變量 消去互為反變量的因子 保留公因子 2 任何4個 22個 標1的相鄰最小項 可以合并為一項 并消去2個變量 3 任何8個 23個 標1的相鄰最小項 可以合并為一項 并消去3個變量 小結 相鄰最小項的數目必須為個才能合并為一項 并消去個變量 包含的最小項數目越多 即由這些最小項所形成的圈越大 消去的變量也就越多 從而所得到的邏輯表達式就越簡單 這就是利用卡諾圖化簡邏輯函數的基本原理 4 圖形法化簡的基本步驟 邏輯表達式或真值表 卡諾圖 1 1 合并