课程简介
离散数学(Discrete Mathematics)："研究离散结构的数学分科。"
--《辞海》79年版, P355
用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个数学证明。
--D.E.Knuth(克纽斯)
1974年Turing奖获得者
离散数学是现代数学的一个重要分支，是计算机科学基础理论的核心课程。离散数学包括数理逻辑、集合论、代数结构、图论、形式语言、自动机和计算几何等。本课程主要介绍其中的数理逻辑和集合论部分。
数理逻辑是研究推理逻辑规则的一个数学分支，它采用数学符号化的方法，给出推理规则来建立推理体系。进而讨论推理体系的一致性、可靠性和完备（全）性等。数理逻辑的研究内容是两个演算加四论，具体为命题演算、谓词演算（第1到第6章）、集合论（第9到第10章）、模型论（形式语言语法与语义间的关系）（第7章）、递归论（可计算性可判定性）（第6章）和证明论（第8章）。数理逻辑是形式逻辑与数学相结合的产物。但数理逻辑研究的是各学科（包括数学）共同遵从的一般性的逻辑规律，而各门学科只研究自身的具体规律。
集合论可看作数理逻辑的一个分支，也是现代数学的一个独立分支，它是各个数学分支的共同语言和基础。集合论是关于无穷集和超穷集的数学理论。古代数学家就已接触到无穷概念，但对无穷的本质缺乏认识。为微积分寻求严密的基础促使实数集结构的研究，早期的工作都与数集或函数集相关联。集合论已在计算机科学、人工智能学科、逻辑学、经济学、语言学和心理学等方面起着重要的应用。
本课程以大体相当的篇幅讲述数理逻辑与集合论的基本内容，鉴于这两部分内容的内在密切联系，我们使用数理逻辑的方法来引入集合论的有关概念并证明有关定理。
◇第一章 命题逻辑的基本概念
◇课前索引
◇第一节 命题
◇第二节 命题联接词及真值表
◇第三节 合式公式
◇第四节 重言式
◇第五节 简单自然句的形式化
◇第六节 波兰表达式
◇章节小结
◇课后习题
◇第二章 命题逻辑的等值和推理演算
◇课前索引
◇第一节 等值定理
◇第二节 等值公式
◇第三节 命题公式与真值表的关系
◇第四节 联接词的完备集
◇第五节 对偶式
◇第六节 范式
◇第七节 推理形式
◇第八节 基本的推理公式
◇第九节 推理演算
◇第十节归结推理法
◇章节小结
◇课后习题
◇第三章 命题逻辑的公理化
◇课前索引
◇第一节 公理系统的结构
◇第二节 命题逻辑的公理系统
◇第三节 命题逻辑的完备性和演绎定理
◇第四节 命题逻辑的另一公理系统
◇第五节 命题逻辑的自然演绎系统
◇第六节 非标准逻辑
◇章节小结
◇课后习题
◇第四章 谓词逻辑的基本概念
◇课前索引
◇第一节 谓词和个体词
◇第二节 函数和量词
◇第三节 合式公式
◇第四节 自然语句的形式化
◇第五节 有限论域下公式的表示法
◇第六节 公式的普遍性和判定问题
◇章节小结
◇课后习题
◇第五章 谓词逻辑的等值和推理演算
◇课前索引
◇第一节 否定型等值式
◇第二节 量词分配等值表
◇第三节 范式
◇第四节 基本的推理公式
◇第五节 推理演算
◇第六节 谓词逻辑的归结推理法
◇章节小结
◇课后习题
◇第六章 谓词逻辑的公理化
◇课前索引
◇第一节 谓词逻辑的公理系统
◇第二节 谓词逻辑的自然演绎系统
◇第三节 递归函数
◇第四节 相等词和摹状词
◇章节小结
◇课后习题
◇第七章 一阶形式理论及模型
◇课前索引
◇第一节 一阶语言及一阶理论
◇第二节 结构、赋值及模型
◇第三节 理论与模型的基本关系
◇第四节 Lowenheim-Skolem 定理
◇第五节 一阶形式Z1
◇第六节 Godel 不完全性定理
◇章节小结
◇课后习题
◇第八章 证明论中的逻辑系统
◇课前索引
◇第一节 λ-演算
◇第二节 Scott 域
◇第三节 Gentzen 串形演算
◇第四节 线性逻辑
◇章节小结
◇课后习题
◇第九章 集合
◇课前索引
◇第一节 集合的概念和表示方法
◇第二节 集合间的关系和特殊集合
◇第三节 集合的运算
◇第四节 集合的图形表示法
◇第五节 集合运算的性质和证明
◇第六节 有限集合及基数
◇第七节 集合论公理系统
◇章节小结
◇课后习题
◇第十章 关系
◇课前索引
◇第一节 二元关系
◇第二节 关系矩阵和关系图
◇第三节 关系的逆、合成、限制和象
◇第四节 关系的性质
◇第五节 关系的闭包
◇第六节 等价关系和划分
◇第七节 相容关系和覆盖
◇第八节 偏序关系
◇章节小结
◇课后习题
◇第十一章 函数
◇课前索引
◇第一节 函数和选择公理
◇第二节 函数的合成与函数的逆
◇第三节 函数的性质
◇第四节 开集与闭集
◇第五节 模糊子集
◇章节小结
◇课后习题
◇第十二章 实数集合与集合的基数
◇课前索引
◇第一节 实数的集合
◇第二节 集合的等势
◇第三节 有限集合与无限集合
◇第四节 集合的基数
◇第五节 基数的算数运算
◇第六节 基数的比较
◇第七节 可数集合与连续统假说
◇章节小结
◇课后习题
本课程是计算机科学基础理论的核心课程，通过课时内的学习及课外练习，学生应能够达到以下目标：
（1） 对数理逻辑与集合论的基本概念有较深入全面的了解；
（2） 系统地掌握命题演算、谓词演算及朴素集合论的经典内容；
（3） 学会形式化演绎推理和定理证明的基本方法；
（4） 强化抽象思维能力、逻辑推理能力和缜密概括能力的培养，进而提高分析问题、解决问题的能力；
（5） 为计算机专业后续课程的学习和科研工作的参与打下坚实的基础。
