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

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

第一部分  数理逻辑<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 />