《邏輯與布爾代數(shù)》課件

邏輯與布爾代數(shù)探索從古典邏輯到現(xiàn)代數(shù)字系統(tǒng)設(shè)計的理論基礎(chǔ)課程概述課程目標掌握邏輯基礎(chǔ)和布爾代數(shù)教材資料指定教材與補充閱讀材料評分標準考試、作業(yè)及課堂表現(xiàn)時間安排16周課程，每周3學時第一部分：邏輯基礎(chǔ)數(shù)理邏輯應用實際應用場景推理規(guī)則有效推理方法謂詞邏輯帶有量詞的邏輯命題邏輯基本命題運算什么是邏輯學？1起源研究有效推理的學科2三段論亞里士多德的推理體系3發(fā)展歷程從傳統(tǒng)到現(xiàn)代數(shù)理邏輯4應用領(lǐng)域計算機科學、數(shù)學、哲學命題及其分類命題定義能判斷真假的陳述句命題類型簡單命題復合命題命題狀態(tài)真命題假命題表示符號用p、q、r等字母表示命題的真值真值表列出所有可能賦值情況系統(tǒng)分析命題真假確定方法分析命題內(nèi)容根據(jù)定義判斷真假邏輯類型二值邏輯：真或假多值邏輯：多種真值邏輯聯(lián)結(jié)詞否定(?)真變假，假變真合取(∧)類似"且"，同真才真析取(∨)類似"或"，同假才假蘊含(→)前假后真，結(jié)果為真等價(?)真值相同則為真否定運算否定定義命題p的否定為非p，記作?p真值表p為真時?p為假，p為假時?p為真雙重否定律?(?p)≡p應用案例開關(guān)電路，反向控制合取運算合取定義命題p與q的合取，記為p∧q真值表僅當p、q都為真時結(jié)果為真特性交換律、結(jié)合律、分配律對比等同于日常語言中的"且"析取運算析取運算p∨q表示"p或q"，當p、q至少有一個為真時結(jié)果為真，僅當都為假時結(jié)果為假蘊含運算蘊含定義"如果p，那么q"，記作p→q真值規(guī)則僅當p為真q為假時結(jié)果為假特殊性前件為假時，蘊含式恒為真條件關(guān)系p是q的充分條件，q是p的必要條件等價運算pqp?q真真真真假假假真假假假真等價運算p?q表示"p當且僅當q"，當p、q真值相同時結(jié)果為真，不同時為假復合命題練習聯(lián)結(jié)詞構(gòu)建利用各種聯(lián)結(jié)詞組合命題真值計算按運算優(yōu)先級計算真值常見錯誤運算順序混淆，真值判斷失誤命題公式合式公式符合語法規(guī)則的命題表達式基本元素命題變元p,q,r和命題常量T,F構(gòu)成規(guī)則變元是公式，聯(lián)結(jié)詞連接的公式也是公式分解方法按主聯(lián)結(jié)詞遞歸分解復雜公式真值表與公式2^n可能情況n個變元有2^n種可能賦值5基本步驟列出所有變元組合及中間計算結(jié)果3簡化技巧利用對稱性減少計算量重言式與矛盾式重言式永真式，在任何賦值下均為真p∨?p(p→q)?(?p∨q)矛盾式永假式，在任何賦值下均為假p∧?p?(p∨?p)判定與應用通過真值表判定用于定理證明構(gòu)建有效論證邏輯等價關(guān)系等價定義p?q為重言式時，稱p與q等價，記為p≡q德·摩根律?(p∧q)≡?p∨?q，?(p∨q)≡?p∧?q分配律p∧(q∨r)≡(p∧q)∨(p∧r)結(jié)合律(p∧q)∧r≡p∧(q∧r)替換規(guī)則與等價變換確定目標明確原始公式和期望形式識別規(guī)則選擇適用的等價規(guī)則替換變形按步驟執(zhí)行等價變換驗證結(jié)果檢查變換是否正確范式范式概念具有特定形式的邏輯表達式1基本范式合取范式(CNF)和析取范式(DNF)主范式主合取范式(PCNF)和主析取范式(PDNF)轉(zhuǎn)換方法利用邏輯等價變換和真值表4謂詞邏輯基礎(chǔ)命題局限無法表達內(nèi)部結(jié)構(gòu)和量化關(guān)系謂詞定義刻畫對象性質(zhì)或關(guān)系的函數(shù)基本元素個體詞a,b,c和謂詞P,Q,R量詞引入全稱量詞?和存在量詞?全稱量詞與存在量詞全稱量詞(?)對所有個體x，P(x)為真例：?x(x>0→x^2>0)存在量詞(?)存在個體x，使P(x)為真例：?x(x^2=2)量詞轉(zhuǎn)換?(?x)P(x)≡(?x)?P(x)?(?x)P(x)≡(?x)?P(x)謂詞公式的構(gòu)造與解釋一階語法謂詞、變量、量詞和聯(lián)結(jié)詞的組合規(guī)則解釋模型給定論域及解釋函數(shù)確定公式意義真值判定基于解釋評估公式真假公式分析?x?y(x第二部分：布爾代數(shù)數(shù)字電路設(shè)計實際工程應用布爾代數(shù)應用電路分析與綜合布爾函數(shù)表達式與真值表基本概念運算與定律布爾代數(shù)的歷史與發(fā)展11854年喬治·布爾發(fā)表《思維規(guī)律研究》21938年克勞德·香農(nóng)證明布爾代數(shù)與開關(guān)電路的關(guān)系31940年代馮·諾依曼計算機架構(gòu)采用二進制邏輯4現(xiàn)代應用數(shù)字系統(tǒng)設(shè)計、計算機體系結(jié)構(gòu)的基礎(chǔ)布爾代數(shù)的公理系統(tǒng)1封閉性任意兩元素的運算結(jié)果仍在集合內(nèi)2單位元存在0和1，滿足特定運算律3互補性每個元素有唯一互補元4對偶原理互換運算和單位元得到對偶定理5集合論聯(lián)系布爾代數(shù)與集合運算直接對應布爾代數(shù)的基本運算與運算(·)對應邏輯"且"電路中的串聯(lián)或運算(+)對應邏輯"或"電路中的并聯(lián)非運算(')對應邏輯"非"電路中的反相優(yōu)先級非>與>或可用括號改變布爾代數(shù)的基本定律布爾代數(shù)基本定律在電路設(shè)計和化簡中的應用頻率統(tǒng)計布爾函數(shù)2^n函數(shù)定義從{0,1}^n到{0,1}的映射2^(2^n)函數(shù)數(shù)量n變量布爾函數(shù)的個數(shù)4表示方法真值表、表達式、卡諾圖、邏輯電路布爾表達式表達式構(gòu)成變量、常量、運算符組合遵循布爾代數(shù)語法規(guī)則表達式求值代入變量值按運算優(yōu)先級計算等價表達式形式不同但函數(shù)相同可通過定律相互轉(zhuǎn)換最小項與最大項變量最小項最大項x=0,y=0x'y'x+yx=0,y=1x'yx+y'x=1,y=0xy'x'+yx=1,y=1xyx'+y'最小項：在特定變量賦值下值為1的與項最大項：在特定變量賦值下值為0的或項標準形式析取標準形式(SOP)最小項之和F=Σm_i合取標準形式(POS)最大項之積F=ΠM_i特性唯一表示可相互轉(zhuǎn)換便于邏輯設(shè)計卡諾圖基礎(chǔ)構(gòu)造原理格雷碼排列的二維真值表維度分類根據(jù)變量數(shù)確定一維或二維表格相鄰概念僅一個變量取值不同的單元主要優(yōu)勢直觀顯示最簡表達式二、三變量卡諾圖二變量圖2×2方格表示四種輸入組合三變量圖2×4方格表示八種輸入組合合并規(guī)則相鄰的2^n個1可合并消除n個變量四變量卡諾圖四變量卡諾圖使用4×4=16個方格，展示所有可能的輸入組合，注意邊緣單元的環(huán)繞相鄰性卡諾圖化簡法填寫卡諾圖將函數(shù)真值寫入對應位置最大圈組找出所有1的最大相鄰組合質(zhì)蘊涵項識別必須使用的圈組最小覆蓋選擇最少圈組覆蓋所有1無關(guān)項在卡諾圖中的應用無關(guān)項定義輸入組合不會出現(xiàn)函數(shù)值可任意指定表示方法用"X"或"d"標記區(qū)別于"0"和"1"優(yōu)化應用可視為0或1選擇有利于簡化的取值減少項數(shù)或門電路布爾代數(shù)的邏輯門實現(xiàn)基本邏輯門與門、或門、非門復合邏輯門與非門、或非門、異或門門電路構(gòu)建連接多個門實現(xiàn)復雜函數(shù)表達式轉(zhuǎn)換布爾表達式直接映射為門電路組合邏輯電路電路特點輸出僅依賴當前輸入，無記憶狀態(tài)常見類型加法器、編碼器、譯碼器、多路復用器設(shè)計方法功能規(guī)格→布爾函數(shù)→化簡→電路實現(xiàn)時序問題門延遲可能導致競爭冒險半加器與全加器半加器或門與門異或門全加器組件構(gòu)成：兩個半加器和一個或門，用于實現(xiàn)三位二進制加法編碼器與譯碼器編碼器多輸入少輸出將2^n個輸入編碼為n位二進制如：8-3優(yōu)先編碼器譯碼器少輸入多輸出將n位二進制譯碼為2^n個輸出如：3-8譯碼器應用示例鍵盤掃描地址解碼顯示驅(qū)動多路復用器與多路分配器多路復用器數(shù)據(jù)選擇器，多輸入單輸出1多路分配器數(shù)據(jù)分配器，單輸入多輸出2函數(shù)實現(xiàn)任意布爾函數(shù)可用多路復用器實現(xiàn)設(shè)計案例數(shù)據(jù)總線選擇，控制信號分發(fā)NAND與NOR通用門NAND門完備性僅用NAND門構(gòu)建任意邏輯函數(shù)NOR門完備性僅用NOR門構(gòu)建任意邏輯函數(shù)成本效率減少芯片類型，提高集成度可編程邏輯設(shè)備PLD類型PLD：簡單可編程邏輯CPLD：復雜可編程邏輯FPGA：現(xiàn)場可編程門陣列編程語言VHDLVerilogSystemVerilog設(shè)計方法結(jié)構(gòu)化描述行為級描述混合級設(shè)計第三部分：實際應用與擴展量子計算布爾邏輯的量子擴展多值邏輯超越二值的邏輯系統(tǒng)算法設(shè)計邏輯在算法中的應用工程問題實際工程案例分析邏輯設(shè)計案例分析交通燈控制狀態(tài)轉(zhuǎn)換與時序控制售貨機控制器輸入識別與狀態(tài)管理簡易計算器運算單元與顯示控制電梯控制優(yōu)先級處理與安全保障時序邏輯簡介基本特點輸出取決于當前輸入和歷史狀態(tài)含有存儲元件觸發(fā)器類型SR、D、JK、T觸發(fā)器不同時鐘觸發(fā)方式狀態(tài)機離散狀態(tài)系統(tǒng)狀態(tài)轉(zhuǎn)換圖和表Moore和Mealy模型邏輯推理在人工智能中的應用定理證明自動推導數(shù)學公式證明專家系統(tǒng)基于規(guī)則的知識推理知識表示邏輯形式化描述事實和規(guī)則機器學習邏輯規(guī)則與神經(jīng)網(wǎng)絡結(jié)合多值邏輯與模糊邏輯三值邏輯真、假、未知三種狀態(tài)SQL數(shù)據(jù)庫中應用廣泛模