命题逻辑的语言 · Topos Uranos

摘要

本课从零开始构造本课程所有公式将要使用的语言。它首先介绍集合中不可或缺的内容（属于关系、用列举法和描述法给出的集合、包含与并集），并将其应用于符号串：符号串的长度、连接和前缀，以及用两个符号可以写出的符号串的计数。在由圆圈和圆盘这两个符号组成的字母表上，它定义基础语言：无穷多个变元、唯一一条形成规则和一个封闭条款，由该条款可推出一条用来证明所有公式之性质的原理。随后它说明如何判定一个符号串是否为公式，陈述唯一可读性，最后在基础语言之上构造今后使用的元语言：元变元、用括号书写的或非，以及其余联结词的正式缩写及其中文读法。

学习目标

用列举法和描述法描述符号串的集合，并判定它们之间的属于、包含与并集关系。
在含两个符号的字母表上，计数给定长度的符号串以及长度有界的符号串。
判定一个由圆圈和圆盘组成的符号串是否为公式，并在它是公式时重建其形成方式。
借助封闭原理证明所有公式都具有某一性质，并利用这些性质排除符号串。
区分对象语言与元语言，把一个缩写展开为基础语言的符号串，并用中文读出公式。

集合方面所需的知识

形式语言首先是一些符号串的汇集：如果是这样，要准确地谈论它，就需要一套谈论汇集的词汇。这套词汇就是集合的词汇，本课只取其中本课程要用到的部分。集合是一些对象的汇集，这些对象称为它的元素，集合由其元素决定：元素相同的两个集合是同一个集合。对象 $a$ 是集合 $A$ 的元素，记作 $a \in A$ ，读作“ $a$ 属于 $A$ ”；不是它的元素，记作 $a \notin A$ 。

集合有两种给出方式。一是列举法，在花括号中逐一列出它的元素，顺序和重复都无关紧要；二是描述法，陈述其元素满足而且只有其元素满足的条件，其中的冒号读作“使得”。例如，小于 $5$ 的自然数构成集合

\{1, 2, 3, 4\} = \{ n \in \mathbb{N} : n < 5 \}

描述法的一种变体在后文中十分常见，它按元素的形式来描述元素： $\{ 2n : n \in \mathbb{N} \}$ 是形如 $2n$ （ $n$ 为自然数）的数的集合，即偶数集。用列举法给出的集合必定是有限的；用描述法还可以给出无限集合，例如偶数集。

说 $A$ 包含于 $B$ ，记作 $A \subseteq B$ ，是指 $A$ 的每个元素都是 $B$ 的元素。由此可知，两个集合相等当且仅当每一个都包含于另一个，因为这时它们的元素相同；这确实是证明集合相等的通常方法：证明两个包含关系。最后，并集 $A \cup B$ 是属于 $A$ 、属于 $B$ 或同时属于两者的对象所成的集合；因此两个集合都包含于它们的并集。

例题属于、包含与并集

设 $A = \{1, 2, 3\}$ ， $B = \{2, 4, 6, 8\}$ ， $P = \{ 2n : n \in \mathbb{N} \}$ 。则 $2 \in A$ ， $4 \notin A$ ；此外 $B \subseteq P$ ，因为 $B$ 的每个元素都是某个自然数的两倍，而 $A$ 不包含于 $P$ ，因为 $1 \in A$ 而 $1 \notin P$ 。 $A$ 与 $B$ 的并集是 $\{1, 2, 3, 4, 6, 8\}$ ：两者共有的 $2$ 只出现一次。