算法简化布尔表达式

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个变量。