如何简化以下CNF

Question

我无法简化上述CNF。有人能帮我简化报表吗

Answer 1

我们可以为此制作一个真值表：

p   q   r   (¬p ∨ ¬q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r)
0   0   0   1
0   0   1   0
0   1   0   0
0   1   1   0
1   0   0   1
1   0   1   0
1   1   0   1
1   1   1   0

如果这个真值表是正确的，那么等价的表达式是：

(¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r)

我们可以考虑简化一点。。。

[¬q ∨ (p ∧ q)] ∧ ¬r

我们还可以认识到，q∧(p∧q(=q∧p。。。

(¬q ∨ p) ∧ ¬r

这似乎与我们得到的真值表相匹配，所以如果真值表是正确的，这个表达式几乎肯定是最小的或接近它。它只使用每个变量一次，所以脑海中浮现的唯一尝试改进它的方法是De Morgan，但它看起来甚至没有减少运算次数，所以这可能是最好的。