算法簡化布爾表達式

Question

我想簡化形式的一個非常大的布爾函數：

f(a1,a2,....,an)= (a1+a2+a5).(a2+a7+a11+a23+a34)......(a1+a3+an). 

「」裝置或

「+」裝置和

可能有100個這樣的術語（「」彼此）的n 值可高達去30.

是否有任何可行算法來簡化此？

注意：這不是一個實驗室任務，這是我粗略的規則生成規則生成的一小部分，其中f是不相似函數。

Answer 1

典型的方法是使用boolean algebra將語句簡化爲最簡單的形式。

如果，例如，您有類似：

(A AND B) OR (A AND C)

，你可以將其轉換爲更簡單的形式：

A AND (B OR C)

Answer 2

如果你所代表的一個值作爲int或long其中a1具有值2，a2具有值4，a3具有值8等：

int a =（a1？ 2^1：0）+（a2 2^2：0）+（a3 2^3：0）+ ...;

（浪費了位保持它的簡單和無視事實，你會與A0更好= 1）

與您所有的條款做同樣的：

long[] terms = ...; 
terms[0] = 2^0 + 2^3 + 2^5   // a1+a2+a5 
terms[1] = 2^2 + 2^7 + 2^23 + 2^34 // (a2+a7+a11+a23+a34) 

然後你就可以找到結果：

foreach(var term in terms) 
{ 
    if (a & term == term) return true; 
} 
return false; 

但這只是非常適用於多達N = 64。在這之上它是混亂。

Answer 3

衆所周知的方法來做到這一點是：

• 如果變量的數量少於5，使用Karnaugh Map Algorithm
• 如果變量的數量爲5個以上，使用Quine McCluskey Algorithm

第二種方法是計算機上最常用的方法。它是表格式和直接的。第一種方式是手工操作的最佳方式，並且更有趣，但不能將其用於可靠的超過4個變量。