本书是国家精品课程主讲教材。本书系统介绍了数理逻辑与基本定理证明方法、二元关系、图论、代数系统与布尔代数中有关的概念、定理及其证明方法。既强化基本概念的描述,还特别着重于阐述有关离散数学的证明方法及离散数学应用实例,并以课程设计和实验的方式举出大量的例子和应用实例,充分展示了离散数学在计算机中的应用。本书有配套的电子教案和《离散数学实验与习题解析》。 本书可作为高等工科院校有关专业学生离散数学课程教材,也适用于计算机专业的科技人员及学生使用。
本书是由电子科技大学离散数学课程组教师共同编写的。电子科技大学离散数学课程于2005年被评为国家级精品课程,2008年被列入国家双语教学示范课程建设项目,2018年被评为国家精品在线开放课程;课程组2009年获得四川省教学团队,2010年所在的“计算机专业核心课程教学团队”获得国家级教学团队。本书就是根据课程组多年讲授离散数学的教学实践经验撰写而成的。
本书针对1-2学期的离散数学课程而设计,适用于高等学校数学类专业、计算机类专业的学生使用,其先行课程为线性代数。
离散数学是现代数学的一个重要分支,也是计算机科学与技术的理论基础,所以又称为计算机数学。
作为数学的一个分支,离散数学的研究对象是各种各样的离散量的结构及其关系,并且一般是有限个或者可数个元素。同时在整个离散数学的讨论中,也非常重视“能行性”问题的研究,即要解决一个问题,首先要证明此问题的解的存在性,但是仅仅解决存在性是不够的,还需要给出得到此问题解的步骤,而且该步骤是有限的、有规则的。这与连续数学中的讨论方式相违背。而且,它由多个数学分支组成,每一个分支基本上可以看成是一个独立的研究领域,它们从不同的角度出发,研究各种离散量之间数与形的关系。同时这些分支也并非相互独立,它们之间有着密切的关系,可以说,离散数学是一门综合的数学学科。离散数学作为计算机科学与技术专业的核心课程,充分地描述了计算机科学离散性的特点,为后继课程,如数据结构、编译系统、操作系统、数据库原理和人工智能、信息安全、计算机网络、算法分析等课程提供了必要的数学基础。
对于学生而言,不仅要学会一些特定的数学知识并知道如何应用,更重要的是要学习如何进行数学思维。本书特别强调数学推理及用不同的方法解题,为学生今后继续学习和工作,参加科学研究,攀登科技高峰,打下坚实的数学基础。
在本书的编写过程中,我们力求充分体现基础与前沿的关系、基础与后续课程的关系,注重理论与实践的结合,强调以逻辑的思想为主线,并在此基础上建立了各种证明问题的方法,突出定义和定理的逻辑描述特征,同时侧重于就若干重要内容介绍其概念和独特的方法,内容以工科学生“够用”为限,突出重点;在阐述内容时,力求做到结构严谨,通俗易懂;推演时务求详尽;大部分概念都用例子加以说明;强化基本概念的描述,注重基本理论的证明方法,目的在于启发学生的思想;淡化大量烦琐的、含有特殊技巧的、不带普遍意义的理论证明方法。针对离散数学的特点,有些问题给出了不同的解法,同一概念给出了不同的描述,希望能起到举一反三的作用。
本书通俗易懂,每个例题和证明都是采用先分析、后求解或证明的描述风格。在每一章前有本章内容提要、学习要求,章后有该章的主要知识点汇集、习题类型、解题分析和证明方法等。另外,由于在学习离散数学的过程中需要相应的数学基础知识,所以在编写本书时增加了一篇预备知识,它包括了学习离散数学所需要的所有数学基础知识,这对学习离散数学会有很大的帮助。
此书分5篇,共15章,第1章、第2章、第6章至第8章由王庆先撰写,第3章至第5章由傅彦撰写,第9章至第11章由顾小丰撰写,第12章至第15章由刘启和撰写,高辉、王丽杰负责全书资源的整理。
由于作者水平有限,书中不当和疏漏之处在所难免,敬请读者不吝赐教。
傅彦,电子科技大学计算机科学与工程学院教授、博士生导师,四川省学术和技术带头人后备人选,主要从事大数据与数据挖掘应用、复杂网络、云计算及信息安全等交叉领域的研究。在PLOSONE和ICDM等国际著名期刊和会议发表论文70多篇,其中被SCI和EI收录论文50多篇;拥有18项大数据应用领域的发明专利和软件著作权;主持多项国家863项目、国家自然基金重点研发项目、军863项目等多项国家项目;参与“网络信息萃取的基础理论和关键算法研究”项目并获得中国计算机学会自然科学二等奖。
第一篇 预置知识
引言
第1章 集合论
1.0 内容提要
1.1 学习要求
1.2 集合
1.2.1 集合的表示
1.2.2 集合与元素的关系
1.2.3 集合与集合的关系
1.2.4 几个特殊的集合
1.2.5 集合的运算
1.2.6 集合的难点
1.3 无限集
1.3.1 可数集合和不可数集合
1.3.2 无限集的难点
1.4 集合的应用
1.5 本章总结
1.6 习题
第2章 计数问题
2.0 内容提要
2.1 学习要求
2.2 基本原理
2.2.1 乘法原理
2.2.2 加法原理
2.2.3 基本原理的难点
2.3 排列与组合
2.3.1 排列问题
2.3.2 组合问题
2.3.3 排列与组合的难点
2.4 容斥原理与鸽笼原理
2.4.1 容斥原理
2.4.2 鸽笼原理
2.4.3 容斥原理与鸽笼原理的难点
2.5 本章总结
2.6 习题
第二篇 数理逻辑
引言
第3章 命题逻辑
3.0 内容提要
3.1 学习要求
3.2 命题与命题联结词
3.2.1 命题
3.2.2 命题联结词
3.2.3 联结词的难点
3.2.4 命题联结词的应用
3.3 命题公式、解释与真值表
3.3 1命题公式
3.3.2 命题公式的解释与真值表
3.3.3 命题公式的分类
3.3.4 命题公式的基本等价关系
3.3.5 命题公式的难点
3.3.6 命题公式的应用
*3.4 联结词的完备集
3.4.1 命题联结词的种数
3.4.2 联结词的完备集
3.4.3 联结词的完备集的应用
3.5 公式的标准型——范式
3.5.1 析取范式和合取范式
3.5.2 主析取范式和主合取范式
3.5.3 范式的难点
3.5.4 范式的应用
3.6 命题逻辑的推理理论
3.6.1 推理的基本概念和推理形式
3.6.2 判断有效结论的常用方法
3.6.3 命题逻辑推理的难点
3.6.4 命题逻辑推理的应用
3.7 本章总结
3.8 习题
第4章 谓词逻辑
4.0 内容提要
4.1 学习要求
4.2 谓词逻辑中的基本概念与表示
4.2.1 谓词
4.2.2 量词
4.2.3 谓词的语言翻译
4.2.4 谓词翻译的难点
4.2.5 谓词翻译的应用
4.3 谓词合式公式与解释
4.3.1 谓词的合式公式
4.3.2 自由变元和约束变元
4.3.3 谓词合式公式的解释
4.3.4 谓词合式公式的分类
4.3.5 谓词合式公式的基本等价关系
4.3.6 谓词合式公式的难点
4.3.7 谓词合式公式的应用
4.4 公式的标准型——范式
……
第三篇 二元关系
第四篇 图论
第五篇 代数系统
参考文献