简化布尔表达式的算法

Question

我希望简化一个非常庞大的布尔函数，形式如下：

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

'.'表示或

'+'表示且

可能会有100个这样的术语（它们之间带有'.'）n的值可能高达30。

是否有可行的算法来简化这个问题？

注意：这不是实验任务，而是我在粗糙集合生成规则项目中的一个小部分，其中f是不相似函数。

- sb15

---

由于并非所有语言都使用该符号表示法，你能具体说明“.”和“+”运算符分别代表什么吗？我猜是“或”和“与”吧？ - D Stanley

“简化”是什么意思？ - Tamas Ionut

如果是这种情况，那么“简化”的主要方法就是将所有或组中可以提取的术语提取出来。除此之外，您可能可以重新组织，但我认为不会有大规模的简化。 - D Stanley

通过简化函数f，我们最多可以生成一个形式为ai.aj.ak.al-> decision的规则，其中ai，aj等是条件属性。 - sb15

你有没有考虑将所有位放入一个int（或long）中，然后执行f = a&19 == 19 | a&c == c | ...其中&是按位&，|是正常的或（具有早期终止）？更简单的是每个术语都很小。 - Ian Mercer

Answer 1

常见的实现方式有：

• 如果变量少于5个，请使用卡诺图算法
• 如果变量数大于等于5个，请使用Quine McCluskey算法

在计算机上，第二种方法是最常用的。它表格化且易于理解。第一种方式适合手工计算并具有趣味性，但是可靠地处理超过4个变量的计算可能较为困难。

- user1952500

Answer 2

如果您将a值表示为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。超过这个数字就会变得混乱。

- Ian Mercer

---

是的！我尝试了类似的方法，但最终得到的规则是a1+a2+..+ak->决策，但我必须得到形式为a1.a2....ak->决策，所有术语都要彼此AND，从这里怎么做呢？ - sb15

@sb15 不确定你的意思。for循环创建OR，一旦其中一个术语匹配其所有位，就会返回true。实际上：result = a&term[0] == term[0] | a&term[1] == term[1] | ... a&term[m] == term[m] - Ian Mercer

Answer 3

典型的方法是使用布尔代数将语句简化为最简形式。

例如，如果您有以下内容：

(A AND B) OR (A AND C)

您可以将其转换为更简单的形式：

A AND (B OR C)

- Chris