离散数学及其应用

本书根据计算机科学与技术专业对离散数学的教学要求，参考国内外众多优秀的离散数学教材，并结合教学组老师多年的教学实践编写而成。本书对离散数学的核心知识单元进行了系统的理论阐述，对离散数学的分析证明方法进行了严谨的介绍，并通过丰富的应用实例介绍了离散系统建模，旨在帮助读者在掌握理论基础的同时，理解如何利用这些理论知识来分析和解决问题。作为《离散数学及其应用》的第!版，本书将函数的相关内容列为独立章节，进行了更详尽的阐述；图论部分增加了握手定理、独立集、覆盖和支配集，以及网络与网络流、基本割集和基本回路的相关内容。此外，本书根据用书学校的反馈对其他章节进行了更新和完善，使其更符合教学要求。本书每部分均配有大量典型例题和难易程度不同的习题，紧密结合实际应用，使学生能够将对离散数学课程的认识由抽象、枯燥转变为易学、有趣。

陈琼，华南理工大学计算机科学与工程学院副教授，主讲本科“数字电路”“离散数学”“人工智能”“机器学习”课程、硕士研究生“人工智能”课程。研究领域为机器学习算法和应用、数据挖掘、计算机图像识别等。中国计算机学会会员、中国人工智能学会离散智能计算专委会委员。<br /><br /> 马千里，华南理工大学计算机科学与工程学院教授，博士生导师，美国加州大学（圣地亚哥分校）访问学者，中国计算机学会（CCF）高级会员。主要研究领域为人工智能、机器学习、数据挖掘、时序数据分析、自然语言处理等。曾获广东省科技进步奖二等奖、中国南方电网科技进步二等奖、华南理工大学教学优秀奖一等奖。<br /><br /> 陈伟能，华南理工大学计算机科学与工程学院教授，博士生导师、副院长。主要研究方向为群体智能、演化计算及其应用。现任大数据与计算智能粤港联合创新平台负责人、IEEE广州分会副主席，中国计算机学会人工智能与模式识别专业委员会委员，中国计算机学会协同计算专业委员会委员，国际期刊IEEE Trans. on Neural Network & Learning Systems及Complex and Intelligent Systems副编辑。<br />周育人，中山大学软件工程学院教授。1988年在北京大学获理学学士学位，2003年在武汉大学获工学博士学位。主要从事算法分析与设计、演化计算等方面的研究。

第一部分　数理逻辑<br />第1章　命题逻辑2<br />　1.1　命题与联结词2<br />　　1.1.1　命题的概念2<br />　　1.1.2　联结词3<br />　1.2　命题公式及其分类8<br />　1.3　命题演算的关系式10<br />　　1.3.1　等价关系式10<br />　　1.3.2　全功能联结词集13<br />　　1.3.3　对偶式14<br />　1.4　范式15<br />　　1.4.1　析取范式和合取范式15<br />　　1.4.2　主析取范式和主合取范式16<br />　1.5　命题逻辑的推理21<br />　　1.5.1　推理理论21<br />　　1.5.2　推理证明方法22<br />　习题26<br />第2章　谓词逻辑30<br />　2.1　谓词逻辑的基本概念30<br />　　2.1.1　个体词和谓词30<br />　　2.1.2　量词32<br />　2.2　谓词合式公式36<br />　2.3　谓词公式的解释和分类37<br />　　2.3.1　谓词公式的解释37<br />　　2.3.2　谓词公式的分类38<br />　2.4　谓词演算的关系式39<br />　2.5　前束范式43<br />　2.6　谓词逻辑的推理44<br />　　2.6.1　推理理论44<br />　　2.6.2　推理问题的证明45<br />　2.7　谓词逻辑的应用48<br />　习题50<br />第二部分　集合、关系和函数<br />第3章　集合56<br />　3.1　集合及其表示56<br />　3.2　集合间的关系57<br />　3.3　集合的运算60<br />　3.4　自然数65<br />　3.5　集合的特征函数66<br />　习题67<br />第4章　关系70<br />　4.1　关系概述70<br />　　4.1.1　有序对和有序n元组70<br />　　4.1.2　笛卡儿积70<br />　　4.1.3　关系的概念72<br />　4.2　关系的表示法74<br />　　4.2.1　用集合表示关系74<br />　　4.2.2　用关系图表示关系75<br />　　4.2.3　用矩阵表示关系76<br />　4.3　关系的运算76<br />　　4.3.1　关系的逆运算77<br />　　4.3.2　关系的复合运算78<br />　4.4　关系的性质82<br />　4.5　关系的闭包88<br />　4.6　等价关系和等价类94<br />　　4.6.1　等价关系94<br />　　4.6.2　等价类95<br />　4.7　偏序关系100<br />　习题105<br />第5章　函数109<br />　5.1　函数的定义109<br />　5.2　特殊函数110<br />　5.3　复合函数111<br />　5.4　反函数113<br />　5.5　集合的基数114<br />　习题118<br />第三部分　组合数学<br />第6章　计数122<br />　6.1　基本计数规则122<br />　　6.1.1　加法法则122<br />　　6.1.2　乘法法则122<br />　6.2　排列与组合124<br />　　6.2.1　排列125<br />　　6.2.2　组合125<br />　　6.2.3　多重集的排列与组合127<br />　　6.2.4　二项式定理129<br />　6.3　容斥原理131<br />　6.4　鸽巢原理136<br />　习题137<br />第7章　高级计数技术139<br />　7.1　递推方程139<br />　　7.1.1　求解递推方程141<br />　　7.1.2　常系数线性齐次递推方程的<br />求解141<br />　　7.1.3　常系数线性非齐次递推方程<br />的求解144<br />　7.2　生成函数147<br />　　7.2.1　牛顿二项式系数与牛顿<br />二项式定理147<br />　　7.2.2　生成函数的定义及其<br />性质149<br />　　7.2.3　生成函数的应用150<br />　　7.2.4　指数型生成函数153<br />　习题155<br />第四部分　图论<br />第8章　图158<br />　8.1　图的基本概念158<br />　　8.1.1　无向图和有向图159<br />　　8.1.2　度的概念160<br />　　8.1.3　握手定理160<br />　　8.1.4　图的分类162<br />　　8.1.5　子图与补图165<br />　　8.1.6　图的同构168<br />　8.2　通路与回路、连通的概念169<br />　　8.2.1　通路与回路169<br />　　8.2.2　连通的概念172<br />　8.3　图的表示175<br />　　8.3.1　邻接表175<br />　　8.3.2　邻接矩阵176<br />　　8.3.3　可达矩阵180<br />　　8.3.4　关联矩阵181<br />　8.4　独立集、覆盖和支配集183<br />　习题186<br />第9章　特殊图189<br />　9.1　欧拉图与哈密顿图189<br />　　9.1.1　欧拉图189<br />　　9.1.2　哈密顿图192<br />　9.2　带权图196<br />　　9.2.1　旅行商问题196<br />　　9.2.2　最短路径问题196<br />　　9.2.3　中国邮路问题198<br />　　9.2.4　关键路径200<br />　　9.2.5　网络与网络流202<br />　9.3　匹配和二分图208<br />　　9.3.1　匹配208<br />　　9.3.2　二分图209<br />　　9.3.3　网络流的应用213<br />　9.4　平面图214<br />　　9.4.1　平面图的定义214<br />　　9.4.2　平面图的欧拉公式216<br />　　9.4.3　对偶图与图着色218<br />　习题222<br />第10章　树227<br />　10.1　树的定义和特性227<br />　10.2　生成树229<br />　　10.2.1　生成树的定义229<br />　　10.2.2　基本割集和基本回路231<br />　　10.2.3　最小生成树及其应用232<br />　10.3　根树233<br />　　10.3.1　有向根树和有序根树233<br />　　10.3.2　有序根树的遍历236<br />　10.4　根树的应用238<br />　　10.4.1　前缀码238<br />　　10.4.2　最优二元树和Huffman<br />编码239<br />　　10.4.3　决策树241<br />　习题242<br />第五部分　代数结构<br />第11章　代数系统246<br />　11.1　代数系统的概念和性质246<br />　　11.1.1　二元运算及其性质246<br />　　11.1.2　代数系统和子代数249<br />　　11.1.3　代数系统的性质250<br />　　11.1.4　代数系统的分类252<br />　11.2　代数系统的同态和同构253<br />　11.3　半群255<br />　11.4　群257<br />　　11.4.1　群及其基本性质257<br />　　11.4.2　子群260<br />　11.5　循环群和置换群261<br />　　11.5.1　循环群261<br />　　11.5.2　置换群263<br />　11.6　环和域264<br />　习题266<br />第12章　格与布尔代数269<br />　12.1　格269<br />　　12.1.1　格的基本概念269<br />　　12.1.2　分配格272<br />　　12.1.3　有界格和有补格274<br />　12.2　布尔代数275<br />　　12.2.1　布尔代数的基本概念275<br />　　12.2.2　布尔表达式与布尔<br />函数277<br />　　12.2.3　布尔代数和数字电路279<br />　习题280<br />参考文献283<br />