第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
第3节真值指派 第2章命题逻辑 围。某种意义上来说,逻辑学关心的不是“原子事实”的真假,而是怎样处理由逻辑符号 生成的复合命题的真假。我们今后会看到,这一点在一阶逻辑的真值理论中表现得更为明 对初学者来说,除了对蕴涵式的规定外,其它的都好理解。当然,我们可以简单地 说:在数学中蕴涵就是这样规定的。但我们还是给出几种解释,希望能说服初学者这样的 规定是有道理的。在专门的模态逻辑课程中对蕴涵的意义往往会有更多的讨论。 第一种解释:考察:“如果中国足球队夺冠,我就把我鼻子吃了” 假设我在看球时跟朋友说了这样的话,而比赛结果真的是中国队夺冠(前件为真), 那朋友绝对有权利要求我把自己的鼻子吃了,因为否则我就说了假话(后件为假,所以整 个命题为假,见真值表的第二行第六列。),无面目站在讲台之上。但是,更为可能的是中 国队没有夺冠(前件为假,在我的记忆中,这个命题总是假。),那朋友就没有权利要求我 吃鼻子了,因为无论如何,我都说了真话(既然前件为假,无论后件是否为真,整个命题 都真。见真值表的第三行第四行,第六列。)。 第二种解释:考察(A∧B)→B。 在这个例子中,后件“包含”在前件中。当我们肯定了前件时,当然肯定了作为其 部分的后件,所以直观上这个命题无论如何都是真的。考察真值表的结果也是一样,不管 A,B取何值,整个公式一定为T。现在考虑如下两种情况:(1)A为假而B为真,则我 们得到的是F→T;(2)B为假,这时前件和后件都是假的,我们得到F→F。但根据 以上的讨论,整个命题依然为真。所以F→T和F→F的真值都应设为T。 第三种解释:我们自行设计我们觉得满意的真值表 B(a→B) aTTFF 首先,大家对前两行应该没有异议。剩下的是选择X和Y的值。我们选了X Y=T大家不满意。现在你们来选。只有三种可能,大家会发现都不合适。第一种可能 X=T,Y=F,这时第二列与第三列完全相同,即A→B与A的真假全无关系。第 种可能:X=F,Y=T,这与A分B相同。第三种可能:X=Y=F,这与AAB相 同 例21.令a为下列合式公式 (B→(A→C)分(B∧A)→C) 假定v(4)=v(B)=T并且v(C)=F。找出v(a)的值。 答案:(a)=T
第 3 节 真值指派 第 2 章 命题逻辑 围。某种意义上来说，逻辑学关心的不是“原子事实”的真假，而是怎样处理由逻辑符号 生成的复合命题的真假。我们今后会看到，这一点在一阶逻辑的真值理论中表现得更为明 显。 对初学者来说，除了对蕴涵式的规定外，其它的都好理解。当然，我们可以简单地 说：在数学中蕴涵就是这样规定的。但我们还是给出几种解释，希望能说服初学者这样的 规定是有道理的。在专门的模态逻辑课程中对蕴涵的意义往往会有更多的讨论。 第一种解释：考察：“如果中国足球队夺冠，我就把我鼻子吃了”。 假设我在看球时跟朋友说了这样的话，而比赛结果真的是中国队夺冠（前件为真）， 那朋友绝对有权利要求我把自己的鼻子吃了，因为否则我就说了假话（后件为假，所以整 个命题为假，见真值表的第二行第六列。），无面目站在讲台之上。但是，更为可能的是中 国队没有夺冠（前件为假，在我的记忆中，这个命题总是假。），那朋友就没有权利要求我 吃鼻子了，因为无论如何，我都说了真话（既然前件为假，无论后件是否为真，整个命题 都真。见真值表的第三行第四行，第六列。）。 第二种解释：考察 (A ∧ B) → B。 在这个例子中，后件“包含”在前件中。当我们肯定了前件时，当然肯定了作为其一 部分的后件，所以直观上这个命题无论如何都是真的。考察真值表的结果也是一样，不管 A，B 取何值，整个公式一定为 T。现在考虑如下两种情况：（1）A 为假而 B 为真，则我 们得到的是 F → T；（2）B 为假，这时前件和后件都是假的，我们得到 F → F。但根据 以上的讨论，整个命题依然为真。所以 F → T 和 F → F 的真值都应设为 T。 第三种解释：我们自行设计我们觉得满意的真值表： α β (α → β) T T T T F F F T X F F Y 首先，大家对前两行应该没有异议。剩下的是选择 X 和 Y 的值。我们选了 X = Y = T 大家不满意。现在你们来选。只有三种可能，大家会发现都不合适。第一种可能： X = T，Y = F，这时第二列与第三列完全相同，即 A → B 与 A 的真假全无关系。第二 种可能：X = F，Y = T，这与 A ↔ B 相同。第三种可能：X = Y = F，这与 A ∧ B 相 同。 例 2.1. 令 α 为下列合式公式 (((B → (A → C)) ↔ ((B ∧ A) → C)))。 假定 v(A) = v(B) = T 并且 v(C) = F。找出 v(α) 的值。 答案：v(α) = T。 6
第2章命题逻辑 第3节真值指派 回到∂的定义。注意在定义中可在定义和被定义的部分同时出现。这样的定义方法是 递归定义的一个例子。递归定义在数学上很常见,比如,阶乘函数n!就可以递归定义成 0!=1并且对所有自然数n,(n+1)!=(n+1)×ml;又比如菲波那契序列f可以递归定 义为f=f1=1并且对所有自然数n,fn+2=fn+fn+1。直观上很容易接受下述定理 定理22.对任意S上的真值指派v都有唯一的一个扩张:5→{T,F}满足前述条件0 5)。 定理2.2的证明本质上是验证递归定义的合理性,即递归定义并没有犯循环定义的错 误。在很多集合论的教科书内都有递归定义合理性的证明,有兴趣的读者可以参考,我们 这里就省略了。 我们称一个真值指派v满足一个公式φ如果可(p)=T。 定义22.我们称一个公式集∑重言蕴涵公式r,记为∑卡T,如果每一个满足∑中所有 公式的真值指派都满足r。 ∑}τ也被读作T是∑的语义后承。如果我们把它的定义用数学语言展开,就会 发现它涉及不止一个量词。∑r当且仅当“对所有的真值指派v[如果(对所有的公式 σ∈∑,列()=T)则列(7)=们”。 例22. 1)验证{(a∧B)}a (2)公式集{A,(A)}重言蕴涵B吗? 答案:是。 我们称一个公式T为一个重言式(记作上T)如果0}r。这与通常的“重言式在所 有真值指派下为真”或“重言式被所有真值指派满足”的说法是一致的。原因是所有的真 值指派υ都满足“空集中每一元素”。不然的话,空集中就会有一个元素让不满足它, 而这显然是不可能的。 如果∑={}只含有一个公式,我们有时会把{a}=r简写成σ卡=T。如果ar和 T}σ都成立,则我们说σ和r重言等价。 重言式举例 (1)结合律 (AV(BVC)分(AVB)VC) (A∧(B∧C)分((AAB)AC) 菲波那契, Fibonacci(约1170-约1250),意大利数学家
第 2 章 命题逻辑 第 3 节 真值指派 回到 v 的定义。注意在定义中 v 在定义和被定义的部分同时出现。这样的定义方法是 递归定义的一个例子。递归定义在数学上很常见，比如，阶乘函数 n! 就可以递归定义成 0! = 1 并且对所有自然数 n, (n + 1)! = (n + 1) × n!；又比如菲波那契1序列 fn 可以递归定 义为 f0 = f1 = 1 并且对所有自然数 n, fn+2 = fn + fn+1。直观上很容易接受下述定理： 定理 2.2. 对任意 S 上的真值指派 v 都有唯一的一个扩张 v : S → {T, F} 满足前述条件 (0) – (5)。 定理 2.2 的证明本质上是验证递归定义的合理性，即递归定义并没有犯循环定义的错 误。在很多集合论的教科书内都有递归定义合理性的证明，有兴趣的读者可以参考，我们 这里就省略了。 我们称一个真值指派 v 满足 一个公式 φ 如果 v(φ) = T。 定义 2.2. 我们称一个公式集 Σ 重言蕴涵 公式 τ，记为 Σ |= τ，如果每一个满足 Σ 中所有 公式的真值指派都满足 τ。 Σ |= τ 也被读作 τ 是 Σ 的语义后承 。如果我们把它的定义用数学语言展开，就会 发现它涉及不止一个量词。Σ |= τ 当且仅当“对所有的真值指派 v [如果（对所有的公式 σ ∈ Σ，v¯(σ) = T）则 v¯(τ ) = T]”。 例 2.2. (1) 验证 {(α ∧ β)} |= α。 (2) 公式集 {A,(¬A)} 重言蕴涵 B 吗？ 答案：是。 我们称一个公式 τ 为一个重言式 （记作 |= τ）如果 ∅ |= τ。这与通常的“重言式在所 有真值指派下为真”或“重言式被所有真值指派满足”的说法是一致的。原因是所有的真 值指派 v 都满足“空集中每一元素”。不然的话，空集中就会有一个元素让 v 不满足它， 而这显然是不可能的。 如果 Σ = {σ} 只含有一个公式，我们有时会把 {σ} |= τ 简写成 σ |= τ。如果 σ |= τ 和 τ |= σ 都成立，则我们说 σ 和 τ 重言等价 。 重言式举例 (1) 结合律： ((A ∨ (B ∨ C)) ↔ ((A ∨ B) ∨ C))。 ((A ∧ (B ∧ C)) ↔ ((A ∧ B) ∧ C))。 1菲波那契，Fibonacci（约 1170 - 约 1250），意大利数学家 7
第4节唯一可读性 第2章命题逻辑 (2)交换律: (AVB)分(BVA) (A∧B)分(B∧A) )分配律 (A∧(B∨C)分(A∧B)V(AAC) (V(BAC)分(AVB)∧(AVC) (4)双重否定 (5)德摩根2定律 (-(A∨B)分(4)∧(=B)。 ((A∧B)分(-4)∨(-B)) (6)其它 排中律:(AV(A) 矛盾律:(-(AA(=4)) 逆否命题:(A→B)4(-B)→(A)) 第4节唯一可读性 自然语言中有大量的与标点有关的有歧义的例子。举一个雅一点的,《论语·子罕》 中的“子罕言利与命与仁”;再举个俗一点的,如段子里的“叔叔亲了我妈妈也亲了 我”。但自然语言中的歧义往往与语义有关。我们这一节要讲的是纯语法的。我们将论证 按照第一节中规则生成的合式公式没有歧义。这里的“歧义”与语义无关,指的是无论 谁来把一个公式分解成子公式,其“结果”都是一样的。或许从反面理解容易一点。像 A→B分C或A∧BVC这样的表达式就有“歧义”,因为没有表达清楚是先处理A和 B之间的运算呢,还是B和C之间的。这一节与后面的内容关系不大,除了最后的一些 约定外,其它内容可以暂时跳过。 定理23(唯一可读性).对任意公式a,下列陈述有且仅有一条适用 2德摩根, Augustus De morgan(1806-1871),英国逻辑学家,数学家 8
第 4 节 唯一可读性 第 2 章 命题逻辑 (2) 交换律： ((A ∨ B) ↔ (B ∨ A))。 ((A ∧ B) ↔ (B ∧ A))。 (3) 分配律： ((A ∧ (B ∨ C)) ↔ ((A ∧ B) ∨ (A ∧ C)))。 ((A ∨ (B ∧ C)) ↔ ((A ∨ B) ∧ (A ∨ C)))。 (4) 双重否定： ((¬(¬A)) ↔ A)。 (5) 德摩根2定律 ： ((¬(A ∨ B)) ↔ ((¬A) ∧ (¬B)))。 ((¬(A ∧ B)) ↔ ((¬A) ∨ (¬B)))。 (6) 其它： 排中律： (A ∨ (¬A))。 矛盾律： (¬(A ∧ (¬A)))。 逆否命题： ((A → B) ↔ ((¬B) → (¬A)))。 第 4 节 唯一可读性 自然语言中有大量的与标点有关的有歧义的例子。举一个雅一点的，《论语·子罕》 中的“子罕言利与命与仁”；再举个俗一点的，如段子里的“叔叔亲了我妈妈也亲了 我”。但自然语言中的歧义往往与语义有关。我们这一节要讲的是纯语法的。我们将论证 按照第一节中规则生成的合式公式没有歧义。这里的“歧义”与语义无关，指的是无论 谁来把一个公式分解成子公式，其“结果”都是一样的。或许从反面理解容易一点。像 A → B ↔ C 或 A ∧ B ∨ C 这样的表达式就有“歧义”，因为没有表达清楚是先处理 A 和 B 之间的运算呢，还是 B 和 C 之间的。这一节与后面的内容关系不大，除了最后的一些 约定外，其它内容可以暂时跳过。 定理 2.3 (唯一可读性). 对任意公式 α，下列陈述有且仅有一条适用： 2德摩根，Augustus De Morgan （1806 - 1871），英国逻辑学家，数学家。 8
第2章命题逻辑 第5节其它联词 1)a是一个命题符号。 2)a形为(-ao)其中a0为一合式公式。 (3)a形为(a1*a2)其中a1和a2为合式公式,*为某个二元联词。 不仅如此,在情形(2)和⑧3)中,公式ao,a1和a2还有二元联词大都是唯一的 证明:首先,令P(a)表示性质“(1)或(2)或(3)对a适用”。对P(a)用归纳很容易证明 三条中至少有一条适用。 然后让我们排除重叠的情形。情形(1)与情形(2)和(3)都没有重叠,因为(1)中第 个符号是命题符号,而(2)和(3)中第一个符号都是左括号;注意我们现在讨论语法,a 是作为字符串来考虑的,两个字符串相等当且仅当它们长度相同,并且每一个字节上的符 号都相同。同样,通过比较第二个字节,容易看出情形(2)和(3)也无重叠。 最后我们检查情形(2)和(3)中的唯一性。我们只看情形(3),因为情形(2)更简单。 假设α=(α1*1a2)=(12B2)(注意:这里=是指作为字符串相等)。则删去第一个左 括号后它们仍相等,a1*1a2)=B12B2)。根据引理2.1,我们有a1=B1,不然的话 个会是另外一个的真前段。继续删去相同段a1和β1,得到为a2)=太2月2)。所以*1=大2 类似地,a2=B2 关于括号省略的一些约定 旦我们知道怎样避免歧义,我们就可以放松一点。记住:底线是一旦有争议,我们 就回到最初,严格遵守规则就好了。 (1)最外的括号总被略去。 (2)否定词的“管辖范围”尽可能短。例如→AVB指的是(-4)VB)。 (3)同一联词反复出现时,以右为先。例如,α→β→γ指的是(a→(B→) 第5节其它联词 让我们再回到语义,研究联词的性质。我们说过,我们之所以选择那五个联词是因为 它们在数学文献中最为常见。很自然的问题是它们够不够用?能不能表达其它所有的联 词?另一方面看,它们有没有多余?在回答这些问题之前,先要把其中涉及的概念搞清 楚。首先,什么是一个任意的联词?字面上看,联词就是把简单句合成复合句的方式。语 义上看,每个联词都唯一确定了从简单句的真假值到复合句真假值的一个规则。说白了
第 2 章 命题逻辑 第 5 节 其它联词 (1) α 是一个命题符号。 (2) α 形为 (¬α0) 其中 α0 为一合式公式。 (3) α 形为 (α1 ⋆ α2) 其中 α1 和 α2 为合式公式，⋆ 为某个二元联词。 不仅如此，在情形 (2) 和 (3) 中，公式 α0，α1 和 α2 还有二元联词 ⋆ 都是唯一的。 证明: 首先，令 P(α) 表示性质“(1) 或 (2) 或 (3) 对 α 适用”。对 P(α) 用归纳很容易证明 三条中至少有一条适用。 然后让我们排除重叠的情形。情形 (1) 与情形 (2) 和 (3) 都没有重叠，因为 (1) 中第一 个符号是命题符号，而 (2) 和 (3) 中第一个符号都是左括号；注意我们现在讨论语法，α 是作为字符串来考虑的，两个字符串相等当且仅当它们长度相同，并且每一个字节上的符 号都相同。同样，通过比较第二个字节，容易看出情形 (2) 和 (3) 也无重叠。 最后我们检查情形 (2) 和 (3) 中的唯一性。我们只看情形 (3)，因为情形 (2) 更简单。 假设 α = (α1 ⋆1 α2) = (β1 ⋆2 β2) （注意：这里 = 是指作为字符串相等）。则删去第一个左 括号后它们仍相等，α1 ⋆1 α2) = β1 ⋆2 β2)。根据引理 2.1，我们有 α1 = β1，不然的话，一 个会是另外一个的真前段。继续删去相同段 α1 和 β1，得到 ⋆1α2) = ⋆2β2)。所以 ⋆1 = ⋆2。 类似地，α2 = β2。 关于括号省略的一些约定 一旦我们知道怎样避免歧义，我们就可以放松一点。记住：底线是一旦有争议，我们 就回到最初，严格遵守规则就好了。 (1) 最外的括号总被略去。 (2) 否定词的“管辖范围”尽可能短。例如 ¬A ∨ B 指的是 ((¬A) ∨ B))。 (3) 同一联词反复出现时，以右为先。例如，α → β → γ 指的是 ((α → (β → γ))。 第 5 节 其它联词 让我们再回到语义，研究联词的性质。我们说过，我们之所以选择那五个联词是因为 它们在数学文献中最为常见。很自然的问题是它们够不够用？能不能表达其它所有的联 词？另一方面看，它们有没有多余？在回答这些问题之前，先要把其中涉及的概念搞清 楚。首先，什么是一个任意的联词？字面上看，联词就是把简单句合成复合句的方式。语 义上看，每个联词都唯一确定了从简单句的真假值到复合句真假值的一个规则。说白了， 9
第5节其它联词 第2章命题逻辑 就是一个真值表。我们给它一个新的名字,称为布尔函数,即,我们称一个从{T,F}映 到{,F}的函数B为一个k元布尔函数 例如,令a为一个仅涉及命题符号A1,A2,…,An的一个公式。那么a就定义了一个 1-元布尔函数Bn Ba(X1,…,Xn)=当A1,…,An被赋予真假值X1,…,Xn时 公式α所取得真假值。 这样每一公式a都表达了一个n-元联词,或m-元布尔函数Bno 有些参考书上会提到0-元联词T和⊥,T代表恒真,⊥代表恒假。如果大家觉得 0-元联词的概念不好理解,我们可以换一种方式来解释。让我们在语言中添加两个常数符 号T和⊥并且修改合式公式的定义如下:所有的命题符号和T还有⊥都是合式公式;如 果a和β都是合式公式,则(-a)和(a大B)也是;别无其它。例如,(A∨⊥)就是新语言 上的一个合式公式。在新语言上真值指派t自然扩展为v(T)=T和v(⊥)=F 例2.3.一元联词有四个:除了本质上是0-元联词的恒真和恒假外,还有恒同和否定。 例24.二元联词有16个。我们分几组讨论(请读者自己做真值表)。 第一组是本质上是0-元联词的恒真和恒假。 第二组是本质上是1-元联词的“与A恒同”,“非A”,“与B恒同”,和“非B”这 四个联词。 第三组是我们已经选的,∧,→,和。还有← 第四组是“A↓B”(也被称为皮尔士3箭头)定义为(AB)和“A|B”(也被称 为谢弗4竖)定义为-(A∧B)。 第五组是“AB”,和“A+B"。特点是如果把F,T分别看成0,1,则 三个联词的取值与“小于”“大于”的判断和加法结果一样(当然1+1=0) 下述定理告诉我们每个n-元布尔函数都可以由某个公式来表达,从而说明我们选的 联词是够用的。在证明一般情形之前,先看一个典型例子 例25.定义M(A,B,C)=A,B,C中的多数,例如M(T,F,T)=T且M(F,F,T)=F。 找出表达M的公式。 答案:( AABAC)V(= AABAO)V(AA=BAC)V(AABA=C) 定理24.对任意的n元布尔函数G,其中n≥1,我们都可以找到一个合式公式a使得a 表达函数G,即G=Ba 3皮尔士, Charles Sanders Peirce(1839-1914),美国逻辑学家,哲学家 4谢弗, Henry M. Sheffer(1882-1964),美国逻辑学家
第 5 节 其它联词 第 2 章 命题逻辑 就是一个真值表。我们给它一个新的名字，称为布尔函数，即，我们称一个从 {T, F} k 映 到 {T, F} 的函数 B 为一个k-元布尔函数 。 例如，令 α 为一个仅涉及命题符号 A1, A2, · · · , An 的一个公式。那么 α 就定义了一个 n-元布尔函数 Bn α： B n α (X1, . . . , Xn) = 当 A1, · · · , An 被赋予真假值 X1, · · · , Xn 时 公式 α 所取得真假值。 这样每一公式 α 都表达 了一个 n- 元联词，或 n-元布尔函数 Bn α。 有些参考书上会提到 0-元联词 ⊤ 和 ⊥ ，⊤ 代表恒真，⊥ 代表恒假。如果大家觉得 0-元联词的概念不好理解，我们可以换一种方式来解释。让我们在语言中添加两个常数符 号 ⊤ 和 ⊥ 并且修改合式公式的定义如下：所有的命题符号和 ⊤ 还有 ⊥ 都是合式公式；如 果 α 和 β 都是合式公式，则 (¬α) 和 (α ⋆ β) 也是；别无其它。例如，(A ∨ ⊥) 就是新语言 上的一个合式公式。在新语言上真值指派 v 自然扩展为 v(⊤) = T 和 v(⊥) = F。 例 2.3. 一元联词有四个：除了本质上是 0-元联词的恒真和恒假外，还有恒同和否定。 例 2.4. 二元联词有 16 个。我们分几组讨论（请读者自己做真值表）。 第一组是本质上是 0-元联词的恒真和恒假。 第二组是本质上是 1-元联词的“与 A 恒同”，“非 A”，“与 B 恒同”，和“非 B”这 四个联词。 第三组是我们已经选的 ∨，∧，→，和 ↔。还有 ←。 第四组是“A ↓ B”（也被称为皮尔士3箭头）定义为 ¬(A ∨ B) 和“A | B”（也被称 为谢弗4竖）定义为 ¬(A ∧ B)。 第五组是“A B”，和“A + B”。特点是如果把 F, T 分别看成 0, 1，则 这三个联词的取值与“小于”“大于”的判断和加法结果一样（当然 1 + 1 = 0）。 下述定理告诉我们每个 n-元布尔函数都可以由某个公式来表达，从而说明我们选的 联词是够用的。在证明一般情形之前，先看一个典型例子。 例 2.5. 定义 M(A, B, C) = A, B, C 中的多数，例如 M(T, F, T) = T 且 M(F, F, T) = F。 找出表达 M 的公式。 答案：(A ∧ B ∧ C) ∨ (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ ¬C)。 定理 2.4. 对任意的 n-元布尔函数 G，其中 n ≥ 1，我们都可以找到一个合式公式 α 使得 α 表达函数 G，即 G = Bn α。 3皮尔士，Charles Sanders Peirce （1839 - 1914），美国逻辑学家，哲学家。 4谢弗，Henry M. Sheffer （1882 - 1964），美国逻辑学家。 10
