离散数学及应用（第2版）

图书标准信息

• 作者 刘铎
• 出版社 清华大学出版社
• 出版时间 2018-08
• 版次 2
• ISBN 9787302496632
• 定价 59.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 482页
• 字数 734千字

【内容简介】

离散数学是现代数学的一个重要分支，是计算机专业和软件工程专业的基础主干课程，是进一步学习后续课程以及进行研究和开发的基础。本书根据作者多年教学经验编写而成，着重讲解离散数学的基本概念、基本方法及其应用，给出了大量的典型例题和习题，以及若干综合专题、应用案例和实验项目。全书共10章，内容包括朴素集合论、数论基础、计数基础、命题逻辑、谓词逻辑、二元关系、函数、偏序关系与格、代数结构、图论与树、形式语言、自动机与正则表达式等。附录给出综合性研讨专题、综合实验、名词中英文对照表等。

【作者简介】

刘铎，1978年9月生，北京人，2006年于清华大学计算机科学与技术系获工学博士，现为北京交通大学软件学院副教授，校级很好主讲教师。主要研究方向为应用密码学、信息安全、组合算法的设计与分析。主持和参加重量、省部级科研项目多项，作为作者在各类重要刊物和会议上发表二十余篇，目前主要承担“离散数学”“算法设计与实践”“信息安全理论与实践”等课程的与建设，作为课题执行负责人完成了北京交通大学多项改革项目。获得多项类成果奖，主持建设的“离散数学”课程成为2014年北京交通大学优质课程建设项目、示范软件学院联盟批慕课课程建设项目等。

【目录】

  
章基础知识/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.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


0章形式语言、自动机与正则表达式/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.1ean-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.5chomp游戏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


附录eprolog语言与逻辑推理/473


e.1prolog基础473


e.2典型逻辑问题479


参文献/483