布尔RPN表达式的中止求值

Question

我有一些RPN格式的布尔表达式，如下所示：

{0} {1} {2} AND OR    // equals: {0} or {1} and {2}

计算布尔变量{x}非常昂贵。显然，如果{1}和{2}已经为真，则不需要计算{0}，因为在这种情况下，表达式将始终计算为true。

如何预先检测必须先计算哪些布尔变量才能用尽可能少的变量来中止表达式的计算？

我想知道有一个确定值的变量将计算整个表达式为真还是假。

Answer 1

您应该更喜欢在预期的子表达式计算数较低的情况下计算表达式。

• A和(b或c或d) 你应该先评估一个--如果它是假的--你就完成了
• A或(b、c和d) 同样，您应该首先评估一个--如果是真的--您已经完成了
• (a或b)及(c或d或e) 首先，评估(a或b) --因为如果是假的--你就完成了

等。

执行：

• 构建根为或如果表达式具有"expr或.“形式的树。或者，如果表达式的形式为"expr和.“，则根应该是和。
• 递归地构建子树。水平或树木是和/或交替。子节点或每个节点的数量不同(除叶外)为2个或更多。
• 通过选择子树和最小子树来递归地进行评估，并首先对其进行评估。

Answer 2

算法

一种方法是首先展开布尔表达式，然后分解。

常见的因素将告诉您哪些变量可以强制表达式为false。

然后，您可以反转表达式并重复查找强制表达式为true的变量。

示例1

用一个例子来说明这一点，我会写+表示OR和。用于和：

0 + 1.2

这已经扩大了。没有共同的因素，因此不可能有一个单一的变量可以强制这是真的。

接下来，我们使用德摩根定律进行反转和扩展。

!(0 + 1.2)
= !0.!(1.2)
= !0.(!1 + !2)

这有一个因子为!0，也就是说，如果0是false，我们可以得出整个表达式为false。

示例2

1.2 + 1.3
= 1.(2 + 3)

因此，如果1为false，则整个表达式为false。

!(1.2 + 1.3)
=!(1.2).!(1.3)
=(!1 + !2).(!1 + !3)
=!1 + !2.!1 + !2.!3

这没有公共因素，因此没有一个变量可以强制表达式为true。

Answer 3

将您的表达式转换为最小的乘积和形式。这可以通过对小表达式使用卡诺-维伊奇地图来实现。更多涉及的方法被描述为这里。

​

​

在您的示例中，您得到一个术语--一个(您的{0})和一个带有两个字面值的第二个术语cb ({1}{2} )。对于每个输入变量，计算受此变量影响的术语。

一个简单的统计不会考虑到术语可能是大的(许多文字)或小的(很少的文字)。因此，您可以用相应的单元格所覆盖的卡诺单元格的数量来加权这些术语。

计数结果(a:1x4，b:1x2，c:1x2)告诉您应该首先计算哪个变量。评估结束时，一旦单个项变为真，或将所有项计算为false。