求解布尔表达式时如何思考？

Question

我有以下问题：

令a和b为布尔变量。是否可以设置 a 和 b 的值以使以下表达式的计算结果为 false？ b or (((not a) or (not a)) or (a or (not b)))

解决此问题的最佳方法是什么？我知道在一张纸上解决所有四种可能性会给我答案，但是有没有有效的策略来处理这类问题？

Answer 1

推导即可得出答案

b or (((not a) or (not a)) or (a or (not b)))

正如我们在这里看到的，b 必须为假才能使整个表达式为假，因为它是 OR 运算符的操作数：

b or ...

然而，在右侧，如果 b 为假，则 not b 为真，因此：

(a or (not b))

正确。

现在我们的表达式变成了：

false or (((not a) or (not a)) or true)

正如您在此处可以清楚地看到的那样，右侧的计算结果必须为真，而整个事物的计算结果为真。因此，答案是否。

Answer 2

你可以写一个小程序或者单元测试。

  @Test
  public void testSomeThing() {
    System.out.println(check(true, true));
    System.out.println(check(true, false));
    System.out.println(check(false, true));
    System.out.println(check(false, false));

  }

  private boolean check(final boolean a, final boolean b) {
    return b || (((!a) || (!a)) || (a || (!b)));
  }

我保留了括号，尽管其中一些可以删除。

结果是：

真
真
真
真

所以你的问题的答案：

Is it possible to set values for a and b to have the following expression evaluate as false?

是"No you can't"。

Answer 3

第二部分的答案：在现实世界中，您将使用 so 调用 SAT solver（为了满足性）。意思是：你可以手动简化小方程，但在现实世界中，你可能有数百万个变量的方程 - 然后你求助于 SAT 求解器。

深入了解这些工具的工作原理是计算机科学基础主题的绝佳切入点。见分别。例如听这个podcast。它讨论了 P 和 NP 之间的差异 - 然后花了很多时间解释为什么我们现在能够有效地解决大型 SAT 问题（属于 NP）。

求解布尔表达式时如何思考？

How to think when solving boolean expressions?

java

boolean-expression