计算机类专业教育 > ---大类---
离散数学
书号：9787113130343 套系名称：高等学校计算机类课程应用型人才培养规划教材
作者：张辉 张瑜 孙宪坤 出版日期：2011-07-01
定价：24.00 页码 / 开本：232 /16
策划编辑：周海燕 责任编辑：鲍闻
适用专业：无 适用层次：高校
最新印刷时间：
资源下载
教学课件
教学素材(暂无)
习题答案(暂无)
教学案例(暂无)
教学设计(暂无)
教学视频(暂无)
内容简介
前言
目录
作者介绍
图书特色
离散数学是计算机科学基础理论的核心课程，也是现代数学的一个重要分支。本教材包含了集合论、图论、数理逻辑、组合数学、代数系统等内容。在介绍离散数学主要内容的同时，对相关知识的专业应用也做了实用性介绍。本书适合作为计算机和相关专业本科生“离散数学”的教学用书，也可以作为对离散数学感兴趣的学生的参考书。
物理、化学等诸多学科处理的对象都是连续量，它们的发展离不开微积分；与连续量相对应的是离散量，现代数字电子计算机的软硬件结构决定了它更适于离散量的处理，连续量也是通过数字化为离散量来进行处理的。以离散量的结构及其相互关系为研究对象的离散数学，就是计算机学科的“微积分”，它是计算机科学与技术及相关专业的核心课程。
离散数学所涉及的概念、方法和理论，大量地应用在计算机科学与技术专业的数字电路、编译原理、数据结构、算法分析与设计、操作系统、数据库系统、人工智能、多媒体技术、计算机网络等专业课程以及数字信号处理、图形图像处理、编码和信息安全等相关课程中。因此，作为计算机数学基础的离散数学，课程的主旨是训练学生的概括抽象能力、逻辑思维能力和归纳构造能力，培养学生严谨、完整、规范的科学态度，这对于无论是今后从事计算机软硬件开发还是技术管理工作的学生，都是不可缺少的。
随着计算机科学技术的飞速发展及其在生产生活各个方面的广泛应用，离散数学所包括的领域也由经典的数理逻辑、集合论、代数系统和图论等内容，扩展到包括组合数学、数论、有限自动机、计算几何等多个领域。同时，由于我国的高等教育已正式步入大众化阶段，应用型本科院校的任务定位是培养面向生产第一线的本科层次的应用型人才，以培养分析问题、解决问题能力为出发点，强调“学以致用”。本书正是参照教育部高等学校计算机科学与技术教学指导委员会制定的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》中对离散结构知识体系的要求，并结合应用型大学计算机科学与技术专业本科学生的特点而编写的。本书涵盖了经典的离散数学课程的主要内容，包括集合论、图论、数理逻辑、组合数学、代数系统等五篇共9章，确保读者能够获得应有的离散数学知识和解决问题的能力。
本书具有以下特色：
注重应用，理论知识与后继课程中相关应用的介绍结合紧密，使学生充分领略离散数学的重要作用；
内容讲述力求严谨，推演和求解务求详尽，注重培养学生的数学思维能力和分析、解决问题的能力；
取材和组织注重传统与新颖的结合，基础理论的介绍突出重点，以“够用”为限，淡化繁琐、特殊的证明技巧；
通过丰富多样的典型例题分析，使学生对所学知识的掌握更加系统化和条理化，更易于对所学知识融会贯通和举一反三；
注重巩固学生所学知识，培养学生的实践能力，书中每一章都安排了一定量的习题。
本书不仅为计算机专业的学生学习专业后继课程打下扎实的理论基础，也为他们未来的专业发展提供必要的理论储备。
本书适合作为计算机和相关专业本科生“离散数学”的教学用书，也可作为对离散数学感兴趣的学生的参考书。
选用本书可根据不同需要，考虑删选带“*”标记的小节或知识点及相应习题。全书包含了大约可在80学时内讲授的内容；如果删除标记“*”的内容，可以在60学时内完成教学计划。
本书由上海工程技术大学计算机系的张辉担任主编，负责第一、二、三篇的编写及全书的统稿，上海工程技术大学计算机系的张瑜和孙宪坤分别编写了本书的第四篇和第五篇。
南京大学徐洁磐教授不辞辛劳审阅了本书，对本书的编写给予了极大的支持和帮助，提出了许多宝贵的意见和建议，编者在此表示衷心的感谢。同时，感谢上海海事大学周广声教授的精心组织，感谢上海工程技术大学电子电气工程学院领导和计算机系老师们的大力支持和协助。
由于编者水平有限，书中不妥之处在所难免，望广大读者不吝赐教。第一篇 集 合 论
第1章 集合 2
1.1 集合的概念与表示 2
1.1.1 集合及其表示 3
1.1.2 子集与幂集 5
1.2 集合的运算 8
1.2.1 集合的交、并、补、差 8
1.2.2 集合运算的性质 10
*1.3 容斥原理 12
本章小结 15
习题一 15
第2章 关系 18
2.1 关系的概念与表示 19
2.1.1 笛卡儿积 19
2.1.2 关系的概念 21
2.1.3 关系的表示 23
2.2 关系的基本性质 24
2.2.1 自反 24
2.2.2 对称 26
2.2.3 传递 27
2.3 关系的运算 30
2.3.1 关系的交、并、补、差 30
2.3.2 关系的复合 30
2.3.3 关系的逆 32
2.3.4 关系的闭包 33
2.4 等价关系与序关系 36
2.4.1 等价关系与划分 36
2.4.2 序关系 39
本章小结 43
习题二 44
第3章 函数 47
3.1 函数的概念与分类 48
3.1.1 函数的概念 48
3.1.2 函数的分类 50
3.2 函数的运算 54
3.2.1 函数的复合 54
3.2.2 函数的逆 56
*3.3 计算机科学中常用的两类函数 57
3.3.1 取整函数 57
3.3.2 哈希函数 58
*3.4 基数 59
3.4.1 基数的概念 59
3.4.2 可数集与不可数集 61
本章小结 63
习题三 64
第二篇 图 论
第4章 图 68
4.1 图的概念与表示 69
4.1.1 图的基本概念 69
4.1.2 图的矩阵表示 76
4.2 路径与连通性 78
4.2.1 路径与回路 78
4.2.2 图的连通性 80
4.3 欧拉图与汉密尔顿图 83
4.3.1 欧拉图 84
4.3.2 汉密尔顿图 86
*4.4 图的应用 89
4.4.1 最短路径问题 89
4.4.2 支配集与通信系统建站问题 90
本章小结 91
习题四 91
第5章 树 95
5.1 树与图的生成树 95
5.1.1 树的概念与性质 96
5.1.2 图的生成树 98
5.2 根树 101
5.2.1 根树的基本概念 101
5.2.2 二叉树 102
5.2.3 二叉树的遍历 104
*5.3 树的应用 105
5.3.1 决策树 105
5.3.2 二叉搜索树 106
5.3.3 最优二叉树与哈夫曼编码 107
本章小结 109
习题五 109
第三篇 数 理 逻 辑
第6章 命题逻辑 114
6.1 命题与命题公式 115
6.1.1 命题的概念与表示 115
6.1.2 命题联结词 116
6.1.3 命题公式 119
6.2 命题公式的真值赋值与分类 120
6.2.1 真值表 120
6.2.2 重言式、矛盾式与可满足式 122
6.2.3 逻辑等价与逻辑蕴涵 123
6.3 范式 128
6.3.1 合取范式与析取范式 128
6.3.2 主析取范式与主合取范式 129
*6.3.3 联结词的完备集 132
6.4 命题逻辑的推理理论 133
6.4.1 推理的形式结构 134
6.4.2 推理规则 135
本章小结 137
习题六 138
第7章 谓词逻辑 140
7.1 谓词与谓词公式 141
7.1.1 个体、谓词与量词 141
7.1.2 项与谓词公式 143
7.1.3 变元的约束 145
7.2 谓词逻辑的语义 147
7.2.1 真值与解释 147
7.2.2 永真式、矛盾式与可满足式 148
7.2.3 逻辑等价与逻辑蕴涵 149
*7.3 前束范式 152
7.4 谓词逻辑的推理理论 152
本章小结 156
习题七 156
第四篇 组 合 数 学
第8章 组合数学 160
8.1 基本计数原理 161
8.1.1 加法原理 161
8.1.2 乘法原理 161
8.2 排列与组合 163
8.2.1 排列 163
8.2.2 组合 164
*8.2.3 广义的排列与组合 166
8.3 二项式系数与组合恒等式 168
8.3.1 二项式系数 168
8.3.2 组合恒等式 169
*8.4 鸽笼原理 171
8.4.1 鸽笼原理的简单形式 171
8.4.2 鸽笼原理的一般形式 173
*8.5 递归关系及其解法 174
8.5.1 递归关系的定义 174
8.5.2 逆向代换法 177
8.5.3 常系数齐次线性递归关系 177
8.5.4 常系数非齐次线性递归关系 179
本章小结 180
习题八 180
第五篇 代 数 系 统
第9章 代数系统 184
9.1 代数系统的概念及运算性质 185
9.1.1 代数系统的概念 185
9.1.2 二元运算的性质 187
9.2 代数系统的同态与同构 190
9.2.1 同态与同构 190
9.2.2 同态的性质 191
9.3 群 193
9.3.1 半群与独异点 193
9.3.2 群及其基本性质 194
9.3.3 子群与陪集 195
9.3.4 循环群与置换群 200
9.4 环与域 203
9.4.1 环与域的概念 203
*9.4.2 环与域的性质 204
9.5 格与布尔代数 205
9.5.1 格的概念与性质 205
9.5.2 分配格、有补格 206
9.5.3 布尔代数 208
本章小结 210
习题九 210
附录A 213
参考文献 221无