算法简化布尔表达式
我想简化形式的一个非常大的布尔函数:算法简化布尔表达式
f(a1,a2,....,an)= (a1+a2+a5).(a2+a7+a11+a23+a34)......(a1+a3+an).
“”装置或
“+”装置和
可能有100个这样的术语(“”彼此)的n 值可高达去30.
是否有任何可行算法来简化此?
注意:这不是一个实验室任务,这是我粗略的规则生成规则生成的一小部分,其中f是不相似函数。
典型的方法是使用boolean algebra将语句简化为最简单的形式。
如果,例如,您有类似:
(A AND B) OR (A AND C)
,你可以将其转换为更简单的形式:
A AND (B OR C)
如果你所代表的一个值作为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。在这之上它是混乱。
是啊!我尝试了类似的方法,但最后我得到了一个规则,例如a1 + a2 + .. + ak-> dicision,但是我必须得到a1.a2 .... ak-> dicision的形式,所有的术语和彼此,如何从这里得到它? – sb15
@ sb15不知道你的意思。 for循环创建OR,只要其中一个项匹配其所有位,就立即返回true。实际上:result = a&term [0] == term [0] | a&term [1] == term [1] | ... a&term [m] == term [m] –
众所周知的方法来做到这一点是:
- 如果变量的数量少于5,使用Karnaugh Map Algorithm
- 如果变量的数量为5个以上,使用Quine McCluskey Algorithm
第二种方法是计算机上最常用的方法。它是表格式和直接的。第一种方式是手工操作的最佳方式,并且更有趣,但不能将其用于可靠的超过4个变量。
由于不是所有的语言都使用这种表示法,你能具体说明'.'和'+'运算符是什么吗?我假设OR和AND? –
“简化”是什么意思? –
如果是这种情况,那么“简化”的主要方法是,如果有条款可以在所有或组中拔出。除此之外,您可能可以重组,但我不认为会有大规模的简化。 –