第2章命题逻辑 第1节引言 通常意义下的命题是指有真假值的语句。一个复杂的命题可以分解成若干简单的原 子命题。这些原子命题与复合命题的关系,就是命题逻辑研究的范围。 对初学者来说,一个很自然的问题是当我们研究逻辑时我们用的是什么逻辑?如果我 们用逻辑本身来研究逻辑,那不是循环论证吗?这就引出逻辑学习中区分元逻辑和对象逻 辑的重要性。打个比方来说,我们想要研究人脑的某些功能,但自己直接研究自己是很困 难的。我们于是造一个机器人(或用某个计算机程序来模拟),对机器人我们可以研究得 清清楚楚。虽然机器人与我们相差很远,但如果我们感兴趣的功能是计算或下棋等等,那 么机器人或许可以很近似地模拟人脑,因此我们可以间接地通过研究机器人来了解人脑 的这一部分功能。这个比方中的人脑相当于我们的“元逻辑”,而机器人则相当于“对象 逻辑”。既然计算机学家在研究机器人时完全不必问我们人脑是怎样运作的,我们在研究 对象逻辑时也可以暂时不用考虑我们用的是什么逻辑。只有在我们把当前的功能研究清 楚之后,我们再来思考怎样让机器人更接近人脑。类似的区分还有很多,例如当我们用中 文来研究语言学或计算机语言学,中文就是“元语言”而被硏究的语言或计算机语言则是 ˆ对象语言”。当对象逻辑越来越像元逻辑时,两者的区别越来越小。而命题逻辑因其简 单,比较容易从元逻辑中分别岀来,例如没有人会认为自然数的性质如归纳法是命题逻辑 里面的,所以便于初学者分清元逻辑和对象逻辑,这样在学习一阶逻辑时可以减少一些困 扰。这是本章的一个重要目的。 数理逻辑的一个重要方面是研究手段的局限。贯穿我们课程的一个中心问题是:是否 真的命题都可证。“真”是我们的目的,而“证明”是我们的手段。我们的手段能达到目 的吗?要想回答这个问题,我们首先要搞清楚“真”是什么意思,“证明”又是什么。这 两个重要概念中,“真”属于语义范畴,而“证明”属于语法范畴。在学习过程中,我们 常把“语法”与“语义”分开讨论,但这是暂时的,如同体育活动中分解动作一样。最终 两者是不可分的。语法一边让人想到机器,规则,算法;语义则让人想到人(脑),意义, 真假等等 事实上,一阶逻辑中“是否真的命题都可证”这个问题是我们真正想回答的。但为了 分散学习难点,我们在材料安排上,特意让命题逻辑与一阶逻辑沿相似的主线发展,都包
第 2 章 命题逻辑 第 1 节 引言 通常意义下的命题是指有真假值的语句。一个复杂的命题可以分解成若干简单的原 子命题。这些原子命题与复合命题的关系，就是命题逻辑研究的范围。 对初学者来说，一个很自然的问题是当我们研究逻辑时我们用的是什么逻辑？如果我 们用逻辑本身来研究逻辑，那不是循环论证吗？这就引出逻辑学习中区分元逻辑和对象逻 辑的重要性。打个比方来说，我们想要研究人脑的某些功能，但自己直接研究自己是很困 难的。我们于是造一个机器人（或用某个计算机程序来模拟），对机器人我们可以研究得 清清楚楚。虽然机器人与我们相差很远，但如果我们感兴趣的功能是计算或下棋等等，那 么机器人或许可以很近似地模拟人脑，因此我们可以间接地通过研究机器人来了解人脑 的这一部分功能。这个比方中的人脑相当于我们的“元逻辑”，而机器人则相当于“对象 逻辑”。既然计算机学家在研究机器人时完全不必问我们人脑是怎样运作的，我们在研究 对象逻辑时也可以暂时不用考虑我们用的是什么逻辑。只有在我们把当前的功能研究清 楚之后，我们再来思考怎样让机器人更接近人脑。类似的区分还有很多，例如当我们用中 文来研究语言学或计算机语言学，中文就是“元语言”而被研究的语言或计算机语言则是 “对象语言”。当对象逻辑越来越像元逻辑时，两者的区别越来越小。而命题逻辑因其简 单，比较容易从元逻辑中分别出来，例如没有人会认为自然数的性质如归纳法是命题逻辑 里面的，所以便于初学者分清元逻辑和对象逻辑，这样在学习一阶逻辑时可以减少一些困 扰。这是本章的一个重要目的。 数理逻辑的一个重要方面是研究手段的局限。贯穿我们课程的一个中心问题是：是否 真的命题都可证。“真”是我们的目的，而“证明”是我们的手段。我们的手段能达到目 的吗？要想回答这个问题，我们首先要搞清楚“真”是什么意思，“证明”又是什么。这 两个重要概念中，“真”属于语义范畴，而“证明”属于语法范畴。在学习过程中，我们 常把“语法”与“语义”分开讨论，但这是暂时的，如同体育活动中分解动作一样。最终 两者是不可分的。语法一边让人想到机器，规则，算法；语义则让人想到人（脑），意义， 真假等等。 事实上，一阶逻辑中“是否真的命题都可证”这个问题是我们真正想回答的。但为了 分散学习难点，我们在材料安排上，特意让命题逻辑与一阶逻辑沿相似的主线发展，都包 1
第2节命题逻辑的语言 第2章命题逻辑 含语法部分,规定好语言,硏究推演系统和证明;也包含语义部分,讨论真值理论。最后 以可靠性和完全性定理把语法和语义联系起来。清华大学有位教授曾讲:学习的过程就是 不断重复,不同层次上的重复。希望我们的课程设计能够有助于读者对数理逻辑的理解 第2节命题逻辑的语言 古典命题逻辑的语言包括以下三部分 (1)可数多个命题符号:A0,A1,A2, (2)五个联词:否定符号→、合取符号∧、析取符号、蕴涵符号→和双蕴涵符号φ。 (3)括号:左括号“(,和右括号)” 注: 1.这里“可数”是一个数学专用术语,大意为同自然数一样多。在一般情况下,只要 有足够(有限)多的命题符号就够用了。而另一方面,人们也可以研究有不可数多 个命题符号的逻辑 2.这五个联词尽管与日常语言有关,但在数学文献中更为常见。 3.在本节中我们强调的是语法。因此尽管我们给这五个联词取了上述的名字,并经常 把它们读成“非”,“并且”,“或”,“如果…那么…”,和“当且仅当”,但那是我 们下一节讨论语义的任务。本节中,我们应把它们视为完全没有意义的字符,所以 上面我们特地强调“符号”二字 4.-是一元联词。其它四个是二元联词。这四个二元联词在讨论语法时区别不大,我 们常用符号来表示它们中任何一个联词。 5.括号只是为了便于阅读,以后(习题?)我们会看到,括号实际上是可有可无的。 比如对计算机语言来说,没有括号更为简练。 规定好基本符号之后,我们就可以形成较为复杂的语句。首先我们称任何一个符号串 为一个表达式,例如(A1)或者(41V都是表达式。表达式可以是任意的,完全不用考 虑其是否有“意义”。当然我们感兴趣的是那些“合乎语法规则”的表达式。我们称它们 为合式公式或简称为公式。确切定义如下 定义21
第 2 节 命题逻辑的语言 第 2 章 命题逻辑 含语法部分，规定好语言，研究推演系统和证明；也包含语义部分，讨论真值理论。最后 以可靠性和完全性定理把语法和语义联系起来。清华大学有位教授曾讲：学习的过程就是 不断重复，不同层次上的重复。希望我们的课程设计能够有助于读者对数理逻辑的理解。 第 2 节 命题逻辑的语言 古典命题逻辑的语言 包括以下三部分: (1) 可数多个命题符号 : A0, A1, A2, · · · (2) 五个联词 : 否定符号 ¬ 、合取符号 ∧ 、析取符号 ∨ 、蕴涵符号 → 和双蕴涵符号 ↔ 。 (3) 括号: 左括号 “(”, 和右括号 “)”。 注: 1. 这里“可数”是一个数学专用术语，大意为同自然数一样多。在一般情况下，只要 有足够（有限）多的命题符号就够用了。而另一方面，人们也可以研究有不可数多 个命题符号的逻辑。 2. 这五个联词尽管与日常语言有关，但在数学文献中更为常见。 3. 在本节中我们强调的是语法。因此尽管我们给这五个联词取了上述的名字，并经常 把它们读成“非”，“并且”，“或”，“如果 · · · 那么 · · · ”，和“当且仅当”，但那是我 们下一节讨论语义的任务。本节中，我们应把它们视为完全没有意义的字符，所以 上面我们特地强调“符号”二字。 4. ¬ 是一元联词。其它四个是二元联词。这四个二元联词在讨论语法时区别不大，我 们常用符号 ⋆ 来表示它们中任何一个联词。 5. 括号只是为了便于阅读，以后（习题 ??）我们会看到，括号实际上是可有可无的。 比如对计算机语言来说，没有括号更为简练。 规定好基本符号之后，我们就可以形成较为复杂的语句。首先我们称任何一个符号串 为一个表达式 ，例如 (¬A1) 或者 ((A1∨ 都是表达式。表达式可以是任意的，完全不用考 虑其是否有“意义”。当然我们感兴趣的是那些“合乎语法规则”的表达式。我们称它们 为合式公式 或简称为公式。确切定义如下： 定义 2.1. 2
第2章命题逻辑 第2节命题逻辑的语言 a)每个命题符号A1都是合式公式。 b)如果a和B都是合式公式,则(-a),(a∧B),(aB),(a→B)和(a+B)也是合 式公式。 c)别无其它。 1.定义中的中文即是“元语言”,而本节一开始定义的命题逻辑语言为“对象语言”。 具体地说,我们用了“每个”这个量词,也使用了a,B等符号作为变元代表这个 语言中任意表达式。但这里的量词和符号变元都是元语言中的,显然不属于我们正 在讨论的命题逻辑语言。 2.虽然我们标准的命题符号为A0,A1,A2,…,在实际工作中我们经常用A、B、P 和Q等符号来表示任意的命题符号。 上述定义中(a),(b)不难理解,(c)有些模糊。由于我们会大量使用这类形式的定义, 让我们花一些篇幅解释一下。熟悉抽象代数的读者会看出这实际上是某种“闭包”,或是 由·生成的集合”。在数学上有两种等价的方式将其严格化:“自上而下”或“自下而 上”。两种方式的等价性我们留给习题。 自上而下”的定义将合式公式集作为一个整体定义出来。让我们临时地把一个满 足性质(b)的表达式集X称为封闭的,即,对所有X中的公式a和β,表达式(a)和 (aB)也在X中(其中代表四个二元联词中的任何一个)。全体合式公式的集合可以 自上而下”地定义为:最小的包含所有命题符号的封闭的表达式集,即 {合式公式}=∩x:所有的A1都属于x并且X是封闭的} 注意:条件(c)体现在“最小”里面,被符号∩精确地表达出来。 自上而下”的定义并没有告诉我们每一个具体的合式公式是什么样子的。这一不足 被“自下而上”的定义所弥补了。“自下而上”的定义给出了公式a的一个构造过程。最 下面的当然是命题符号,它们相当于楼梯的第一级台阶。站在这一级上,我们可以构造下 级的公式,如(-A1),(A1∨A2);站在“第二级”上,我们就可以构造“第三级”的公 式,如(-A1)→A2)。如此拾级而上,就会得到任意“高度”的公式。准确地说,我们 称一个表达式的有穷序列 为a的一个构造序列,如果最后一项φn为a并且对每一个i≤n,或者y;是一个命题符 号,或者存在jk<i使得y为(-9)或(*9k)。我们称一个表达式a为一个合式公式 如果存在a的一个构造序列。注意构造序列并不唯一,事实上每一个合式公式都有无穷 多个不同的构造序列
第 2 章 命题逻辑 第 2 节 命题逻辑的语言 (a) 每个命题符号 Ai 都是合式公式。 (b) 如果 α 和 β 都是合式公式，则 (¬α)，(α ∧ β)，(α ∨ β)，(α → β) 和 (α ↔ β) 也是合 式公式。 (c) 别无其它。 注: 1. 定义中的中文即是“元语言”，而本节一开始定义的命题逻辑语言为“对象语言”。 具体地说，我们用了“每个”这个量词，也使用了 α，β 等符号作为变元代表这个 语言中任意表达式。但这里的量词和符号变元都是元语言中的，显然不属于我们正 在讨论的命题逻辑语言。 2. 虽然我们标准的命题符号为 A0, A1, A2, · · · ，在实际工作中我们经常用 A、B、P、 和 Q 等符号来表示任意的命题符号。 上述定义中 (a)，(b) 不难理解，(c) 有些模糊。由于我们会大量使用这类形式的定义， 让我们花一些篇幅解释一下。熟悉抽象代数的读者会看出这实际上是某种“闭包”，或是 “由 · · · 生成的集合”。在数学上有两种等价的方式将其严格化：“自上而下”或“自下而 上”。两种方式的等价性我们留给习题。 “自上而下”的定义将合式公式集作为一个整体定义出来。让我们临时地把一个满 足性质 (b) 的表达式集 X 称为封闭的，即，对所有 X 中的公式 α 和 β，表达式 (¬α) 和 (α ⋆ β) 也在 X 中（其中 ⋆ 代表四个二元联词中的任何一个）。全体合式公式的集合可以 “自上而下”地定义为：最小的包含所有命题符号的封闭的表达式集，即 {合式公式} = ∩ {X : 所有的 Ai 都属于 X 并且 X 是封闭的}。 注意：条件 (c) 体现在“最小”里面，被符号 ∩ 精确地表达出来。 “自上而下”的定义并没有告诉我们每一个具体的合式公式是什么样子的。这一不足 被“自下而上”的定义所弥补了。“自下而上”的定义给出了公式 α 的一个构造过程。最 下面的当然是命题符号，它们相当于楼梯的第一级台阶。站在这一级上，我们可以构造下 一级的公式，如 (¬A1)，(A1 ∨ A2)；站在“第二级”上，我们就可以构造“第三级”的公 式，如 ((¬A1) → A2)。如此拾级而上，就会得到任意“高度”的公式。准确地说，我们 称一个表达式的有穷序列 (φ0, φ1, . . . , φn) 为 α 的一个构造序列，如果最后一项 φn 为 α 并且对每一个 i ≤ n，或者 φi 是一个命题符 号，或者存在 j, k < i 使得 φi 为 (¬φj ) 或 (φj ⋆ φk)。我们称一个表达式 α 为一个合式公式 如果存在 α 的一个构造序列。注意构造序列并不唯一，事实上每一个合式公式都有无穷 多个不同的构造序列。 3
第3节真值指派 第2章命题逻辑 既然每一个公式都是一步步地构造出来的,我们就有可能把通常在自然数上的数学 归纳法转化成“对公式的归纳法”,具体的转化过程我们留作习题。如下形式的归纳原理 非常有用,利用它我们可以直接讨论公式的性质,而不用每次都绕回到自然数上去做归 纳 定理21(归纳原理)令P(a)为一个关于合式公式的性质。假设 1)对所有的命题符号A,性质P(A)成立:并且 2)对所有的合式公式a和如果P(a)和P(B)成立,则P(a)和P(a大B)也成 那么P(a)对所有的合式公式a都成立。 我们用下面的引理来说明归纳原理的用法。在以后我们会用该引理来证明公式的唯 引理21.每一合式公式中左右括号的数目相同。而且每一合式公式的真前段中左括号多 于右括号。因此合式公式的真前段一定不是合式公式。 证明:我们只证明第一个命题,第二个命题的证明完全类似。令P(a)表示在a中左右括 号数目相同。我们对P(a)施行归纳法。初始情形:对所有的命题符号A,性质P(A1)显 然成立,因为左右括号的数目都是零。归纳情形:假设P(a)和P(B)成立,即在a和B 中左右括号的数目都相同。由于(-a)和(a*β)都仅仅添加了最外端的一对括号,它们中 的左右括号的数目依旧保持相同,即P(-a)和P(α大)成立。根据归纳原理,P(a 对所有公式都成立 第3节真值指派 我们开始探讨语义。首先规定真假值集合为{,F},其中T代表“真”,F代表 “假”;很多参考书也用{1,0}来代表。令S为一个命题符号的集合。S上的一个真值指派 U就是从S到真假值的一个映射 U:S→{T,F 令为只含有S中的命题符号的公式集。数学上更准确的说法应该是这样:每一个 联词都对应于一个表达式上的函数,例如,一对应于f:{表达式}→{表达式}, f-(a)=(-a),同样地,每一个二元联词大就对应于f:{表达式}×{表达式}
第 3 节 真值指派 第 2 章 命题逻辑 既然每一个公式都是一步步地构造出来的，我们就有可能把通常在自然数上的数学 归纳法转化成“对公式的归纳法”，具体的转化过程我们留作习题。如下形式的归纳原理 非常有用，利用它我们可以直接讨论公式的性质，而不用每次都绕回到自然数上去做归 纳。 定理 2.1 (归纳原理). 令 P(α) 为一个关于合式公式的性质。假设 (1) 对所有的命题符号 Ai , 性质 P(Ai) 成立; 并且 (2) 对所有的合式公式 α 和 β, 如果 P(α) 和 P(β) 成立，则 P((¬α)) 和 P((α ⋆ β)) 也成 立。 那么 P(α) 对所有的合式公式 α 都成立。 我们用下面的引理来说明归纳原理的用法。在以后我们会用该引理来证明公式的唯 一可读性。 引理 2.1. 每一合式公式中左右括号的数目相同。而且每一合式公式的真前段中左括号多 于右括号。因此合式公式的真前段一定不是合式公式。 证明: 我们只证明第一个命题，第二个命题的证明完全类似。令 P(α) 表示在 α 中左右括 号数目相同。我们对 P(α) 施行归纳法。初始情形：对所有的命题符号 Ai , 性质 P(Ai) 显 然成立，因为左右括号的数目都是零。归纳情形：假设 P(α) 和 P(β) 成立，即在 α 和 β 中左右括号的数目都相同。由于 (¬α) 和 (α ⋆ β) 都仅仅添加了最外端的一对括号，它们中 的左右括号的数目依旧保持相同，即 P((¬α)) 和 P((α ⋆ β)) 成立。根据归纳原理，P(α) 对所有公式都成立。 第 3 节 真值指派 我们开始探讨语义。首先规定真假值 集合为 {T, F}，其中 T 代表“真”，F 代表 “假”；很多参考书也用 {1, 0} 来代表。令 S 为一个命题符号的集合。S 上的一个真值指派 v 就是从 S 到真假值的一个映射 v : S → {T, F}。 令 S 为只含有 S 中的命题符号的公式集。数学上更准确的说法应该是这样：每一个 联词都对应于一个表达式上的函数，例如，¬ 对应于 f¬ : { 表达式 } → { 表达式 }， f¬(α) = (¬α)，同样地，每一个二元联词 ⋆ 就对应于 f⋆ : { 表达式 } × { 表达式 }， 4
第2章命题逻辑 第3节真值指派 f(a,B)=(a大B)。S就是表达式中由S经这五个函数生成的集合(见习题??)。我们把 真值指派v扩张到§上得到新函数 7:S→{T,F}口 满足 (0)对任意A∈S,(A)=v(A) (1) T,如果(a)=F F,其它 (2) (aAm)=T,如果可(a)=T并且可(B)=T QF,其它。 (3) (aV)=7,如果可(a)=T或者可()=T QF,其它。 (a→B) F,如果(a)=T并且可(B)=F, T,其它。 (5) 可(a分B) T,如果(a)=() F,其它。 我们也可以用真值表来表示可 aB(-ma)(aAB)(avB)(a→B)(a分B) TT F T T T FF F T F TT F TFTT TFFT FF T F F 注:以上的真值表虽然再自然不过,但却是命题逻辑语义最根本的部分。首先注意, 在我们考察命题逻辑语言时,联词都被视为无意义的符号;公式也只是按规则排列的符号 串。直到现在,我们才通过定义可来体现联词的意义和规定公式的真假值。同时注意:我 们对命题公式真值的定义是基于元语言做出的,即,只有在真值指派确定以后,公式的 真值才有意义。至于说,例如v为什么让A3为假,而让A4为真等等不是我们考虑的范
第 2 章 命题逻辑 第 3 节 真值指派 f⋆(α, β) = (α ⋆ β)。S 就是表达式中由 S 经这五个函数生成的集合（见习题 ??）。我们把 真值指派 v 扩张到 S 上得到新函数 v： v : S → {T, F} 满足 (0) 对任意 A ∈ S，v(A) = v(A)。 (1) v((¬α)) = { T, 如果 v(α) = F; F, 其它。 (2) v((α ∧ β)) = { T, 如果 v(α) = T 并且 v(β) = T; F, 其它。 (3) v((α ∨ β)) = { T, 如果 v(α) = T 或者 v(β) = T; F, 其它。 (4) v((α → β)) = { F, 如果 v(α) = T 并且 v(β) = F; T, 其它。 (5) v((α ↔ β)) = { T, 如果 v(α) = v(β); F, 其它。 我们也可以用真值表 来表示 v： α β (¬α) (α ∧ β) (α ∨ β) (α → β) (α ↔ β) T T F T T T T T F F F T F F F T T F T T F F F T F F T T 注：以上的真值表虽然再自然不过，但却是命题逻辑语义最根本的部分。首先注意， 在我们考察命题逻辑语言时，联词都被视为无意义的符号；公式也只是按规则排列的符号 串。直到现在，我们才通过定义 v 来体现联词的意义和规定公式的真假值。同时注意：我 们对命题公式真值的定义是基于元语言做出的，即，只有在真值指派 v 确定以后，公式的 真值才有意义。至于说，例如 v 为什么让 A3 为假，而让 A4 为真等等不是我们考虑的范 5