第 4 章 邏輯門和布爾代數(shù) - SJTU

1、第 4 章 邏輯門和布爾代數(shù)第三部分：邏輯表達(dá)式簡化邏輯表達(dá)式的標(biāo)準(zhǔn)表示法和真值表卡諾圖內(nèi)容提要o 用布爾代數(shù)的常用公式進(jìn)行布爾表達(dá)式（邏用布爾代數(shù)的常用公式進(jìn)行布爾表達(dá)式（邏輯表達(dá)式）的化簡輯表達(dá)式）的化簡o 邏輯表達(dá)式的標(biāo)準(zhǔn)形式n 標(biāo)準(zhǔn)和之積n 標(biāo)準(zhǔn)積之和o 卡諾圖n 用卡諾圖化簡積之和n 用卡諾圖化簡和之積邏輯表達(dá)式的簡化o 為什么要簡化？n 用軟件實現(xiàn)邏輯表達(dá)式時，可以減少判斷，減少分支n 用硬件實現(xiàn)邏輯表達(dá)式時，可以減少門和連線的數(shù)量n 既然能簡單，為什么要搞那么復(fù)雜？o 簡化的方法n 使用布爾代數(shù)的常用公式n 使用卡諾圖邏輯表達(dá)式的簡化o 例：化簡如下表達(dá)式n ab+a(b+c)+

2、b(b+c)=ab+ab+ac+bb+bc=ab+ac+b+bc=b(a+1+c)+ac=b+ac邏輯表達(dá)式的簡化o ab+a(b+c)+b(b+c)=b+ac再來看一個例子()()()()( ()()()ab cbdab cabcab caca bcacacacac bcc aaa cc bcca bccbcabcbc()ab cbdab c內(nèi)容提要o 用布爾代數(shù)的常用公式進(jìn)行布爾表達(dá)式（邏輯表達(dá)式）的化簡o 邏輯表達(dá)式的標(biāo)準(zhǔn)形式邏輯表達(dá)式的標(biāo)準(zhǔn)形式n 最小項和最大項最小項和最大項n 標(biāo)準(zhǔn)積之和標(biāo)準(zhǔn)積之和n 標(biāo)準(zhǔn)和之積標(biāo)準(zhǔn)和之積o 卡諾圖n 用卡諾圖化簡積之和n 用卡諾圖化簡和之積內(nèi)容提要o

3、 用布爾代數(shù)的常用公式進(jìn)行布爾表達(dá)式（邏輯表達(dá)式）的化簡o 邏輯表達(dá)式的標(biāo)準(zhǔn)形式n 最小項和最大項最小項和最大項n 標(biāo)準(zhǔn)積之和與標(biāo)準(zhǔn)和之積n 真值表與標(biāo)準(zhǔn)形式的關(guān)系o 卡諾圖最小項（標(biāo)準(zhǔn)乘積項）o 最小項是包含所有變量（或其反變量）的乘積項乘積項n只有一個輸入組合可以使最小項的值為1n該組合的二進(jìn)制值就是最小項的編號o 例如：對于4變量的邏輯函數(shù)，w、x、y、z四個邏輯變量，有16個最小項nwxyz只有在各個變量分別等于0000時才為1，因此其編號是0，記為m0nwxyz只有在各個變量分別為1111時才為1，因此其編號為(1111)2，即15，記為m15o 簡單的編號方法：原變量取1，反變量取

4、0，即可得到編號n例如：wxyz的編號是(1001)2,因此是m9最大項（標(biāo)準(zhǔn)求和項）o 最大項是包含所有變量（或其反變量）的求和項求和項n只有一個輸入組合可以使最大項的值為0n該組合的二進(jìn)制值就是最大項的編號o 例如：對于4變量的邏輯函數(shù)，w、x、y、z四個邏輯變量，有16個最大項n(w+x+y+z)只有在各個變量分別等于1111時才為0，因此其編號是(1111)2 ，即15，記為m15n(w+x+y+z)只有在各個變量分別為0000時才為0，因此其編號為(0000)2，記為m0o 簡單的編號方法：原變量取0，反變量取1，即可得到編號n例如：w+x+y+z的編號是(0110)2,因此是m6內(nèi)

5、容提要o 用布爾代數(shù)的常用公式進(jìn)行布爾表達(dá)式（邏輯表達(dá)式）的化簡o 邏輯表達(dá)式的標(biāo)準(zhǔn)形式n 最小項和最大項n 標(biāo)準(zhǔn)積之和標(biāo)準(zhǔn)積之和與標(biāo)準(zhǔn)和之積n 真值表與標(biāo)準(zhǔn)形式的關(guān)系o 卡諾圖積之和、和之積o 積之和n sum of product: sopn 一系列乘積的和n 可以用與或門實現(xiàn)o 和之積n product of sum: posn 一系列和的乘積n 可以用或與門實現(xiàn)任意表達(dá)式到積之和表達(dá)式的轉(zhuǎn)換o a(b+cd)=ab+acdo 用到了乘法的分配率n a(b+c) = ab+ac邏輯表達(dá)式的標(biāo)準(zhǔn)積之和形式o 是一個積之和o 每個乘積項均為最小項（一系列最小項之和）abababcabcabc

6、abcabd是積之和，但是不是標(biāo)準(zhǔn)積之和把積之和轉(zhuǎn)化為標(biāo)準(zhǔn)積之和abcabd11abcabd ()()abcddabccdabcdabcdabcdabcd標(biāo)準(zhǔn)積之和的另一種形式o 每個最小項用其名字代替，可以簡化表達(dá)式abcabcabcababm3m0a,b(0,3)m7m1m2a,b.c(1,2,7)內(nèi)容提要o 用布爾代數(shù)的常用公式進(jìn)行布爾表達(dá)式（邏輯表達(dá)式）的化簡o 邏輯表達(dá)式的標(biāo)準(zhǔn)形式n 最小項和最大項n 標(biāo)準(zhǔn)積之和與標(biāo)準(zhǔn)和之積標(biāo)準(zhǔn)和之積n 真值表與標(biāo)準(zhǔn)形式的關(guān)系o 卡諾圖積之和、和之積o 積之和n sum of product: sopn 一系列乘積的和式n 可以用與或門實現(xiàn)o 和之積

7、n product of sum: posn 一系列和的乘積n 可以用或與門實現(xiàn)任意表達(dá)式到和之積表達(dá)式的轉(zhuǎn)換o a(b+cd)=a(b+c)(b+d)o 用到了”加法的分配率”n a+bc = (a+b)(a+c)()abcd abcdababcdcdabcd()()acd bcd()()()()acad bc bd任意表達(dá)式到和之積表達(dá)式的轉(zhuǎn)換()abcd abcdababcdcdabcd()()acd bcd()()()()acad bc bd邏輯表達(dá)式的標(biāo)準(zhǔn)和之積形式o 是一個和之積o 每個求和項均為最大項（一系列最大項之積）()()ab ab()()()abcabcabc()()ab

8、cabd是和之積，但是不是標(biāo)準(zhǔn)和之積把和之積轉(zhuǎn)化為標(biāo)準(zhǔn)和之積()()abcabd(0)(0)abcabd()()abcdd abccd()()()()abcd abcd abcd abcd使用加法的分配律標(biāo)準(zhǔn)和之積的另一種形式o 每個最大項用其名字代替，可以簡化表達(dá)式()()ab ab()()()()abcd abcd abcd abcd03m m,(0,3)a bc011214m m m m, , ,(0,1,12,14)a b c dc內(nèi)容提要o 用布爾代數(shù)的常用公式進(jìn)行布爾表達(dá)式（邏輯表達(dá)式）的化簡o 邏輯表達(dá)式的標(biāo)準(zhǔn)形式n 最小項和最大項n 標(biāo)準(zhǔn)積之和與標(biāo)準(zhǔn)和之積n 真值表與標(biāo)準(zhǔn)形式的

9、關(guān)系真值表與標(biāo)準(zhǔn)形式的關(guān)系o 卡諾圖邏輯表達(dá)式和真值表o 邏輯表達(dá)式真值表abcabcabcinputoutputa b c00 000 101 001 110 010 111 011 111100000邏輯表達(dá)式和真值表o 邏輯表達(dá)式真值表abcabcabcabcinputoutputa b c00 000 101 001 110 010 111 011 110100011邏輯表達(dá)式和真值表o 邏輯表達(dá)式真值表abcabinputoutputa b c00 000 101 001 110 010 111 011 101000011邏輯表達(dá)式和真值表o 邏輯表達(dá)式真值表inputoutputa

10、 b c00 000 101 001 110 010 111 011 111111100()()abcabc邏輯表達(dá)式和真值表o 真值表邏輯表達(dá)式abcinputoutputa b c00 000 101 001 110 010 111 011 110100011abcabcabc+邏輯表達(dá)式和真值表o 真值表邏輯表達(dá)式abcinputoutputa b c00 000 101 001 110 010 111 011 110100011abcabcabc()()()()abcabcabcabc最小項和最大項之間的對偶關(guān)系o 最小項對應(yīng)于真值表中值為1的項，而最大項對應(yīng)于真值表中值為0的項o 如果邏輯函數(shù)標(biāo)準(zhǔn)積之和表達(dá)式中最小項編號的集合是a，最大項編號集合是b，那么|a+b|=2n,其中n是邏輯變量的個數(shù)o 例如：f(w,x,y,z)= w,x,y,z(1,2,3,5,7,11,13)