关于合取范式中的公式，以下哪项是正确的？
Which of the following is TRUE about formulae in Conjunctive Normal Form?
关于合取范式中的公式，下列哪项是正确的？
一个。对于任何公式，都有一个真值赋值，其中至少一半的子句求值为真。
乙。对于任何公式，都有一个真值赋值，所有子句的计算结果都为真。
C。有一个公式使得对于每个真值分配，最多四分之一的子句评估为真。
D. None 以上。
我的疑问：我知道Conjunctive normal form is Product of sum form，但是这个问题让我很困惑，请用简单的语言解释我。
我将展示 (A) 的两个证明。我们可以用任何不可满足的公式快速打折 (B)，比如 x ∧ ¬x。从 (A) 的证明我们也可以折扣 (C) 和 (D)。
构造证明
假设我们在 CNF 中有一些公式。让我们检查任何命题变量（或项，或任何你想给它起的名字），我们称之为 x。我们可以在三种不同的情况下考虑所有包含 x 或 ¬x 的子句：
如果x出现在子句中而¬x没有出现，我们知道如果x赋值为真，子句就会满足，不会如果 x 被赋值为 false，则满足。
类似地，如果¬x出现在子句中而x没有出现，我们知道如果x被赋值为false，子句将被满足，并且如果 x 赋值为 true，则不会满足。
如果x和¬x都出现在子句中，任何赋值都将满足该子句。
如果情况 1 的子句多于情况 2，则对 x 的赋值将满足至少一半的考虑子句。如果情况 2 的子句多于情况 1，则将 false 赋给 x 将满足至少一半的考虑子句。如果案例 1 和案例 2 的出现次数相等，那么对 x 的任何赋值都将满足至少一半的考虑条款。
在剩下的子句中，我们可以对剩下的命题变量应用类似的算法，直到所有子句都至少有一个赋值变量，并且所有这些子句中至少有一半的值为真。
预期值证明
考虑 CNF 中某些公式的任何子句。鉴于每个子句都在 'sum form' 中，所有组成文字只有一个赋值，这将导致该子句的计算结果为 false。这意味着，对于具有 k 个文字的子句，有 2k - 1 个组成文字的赋值，这将使该子句评估为真。因为每个赋值的可能性都是独立的，所以子句评估为真的预期概率是 (2k - 1) / 2k，这是 1 - (1 / 2k)。显然，对于 k 的任何正值，一个子句被任意真值赋值满足的概率至少是二分之一。
根据某个任意条款被满足的概率，我们可以说期望的满足条款数是每个条款被满足的概率之和。从这里，通过少量数学运算，我们可以得出结论，满足子句的预期数量至少是子句总数的一半。因为必须至少有一个真值赋值至少满足这个数量的预期满足子句，我们可以得出结论，对于任何给定的公式，至少存在一个真值赋值满足至少一半的子句。
关于合取范式中的公式，下列哪项是正确的？
一个。对于任何公式，都有一个真值赋值，其中至少一半的子句求值为真。
乙。对于任何公式，都有一个真值赋值，所有子句的计算结果都为真。
C。有一个公式使得对于每个真值分配，最多四分之一的子句评估为真。
D. None 以上。
我的疑问：我知道Conjunctive normal form is Product of sum form，但是这个问题让我很困惑，请用简单的语言解释我。
我将展示 (A) 的两个证明。我们可以用任何不可满足的公式快速打折 (B)，比如 x ∧ ¬x。从 (A) 的证明我们也可以折扣 (C) 和 (D)。
构造证明
假设我们在 CNF 中有一些公式。让我们检查任何命题变量（或项，或任何你想给它起的名字），我们称之为 x。我们可以在三种不同的情况下考虑所有包含 x 或 ¬x 的子句：
如果
x出现在子句中而¬x没有出现，我们知道如果x赋值为真，子句就会满足，不会如果x被赋值为 false，则满足。类似地，如果
¬x出现在子句中而x没有出现，我们知道如果x被赋值为false，子句将被满足，并且如果x赋值为 true，则不会满足。如果
x和¬x都出现在子句中，任何赋值都将满足该子句。
如果情况 1 的子句多于情况 2，则对 x 的赋值将满足至少一半的考虑子句。如果情况 2 的子句多于情况 1，则将 false 赋给 x 将满足至少一半的考虑子句。如果案例 1 和案例 2 的出现次数相等，那么对 x 的任何赋值都将满足至少一半的考虑条款。
在剩下的子句中，我们可以对剩下的命题变量应用类似的算法，直到所有子句都至少有一个赋值变量，并且所有这些子句中至少有一半的值为真。
预期值证明
考虑 CNF 中某些公式的任何子句。鉴于每个子句都在 'sum form' 中，所有组成文字只有一个赋值，这将导致该子句的计算结果为 false。这意味着，对于具有 k 个文字的子句，有 2k - 1 个组成文字的赋值，这将使该子句评估为真。因为每个赋值的可能性都是独立的，所以子句评估为真的预期概率是 (2k - 1) / 2k，这是 1 - (1 / 2k)。显然，对于 k 的任何正值，一个子句被任意真值赋值满足的概率至少是二分之一。
根据某个任意条款被满足的概率，我们可以说期望的满足条款数是每个条款被满足的概率之和。从这里，通过少量数学运算，我们可以得出结论，满足子句的预期数量至少是子句总数的一半。因为必须至少有一个真值赋值至少满足这个数量的预期满足子句，我们可以得出结论，对于任何给定的公式，至少存在一个真值赋值满足至少一半的子句。