寻找真值组合的#

Question

有个问题我一直做不好。

有多少种 p、q 和 r 真值的组合使这个表达式为真？ (p && !q) || (q || !r)

我知道答案是7，但不知道他们是怎么得出答案的。我可以简单地测试每个组合（最多 8 个，2^3），但是有没有更快的方法可以做到这一点？表达式可以简化吗？

Answer 1

这当然不需要穷举。你可以这样推理：

1. 由于 || !r 你知道 r == false 的 4 种组合满足表达式
2. 由于|| q你知道在剩下的4个组合中，q == true的2个满足表达式
3. 由于 (p && !q) 你知道剩下的 2 个组合都有 q == false（因为你已经考虑了上面 q == true 的情况）所以 1 p == true满足表达式

将这些相加得到满足表达式的 7 个组合。

至于简化表达式，(p && !q) || q等同于p || q。所以表达式可以简化为p || q || !r。这也可以表示为 !(!p && !q && r) 这使得为什么有 7 种组合很明显：只有一种组合不满足表达式。

Answer 2

回答第二个问题，"can it be simplified?"：在布尔代数中，表达式

a || (!a && b)

等同于

a || b

看原文：

(p && !q) || (q || !r)

注意 || 是关联的（&& 也是），因此您可以重新排列括号：

((p && !q) || q) || !r

第一部分是我答案顶部的等价情况，因此

((p && !q) || q)

等同于

p || q

（注意||和&&都是可交换的），所以整个表达式等价于

p || q || !r