3

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

A. 对于任何公式，都有一个真值分配，至少有一半的子句评估为真。

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

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

D. 以上都不是。

我的疑问：我知道合取范式是求和形式的乘积，但是这个问题让我很困惑，请用简单的语言解释一下。

4

1 回答 1

1

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

施工证明

假设我们在 CNF 中有一些公式。让我们检查任何命题变量（或术语，或任何你想称之为的），我们将称之为x。我们可以考虑包含三种不同情况中的一种x或三种以上的所有条款：¬x

  1. 如果x出现在子句中而¬x没有出现，我们知道如果赋值为真则满足子句，如果赋值为假x则不满足子句。x

  2. 类似地，如果¬x出现在子句中而x没有出现，我们知道如果x赋值为假则满足子句，如果x赋值为真则不满足子句。

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

如果 case 1 的子句多于 case 2，则分配 true tox将满足至少一半的考虑子句。如果 case 2 的子句多于 case 1，则分配 false tox将满足至少一半的考虑子句。如果情况 1 和情况 2 的出现相同，则任何赋值都x将满足至少一半的考虑子句。

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

期望值证明

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

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

于 2020-07-15T01:12:01.357 回答