二章節(jié)邏輯代數(shù)基礎(chǔ)課件

1、第二章 邏輯代數(shù)基礎(chǔ)第一節(jié) 邏輯代數(shù) 邏輯代數(shù)是由邏輯變量集K，常量0、1，“與”、“或”、“非”三種運(yùn)算構(gòu)成的代數(shù)系統(tǒng)。一、邏輯變量 邏輯變量集指邏輯代數(shù)中所有可能變量的集合，它可用任何字母表示，但每個(gè)變量的取值只可能為常量0或1，表示兩種狀態(tài)。二、邏輯運(yùn)算 1、或運(yùn)算 符號(hào)“+”，L=A+B 真值表：ABL000011101111 2、與運(yùn)算 符號(hào)“”，L=AB 真值表：ABL000010100111 4、或非運(yùn)算 L=A+B 真值表：ABL001010100110 5、與非運(yùn)算 L=AB 真值表：ABL001011101110 7、異或運(yùn)算 符號(hào)“ ”，L = A B = AB+AB 真

2、值表：ABL000011101110注意：先“非”后“與”最后“或”；先括號(hào)內(nèi)再括號(hào)外；同種邏輯運(yùn)算符號(hào)按從左到右的順序。三、 邏輯函數(shù)1、定義 設(shè)某一邏輯網(wǎng)絡(luò)的輸入邏輯變量為 A1，A2，An，輸出邏輯變量為F，當(dāng) A1，A2，An的取值確定后，F(xiàn)的值就惟一確定。則稱F是A1，A2，An的邏輯函數(shù)。記為：F=f（A1，A2，An）邏輯網(wǎng)絡(luò)A1AnA2F （1）邏輯表達(dá)式 邏輯表達(dá)式是由邏輯變量和“與”“或”“非”三種運(yùn)算符構(gòu)成的式子。 如：F=f（A，B）=AB+AB 2、邏輯函數(shù)的表示法（2）真值表 由邏輯變量的所有可能取值組合及其對(duì)應(yīng)的邏輯函數(shù)所構(gòu)成的表格。ABF000011101110

3、（3）卡諾圖 由邏輯變量的所有可能組合的小方格構(gòu)成的圖形。例.表達(dá)式：F=AB+AC+ABCABCF000000110100011010011010110111111111ABC00 01 11 10 01真值表：卡諾圖：（5）交換律 A+B=B+A AB =BA（6）結(jié)合律 （A+B）+C=A+（B+C） （AB） C=A（BC）（7）分配律 （A+B）C=AC+BC A+（B C）=（A+B）（A+C）2.2定理定理1：德摩根定理 （1）（X1+X2+Xn） = X1X2Xn （2）（X1X2Xn） = X1+X2+Xn敘述：n個(gè)邏輯變量的“或”的“非”等于各個(gè)邏輯變量的“非”的“與”；

4、n個(gè)邏輯變量的“與”的“非”等于各邏輯變量的“非”的“或”。定理3：對(duì)偶定理對(duì)偶定義：f （X1，X2，Xn，0，1，+，）= f（X1，X2，Xn，1，0，+）敘述：邏輯函數(shù)f(X1，X2，Xn，0，1，+，)，若把該函數(shù)中的“”換為“+”，“+”換為“”，0換為1，1換為0，而變量保持不變，則所得函數(shù)稱原函數(shù)的對(duì)偶函數(shù)。定理：f（X1，X2，Xn，0，1，+，）= f（X1，X2，Xn，0，1，+，）敘述：任何函數(shù)的對(duì)數(shù)偶函數(shù)，可通過(guò)原函數(shù)的所有變量取反，再對(duì)整個(gè)函數(shù)求反而得。推理1： 原函數(shù)f與對(duì)偶函數(shù)f互為對(duì)偶函數(shù)，（f） =f推理2： f=g f= g自對(duì)偶函數(shù)：若f=f，則稱f為自

5、對(duì)偶函數(shù)。 定理4 展開(kāi)定理1. f(X1, ,Xi, ,Xn) = Xif(X1, ,1, Xn)+Xif(X1, 0, Xn)2. f(X1, ,Xi, ,Xn) = Xi+ f(X1, ,0, ,Xn) Xi+ f(X1, ,1, ,Xn)敘述：任何邏輯函數(shù)都可對(duì)它的某一個(gè)變量Xi展開(kāi)，或展開(kāi)“與一或”形式，或展開(kāi)為“或一與”形式。2.3常用公式1、AB+AB=A2、A+AB=A3、A+AB=A+B4、AB+AC+BC=AB+AC5、AB+AB=AB+AB第三節(jié) 邏輯函數(shù)的形式一、基本形式 1.與或式 一個(gè)函數(shù)表達(dá)式中包含著若干個(gè)與式，每個(gè)與式中可有多個(gè)以原變量或反變量出現(xiàn)的字母，所有這

6、些與項(xiàng)的或運(yùn)算就構(gòu)成與或式。 例.F=AB+BC+ABC二、邏輯函數(shù)的標(biāo)準(zhǔn)形式 最小項(xiàng)表達(dá)式 最大項(xiàng)表達(dá)式1.最小項(xiàng) 定義 最小項(xiàng)就是包含函數(shù)中所有變量的乘積項(xiàng)。變量或以原變量或以反變量形式出現(xiàn)，且每個(gè)變量在乘積項(xiàng)中出現(xiàn)且只出現(xiàn)一次。數(shù)目 n個(gè)變量最多可有 個(gè)最小項(xiàng)。用mi表示，0i2n-1舉例 三變量A，B，C，可構(gòu)成 個(gè)最小項(xiàng)：8ABC ABC ABC ABCABC ABC ABC ABC用“1”表示原變量，“0”表示反變量，構(gòu)成二進(jìn)制數(shù)的對(duì)應(yīng)的十進(jìn)制數(shù)即為m的下標(biāo)。=m0 =m1 =m2 =m3=m4 =m5 =m6 =m7 2n2.最小項(xiàng)表達(dá)式（1）給定最小項(xiàng)之和所組成的邏輯表達(dá)式為最

7、小項(xiàng)表達(dá)式。（2）任意一個(gè)不是最小項(xiàng)表達(dá)式形式的邏輯函數(shù)可通過(guò)反復(fù)使用下式將其變?yōu)樽钚№?xiàng)表達(dá)式： A=A（B+B）（3）最小項(xiàng)表達(dá)式的主要性質(zhì)：若mi是邏輯函數(shù)F（A1，A2，An） 的一個(gè)最小項(xiàng)，則使mi=1的一組變量取值必定使F值為1；若F1和F2都是A1，A2，An的函數(shù)，則F=F1+F2將包括F1和F2中所有的最小項(xiàng)，G=F1F2將包括F1和F2的公共最小項(xiàng)；反函數(shù)F必定由原函數(shù)F所包含的最小項(xiàng)之外的全部最小項(xiàng)組成；（4）最小項(xiàng)表達(dá)式是邏輯函數(shù)標(biāo)準(zhǔn)形式之一，稱之為“積之和范式”或“主析取范式”。3.最大項(xiàng) 定義 給定函數(shù)的n個(gè)邏輯變量，它們所組成的和項(xiàng)中，每個(gè)變量或以原變量或以反變量的

8、形式出現(xiàn)，且僅出現(xiàn)一次，這個(gè)和項(xiàng)稱為n變量的最大項(xiàng)。 數(shù)量 n變量可構(gòu)成2n個(gè)最大項(xiàng)，用Mi表示，其中0i2n-1 =M7 =M6 =M5 =M4 =M3 =M2 =M1 =M0 A+B+C A+B+C A+B+C A+B+C A+B+C A+B+C A+B+C A+B+C 舉例 3變量A，B，C可構(gòu)成8個(gè)最大項(xiàng)： 用0代替最大項(xiàng)中原變量，1代替反變量所得二進(jìn)制數(shù)的等值十進(jìn)制數(shù)即是下標(biāo)i。最大項(xiàng)的性質(zhì)： 對(duì)于任一最大項(xiàng)，只有一組變量可使其值為0； 任意兩個(gè)最大項(xiàng)Mi和Mj（ij）之和必為1； n變量的所有2n個(gè)最大項(xiàng)之積為0： 4.最大項(xiàng)表達(dá)式（1）由給定函數(shù)的最大項(xiàng)之積所組成的邏輯表達(dá)式為最

9、大項(xiàng)表達(dá)式。（2）任意一個(gè)不是最大項(xiàng)表達(dá)式形式的邏輯函數(shù)可通過(guò)反復(fù)使用下式將其變?yōu)樽畲箜?xiàng)表達(dá)式： A=A+BB（3）最大項(xiàng)表達(dá)式的主要性質(zhì)可根據(jù)最小項(xiàng)表達(dá)式的性質(zhì)得出。最小項(xiàng)表達(dá)式和最大項(xiàng)表達(dá)式是邏輯函數(shù)的兩種標(biāo)準(zhǔn)形式。5.最小項(xiàng)和最大項(xiàng)的關(guān)系： （1）同一邏輯問(wèn)題中，下標(biāo)相同的最小項(xiàng)和最大項(xiàng)之間存在互補(bǔ)關(guān)系，即mi=Mi； （2）對(duì)于一個(gè)用最小項(xiàng)表達(dá)式表示的n變量函數(shù)，改用最大項(xiàng)表達(dá)式表示時(shí)，其最大項(xiàng)的編號(hào)必定都不是最小項(xiàng)的編號(hào)，這些最小項(xiàng)的個(gè)數(shù)與最大項(xiàng)的個(gè)數(shù)之和為2n； （3）對(duì)于邏輯函數(shù)F，F(xiàn)的最小項(xiàng)為F中最小項(xiàng)以外的所有最小項(xiàng)； （4）F中包含mi，則F中必包含M2n-i-1； 三、邏

10、輯函數(shù)的三種表示方法的關(guān)系 1.表達(dá)式與真值表（1）最小項(xiàng)表達(dá)式中的各個(gè)最小項(xiàng)與真值表中F=1的各行變量取值一一對(duì)應(yīng)；（2）最大項(xiàng)表達(dá)式中各個(gè)最大項(xiàng)與真值表中F=0的各行變量取值一一對(duì)應(yīng)。 2.表達(dá)式與卡諾圖卡諾圖中標(biāo)“1”的小方格與最小項(xiàng)表達(dá)式中的最小項(xiàng)一一對(duì)應(yīng)。 邏輯函數(shù)表達(dá)式的形式不惟一，但都可以轉(zhuǎn)換成惟一的標(biāo)準(zhǔn)形式，方法有兩種： 代數(shù)轉(zhuǎn)換法真值表轉(zhuǎn)換法 第四節(jié) 邏輯函數(shù)的化簡(jiǎn)最簡(jiǎn)邏輯函數(shù)的形式： 最簡(jiǎn)與或形式 最簡(jiǎn)或與形式最簡(jiǎn)式的條件： 一個(gè)給定函數(shù)等效的積之和式中，若同時(shí)滿足乘積項(xiàng)數(shù)最少；每個(gè)乘積項(xiàng)中變量的個(gè)數(shù)最少，則成此積之和式是給定函數(shù)的最簡(jiǎn)式。 兩種化簡(jiǎn)方法： 代數(shù)化簡(jiǎn)法 卡諾

11、圖化簡(jiǎn)法 一、代數(shù)化簡(jiǎn)法 應(yīng)用常用公式、定理、公理進(jìn)行化簡(jiǎn)。二、卡諾圖化簡(jiǎn)法 1.化簡(jiǎn)原理 F=ABC+ABC=（A+A）BC=BC即卡諾圖上相鄰的兩個(gè)小方格可合成一項(xiàng)?！跋噜彙保核交虼怪狈较驇缀蜗噜?。2.形成“圈”的規(guī)則：（1）n變量卡諾圖中，任何2m格標(biāo)“1”的相鄰單元可形成一個(gè)圈，該圈所代表的乘積項(xiàng)由n-m個(gè)變量組成；（2）若相鄰標(biāo)“1”的單元格個(gè)數(shù)非2m個(gè)，則至少形成兩個(gè)圈。3.化簡(jiǎn)步驟：（1）列出邏輯函數(shù)的最小項(xiàng)表達(dá)式；（2）畫(huà)對(duì)應(yīng)卡諾圖；（3）確定化簡(jiǎn)相鄰項(xiàng)的組合，形成“圈”；（4）寫(xiě)出最簡(jiǎn)式。4.化簡(jiǎn)規(guī)則：（1）等效性 所有標(biāo)“1”的小方格都劃進(jìn)圈內(nèi)，所有值為0 的小方格都劃在

12、圈外。（2）最簡(jiǎn)性圈數(shù)最少，圈內(nèi)小方格數(shù)最多。包含無(wú)關(guān)最小項(xiàng)的邏輯函數(shù)的化簡(jiǎn)（1）無(wú)關(guān)最小項(xiàng) 變量的某些取值不可能出現(xiàn) 變量某些取值下使邏輯函數(shù)的值不確定（2）方法 恰當(dāng)?shù)亓顭o(wú)關(guān)項(xiàng)取值“0”或取值“1”，使函數(shù)化為最簡(jiǎn)。例1. A、B、C、D表示8421碼，F(xiàn)為輸出，當(dāng)8421碼對(duì)應(yīng)的十進(jìn)制數(shù)5時(shí)，輸出“1”，否則輸出“0”，求其最簡(jiǎn)式。例2. 十字路口的交通信號(hào)燈，紅、綠黃分別用A、B、C表示，燈亮“1”，燈滅“0”，停車時(shí)L=1，通車時(shí)L=0，用卡諾圖化簡(jiǎn)此函數(shù)。多輸出函數(shù)的化簡(jiǎn) 對(duì)同一組變量的輸入，有多個(gè)不同函數(shù)輸出，并且多個(gè)輸出間有關(guān)聯(lián)，應(yīng)考慮化簡(jiǎn)結(jié)果使多個(gè)輸出函數(shù)間公共部分最多，即用到的與項(xiàng)最少。1.證明下列等式（1）AB+AC+BC+CD=AB+C（2）BC+D+D（B+C）（DA+B）=B+D（3）AB+BC+CA=AB+BC+CA（4）AB+BC+CA=（A+B）（B+C）（C+A）2.用摩根或香農(nóng)定理求反函數(shù)3.求最小項(xiàng)表達(dá)式和最大項(xiàng)表達(dá)式 F（A，B，C）=A+BC+ABC4.用代數(shù)化簡(jiǎn)法化簡(jiǎn)下式為最間與或式（1）F=AB+AC+BC（2）F=ABC