查找可能的布尔值以将表达式评估为真
Find possible boolean values to evaluate an expression to true
如果我有一个给定的布尔表达式（AND 和 OR 操作）和许多布尔变量，然后我想将这个表达式计算为真，我怎样才能找到所有可能的集合布尔值来实现真正的表达？
例如，我有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，然后计算表达式。如果表达式 returns 为真，我将使用这些值保存子集。
编辑： 我删除了 NOT 运算符以使问题更简单。
我想我找到了一种无需尝试所有排列即可进行计算的方法，而且我的高级大纲（如下所述）并不是真的很复杂。我将概述基本方法，您将有两个 follow-up 任务需要自己完成：
将一个逻辑表达式，如 "A && (B || C)" 解析成一个经典的解析树，表示表达式，树中的每个节点要么是一个变量，要么是一个布尔运算，要么是“ &&”、“||”或“！” （NOT），两个 children 是它的操作数。这是一个经典的解析树。在 Google.
将我的大纲翻译成实际的 C++ 代码。这也将取决于您，但我认为一旦您对整个方法全神贯注，实施应该是相当明显的。
为了解决这个问题，我将使用 two-phase 方法。
我将使用 proof by induction 的一般方法来得出布尔表达式将计算为 [ 的所有变量的所有潜在值集的暂定列表=20=].
在第二阶段，我将从所有潜在集合列表中删除那些逻辑上不可能的集合。这可能听起来令人困惑，所以我先解释一下第二阶段。
让我们使用以下数据类型。首先，我将使用这种可能值的数据类型，布尔表达式的计算结果为 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，并删除包含两个 [=20] 的 "impossible" values_t =] 和 false 用于一些变量。这样做的方法应该很明显，我不会浪费时间来描述它，但是阶段 2 应该很简单，一旦阶段 1 完成。
对于第 1 阶段，我们的目标是提出一个大致如下声明的函数：
all_values_t phase1(expression_t expr, bool goal);
expr 是布尔表达式的解析表示，作为解析树（正如我在开头提到的，这部分由您决定）。 goal 是您希望将已解析的表达式计算为的方式：phase1() returns all possible all_values_t which expr evaluates to either true或 false，如 "goal" 所示。显然，您会调用 phase1() 传递 true 以获得 "goal" 作为您的答案，因为这就是您想要弄清楚的。但是 phase1() 会递归地调用自己，使用 true 或 false "goal" 来发挥它的魔力。
在继续之前，现在重要的是阅读和理解描述归纳证明如何工作的各种资源。在您完全理解这个一般概念之前，不要继续进行下去。
好了，现在你明白这个概念了。如果你这样做，那么你现在必须同意我的观点，phase1() 已经完成了。有用！归纳证明首先假设 phase1() 做了它应该做的事情。 phase1() 将对自身进行递归调用，并且由于 phase1() return 是正确的结果，phase1() 可以简单地依靠自身来解决所有问题。看看这有多简单？
phase1() 确实有一项 "simple" 任务在手：
检查解析树的顶级节点是什么。它将是变量节点或表达式节点（见上文）。
Return 合适的all_values_t，基于那个。
就是这样。我们将同时考虑两种可能性。
- 顶级节点是一个变量。
因此，如果您的表达式只是一个变量，并且您希望表达式为 return goal，那么：
values_t v{ {name, goal} };
表达式的计算结果只有一种可能的方式 goal：一个明显的 no-brainer：变量，以及 goal 的值。
而且只有一种可能的解决方案。没有其他选择：
all_values_t res;
res.push_back(v);
return res;
现在，另一种可能性是表达式中的 top-level 节点是 boo 之一EAN 操作：与、或、或非。
同样，我们将分而治之，一次解决一个问题。
假设它是"not"。那怎么办呢？那应该很容易：
return phase1(child1, !goal);
只需递归调用phase1()，传递"not"表达式的child节点，goal逻辑反转。因此，如果您的 goal 为真，请使用 phase1() 返回 "not" sub-expression 为假和 vice-versa 的值。请记住，归纳证明假设 phase1() 像宣传的那样工作，因此您可以依靠它来获得 sub-expression.
的正确答案
phase1() 其余部分的工作原理现在应该开始变得显而易见了。只剩下两种可能性："and"和"or"逻辑运算。
对于"and"操作，我们会分别考虑"and"操作的"goal"应该是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 中的每个值（可以为空 list/vector）代表一种可能的解决方案。左右 sub-expression 都必须在逻辑上组合，但是 left_result 中的任何可能解决方案都可以与任何 right_result 一起使用。左子表达式为真的任何潜在解决方案都可以（而且必须）与右子表达式为真的任何潜在解决方案一起使用。
所以需要return编辑的all_values_t，在这种情况下，是通过在left_result和[=76=之间做一个cartesian product得到的].即：取第一个值，left_result 中的第一个 values_t std::set，然后将第一个 right_result std::set 添加到此集合，然后是第一个 left_result 与第二个 right_result，依此类推；然后是第二个 left_result 和第一个 right_result，然后是第二个 right_result，依此类推。这些组合中的每一个都被 push_back()ed 到 all_values_t 中，all_values_t 从对 phase1() 的调用中得到 returned。
但是您的 goal 是要有 "and" 表达式 return false，相反，您只需将其变体 3 次即可。第一次用phase1(child2, false)调用phase1(child1, false)；然后 phase1(child1, true) 和 phase1(child2, false)；最后 phase1(child1, false) 和 phase1(child2, true)。 child1 或 child2，或两者的计算结果必须为 false。
这样就完成了 "and" 操作。
最后，也是最后一种phase1()可能要处理的是逻辑或操作。你现在应该可以自己弄清楚如何做，但我只是简单地总结一下：
如果 goal 为假，您必须用 phase1(child2, false) 调用 phase1(child1, false)，然后将两个结果组合在一起，作为笛卡尔积。如果 goal 为真，您将针对其他三种可能性进行三组递归调用，并将所有内容组合在一起。
大功告成。 phase1()没有别的事可做，我们通过归纳法完成了证明。
好吧，我撒了点小谎。您还需要做一个小 "Phase 3"。回想一下，在 "Phase 2" 中我们排除了所有不可能的解决方案。好吧，作为所有这些的结果，可能的解决方案的最终列表将有相同的 values_t 在 all_values_t 中出现不止一次，所以你只需要重复数据删除它。
P.S。作为第 1 阶段的一部分，也可以通过即时进行来避免离散的第 2 阶段。这种变化也将成为您的家庭作业。
如果我有一个给定的布尔表达式（AND 和 OR 操作）和许多布尔变量，然后我想将这个表达式计算为真，我怎样才能找到所有可能的集合布尔值来实现真正的表达？
例如，我有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，然后计算表达式。如果表达式 returns 为真，我将使用这些值保存子集。
编辑： 我删除了 NOT 运算符以使问题更简单。
我想我找到了一种无需尝试所有排列即可进行计算的方法，而且我的高级大纲（如下所述）并不是真的很复杂。我将概述基本方法，您将有两个 follow-up 任务需要自己完成：
将一个逻辑表达式，如 "A && (B || C)" 解析成一个经典的解析树，表示表达式，树中的每个节点要么是一个变量，要么是一个布尔运算，要么是“ &&”、“||”或“！” （NOT），两个 children 是它的操作数。这是一个经典的解析树。在 Google.
中可以找到大量有关如何执行此操作的示例
将我的大纲翻译成实际的 C++ 代码。这也将取决于您，但我认为一旦您对整个方法全神贯注，实施应该是相当明显的。
为了解决这个问题，我将使用 two-phase 方法。
我将使用 proof by induction 的一般方法来得出布尔表达式将计算为 [ 的所有变量的所有潜在值集的暂定列表=20=].
在第二阶段，我将从所有潜在集合列表中删除那些逻辑上不可能的集合。这可能听起来令人困惑，所以我先解释一下第二阶段。
让我们使用以下数据类型。首先，我将使用这种可能值的数据类型，布尔表达式的计算结果为 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，并删除包含两个 [=20] 的 "impossible" values_t =] 和 false 用于一些变量。这样做的方法应该很明显，我不会浪费时间来描述它，但是阶段 2 应该很简单，一旦阶段 1 完成。
对于第 1 阶段，我们的目标是提出一个大致如下声明的函数：
all_values_t phase1(expression_t expr, bool goal);
expr 是布尔表达式的解析表示，作为解析树（正如我在开头提到的，这部分由您决定）。 goal 是您希望将已解析的表达式计算为的方式：phase1() returns all possible all_values_t which expr evaluates to either true或 false，如 "goal" 所示。显然，您会调用 phase1() 传递 true 以获得 "goal" 作为您的答案，因为这就是您想要弄清楚的。但是 phase1() 会递归地调用自己，使用 true 或 false "goal" 来发挥它的魔力。
在继续之前，现在重要的是阅读和理解描述归纳证明如何工作的各种资源。在您完全理解这个一般概念之前，不要继续进行下去。
好了，现在你明白这个概念了。如果你这样做，那么你现在必须同意我的观点，phase1() 已经完成了。有用！归纳证明首先假设 phase1() 做了它应该做的事情。 phase1() 将对自身进行递归调用，并且由于 phase1() return 是正确的结果，phase1() 可以简单地依靠自身来解决所有问题。看看这有多简单？
phase1() 确实有一项 "simple" 任务在手：
检查解析树的顶级节点是什么。它将是变量节点或表达式节点（见上文）。
Return 合适的
all_values_t，基于那个。
就是这样。我们将同时考虑两种可能性。
- 顶级节点是一个变量。
因此，如果您的表达式只是一个变量，并且您希望表达式为 return goal，那么：
values_t v{ {name, goal} };
表达式的计算结果只有一种可能的方式 goal：一个明显的 no-brainer：变量，以及 goal 的值。
而且只有一种可能的解决方案。没有其他选择：
all_values_t res;
res.push_back(v);
return res;
现在，另一种可能性是表达式中的 top-level 节点是 boo 之一EAN 操作：与、或、或非。
同样，我们将分而治之，一次解决一个问题。
假设它是"not"。那怎么办呢？那应该很容易：
return phase1(child1, !goal);
只需递归调用phase1()，传递"not"表达式的child节点，goal逻辑反转。因此，如果您的 goal 为真，请使用 phase1() 返回 "not" sub-expression 为假和 vice-versa 的值。请记住，归纳证明假设 phase1() 像宣传的那样工作，因此您可以依靠它来获得 sub-expression.
phase1() 其余部分的工作原理现在应该开始变得显而易见了。只剩下两种可能性："and"和"or"逻辑运算。
对于"and"操作，我们会分别考虑"and"操作的"goal"应该是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 中的每个值（可以为空 list/vector）代表一种可能的解决方案。左右 sub-expression 都必须在逻辑上组合，但是 left_result 中的任何可能解决方案都可以与任何 right_result 一起使用。左子表达式为真的任何潜在解决方案都可以（而且必须）与右子表达式为真的任何潜在解决方案一起使用。
所以需要return编辑的all_values_t，在这种情况下，是通过在left_result和[=76=之间做一个cartesian product得到的].即：取第一个值，left_result 中的第一个 values_t std::set，然后将第一个 right_result std::set 添加到此集合，然后是第一个 left_result 与第二个 right_result，依此类推；然后是第二个 left_result 和第一个 right_result，然后是第二个 right_result，依此类推。这些组合中的每一个都被 push_back()ed 到 all_values_t 中，all_values_t 从对 phase1() 的调用中得到 returned。
但是您的 goal 是要有 "and" 表达式 return false，相反，您只需将其变体 3 次即可。第一次用phase1(child2, false)调用phase1(child1, false)；然后 phase1(child1, true) 和 phase1(child2, false)；最后 phase1(child1, false) 和 phase1(child2, true)。 child1 或 child2，或两者的计算结果必须为 false。
这样就完成了 "and" 操作。
最后，也是最后一种phase1()可能要处理的是逻辑或操作。你现在应该可以自己弄清楚如何做，但我只是简单地总结一下：
如果 goal 为假，您必须用 phase1(child2, false) 调用 phase1(child1, false)，然后将两个结果组合在一起，作为笛卡尔积。如果 goal 为真，您将针对其他三种可能性进行三组递归调用，并将所有内容组合在一起。
大功告成。 phase1()没有别的事可做，我们通过归纳法完成了证明。
好吧，我撒了点小谎。您还需要做一个小 "Phase 3"。回想一下，在 "Phase 2" 中我们排除了所有不可能的解决方案。好吧，作为所有这些的结果，可能的解决方案的最终列表将有相同的 values_t 在 all_values_t 中出现不止一次，所以你只需要重复数据删除它。
P.S。作为第 1 阶段的一部分，也可以通过即时进行来避免离散的第 2 阶段。这种变化也将成为您的家庭作业。