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