計算機輔助卡諾圖的快速化簡

 引言
利用計算機輔助卡諾圖化簡，使授課方式變得方便、快捷，節(jié)省了教師授課時的板書時間，提高了教學效率，使課堂教學活動變得活潑，生動有趣，富有啟發(fā)性、真實性，可以從根本上改變傳統上單調的教學模式，從而活躍學生的思維，激發(fā)學生的學習興趣。
1 卡諾圖化簡邏輯簡介
1.1 卡諾圖的構成 卡諾圖是一種平面方格圖，每個小方格代表一個最小項，故又稱為最小項方格圖。結構特點：n個變量的卡諾圖由2n個小方格組成，每個小方格代表一個最小項；卡諾圖上處在相鄰、相對、相重位置的小方格所代表的最小項為相鄰最小項。（圖1）
1.2 卡諾圖的性質 卡諾圖的構造特點使卡諾圖具有一個重要性質：可以從圖形上直觀地找出相鄰最小項合并。合并的理論依據是并項定理AB+AB’=A。例如，兩個相鄰最小項可以合并為一個“與”項并消去一個變量。用卡諾圖化簡邏輯函數的基本原理就是把上述邏輯依據和圖形特征結合起來，通過把卡諾圖上表征相鄰最小項的相鄰小方格“圈”在一起進行合并，達到用一個簡單“與”項代替若干最小項的目的。通常把用來包圍那些能由一個簡單“與”項代替的若干最小項的“圈”稱為卡諾圈。
1.3 邏輯函數在卡諾圖上的表示 當邏輯函數為標準“與-或”表達式時，只需在卡諾圖上找出和表達式中最小項對應的小方格填上1，其余小方格填上0，即可得到該函數的卡諾圖。[1]
如函數Y=AB+CD+ACD的卡諾圖如圖2所示。
手工填寫卡諾圖既費時又易出錯，如果在輸入邏輯表達式后，由計算機自動進行邏輯運算，自動填寫卡諾圖既方便又快捷。
2 利用計算機的圖形處理系統繪制卡諾圖
2.1 繪圖前的各種屬性的設置 計算機的圖形操作，都要使用繪圖區(qū)或容器的坐標系統，窗體是一個容器，所有的控件都分布窗體內，每個容器都有一個坐標系，構成一個坐標系，需要三個元素：坐標原點、坐標度量單位、坐標軸的長度與方向。在VB中，當新建一個窗體時，新窗體采用默認坐標系，坐標原點在窗體的左上角，橫向向右為X軸的正方向，縱向向下為Y軸的正向，單位為twip。為了符合日常的繪圖習慣，我們可以使用屏幕的SCALE方法將坐標的原點設置在屏幕的左下角，橫向向右為X軸的正方向，縱向向上為Y軸的正方向。并利用窗體的SCALEMODE屬性將坐標單位改為毫米。設置好畫圖的線條粗細和顏色。[2]
2.2 繪圖 繪圖時輸入變量的個數及卡諾圖的大小。計算機便依據變量個數分別動態(tài)繪出三變量、四變量，或五變量卡諾圖。精確繪圖必須熟悉對坐標的計算。
3 邏輯表達式的輸入，譯碼及運算
當輸入邏輯表達式時，原變量照寫，反變量在字母后加單引號，如Y=AB’+BC’+B’C+A’B，或者是輸入函數包含最小項的形式，如Y=∑（3，2，4，5，7，6，12，13，8，9，10，11）。用一個文本框接收邏輯表達式AB’+BC’+B’C+A’B后，以“+”為界將其分解為若干個“與”項。再將每個“與”項中的反變量先進行非運算（NOT），然后進行“與”（AND）運算，最后將四個“與”項運算的結果進行“或”（OR）運算。在運算前按照變量在卡諾圖上的分布分別給變量賦值：讓A=&H00FF，B=&H0FF0，C=&H3333，D=&H6666（按十六進制書寫）。因為變量A在四變量卡諾圖最上面兩行為（0000，00000），最下面兩行為（1111，1111），故賦值A=&H00FF。
4 卡諾圖的填寫
上述邏輯運算的結果為十進制數，將其轉化為二進制數后，依次賦給動態(tài)產生的十六個文本框。然后將十六個文本框依次移動到卡諾圖對應的位置上，并在卡諾圖上每個方格的右下角標上最小項的編號。如圖2所示。
5 畫卡諾圈，合并最小項，生成最簡“與-或”表達式[3]
卡諾圖具有循環(huán)鄰接的特性，即相鄰的兩個最小項只有一個變量不同。若圖中兩個相鄰的小方格均為1，則這兩個相鄰的最小項的和將消去一個變量；若卡諾圖中四個相鄰的方格為1，則這四個相鄰的最小項的和將消去二個變量；八個相鄰的最小項合并時可消去三個變量；利用卡諾圖化簡邏輯函數常用的方法是“圈1法”。用“圈1法”畫包圍圈的原則如下：①圈的個數應最少，圈內的小方格個數應盡可能的多。②將值為“1”的相鄰方格圈成矩形或方形。③所圈取值為1的相鄰小方格的個數應為1，2，4，8，其它形式是非法形式。④畫包圍圈時，每個取值為1的方格可以被重復包圍，但每個包圍圈都要有新的方格，同時不能漏去任何一項。
當輸入一個卡諾圈所包含的最小項，如（3，2，7，6）時，由計算機自動生成最簡與或表達式的算法如下：
①將上述包含的最小項輸入給一個文本框，利用Q=SPLIT（TEXT1，”，”）語句將各個最小項分別賦值給一個動態(tài)數組Q，并按升序排列，這里Q（0）=2為四個最小項的最小值。然后根據Q（0）的值寫出代表的最小項，如：Q（0）=0，則STR1=“A’B’C’D’”，Q（0）=1、則STR1=“A’B’C’D”，這里的Q（0）=2所以STR1=“A’B’CD’”。
②依次求Q（1），Q（2），Q（3）與Q（0）的差值，凡是差值為2N（即1，2，4，8）時，執(zhí)行3，否則執(zhí)行4。
③依據差值消去相應的變量：當差值為8時、則消去STR1中的變量A，當差值為4時、消去STR1中的變量B， 當差值為2時消去STR1中的變量C，當差值為1時、消去STR1中的變量D，例Q（1）-Q（0）=3-2=1，則消去STR1中的變量D，這里的Q（2）-Q（0）=6-2=4，則消去STR1中的變量B，所以最初STR1=“A’BCD”，則變?yōu)镾TR1=“A’C”。即A’C含概了最小項（3，2，7，6）。
④將上述生成的最簡與項用加號“+”連接起來，就是最簡“與-或”表達式。圖3為輸入函數Y=AB’+BC’+B’C+A’B后的運行結果。
結論：應用VB編程，由計算機繪制卡諾圖，對邏輯表達式的自動譯碼、運算、卡諾圖的自動填寫、最后生成最簡“與-或”表達式。實現了邏輯函數化簡的高效性。