离散数学
2010-1
中国科学技术大学出版社
孙道德，王敏生 主编
307
离散数学作为一门理论兼应用的综合性学科，既具有严谨的理论基础，又具备应用学科的特点，它是计算机科学和其他应用科学的基础理论课。读者通过本课程学习，能培养和训练抽象思维能力和严格的逻辑推理的能力，并了解离散数学在计算机学科和日常生活中的作用，为以后处理离散信息以及用计算机处理大量的日常事务和科研项目，从事计算机科学和应用打下坚实基础。特别是对那些从事计算机科学与理论研究的高层次计算机人员来说，这更是一门必不可少的基础理论工具。 离散数学的主要内容和作用包括：①数理逻辑：含命题逻辑、谓词逻辑和数理逻辑在计算机科学中的应用三部分。其中命题逻辑有：命题、联结词、真值表、公式与公式解释、公式等价和蕴涵关系、范式、命题演算的方法；谓词逻辑有：谓词、量词、谓词公式等价与蕴涵关系，SKOLEM范式、谓词演算的推理规则与推理方法；数理逻辑在计算机科学中的应用有：命题逻辑在计算机科学中的应用，谓词逻辑与数据子语言，谓词逻辑与逻辑程序设计语言，并对以后学习奠定逻辑基础。②集合论：集合的基本概念与各种表示、集合的运算与性质、无限集合、笛卡儿积、序列、整除、容斥原理和鸽笼原理。二元关系、特殊关系及关系在计算机科学中的应用：关系及其表示、关系运算与性质、等价关系、偏序关系、全序关系、良序关系、函数及其特殊函数的定义与性质、关系与函数的证明方法、关系在关系数据库中的应用、关系代数与数据子语言、关系闭包与计算机程序、划分在计算机中的应用。③代数系统：一般代数系统和子代数系统的基本概念及其基本性质、代数系统的同态与同构、同余关系与商代数、半群与群的基本概念与性质、特殊群、陪集与拉格朗日定理、商集、环和域的基本概念与判断方法、格的定义与基本性质、偏序关系与代数系统的关系、特殊格、布尔代数与布尔表达式、有限自动机、计数问题、纠错码和开关电路。④图论：图的基本概念及其各种表示、图的通路与连通性、图的矩阵表示、特殊图（欧拉图、哈密顿图、平面图、二分图、树）的定义和判别方法以及图论在计算机科学中的应用。 本教材以《中国计算机科学与技术学科教程（2002）》中制定的关于离散数学的知识结构和内容体系编写，内容设计增加了帮助理解理论的习题分析，对于培养学生的抽象思维和逻辑表达能力，提高发现问题、分析问题、解决问题的能力起着引导和帮助作用。教材编写力求体系严谨、选材适当、针对性强、有利教学，在素材组织上更加注重在计算机科学技术中的应用。注重语言的通俗性和符号的统一性、规范性、简洁性。
离散数学作为一门理论兼实际应用的综合性学科，既具有严谨的理论基础，又具备应用学科的特点，它是计算机科学和其他应用科学的基础理论课。本教材以《中国计算机科学与技术学科教程（2002）》中制定的关于“离散数学”的知识结构和内容体系编写。全书分为数理逻辑、集合与关系、代数系统与布尔代数4篇，共9章。内容包括：命题逻辑，一阶谓词逻辑，集合及其运算，二元关系，函数，代数结构，格与布尔代数，无向图和有向图，基本图类的算法等。
前言第1篇 数理逻辑 第1-1章 命题逻辑 1-1-1 命题、逻辑联结词与真值表 1-1-2 命题公式与真值函数 1-1-3 公式的等价与蕴涵 1-1-4 命题逻辑的推理理论 1-1-5 对偶与范式 1-1-6 其他逻辑联结词 1-1-7 逻辑联结词的功能完备集 第1-2章 一阶谓词逻辑 1-2-1 基本概念 1-2-2 谓词合式公式与客体变元的约束 1-2-3 谓词公式的等价与蕴涵 1-2-4 谓词逻辑的推理理论 1-2-5 前束范式第2篇 集合与关系 第2-1章 集合及其运算 2-1-1 集合的概念及其表示 2-1-2 集合的基本运算 2-1-3 集合中元素的计数 第2-2章 二元关系 2-2-1 集合的笛卡儿积 2-2-2 二元关系的基本概念及其表示 2-2-3 关系的运算 2-2-4 关系的性质 2-2-5 关系的闭包运算 2-2-6 等价关系与集合的划分 2-2-7 相容关系与集合的覆盖 2-2-8 序关系 第2-3章 函数 2-3-1 函数的概念 2-3-2 逆函数与复合函数 2-3-3 基数、可数集与不可数集第3篇 代数系统篇 第3-1章 代数结构 3-1-1 代数系统的概念 3-1-2 代数系统的运算及其性质 3-1-3 半群与含幺半群 3-1-4 群与子群 3-1-5 交换群与循环群、置换群 3-1-6 陪集与拉格朗日定理 3-1-7 同态与同构 3-1-8 环与域 第3-2章 格与布尔代数 3-2-1 格的概念 3-2-2 分配格 3-2-3 有补格 3-2-4 布尔代数与布尔表达式第4篇 图论 第4-1章 无向图和有向图 4-1-1 图的基本概念 4-1-2 图的道路与连通性 4-1-3 图的矩阵表示 4-1-4 图的着色 第4-2章 基本图类和算法 4-2-1 树与生成树 4-2-2 根树及其应用 4-2-3 平面图与对偶图 4-2-4 欧拉图及其应用 4-2-5 哈密顿图及其应用 4-2-6 图的匹配与匈牙利算法附录 各章知识结识图
第1篇 数理逻辑 数理逻辑是一门应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科。它起源于公元17世纪中叶，德国数学家、哲学家莱布尼兹曾经提出“用计算机代替思维完成推理过程”的设想。其后，由美国数学家布尔于1847年出版的《逻辑的数学分析》一书发展了逻辑代数，通常称布尔代数。德国数学家弗雷格于1879年出版了《表意符号》，引入了量词、约束元，使逻辑演算趋于完备。1930年出生于奥地利的美籍数学家哥德尔的完全性定理证明使数理逻辑基础得以完善，意大利数学家皮亚诺、美国数学家德·摩根、罗素等人对数理逻辑都做出了很大的贡献。20世纪30年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺依曼、图灵、克林等人研究了逻辑与计算的关系。随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真、假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等，不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论、递归论（与形式语言语法有关）、模型论、公理化集合论（与形式语言的语义有关）。 第1-1章命题逻辑 【学习要求】掌握命题、命题公式、重言式、等价式、蕴涵式等基本概念；能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理。
