形式逻辑/命题逻辑/形式语法

← 命题语言

↑ 命题逻辑

非正式约定 →

形式语法

在命题语言中，我们非正式地描述了我们的命题语言。在这里，我们给出它的形式语法或文法。我们将我们的语言称为${\mathcal {L_{S}}}\,\!$.

词汇

• 命题字母：大写字母 'A' – 'Z'，每个字母都有 (1) 上标 '0' 和 (2) 自然数下标。（自然数 是正整数和零的集合。）因此，命题字母是

$\mathrm {A_{0}^{0}} ,\ \mathrm {A_{1}^{0}} ,\ ...,\ \mathrm {B_{0}^{0}} ,\ \mathrm {B_{1}^{0}} ,\ ...,\ ...,\ \mathrm {Z_{0}^{0}} ,\ \mathrm {Z_{1}^{0}} ,\ ...\,\!$

• 命题联结词:

$\land ,\ \lor ,\ \lnot ,\ \rightarrow ,\ \leftrightarrow \,\!$

• 分组符号

$(,\ )\,\!$

命题字母上的上标直到我们学习谓词逻辑才重要，所以在这里我们不会太在意它们。命题字母的下标是为了确保命题字母有无限个。在下一页，我们将缩写掉大多数上标和下标。

表达式

来自${\mathcal {L_{S}}}\,\!$词汇的任何字符序列都是${\mathcal {L_{S}}}\,\!$的表达式。有些表达式在语法上是正确的。有些表达式在${\mathcal {L_{S}}}\,\!$中与 'Over talks David Mary the' 在英语中的错误一样。其他一些表达式在${\mathcal {L_{S}}}\,\!$中与 'jmr.ovn asgj as;lnre' 在英语中的错误一样。

我们将语法上正确的${\mathcal {L_{S}}}\,\!$表达式称为合式公式。当我们开始学习谓词逻辑时，我们会发现只有部分合式公式才是句子。不过现在，我们将所有合式公式都视为句子。

构造规则

${\mathcal {L_{S}}}\,\!$中的表达式，如果它是根据以下规则构造的，则被称为${\mathcal {L_{S}}}\,\!$的合式公式。

${\mbox{i.}}$ 该表达式由一个句子字母组成

${\mbox{ii.}}$ 该表达式是通过以下几种方式之一，由其他合式公式$\varphi \,\!$和$\psi \,\!$构造的

${\mbox{ii-a.}}\ \ \lnot \varphi \,\!$

${\mbox{ii-b.}}\ \ (\varphi \land \psi )\,\!$

${\mbox{ii-c.}}\ \ (\varphi \lor \psi )\,\!$

${\mbox{ii-d.}}\ \ (\varphi \rightarrow \psi )\,\!$

${\mbox{ii-e.}}\ \ (\varphi \leftrightarrow \psi )\,\!$

一般来说，我们将使用 'formula' 来简化 'well-formed formula'。由于${\mathcal {L_{S}}}\,\!$ 中的所有公式都是句子，我们将交替使用 'formula' 和 'sentence'。

引用约定

我们将把${\mathcal {L_{S}}}\,\!$中的表达式视为自我引用，并因此将其视为

$(\mathrm {P_{0}^{0}} \rightarrow \mathrm {Q_{0}^{0}} )\,\!$

包含隐式引号。但是，类似

$(1)\quad (\varphi \rightarrow \psi )\,\!$

需要特别考虑。它本身不是 ${\mathcal {L_{S}}}\,\!$ 的表达式，因为 $\varphi \,\!$ 和 $\psi \,\!$ 不在 ${\mathcal {L_{S}}}\,\!$ 的词汇表中。相反，它们在英语中用作变量，这些变量在 ${\mathcal {L_{S}}}\,\!$ 的表达式上取值。这样的变量称为 *元变量*，使用来自 ${\mathcal {L_{S}}}\,\!$ 和元变量的词汇的表达式称为 *元逻辑表达式*。假设我们让 $\varphi \,\!$ 为 $\mathrm {P_{0}^{0}} \,\!$，并且 $\psi \,\!$ 为 $(\mathrm {Q_{0}^{0}} \lor \mathrm {R_{0}^{0}} )\ .\,\!$ 那么 (1) 变成

$(\,\!$'$\mathrm {P_{0}^{0}} \,\!$' $\rightarrow (\,\!$'$\mathrm {Q_{0}^{0}} \,\!$' $\lor \,\!$'$\mathrm {R_{0}^{0}} \,\!$'$))\,\!$

这与我们想要的不同。相反，我们将（1）理解为（使用明确的引号）

由 '$(\,\!$' 接着 $\varphi \,\!$ 接着 '$\rightarrow \,\!$' 接着 $\psi \,\!$ 接着 '$)\,\!$' 组成的表达式。

遵循这种约定的明确引号被称为 *Quine 引号* 或 *角引号*。我们的角引号将是隐式的。

其他术语

我们介绍（或在某些情况下，重复）一些有用的语法术语。

• 我们区分表达式（或公式）和表达式的 *出现*（或公式）。公式

$((\mathrm {P_{0}^{0}} \land \mathrm {P_{0}^{0}} )\land \lnot \mathrm {P_{0}^{0}} )\,\!$

无论写多少次，都是同一个公式。但是，它包含三个句子字母 $\mathrm {P_{0}^{0}} \,\!$ 的出现，以及两个句子连接词 $\land \,\!$ 的出现。

• $\psi \,\!$ 是 $\varphi \,\!$ 的一个 子公式 当且仅当 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式，并且 $\varphi \,\!$ 包含 $\psi \,\!$ 的一个出现。 $\psi \,\!$ 是 $\varphi \,\!$ 的一个 真子公式 当且仅当 (i) $\psi \,\!$ 是 $\varphi \,\!$ 的一个子公式，并且 (ii) $\psi \,\!$ 与 $\varphi \,\!$ 不是同一个公式。

• 一个 原子公式 或 原子句子 是一个仅包含一个句子字母的公式。或者换句话说，它是一个不包含任何句子连接词的公式。一个 分子公式 或 分子句子 是一个包含至少一个句子连接词的公式。

• 一个分子公式的 主连接词 是在根据上述规则构造公式时最后添加的连接词的最后一个出现。

• 一个 否定 是一个形式为 $\lnot \varphi \,\!$ 的公式，其中 $\varphi \,\!$ 是一个公式。

• 合取 是一个形如 $(\varphi \land \psi )\,\!$ 的公式，其中 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式。在这种情况下，$\varphi \,\!$ 和 $\psi \,\!$ 都是 合取式。

• 析取 是一个形如 $(\varphi \lor \psi )\,\!$ 的公式，其中 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式。在这种情况下，$\varphi \,\!$ 和 $\psi \,\!$ 都是 析取式。

• 条件式 是一个形如 $(\varphi \rightarrow \psi )\,\!$ 的公式，其中 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式。在这种情况下，$\varphi \,\!$ 是 前件，$\psi \,\!$ 是 后件。 $(\varphi \rightarrow \psi )\,\!$ 的 逆命题 是 $(\psi \rightarrow \varphi )\,\!$。 $(\varphi \rightarrow \psi )\,\!$ 的 逆否命题 是 $(\lnot \psi \rightarrow \lnot \varphi )\,\!$.

• 双条件式是一个形如$(\varphi \leftrightarrow \psi )\,\!$ 的公式，其中 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式。

示例

$(1)\quad (\lnot (\mathrm {P_{0}^{0}} \lor \mathrm {Q_{0}^{0}} )\rightarrow (\mathrm {R_{0}^{0}} \land \lnot \mathrm {Q_{0}^{0}} ))\,\!$

根据规则 (i)，所有句子字母，包括

$\mathrm {P_{0}^{0}} ,\ \mathrm {Q_{0}^{0}} ,\ {\mbox{and}}\ \mathrm {R_{0}^{0}} \ ,\,\!$

都是公式。那么，根据规则 (ii-a)，否定

$\lnot \mathrm {Q_{0}^{0}} \,\!$

也是公式。然后，根据规则 (ii-c) 和 (ii-b)，我们得到析取和合取

$(\mathrm {P_{0}^{0}} \lor \mathrm {Q_{0}^{0}} ),\ {\mbox{and}}\ (\mathrm {R_{0}^{0}} \land \lnot \mathrm {Q_{0}^{0}} )\,\!$

作为公式。再次应用规则 (ii-a)，我们得到否定

$\lnot (\mathrm {P_{0}^{0}} \lor \mathrm {Q_{0}^{0}} )\,\!$

作为公式。最后，规则 (ii-c) 生成 (1) 的条件式，所以它也是公式。

$(2)\quad ((\mathrm {P_{0}^{0}} \lnot \land \mathrm {Q_{0}^{0}} )\lor \mathrm {S_{0}^{0}} )\,\!$

这似乎是由规则 (ii-c) 从以下公式生成的

$(\mathrm {P_{0}^{0}} \lnot \land \mathrm {Q_{0}^{0}} ),\ {\mbox{and}}\ \mathrm {S_{0}^{0}} \ .\,\!$

其中第二个公式是根据规则 (i) 得出的。但第一个公式呢？它必须根据规则 (ii-b) 从

$\mathrm {P_{0}^{0}} \lnot \ {\mbox{and}}\ \mathrm {Q_{0}^{0}} \ .\,\!$

但是

$\mathrm {P_{0}^{0}} \lnot \,\!$

不能根据规则 (ii-a) 生成。因此 (2) 不是一个公式。

← 命题语言

↑ 命题逻辑

非正式约定 →