《數(shù)據(jù)結(jié)構(gòu)C語言版》嚴(yán)蔚敏第二章邏輯代數(shù)基礎(chǔ).ppt

《《數(shù)據(jù)結(jié)構(gòu)C語言版》嚴(yán)蔚敏第二章邏輯代數(shù)基礎(chǔ).ppt》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)C語言版》嚴(yán)蔚敏第二章邏輯代數(shù)基礎(chǔ).ppt（59頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、（ 2-1） 第 二 章 邏 輯 代 數(shù) 基 礎(chǔ)數(shù) 字 電 路 （ 2-2） 1.2.1 邏 輯 代 數(shù) 與 基 本 邏 輯 關(guān) 系在 數(shù) 字 電 路 中 ， 我 們 要 研 究 的 是 電 路的 輸 入 輸 出 之 間 的 邏 輯 關(guān) 系 ， 所 以 數(shù) 字 電路 又 稱 邏 輯 電 路 ， 相 應(yīng) 的 研 究 工 具 是 邏 輯代 數(shù) （ 布 爾 代 數(shù) ） 。在 邏 輯 代 數(shù) 中 ， 邏 輯 函 數(shù) 的 變 量 只 能取 兩 個 值 （ 二 值 變 量 ） ， 即 0和 1， 中 間 值沒 有 意 義 ， 這 里 的 0和 1只 表 示 兩 個 對 立 的邏 輯 狀 態(tài) ， 如 電 位

2、 的 低 高 （ 0表 示 低 電 位 ，1表 示 高 電 位 ） 、 開 關(guān) 的 開 合 等 。 1.2 邏 輯 代 數(shù) 及 運 算 規(guī) 則 （ 2-3） （ 1） “ 與 ” 邏 輯A、 B、 C條 件 都 具 備 時 ， 事 件 F才 發(fā) 生 。基 本 邏 輯 關(guān) 系 ：E FA B C邏 輯 符 號 （ 2-4） F=ABC邏 輯 式 邏 輯 乘 法邏 輯 與A FB C000 0100 0010 0110 0001 0101 0011 0111 1 真 值 表 （ 2-5） （ 2） “ 或 ” 邏 輯A、 B、 C只 有 一 個 條 件 具 備 時 ， 事 件 F就發(fā) 生 。邏 輯

3、 符 號 AE FBC （ 2-6） F=A+B+C邏 輯 式 邏 輯 加 法邏 輯 或A FB C000 0100 1010 1110 1001 1101 1011 1111 1 真 值 表 （ 2-7） （ 3） “ 非 ” 邏 輯A條 件 具 備 時 ， 事 件 F不 發(fā) 生 ； A不 具 備時 ， 事 件 F發(fā) 生 。邏 輯 符 號 AE FR （ 2-8） 邏 輯 式 邏 輯 非邏 輯 反真 值 表AF A F0 11 0 （ 2-9） （ 4） 幾 種 常 用 的 邏 輯 關(guān) 系“與 ” 、 “ 或 ” 、 “ 非 ” 是 三 種 基 本 的 邏輯 關(guān) 系 ， 任 何 其 它 的

4、邏 輯 關(guān) 系 都 可 以 以 它們 為 基 礎(chǔ) 表 示 。 CBAF 與 非 ： 條 件A、 B都 具 備 ，則 F 不 發(fā) 生 。 （ 2-10） CBAF 或 非 ： 條 件A、 B任 一 具 備 ，則 F不 發(fā) 生 。 BA BABAF 異 或 ： 條 件A、 B有 一 個 具備 ， 另 一 個 不具 備 則 F 發(fā) 生 。 （ 2-11） （ 5） 幾 種 基 本 的 邏 輯 運 算 從 三 種 基 本 的 邏 輯 關(guān) 系 出 發(fā) ， 我 們 可以 得 到 以 下 邏 輯 運 算 結(jié) 果 ：0 0=0 1=1 0=0 1 1=10+0=00+1=1+0=1+1=1 10 01 （ 2

5、-12） 1.2.2 邏 輯 代 數(shù) 的 基 本 定 律一 、 基 本 運 算 規(guī) 則 (0-1律 )A+0=A A+1=1 A 0 =0 A=0 A 1=A1AA AAA 0AA AAA AA （ 2-13） 二 、 基 本 代 數(shù) 規(guī) 律交 換 律結(jié) 合 律分 配 律 A+B=B+AA B=B AA+(B+C)=(A+B)+C=(A+C)+BA (B C)=(A B) CA(B+C)=A B+A CA+B C=(A+B)(A+C) 普 通 代數(shù) 不 適用 ! （ 2-14） 三 、 吸 收 規(guī) 則 （ 吸 收 律 ）1.原 變 量 的 吸 收 ：A+AB=A證 明 ： A+AB=A(1+B

6、)=A1=A利 用 運 算 規(guī) 則 可 以 對 邏 輯 式 進(jìn) 行 化 簡 。例 如 ： CDABFEDABCDAB )(被 吸 收 （ 2-15） 2.反 變 量 的 吸 收 ： BABAA 證 明 ： BAABABAA BAAABA )(例 如 ： DCBCADCBCAA 被 吸 收 （ 2-16） 3.混 合 變 量 的 吸 收 ： CAABBCCAAB 證 明 ： BCAACAAB BCCAAB )( CAAB BCAABCCAAB 例 如 ： CAAB BCCAAB BCDBCCAAB BCDCAAB 1 吸 收吸 收 （ 2-17） 4. 代 入 定 理 ： 在 任 何 一 個 包

7、 含 A的 邏 輯 等 式 中 ， 若以 另 外 一 個 邏 輯 式 代 入 式 中 A的 位 置 ， 則等 式 依 然 成 立 。例 如 ： （ 2-18） 5. 反 演 定 理 ： 對 任 一 邏 輯 式 原 變 量反 變 量 反 變 量原 變 量 ， 0110 YY 變 換 順 序 先 括 號 ，然 后 乘 ， 最 后 加不 屬 于 單 個 變 量 的反 號 保 留 不 變 （ 2-19）DCBDACBCA DCCBAY CDCBAY )( )(例 如 ： （ 2-20） 5. 反 演 定 理 （ 特 例 ） ：BABA BABA A B AB0 0 0 1 1 1 10 1 0 1 1

8、 0 11 0 0 1 0 1 11 1 1 0 0 0 0BA A B BA可 以 用 列 真 值 表 的 方 法 證 明 ： （ 2-21） 6. 對 偶 定 理 ： 原 變 量反 變 量 反 變 量原 變 量 ， 0110Y YD公 式 的 對 偶式 為 ？ CAABBCCAAB 對 任 何 一 個 邏 輯 式 Y，若 兩 邏 輯 式 相 等 ， 則 它 們 的 對 偶 式 也 相 等 。 （ 2-22） 1.3.1 真 值 表 ： 將 輸 入 、 輸 出 的 所 有 可 能 狀 態(tài) 一 一 對 應(yīng) 地 列 出 。A B C F0 1 0 00 1 1 00 0 0 0 0 0 1 01

9、 0 0 01 0 1 11 1 0 11 1 1 1設(shè) A、 B、 C為 輸 入 變 量 ， F為 輸 出 變 量 。 1.3 邏 輯 函 數(shù) 的 表 示 法 （ 2-23） n個 變 量 可 以 有 2n個 組 合 ， 一般 按 二 進(jìn) 制 的 順 序 ， 輸 出 與 輸 入狀 態(tài) 一 一 對 應(yīng) ， 列 出 所 有 可 能 的狀 態(tài) 。 （ 2-24） 1.3.2 邏 輯 函 數(shù) 式把 邏 輯 函 數(shù) 的 輸 入 、 輸 出 關(guān) 系 寫 成 與 、或 、 非 等 邏 輯 運 算 的 組 合 式 ， 即 邏 輯 代 數(shù)式 ， 又 稱 為 邏 輯 函 數(shù) 式 ， 通 常 采 用 “ 與 或

10、”的 形 式 。 邏 輯 函 數(shù) 的 兩 種 標(biāo) 準(zhǔn) 形 式 ：最 小 項 之 和 最 大 項 之 積比 如 ： ABCCBACBACBACBAF F=(A+B+C)(A+B+C)(A+B+C) （ 2-25） 若 表 達(dá) 式 的 乘 積 項 中 包 含 了 所 有 輸 入 變量 的 原 變 量 或 反 變 量 ， 則 這 一 項 稱 為 最 小項 ， 上 式 中 每 一 項 都 是 最 小 項 。最 小 項 m： m是 乘 積 項 包 含 n個 因 子 n個 變 量 均 以 原 變 量 和 反 變 量 的 形式 在 m中 出 現(xiàn) 一 次 （ 2-26） 最 小 項 舉 例 ： 兩 變 量 A

11、, B的 最 小 項 三 變 量 A,B,C的 最 小 項 ）4個（ 22ABBABABA , ）8個（ 32ABCCABCBACBA BCACBACBACBA , , （ 2-27） 最 小 項 的 編 號 ：最 小 項 取 值 對 應(yīng) 編 號A B C 十 進(jìn) 制 數(shù)0 0 0 0 m00 0 1 1 m10 1 0 2 m20 1 1 3 m31 0 0 4 m41 0 1 5 m 51 1 0 6 m61 1 1 7 m7ABCCABCBA CBABCA CBA CBA CBA （ 2-28） 最 小 項 的 性 質(zhì) 在 輸 入 變 量 任 一 取 值 下 ， 有 且 僅 有 一 個

12、最 小 項 的值 為 1。 全 體 最 小 項 之 和 為 1 。 任 何 兩 個 最 小 項 之 積 為 0 。 若 兩 個 最 小 項 中 只 有 一 個 變 量 以 原 、 反 狀 態(tài) 相 區(qū)別 ， 則 稱 它 們 為 邏 輯 相 鄰 。 兩 個 相 鄰 的 最 小 項 之 和 可 以 合 并 ， 消 去 一 對 因 子 ， 只留 下 公 共 因 子 。 （ 2-29） ABCCBACBACBACBAF 邏 輯 相 鄰 CBCBACBA 邏 輯 相 鄰 的 項 可 以合 并 ， 消 去 一 個 因 子 （ 2-30） 邏 輯 函 數(shù) 最 小 項 之 和 的 形 式 ： 例 ： ),( )

13、(),( 763m BCAABCCAB AABCCAB BCCABCBAY 利 用 公 式可 將 任 何 一 個 函 數(shù) 化 為1AA im （ 2-31） 邏 輯 函 數(shù) 最 小 項 之 和 的 形 式 ： 例 ： ),( )(),( 763m BCAABCCAB AABCCAB BCCABCBAY 利 用 公 式可 將 任 何 一 個 函 數(shù) 化 為1AA im （ 2-32） 邏 輯 函 數(shù) 最 小 項 之 和 的 形 式 ： 例 ： ),( )(),( 763m BCAABCCAB AABCCAB BCCABCBAY 利 用 公 式可 將 任 何 一 個 函 數(shù) 化 為1AA im （

14、 2-33） 1.3.3 卡 諾 圖 ：將 n個 輸 入 變 量 的 全 部 最 小 項 用 小 方 塊陣 列 圖 表 示 ， 并 且 將 邏 輯 相 臨 的 最 小 項 放在 相 臨 的 幾 何 位 置 上 ， 所 得 到 的 陣 列 圖 就是 n變 量 的 卡 諾 圖 。 卡 諾 圖 的 每 一 個 方 塊 （ 最 小 項 ） 代 表一 種 輸 入 組 合 ， 并 且 把 對 應(yīng) 的 輸 入 組 合 注明 在 陣 列 圖 的 上 方 和 左 方 。 （ 2-34） 1 00 1A B 0 101 A BC00 01 11 1001 1 1 0 11 0 1 兩 變 量 卡 諾 圖 三 變

15、量 卡 諾 圖 （ 2-35） ABCD00 01 11 100001 1 1 0 1 1 0 10 0 1 1 1 0 1 1110 四 變 量 卡 諾 圖 單 元 編 號0010， 對應(yīng) 于 最 小項 ： DCBAABCD=0100時 函數(shù) 取 值 函 數(shù) 取 0、1均 可 ，稱 為 無 所謂 狀 態(tài)（ 或 任 意狀 ） 。只 有一 項不 同 （ 2-36） 約 束 項 任 意 項 邏 輯 函 數(shù) 中 的 無 關(guān) 項 ： 約 束 項 和 任 意 項 可以 寫 入 函 數(shù) 式 ， 也 可 不 包 含 在 函 數(shù) 式 中 ，因 此 統(tǒng) 稱 為 無 關(guān) 項 。 （ 2-37） 有 時 為 了 方

16、 便 ， 用 二 進(jìn) 制 對 應(yīng) 的 十 進(jìn) 制表 示 單 元 編 號 。ABC00 01 11 1001 0 1 3 24 5 7 6F( A , B , C )=( 1 , 2 , 4 , 7 ) 1,2,4,7單元 取 1， 其它 取 0 （ 2-38） ABCD00 01 11 100001 0 1 3 2 4 5 7 612 13 15 14 8 9 11 10 1110 （ 2-39） 1.3.4 邏 輯 圖 ：把 相 應(yīng) 的 邏 輯 關(guān) 系 用 邏 輯 符 號 和連 線 表 示 出 來 。 )( BAB )( BAA )()( BABA （ 2-40） 1.3.5 波 形 圖 ：

17、 （ 2-41） 邏 輯 圖波 形 圖真 值 表 邏 輯 表 達(dá) 式 卡 諾 圖 （ 2-42） 1.4.1 利 用 邏 輯 代 數(shù) 的 基 本 公 式 ：例 ： ABAC BCA BCBA ABCBA CCABCBA ABCCABCBAF )( )( )( 反 變 量 吸 收提 出 AB=1提 出 A 1.4 邏 輯 函 數(shù) 的 化 簡 （ 2-43） 例 ： CBBCBAABF )( CBBCBAAB ）（ 反 演CBAABC CCBAAB )( )( 配 項CBBCAABC CBACBAAB 被 吸 收 被 吸 收CBBBCAAB )( CBCAAB （ 2-44）AB=AC B=C ?

18、A+B=A+C B=C?請 注 意 與 普 通 代 數(shù) 的 區(qū) 別 ！ （ 2-45） 1.4.2 利 用 卡 諾 圖 化 簡 ：ABC00 01 11 1001 0 0 1 00 0 1 1ABC BCA BC BCAABC （ 2-46） ABC00 01 11 1001 0 0 1 0 0 0 1 1 AB? （ 2-47） ABC00 01 11 1001 0 0 1 0 0 0 1 1 AB BCF=AB+BC化 簡 過 程 ： （ 2-48） 利 用 卡 諾 圖 化 簡 的 規(guī) 則 ：（ 1） 相 臨 單 元 的 個 數(shù) 是 2N個 ， 并 組 成 矩 形時 ， 可 以 合 并 。

19、ABCD00 01 11 100001 0 0 0 00 0 1 0 0 1 1 01 1 1 01110 AD （ 2-49） ABCD00 01 11 100001 0 0 0 0 0 1 0 01 1 0 0 1 0 0 01110不 是 矩 形 （ 2-50） （ 2） 先 找 面 積 盡 量 大 的 組 合 進(jìn) 行 化 簡 ， 可 以 減 少 更 多 的 因 子 ， 。（ 3） 各 最 小 項 可 以 重 復(fù) 使 用 。（ 4） 注 意 利 用 無 所 謂 狀 態(tài) ， 可 以 使 結(jié) 果 大 大 簡 化 。（ 5） 所 有 的 1都 要 被 圈 過 ， 。（ 6） 化 簡 后 的 邏

20、 輯 式 是 各 化 簡 項 的 邏 輯 和 。（ 7） 化 簡 結(jié) 果 不 唯 一 。 （ 2-51） 例 ： 化 簡 F(A,B,C,D)=(0,2,3,5,6,8,9,10,11, 12,13,14,15)ABCD00 01 11 100001 1 0 1 10 1 0 1 1 1 1 11 1 1 11110 ADC CBDB DCB DCBDBCBDCAF （ 2-52） 例 ： 化 簡ABCD00 01 11 100001 1 1 1 11 1 1 1 1 0 0 11 1 1 11110 ABDABDF （ 2-53） 例 ： 已 知 真 值 表 如 圖 ， 用 卡 諾 圖 化

21、簡 。A B C F0 0 0 00 0 1 00 1 0 00 1 1 0 1 0 0 11 1 0 11 1 1 1101狀 態(tài) 未 給 出 ， 即 是 無 所 謂 狀 態(tài) 。 （ 2-54） ABC00 01 11 1001 0 0 0 0 1 1 1 化 簡 時 可 以 將 無 所 謂 狀 態(tài) 當(dāng) 作 1或 0，目 的 是 得 到 最 簡 結(jié) 果 。認(rèn) 為 是 1 AF=A （ 2-55） 00 01 11 1000 101 11110 1AB CD =0DCB+ADD+ABCD+ABCCB+ADCD+ABCBACD+BA DCBABCDADCBAY 給 定 約 束 條 件 為 ：例

22、：例 （ 2-56） 00 01 11 1000 0 1 x 001 0 x 1 011 x 0 x x10 1 x 0 xAB CD =0DCB+ADD+ABCD+ABCCB+ADCD+ABCBACD+BA DCBABCDADCBAY 給 定 約 束 條 件 為 ：例 ： （ 2-57） 00 01 11 1000 0 1 x 001 0 x 1 011 x 0 x x10 1 x 0 xAB CD DADA =0DCB+ADD+ABCD+ABCCB+ADCD+ABCBACD+BA DCBABCDADCBAY 給 定 約 束 條 件 為 ：例 ： （ 2-58） 08642 1514131211105 mmmmmmm: ),(m)D,C,B,A(Y約 束 條 項 00 01 11 1000 0 0 0 101 1 x 0 111 x x x x10 1 0 x xAB CD DCDBDAY 例 （ 2-59） 第 二 章 作 業(yè) P62 2.15 (6)(7)(8)(9)(10) P63 2.19 (4)(5) 2.20 (b)(d) P64 2.22 (3)(4) 2.23 (3)(4)