cover

作者: 邢滔滔 
出版社: 北京大学出版社
出版年: 2008-8
页数: 274
定价: 28.00元
装帧: 简
ISBN: 9787301112557

第1章绪论：从直观到形式
第2章集合
第3章一阶语言的语形
第4章经典语义学
第5章自然推演系统
第6章可靠性与完全性

第1章绪论：从直观到形式

1.从“矛盾”说起

同时肯定和否定同一个主张就是矛盾，而不管这个主张是什么。
我们有一条普遍的形而上学原则，即所有的矛盾都不可能为真。
这条“（不）矛盾律”同时是我们思想的“最确定的推理原则”或规则，这条规则说：如果你从一个主张推出了矛盾，你就要否定这个主张。后来的西方人把这条思想规则称为“reductio ad absurdum”（RAA）。

2.直观上地推理

把句子的意义，或表达在句子之中地思想称为命题。命题有真假。

推理是一组命题，其中之一（称为结论）是从其他的（全部或部分）命题（称为前提）推出的，而这个“推出”关系，表现为某种结构。

3.正确推理

一个正确的推理，说的是它的前提和结论之间有某种确定的关系。

3.1 合规则性

所有这样的都是那样的。某某是这样的。
------
某某是那样的。

这是一个推理规则。一般而言，一个推理规则首先明确一个基本推理地形式，然后规定：具有这种形式的推理都是合乎此规则地。

若干推理规则组成一个逻辑系统。一个推理地每一步（其中的每个基本推理）如果都合乎这个系统中地某个规则，则称这个推理在这个系统中是合规则的，否则称它在其中不合规则。

对于一个推理系统而言，一个推理是正确的，当且仅当它在这个系统中是合规则的。

正如推理由命题组成，推理形式也是由命题形式组成的，而命题形式是由相应的命题表达式通过删除一些“有实义的”部分（即容许这些部分用其他的同类语言单位替换）构成的。

把命题形式中的代词换成一些变项符号，如把“某某”换成x，把“这样的”换成A，把“那样的”换成B等等。命题形式中未经变项替换的部分（如“所有的”），称为逻辑常项。

借助变项表示：

所有A都是B。x是A。
------
x是B。

因此，一个推理，如果把其中作前提和结论的命题分别代换成相应的命题形式，就得到这个推理地形式。

亚里士多德建立的三段论学说：

所有的S都是P。（全称肯定）
所有的S都不是P。（全称否定）
有些S是P。（特称肯定）
有些S不是P。（特称否定）

其中的逻辑常项是：“所有的”（全称量词）、“有些”（存在量词）、“是”和“不是”，而命题的主项和谓项是可以替换的。对于“韩非是人”、“这支矛不能刺破这张盾”这类的单称命题，传统逻辑把它们分别归到全称肯定和全称否定的形式里。这称为命题的主谓形式分析。

一般地，从每一个推理形式都能够类似地得到一些具体推理，而每一个这样得到的具体推理就叫做这个形式的一个实例，这个形式也称作它的诸实例的一个模式。

肯定前件式或分离规则：

如果p，则q；p
------
q

否定后件式：

如果p，则q；非q
------
非p

排中律：从任何前提都能推出形如“p或者非p”的结论。

3.2 有效性

从语义上判断一个推理是否正确，要看它的前提如何支持它的结论。前提100%支持结论地，我们称为有效的推理，否则称为非有效的。研究推理的有效性的称为演绎推理。与演绎推理相对的研究领域一般称为归纳推理，它关心前提对结论地不同支持程度。本书不讨论归纳逻辑，凡提到“逻辑”之处，皆指演绎逻辑。

我们把在任何可能得情形中都没有真实例的命题形式称为矛盾式，把矛盾式的实例称为逻辑上假的命题（或矛盾）。反之，在任何可能的情形中都只有真实例的命题形式是有效式，有效式的实例是逻辑上真的命题。

4.一阶语言

4.1 命题成分

命题中指称个体的成分为个体项，表达性质和关系的成分为概念。像“韩非”、“这支矛”等专名和确定指示词指称确定的个体，因此是个体项。概念的特点是，它们具有“空位”，当空位被确定的词项填充进去，我们就得到一个完整的命题。如概念“…是哲学家”有一个空位，用专名“亚里士多德”填充后，我们得到“亚里士多德是哲学家”这个命题，它表达一个确定的个体具有某个确定的性质；概念“…喜欢…”有前后两个空位，用名字“韩非”与“这支矛”分别填充后，我们得到“韩非喜欢这支矛”这个命题，它表达两个确定的个体具有某个确定的关系。关系可以是二元、三元…n元的（称为n元概念）。一个典型的二元概念是等同，就是“…等于…”，我们把一个个体的性质也称为一元关系。

对命题的这种个体项——概念式分析不同于传统逻辑的主-谓式分析，后者只讲性质。把“这支矛能刺破这张盾”这样的关系命题仅分析为“这支矛”具有“能刺破这张盾”这个性质。这种分析表达力较弱。

称“所有的”为全称量词，“有些”称为存在量词。变项x是个体变项。

我们一般用+和·分别表示加法和乘法，它们称为函数符号。这里的函数是某种运算，一元函数施于一个对象之上，n元函数施于n个对象之上，“变换”出一个对象（函数值）。

用命题联结词从已有命题构造出复合命题。

上述命题，总体上说，表达的是个体具有什么性质及个体间具有什么关系，我们称这类命题为一阶命题。一阶命题描述的世界，由个体、性质和关系（包括函数）组成，大部分的数学“世界”正是这样组成的，我们日常的世界，在某种哲学观点下也可以“看成”是这样组成的。

4.2 外延性与真

韩非、亚里士多德等个体分别例示了“…是人”这个性质；反过来，每个性质规定或“挑出”一些个体，就是那些例示了这个性质的个体，如“…是人”这个性质挑出了韩非、亚里士多德等个体。

性质“…是一只狗”和“…是你喜爱的动物”挑出了同一些个体，而这两个概念具有相同的外延，但这两个性质或概念显然是不同的。

在任何一阶命题里，都可以将具有相同外延的概念或具有共同指称的名字相互替换而不改变这个命题的真假。这是因为，一阶命题的真假只与个体是否例示关系有关，而与如何指称个体或如何表达关系无关。在这个意义上，只涉及一阶命题的语言是外延性的。

因此，对概念来说，我们可以忽略它的非外延方面的内容，而只考虑它所涉及的那些个体或个体序列。这种抽象的结果，逻辑学家称为集合。集合作为概念的外延，包含了性质或关系挑出的个体或个体序列。

一个集合所包含的东西，称为这个集合的元素。a是集合A的元素，记作$a \in A$。

集合的外延性原则：如果集合A与集合B包含相同的元素（就是说，对任意的x，$x \in A$当且仅当$x \in B$），则A与B就是同一个集合。

“…是一只狗”和“…是你喜爱的动物”，虽然是不同的概念，但作为集合，是同一个东西。

这样建立的集合概念恰好解释了命题的真假：命题“韩非是人”为真的充分必要条件，不需要再表述为韩非这个个体例示了性质“…是人”，而只要表述为这个个体属于这个性质决定的集合。

4.3 一阶符号语言

推理的有效性只与命题的真假有关，而命题的真假又只由个体的集合来决定，所以，探讨有效性问题就只需要关注集合和个体。这要求我们设计一种专供逻辑使用的语言，使其中的句子不再描述个体具有什么性质或关系，而描述个体或个体序列属于什么集合。就是说，这个语言中的“概念”不再表示个体的性质和关系，而表示个体或个体序列的集合，这个语言中的“名字”也不再有涵义，而只是指称。这个语言的句子，因此表达而且只表达一阶命题的真假。

语言首先需要以下这些词汇：

（对应于名字）个体常项：a,b,c等，它们指称论域里某些特定的个体；
（对应于概念）谓词：F,G,H等，表达论域中那些个体的集合和合体序列的集合；
函数符号：f,g,h等，表达论域上的函数；
个体变项：x,y,z,u,v,…；
全称量词$\forall$和存在量词$\exists$，它们使用在论域的个体之上；
真值联结词：$\lnot,\land,\lor,\to$

表达一阶命题（的真假）的，称为公式。1-3称为非逻辑符号；4-6称为逻辑符号。所有这些符号组成一个语言的字母表。

当一个（一些）公式经解释后在一个结构中为真时，我们称这个结构为这个（这些）公式的模型。

任意一个一阶语言中，设$\Phi$为一组公式，$\varphi$为一个公式，我们用$\Phi \models \varphi$表达如下事实：$\Phi$的任何模型都是$\varphi$的模型。此时我们称$\varphi$是$\Phi$的语义后承。显然$\Phi \models \varphi$放在直观背景下来理解，它说的恰好是：从前提$\Phi$到结论$\varphi$的推理是有效的。

5.推演系统

5.1 公式模式与推理规则

自然语言中的推理：

7)所有跟亚里士多德同时代的人都是哲学家。 韩非是跟亚里士多德同时代的人。
------
韩非是哲学家。

在$L_1$中就“翻译”成如下推理：

7’)

\[\forall x(G(x,b) \to F(x))\ G(a,b)\]

\[F(a)\]

我们用变项$\alpha,\beta$等代表$L_1$中的那些个体常项，用变项$\pi,\gamma$等代表其中的谓词，则7)中的三个命题的形式以及它们组成的推理形式就可以表达城：

7’’)

\[\forall x(\pi(x,\beta) \to \gamma(x))\ \pi(\alpha,\beta)\]

\[\gamma(\alpha)\]

注意，$\alpha,\beta,\pi,\gamma$等不是一阶语言中的符号，而是我们为了讨论一阶语言的公式形式而使用的变项。因此，7’‘)中的那些符号序列不是一阶公式。这里出现了两个层次的语言，一是一阶语言（在这里具体是$L_1$），它是我们眼下讨论和研究的对象，称为对象语言；另一个是我们讨论对象语言时使用的语言，就目前情形而言，它是汉语加上一些特别的符号（包括$L_1$中的逻辑符号），这称为元语言。

7’‘)中的三个元语言公式，我们称为7’)中相应的$L_1-$公式的模式。这跟前面介绍的模式概念是统一的。一般而言，一个公式模式是用元语言变项替换一个公式中的非逻辑符号而得到的，这个公式是这个模式的一个实例。

5.2 形式推演系统

假定我们选定了一个推演系统$\Im$。在任意一个一阶语言中，从一组给定的前提$\Phi$出发，经过一些列（有穷的）推理步骤，若每一步都合乎$\Im$的一个规则，而最后得到公式$\varphi$，我们就称这个过程是前提$\Phi$在$\Im$中对结论$\varphi$的一个推演。

如果在$\Im$中存在从$\Phi$到$\varphi$的一个推演，则称$\Phi$在$\Im$中可推演$\varphi$，记作$\Phi \vdash_\Im \varphi$。此时我们也称$\varphi$是$\Phi$的语形后承。

要求每一个推演都满足下面的条件：

必须在有穷步内完成。
我们可以能行地检验推演中每一个推理步骤是否合乎系统的某个规则。
推演的前提与结论可以能行地找出来。

满足这些条件的证明系统称为形式推演系统。

如果在L中以下1~4都是能行可判定的，则称L是一个形式语言。

任意一个符号是不是L的符号；
L中任意符号是一个逻辑符号还是非逻辑符号；
L中任意符号是哪一类逻辑符号或非逻辑符号；
任意符号序列是不是一个L-公式或其组成部分。

我们要建立这样一个形式推演系统：对任意给定一个一阶形式语言L，

它的规则在L中产生且仅产生有效推理地实例，这就是说，对任何L-公式集$\Phi$和公式$\varphi$，如果$\Phi \vdash \varphi$，则$\Phi \vDash \varphi$；
L中所有有效推理的实例，都可以用系统的规则产生，换言之，如果$\Phi \vDash \varphi$，则$\Phi \vdash \varphi$。

第一点称为系统的可靠性，第二点称为完全性。两者合起来就是这样一个要求：$\Phi \vDash \varphi$，当且仅当$\Phi \vdash \varphi$。这表明了语形后承和语义后承这两个概念（在外延上）的重合，精确解释了推理地合规性和有效性相互吻合的直观思想。一阶逻辑的这个结果，由哥德尔（Godel，1930）证明。

莱布尼茨将推理变成计算的思想，大概还蕴涵着这样一个要求：有一个机械过程，对任意的$\Phi$和$\varphi$，都可以能行地判定$\Phi \vdash \varphi$是否成立。这个要求称为系统的可判定性。但丘奇（A.Church,1936）证明，一般而言，形式推演系统不具有可判定性。与此相关的还有著名的哥德尔不完全性定理，它表明形式化的算术理论不能穷尽真算术命题。这些是形式化的代价，其中的哲学意义也许可以这样表述：当我们从直观一步步走向形式，确定性和清晰性都逐步加强，但直观方面的一些内容却不可避免地损失掉了。”

第2章集合

1.集合（不）是什么？

只有一个元素的集合，称为单元素。

一般而言，如果$\varphi(x)$表示一个性质，则我们就用${x

\varphi(x)}$表示所有具有此性质的元素的聚合，换言之：任给x,$x \in {x

\varphi(x)}$当且仅当x满足$\varphi$（即$\varphi(x)$成立）。

直观上看来，对任意一个集合，我们似乎可以设计一个概念来表述它；而任意一个概念，也似乎决定一个集合。这与弗雷格的观念（集合是概念的外延）吻合。

不含任何元素的集合称为空集。空集A因此是这样的集合：对任意的x，都有$x \in A$。

给定集合A与B，如果对任意x，$x \in A$当且仅当$x \in B$，则A=B。这即是外延性原则，它给出了集合的同一性条件。外延性原则保证了空集是唯一的。

1.1 定义：集合A是集合B的子集，记为$A \subseteq B$，当且仅当对任意的x，如果$x \in A$，则$x \in B$。

如果$A \subseteq B$且$A \ne B$，则称A是B的真子集，记为$A \subset B$。

集合的确定性原则：对任意的对象x和任意的集合A，$x \in A$或$x \notin A$。

在一个语言里，如果不仅允许量词使用在个体之上，而且允许它们使用在个体的性质和关系之上，则这个语言就不仅能谈论个体有什么性质（关系），而且能谈论个体的性质或关系有什么性质或关系。这称为二阶语言，研究其中推理的，称为二阶逻辑。二阶语言的论域里面不仅有个体，还有个体的集合。

1.3 定义：设A是集合，称集合${X X \subseteq A}$为A的幂集,记为$\mathcal P(A)$。直观上说，一个集合的幂集就是这个集合的所有子集的集合。

1.5 定义：给定集合A和B，

称集合${x x \in A\ or\ x \in B}$为A和B的并集，记为$A \cup B$
称集合${x x \in A\ and\ x\in B}$为A和B的交集，记为$A \cap B$
称集合${x x \in A\ and\ x \notin B}$为A和B的差集，记为A - B。

两个集合的并集和交集运算可以推广到任意多集合上。其元素都是集合的集合叫集合族。设A是一个集合族，我们

A的并，记作$\cup A$，它是A中所有元素的并；
A的交，记作$\cap A$，它是A中所有元素的交。

集合是某种统一体，是由“多”聚成的“一”。按照一种朴素的哲学观念，当我们用一个概念（谓词）“把握”了多个东西之后，这多就同时成了作为思想对象的一。

用上述观念解释康托尔，就似乎有以下结论：

每个集合都有一个定义它的谓词；
每个谓词都决定一个集合（其元素是所有满足这个谓词的对象）

现在人们意识到，这两点恐怕都错了，且都不是康托尔的原文。我们着重谈第二点，因为这是弗雷格关于每个性质决定一个集合的想法的另一种表述。文献上称这个想法为一般概括原则，它说的是：

对任意性质词$\varphi$，存在一个集合S，它的元素是所有满足这个性质的对象，即$S={x

\varphi(x)}$。

1902年，罗素给弗雷格写了一封信，说明当$\varphi$表达某种集合的性质时，这个原则导致了矛盾。其推论如下：

1.7 罗素悖论：令$\varphi$为$X \notin X$。根据上述原则，存在集合$S={X

X \notin X}$，即对任意X，$X \in S$当且仅当$X \notin X$。特别地，$S \in S$当且仅当$S \notin S$。矛盾。

直观上看，这里的$\varphi$表达性质“…不属于自身”，而S相当于所有不属于自身的集合的“集合”。如果$X \in S$，则根据S的定义，S有“…不属于自身”这个性质，即$S \notin S$；另一方面，如果$S \notin S$，则S具有“…不属于自身”这个性质，再根据S的定义，$S \in S$。所以，$S \in S$当且仅当$S \notin S$。矛盾。

不能简单地说集合是概念或谓词的外延，有的概念的外延不是集合，有的性质不对应任何集合，这是集合概念深藏不显的特性之一。

既然概念的外延不全是集合，一种处理方式是把概念的外延统称为类。有的类是集合，有的不是，不是集合的类（如罗素悖论里的S），叫做真类。

我们仍然无法解决关于性质的罗素悖论：有的性质能例示自身，如“…是抽象的”（“…是抽象的”这个性质是抽象的），有的不能，如“…是人”（“…是人”这个性质不是人）。”

2.关系

一般而言，给定任意n($\ge 1$)个对象$x_1,x_2,\cdots,x_n$，我们都可以构造一个有序n元组（或n元组）$x_1,x_2,\cdots,x_n$，其中的诸$x_i$不必不同，n称为这个有序组的长度。

规定：$<x_1,x_2,\cdots,x_m>=<y_1,y_2,\cdots,y_n>$当且仅当m=n且$x_1=y_1,x_2=y_2,\cdots,x_n=y_n$。

这就是说，有序组被其长度、构成对象及其顺序所决定。

如果R是一个n元关系，那么对任何的$<x_1,x_2,\cdots,x_n> \in R$，称$x_1,x_2,\cdots,x_n$具有关系R。特别对二元关系来说，如果存在集合A，B，使得对任何的$<x,y> \in R$，都有$x \in R,y \in R$，则称R为从A到B的关系。

集合{x 存在y，使得$<x,y> \in R$}叫做关系R的前域；
集合{x 存在y，使得$<y,x> \in R$}叫做关系R的后域。

集合${<x,y> x \in A,y \in B}$，称为集合A和B的笛卡尔积，记为$A \times B$。

直观上，$A \times B$就是把A中所有元素与B中所有元素一一配成有序对而组成的二元关系。显然，任何从A到B的关系，都是$A \times B$的子集。这使得我们可以把“R是从A到B的二元关系”简单地表示成：$R \subseteq A \times B$。

如果A=B，则称R是A中的一个二元关系。

设$n \ge 1,A_1,\cdots,A_n$是集合，则笛卡尔积$A_1 \times A_2 \times \cdots \times A_n={<x_1,x_2,\cdots,x_n>

x_1 \in A_1,x_2 \in A_2,\cdots,x_n \in A_n}$。

若$A_1=A_2=\cdots=A_n=A$，则 $A_1 \times A_2 \times \cdots \times A_n$就简记为$A^n$。如果关系$R \subseteq A^n$，则称R为A中的一个n元关系。

2.1 等价关系

2.1.1 定义：设R是集合A中的二元关系。

R是A中的自反关系，如果对于任意的$x \in A$，都有xRx。
R是A中的对称关系，如果对任意的$x,y \in A$，若xRy则yRx。
R是A中的传递关系，如果对任意的$x,y,z \in A$，若（xRy且yRz）则xRz。

2.1.3 定义：集合A中的二元关系R是A中的等价关系，如果R是A中的自反关系、对称关系和传递关系。

2.1.4 定义：令R是集合A中的一个等价关系，a是A的一个元素。称A的子集${x x \in A\ and\ aRx}$为a生成的R-等价类，记为$[a]_R$。

2.1.5 引理：令R是集合A中的一个等价关系。那么，对所有$x,y \in A$，如果$y \in [x]_R$，则$[x]_R = [y]_R$。

因此，一个等价类的所有元素都是“平等的”，它们都生成同一个等价类，其代表元可以在这个等价类中任意选取。

2.2 序关系

2.2.1 定义：集合A中的一个二元关系R是反对称的，如果对任意的$x,y \in A$，若(xRy 且 yRx)则x=y。

反对称关系的一个明显例子是自然数集N中的$\le$关系。

2.2.2 定义：集合A中的二元关系R称为A中的一个偏序，如果R是A中的自反、反对称和传递关系。

对于$x \in A$，如果不存在另一个$y \in A$，使得yRx，则称x为此偏序的一个极小元。
对于$x \in A$，如果不存在另一个$y \in A$，使得xRy，则称x为此偏序的一个极大元。

2.2.4 定义：集合A中的一个偏序R称为全序（或线性序），如果对任意$x,y \in A$，xRy和yRx必有一个成立。

自然数集N中的$\le$不仅是偏序，也是全序。
树是偏序。

2.2.7 定义：集合A中的一个偏序R称为一棵树，如果它有唯一的极小元a，而且对任意$x \in A$，{y yRx}中的R是全序。

A中元素称为此树的结点，极小元a称为此树的根。
A的一个子集B是一条枝，如果
1. $a \in B$；
2. B中的R是全序；
3. B是满足(1)和(2)的最大子集。
枝上的极大元素称为此树的叶。”

3.函数

3.1 定义：令A和B为非空集合。从A到B的二元关系R称为从A到B的函数，当且仅当

对任意的$x \in A$，都有$y \in B$，使得xRy；
如果存在$y,z \in B$，使得xRy并且xRz，则y=z。

A到B的函数f经常表示为:$f:A \to B$，a是A中的元素，f把a与B中的一个元素对应起来。

B中的这个元素，称为f在a处的函数值，记为f(a)；
A称为f的定义域；
f在A上的函数值都在B中，称这些函数值的集合为f的值域。

如果f的定义域是笛卡尔集$A_1 \times A_2 \times \cdots \times A_n,n \ge 1$，则称f为一个n元函数（或A中的n元计算）。

设f是从A到B的函数，如果还有一个从B到C的函数g，则我们可以定义g和f的复合函数gf。

3.2 定义：设$f:A \to B$

如果f的值域等于B，即任给$y \in B$，都有$x \in A$，使得f(x)=y，则称f为A到B的满射。
如果对任意的$x,y \in A$，若f(x)=f(y)则x=y，即f的定义域中不同的元素对应于值域中不同的元素，则称f为A到B中的单射，会一一映射。
如果f既是满射又是单射，则称f为A到B的双射，或一一对应。

一个A到B的双射f，建立了A和B的元素之间一对一的关系。这个关系，如果反过来考虑，则构成了B到A的双射。这就是说，有一个函数g，定义在B上，对任意的$y \in B,g(y)=A$中唯一的那个x，使得f(x)=y。这样的g，称为f的反函数，记为$f^{-1}$。”

4.可数集与不可数集

把一个集合的“大小”叫做A的基数，记为|A|。于是，集合A和集合B“一样大”就表为：|A|=|B|，这称为A和B等势，其定义就是：存在A到B的双射。

4.1 引理：集合间的等势是一种等价关系。

一个集合，若与自身的一个真子集等势，就称为无穷集，否则称为有穷集。

集合A是有穷的，当且仅当，或者A是空集，或者存在自然数n，使得{0,1,2,…,n}与A之间有双射。

A的大小有两种可能。一种是A与N本身等势，比如N与自身等势，偶数集与N等势等。这样的A称为可数无穷的，其元素可以列为：$a_0,a_1,a_3,\cdots$。另一种可能是，A与N之间没有一一对应，这样的A，其基数大于N的基数，不能用N来映满，称为不可数的。借用这些术语，可以把全部集合分为可数的与不可数的两个部分：可数的集合，包含全部可数无穷集合有穷集，其他是不可数集合。

4.4 定义：集合A是可数的，当且仅当，或者A是空集，或者存在从N到A上的满射f。

4.6 引理：设非空集合A是可数的，集合$B=\cup{A^n

n \ge 1}$，则B是可数无穷的。

4.7 定理：有些集合是不可数的。

证明：考虑由0、1两个数字组成的无穷序列，如01001110101…，令A为这样的序列的集合。我们用归谬法证明，A是不可数的。就是说，我们先假设A是可数的，然后从这个假设推出矛盾，由此得到这个假设的否定，即A不可数。

设A是可数的。根据可数集的定义，存在从N到A上的满射f。比如说，我们有以下的枚举：

f(0)=100011010100...
f(1)=011100000001...
f(2)=110011001111...
f(3)=100000111000...

注意等号右边的这个阵的对角线上的数字，即f(0)的第1个、f(1)的第2个…f(n)的n+1个…数字，它们组成一个无穷序列（在上面的例子里，这个序列是1100…）。把这个序列里的每个0换成1，每个1换成0，我们又得到一个新的无穷序列$\alpha$（在上面的例子里，这个$\alpha$序列是0011…）。显然$\alpha$属于A（它是由0、1两个数字组成的无穷序列）。因此f是满射，所以存在自然数m，使得$f(m)=\alpha$。但是，由$\alpha$的构造，我们知道，f(m)的m+1个数字与$\alpha$的第m+1个数字不同，即$f(m)\ne \alpha$。矛盾。因此，最初的假设为假，A是不可数的。

这是著名的康托尔对角线定理，由此得出以下推论：

因为一个由0、1组成的无穷序列$a_0,a_1,a_3,\cdots$可以唯一对应于一个[0,1]区间里的实数a（用二进制表达），所以，对角线定理表明，[0,1]区间里的实数是不可数的（因此实数集也是不可数的）。
一个由0、1组成的无穷序列$a_0,a_1,a_3,\cdots$也可以唯一对应于一个自然数集M，只要令$n \in M$当且仅当$a_n=0$即可。因此，对角线定理又表明，N的幂集$\mathcal{P}(N)$是不可数的。
一个由0、1组成的无穷序列$a_0,a_1,a_3,\cdots$还可以看成对集合{0,1}的一个无穷长（有重复的）枚举，即从N到{0,1}上的一个满射f的值，使得$f(n)=a_n$。显然$a_0,a_1,a_3,\cdots$唯一对应于一个这样的f。因此，对角线定理还表明，从N到{0,1}上的函数的集合是不可数的。”

第3章一阶语言的语形

1.字母表

1.1 定义：一个一阶语言$\mathcal L$的字母表由以下符号组成：

一组非逻辑符号，其中包括：
1. 一个（可能空的）个体常项集；
2. 对每个$n \ge 1$，一个（可能空的）n元谓词集；
3. 对每个$n \ge 1$，一个（可能空的）n元函数符号集。
一组固定的逻辑符号，其中包含：
1. 个体变项$x_0,x_1,x_2,\cdots$（可数无穷多）；
2. 量词$\forall, \exists$；
3. 联结词$\lnot,\land,\lor,\to$；
4. 等词$\equiv$；
5. 括号)，(

进一步要求$\mathcal L$是一个形式语言，就必须要求它的字母集及其每个子类都是能行可判定的，就是说，我们能行的程序来判定下面的问题：任给一个符号，它是不是$\mathcal L$的字母？是不是$\mathcal L$的逻辑符号？是不是$\mathcal L$的非逻辑符号？是逻辑符号的哪一类？是非逻辑符号的哪一类？

形式语言对其字母集（及其每个子类）的大小做了限定，要求它（它们）是可数的。

词项、公式等语言对象的形态最终由字母决定。又因为所有一阶语言有共同的逻辑符号，它们的字母表的差别完全由非逻辑符号决定，不妨把一个一阶语言就简单地看成它的非逻辑符号集。若它的非逻辑符号集是有穷的，我们就说这个语言是有穷的；反之就称这个语言是无穷的。

在谈论一个一阶语言的时候，我们需要一些元语言的变项来代表这个（对象）语言字母表中的任意某类符号。我们约定，在元语言中用

x,y,x等代表一阶语言的个体变项；
c,d,e等代表一阶语言的个体常项；
P,Q,R等代表一阶语言的谓词；
f,g,h等代表一阶语言的函数符号。”

2.归纳定义

一般而言，对一个集合A的归纳定义包含三个步骤：

我们规定某些（不限于一个）特定的元素属于A，这一步叫基始条件。
称归纳条件，它包含有穷的一组条件，其中每个条件涉及一个n($n \ge 1$)元函数f，并规定，对任何$a_1,\cdots,a_n \in A$，函数值$f(a_1,\cdots,a_n) \in A$。
陈述的是封闭条件，它规定A只包含有穷步使用基始条件和归纳条件而得到的元素。

一个集合，如果对它有一个归纳定义，那么我们就可以设计一个有力的证明方法，来证明这个集合的全部元素都有某性质P，这个方法叫做归纳证明：对归纳定义的集合A，要证明任意$x \in A$都有P(x)，我们只要做两步工作：

证明A的基始元素（基始条件确定的元素）都有性质P。这一步称为归纳基始。
证明每个归纳条件涉及的函数都“保持”性质P。就是说，对任意这样的一个n元函数f，证明：如果$a_1,\cdots,a_n \in A$，且$P(a_1),\cdots,P(a_n)$，则$P(f(a_1,\cdots,a_n))$。这一步称为归纳推步，其中的条件——$a_1,\cdots,a_n \in A$且$P(a_1),\cdots,P(a_n)$——称为归纳假设。”

3.项

3.1 定义：对于一阶语言$\mathcal L$，一个$\mathcal L$的符号串 （简称$\mathcal L$-串）是$\mathcal L$的字母表中的符号组成的一个有序n元组($n \ge 1$)，n称为这个$\mathcal L$-串的长度。

我们约定，在元语言中的$\lambda,\mu,\epsilon$等代表任意$\mathcal L$-串。如果$\mathcal L$的字母表为A，则$\mathcal L$-串的集合=$\cup{A^n

n \ge 1}$。

我们先前已经假定$\mathcal L$是可数语言，所以$\mathcal L$-串的集合是可数无穷大的。

对任意有穷个符号串$\lambda_1,\lambda_2,\cdots,\lambda_n$，我们用$\lambda_1\lambda_2\cdots\lambda_n$表示这n个字符串前后邻接起来形成的新符号串。如果$\lambda_1=f,\lambda_2=gf$，则$\lambda_1\lambda_2=fgf$。这使得我们可以对任意$n \ge 1$，在$\mathcal L$-串的集合上定义如下的n元邻接函数函数$C_n:C_n(\lambda_1,\lambda_2,\cdots,\lambda_n)=\lambda_1\lambda_2\cdots\lambda_n$

3.3 定义：设$\mathcal L$为一阶语言。$\mathcal L$-项定义为：

基始条件：
1. $\mathcal L$的字母表中的每个个体常项c是$\mathcal L$-项。
2. 每个个体变项x是$\mathcal L$-项。
归纳条件：对任意$n \ge 1$，若f是$\mathcal L$的n元函数符号，且$\mathcal L$-串$t_1,\cdots,t_n$是n个$\mathcal L$-项，则$\mathcal L$-串$ft_1\cdots t_n$也是$\mathcal L$-项。
封闭条件：没有其他$\mathcal L$-串是$\mathcal L$-项。

对一个形式语言$\mathcal L$来说，一个符号是不是$\mathcal L$-项，或者是否属于$\mathcal L$-项的集合，是能行可判定的。这就是说，存在一个有穷长的机械过程过或程序，其中每一步到下一步都由确定的规则决定，而对每个符号串，在其上执行这个程序后，都在有穷步后得到一个是或否的答案，回答这个符号串是不是$\mathcal L$-项。一般而言，这样一种程序叫算法。对集合A，如果有一个算法来判定任意a是否属于A，则称A为可判定的。

3.6 定理：设$\mathcal L$为形式语言。$\mathcal L$-项的集合是可判定的。

如$\mathcal L$-项$f_2^2f_0^1c_1f_0^1f_1^2c_1x_0$的构造过程可以分析下面的分解树。

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ c_1\ x_0$

$c_1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f_1^2c_1x_0\ (r_1)$

$f_0^1c_1\ (r_3)\ \ \ \ \ \ f_0^1f_1^2c_1x_0\ (r_2)$

$\ \ \ \ \ \ \ \ f_2^2f_0^1c_1f_0^1f_1^2c_1x_0$

每一层所有的符号串都是项。最上面没有横线的（叶上的项），是基始条件确定的项。即个体常项或个体变项；上面有横线的项，则表明它是横线之上的项根据归纳条件与适当的函数符号连接所形成的。下面没有横线的（根上的项），是最终形成的项。

如果项s（作为符号串）是项t的一部分（包括t本身），则称s是t的子项。项的分解树从根到叶，正是把根上的项拆开为其子项的过程。对每一枝来说，位置在上的每一项都是位置在下的所有项的子项；而树上的所有项，恰是根上的项的所有子项。所以，子项也可以这样定义：

s是t的子项，当且仅当s出现在t的分解树上。

3.8 项的归纳证明：设$\mathcal L$为一阶语言，P为关于$\mathcal L$-项的性质。要证明每个$\mathcal L$-项都具有性质P，只要证：

$\mathcal L$字母表中的每个个体常项具有性质P；
每个个体变项具有性质P；
对$\mathcal L$的n元函数符号f和$\mathcal L$-项$t_1\cdots t_n$，证明：若$t_1\cdots t_n$具有性质P，则$t_1\cdots t_n$-项$ft_1\cdots t_n$也有性质P。

3.9 引理：设$\mathcal L$为一阶语言。每个给定的$\mathcal L$-项的分解树都不同于其他项的分解树。

这个引理表明，不同的项有不同的分解树，每个项分解树只对应于一个项，因而从项分解树集到项集有一个函数关系，而且是满射。我们自然会问：这个函数是不是单射？或者，一个给定的项是不是只有唯一的分解树？既然一个项在语形上是一个符号串，那么，这个问题就相当于：以同一个项符号串为根，有没有可能存在不同的分解方法，从而产生两个不同的项分解树？

3.10 引理：如果符号串$\lambda$组成项，则$\lambda$只有唯一的项分解树。

3.11 定理（项的读法唯一性）：设$\lambda$为一个$\mathcal L$-串。如果$\lambda$组成$\mathcal L$-项t，又组成$\mathcal L$-项s，则t与s为同一个项。

这个事实从一个侧面反映了一阶语言的严格和精确：一个符号串如果组成项的话，则它只组成一个固定的项；不存在不同的读法，把其中符号排列重新“点断”，使得这个串同时也能组成另一个不同的项。日常语言中的词项，显然没有这种语形上的读法唯一性。”

4.公式

4.1 定义：设$\mathcal L$是任意一阶语言。$\mathcal L$的公式（或$\mathcal L$-公式）定义为：

基始条件
1. 对$\mathcal L$的任意n($n \ge 1$)元谓词P和任意n个$\mathcal L$-项$t_1t_2,…t_n,Pt_1t_2,…t_n$是$\mathcal L$-公式；
2. 对任意的$\mathcal L$-项t和s，$t \equiv s$是公式。
归纳条件
1. 如果$\varphi$是$\mathcal L$-公式，则$\lnot \varphi$也是$\mathcal L$-公式；
2. 如果$\varphi,\psi$是$\mathcal L$-公式，则$(\varphi \land \psi)$也是$\mathcal L$-公式；
3. 如果$\varphi,\psi$是$\mathcal L$-公式，则$(\varphi \lor \psi)$也是$\mathcal L$-公式；
4. 如果$\varphi,\psi$是$\mathcal L$-公式，则$(\varphi \to \psi)$也是$\mathcal L$-公式；
5. 如果$\varphi$是$\mathcal L$-公式，x是个体变项，则$\forall x \varphi$也是$\mathcal L$-公式；
6. 如果$\varphi$是$\mathcal L$-公式，x是个体变项，则$\exists x \varphi$也是$\mathcal L$-公式。

基始条件确定的公式，称为原子公式。2）中的公式1~4分别称为否定式、合取式、析取式和蕴含式，它们合称布尔式。2）中的5，6分别称为全称式和存在式。

显然，与$\mathcal L$-项的情形一样，每个$\mathcal L$-公式都是有穷长的。

4.5 定理：设$\mathcal L$为形式语言。$\mathcal L$-公式集是可判定的。

一个公式的子公式就是出现在它的分解树上的所有公式。

4.10 定理（公式的读法唯一性）：一个$\mathcal L$-串$\lambda$或者不是任何$\mathcal L$-公式，或者是唯一的一个$\mathcal L$-公式。

这个定理推广了项的读法唯一性定理，进一步表明了一阶语言的严格和精确：一个给定的公式，只有一种读法，不存在其他的点断方法，把它同时读为另一个公式。”

5.递归定义

给定$\mathcal L$-公式集，其上的秩可以如下分步定义：

对于$\mathcal L$的原子公式$\varphi,r(\varphi)=0$；
对于$\mathcal L$的非原子公式$\varphi$，
1. 如果$\varphi$为$\lnot \psi$，则$r(\varphi)=r(\psi)+1$；
2. 如果$\varphi$为$\psi_1 \Box \psi_2,\Box \in {\land,\lor,\lnot,\to}$，则$r(\varphi)=r(\psi_1)+r(\psi_2)+1$；
3. 如果$\varphi$为$\diamond x \psi,\diamond \in {\forall,\exists}$，则$r(\varphi)=r(\psi)+1$；

这种定义函数的方法叫递归定义。

5.1 定义：设$\mathcal L$为一阶语言。一个$\mathcal L$-项的所有子项形成一个$\mathcal L$-项的集合，记为S(t)。其中S为从$\mathcal L$-项集到其幂集的函数，按如下方式递归定义：

若t为个体常项或变项，则S(t)={t}；
若t为$ft_1\cdots t_n$，其中$t_1,t_2,\cdots,t_n$为$\mathcal L$-项，则$S(t)=S(t_1) \cup \cdots S(t_n) \cup {ft_1 \cdots t_n}$。

5.2 定义：设$\mathcal L$为一阶语言。一个$\mathcal L$-公式$\varphi$的所有子公式形成一个$\mathcal L$-公式的集合，记为S($\varphi$)。其中S为从$\mathcal L$-公式集到其幂集的函数，按如下方式递归定义：

若$\varphi$为原子公式，则$S(\varphi)={\varphi}$；
设$\varphi$为非原子公式，
1. 如果$\varphi$为$\lnot \psi$，则$S(\varphi)=S(\psi) \cup {\lnot \psi}$；
2. 如果$\varphi$为$\psi_1 \Box \psi_2,\Box \in {\land,\lor,\lnot,\to}$，则$S(\varphi)=S(\psi_1) \cup S(\psi_2) \cup {\psi_1 \Box \psi_2}$；
3. 如果$\varphi$为$\diamond x \psi,\diamond \in {\forall,\exists}$，则$S(\varphi)=S(\psi) \cup {\diamond x \psi}$。”

6.自由和约束代入

6.1 定义：对一个量化式$\forall x \varphi$（或$\exists x \varphi$），称其子公式$\varphi$是量词$\forall x$（或$\exists x$）的辖域。一般而言，如果$\forall x \varphi$（或$\exists x \varphi$）作为公式出现在公式$\psi$中，则称$\varphi$是这处量词在$\psi$中的辖域。

6.2 定义：在公式$\varphi$中，一个变项x如果出现在某个形如$\forall x$(或$\exists x$)的量词的某处辖域中，则称x在$\varphi$中的这处出现（以及它在这个量词中的出现）是约束的。变项的非约束的出现，称为自由出现。

如果x出现在$\varphi$中，只要x有一处自由出现，就称x是$\varphi$中的自由变项；否则称x为$\varphi$的约束变项。

我们称含有自由变项的公式为开公式，称不含有自由变项的公式为闭公式或语句。

6.5 定义：设$\mathcal L$是一个一阶语言，$s(x_1,x_2,\cdots,x_n)$是一个$\mathcal L$-项对任意$\mathcal L$-项。$t_1,t_2,\cdots,t_n$，我们如下递归定义$t_1,t_2,\cdots,t_n$在s中对$x_1,x_2,\cdots,x_n$的代入，代入结果记为$s(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$:

若s为个体常项，则$s(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)=s$；
若s为个体变项y，则 $s(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)=\left\{ \begin{matrix} t_1,& if\ x_i=y,\ for\ some\ i(1 \le i \le n) > 0 \ y, & elsewise. \end{matrix} \right.$
若s为$fs_1\cdots s_n$，则$s(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)=fs_1(t_1/x_1,t_2/x_2,\cdots,t_n/x_n) \cdots s_n(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$。

容易归纳证明$s(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$仍然是$\mathcal L$-项。

6.6 定义：设$\mathcal L$是一个一阶语言，$\varphi(x_1,x_2,\cdots,x_n)$是一个$\mathcal L$-公式。对任意$\mathcal L$-项$t_1,t_2,\cdots,t_n$，我们如下归纳定义$t_1,t_2,\cdots,t_n$在$\varphi$中对$x_1,x_2,\cdots,x_n$的代入，代入结果记为$\varphi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$:

若$\varphi$为原子公式$Ps_1\cdots s_n$，则$\varphi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)=Ps_1(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)\cdots s_n(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$；
若$\varphi$为原子公式$s_1 \equiv s_2$，则$\varphi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)=s_1(t_1/x_1,t_2/x_2,\cdots,t_n/x_n) \equiv s_2(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$；
若$\varphi$为$\lnot \psi$，则$\varphi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)=\lnot \psi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$；
若$\varphi$为$\psi_1 \Box \psi_2,\Box \in {\land,\lor,\lnot,\to}$，则$\varphi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)=\psi_1(t_1/x_1,t_2/x_2,\cdots,t_n/x_n) \Box \psi_2(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$；
若$\varphi$为$\diamond y \psi,\diamond \in {\forall,\exists}$，则 $\psi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)=\left\{\begin{matrix} \diamond y \psi(\cdots,t_{i-1}/x_{i-1},t_{i+1}/x_{i+1},\cdots),& if\ x_i=y,for\ some\ i(1 \le i \le n) > 0 \ \diamond y \psi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n), & elsewise. \end{matrix}\right.$

容易归纳证明，$\varphi(t_1/x_1,t_2/x_2,\cdots,t_n/x_n)$仍然是$\mathcal L$-公式。”

第4章经典语义学

1.结构与解释

1.1 定义：设$\mathcal L$是一阶语言。一个$\mathcal L$-结构$\mathcal A$是一个有序对<A, $\eta$>，它满足以下性质：

A是个体的非空集合，称为$\mathcal A$的全域或$\mathcal L$的论域。
$\eta$是定义在$\mathcal L$的非逻辑符号集上的函数，使得
1. 对$\mathcal L$的每个个体常项c,$\eta(c) \in A$。
2. 对$\mathcal L$的每个n元谓词P，$\eta(P)$是A中的一个n元关系。
3. 对$\mathcal L$的每个n元函数符号f，$\eta(f)$是A中的一个n元函数。

由定义知，一个$\mathcal L$-结构$\mathcal A=<A,\eta>$首先有一个作为语言$\mathcal L$的论域的非空个体域A，然后它有一个解释函数$\eta$，把$\mathcal L$中的个体常项、谓词、函数符号分别对应或解释为A中的个体、关系（一元关系是性质）和函数：$\eta(c)$是常项c的指称，$\eta(P)$是谓词P所表达的关系，$\eta(f)$是函数符号f表达的函数。一个$\mathcal L$-结构确定了$\mathcal L$的所有非逻辑符号的意义。

以后我们把$\eta$的值$\eta(c),\eta(P),\eta(f)$分别记作：$c^{\mathcal A},P^{\mathcal A},f^{\mathcal A}$。

例如，$\mathcal L_m={a,P,Q,f}$，一个$\mathcal L_m$结构就可记为$\mathcal A=<A,a^{\mathcal A},P^{\mathcal A},Q^{\mathcal A},f^{\mathcal A}>$，其中

a是A中个体$a^{\mathcal A}$的名字；
P表达A的子集（A中的性质）$P^{\mathcal A}$；
Q表达$A^2$的子集（A中的二元关系）$Q^{\mathcal A}$；
f表达A中一元函数$f^{\mathcal A}$。

注意这里两套语言的区别。首先，我们有一阶语言$\mathcal L_m,a,P,Q,f$等是这个语言中的符号，它们可以构成项、公式等$\mathcal L$-表达式。这是我们要解释，或通过结构赋予意义的对象语言。

其次，$a^{\mathcal A},P^{\mathcal A},Q^{\mathcal A},f^{\mathcal A},\in$等，不是$\mathcal L_m$中的符号，它们属于元语言层次，是用来解释$\mathcal L_m$的。

1.6 定义：对给定的$\mathcal L$-结构$\mathcal A=<A,\eta>$，一个$\mathcal A$中的赋值是从$\mathcal L$的个体变项集到$\mathcal A$的全域A中的一个函数：$\rho:{x_0,x_1,x_2,\cdots} \to A$。

$\rho$对每个个体变项x指定A中的一个元素$\rho(x)$作为其值。对个体变项的赋值加上结构中已有的对非逻辑符号的解释，就使$\mathcal L$中的所有项（包括含有个体变项的）都代表个体，所有的非等式原子公式（包括开公式）都有真值。

1.7 定义：对语言$\mathcal L$的一个解释指有序对$\sigma=<\mathcal A,\rho>$，其中$\mathcal A$是一个$\mathcal L$-结构，$\rho$是一个$\mathcal A$中的赋值。

定义中的$\mathcal A$叫做$\sigma$的结构，$\mathcal A$的全域A也称解释$\sigma$的全域。显然，一个解释就是一个结构加上其中的一个赋值，把语言中的个体变项一并规定了确定的取值。

一个$\mathcal L$-解释能够确定所有$\mathcal L$-项对应的个体，我们把这个事实总结为如下的递归定义：

1.8 定义：设t是一个$\mathcal L$-项，$\sigma=<\mathcal A,\rho>$是个$\mathcal L$-解释。我们称t在$\sigma$之下所对应的个体为t在$\sigma$之下的取值，记为$\sigma(t)$。$\sigma(t)$是满足以下条件的函数的值：

若t为个体变项$x_i(i \ge 0)$，则$\sigma(t)=\rho(x_i)$；
若t为$\mathcal L$的个体常项c，则$\sigma(t)=c^{\mathcal A}$；
若t为$ft_1\cdots t_n$，其中f是$\mathcal L$的n元函数符号$(n \ge 1),t_1,\cdots,t_n$是n个$\mathcal L$-项，则$\sigma(t)=f^{\mathcal A}(\sigma(t_1),\cdots,\sigma(t_n))$。

定义了每个$\mathcal L$-项t的值$\sigma(t)$之后，$\mathcal L$的每个形如$Pt_1\cdots t_n$的原子公式都有了确定的真值。\n”

2.等词、量词和联结词

2.1 等词

在一阶语言$\mathcal L$中，若t和s是$\mathcal L$-项，则$\mathcal L$-公式$t \equiv s$在任何$\mathcal L$-解释里都表示t与s代表此结构中的同一个个体。就是说，在任意$\mathcal L$-解释$\sigma$下，

$t \equiv s$ 表达 $\sigma(t)=\sigma(s)$

2.2 量词

$\forall x \varphi(x)$在$\sigma$ 之下应读为：对所有的$a \in A,\varphi(x)$在$\sigma(a/x)$之下为真。

$\exists x \varphi(x)$则读作：存在$a \in A$，使得$\varphi(x)$在$\sigma(a/x)$之下为真。

2.3 联结词

2.3.1 定义：对$n \ge 1$，一个n元真值函数f是从集合${T,F}^n$到集合{T,F}的函数：$f:{T,F}^n \to {T,F}$

如果对某个二元真值函数f，我们可以这样刻画它：

f{T,T}=T,
f{T,F}=T,
f{F,T}=T,
f{F,F}=F。

可以列一个表：

x	y	f(x,y)
T	T	T
T	F	T
F	T	T
F	F	F

这称为真值函数f的真值表。其中左边一列自变元x和y的取值穷尽了${T,F}^2$的所有元素，右边一列给出相应的函数值。

每个公式都有一个子公式的分解树，其中的子公式或为原子公式，或为量化式、布尔式，分解进行到原子公式为止（原子公式出现且仅出现在叶子）。为了单独研究布尔式的性质，我们把所有原子公式和量化式看作一类，统称为素公式。

设想每个公式$\varphi$只分解到素公式为止（即$\varphi$的分解树的叶子上只有素公式，且每个素公式都在叶上）。再把叶上的公式抹掉，从左到右分别代以$p_0,p_1,\cdots,p_{n-1}$等，相同的公式代以相同的$p_i$。现把这些$p_i$还原到根公式$\varphi$中，即把$\varphi$中的每个素子公式按其在叶上的替换也换成相应的$p_i$。这样，我们就从$\varphi$得到一个元语言表达式$\varphi^p$，其中只含诸$p_i$和联结词，而不含谓词（包括等词）、量词、函数符号以及由此产生的项和公式等。由公式的分解唯一性知，给定$\varphi,\varphi^p$是唯一的。我们称$\varphi^p$为$\varphi$的布尔形式。比如，如果$\varphi$为

\[\exists x_0 P x_0 \land \lnot Qfaa \to \lnot Qfaa\]

则其布尔形式$\varphi^p$为

\[p_0 \land \lnot p_1 \to \lnot p_1\]

对于$\varphi^p$来说，那些$p_i$的值是事先给定的，或者说，它们表达0元真值函数。换言之，我们可以把诸$p_i$看成直接在{T,F}中取值的（命题）变项，而把$\varphi^p$看成主目为诸$p_i$的真值函数表达式。不妨把$\varphi^p$对应的真值函数的真值表直接称为$\varphi^p$的真值表，此时的诸$p_i$相当于真值函数中的自变元x，y等。

一个联结词集合C称为表达完全的，如果对任一n元真值函数f，都有在C的基础上定义的公式$\varphi$（即其中的联结词都在C中），使得$\varphi^p$表达函数f。

2.3.5 定理：联结词集合${\lnot,\land,\lor}$是表达完全的。

描述这样一个命题逻辑语言$\mathcal L^p$：

$\mathcal L^p$-初始符号：

（可数无穷多）命题变项：$p_0,p_1,p_2,\cdots$；
联结词：$\lnot,\land,\lor,\to$；
括号：)，(。

$\mathcal L^p$-公式：

任何命题变项是$\mathcal L^p$-公式（原子公式）；
如果$\varphi$是$\mathcal L^p$-公式，则$\lnot \varphi$也是；
如果$\varphi,\psi$是$\mathcal L^p$-公式，则$\varphi \land \psi$也是；
如果$\varphi,\psi$是$\mathcal L^p$-公式，则$\varphi \lor \psi$也是；
如果$\varphi,\psi$是$\mathcal L^p$-公式，则$\varphi \to \psi$也是；
只有以上是$\mathcal L^p$-公式。

2.3.8 习题：

$\mathcal L^p$-公式集是可判定的；
$\mathcal L^p$-公式具有读法唯一性；
从命题变项集到{T,F}一个函数$\tau:{p_0,p_1,p_2,\cdots} \to {T,F}$称为一个真值赋值。它把每个命题变项对应到一个真值，从而把原子公式解释为命题。

一个真值赋值$\tau$就是一个$\mathcal L^p$-解释。

一个$\mathcal L^p$-公式$\varphi$称为重言式，如果对任意真值赋值$\tau$，都有$\tau(\varphi)=T$。”

3.满足真

3.1 定义：设$\mathcal L$是一阶语言，$\sigma=<\mathcal A,\rho>$是一个$\mathcal L$-解释。对任意$\mathcal L$-公式$\varphi$，$\sigma$满足$\varphi$，记为$\sigma(\varphi)=T$；$\sigma$不满足$\varphi$，记为$\sigma(\varphi)=F$。$\sigma(\varphi)$是以下递归定义的唯一的函数的值：

若$\varphi$是原子公式$Pt_1\cdots t_n$，其中P是$\mathcal L$的n元谓词，$t_1,\cdots,t_n$是n个$\mathcal L$-项，则$\sigma(\varphi)=\left{\begin{matrix} T,& if\ P^{\mathcal A}(\sigma(t_1),\cdots,\sigma(t_n))\ establish(or\ <\sigma(t_1),\cdots,\sigma(t_n)> \in P^{\mathcal A}) \ F, & elsewise. \end{matrix}\right.$
若$\varphi$是等式$t \equiv s$，其中t和s是$\mathcal L$-项，则$\sigma(\varphi)=\left{\begin{matrix} T,& if\ \sigma(t)=\sigma(s) \ F, & elsewise. \end{matrix}\right.$
若$\varphi$为$\lnot \psi$，则$\sigma(\varphi)=\lnot\sigma(\psi)$，即$\sigma(\varphi)=\left{\begin{matrix} T,& if\ \sigma(\psi)=F \ F, & elsewise. \end{matrix}\right.$
若$\varphi$为$\psi_1 \land \psi_2$，则$\sigma(\varphi)=\sigma(\psi_1) \land \sigma(\psi_2)$，即$\sigma(\varphi)=\left{\begin{matrix} T,& if\ \sigma(\psi_1)=\sigma(\psi_2)=T \ F, & elsewise. \end{matrix}\right.$
$\varphi$为$\psi_1 \lor \psi_2$，则$\sigma(\varphi)=\sigma(\psi_1) \lor \sigma(\psi_2)$，即$\sigma(\varphi)=\left{\begin{matrix} F,& if\ \sigma(\psi_1)=\sigma(\psi_2)=F \ T, & elsewise. \end{matrix}\right.$
$\varphi$为$\psi_1 \to \psi_2$，则$\sigma(\varphi)=\sigma(\psi_1) \to \sigma(\psi_2)$，即$\sigma(\varphi)=\left{\begin{matrix} F,& if\ \sigma(\psi_1)=T\ and\ \sigma(\psi_2)=F \ T, & elsewise(\sigma(\psi_1)=F\ or\ \sigma(\psi_2)=T). \end{matrix}\right.$
若$\varphi$为$\forall x \psi$，其中x为个体变项，则$\sigma(\varphi)=\left{\begin{matrix} T,& if\ for\ every\ a \in A,\sigma(a/x)(\psi)=T \ F, & elsewise. \end{matrix}\right.$
若$\varphi$为$\exists x \psi$，其中x为个体变项，则$\sigma(\varphi)=\left{\begin{matrix} T,& if\ for\ exists\ a \in A,\sigma(a/x)(\psi)=T \ F, & elsewise. \end{matrix}\right.$

对一个$\mathcal L$-公式集$\Phi$和一个$\mathcal L$-解释$\sigma$，我们用$\sigma(\Phi)=T$表示$\sigma$满足$\Phi$，它的定义为：对每个$\varphi \in \Phi$，都有$\sigma(\varphi)=T$（或者，对任意的$\varphi$，若$\varphi \in \Phi$，则$\sigma(\varphi)=T$）

如果t同时是$\mathcal L_1$和$\mathcal L_2$的项，而且对t中出现的每个非逻辑符号u，$u^{\mathcal A_1}=u^{\mathcal A_2}$，对t中出现的每个个体变项x，$\sigma_1(x)=\sigma_2(x)$，则称$\sigma_1$与$\sigma_2$在t上合同。

如果$\varphi$同时是$\mathcal L_1$和$\mathcal L_2$的公式，而且对$\varphi$中出现的每个非逻辑符号u，$u^{\mathcal A_1}=u^{\mathcal A_2}$，对$\varphi$中出现的每个自由变项x，$\sigma_1(x)=\sigma_2(x)$，则称$\sigma_1$与$\sigma_2$在$\varphi$上合同。

3.6 合同引理：设$\sigma_1=<\mathcal A_1,\rho_1>$和$\sigma_2=<\mathcal A_2,\rho_2>$分别是$\mathcal L_1$和$\mathcal L_2$解释，$A_1=A_2$，t和$\varphi$是语言 $\mathcal{L}=\mathcal L_1 \cap \mathcal L_2$的项和公式。

若$\sigma_1$与$\sigma_2$在t上合同，则$\sigma_1(t)=\sigma_2(t)$；
若$\sigma_1$与$\sigma_2$在$\varphi$上合同，则$\sigma_1(\varphi)=\sigma_2(\varphi)$。

3.10 定义：对$\mathcal L$-语句$\varphi$和$\mathcal L$-解释$\sigma=<\mathcal A,\rho>$，如果$\sigma(\varphi)=T$，则称$\varphi$在结构$\mathcal A$中为真，或$\mathcal A$为$\varphi$的模型，记为$\mathcal A(\varphi)=T$。如果$\Phi$为$\mathcal L$-语句集，且对每个$\varphi \in \Phi$，$\mathcal A$为$\varphi$的模型，则称$\mathcal A$为$\Phi$的模型，记为$\mathcal A(\Phi)=T$。”

4.语义后承

4.1 定义：设$\Phi$为语言$\mathcal L$的一个公式集，$\varphi$是一个$\mathcal L$-公式。如果对任意的$\mathcal L$-解释$\sigma$，只要$\sigma(\Phi)=T$，就有$\sigma(\varphi)=T$，则称$\varphi$为$\Phi$的语义后承，记为$\Phi \models \varphi$。

直观上表达的就是：前提集$\Phi$和结论$\varphi$组成一个有效的推理。这也可以表述为：$\Phi$语义蕴含$\varphi$。

表达的是实质蕴含：$\varphi$不是$\Phi$的语义后承，当前仅当存在$\mathcal L$-解释$\sigma$，使得$\sigma(\Phi)=T$，但$\sigma(\varphi)=F$。

4.2 引理：设语言$\mathcal L_1 \subseteq \mathcal L_2$，$\Phi$为$\mathcal L_1$-公式集，$\varphi$为$\mathcal L_1$-公式。则$\Phi \models_1 \varphi$当且仅当$\Phi \models_2 \varphi$。

4.3 定理：设$\Phi$同时是$\mathcal L_1$和$\mathcal L_2$的公式集，$\varphi$同时是$\mathcal L_1$和$\mathcal L_2$的公式，则$\Phi \models_1 \varphi$当且仅当$\Phi \models_2 \varphi$。

定理表明，语义后承关系是否成立，于语言背景无关。

4.8 引理：设$\Phi,\Psi$是$\mathcal L$的公式集，$\varphi,\psi$是$\mathcal L$-公式。我们有：

如果$\varphi \in \Phi$，则$\Phi \models \varphi$。
如果$\Phi \models \varphi$，且$\Phi \subseteq \Psi$，则$\Psi \models \varphi$。
如果$\Phi \models \Psi$，且$\Psi \models \varphi$，则$\Phi \models \varphi$。（$\Phi \models \Psi$定义为：对任意$\varphi \in \Psi$，都有$\Phi \models \varphi$）
$\Phi,\varphi \models \psi$，当且仅当$\Phi \models \varphi \to \psi$。

这表明了语义蕴含与实质蕴含之间的关系。令$\Phi$为空集，我们有：$\varphi \models \psi$当且仅当$\models \varphi \to \psi$。

这个断言的直观意义是：从$\varphi$到$\psi$形成一个有效推理，当且仅当蕴含式“$\varphi \to \psi$”永真（在一切情形或解释下为真）。

4.10 引理：设$\Phi$是$\mathcal L$的公式集，$\varphi$是$\mathcal L$-公式。如果$\Phi \models \varphi$，且x不在$\Phi$的任何公式中自由，则$\Phi \models \forall x \varphi$。”

5. 可满足性有效性语义等值

5.1 定义：$\mathcal L$-公式$\varphi$称为可满足的，如果存在一个$\mathcal L$-解释$\sigma$，使得$\sigma(\varphi)=T$。

$\mathcal L$的公式集$\Phi$称为可满足的，如果存在一个$\mathcal L$-解释$\sigma$，使得$\sigma(\Phi)=T$。

直观上讲，公式$\varphi$可满足说的是$\varphi$可能为真，或者，$\varphi$语义上不蕴涵矛盾；而公式集$\Phi$可满足说的是$\Phi$中的公式可以同时为真，或者，$\Phi$语义上不蕴涵矛盾。反之，$\varphi$不可满足则意味着$\varphi$是“永假的”、矛盾的；$\Phi$不可满足意味着$\Phi$中的公式不能同真，它们蕴涵着矛盾。

5.3 引理：设$\Phi$为$\mathcal L$的公式集，$\varphi$为$\mathcal L$-公式，则$\Phi \cup{\varphi}$可满足，当且仅当，并非$\Phi \models \lnot \varphi$。

5.5 定义：$\mathcal L$-公式 $\varphi$称为有效的，如果对所有的$\mathcal L$-解释$\sigma$，都有$\sigma(\varphi)=T$。（按照我们引入的记法，$\varphi$有效可以记为$\models \varphi$）

有效的公式不但可满足，而且是“用真的”，或不可能为假的，就是说，不管你给出什么解释，不管其论域是什么、有多大，也不管它对相关语言中的符号赋予什么意义，有效公式在其中总是真的。

5.8 定理：如果$\varphi$为重言式，则$\models \varphi$。

5.10 定义：对公式$\varphi$和$\psi$，如果$\models \varphi \to \psi$，并且$\models \psi \to \varphi$，则称$\varphi$和$\psi$是语义等值的。

$\varphi$和$\psi$语义等值也可以表达成：$\varphi\models\psi$并且$\psi\models\varphi$，即两者互为对方的语义后承。显然$\varphi$和$\psi$语义等值，当且仅当，对任意的解释$\sigma,\sigma(\varphi)=\sigma(\psi)$。由此即得：语义等值关系是自反的、对称的、传递的。因此，语义等值关系是一个等价关系。

5.18 等值替换定理：设$\varphi,\psi,\psi^{\prime}$为公式，$\varphi^{\prime}$是由$\psi^{\prime}$替换$\psi$在$\varphi$中的一些出现而得到的公式。我们有：如果$\models \psi \leftrightarrow \psi^{\prime}$，那么$\models \varphi \leftrightarrow \varphi^{\prime}$”

6.代入引理

6.1 代入引理：设$\mathcal L$为一阶语言，$\sigma=<\mathcal A,\rho>$是$\mathcal L$-解释，t是$\mathcal L$-项，x是个体变项。

对任意$\mathcal L$-项s，有$\sigma(s(t/x))=\sigma(\sigma(t)/x)(s)$；
对任意$\mathcal L$-公式$\varphi$，若t在$\varphi$中对x可代入，则$\sigma(\varphi(t/x))=\sigma(\sigma(t)/x)(\varphi)$。

6.3 系理：如果$\varphi$是一个量化式，$\varphi^{\prime}$是由$\varphi$经易字而得到的变式，那么$\models \varphi \leftrightarrow \varphi^{\prime}$。

6.4 系理：如果$\varphi$是公式，t是项，那么，

$\models \forall x \varphi \to \varphi(t/x)$；
$\models \varphi(t/x) \to \exists x \varphi$。

6.5 系理：设$\Phi$是$\mathcal L$的公式集，$\varphi$是$\mathcal L$-公式。如果$\Phi \models \varphi(y/x)$，则$\Phi \models \forall x \varphi$，其中y不在$\Phi$的任何公式及$\forall x \varphi$中自由。

6.6 系理：如果s、t是项，$\varphi$是公式，那么，$\models t \equiv s \to (\varphi(t/x) \leftrightarrow \varphi(s/x))$。”

第5章自然推演系统

2.联结词规则

2.1 规则的说明

1） $\land$-引入（$\land I$）

\[\varphi\ \ \ \psi\]

\[\varphi \land \psi\]

2）$\land$-消去（$\land E$）

\[\varphi \land \psi\]

\[\varphi\]

和

\[\varphi \land \psi\]

\[\psi\]

3）$\lor$-引入（$\lor I$）

\[\varphi\]

\[\varphi \lor \psi\]

和

\[\psi\]

\[\varphi \lor \psi\]

4）$\to$-消去（$\to E$）

\[\varphi\ \ \ \varphi \to \psi\]

\[\psi\]

5）$\to$-引入（$\to I$）

$[\varphi]$ $\vdots$ $\psi$

\[\varphi \to \psi\]

把$\varphi$用方括号表示出来，表明它是$\psi$的前提，但在使用这个规则时被消除。联结$\varphi$和$\psi$的竖虚线表示$\psi$依赖于前提$\varphi$。

6）$\lor$-消去($\lor E$)

如果你有前提“$\varphi$或者$\psi$”，又分别从$\varphi$和$\psi$都推出了$\theta$，那么结论$\theta$就是不可避免的。但是，从$\varphi$推出$\theta$和从$\psi$推出$\theta$在这里都是辅助性的子推理，一旦完成，其前提$\varphi$和$\psi$就可以消除。最终结论$\theta$只依赖于“$\varphi$或者$\psi$”和其他未消除的前提。这提示出以下规则：

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [\varphi]\ \ \ [\psi]$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\ \ \ \vdots$ $\varphi \lor \psi\ \ \ \ \ \theta\ \ \ \theta$

\[\theta\]

7）$\lnot$-引入（$\lnot I$）

归谬法可以表为如下的$\lnot$-引入规则：

$[\varphi]$ $\vdots$ $\psi \land \lnot\psi$

\[\lnot\varphi\]

8）直觉主义规则（IN）

对于$\lnot$还有更强的解释，牵涉到另一个古老而著名的规则：矛盾推出一切（ex falso sequitur quodlibet）。这个规则表现了直觉主义逻辑的特征，所以我们又称它为直觉主义规则：

\[\varphi \land \lnot\varphi\]

\[\psi\]

$\lnot\varphi$即意味着$\varphi$推出一切。我们把推出一切的称为荒谬的，因此，$\lnot\varphi$即意味着$\varphi$是荒谬的。

9）反证法（CL）

反证法是RAA的另一种形式，它规定，如果从$\lnot\varphi$推出了矛盾，就要得到$\varphi$。注意它跟归谬法的区别：归谬法是反驳的方法，为论证的缘故，先假设$\varphi$，再借矛盾来否定它，因此结论是否定式$\lnot\varphi$；而反证法是证明的方法，也是为论证的缘故，先假设否定$\lnot\varphi$，结论却是$\varphi$。跟归谬法一样，反证法的假设，只在推出矛盾的过程中起作用，得到最后的结论，它便消除了。

反证法在形式上表现为一种$\land$-消去规则：

$[\lnot\varphi]$ $\vdots$ $\psi \land \lnot\psi$

\[\varphi\]

3.命题推演语形后承

首先约定几种元语言记法，其中我们统一用D表示推演（derivation）。

第一，我们用

$D$ $\varphi$

表示其结论为$\varphi$的一个推演D。如果需要标示D的某个前提$\psi$，则可以进一步把D表示为

$\psi$ $D$ $\varphi$

注意：$\psi$和$\varphi$都是D的一部分。

第二，如果

$D\ \ \ D^{\prime}$ $\varphi\ ,\ \varphi^{\prime}$

是推演，那么

$D\ \ \ \ \ \ D\ \ \ D^{\prime}$ $\varphi\ ,\ \varphi\ \ \ \varphi^{\prime}$

\[\psi\ \ \ \ \ \ \psi^{\prime}\]

第三，我们如下表示前提和消除。如果

$\psi$ $D$ $\varphi$

是一个推演，则

$[\psi]$ $D$ $\varphi$

\[\theta\]

表示应用某规则于推演D，得到一个新的推演，其结论为$\theta$，同时按这个规则地要求，消除了D的前提$\psi$。

现在归纳定义命题逻辑推演和与其相关的语形后承概念。这牵涉到从小到大几种逻辑，包括极小逻辑、直觉逻辑和经典逻辑。

3.1 极小命题逻辑

3.1.1 定义：设$\mathcal L$为一阶语言，$\varphi,\psi,\theta$为$\mathcal L$-公式。$\mathcal L$中的极小命题推演定义为：

1）基始条件：任何单点树$\varphi$是$\mathcal L$-极小命题推演。

2）归纳条件为以下7条规则：

2.1）（$\land I$）如果

$D_1\ \ \ D_2$ $\varphi\ ,\ \psi$

是$\mathcal L$-极小命题推演，那么

$D_1\ \ \ D_2$ $\varphi\ ,\ \psi$

\[\varphi \land \psi\]

也是。

2.2）（$\land E$）如果

$D$ $\varphi \land \psi$

是$\mathcal L$-极小命题推演，那么

$D\ \ \ \ \ \ \ \ \ D$ $\varphi \land \psi\ \ \ \varphi \land \psi$

\[\varphi\ \ \ \ \ \ \ \ \ \psi\]

也是。

2.3）（$\lor I$）如果

$D$ $\varphi$

是$\mathcal L$-极小命题推演，那么

$D\ \ \ \ \ \ \ \ \ D$ $\varphi\ \ \ \ \ \ \ \ \ \varphi$

\[\varphi \land \psi\ \ \ \psi \land \varphi\]

也是。

2.4）（$\lor E$）如果

$\ \ \ \ \ \ \ \ \ \ \ \varphi\ \ \ \psi$ $D_1\ \ \ \ \ \ \ \ \ D_2\ \ \ D_3$ $\varphi \land \psi\ \ \ ,\ \ \theta,\ \ \ \theta$

是$\mathcal L$-极小命题推演，那么

$\ \ \ \ \ \ \ \ \ \ \ [\varphi]\ \ \ [\psi]$ $D_1\ \ \ \ \ \ \ \ \ D_2\ \ \ D_3$ $\varphi \land \psi\ \ \ ,\ \ \theta,\ \ \ \theta$

\[\theta\]

也是。

2.5）（$\to I$）如果

$\varphi$ $D$ $\psi$

是$\mathcal L$-极小命题推演，那么

$[\varphi]$ $D$ $\psi$

\[\varphi \to \psi\]

也是。

2.6）（$\to E$）如果

$D_1\ \ \ \ \ \ \ \ \ D_2$ $\varphi\ \ \ \ \ \ \ \ \ \varphi\to\psi$

是$\mathcal L$-极小命题推演，那么

$D_1\ \ \ \ \ \ \ \ \ D_2$ $\varphi\ \ \ \ \ \ \ \ \ \varphi\to\psi$

\[\psi\]

也是。

2.7）（$\lnot I$）如果

$\varphi$ $D$ $\psi\land\lnot\psi$

是$\mathcal L$-极小命题推演，那么

$[\varphi]$ $D$ $\psi\land\lnot\psi$

\[\lnot\varphi\]

也是。

3）封闭条件：只有以上的是是$\mathcal L$-极小命题推演。

对一个推演D，称其叶上未被消除的公式为D的前提，根上的公式为D的结论。上述定义的归纳条件中涉及的规则，称为初始的极小命题规则。

3.1.6 定义：设$\Phi$是一个$\mathcal L$-公式集，$\varphi$是一个$\mathcal L$-公式。如果存在一个极小命题推演D，使得D的前提集是$\Phi$的子集，且D的结论为$\varphi$，则称$\varphi$为$\Phi$的极小命题语形后承（或在极小命题逻辑里，从$\Phi$可推演$\varphi$），记为$\Phi \vdash_m\varphi$。

当$\Phi$为空集时，记$\Phi \vdash_m\varphi$为$\vdash_m\varphi$。此时$\varphi$为极小命题逻辑定理。

3.1.13 引理：

如果$\varphi \in \Phi$，则$\Phi \vdash\varphi$。
如果$\Phi \vdash\varphi$，且$\Phi \subseteq\Psi$，则$\Psi \vdash\varphi$。

3.1.14 引理：如果$\Phi \vdash \varphi$，则存在$\Phi$的有穷子集$\Psi$，使得$\Psi \vdash\varphi$。

3.1.15 引理：如果$\Phi \vdash\Psi$且$\Psi \vdash\varphi$，则$\Phi\vdash\varphi$。

3.1.16 引理：$\Phi,\varphi\vdash\psi$当且仅当$\Psi\vdash\varphi\to\psi$。

3.1.18 引理：$\vdash\varphi\leftrightarrow\psi$，当且仅当$\varphi\vdash\psi$且$\psi\vdash\varphi$。

3.2 直觉主义命题逻辑

3.2.1 定义：设$\mathcal L$为一阶语言，$\varphi,\psi$为$\mathcal L$-公式。$\mathcal L$中的直觉主义命题推演定义为：

1）基始条件：任何点单树$\varphi$都是$\mathcal L$-直觉主义命题推演。

2）归纳条件：前7条规则照搬定义3.1.1中归纳条件（把其中的“极小”字样全部改为“直觉主义”），再加上：

2.8）（IN）如果

$D$ $\varphi \land \lnot\varphi$

是$\mathcal L$-直觉主义命题推演，那么

$D$ $\varphi \land \lnot\varphi$

\[\psi\]

也是。

3）只有以上是$\mathcal L$-直觉主义命题推演。

相应地，直觉主义的语形后承$\vdash_i$是$\vdash_m$的扩充：

3.2.2 定义：设$\Phi$是一个$\mathcal L$-公式集，$\varphi$是一个$\mathcal L$-公式。如果存在一个直觉主义命题推演D，使得D的前提集是$\Phi$的子集，且D的结论为$\varphi$，则称$\varphi$为$\Phi$的直觉主义命题语形后承（或在直觉主义命题逻辑里，从$\Phi$可推演$\varphi$），记为$\Phi\vdash_i\varphi$。

如果$\vdash_i\varphi$，则称为直觉主义命题逻辑定理。

3.2.3 定理：对任何公式集$\Phi$和公式$\theta$，

如果$\Phi\vdash_m\theta$，则$\Phi\vdash_i\theta$；
$\Phi\vdash_i\theta$，当且仅当$\Phi \cup {such\ as\ \varphi\land\lnot\varphi\to\psi\ formula}\vdash_m\theta$。

3.3 经典命题逻辑

3.3.1 定义：设$\mathcal L$为一阶语言，$\varphi,\psi$为$\mathcal L$-公式。$\mathcal L$中的经典命题推演定义为：

1）基始条件：任何单点树$\varphi$都是$\mathcal L$-经典命题推演。

2）归纳条件：前8条规则照搬定义3.2.1中归纳条件（把其中的“直觉主义”字样全部改为“经典”），再加上：

2.9）（CL）如果

$\lnot\varphi$ $D$ $\psi\land\lnot\psi$

是$\mathcal L$-经典命题推演，那么

$[\lnot\varphi]$ $D$ $\psi\land\lnot\psi$

\[\varphi\]

也是。

3）只有以上是$\mathcal L$-经典命题推演。

经典语形后承$\vdash_c$是$\vdash_i$的扩充：

3.3.2 定义：设$\Phi$是一个$\mathcal L$-公式集，$\varphi$是一个$\mathcal L$-公式。如果存在一个经典命题推演D，使得D的前提集是$\Phi$的子集，且D的结论为$\varphi$，则称$\varphi$为$\Phi$的经典命题语形后承（或在经典命题逻辑里，从$\Phi$可推演$\varphi$），记为$\Phi\vdash_c\varphi$。

如果$\vdash_c\varphi$，则称为经典命题逻辑定理。

3.3.3 定理：对任何公式集$\Phi$和公式$\theta$，

如果$\Phi\vdash_i\theta$，则$\Phi\vdash_c\theta$；
$\Phi\vdash_c\theta$，当且仅当$\Phi + ( \lnot\varphi\to\psi\land\lnot\psi)\to\varphi\vdash_i\theta$。

3.3.6 引理：

$\Phi\vdash_c\varphi\lor\lnot\varphi$（排中律规则）；
如果$\Phi\vdash_c\lnot\lnot\varphi$，那么$\Phi\vdash_c\varphi$（双重否定消去规则）；
如果$\Phi,\varphi\vdash_m\psi$，且$\Psi,\lnot\varphi\vdash_m\psi$，则$\Phi\cup\Psi\vdash_m\psi$（二难推理规则）。”

4.量词和等词规则

4.1 量词规则

1）$\forall$-消去（$\forall E$）

\[\forall x\varphi\]

\[\varphi(t/x)\]

其中项t对$\varphi$中的x可代入，而$\varphi(t/x)$是代入结果——以后我们只要写出$\varphi(t/x)$，都假设t对$\varphi$中的x可代入。

2）$\exists$-引入（$\exists I$）

\[\varphi(t/x)\]

\[\exists x\varphi\]

3）$\forall$-引入（$\forall I$）

$\vdots$ $\varphi(y/x)$

\[\forall x\varphi\]

其中y不在$\varphi(y/x)$所依赖的任何（未消除的）前提及$\forall x\varphi$中自由。这两个条件，前者保证了y的“任意性”，后者保证$\forall y\varphi(y/x)$与$\forall x\varphi$互为（经易字得到的）变式，因此表达同样的命题。

4）$\exists$-消去（$\exists E$）

$\ \ \ \ \ \ [\varphi(y/x)]$ $\ \ \ \ \ \ \vdots$ $\exists x\varphi\ \psi$

\[\psi\]

其中的变项y，满足如下条件：

y不在上面那个$\psi$所依赖的前提——除$\varphi(y/x)$外——中自由。
y不在$\exists x\varphi$中自由。
y不在$\psi$中自由。

4.2 等词规则

1）$\equiv$-引入（$\equiv I$）

\[t\equiv t\]

这个无前提的规则说的是：对任何项t，$t\equiv t$无条件成立。这在语形上表达了关于“同一”的第一个原则：任何个体都是自身同一的。

2）$\equiv$-消去（$\equiv E$）

\[t\equiv s\ \ \ \varphi(t/x)\]

\[\varphi(s/x)\]

这是“同一者不可分辨”原则的表达：同一的东西有相同的性质，所以，若项t和s代表相同的东西，那么对t所说的，对s同样成立。”

5.一阶推演

5.1 定义：取极小、直觉主义、经典命题推演之一，把其归纳定义（定义3.1.1、3.2.1或3.3.1）中的“（极小、直觉主义或经典）命题推演”字样改成“$\Im-$推演”；增加1条基始条件：

1）（$\equiv I$）对于任何项t，

\[t \equiv t\]

是$\Im-$推演。

再增加以下5条归纳条件：

1）（$\forall I$）如果

$D$ $\varphi(y/x)$

是$\Im-$推演，且y不在D的任何前提及$\forall x \varphi$中自由，那么

$D$ $\varphi(y/x)$

\[\forall x\varphi\]

也是$\Im-$推演。

2）（$\forall E$）如果

$D$ $\forall x\varphi$

是$\Im-$推演，那么

$D$ $\forall x\varphi$

\[\varphi(t/x)\]

也是。

3）（$\exists I$）如果

$D$ $\varphi(t/x)$

是$\Im-$推演，那么

$D$ $\varphi(t/x)$

\[\exists x\varphi\]

也是。

4）（$\exists E$）如果

$\ \ \ \ \ \ \ \ \ \ \ \ \varphi(y/x)$ $D_1\ \ \ \ \ \ \ \ \ D_2$ $\exists x\varphi\ \ \ ,\ \ \ \psi$

都是$\Im-$推演，且y不在$\exists x\varphi,\psi$及$D_2$的除$\varphi(y/x)$外的前提中自由，那么，

$\ \ \ \ \ \ \ \ \ \ \ \ [\varphi(y/x)]$ $D_1\ \ \ \ \ \ \ \ \ D_2$ $\exists x\varphi\ \ \ ,\ \ \ \psi$

\[\psi\]

也是$\Im-$推演。

5）（$\equiv$ E）如果

$D_1\ \ \ \ \ \ D_2$ $t\equiv s\ \ \ ,\ \ \ \varphi(t/x)$

是$\Im-$推演，那么，

$D_1\ \ \ \ \ \ D_2$ $t\equiv s\ \ \ ,\ \ \ \varphi(t/x)$

\[\varphi(s/x)\]

也是。

这样定义的$\Im-$推演，称为相应的（极小、直觉主义或经典）逻辑的一阶推演。

5.2 定义：设$\Phi$是一个$\mathcal L$-公式集，$\varphi$是一个$\mathcal L$-公式。如果存在一个极小、直觉主义或经典一阶推演D，使得D的前提集是$\Phi$的子集，且D的结论为$\varphi$，则称$\varphi$为$\Phi$的极小、直觉主义或经典一阶语形后承（或在极小、直觉主义或经典逻辑里，从$\Phi$可推演$\varphi$），仍分别记为$\Phi\vdash_m\varphi,\Phi\vdash_i\varphi,\Phi\vdash_c\varphi$。

令$\vdash$是$\vdash_m$，$\vdash_i$或$\vdash_c$。如果$\vdash\varphi$，则分别称$\varphi$为极小、直觉主义或经典逻辑定理。

5.3 定理：对任何公式集$\Phi$和公式$\varphi$，

$\Phi\vdash_m\Rightarrow\Psi\vdash_i\varphi\Rightarrow\vdash_c\varphi$。
前面引理3.1.13-3.1.16所描述的命题语形后承的性质（单调性、前提有穷性、传递性、演绎引理等），对一阶语形后承同样成立。”

6.经典与直觉主义逻辑的关系

6.1 定义：一阶语言中的公式$\varphi$称为否定化的，如果$\varphi$中的原子公式的出现，都直接处于否定词之后，且$\varphi$中不含$\lor$或$\exists$。

6.4 定义：从公式集到公式集中的函数g由以下条件归纳定义：

$\varphi^g=\lnot\lnot\varphi$，如果$\varphi$为原子公式。
$(\lnot\varphi)^g=\lnot\varphi^g$。
$(\varphi\land\psi)^g=\varphi^g\land\psi^g$
$(\varphi\lor\psi)^g=\lnot(\lnot\varphi^g\land\lnot\psi^g)$
$(\varphi\to\psi)^g=\varphi^g\to\psi^g$
$(\forall x\varphi)^g=\forall x\varphi^g$
$(\exists x \varphi)^g=\lnot\forall x\lnot\varphi^g$

6.5 定理：任给公式集$\Phi$和公式$\varphi$，$\Phi \vdash_c\varphi$当且仅当$\Phi^g\vdash_i\varphi^g$。

6.7 系理：对于否定化的$\varphi$，$\vdash_c\varphi$当且仅当$\vdash_i\varphi$。”

第6章可靠性与完全性

我们要证明，经典语义后承概念$\models$与经典语形后承概念$\vdash_c$在外延上恰好重合，就是说$\Phi\models\varphi\Leftrightarrow\Phi\vdash_c\varphi$。

方向“$\Leftarrow$”表明，经典逻辑的推演是有效的推理，语形上的推演不会导致语义上不正确的推理，这称为经典逻辑的可靠性；而“$\Rightarrow$”表明有效的推理都能实现为经典逻辑的推演，语形上的推演穷尽了语义上正确的推理，这称为经典逻辑的完全性。”

1.经典可靠性

1.1 经典逻辑的可靠性定理：对于$\mathcal L$-公式集$\Phi$与$\mathcal L$-公式$\varphi$，如果$\Phi\vdash_c\varphi$，那么$\Phi\models\varphi$。

1.2 系理：对于$\mathcal L$-公式$\varphi$，如果$\vdash_c\varphi$，那么$\models\varphi$。”

2.一致性

2.1 定义：对于$\mathcal L$-公式集$\Phi$，$\Phi$是c-一致的，当且仅当，不存在$\mathcal L$-公式$\varphi$，使得$\Phi\vdash_c\varphi\land\lnot\varphi$。

并非c-一致，称为c-不一致。因此，$\Phi$是c-不一致的，当且仅当在经典逻辑里，$\Phi$可推出矛盾。

2.10 定义：$\mathcal L$-公式集$\Phi$称为极大一致的，如果

$\Phi$是一致的；
对于任何$\mathcal L$-公式$\varphi$，若$\Phi\cup{\varphi}$是一致的，则$\varphi\in\Phi$。

2.13 极大化引理（Lindenbaum）：设$\mathcal L$为一阶语言，如果$\mathcal L$-公式集$\Phi$是一致的，则存在极大一致的$\mathcal L$-公式集$\Psi$，使得$\Phi\subseteq\Psi$。”

3.经典命题完全性

3.1 可满足性引理：如果$\mathcal L^p$-公式集$\Phi$是一致的，则$\Phi$可满足。

3.2 经典命题逻辑完全性定理：对于任何的公式集$\Phi$和公式$\varphi$，如果$\Phi\models\varphi$，那么$\Phi\vdash_c\varphi$。

这个定理的一个特例是：

3.3 定理：如果$\varphi$是重言式，则$\vdash_c\varphi$。

3.4 定理：$\Phi$是可满足的，当且仅当，$\Phi$的任何有穷子集都是可满足的”

第1章 绪论：从直观到形式

1.从“矛盾”说起

2.直观上地推理

3.正确推理

3.1 合规则性

3.2 有效性

4.一阶语言

4.1 命题成分

4.2 外延性与真

4.3 一阶符号语言

5.推演系统

5.1 公式模式与推理规则

5.2 形式推演系统

第2章 集合

1.集合（不）是什么？

2.关系

2.1 等价关系

2.2 序关系

3.函数

4.可数集与不可数集

第3章 一阶语言的语形

1.字母表

2.归纳定义

3.项

4.公式

5.递归定义

6.自由和约束 代入

第4章 经典语义学

1.结构与解释

2.等词、量词和联结词

2.1 等词

2.2 量词

2.3 联结词

3.满足 真

4.语义后承

5. 可满足性 有效性 语义等值

6.代入引理

第5章 自然推演系统

2.联结词规则

2.1 规则的说明

3.命题推演 语形后承

3.1 极小命题逻辑

3.2 直觉主义命题逻辑

3.3 经典命题逻辑

4.量词和等词规则

4.1 量词规则

4.2 等词规则

5.一阶推演

6.经典与直觉主义逻辑的关系

第6章 可靠性与完全性

1.经典可靠性

2.一致性

3.经典命题完全性

第1章绪论：从直观到形式

第2章集合

第3章一阶语言的语形

6.自由和约束代入

第4章经典语义学

3.满足真

5. 可满足性有效性语义等值

第5章自然推演系统

3.命题推演语形后承

第6章可靠性与完全性