digital - 关于合取范式中的公式，以下哪项是正确的？

Question

关于合取范式中的公式，以下哪项是正确的？

一个。对于任何公式，都有一个真值赋值，至少有一半的子句求值为真。

B.对于任何公式，都有一个真值赋值，所有子句的计算结果都为真。

C.有一个公式使得对于每个真值分配，最多四分之一的子句评估为真。

D.以上都不是。

我的疑惑:我知道Conjunctive normal form is Product of sum form，但是这个问题让我很困惑，请用简单的语言解释我。

Answer 1

我将展示 (A) 的两个证明。我们可以用任何不可满足的公式快速打折 (B)，例如 x ∧ ¬x。从 (A) 的证明我们也可以折扣 (C) 和 (D)。

构造证明

假设我们在 CNF 中有一些公式。让我们检查任何命题变量(或术语，或任何你想调用它的东西)，我们将其称为 x。我们可以在三种不同的情况下考虑所有包含 x 或 ¬x 的子句:

1. 如果 x 出现在子句中而 ¬x 没有出现，我们知道如果 x 是，子句将得到满足赋值为 true，如果 x 赋值为 false，则不满足。

2. 类似地，如果¬x出现在子句中而x没有出现，我们知道如果x子句将被满足> 被赋值为 false，如果 x 被赋值为 true 将不满足。

3. 如果 x 和 ¬x 都出现在子句中，则任何赋值都将满足该子句。

如果情况 1 的子句多于情况 2，则将 true 分配给 x 将满足至少一半的考虑子句。如果情况 2 的子句多于情况 1，则将 false 赋值给 x 将至少满足一半的考虑子句。如果案例 1 和案例 2 的出现次数相等，则对 x 的任何赋值都将满足至少一半的考虑子句。

在剩下的子句中，我们可以对剩下的命题变量应用类似的算法，直到所有子句都至少有一个赋值变量，并且所有这些子句中至少有一半的值为真。

期望值证明

考虑 CNF 中某些公式的任何子句。鉴于每个子句都是“总和形式”，所有组成文字只有一个赋值，这将导致子句评估为假。这意味着，对于具有 k 个文字的子句，有 2^k - 1 个组成文字的赋值，这将使该子句评估为真。因为每个赋值的可能性都是独立的，所以子句评估为真的预期概率是 (2^k - 1)/2^k，即 1 - (1/2^k)。显然，对于任何正的 k 值，一个子句被任意真值赋值满足的概率至少是一半。

根据某个任意条款被满足的概率，我们可以说满足条款的预期数量是每个条款被满足的概率之和。从这里，通过少量数学运算，我们可以得出结论，满足子句的预期数量至少是子句总数的一半。因为必须至少有一个真值赋值至少满足这个数量的预期满足子句，我们可以得出结论，对于任何给定的公式，至少存在一个真值赋值满足至少一半的子句。