如何最小化重複布爾表達式

Question

假設我有一個名爲'foo'的邏輯門的真值表。

a | b | out | 
0 | 0 | 1 | 
0 | 1 | 0 | 
1 | 0 | 0 | 
1 | 1 | 1 | 

這解決以下布爾表達式：

富=（-a^-b）V（A^B）

我們還假設我有以下電路圖用於邏輯門叫'酒吧'。

  -----  ----- 
a -------|  |  |  | 
     | foo |------|  | 
b -------|  |  | foo |------ out 
      -----  |  | 
c --------------------|  | 
         ----- 

這解決以下布爾表達式：

巴=（ - （（ - 一^ -b）V（A^B））^ -c）V（（（-a^- b）v（a^b））^ c）

爲了找到這個結果，我把'foo'的布爾表達式替換爲'a'。

有沒有簡單的算法來簡化這個布爾表達式？它顯然有很多重複，我希望得到一個最小的布爾表達式，最好是CNF或DNF。

在此先感謝。

Answer 1

表達最終的輸出作爲克功能：

f = foo(a,b) = ¬a·¬b + a·b 
g = foo(f,c) = ¬f·¬c + f·c 
g = foo(foo(a,b),c) = ¬(¬a·¬b + a·b)·¬c + (¬a·¬b + a·b)·c 

假設⋅操作者表示二進制結合（∧），則+二進制析取（∨）和 - 或¬一元否定，我將適用的Boolean algebra規律是這樣的：

 ¬(¬a·¬b + a·b)  ·¬c + (¬a·¬b + a·b)·c 
    ¬(¬a·¬b + a·b)  ·¬c + ¬a·¬b·c + a·b·c //distributivity of · over + 
    (¬(¬a·¬b)·¬(a·b))  ·¬c + ¬a·¬b·c + a·b·c //De Morgan's law 
((¬¬a + ¬¬b)·(¬a + ¬b)) ·¬c + ¬a·¬b·c + a·b·c //De Morgan's law 
    ((a + b)·(¬a + ¬b)) ·¬c + ¬a·¬b·c + a·b·c //double negation law 
(a·¬a + a·¬b + b·¬a + b·¬b)·¬c + ¬a·¬b·c + a·b·c //distributivity of · over + 
    (0 + a·¬b + b·¬a + 0) ·¬c + ¬a·¬b·c + a·b·c //complementation: x·¬x = 0 
     (a·¬b + b·¬a)  ·¬c + ¬a·¬b·c + a·b·c //identity for +: 0 + x = x 
      a·¬b·¬c + b·¬a·¬c + ¬a·¬b·c + a·b·c //distributivity of · over + 

      a·¬b·¬c + ¬a·b·¬c + ¬a·¬b·c + a·b·c 

的最後一行是原始表達式的最小DNF。你也可以將它到它的最小CNF這樣：

a·¬b·¬c + ¬a·b·¬c + ¬a·¬b·c + a·b·c 
a·¬b·¬c + a·b·c + ¬a·b·¬c + ¬a·¬b·c   //just permuting 
a·(¬b·¬c + b·c) + ¬a·(b·¬c + ¬b·c)   //distributivity of · over + 

//distributivity of + over ·: 
(a + ¬a)·(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b·¬c + b·c + b·¬c + ¬b·c) 

//complementation: (a + ¬a) = 1 
    (1)·(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·((¬b·¬c + b·c) + (b·¬c + ¬b·c)) 

//identity for ·: 1·x = x 
     (a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b·¬c + b·c + b·¬c + ¬b·c) 

//(¬b·¬c + b·c + b·¬c + ¬b·c) = 1 i.e. sum of all b, c combinations; to be sure: 
(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b·(¬c + c) + b·(¬c + c)) //distribut. 
(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b·(1) + b·(1))  //complementation 
(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b + b)    //identity for · 
(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(1)     //complementation 

(a + (b·¬c + ¬b·c)      )·((¬b·¬c + b·c) + ¬a) //identity for · 
(a + (b + ¬b)·(b + c)·(¬c + ¬b)·(¬c + c))·((¬b·¬c + b·c) + ¬a) //distributivity 
(a +  (1)·(b + c)·(¬c + ¬b)·(1) )·((¬b·¬c + b·c) + ¬a) //complementation 
(a +   (b + c)·(¬c + ¬b)  )·((¬b·¬c + b·c) + ¬a) //identity for · 
       ((a + b + c)·(a + ¬c + ¬b))·((¬b·¬c + b·c) + ¬a) //distributivity 
//distribut.: ((a + b + c)·(a + ¬c + ¬b))·((¬b+b)·(¬b + c)·(¬c + b)·(¬c+c) + ¬a) 
//complem.: ((a + b + c)·(a + ¬c + ¬b))·( (1)·(¬b + c)·(¬c + b)·(1) + ¬a) 
//identity: ((a + b + c)·(a + ¬c + ¬b))·(  (¬b + c)·(¬c + b)  + ¬a) 
//distribut.: ((a + b + c)·(a + ¬c + ¬b))·((¬b + c + ¬a)·(¬c + b + ¬a)) 

       (a + b + c)·(a + ¬b + ¬c)·(¬a + ¬b + c)·(¬a + b + ¬c) 

你的功能可以簡化爲這兩種表達式之一：

g = a·¬b·¬c + ¬a·b·¬c + ¬a·¬b·c + a·b·c //minimal DNF 
g = (a + b + c)·(a + ¬b + ¬c)·(¬a + ¬b + c)·(¬a + b + ¬c) //minimal CNF 

的[任何良好的布爾表達式簡單化者在那裏？]

Answer 2

使用De Morgan's laws，可以進一步簡化爲CNF或DNF。