命题逻辑语言

发表于 由 giorgio.reveco
命题逻辑语言

命题逻辑语言

摘要

本笔记审查了命题逻辑语言作为一种元语言，用于从由两个符号组成的基础语言中获得有效的表达式。解释了句法规则、命题变量和连接词的概念，还介绍了联合否定、括号和重排的使用，以便于表达式的阅读。此外，还提到了命题逻辑表达式的发音。最后，将命题逻辑语言总结为数学和逻辑中的一项基本工具，并探讨了找到“基础语言的基础语言”的可能性，从而可以用它重建一切。

学习目标：

完成本部分后，期望学生能够：

  1. 理解元语言的概念及其在命题逻辑中的应用。
  2. 理解命题逻辑语言的句法规则。
  3. 了解命题变量的概念及其在构建表达式中的应用。
  4. 理解连接词和联合否定在命题逻辑语言中的使用。
  5. 学习使用括号和重排以便于阅读表达式。
  6. 了解命题逻辑表达式的发音。
  7. 总结命题逻辑语言作为数学和逻辑中的一项基本工具。
  8. 思考找到“基础语言的基础语言”的可能性，从而可以用它重建一切。
  9. 应用所学概念构建命题逻辑表达式。
  10. 使用命题逻辑语言来理解和解决数学和逻辑问题。

目录

命题逻辑语言：字母表和符号串
从一个符号开始
然后添加第二个符号
命题逻辑语言：句法
句法审查示例
符号约定
元变量与连接词\downarrow
联合否定的使用示例
重排与括号
派生连接词
命题逻辑表达式的发音
命题逻辑语言的总结与反思
理解一切背后的“矩阵”

命题逻辑语言：字母表和符号串

从一个符号开始

为了构建命题逻辑语言，我们将从最简单的字母表开始：一个仅包含一个符号的字母表。符号的形状并不重要，重要的是它是唯一的。如果我们使用这样的字母表进行书写，唯一区分符号串的因素就是该符号重复的次数。因此，如果我们能够写出长度为 N 的符号串，我们只能写出 N 个不同的符号串。正如你所见，这个字母表非常有限，没有太多可以说的。

然后添加第二个符号

如果我们为字母表添加第二个符号，书写会比之前的字母表更丰富。现在我们可以观察符号的排列方式，例如，如果 0 和 1 是我们的符号，我们可以区分 01 和 10。两者都包含相同的符号，但顺序不同。如果我们能够写出最长为 N =1,2,3,\cdots 的符号串，那么我们可以写出 2^1=2 个长度为 1 的符号串，2^2=4 个长度为 2 的符号串，2^3=8 个长度为 3 的符号串，以此类推，一般来说， 2^N 个长度为 N 的不同符号串。

练习：在纸上写下所有可能的不同符号串，长度从 1 到 N 不等。总共可以写出多少个符号串？

解答：
如果 S_N 是所有符号串的总和，长度为 1, 2, 3, 等等直到 N，那么我们已经知道：

\displaystyle S_N=2^1 + 2^2 + \cdots +2^{N-1} + 2^N

将上式乘以 2，我们得到：

\displaystyle 2 S_N=2^2 + 2^3 + \cdots + 2^N + 2^{N+1}

因此：

\displaystyle S_N=2 S_N - S_N = 2^N-1

因此，在纸上写下的总符号串数量将是 2^N-1。

命题逻辑语言：句法

我们已经看到，使用两个符号，我们可以通过符号串的长度和符号的排列顺序来区分它们。 这很重要，因为它允许我们为构建的字母表定义句法。句法是一组规则，将符号串分为两类：表达式和非表达式。如果 \mathcal{L}_2 是可以用符号 0 和 1 构建的所有符号串的集合，那么 \mathcal{L}_2 的句法是一个子集 \mathcal{SL}_2\subset\mathcal{L}_2。

我们可以通过以下递归规则定义集合 \mathcal{SL}_2：

  1. 00, 11 \in \mathcal{SL}_2
  2. 如果 \alpha, \beta \in \mathcal{SL}_2，则 01\alpha\beta \in \mathcal{SL}_2

通过这两个规则，我们可以构建语言的表达式，并验证给定的符号串是否为语言的表达式。语言是具有相关句法的字母表。我们将这里介绍的语言命名为“二符号基础语言”，或 \mathcal{B}_2。

句法审查示例

为了更容易理解这些概念，让我们来看以下示例：

示例： 鉴于 0000 和 1111 包含在 \mathcal{SL}_2 中，因此 0100 00 01 0011 01 110000 和 0111111111 都在 \mathcal{SL}_2 中；因此，它们是 \mathcal{B}_2 的表达式。这可以通过我们刚刚介绍的规则来证明。

示例结束 \blacksquare

练习： 在前面的示例中，我们看到了如何从其他两个基本表达式构建表达式。这并不复杂；然而，逆向过程，即证明某个表达式是否为表达式，可能会更具挑战性。

请根据句法规则确定以下符号串是否为 \mathcal{B}_2 的表达式：

  1. {}012100

  2. 101100

  3. {}0100010000

  4. 0101000011

  5. {}01010000010000

  6. 01010010000100101000011

解答：
在查看解答之前，我建议你先自己尝试一下，然后再比较结果。如果你已经完成了，那么继续👍

  1. 012100.

    正如我们所见，它包含符号 2，该符号不包含在 \mathcal{L}_2 中；因此，此符号串不能包含在 \mathcal{SL}_2 中，因此不是 \mathcal{B}_2 的表达式。

  2. 101100.

    这里可以看出，这个符号串以 10 开头。根据句法规则，我们可以推断出，所有长度超过 2 的符号串必须以 01 开头，因此它不能是 \mathcal{B}_2 的表达式。

  3. 0100010000

    这个符号串以 01 开头，因此通过了第一个测试。为了使其成为 \mathcal{L}_2 的表达式，有必要将蓝色标记部分唯一地分解为两个表达式。

    0100010000

    如果即使遵循句法规则，分解仍然不是唯一的，那么定义的句法是模棱两可的，因此必须进行修正。

    分析蓝色部分，可能的分解如下：

    000100000001000000010000
    000100000001000000010000
    00010000

    在这部分，我们需要注意，如果金色部分不是 0000 0 1111，那么相应的蓝色部分必须以 01 开头，以确保整个符号串是表达式，因此可以进行以下排除

    0{}0010000❌00010000✅000{}10000❌
    00010000❌00010000❌00010000❌
    00010000❌

    因此，唯一通过分析的分解是 00010000，其中金色部分是一个表达式，蓝色部分可以唯一且符合句法地分解。最后，符号串 0100010000 允许唯一且符合句法的分解，即 0100010000，因此它是语言 \mathcal{B}_2 的表达式。

  4. 0101000011

    对于这个符号串，我们可以做以下分解，用颜色标记：

    010100001111

    根据句法规则，长度超过 2 的符号串必须以 01 开头，然后必须跟随两个表达式，分别用蓝色和金色标记。很容易看出，这个分解是唯一的，因为如果蓝色或金色部分的长度发生变化，无论是什么变化，两部分都不会同时是表达式。

  5. 01010000010000

    从右向左检查，我们可以找到以下分解：

    \underbrace{01\underbrace{01\overbrace{00}\overbrace{00}}_{{表达式}}\underbrace{01\overbrace{00}\overbrace{00}}_{{表达式}}}_{{表达式}}

  6. 01010010000100101000011

    敏锐的眼睛会注意到，这个符号串的长度为 23，而根据 \mathcal{L}_2 的句法规则，不可能构建长度为奇数的符号串，因为它通过并置长度为偶数的符号串构建表达式。\mathcal{SL}_2 的所有符号串都具有偶数长度，因此 01010010000100101000011 不是 \mathcal{B}_2 的表达式。

练习结束 \blacksquare

一块解码符号的石板

符号约定

使用 0 和 1 可能会使我们感到困惑 并导致我们犯错误。为了让过程更符合人类的理解方式，我们可以使用符号约定和一些元符号。

元变量和连词 \downarrow

元符号是用于表示目标语言符号串的符号。 例如，当定义 \mathcal{SL}_2 的句法时，使用了符号 \alpha 和 \beta 来表示 \mathcal{B}_2 的表达式。这些符号被称为 \mathcal{B}_2 的元变量： 元符号，当它们全部被语言表达式取代时，通过句法生成另一个语言表达式，正如我们之前讨论的关于 \mathcal{SL}_2 元素的第二条规则所示：

如果 \alpha,\beta \in \mathcal{SL}_2，则 01\alpha\beta \in\mathcal{SL}_2

因此，这些元变量被称为 \mathcal{B}_2 的元表达式。

为了简化我们的写作，我们将使用元符号 \downarrow 来表示符号串 01。这个元符号是我们所谓的 连词，由于语义原因，它被称为 联合否定。

通过这种方式，我们可以通过以下递归规则，以元语言表达 \mathcal{SL}_2 的句法：

  1. 所有 \mathcal{B}_2 的元变量都是 \mathcal{B}_2 的元表达式。

  2. 如果 \alpha 和 \beta 是 \mathcal{B}_2 的元变量，那么 \downarrow\alpha\beta 是 \mathcal{B}_2 的元表达式。

通过这些规则，我们可以编写元表达式，当它们的所有元变量都被表达式和 连词 以 0 和 1 的形式表示时，便生成了 \mathcal{B}_2 的表达式。这种类型的每个元表达式都代表了一个无限的表达式家族：可以通过该结构表示的所有 \mathcal{B}_2 表达式的集合。这正是拥有形式语言的含义。

联合否定的使用示例

示例： 从元表达式 \downarrow\alpha\downarrow\beta\gamma 可以通过替换得到以下表达式：

  1. 替换 \alpha := 00，\beta := 011100 和 \gamma := 010011

    得到表达式：

    010001011100010011

  2. 如果我们替换 \alpha := 011100，\beta := 0111011100 和 \gamma := 0111010011

    生成：

    010111000101110111000111010011

元表达式 \downarrow\alpha\downarrow\beta\gamma 不仅比任何其他符合其形式的表达式更容易理解，而且它还代表了所有可以通过替换其元变量得到的表达式。

示例结束 \blacksquare

当替换元变量时，需要在所有出现的地方替换。

示例： 考虑元表达式 \downarrow\downarrow\alpha\beta\downarrow\alpha\gamma

  1. 如果我们替换 \alpha:=11，我们得到：

    \downarrow\downarrow 11\beta\downarrow 11\gamma

  2. 如果我们现在替换 \beta:=011100，结果将是：

    \downarrow\downarrow 11011100\downarrow 11\gamma

  3. 如果我们现在将 \gamma:=011111 进行替换，得到：

    \downarrow\downarrow 11011100\downarrow 11011111

  4. 最后，替换 \downarrow:=01，我们得到以下表达式：

    0101110111000111011111

示例结束 \blacksquare

重新排序与括号

验证这是否是一个元表达式并不是特别困难，但需要时刻关注元符号的数量和连词 \downarrow 的范围。随着元表达式长度的增加，这种困难会迅速增加。因此，有一个合理的问题：是否存在一种更容易验证这些内容的方法？答案是肯定的；事实上，我们可以使用括号和适当的重新排序来更好地适应我们自然的分组方式。为了说明这一点，让我们来审查以下元表达式：

\downarrow\alpha\downarrow\downarrow\alpha\beta\alpha

事实证明，尽管确认这是否是一个元表达式并不特别困难，但我们无法在不数符号的情况下进行操作，而且在这个过程中，我们可能会失去对符号数量的控制，而随着元表达式长度的增加，这种风险也会迅速增加。是否有更便于阅读的方式来表示相同内容？答案是肯定的，这种方法符合我们自然的分组方式。为此，引入括号和重新排序的符号约定如下：

\downarrow\alpha\beta:=(\alpha\downarrow\beta)

示例： 让我们考虑元表达式 \downarrow\alpha\downarrow\downarrow\beta\gamma\delta。如果我们应用括号和重新排序的约定，那么它将按如下方式转变：

\downarrow\alpha\downarrow\downarrow\beta\gamma\delta:=\downarrow\alpha\downarrow(\beta\downarrow \gamma)\delta
\downarrow\alpha\downarrow(\beta\downarrow \gamma)\delta:=\downarrow\alpha((\beta\downarrow \gamma)\downarrow\delta)
\downarrow\alpha((\beta\downarrow \gamma)\downarrow\delta):=(\alpha \downarrow((\beta\downarrow \gamma)\downarrow\delta)) ✅

最后的这个元表达式比原始表达式更容易阅读和检查，因为每个括号块都是由易于区分的元素组成的元表达式：一个在中心的联合否定符号和两边的元表达式。

示例结束 \blacksquare

衍生连词

在逻辑和数学中，存在某些连词组合被频繁使用。为此，为了使书写更加方便（对于人类而言），通过以下符号约定引入了衍生连词：

否定：\neg \alpha:=(\alpha\downarrow\alpha)
或运算（包含性“或”）：(\alpha \vee \beta):=\neg(\alpha\downarrow\beta)
与运算：(\alpha \wedge \beta):=\neg(\neg\alpha\vee \neg\beta)
蕴含：(\alpha \rightarrow \beta):=(\neg\alpha\vee \beta)
双向蕴含：(\alpha \leftrightarrow \beta):=((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha))
异或：(\alpha \veebar \beta):=\neg(\alpha\leftrightarrow \beta)

我们在两个符号基础语言之上构建的这种元语言就是所谓的命题逻辑的零阶语言。通过这种语言，可以精确地且无歧义地表示命题逻辑的所有表达式。

命题逻辑表达式的发音

虽然逻辑推理不一定需要发音，但我们需要认识到我们的交流不仅仅依赖于书面符号，我们也倾向于在自然语言中将事物发音。因此，命题逻辑语言的表达式有其发音，能够唤起类似于命题逻辑中其对应表达式所表达的想法。以下是这些发音：

(\alpha \downarrow \beta)既不\alpha也不\beta
\neg \alpha否定\alpha
(\alpha \vee \beta)\alpha或\beta
(\alpha \wedge \beta)\alpha与\beta
(\alpha \rightarrow \beta)\alpha蕴含\beta
(\alpha \leftrightarrow \beta)\alpha当且仅当\beta
(\alpha \veebar \beta)要么\alpha，要么\beta，但不是两者

命题逻辑语言的总结与反思

通过最后这部分，我们完成了命题逻辑语言的构建，可以将其总结为一种元语言，能够在两个符号的基础语言中得到有效表达。命题逻辑语言是一种形式语言，因为它定义了基础语言表达式的结构（或形式），并且其每个表达式决定了基础语言中无限多的表达式形式。正如前面提到的，形式语言的语法极其严格，但作为交换，它具有精确性和无歧义性。

理解一切事物的 Matrix 背后的 Matrix

最后一件事。命题逻辑和数学在很大程度上依赖于命题逻辑，而命题逻辑是建立在由 0 和 1 组成的基础语言之上的。这是否意味着我们已经触及了逻辑和数学背后的“Matrix”？这是有可能的。但也有可能为基础语言考虑一种基础语言，通过它可以重建所有其他内容；然而，要找到这种语言，我们需要找到比秩序和数量概念（用于建立第一种基础语言的概念）更为基本的概念。寻找基础的基础语言意味着要对“理解事物”的最基本方面进行反思。如果你深入下去，如果你能够到达底部，我们可以说你已经看到了“理解一切事物的 Matrix 背后的 Matrix”，而且这种基础的反思过程可能会无限地继续进行，在每个基础步骤中赋予知识更深一层的深度。

Views: 2

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注