形式逻辑/命题逻辑/替换和互换

← 命题联结词的性质

↑ 命题逻辑

翻译 →

替换和互换

本页面将使用在形式语法附加术语部分介绍的出现和子公式的概念。这些概念自从那时以来很少使用，因此你可能想回顾一下它们。

替换

重言式形式

我们已经介绍了一些重言式，其中一个例子是

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

使用元变量$\psi$和$\varphi$来替换(1)中的$\mathrm {Q}$和$\mathrm {R}$。这将产生以下形式

(2)    $\psi \rightarrow (\varphi \rightarrow \psi )\,\!$

事实证明，任何与这种形式匹配的公式都是一个重言式。因此，例如，设$\psi =\mathrm {R} \land \mathrm {S}$和$\varphi =\mathrm {P} \lor \mathrm {Q}$。然后，

(3)    $\mathrm {R} \land \mathrm {S} \rightarrow (\mathrm {P} \lor \mathrm {Q} \rightarrow \mathrm {R} \land \mathrm {S} )\,\!$

是一个重言式。这个过程可以推广到所有重言式：对于任何重言式，通过用不同的元变量（如(2)中所示的希腊字母）替换每个句子字母来找到它的显式形式。我们可以称之为重言式形式，它是一个元逻辑表达式，而不是一个公式。这种重言式形式的任何实例都是一个重言式。

替换实例

前面已经说明了如何通过重言式形式从旧的重言式中生成新的重言式。这里，我们将展示如何在不诉诸重言式形式的情况下生成重言式。为此，我们定义一个公式的替换实例。任何重言式的替换实例也是一个重言式。

首先，我们定义一个公式对句子字母的简单替换实例。设 $\varphi \,\!$ 和 $\psi \,\!$ 是公式，$\pi \,\!$ 是一个句子字母。简单替换实例 $\varphi [\pi /\psi ]\,\!$ 是将 $\varphi \,\!$ 中所有出现的 $\pi \,\!$ 替换为一个出现的 $\psi \,\!$ 所得到的结果。对句子字母的公式替换实例 是简单替换实例链的结果。特别是，从 $\varphi \,\!$ 开始的零个简单替换实例链是一个替换实例，实际上就是 $\varphi \,\!$ 本身。因此，任何公式都是它自身的替换实例。

事实证明，如果 $\varphi \,\!$ 是一个重言式，那么任何简单替换实例 $\varphi [\pi /\psi ]\,\!$ 也是一个重言式。如果我们从一个重言式开始，生成一个简单替换实例链，那么链中的每个公式也是一个重言式。因此，任何（不一定是简单的）重言式的替换实例也是一个重言式。

替换示例

再次考虑 (1)。我们将 $\mathrm {R} \land \mathrm {S} \,\!$ 替换为 (1) 中每个出现的 $\mathrm {Q} \,\!$。这给了我们 (1) 的以下简单替换实例

(4)    $\mathrm {R} \land \mathrm {S} \rightarrow (\mathrm {P} \rightarrow \mathrm {R} \land \mathrm {S} )\,\!$

在本例中，我们将 $\mathrm {P} \lor \mathrm {Q} \,\!$ 代替 $\mathrm {P} \,\!$。这使得 (3) 成为 (4) 的一个简单替换实例。由于 (3) 是两个简单替换实例链的结果，因此它是 (1) 的一个（非简单）替换实例。由于 (1) 是一个永真式，因此 (3) 也是一个永真式。我们可以将替换链表示为

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {Q} /\mathrm {R} \land \mathrm {S} ][\mathrm {P} /\mathrm {P} \lor \mathrm {Q} ]\,\!$

再举一个例子，同样从 (1) 开始。我们想要得到

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

我们第一次尝试可能是将 $\mathrm {P} \,\!$ 代替 $\mathrm {Q} \,\!$，

(6)    $\mathrm {P} \rightarrow (\mathrm {P} \rightarrow \mathrm {P} )\,\!$

这确实是一个永真式，但它不是我们想要的那个。相反，我们将 $\mathrm {R} \,\!$ 代替 $\mathrm {P} \,\!$ 在 (1) 中，得到

$\mathrm {Q} \rightarrow (\mathrm {R} \rightarrow \mathrm {Q} )\,\!$

现在将 $\mathrm {P} \,\!$ 代替 $\mathrm {Q} \,\!$，得到

$\mathrm {P} \rightarrow (\mathrm {R} \rightarrow \mathrm {P} )\,\!$

最后，用 $\mathrm {Q} \,\!$ 替换 $\mathrm {R} \,\!$，我们得到了我们想要的结果，即 (5)。由于 (1) 是一个重言式，所以 (5) 也是一个重言式。我们可以将替换链表示为

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {P} /\mathrm {R} ][\mathrm {Q} /\mathrm {P} ][\mathrm {R} /\mathrm {Q} ]\!$

同时替换

我们可以将一系列简单替换压缩成一个复杂的替换。设 $\varphi \,\!$，$\psi _{1}\,\!$，$\psi _{2}\,\!$，... 是公式；设 $\pi _{1}\,\!$，$\pi _{2}\,\!$，... 是句子字母。我们定义 _对句子字母的公式的**同时替换实例**_ $\varphi [\pi _{1}/\psi _{1},\ \pi _{2}/\psi _{2},\ ...]\,\!$ 为从 $\varphi \,\!$ 开始，并同时用 $\psi _{1}\,\!$ 替换 $\pi _{1}\,\!$，用 $\psi _{2}\,\!$ 替换 $\pi _{2}\,\!$，.... 我们可以重新生成我们的示例。

之前生成的公式 (3) 为

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {P} /\mathrm {P} \lor \mathrm {Q} ,\mathrm {Q} /\mathrm {R} \land \mathrm {S} ]\,\!$

类似地，(5) 为

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {P} /\mathrm {Q} ,\ \mathrm {Q} /\mathrm {P} ]\,\!$

最后（6）是

$\mathrm {Q} \rightarrow (\mathrm {P} \rightarrow \mathrm {Q} )[\mathrm {Q} /\mathrm {P} ]\,\!$

当我们进入谓词逻辑时，将不再可以使用同时替换实例。这就是为什么我们通过参考一系列简单替换实例来定义替换实例，而不是作为同时替换实例。

互换

等效子公式的互换

我们之前在命题连接词的性质中看到了以下等价性

(7)    $\mathrm {P} \,\!$       $\lnot \lnot \mathrm {P} \,\!$

然后你可能会期待以下等价性

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

这个期望是正确的；这两个公式是等价的。令 $\varphi \,\!$ 和 $\psi \,\!$ 是等价的公式。令 $\chi _{1}\,\!$ 是一个公式，其中 $\varphi \,\!$ 作为子公式出现。最后，令 $\chi _{2}\,\!$ 是在 $\chi \,\!$ 中至少用一次（不一定是全部） $\varphi \,\!$ 替换 $\psi \,\!$ 所得到的结果。那么 $\chi _{1}\,\!$ 和 $\chi _{2}\,\!$ 是等价的。这种替换被称为替换。

举个例子，假设我们想要生成等价性

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

我们注意到以下等价性

(9)    $\mathrm {Q} \land \mathrm {R} \,\!$       $\lnot \lnot (\mathrm {Q} \land \mathrm {R} )\,\!$

这两个公式可以通过真值表来确认是等价的，或者更简单的方法是，在 (7) 的两个公式中用 $\mathrm {Q} \land \mathrm {R} \,\!$ 替换 $\mathrm {P} \,\!$。

这种替换确实将 (9) 建立为等价。我们已经注意到 $\varphi \,\!$ 和 $\psi \,\!$ 等价当且仅当 $\varphi \leftrightarrow \psi \,\!$ 是重言式。根据 (7)，我们得到重言式

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

然后我们的替换得到

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

这也是一个重言式。相应的等价式就是 (9)。

基于 (9)，我们现在可以将 $\mathrm {P} \rightarrow \mathrm {Q} \land \mathrm {R} \,\!$ 的后件替换为等价式。这将生成我们需要的等价式，即 (8)。

每个等价于重言式的公式也是重言式。因此，在重言式中交换等价子公式会导致重言式。例如，我们可以使用 (7) 的替换实例

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

以及之前在 命题连接词性质 中看到的重言式

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

得到

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

作为一个新的重言式。

交换示例

例如，我们将使用 连接词的可互定义性 来表达

(10)    $\mathrm {P} \leftrightarrow \mathrm {Q} \lor \mathrm {R} \,\!$

只使用条件语句和否定。

基于

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

我们得到替换实例

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

这反过来让我们能够替换(10)中相应的子公式，得到

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

等价

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

以及相应的替换，为我们提供了

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

与(11)等价。

最后，应用

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

以及相应的替换，产生了我们的最终结果

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

摘要

本页介绍了两个论点。

• 重言式的替换实例也是重言式。

• 给定一个公式，用等价的子公式替换子公式的结果是一个等价于给定公式的公式。

这些论点并非微不足道的观察结果，也非简单真值表的结论。它们是需要证明的实质性论点。许多标准元逻辑教科书中提供了证明，但此处未给出。

← 命题联结词的性质

↑ 命题逻辑

翻译 →