本书是国家精品课程——解放军理工大学王元元老师主持的“离散数学”配套的主讲教材,也是教育部高等理工教育教学改革与实践项目——“高等学校计算机科学与技术专业核心课程教学实施方案研究”成果之一。本书内容按照教育部高等学校计算机科学与技术教学指导委员会发布的《高等学校计算机专业核心课程教学实施方案》并参考IEEE&ACM的CC 2008教程编写而成,主要内容包括离散数学四大分支的基础理论:数理逻辑、图论、集合论、抽象代数学。它既注重离散数学内容本身的系统完善,同时又注重与计算机科学的密切联系,具有结构合理、内容系统、阐释新颖的特点。本书取材详略得当,叙述清楚流畅,论证科学严谨,释例、练习精选独到,力求科学性、应用性、工具性和可读性的完美统一。本书可作为高等院校计算机专业及相关专业本科生的离散数学教材和教学参考书,也可作为计算机软硬件研究开发者和应用人员的学习用书,以及大学毕业生考研复习用书。
《离散数学教程(第2版)》针对综合性大学和工程类院校计算机类专业本科生进行选材与编撰,内容覆盖ACM计算机科学课程体系规范2013( Computer Science Cur-ricula 2013)中离散结构知识领域下除离散概率之外的全部知识点。
从离散结构形式化表示理论到各类离散结构及其数学模型的介绍,该书在内容组织上力求做到突出知识内在联系与保持知识模块完整性之间的平衡,从而使教材更具可读性和系统性。该书章节内容不仅覆盖集合论、数理逻辑、组合论、图论、可计算性、抽象代数等基础理论部分,还给出了这些基本理论在粗糙集、模糊集、自动推理、智能搜索、加密技术等领域的应用,并涉及公理化集合论、数理逻辑形式系统、形式语言与自动机等相关理论。该书以离散结构为建模对象,紧密联系计算机科学技术,特别强调应用能力、证明技术、计算思维的培养。
为便于学生及时复习并巩固所学知识,该书在每节后安排了大量习题;同时,为便于学有余力的学生进一步深造,每章后安排了一节阅读材料,以此来对本章所介绍的理论进行深入探讨,或进一步介绍技术的相关应用。
该书不仅可用作高等学校计算机类专业本科生的离散数学课程教材,也可供相关工程技术人员阅读参考。
《离散数学教程》第一版出版距今八年了。这八年来,互联网、人工智能等信息技术推动下的教育革新可谓风起潮涌、方兴未艾。慕课、视频公开课、资源共享课等在线数字资源极大提高了教育的受众面,提升了学习者的个性化学习体验。受惠于这一波革新浪潮,传统的纸质教材也可一改以往刻板单调的形象,结合形式各异的在线资源向读者呈现一个丰富、生动、易得、满足个性化需求的“新形态”。教程第2版正是在这一背景下应运而生。
如上所述,相对教程第1版,本版的最大特色是融合了在线教学资源。这些资源共分为四类:授课幻灯片,重难点讲解,典型习题解答与常见错误分析,以及知识点讲解视频。这些资源来自笔者多年的教学积累与心得,感谢高教出版社“新形态”教材计划,使其有机会被整理出来,与课堂之外的广大读者见面。目前上线的资源只是一部分,后期还会有一些陆续整理完成后上线。
相对前一版次,本版教程在内容上也稍作了一些调整。本版在内容编排上沿袭了前一版中先介绍离散结构形式化表示理论(逻辑代数和集合代数),再依次介绍各类离散结构及其数学模型的思路,但删除了原“准备知识”一章,将原在这一章集中介绍的集合、命题、谓词、运算等基本概念分类并入后续相关章节。作此改动,目的主要是希望在突出知识内在联系的同时更好地保持各个知识模块的完整性,在两者之间取得某种平衡,使教材更具可读性。
此外,本教程还对关系和图论两个知识模块作了扩充,增加了相容关系、图搜索、最短路径、有向无环图等内容的介绍,如此更加突出了教程所强调的在应用能力、证明技术和计算思维培养方面的特色。同时,为控制篇幅本版去掉了原“数论”一章,还请老读者见谅。
我们希望本版能够为读者带来更好的阅读体验,为教师和学生运用本教材教授和学习离散数学课程提供更多更好的帮助。但限于编者专业水平,错误和疏漏之处在所难免,还请读者不吝指正。
王元元,原中国人民解放军理工大学教授、博士研究生指导教师,长期从事计算机基础理论的研究和教学工作。先后被评为总参优秀教员,全军优秀教员;荣获国家教学名师奖、国家教学成果二等奖;荣立二等功一次、三等功三次。其任教的主要课程有离散数学、组合数学以及数理逻辑等,其中离散数学课程被推荐为军队级优质课程和国家精品课程。所主编的教材《计算机科学中的逻辑学》《离散数学》曾分别获得***优秀教材奖和电子工业部优秀教材奖。
宋丽华,中国人民解放军陆军工程大学教授、硕士研究生指导教师,多年从事计算机基础理论的研究和教学工作。曾获军队教学成果一等奖一项,军队科技进步二等奖两项;荣立三等功一次。其任教的主要课程有离散数学、数理逻辑、计算科学基础理论、函数式语言与编译方法等。
第1章 逻辑代数(上):命题演算
1.1 逻辑联结词与命题公式
1.1.1 命题
1.1.2 逻辑联结词
1.1.3 命题公式
1.1.4 语句形式化
练习1.1
1.2 命题演算永真式
1.2.1 重言式
1.2.2 逻辑等价式与逻辑蕴
涵式
1.2.3 对偶原理
1.2.4 逻辑应用
练习1.2
1.3 范式
1.3.1 析取范式与合取范式
1.3.2 主析取范式与主合取
范式
1.3.3 联结词的扩充与归约
练习1.3
1.4 命题演算消解原理
练习1.4
1.5 阅读材料:布尔代数
第2章 逻辑代数(下):谓词演算
2.1 谓词演算基本概念
2.1.1 个体
2.1.2 谓词
2.1.3 量词
2.1.4 谓词公式及语句形式化
练习2.1
2.2 谓词演算永真式
2.2.1 谓词公式的语义
2.2.2 几组谓词演算永真式
2.2.3 谓词公式等价变换的几个
基本原理
练习2.2
*2.3 谓词演算消解原理
2.3.1 前束化与消去量词
2.3.2 谓词演算消解原理简介
练习2.3
2.4 阅读材料:形式推理与形式
系统
2.4.1 一个形式系统的例子
2.4.2 自然推理形式系统ND
第3章 集合代数
3.1 集合的概念与表示
3.1.1 集合基本概念
3.1.2 集合的表示
3.1.3 外延性原理与子集合
练习3.1
3.2 集合运算
3.2.1 并、交、差、补运算
3.2.2 环和与环积运算
3.2.3 幂集与广义并、交运算
练习3.2
3.3 集合的笛卡儿积
练习3.3
3.4 集合的归纳定义
3.4.1 集合的归纳定义方法
3.4.2 集合定义的自然数
练习3.4
3.5 归纳法证明
3.5.1 结构归纳法
3.5.2 数学归纳法
练习3.5
3.6 阅读材料:公理化集合论
简介
第4章 计数
4.1 计数基本原理
4.1.1 加法原理与乘法原理
4.1.2 包含排斥原理
练习4.1
4.2 鸽笼原理
4.2.1 鸽笼原理基本形式
4.2.2 鸽笼原理加强形式
练习4.2
4.3 排列与组合
4.3.1 排列的计数
4.3.2 组合的计数
练习4.3
4.4 重集的排列与组合
4.4.1 重集的排列
4.4.2 重集的组合
4.4.3 错置的计数
练习4.4
4.5 递归式及其应用
4.5.1 递归式建模
4.5.2 递归式求解
练习4.5
4.6 阅读材料:母函数
……
第5章 关系
第6章 函数
第7章 可计算函数
第8章 图与树
第9章 特殊图
第10章 代数结构通论
第11章 群、环、域
参考文献