e书联盟好 下馨半学许算"机系列教材 华 数理逻辑 大 与 学 集合论 计 第二版 11 12 算 1 9 机 8 系 石纯一 王家麽 编著 清华大学出版社 http://www.tup.tsinghua.edu.cn
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 再版前言 随着计算技术的发展，数埕逻辑与集合论做为计算机科学的一种数学工具·它的作用显 得更加重要了、如果仅限于学会一种程序设计语言·掌握一些编程技巧，不一定要学习芸础 性知识，芹至有高中水平款可以了，但对计算礼系的大学生来说，应有更高的要求，仅满足于 写个简单程序就不够了.仍拿种程序设计语言来说，为什么会提出来？它能解决什么问题？ 好在哪里？存在什么问题？它的语法语义又怎样？要懂得一些深层的基础性知识才能对这 兰问题做出回答， 《数理逻辑与集台论》一书的第1版发行至今已有÷多年了，在教学过程中已感到数理 逻辑部分内容浅了些，需增加深层知识，这是本书再版的原因，为此我们在原书的基础上增 加了模型论和证明论两部分，理解这部分内容不甚容易，不求立即直接会用，而是做为基砧 知识的储备，这部分内容是请中国科学院软件研究所王驹研究员编写的，在此表示谢意！ 石纯一 2000.7于清华星 。1·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 前 言 岗散数学足大学算机系的基础数学课程、它以离散量为研究对象.而数学分析（微积 分)以连实啊数为正要究对象，国于连续型数学， 由下}算机的软、梗件都其有离散型结构、从而使离散数学成为计算机科学的某木工 过.例如，Turing对可i计算性的研究所建立的丁urig机是计算机的理论模型.宁致了计算 机的出现：oc的逻辑代数已十分成功地用十计算机的硬件分析和设计：谓词逻辑演算为 人：州能学科提供了·种重要的知识表示和推理方法等. 离散数学的原理和方法常常要求在计算机上的可实现性.而一般数学理论有时仅给出 作在性讨论，这是不能满足实州要求的， 离散数学包括数理逻辑、集合论、代数结构、图论、形式语言、自动机和计算几何等 清华大学计算机系把离散数学安排为“数理逻辑与集合论”和“代数结构与图论“两门课 程，分两个学期讲投，各占)学时.本书是编茗者在讲授“数理逻辑与集合论“时所编写的讲 义基础上完成的.孙承槛、陈群秀和赵琦等同志参加了编写工作，在此表示谢意 离做数学的参考书较多、而且其各部分也有专]的书，本书的编写过程主要参考了上驼 钧的数理逻辑引论、胡世华和陆钟万的《数理逻辑基础？、陈进元等的《离散数学（上）和张 1 锦义的（集合论浅说等书. 山于编菩者水平所限，错误和不当之处任所难免，请读者批评指止， 石纯一王家底 1988.3于清华园
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 目 录 概述……………… 第【章命题逻辑的基本概念………… 2 1.命题…… 1,2命题联结问及其俏表…… 3 小.3介式公式…………… 1.5命题形式化 小.行波兰报达式… 11 习鮑1……*…4… … 第2章命题逻辑的等值和推理演算……1 2.1等值定理……… 公，名等值公式… 15 i 2.3命题公式与真伉表的关系… 2.1联结词的完备集……… 2) 2.5对偶式… 23 2.巧池式…… 21 2.7推理形式…… 29 2.公基不的推理公式… 31 .推理演算… 33 2.10归结推理法… 35 题2………… 第3章命题逻辑的公理化 4) 子，1公理系统的结构…… 10 3.2命题逻辑的公理系统… 41 .3公理系统的完备性和演绎定理 3.1命题逻辑的另-…公理系统一王浩算法… 45 3.5命题逻辑的自然演泽系统… 49 3.6非标准逻辑………………… 50 小题3… 53 第4章谓词逻辑的基本概念… 1.上谓词利个休词…
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 1,2函数城时…………………56 4.3合式公式…………*458 ,1[然语的形式化……*……*……………………………59 .有限城下公式(r)1(r)、(])1(x)的表示法… 53 4,6公式的语遍有效性和判定问题………… 65 以题斗… ……*466 第5章谓词逻辑的等值和推理演算 69 ,1价定明等值式……… 69 5,之情训分配等伯式… 71 5,3池式…… …71 5、4基本的推理公式… 7? 5.5推理演算…… 79 5.6谓词逻辑的归结推理法 82 题5………*……… 84 第6章谓词逻辑的公理化……… ……87 6,1谓词逻辑的公理系统… 87 6,2谓问逻辑的自然演举系统… …92 6.3递山函数 91 6.4相等词和墓状词……… 90 习题6 …02 第7章一阶形式理论及模型…… 103 7.】阶语言及阶埋论………………103 7,2结构、赋值及模型……10列 7,3理论与模型的基本关系完全性定理………105 7.4l0 wenheim-Skolem定理及Herbrand方法………l07 7.了阶形式理论乙，……110 7.6。(0不完全性定理… 111 第8章证明论中的逻辑系统… 8,1-演算…… 8.2Slt域… …+………16 8.3(0 ntzen串形演算…… ……8 8,线性逻辑…… 4124 第9章集合……… 9.1朱合的做念利相衣小打法… ··
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 9.2集合间的关系和特殊集介… 131 9.3集合的运算… 133 .1朱合的图形表示法…… 137 9.5华介达算的性质和证州……138 小.行有限绯合的其数……… 148 9.?集个论公理系统 150 以题9… 135 第10章关系…………………… 150 1,1儿关系…… 16) 1.之关系阵和火系图……… 12 I.3关系的逆、合成、限制和象… 363 }(,4关系的性质…… 18 以.5关系的闭包… 171 1山.6等价关系和划分…… 1T9 10.了利相容关系和泼盖… 183 1以，8偏序关系………… 18d 题10*…… 188 第1章函数… 113 }1,1数和选择公理… ì3 11.2晰数的合成与函数的逆… 04………l07 11.3丙数的性质… 201 11.4开柒与闭集… 213 1】.5模糊子粜… 2(15 小题11… 4……*21(0 第12章实数集合与集合的基数 213 12.1实数集合…… 213 12.2集合的等势… 216 12.3有限集合与无限集合… …*4…]8 12.1集合的基数… *……21 12.5基数的算术运算…… …4219 12.6基数的比较… 22」 12.7可数集合与连续统假设… *………223 题]2…… ………223 10·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 概 述 数理逻辑是研究推理逻辑规律的一个数学分支，它采用数学符号化的方法，给出推理规 则来建立推理体系.进而论理体系的一致性、可苹性和完备全)性等. 数明逻辑的研究内容是两个演算加四论，其体为命趣演算、谓河演算（第】到第6章）、 集介论（第9到第12章）、模型论形式语言语法与语义间的关系)（第：年）、递H论（计算 性可判定性)（第6章）和证明论（数学本身的尤承盾性）（第8章）. 数理逻辑是形式逻辑与数学相结合的产物，红数理逻辑研究的是各学科（包括数学）共 同遵从的·般性的逻辑规律，而各」学科只研究自身的其体规律. 数理逻辑的创始人是17世纪德国数学家和哲学家Le1bn1z,他把数学引人形式逻辑. 1847年1le实现了命题演算，1879年Frege建立.了第个谓词演算系统.到20世纪30 年代数理逻辑进人了一个新的时期.逻辑学不仅与数学相互渗透与结合，而且与其他科学技 术相互渗透与结合，显示了逻辑学的实用意义.1931年G0dcl不安全性定理的提出以及递 归函数可计算性的引人，导致了1936年Turing机器的出现，它是现代电子计算机的理想的 数学模型.10年后1946年第-台电子计算机诞生，数理逻辑与计算机科学、控制论、人工智 能的相互渗透推动了数理逻辑的发展.人们正在模糊逻辑，概率逻辑、归纳逻辑、时态逻辑和 非单调逻辑等方面进行研究. 集合论可看作为数理逻辑的·个分支·也是现代数学的·个独立分支，它是各个数学分 支的共问语言和基础、 集合论是关于无穷集和超穷集的数学理论.古代数学家就已接触到无穷概念，們对无穷 的本质缺乏认识.为微积分十求严密的基础促使实数集结构的研究，早期的门作都与数集或 函数集相关联 集合论中·直引人注意的·些问题有：选择公理A((对任意多个两两不相交的非空集 合，存在一个保合与这些非空集合中的每·个都有唯·的·个共同元素)、连续统假设(H (Cantor对直线上点的个数问题的猜测)，广义连续统假设GCH(无穷集的幂集基数的 猜测) 集合论的创始人是Cnt0r,他从187？华到1383年发表了关于基数、序数和良序失埋论 的·系列结果.1909年前后在他创建的集合论中发现了种种悖论.1908年乙rmelo给出了 朱合论的第·个公理系统Z.此后人们又提ZF和(GB等公理系统.1938年(odel证明∫ 用现有的集合论公理系统不能证明(IH是假的.1963年(oen证明.用现有的集合论公理 系统也不能证明CH是真的，应当寻求新的工其和方法来解决这个问题. 集个论已在：计算机科学、人I:智能学科，逻辑学、经济学、语言学和心理学等方面起若重 要的应刑， 本书以大体相当的篇鲴讲述数理逻辑与集合论的基本内容·鉴于这两部分内答的内在 密切联系，我们使用数理逻帮的方法来引人集合论的有关概念并证明有关定理 ·】·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 第1章 命题逻辑的基本概念 命题逻辑研究的是命题的椎理演算，这一章介绍命题逻辑的基本概念，包括引入命题联 结词，讨论合式公式、重言式以及自然语句的形式化等内容. 1.1命 题 1.1.1什么是命题 命题是一个非真即假（不可兼）的陈述句.有两层意思，首先命题是一个陈述句，而命令 句、疑问句和感叹句都不是命题.其次是说这个陈述句所表达的内容可决定是真还是假，而 且不是真的就是假的，不能不真又不假，也不能又真又假，凡与事实相符的陈述句为真语句， 而与事实不符的陈述句为假语句，这说是说，一个命题具有两种可能的取值（又称真值），为 真或为假，并且只能取其一，通常用大写字母T表示真值为真，用F表示真值为假，有时也 可分别用1和0表示它们.因为只有两种取值，所以这样的命题逻辑称为二值逻辑. 举例说明命题概念： (1)“雪是白的”是一个陈述句，可决定真值，显然其真值为真，或说为T,所以是一个 命题 (2)“雪是黑的”.是一个陈述句，可决定真值、显然其真值为假，或说为F,所以是-个 命题 (3)“好大的雪啊！”不是陈述句，不是命题， (4)“-·个偶数可表示成两个素数之和”（哥德巴赫猜想）.是命题，或为真或为假，只不 过当今尚不知其是真命题还是假命题. (5)“1+101=110”.这是-个数学表达式，相当于一个陈述句，可以叙述为“1加101等 于110”，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围屮真值为真.可 见，这个命题的真值与所讨论问题的范围有关， 1.1.2命题变项 为了对命题作逻辑演算，采用数学手法将命题符号化（形式化）是十分重要的.我们约定 州人写字母表示命题，如以P表示“雪是白的”，Q表示“北京是中国的首都”等.当P表示任 “命题时，P就称为命题变项（变元）. 命题与命题变项含义是不问的，命题指具体的陈述句，是有确定的真值，而命题变项的 真值不，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值.命题 与命题变项像初等数学中常量与变量的关系一样.如5是一个常量，是一个确定的数字，而 x是一个变茧，赋给它·个什么值它就代表什么值，即1的值是不定的.初等数学的运算规 ·2·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 则中对常射变址的处弹腺则是相问的、同样.在命题逻的演算对命题与命题变项的处 埋原也是相问的.因此，除在概念上要区分命题与命题变项外，杯逻辑演箅中就不冉X分 它们了. 1..3简单命题和复合命题 简单命题又称原广命题，它是不包含任何的灯、或、非-类联结训的命趣.1.1.1中所 举的命题例子都是简单命题，这样的命题不可内分制.如：分割就不是命题了.而像命题“ 是广1的1·一2“.就不是简单命遵，它以分割为“雪是F的"以及“】·1公”两个简 单命题，联结可是“且”.在箭单命题中，尽管常有语和渭语，但我们不去加以分料.是将 简单命趣作为·个不可分的整体来看待，进而作命题演算.在端词逻辑里，才对命题中的 谓结构进行深人分析. 把~个或儿个简单命题用联结词（如与、或、非）联站所构成的新的命题称为复合命题· 也称为分子命题.复合命题自然地是陈述句，其自值依赖于构成该复合命题的个简单命题的 真值以及联结词，从而复合命题有确定的真值.如“张三学英语和李四学日语”就是·个复合 命题简单命题“张二学英语“李四学}语”经联结词“和”联结而成，这两个简单命题其值 均为真时，该复合命题方为真.如果只限于简单命题的讨论，则除讨论真值外，中没有叮研究 的内容了，而命题逻辑所讨论的正是多个命题联结而成的复合命题的规律性， 在：数理逻辑里，仅仅把命题看成是~个可取真或取假的陈述句，所关心的并不是这些 共体的陈述的真值究竞为仆么或在什么环境下是真还是假，这是有关学科本身研究的间 题，而逻辑关心的仪是命题可以被赋予真或假这样的可能性，以及规定了真值后思样与其他 命题发生联系， 1.2命题联结词及真值表 联结词可将命题联钻起来构成复杂的命题，命题逻辑联钻词的引人是十分重要的，其作 用相当初等数学里在实数集上定义的·、一、、÷等运算符，通过联结词使可定义新的命 题，从附使命题逻辑的内容变得窗起来，我们要讨论的仅只是复合命题的直值.此值可山 组成它的商单命题的真值所确定.值得注：意的是逻辑联钻词与日常：然用语中的有关联特 词的共问点和不同点. 下介绍h个常用的逻联结词： -、A、V、*、+ 1.2.1否定词7 5定词“·”是个一元联结词，亦称香定符号，个命题P加上否定词就形成了·个新 的命题，记作-P,这个新命题是命题的合定，读作非P. 心词的其侑规定如下：若命题P的真值为真，那么P的真值就为假：若P的直值为 假、那么”的真值就为典.·P与P问的真俏关系、常常使用称作宜值表的一种表格束表 ·5·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 示，如图1.2.1所示. 也可将图1.2.1肴作是对-P的定义.它表明了-P的真值如何依赖于’的真值.真值 表描述了命题之间的宜值关系，很直观，当命题变项的个数不多时，也很容易建立·真值表是 命题逻辑里研究真值关系的重要工具. 例1“昨大张一去看球赛了”，该命题以P表示，丁是“昨天 1”1” TF线1n 张三设有去君球赛”，该新命题便可用P表示. 若昨天张三去看球赛了，命题P是真的，那么新命趣P必然 图」.2.」 是假的.反之，若命题P是假的，那么”P就是真的.这符合图 1.2.1的描述. 例2Q:今天是星期三： Q:今天不是星期三 然而Q不能理解为“今天是星期四”、因为“今天是星期三”的否定，并不一定必是星期 四，还可能是星期五、星期六…在这种情祝下，要注意否定词的含义是否定被否定命题的 全部，而不是一部分 1.2.2合取词八 合取词“A”是个二元命题联结词，亦称合取符号.将两个命题P,Q联结起来，构成一个 、 新的命题PAQ,读作P,Q的合取，也可读作P与Q.这个新命题的真值与构成它的命题 P,Q的真值间的关系，由合取词真值表来规定如图1.2.2. 图1.2.2指出，只有兰两个命题变项P=下，Q=T时方有 P Q PAQ PAQ=T,而P,Q只要有一为F,则PAQ=F,这样看来， FTF PAQ可用来表示日常用语P与Q,或P并且Q. TF 例3P:教室里有10名女同学. T TT Q:教室里有15名男同学， 图1.2.2 不难看出，命题“教室里有10名女同学与15名男同学”，便可由PAQ来描述了， 例4A:今天下雨了. B:教室里有100张桌子， 可知A八B就是命题“今天下雨了并且教室里有100张桌子”， P,Q,A,B都是简单命题、通过合取词A,得到了复合命题PAQ,AAB.复合命题通 过A还可得到复合命题的复合命题. 日常自然用语里的联结词“和”、“与”、“并且”，一般是表示两种同类有关事物的并列关 系（如例3）.而在逻辑语言中仅考虑命题与命题之间的形式关系或说是逻辑内容，并不顾及 日常自然用语中是否有此说法，这样，“A”同“与”、“并且”又不能等同视之.例4在日常自然 用语中是不会出现的语句，因A,B毫无联系，然而在数理逻辑中A八B是可以讨论的. 日常自然用语中说，“这台机器质量很好，但是很贵”，这句话的含义是说同一台机器质 量很好而且很贵.若用P表示“这台机器质量很好”，用Q表示“这台机器很贵”，那么这句话 的逻辑表示就是PAQ,尽管这句话里出现的联结词是“但是”.总之，合取词有“与”、“并月” 的含义，逻辑联结词是自然用语中联钻词的抽象.两者并不等同，这是需注意的. 4
e书联盟好书下载www.book118.com