Karnaugh map

卡諾圖中所有取值為1的方格均要被圈過,即不能漏下取值為1的最小項。 (3)卡諾圈中的2m個小方格對應的最小項可用(n 顯然,在函式卡諾圖中,任何一個1方格所對應的最小項或者卡諾圈中的2m個1方格所對應的“與”項都是函式的蘊涵項。

卡諾圖是邏輯函式的一種圖形表示。一個邏輯函式的卡諾圖就是將此函式的最小項表達式中的各最小項相應地填入一個方格圖內,此方格圖稱為卡諾圖。
卡諾圖的構造特點使卡諾圖具有一個重要性質:可以從圖形上直觀地找出相鄰最小項。兩個相鄰最小項可以合併為一個與項並消去一個變數。
用卡諾圖化簡邏輯函式的基本原理就是把上述邏輯依據和圖形特徵結合起來,通過把卡諾圖上表征相鄰最小項的相鄰小方格“圈”在一起進行合併,達到用一個簡單“與”項代替若乾最小項的目的。
在數字電路中經常使用。
缺點:當變數的數目超過6時.畫圖就變得複雜了,也不容易計算.........
用卡諾圖簡化邏輯函式
邏輯函式未用最小項表示照樣可以化簡。如果F採用與—或表達式,在填入卡諾圖過程中就能把函式展開成最小項。
具有無關項的化簡
無關項又叫任意項,是一種最小項,其值可以取0或1。利用無關項這一特點,可以使函式簡化。
用卡諾圖化簡邏輯函式的步驟
如果表達式為最小項表達式,則可直接填入卡諾圖
如表達式不是最小項表達式,但是“與—或表達式”,可將其先化成最小項表達式,再填入卡諾圖。也可直接填入。
合併相鄰的最小項,即根據下述原則畫圈
儘量畫大圈,但每個圈內只能含有2n(n=0,1,2,3……)個相鄰項。要特別注意對邊相鄰性和四角相鄰性。
圈的個數儘量少。
卡諾圖中所有取值為1的方格均要被圈過,即不能漏下取值為1的最小項。
在新畫的包圍圈中至少要含有1個末被圈過的1方格,否則該包圍圈是多餘的。
寫出化簡後的表達式。每一個圈寫一個最簡與項,規則是,取值為1的變數用原變數表示,取值為0的變數用反變數表示,將這些變數相與。然後將所有與項進行邏輯加,即得最簡與—或表達式。
在進行化簡時,如果用圖中真值為0的項更方便,可以用他們來處理,方法和真值取1時一樣,只是結果要再做一次求反。
卡 諾 圖 化 簡 法
一 卡諾圖的構成
卡諾圖是一種平面方格圖,每個小方格代表一個最小項,故又稱為最小項方格圖。
1.結構特點
卡諾圖中最小項的排列方案不是唯一的,變數的坐標值0表示相應變數的反變數,1表示相應變數的原變數。各小方格依變數順序取坐標值,所得二進制數對應的十進制數即相應最小項的下標i。
在五變數卡諾圖中,為了方便省略了符號“m”,直接標出m的下標i 。
歸納起來,卡諾圖在構造上具有以下兩個特點:
☆ n個變數的卡諾圖由2n個小方格組成,每個小方格代表一個最小項;
☆ 卡諾圖上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。
二 卡諾圖的性質
卡諾圖的構造特點使卡諾圖具有一個重要性質:可以從圖形上直觀地找出相鄰最小項合併。合併的理論依據是並項定理AB+AB=A。例如,
根據定理AB+AB=A和相鄰最小項的定義,兩個相鄰最小項可以合併為一個與項並消去一個變數。例如,4變數最小項ABCD和ABCD相鄰,可以合併為ABD;ABCD和ABCD相鄰,可以合併為ABD;而與項ABD和ABD又為相鄰與項,故按同樣道理可進一步將兩個相鄰與項合併為BD。
用卡諾圖化簡邏輯函式的基本原理就是把上述邏輯依據和圖形特徵結合起來,通過把卡諾圖上表征相鄰最小項的相鄰小方格“圈”在一起進行合併,達到用一個簡單“與”項代替若干最小項的目的。
通常把用來包圍那些能由一個簡單“與”項代替的若干最小項的“圈”稱為卡諾圈。
三 邏輯函式在卡諾圖上的表示
1.給定邏輯函式為標準“與-或”表達式
當邏輯函式為標準“與-或”表達式時,只需在卡諾圖上找出和表達式中最小項對應的小方格填上1,其餘小方格填上0,即可得到該函式的卡諾圖。
2.邏輯函式為一般“與-或”表達式
當邏輯函式為一般“與-或”表達式時,可根據“與”的公共性和“或”的疊加性作出相應卡諾圖。
填寫該函式卡諾圖時,只需在4變數卡諾圖上依次找出和“與項”AB、CD、A·BC對應的小方格填上1,便可得到該函式的卡諾圖。
當邏輯函式表達式為其他形式時,可將其變換成上述形式後再作卡諾圖。
為了敘述的方便,通常將卡諾圖上填1的小方格稱為1方格,填0的小方格稱為0方格。0方格有時用空格表示。
四 卡諾圖上最小項的合併規律
卡諾圖的一個重要特徵是,它從圖形上直觀、清晰地反映了最小項的相鄰關係。
2.四個小方格組成一個大方格、或組成一行(列)、或處於相鄰兩行(列)的兩端、或處於四角時,所的表的最小項可以合併,合併後可消去兩個變數。
3.八個小方格組成一個大方格、或組成相鄰的兩行(列)、或處於兩個邊行(列)時,所代表的最小項可以合併,合併後可消去三個變數。
至此,以3、4變數卡諾圖為例,討論了2,4,8個最小項的合併方法。依此類推,不難得出n個變數卡諾圖中最小項的合併規律。
歸納起來,n個變數卡諾圖中最小項的合併規律如下:
(1)卡諾圈中小方格的個數必須為2m個,m為小於或等於n的整數。
(2)卡諾圈中的2m個小方格有一定的排列規律,具體地說,它們含有m個不同變數,(n-m)個相同變數。
(3)卡諾圈中的2m個小方格對應的最小項可用(n-m)個變數的“與”項表示,該“與”項由這些最小項中的相同變數構成。
(4)當m=n時,卡諾圈包圍了整個卡諾圖,可用1表示,即n個變數的全部最小項之和為1。
五、卡諾圖化簡邏輯函式
1.幾個定義
蘊涵項:在函式的“與-或”表達式中,每個“與”項被稱為該函式的蘊涵項(Implicant)。
顯然,在函式卡諾圖中,任何一個1方格所對應的最小項或者卡諾圈中的2m個1方格所對應的“與”項都是函式的蘊涵項。
質蘊涵項:若函式的一個蘊涵項不是該函式中其他蘊涵項的子集,則此蘊涵項稱為質蘊涵項(Prime Implicant),簡稱為質項。
顯然,在函式卡諾圖中,按照最小項合併規律,如果某個卡諾圈不可能被其他更大的卡諾圈包含,那么,該卡諾圈所對應的“與”項為質蘊涵項。
必要質蘊涵項:若函式的一個質蘊涵項包含有不被函式的其他任何質蘊涵項所包含的最小項,則此質蘊涵項被稱為必要質蘊涵項(Essential Prime Implicant),簡稱為必要質項。
在函式卡諾圖中,若某個卡諾圈包含了不可能被任何其他卡諾圈包含的1方格,那么,該卡諾圈所對應的“與”項為必要質蘊涵項。
2.求函式最簡“與-或”表達式
(1)一般步驟: 第一步:作出函式的卡諾圖。
第二步:在卡諾圖上圈出函式的全部質蘊涵項。按照卡諾圖上最小項的合併規律,對函式F卡諾圖中的1方格畫卡諾圈。為了圈出全部質蘊涵項,畫卡諾圈時在滿足合併規律的前題下應儘可能大,若卡諾圈不可能被更大的卡諾圈包圍,則對應的“與”項為質蘊涵項。
第三步:從全部質蘊涵項中找出所有必要質蘊涵項。在卡諾圖上只被一個卡諾圈包圍的最小項被稱為必要最小項,包含必要最小項的質蘊涵項即必要質蘊涵項。為了保證所得結果無一遺漏地覆蓋函式的所有最小項,函式表達式中必須包含所有必要質蘊涵項。
第四步:求出函式的最簡質蘊涵項集。若函式的所有必要質蘊涵項尚不能覆蓋卡諾圖上的所有1方格,則從剩餘質蘊涵項中找出最簡的所需質蘊涵項,使它和必要質蘊涵項一起構成函式的最小覆蓋。
歸納起來,卡諾圖化簡的原則是:
☆ 在覆蓋函式中的所有最小項的前提下,卡諾圈的個數達到最少。
☆ 在滿足合併規律的前題下卡諾圈應儘可能大。
☆ 根據合併的需要,每個最小項可以被多個卡諾圈包圍。
3.求函式的最簡“或-與”表達式
當需要求一個函式的最簡“或-與”表達式時,可採用“兩次取反法”。
具體如下:
☆ 先求出函式F的反函式F的最簡“與-或”表達(合併卡諾圖上的0方格);
☆ 然後對F的最簡“與-或”表達式取反,從而得到函式F的最簡“或-與”表達式。
卡諾圖化簡邏輯函式具有方便、直觀、容易掌握等優點。但依然帶有試湊性。尤其當變數個數大於6時,畫圖以及對圖形的識別都變得相當複雜。

相關詞條

熱門詞條

聯絡我們