查找可能的布尔值来评估表达式为真

Question

如果我有一个给定的布尔表达式（AND和OR操作）与许多布尔变量，那么我想评估这个表达式为真，我怎么能找到所有可能的集合布尔值来实现真正的epxression？

例如，我有4个布尔变量a，b，c，d和表达式：

(a^b) v (c^d) 

我试图做的最慢的方法是：

• 我建立一个表达式树来获取表达式中的所有变量，我得到一个{a,b,c,d}集合。
• 我找到该集合的所有子集：{a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}
• 对于每个子集，我将每个变量设置为true，然后评估表达式。如果表达式返回true，那么我使用这些值保存子集。

编辑：我消除NOT操作使问题更简单。

Answer 1

我想我看到了一种计算方法，无需尝试所有的排列组合，而我的高级轮廓描述如下，并不是很复杂。我将概述的基本方法，你将有两个后续任务做你自己：

• 解析逻辑表达式，如“A & &（B || C）”成经典解析树，表示表达式，树中的每个节点是变量还是布尔操作，或者是“& &”，“||”或“！” （不），有两个孩子是它的操作数。这是一个经典的分析树。谷歌可以找到很多关于如何做到这一点的例子。

• 将我的大纲翻译成实际的C++代码。这也将取决于你，但是我认为，一旦你围绕整体方法进行思考，实施应该是相当明显的。

要解决此问题，我将使用两阶段方法。

1. 我会用proof by induction的一般方法，以拿出所有这些布尔表达式会true的变量值的所有潜在组初步清单。

2. 在第二阶段，我将从所有潜在集的列表中排除那些逻辑上不可能的集合。这听起来可能令人困惑，所以我会先解释第二个阶段。

让我们使用下面的数据类型。首先，我将使用可能值这个数据类型，其布尔表达式会要么true或false：

typedef std::set<std::pair<std::string, bool>> values_t; 

这里，std::pair<std::string, bool>代表变量，其名称为std::string，有这个bool值。例如：

{"a", true} 

指该变量的值“a”具有true值。由此可见，这个std::set表示一组变量及其相应的值。

所有这些可能的解决方案将是一个：

typedef std::list<values_t> all_values_t; 

所以这是我们如何将代表所有变量的值的所有组合，产生两种true或false的结果列表。您可以使用std::vector而不是std::list，这并不重要。

现在请注意，这是可能的values_t有两种：

{"a", true} 

和

{"a", false} 

在集合

。这意味着为了使表达式评估为true或false，“a”必须同时为真和假。

但是，显然这在逻辑上是不可能的。因此，在此解决方案的阶段2中，您需要简单地遍历all_values_t中的所有个人values_t，然后删除包含true和false的“不可能的”values_t以用于某些变量。做这件事的方式应该看起来很明显，我不会浪费时间来描述它，但是第一阶段完成后，第二阶段应该是直截了当的。

对于第一阶段我们的目标是要拿出那个版大约声明如下功能：

all_values_t phase1(expression_t expr, bool goal); 

expr是你的布尔表达式解析后的表示，作为解析树（正如我在开头提到的，做这部分将取决于你）。 goal是您希望如何评估解析的表达式：phase1()返回所有可能的all_values_t，其中expr的计算结果为true或false，如“目标”所示。很显然，你会打电话phase1()为你的答案传递true作为“目标”，因为这就是你想要弄清楚的。但是phase1()会以递归方式调用自己，无论是true还是false“目标”，都会发挥它的魔力。

在继续之前，阅读并理解描述如何通过归纳证明工作的各种资源非常重要。除非你完全理解这个一般概念，否则不要继续下去。

好吧，现在你明白了这个概念。如果你这样做，那么你现在必须同意我的观点，phase1()已经完成。有用！通过归纳证明，首先假定phase1()做它应该做的事情。 phase1()会对自己进行递归调用，并且由于phase1()返回正确的结果，因此phase1()可以简单地依靠自己来确定所有事情。看看这是多么容易？

phase1()真的手头有一个“简单”的任务：

• 检查什么语法树的顶级节点。它将是一个变量节点或一个表达式节点（见上文）。

• 根据此返回适当的all_values_t。

就是这样。我们将同时采取两种可能性。

1. 顶层节点是一个变量。

所以，如果你的表现仅仅是一个变量，你想表达返回goal，则：

values_t v{ {name, goal} }; 

只有一种可能的方式表达，以评估goal：一个明显的不-brainer：变量，goal的值。

只有一种可能的解决方案。没有其他替代方案：现在

all_values_t res; 

res.push_back(v); 

return res; 

，另一种可能性是，在表达顶级节点是布尔操作之一：与，或，还是不行。

再次，我们将分而治之，并逐一解决每一个问题。

让我们说这是“不”。我们应该怎么做？这应该是很容易：

return phase1(child1, !goal); 

就叫phase1()递归，传递了“不”表达的子节点，goal逻辑反向。因此，如果您的goal为真，请使用phase1()返回“not”子表达式的值为false，反之亦然。请记住，通过归纳证明假设phase1()按照广告方式工作，因此您可以依靠它来获得子表达式的正确答案。

它现在应该开始变得明显如何phase1()的其余部分工作。剩下的只有两种可能性：“和”和“或”逻辑运算。

对于“和”操作，我们将分别考虑“和”操作的“目标”是否应为true或false。

如果goal是真实的，你必须使用phase1()拿出all_values_t两个子表达式为真：

all_values_t left_result=phase1(child1, true); 

all_values_t right_result=phase1(child2, true); 

然后，只需两个结果结合起来。现在回想一下，all_values_t是所有的列表可能的值。 all_values_t中的每个值（可以是空列表/矢量）代表一种可能的解决方案。左边和右边的子表达式必须在逻辑上组合，但left_result的任何可能的解决方案都可以与任何right_result一起使用。左子表达式为真的任何可能的解决方案都可以（并且必须）与任何可能的解决方案一起使用，正确的子表达式是正确的。

因此，需要返回的all_values_t，在这种情况下，通过在left_result和right_result之间执行cartesian product来获得。即：取第一个值，第一个values_tstd::set中的left_result，然后加上这个集合的第一个right_resultstd::set，然后第一个left_result与第二个right_result，依此类推;然后第二个left_result与第一个right_result，然后第二个right_result等。这些组合中的每一个都将push_back()编入all_values_t，该编号从此调用返回到phase1（）。

但是你的goal是让“和”表​​达式返回false，相反，你只需要对这三次进行变化。第一次通过与phase1(child2, false)联系;然后phase1(child1, true)与phase1(child2, false);最后是phase1(child1, false)和phase1(child2, true)。 child1或child2或两者都必须评估为false。

因此，照顾“和”的操作。

最后一个和phase1()处理的最终可能性是逻辑或操作。你应该是可以的，现在，找出如何自己做，但我只是简单地总结一下：

如果goal是假的，你必须调用phase1(child1, false)与phase1(child2, false)，那么这两个结果结合在一起，作为一个笛卡尔积。如果goal为真，您将针对其他三种可能性进行三组递归调用，并将所有内容组合在一起。

你完成了。 phase1()没有别的可做的事情，我们通过归纳完成了我们的证明。

嗯，我撒了一点点。你还需要做一个小小的“阶段3”。回想一下，在“阶段2”中，我们排除了所有不可能的解决方案那么可能的是，由于所有这些，可能的解决方案的最终列表将具有相同的values_t在all_values_t中出现多次，所以您只需要重复它即可。

P.S.作为第一阶段的一部分，也可以通过动态地执行第二阶段来避免第二阶段。这种变化也将成为您的家庭作业。