离散数学：计算机数学基础教程

　　自然界广泛地存在着离散事物，离散数学就是用适当的数学工具来描述和研究离散对象以及离散对象（Discrete Objects）之间各种相互关系的数学分支。尤其在计算机科学迅速发展的今天，离散数学的研究就更重要了。离散数学的内容很广，如集合论、组合论、图论、群论、数理逻辑等，由于概率论，算法论等也研究离散对象，有人把它们也归纳到离散数学之中。通常，概率论，算法分析已单独列为一门课，此教材中就不包括这些内容了。作为一门计算机专业的基础课，我们着重介绍集合论（集合，自然数集，二元关系），组合论（离散函数，计数与生成），图论（图，树），群论（群，环，域）以及数理逻辑（命题逻辑，谓词逻辑）中较基本的及与计算机科学有较密切联系的内容。本教材是按本人上课用的讲稿写的。最早参考的是金廷赞老师的离散数学讲义，素材主要取自Liu，Chung Laung在美国E11inois大学计算机科学系任教时的讲义基础上写的课本：“Elements of Discete mathematics”，同时参考了J．P．Trembley和R．Manohar著的“离散数学结构及其在计算机科学中的应用”，以及Leon S．Levy著的“Discr-ete Structures of Computer Science”，还有BobrOW和Arbib著的“Discrete Mathematics”等书。后来，又参考左孝凌、张一立、周以铨、洪帆等老师在国内出版的离散数学教材，补充了内容，增加了例子，添上了数理逻辑一章，并在每章后附上了习题。经过1993年、1996年、1997年三次胶印，每次都作了修改和补充，张三元老师参加了修改工作。为了引导学生开阔思路，尽量把自己学习的体会贯穿在教材中。例如：把看上去似乎很简单的概念进行深入一些的讲解；增加一些例子以增强感性认识；指出某些常见的错误；加强前后知识之间的联系等。教材自始至终保持数学的严格性，对于如何证明命题的成立，每一章都有一些示范。编入了不少结合计算机应用的启蒙算法，为学生学以致用搭起了桥梁。编此书的愿望是使学生能学到离散数学的思想方法与处理问题的技巧，且希望达到深入浅出，更便于自学的目的。按讲稿写数学教材是一种尝试，教学效果怎样有待试验，各种缺点在所难免，欢迎大家批评指正。

暂缺《离散数学：计算机数学基础教程》作者简介

第一章　集合
　1 集合
　2　集合的运算及文氏图
　3　笛卡儿积
　4　集合的基数
　习题
第二章　归纳方法
　1　自然数集与皮亚诺公理
　2　数学归纳法
　习题
第三章　二元关系
　1　二元关系
　2　二元关系的运算
　3　A上各类二元关系的性质
　4　等价关系
　5　半序关系
　习题
第四章　离散函数
　1　鸽洞原理
　2　离散数值函数
　3　离散数值函数的生成函数
　4　离散数值函数的递推关系
　习题
第五章　计数与生成
　1　事件及计数原则
　2　典型计数问题
　3　生成函数与排列组合
　4　利用递推关系计数
　5　排列与组合的生成算法
　习题
第六章　数理逻辑基础
　1　命题逻辑
　习题
　2　谓词逻辑
　　习题
第七章　图论
　1 图的概念
　2　图的矩阵表示
　3　加权图中的最短道路问题
　4　欧拉道路与欧拉回路
　5　哈密顿道路
　6　平面图
　7 图的着色
　习题
第八章　树
　1　树的概念和性质
　2　有根树
　3　前缀码
　4　二元检索树
　5　生成树
　习题
第九章　群和环
　1　代数系统
　2　群
　3　陪集及其应用
　4　同构与同态
　5　环和域
　6　多项式环与循环玛
　习题
离散数学习题参考答案