形式逻辑/命题逻辑/表达能力

← 有效性

↑ 命题逻辑

命题连接词的性质 →

表达能力

公式真值表

一个包含 n 个命题字母的公式在其 真值表 中需要 $2^{n}\,\!$ 行。对于一个包含 m 行的真值表，存在 $2^{m}\,\!$ 种可能的公式。因此，对于一个包含 n 个字母的句子，$m=2^{n}$，可能的公式数量为 $2^{2^{n}}$。

例如，存在四个包含一个命题字母的可能公式（需要一个两行真值表），以及 16 个包含两个命题字母的可能公式（需要一个四行真值表）。我们用以下表格来说明这一点。编号的列代表主连接词列的不同可能性。

$\mathrm {P} \,\!$ (i) (ii) (iii) (iv) T T T F F F T F T F

第 (iii) 列是 之前 提出的否定公式。

$\mathrm {P} \,\!$ $\mathrm {Q} \,\!$ (i) (ii) (iii) (iv) (v) (vi) (vii) (viii) (ix) (x) (xi) (xii) (xiii) (xiv) (xv) (xvi) T T T T T T T T T T F F F F F F F F T F T T T T F F F F T T T T F F F F F T T T F F T T F F T T F F T T F F F F T F T F T F T F T F T F T F T F

第 (ii) 列表示析取公式，第 (v) 列表示条件公式，第 (vii) 列表示双条件公式，第 (viii) 列表示合取公式。

表达任意公式

问题出现了，我们是否有足够的连接词来表示任意数量的命题字母的所有公式。请记住，每一行都代表一种赋值。我们可以通过将该赋值下被赋值为真的命题字母与被赋值为假的命题字母的否定进行合取来表达该赋值。上面的第二个表格中的四个赋值可以表达为

$\mathrm {P} \land \mathrm {Q} \,\!$

$\mathrm {P} \land \lnot \mathrm {Q} \,\!$

$\lnot \mathrm {P} \land \mathrm {Q} \,\!$

$\lnot \mathrm {P} \land \lnot \mathrm {Q} \,\!$

现在我们可以通过对公式值为真的赋值进行析取来表达任意公式。例如，我们可以用以下公式表达第 (x) 列

(1)      $(\mathrm {P} \land \lnot \mathrm {Q} )\lor (\lnot \mathrm {P} \land \mathrm {Q} )\,\!$

您可以通过完成真值表来确认此公式是否产生了预期的结果。该公式在以下情况下为真： (a) $\mathrm {P} \,\!$ 为真且 $\mathrm {Q} \,\!$ 为假，或者 (b) $\mathrm {P} \,\!$ 为假且 $\mathrm {Q} \,\!$ 为真。有一个更简单的方法来表达相同的公式： $\mathrm {P} \leftrightarrow \lnot \mathrm {Q} \,\!$。想出一个表达任意公式的简单方法可能需要洞察力，但至少我们有一个自动机制来找到表达它的某些方法。

现在考虑第二个例子。我们想表达一个关于 $\mathrm {P} \,\!$，$\mathrm {Q} \,\!$ 和 $\mathrm {R} \,\!$ 的公式，我们希望该公式在以下三种赋值下（且仅在以下三种赋值下）为真。

			(i)		(ii)		(iii)
	$\mathrm {P} \,\!$		真		假		假
	$\mathrm {Q} \,\!$		真		真		假
	$\mathrm {R} \,\!$		假		假		真

我们可以将产生真值的三个条件表达为

$\mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} \,\!$

$\lnot \mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} \,\!$

$\lnot \mathrm {P} \land \lnot \mathrm {Q} \land \mathrm {R} \,\!$

现在我们需要说第一个条件或第二个条件或第三个条件成立。

(2)      $(\mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} )\lor (\lnot \mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} )\lor (\lnot \mathrm {P} \land \lnot \mathrm {Q} \land \mathrm {R} )\,\!$

您可以通过真值表验证它是否产生了预期的结果，即该公式仅在上述解释下为真。

这种表达任意公式的技术不适用于在所有解释中都计算为 False 的公式。我们需要至少一个解释得出 True，才能启动公式。但是，我们可以使用任何永真假公式来表达这种公式。 $\mathrm {P} \land \lnot \mathrm {P} \,\!$ 就足够了。

范式

范式提供了一种标准化的表达规则，任何公式都等效于符合该规则的公式。在以下内容中，将文字定义为句子字母或其否定（例如 $\mathrm {P}$ 和 $\mathrm {Q}$，以及 $\neg \mathrm {P}$ 和 $\neg \mathrm {Q}$）。

析取范式

我们说一个公式处于析取范式，如果它是文字的合取的析取。例如 $(\mathrm {P} \land \mathrm {Q} )\lor (\lnot \mathrm {R} \land \mathrm {S} )$。为了这个定义的目的，我们承认所谓的退化析取和合取，它们只有一个析取项或合取项。因此，我们将 $\mathrm {P} \,\!$ 算作处于析取范式，因为它是一个退化（单一位置）析取的退化（单一位置）合取。可以通过将其转换为等效公式 $(\mathrm {P} \land \mathrm {P} )\lor (\mathrm {P} \land \mathrm {P} )\,\!$ 来消除这种退化。为了这个定义的目的，我们还承认多位置析取和合取，例如 $(\lnot \mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} )\lor (\mathrm {S} \land \mathrm {R} )$。上面展示了一种找到任意公式的析取范式的方法。

合取范式

在命题逻辑中还有另一种常见的范式，即合取范式。一个公式处于合取范式，如果它是文字的析取的合取。例如 $(\mathrm {P} \lor \lnot \mathrm {Q} )\land (\mathrm {R} \lor \mathrm {S} )$。同样，我们可以用合取范式表达任意公式。首先，取公式计算为 False 的赋值。对于每个这样的赋值，形成一个析取，该析取包含赋值为 False 的句子字母以及赋值为 True 的句子字母的否定。对于赋值

$\mathrm {P} \,\!$   :    False

$\mathrm {Q} \,\!$   :    True

$\mathrm {R} \,\!$   :    假

我们形成析取

$\lnot \mathrm {P} \lor \mathrm {Q} \lor \lnot \mathrm {R} \,\!$

任意公式的合取范式表达式是所有与公式计算为假的解释相匹配的这种析取的合取。上面 (1) 的合取范式等价形式是

$(\lnot \mathrm {P} \lor \mathrm {Q} )\land (\mathrm {P} \lor \lnot \mathrm {Q} )\,\!$

上面 (2) 的合取范式等价形式是

$(\lnot \mathrm {P} \lor \lnot \mathrm {Q} \lor \lnot \mathrm {R} )\land (\mathrm {P} \lor \lnot \mathrm {Q} \lor \lnot \mathrm {R} )\land (\mathrm {P} \lor \lnot \mathrm {Q} \lor \mathrm {R} )\land (\mathrm {P} \lor \mathrm {Q} \lor \lnot \mathrm {R} )\land (\mathrm {P} \lor \mathrm {Q} \lor \mathrm {R} )$

连接词的互定义性

否定和合取足以表达其他三个连接词，事实上可以表达任何任意公式。

$\mathrm {P} \lor \mathrm {Q} \,\!$       $\lnot (\lnot \mathrm {P} \land \lnot \mathrm {Q} )\,\!$

$\mathrm {P} \rightarrow \mathrm {Q} \,\!$       $\lnot (\mathrm {P} \land \lnot \mathrm {Q} )\,\!$

$\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$       $(\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {Q} \rightarrow \mathrm {P} )\,\!$       $\lnot (\mathrm {P} \land \lnot \mathrm {Q} )\land \lnot (\mathrm {Q} \land \lnot \mathrm {P} )\,\!$

否定和析取足以表达其他三个连接词，实际上可以表达任何任意公式。

$\mathrm {P} \land \mathrm {Q} \,\!$       $\lnot (\lnot \mathrm {P} \lor \lnot \mathrm {Q} )\,\!$

$\mathrm {P} \rightarrow \mathrm {Q} \,\!$       $\lnot \mathrm {P} \lor \mathrm {Q} \,\!$

$\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$       $(\mathrm {P} \land \mathrm {Q} )\lor (\lnot \mathrm {P} \land \lnot \mathrm {Q} )\,\!$       $\lnot (\lnot \mathrm {P} \lor \lnot \mathrm {Q} )\lor \lnot (\mathrm {P} \lor \mathrm {Q} )\,\!$

否定和条件句足以表达其他三个连接词，实际上可以表达任何任意公式。

$\mathrm {P} \lor \mathrm {Q} \,\!$       $\lnot \mathrm {P} \rightarrow \mathrm {Q} \,\!$

$\mathrm {P} \land \mathrm {Q} \,\!$       $\lnot (\mathrm {P} \rightarrow \lnot \mathrm {Q} )\,\!$

$\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$       $(\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {Q} \rightarrow \mathrm {P} )\,\!$       $\lnot ((\mathrm {P} \rightarrow \mathrm {Q} )\rightarrow \lnot (\mathrm {Q} \rightarrow \mathrm {P} ))\,\!$

否定和双条件句不足以表达其他三个连接词。

联合否定和选择否定

我们已经看到，三对连接词可以共同表达任何任意公式。于是就产生了疑问，是否可以通过仅仅一个连接词来表达任何任意公式？答案是肯定的，但不能使用我们已有的任何连接词。如果在${\mathcal {L_{S}}}\,\!$中添加一个新的连接词，那么会有两个可能的二元连接词，如果添加它们，则足以表达任何公式。

选择否定

替代否定，有时也称为NAND。这个的常用符号被称为Sheffer 竖线，写成 $\mid$（有些作者使用 ↑）。暂时将符号 $\mid \,\!$ 添加到 ${\mathcal {L_{S}}}\,\!$，并令 ${\mathfrak {v}}[(\varphi \mid \psi )]\,\!$ 在 $\varphi \,\!$ 或 $\psi \,\!$ 中至少有一个为假时为真。它具有如下真值表 

$\mathrm {P} \,\!$ $\mathrm {Q} \,\!$ $\mathrm {P} \mid \mathrm {Q} \,\!$ T T F T F T F T T F F T

现在我们有以下等价关系。

$\lnot \mathrm {P} \,\!$       $\mathrm {P} \mid \mathrm {P} \,\!$

$\mathrm {P} \land \mathrm {Q} \,\!$       $(\mathrm {P} \mid \mathrm {Q} )\mid (\mathrm {P} \mid \mathrm {Q} )\,\!$

$\mathrm {P} \lor \mathrm {Q} \,\!$       $(\mathrm {P} \mid \mathrm {P} )\mid (\mathrm {Q} \mid \mathrm {Q} )\,\!$

$\mathrm {P} \rightarrow \mathrm {Q} \,\!$       $\mathrm {P} \mid (\mathrm {Q} \mid \mathrm {Q} )\,\!$

$\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$       $(\mathrm {P} \mid \mathrm {Q} )\mid ((\mathrm {P} \mid \mathrm {P} )\mid (\mathrm {Q} \mid \mathrm {Q} ))\,\!$

联合否定

联合否定，有时称为NOR。暂时将符号 $\downarrow \,\!$ 添加到 ${\mathcal {L_{S}}}\,\!$，并让 ${\mathfrak {v}}[(\varphi \downarrow \psi )]\,\!$ 在 $\varphi \,\!$ 和 $\psi \,\!$ 都为假时为真。它具有真值表 

$\mathrm {P} \,\!$ $\mathrm {Q} \,\!$ $\mathrm {P} \downarrow \mathrm {Q} \,\!$ T T F T F F F T F F F T

现在我们有以下等价关系。

$\lnot \mathrm {P} \,\!$       $\mathrm {P} \downarrow \mathrm {P} \,\!$

$\mathrm {P} \land \mathrm {Q} \,\!$       $(\mathrm {P} \downarrow \mathrm {P} )\downarrow (\mathrm {Q} \downarrow \mathrm {Q} )\,\!$

$\mathrm {P} \lor \mathrm {Q} \,\!$       $(\mathrm {P} \downarrow \mathrm {Q} )\downarrow (\mathrm {P} \downarrow \mathrm {Q} )\,\!$

$\mathrm {P} \rightarrow \mathrm {Q} \,\!$       $((\mathrm {P} \downarrow \mathrm {Q} )\downarrow \mathrm {Q} )\downarrow ((\mathrm {P} \downarrow \mathrm {Q} )\downarrow \mathrm {Q} )\,\!$

$\mathrm {P} \leftrightarrow \mathrm {Q} \,\!$       $((\mathrm {P} \downarrow \mathrm {P} )\downarrow \mathrm {Q} )\downarrow (\mathrm {P} \downarrow (\mathrm {Q} \downarrow \mathrm {Q} ))\,\!$

← 有效性

↑ 命题逻辑

命题连接词的性质 →