卡諾圖

卡諾圖是一種以圖形化的方式來進行布林代數化簡的表示圖。

由於卡諾圖本身亦記錄布林函數的數值，因此我們也可以視其為一種特別版本的真值表(truth table)。 (因為其變數的排列順序較為特殊)

當我們使用卡諾圖進行布林代數化簡時，需注意每次以2的指數次方擴大，儘可能以較大的方塊將布林值為1的部份給包起來，且不得包涵布林值為0的部份。

---

• 兩個變數的卡諾圖...
  
  • 兩個變數的卡諾圖

    a\b	b = 1	b = 0
    a = 1	11	10
    a = 0	01	00

    注意，藍色區塊內的每一個方格都有兩個位元，第一個位元代表a的數值，第二個位元代表b的數值。
    每個相鄰的區塊都只會相差一個位元，如果相鄰的區塊彼此的數值相同，則表示可以化簡一個布林變數。 (表示有一個變數不會有影響布林函數的結果)
    
  • 兩個布林變數的範例

    a\b	b	b'
    a	1	1
    a'	1	0

    注意，綠色區塊為布林值。
    
    • 第一次選取

      a\b	b	b'
      a	1	1
      a'	1	0

      注意，兩個黃色區塊即為被選定的區塊。
      黃色區塊所代表的函數為 a (因為 b的數值不會影響結果)
      
    • 第二次選取

      a\b	b	b'
      a	1	1
      a'	1	0

      注意，兩個黃色區塊即為被選定的區塊。
      黃色區塊所代表的函數為 b (因為 a的數值不會影響結果)
      
      由以上可知，該布林函數可化簡為 F = a + b

  ---

  
  
• 三個變數的卡諾圖...
  
  • 三個變數的卡諾圖

    a\bc	b=1,c=1	b=1,c=0	b=0,c=0	b=0,c=1
    a = 1	111	110	100	101
    a = 0	011	010	000	001

    注意，藍色區塊內的每一個方格都有三個位元，第一個位元代表a的數值，第二個位元代表b的數值，第三個位元代表c的數值。
    每個相鄰的區塊都只會相差一個位元，如果相鄰的區塊彼此的數值相同，則表示可以化簡一個布林變數。 (表示有一個變數不會有影響布林函數的結果)
    
  • 三個布林變數的範例

    a\bc	b=1,c=1	b=1,c=0	b=0,c=0	b=0,c=1
    a = 1	1	0	1	1
    a = 0	1	0	0	1

    注意，綠色區塊為布林值。
    
    • 第一次選取

      a\bc	b=1,c=1	b=1,c=0	b=0,c=0	b=0,c=1
      a = 1	1	0	1	1
      a = 0	1	0	0	1

      注意，四個黃色區塊即為被選定的區塊。
      ps. 卡諾圖的邊緣仍然是相連接。
      黃色區塊所代表的函數為 c (因為 a 與 b的數值不會影響結果)
      
      理由如下：
      (A) 我們使用 (a,b,c) 來表達literal a, b, c的數值...
      請注意看黃色區塊 (總共有4個1)
      先看左邊的兩個1，這兩個1所表示的minterm分別為 (1,1,1) 與 (0,1,1)
      有沒有發現，不管第一個literal a 是 1 還是 0，布林函數值都是 1。
      所以，a 不管是1還是0，都不會影響。因此，這兩個minterm可以變成 b c
      也就是 a b c + a' b c = b c
      ps. 即，當 b=1且c=1時，布林函數值為1。
      
      同理，我們再看右邊兩個1所表示的minterm分別為 (1,0,1) 與 (0,0,1)
      我們再度發現，不管第一個literal a 是 1 還是 0，布林函數值仍是 1。
      所以，a 不管是1還是0，都不會影響。因此，這兩個minterm可以變成 b' c
      也就是 a b' c + a' b' c = b' c
      ps. 即，當 b=0且c=1時，布林函數值為1。
      
      (B) 在下面的內容，我們使用 (b,c) 來表達literal b, c的數值...
      由(A)，我們可以得到 b c 與 b' c，相當於 (1,1) 與 (0,1)
      我們發現，不管第一個literal (b) 是 1 還是 0，其結果仍然是 1。
      所以，b 不管是1還是0，都不會影響。因此，可以得到 c
      也就是 b c + b' c = c
      ps. 即，c=1時，布林函數值為1。
      
      所以，我們將發現，在這四個1的minterm所組成的方塊中，
      literal a 和 literal b 將不會影響布林函數值。 (因為都是1)
      
      而化簡後的布林函數就是 c
      也就是 a b c + a' b c + a b' c + a' b' c = c
      
    • 第二次選取

      a\bc	b=1,c=1	b=1,c=0	b=0,c=0	b=0,c=1
      a = 1	1	0	1	1
      a = 0	1	0	0	1

      注意，兩個黃色區塊即為被選定的區塊。
      黃色區塊所代表的函數為 a b' (因為 c的數值不會影響結果)
      
      由以上可知，該布林函數可化簡為 F = c + a b'

  ---

  
  
• 四個變數的卡諾圖...
  
• 四個變數的卡諾圖

  ab\cd	c=1,d=1	c=1,d=0	c=0,d=0	c=0,d=1
  a=1,b=1	1111	1110	1100	1101
  a=1,b=0	1011	1010	1000	1001
  a=0,b=0	0011	0010	0000	0001
  a=0,b=1	0111	0110	0100	0101

  注意，藍色區塊內的每一個方格都有四個位元，第一個位元代表a的數值，第二個位元代表b的數值，第三個位元代表c的數值，第四個位元代表d的數值。
  每個相鄰的區塊都只會相差一個位元，如果相鄰的區塊彼此的數值相同，則表示可以化簡一個布林變數。 (表示有一個變數不會有影響布林函數的結果)