查找可能的布尔值以将表达式计算为true

1 回答

• 0

  我想我看到了一种计算方法，而不必尝试所有的排列，下面描述的高级轮廓并不是非常复杂 . 我将概述基本方法，您将自己完成两项后续任务：

  • 将逻辑表达式（如“A &&（B || C）”）解析为经典的解析树，表示树中的每个节点都是变量或布尔运算的表达式，“&&”，“ ||“，或”！“ （不），有两个孩子是它的操作数 . 这是一个经典的解析树 . 在Google中可以找到大量如何执行此操作的示例 .

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

  为了解决这个问题，我将采用两阶段方法 .

  • 我将使用proof by induction的一般方法，以便得出布尔表达式将评估为 true 的所有变量的所有潜在值集的暂定列表 .

  • 在第二阶段，我将从所有潜在集合的列表中删除那些在逻辑上不可能的集合 . 这可能听起来很混乱，所以我先解释第二阶段 .

  设's use the following datatypes. First, I' ll使用布尔表达式将评估为 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"必须同时为true和false .

  但显然，这在逻辑上是不可能的 . 因此，在此解决方案的第2阶段，您需要简单地浏览 all_values_t 中的所有单个 values_t ，并删除包含 true 和 false 的"impossible" values_t 作为某个变量 . 这样做的方式似乎相当明显，我不会浪费时间来描述它，但是第1阶段完成后，第2阶段应该是直截了当的 .

  对于阶段1，我们的目标是提出一个大致如下所述的函数：

  all_values_t phase1(expression_t expr, bool goal);
  

  expr 是你的布尔表达式的解析表示，作为一个解析树（正如我在开头提到的那样，这部分将取决于你） . goal 是您希望如何计算解析后的表达式： phase1() 将 expr 评估为 true 或 false 的所有可能 all_values_t 返回，如"goal"所示 . 显然，你将 phase1() 调用 true 为"goal"作为答案，因为这是你想要弄清楚的 . 但 phase1() 将以递归方式调用自身，使用 true 或 false "goal"来实现其魔力 .

  在继续之前，现在重要的是阅读和理解描述感应证明如何工作的各种资源 . 在完全理解这个一般概念之前，不要再继续了 .

  好的，现在您了解这个概念 . 如果你这样做，那么你现在必须同意我 phase1() 已经完成了 . 有用！归纳证明首先假设 phase1() 做了它应该做的事情 . phase1() 将对自身进行递归调用，并且由于 phase1() 返回正确的结果， phase1() 可以简单地依靠自身来计算所有内容 . 看看这有多容易？

  phase1() 手边有一个"simple"任务：

  • 检查解析树的顶级节点是什么 . 它将是变量节点或表达式节点（参见上文） .

  • 基于此返回相应的 all_values_t .

  而已 . 我们将同时采取两种可能性 .

  • 顶级节点是一个变量 .

  所以，如果你的表达式只是一个变量，并且你希望表达式返回 goal ，那么：

  values_t v{ {name, goal} };
  

  表达式只有一种可能的方式来评估 goal ：一个明显的简单：变量，以及 goal 的值 .

  而且只有一种可能的解决方案 . 没有其他选择：

  all_values_t res;
  
  res.push_back(v);
  
  return res;
  

  现在，另一种可能性是表达式中的顶级节点是布尔运算之一：和，或者不是 .

  再一次，我们将分裂并征服这一点，并逐一解决每一个问题 .

  让我们说它是“不” . 那我们该怎么办？这应该很容易：

  return phase1(child1, !goal);
  

  只需递归调用 phase1() ，传递"not"表达式的子节点，逻辑反转 goal . 因此，如果您的 goal 为真，请使用 phase1() 返回"not"子表达式的值为false，反之亦然 . 请记住，归纳证明假定 phase1() 的工作方式与广告一致，因此您可以依靠它来获得子表达式的正确答案 .

  它现在应该开始显而易见 phase1() 的其余部分如何工作 . 只剩下两种可能性："and"和"or"逻辑运算 .

  对于"and"操作，我们将单独考虑"and"操作的"goal"应该是 true 还是 false .

  如果 goal 为true，则必须使用 phase1() 为 all_values_t 提供两个子表达式为true：

  all_values_t left_result=phase1(child1, true);
  
  all_values_t right_result=phase1(child2, true);
  

  然后将两个结果合并在一起 . 现在，请回想一下 all_values_t 是所有 possible 值的列表 . all_values_t 中的每个值（可以是空列表/向量）表示一种可能的解决方案 . 左侧和右侧子表达式必须在逻辑上组合，但 left_result 中的任何可能解决方案都可以与任何 right_result 一起使用 . 左子表达式为true的任何潜在解决方案都可以（并且必须）与任何可能的解决方案一起使用，右子表达式为true .

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

  但是你的 goal 要让"and"表达式返回 false ，相反，你只需要做三次这样的变化 . 第一次通过 phase1(child2, false) 调用 phase1(child1, false) ;然后 phase1(child1, true) 与 phase1(child2, false) ;最后 phase1(child1, false) 和 phase1(child2, true) . child1 或 child2 或两者必须评估为 false .

  因此，它负责“和”操作 .

  最后，也是 phase1() 处理的最终可能性是逻辑或操作 . 你现在应该能够自己弄清楚如何做到这一点，但我只是简单地总结一下：

  如果 goal 为false，则必须使用 phase1(child2, false) 调用 phase1(child1, false) ，然后将两个结果合并为一个笛卡尔积 . 如果 goal 为真，您将为其他三种可能性进行三组递归调用，并将所有内容组合在一起 .

  你 phase1() 没什么可做的，我们通过归纳完成了我们的证明 .

  好吧，我撒谎了一下 . 你还需要做一个小"Phase 3" . 回想一下，在"Phase 2"中我们消除了所有不可能的解决方案 . 好吧，有可能的是，由于所有这些，最终的可能解决方案列表将具有相同的 values_t 出现不止一次 all_values_t ，所以你只需重复数据删除即可 .

  附：作为第1阶段的一部分，也可以通过动态执行来避免离散阶段2.这种变化也将成为您的家庭作业 .

  回复于 2024-05-08T20:02:07+08:00