复旦大学：《数理逻辑》课程教学资源（讲义）第2章命题逻辑.pdf_大学文库

第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

第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 节真值指派回到 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

第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

复旦大学：《数理逻辑》课程教学资源（讲义）第2章 命题逻辑

复旦大学：《数理逻辑》课程教学资源（讲义）第2章命题逻辑