如何最小化重复布尔表达式

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。