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

我们可以通过演绎得到答案。

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

b 必须为false才能使整个表达式为false,因为它是OR运算符的操作数:

b or ...

然而,在右侧,如果 那么是假的 not b 这是真的:

(a or (not b))

是的。

现在我们的表达变成了:

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

正如你们在这里可以清楚地看到的,右边必须评估为真,整个事情评估为真。因此,答案是 .

您可以编写一个小程序或单元测试。

  @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)));
  }

我保留了支架,即使其中一些可以移除。

结果是:

真的

真的
真的

那么你的问题的答案是:

是“不,你不能”。

第二部分的答案是:在现实世界中,你会使用所谓的呼叫 SAT solver

深入了解这些工具的工作原理是计算机科学基础课题的一个极好的切入点。参见resp。听听这个 podcast 例如它讨论了P和NP之间的差异,然后花了很多时间解释为什么我们能够解决这个问题 SAT问题(在NP中)是目前有效的。