离散数学及应用（第2版） 刘铎 清华大学出版社 2018-09-01
100%正版图书
￥ 5.8 1.0折 ￥ 59 九品
仅1件
广东东莞
认证卖家担保交易快速发货售后保障
作者刘铎
出版社清华大学出版社
ISBN9787302496632
出版时间2018-09
装帧平装
开本16开
定价59元
货号9787302496632
上书时间2024-07-04
- 最新上架
商品详情
- 品相描述：九品
- 商品描述
-
前言
作 者 2018年5月
作 者 2012年12月
【免费在线读】
商品简介
离散数学是现代数学的一个重要分支，是计算机专业和软件工程专业的基础主干课程，是进一步学习后续课程以及进行研究和开发的基础。本书根据作者多年教学经验编写而成，着重讲解离散数学的基本概念、基本方法及其应用，给出了大量的典型例题和习题，以及若干综合专题、应用案例和实验项目。全书共10章，内容包括朴素集合论、数论基础、计数基础、命题逻辑、谓词逻辑、二元关系、函数、偏序关系与格、代数结构、图论与树、形式语言、自动机与正则表达式等。附录给出综合性研讨专题、综合实验、名词中英文对照表等。
目录
第1章?基础知识??/ 1
1.1 集合与序列1
1.1.1 集合的基本概念1
1.1.2 集合的运算及性质3
1.1.3 序列6
1.2 数论基础7
1.3 计数基础10
1.3.1 加法法则与乘法法则10
1.3.2 排列与组合11
1.3.3 鸽巢原理16
1.3.4 有限集的计数——容斥原理19
1.3.5 递推关系22
1.4 布尔矩阵及其运算26
习题128
第2章?命题逻辑??/ 41
2.1 命题逻辑的基本概念41
2.2 命题公式及其分类45
2.3 命题逻辑的等值演算48
2.4 对偶与范式53
2.4.1 对偶53
2.4.2 析取范式和合取范式54
2.4.3 主范式56
2.5 命题联结词的完备集63
2.6 命题逻辑的推理64
习题270
第3章?谓词逻辑??/ 79
3.1 谓词与量词79
3.1.1 谓词79
3.1.2 量词80
3.2 谓词公式及分类81
3.3 自然语言形式化83
3.4 谓词逻辑的等值演算86
3.5 前束范式90
3.6 谓词逻辑的推理91
习题398
第4章?二元关系??/ 104
4.1 关系及其表示104
4.1.1 有序对与笛卡儿积104
4.1.2 二元关系的定义106
4.1.3 二元关系的表示109
4.2 关系的运算110
4.2.1 关系的基本运算110
4.2.2 关系的幂和道路113
4.3 关系的性质116
4.3.1 关系性质的定义和判断116
4.3.2 关系运算对性质的保持120
4.4 关系的闭包122
4.5 等价关系和集合的划分127
4.5.1 等价关系、等价类和商集127
4.5.2 集合的划分128
4.5.3 等价关系与划分的一一对应129
*4.6 相容关系与集合的覆盖130
*4.7 关系在计算机中的表示方法131
习题4132
第5章?函数??/ 141
5.1 函数的定义141
5.2 函数的性质142
5.3 函数的复合144
5.4 逆函数146
5.5 计算机科学中的常用函数147
*5.6 双射函数及集合的势152
习题5156
第6章?偏序关系??/ 162
6.1 偏序关系和偏序集162
6.1.1 偏序关系和偏序集的定义与性质162
6.1.2 积偏序和字典序164
6.1.3 哈斯图164
6.2 偏序集中的特殊元素166
6.2.1 偏序集中的特殊元素166
6.2.2 拓扑排序169
6.3 格与布尔代数171
6.3.1 格的定义171
6.3.2 特殊的格174
*6.3.3 布尔代数177
*6.3.4 信息流的格模型179
习题6181
第7章?代数结构??/ 187
7.1 代数结构187
7.1.1 运算与代数结构的定义187
7.1.2 二元运算的性质189
7.2 群192
7.2.1 半群与亚群192
7.2.2 群的概念193
7.2.3 群的性质196
7.2.4 子群198
7.2.5 循环群与置换群199
7.2.6 陪集与拉格朗日定理200
7.3 环与域203
7.3.1 环203
7.3.2 域205
7.4 作为代数结构的格与布尔代数206
习题7208
第8章?图论??/ 218
8.1 基本概念218
8.1.1 无向图、有向图和握手定理218
8.1.2 图的同构与子图224
8.1.3 道路、回路与连通性227
8.1.4 图的矩阵表示228
8.2 欧拉图230
8.3 哈密顿图234
8.4 平面图238
8.5 顶点支配、独立与覆盖244
8.6 匹配247
8.6.1 匹配与最大匹配247
8.6.2 霍尔定理及其应用252
8.6.3 匹配与覆盖254
*8.6.4 二部图中的最佳匹配258
8.7 图的着色263
8.8 网络与流267
习题8282
第9章?树及其应用??/ 306
9.1 无向树306
9.2 支撑树及其应用310
9.3 最短道路树321
9.4 根树及其应用325
9.4.1 根树的定义和基本概念325
9.4.2 二叉树的遍历330
9.4.3 最优二叉树与赫夫曼编码332
习题9335
第10章?形式语言、自动机与正则表达式??/ 342
10.1 语言342
10.2 文法346
10.3 巴科斯-诺尔范式和语法图351
10.4 有限状态自动机353
10.5 语言与自动机的关系359
10.6 正则表达式361
习题10362
附录A?综合性研讨专题??/ 371
A.1 凑邮资、分油、爬台阶与台球桌371
A.1.1 邮资问题371
A.1.2 分油问题373
A.1.3 登阶问题376
A.1.4 台球问题378
A.2 基于模运算的校验码379
A.2.1 EAN-13码379
A.2.2 新版国际标准书号ISBN-13380
A.2.3 第二代身份证380
A.3 应用鸽巢原理的纸牌魔术二则382
A.3.1 纸牌魔术A382
A.3.2 纸牌魔术B384
A.4 完美洗牌法385
A.5 Chomp游戏388
A.6 麻花辫390
A.7 伯恩赛德引理与波利亚定理394
A.8 顿时错乱问题398
A.9 抽芽游戏与抱子甘蓝游戏402
A.9.1 抽芽游戏402
A.9.2 抱子甘蓝游戏405
A.10 汉诺塔杂谈407
A.10.1 汉诺塔图407
A.10.2 汉诺塔的非递归算法410
A.10.3 汉诺塔与普通二进制码411
A.11 存储器轮412
A.11.1 存储器轮及解决方法412
A.11.2 德·布鲁因序列414
A.12 中国邮路问题417
A.13 格雷码、超立方体的哈密顿回路和九连环420
A.13.1 格雷码420
A.13.2 超立方体图中的哈密顿回路421
A.13.3 九连环与格雷码423
A.14 谢尔宾斯基三角426
附录B?课程综合实验??/ 433
B.1 实验一：汉诺塔问题的变体433
B.1.1 实验内容433
B.1.2 实验要求434
B.1.3 扩展阅读435
B.2 实验二：命题演算的计算机实现435
B.3 实验三：二元关系及其应用436
B.3.1 准备工作436
B.3.2 等价关系及其应用436
B.3.3 偏序关系及其应用437
B.3.4 连通性和欧拉道路/回路439
B.4 实验四：村庄修引水渠问题440
B.4.1 实验内容（一）441
B.4.2 实验内容（二）442
B.4.3 讨论与思考442
B.5 实验五：考场安排问题443
B.5.1 实验内容443
B.5.2 实验要求444
B.6 实验六：展览馆的参观与维护444
B.7 实验七：导师和研究生的自动分配445
B.8 实验八：绿色健康城市规划446
B.9 实验九：羽毛球双打配对和住宿安排446
附录C?名词英汉对照表??/ 448
附录D?使用Mathematica学习离散数学??/ 459
D.1 集合、序列与矩阵459
D.2 排列、组合、递推关系与划分462
D.3 关系与有向图463
D.4 图467
D.5 树471
附录E?Prolog语言与逻辑推理??/ 473
E.1 Prolog基础473
E.2 典型逻辑问题479
参考文献??/ 483
VIII
离散数学及应用（第2版）
IX
目录
内容摘要
\" 离散数学是现代数学的一个重要分支，是计算机专业和软件工程专业的基础主干课程，是进一步学习后续课程以及进行研究和开发的基础。本书根据作者多年教学经验编写而成，着重讲解离散数学的基本概念、基本方法及其应用，给出了大量的典型例题和习题，以及若干综合专题、应用案例和实验项目。全书共10章，内容包括朴素集合论、数论基础、计数基础、命题逻辑、谓词逻辑、二元关系、函数、偏序关系与格、代数结构、图论与树、形式语言、自动机与正则表达式等。附录给出综合性研讨专题、综合实验、名词中英文对照表等。
本书结构紧凑，内容精练，体系严谨，语言流畅，讲解详细，可作为高等院校计算机或软件工程专业本科生的“离散数学”课程教材，也可供其他专业学生和科技人员阅读参考。
\"
主编推荐
“中国大学MOOC”平台“离散数学”课程指定教材
【内容简介】
精彩内容
第5章函数
函数是一种特殊的关系，也称为映射，它在计算机科学与技术以及相关学科中有着重要的作用和广泛的应用。
最初开始使用“函数”一词的是莱布尼茨（Leibniz，1646—1716），用以描述曲线的一个相关量；而中文的“函数”一词由清朝数学家李善兰（1811—1882）译出。
本章主要介绍函数的定义、几种特殊的函数及相关性质、函数的运算以及常用的一些函数。
5.1函数的定义 定义5.1设f为集合A到B的二元关系,若对于任意xDom(f)都存在唯一的yRan(f)使得(x,y)f成立，则称f为函数(function)，此时记y=f(x)，称x为自变量（argument），y为f在x的值（value）或x在f作用下的像（image）。函数也称作映射（mapping）或变换（transformation）。
注：A=A1A2…An时，一般也将f((x1,x2,…,xn))简记为f(x1,x2,…,xn)。
函数的定义如图5.1所示。
图5.1函数 【例5.1】R1={(1,1),(2,3),(4,1),(3,5),(5,3)}是函数，而R2={(1,1),(1,3),(4,1),(3,5),(5,3)}不是函数，因为R2(1)={1,3}。
在函数R1中，R1(1)=1,R1(2)=3,R1(4)=1,R1(3)=5,R1(5)=3，于是R1也可以写作R1={(1,R1(1)),(2,R1(2)),(4,R1(4)),(3,R1(3)),(5,R1(5))}。
【例5.2】设A=B=，则、、都是函数。
注：两个函数f和g相等当且仅当满足下面两个条件： （1）Dom(f)=Dom(g)。
（2）对于任意xDom(f)=Dom(g)都有f(x)=g(x)。
例如，函数f(x)=(x2-1)/(x-1)和g(x)=x+1不相等，因为Dom(f)Dom(g)。
定义5.2设A、B是非空集合，f是A到B的一个关系，如果对每个xA，存在唯一的yB，使得(x,y)f，则称f为A到B的函数，记作f:A→B。
注：对于A到B的函数f，Dom(f)=A，Ran(f)B。
如果一个A到B的关系是函数，则它的关系矩阵中每一行至多有一个1；如果它是一个A到B的函数，则它的关系矩阵每一行恰好有一个1。
如果一个A上的关系是函数，则它的关系图中每一个顶点至多发出一条有向边（出度不超过1）；如果它是一个A上的函数，则它的关系图中每一个顶点恰好发出一条有向边（出度恰为1）。
【例5.3】设A=B=，则是到的函数，而、则不是。
定义5.3设函数f:A→B,A1A，则称f(A1)={f(x)|xA1}为A1在f下的像（imageofA1underf），f(A)称为函数的像（image）。
【例5.4】设函数f:→定义为f(1)=1，f(n)=n–1(n>1)，则有f({2,3})=f({1,2,3})={1,2}。
下面定义一些常用的函数。
定义5.4 （a）设f:A→B，如果存在cB使得对所有的xA都有f(x)=c，则称f:A→B是常值函数。
（b）设A是非空集合，称A上的恒等关系IA为A上的恒等函数（identityfunction），也记作1A。即对于所有的xA，1A(x)=x。
（c）设R是A上的等价关系，定义从A到A/R的函数g:A→A/R，对任意aA，g(a)=[a]，即将元素映到该元素所在的等价类，称g是从A到商集A/R的典范映射（canonicalmap）或自然映射。
注：给定集合A和A上的一个等价关系R，就可以确定一个典范映射g:A→A/R。不同的等价关系确定不同的典范映射。
【例5.5】定义函数g为g(x)=2，则g是到的常值函数。
【例5.6】A={1,2,3}上的等价关系R={(1,1),(1,3),(2,2),(3,1),(3,3)}∪IA所确定的典范映射是g1(1)=g1(3)={1,3},g1(2)={2}；A={1,2,3}上的等价关系IA所确定的典范映射是g2(1)={1},g2(2)={2},g2(3)={3}。
5.2函数的性质 定义5.5设函数f:A→B。
（a）若Ran(f)=B，则称f是满射（surjection）或映上的（onto）。
（b）若任意yRan(f)都存在唯一的xA使得f(x)=y，则称f:A→B是单射（injection）或一一的（one-to-one）； （c）若f既是满射又是单射，则称f是双射（bijection）或一一对应（one-to-onecorrespondence）。
函数的满射、单射和双射如图5.2所示。其中，(a)是满射，(b)是单射，(c)是双射。
— 没有更多了 —
以下为对购买帮助不大的评价