离散数学

前言第一篇 数理逻辑第1章 命题逻辑 1.1 命题与联结词 1.1.1 命题及其表示 1.1.2 联结词 1.2 命题公式与翻译 1.2.1 命题公式 1.2.2 命题的翻译 1.3 真值表与等价公式 1.3.1 真值表 1.3.2 公式分类 1.3.3 等价公式 1.3.4 代入规则和替换规则 1.4 对偶原理与蕴含式

前言第一篇 数理逻辑第1章 命题逻辑 1.1 命题与联结词 1.1.1 命题及其表示 1.1.2 联结词 1.2 命题公式与翻译 1.2.1 命题公式 1.2.2 命题的翻译 1.3 真值表与等价公式 1.3.1 真值表 1.3.2 公式分类 1.3.3 等价公式 1.3.4 代入规则和替换规则 1.4 对偶原理与蕴含式 1.4.1 对偶原理 1.4.2 蕴含式 1.5 联结词的扩充与功能完全组 1.5.1 其他联结词 1.5.2 联结词的功能完全组 1.6 范式 1.6.1 析取范式与合取范式 1.6.2 主析取范式与主合取范式 1.7 命题逻辑的推理理论 1.7.1 推理的基本概念 1.7.2 推理常用方法 习题一第2章 谓词逻辑 2.1 谓词逻辑的基本概念 2.1.1 个体、谓词和命题的谓词形式 2.1.2 原子谓词 2.1.3 量词 2.2 谓词公式与翻译 2.2.1 谓词公式 2.2.2 谓词逻辑的翻译 2.3 变元的约束 2.4 谓词演算的等价式与蕴含式 2.5 谓词公式范式 2.5.1 前束范式 2.5.2 斯柯伦范式 2.6 谓词演算的推理理论 2.6.1 有关量词的规则 2.6.2 谓词逻辑推理实例 习题二第二篇 集合论第3章 集合与关系 3.1 集合的基本概念 3.2 集合的运算与性质 3.2.1 集合的运算 3.2.2 集合的运算与性质 3.3 序偶与笛卡尔积 3.3.1 序偶及序偶的推广 3.3.2 笛卡尔积 3.4 关系及其表示方法 3.4.1 关系 3.4.2 几种特殊的关系 3.4.3 关系的表示方法 3.5 关系的性质 3.5.1 关系的五种特殊性质 3.5.2 关系图、关系矩阵与关系的性质 3.6 关系的运算 3.6.1 关系的集合运算 3.6.2 复合关系 3.6.3 逆关系 3.6.4 闭包运算 3.7 集合的划分和覆盖 3.8 等价关系 3.8.1 等价关系的定义 3.8.2 等价类及其性质 3.8.3 等价关系与划分的一一对应 3.9 相容关系 3.10 偏序关系 3.10.1 偏序关系的定义 3.10.2 偏序关系的哈斯图 3.10.3 偏序集中特殊位置的元素 习题三第4章 函数 4.1 函数的概念 4.1.1 函数的定义 4.1.2 函数的相等 4.1.3 特殊的函数 4.2 函数的运算 4.2.1 复合函数 4.2.2 逆函数 习题四第三篇 代数系统第5章 代数系统 5.1 代数系统的基本概念 5.2 运算及其性质 5.3 同态与同构 5.4 同余关系 习题五第6章 典型代数系统 6.1 半群与群 6.1.1 半群与独异点 6.1.2 群的定义与性质 6.1.3 阿贝尔群、置换群与循环群 6.1.4 子群、陪集与拉格朗日定理 6.1.5 群同态与群同构 6.2 环与域 6.2.1 环 6.2.2 域 6.3 格与布尔代数 6.3.1 辛各 6.3.2 布尔代数 习题六第四篇 图论第7章 图论基础 7.1 图的基本概念 7.2 路与回路 7.3 图的矩阵表示 习题七第8章 几类典型的图 8.1 欧拉图与哈密尔顿图 8.1.1 欧拉图 8.1.2 哈密尔顿图 8.2 二部图和平面图 8.2.1 二部图 8.2.2 平面图 8.3 树 8.3.1 树与生成树 8.3.2 根树及其应用 习题八第五篇 组合学第9章 基本计数原理 9.1 排列与组合 9.1.1 加法原理与乘法原理 9.1.2 集合的排列和组合 9.1.3 重集的排列和组合 9.2 容斥原理 9.2.1 容斥原理 9.2.2 容斥原理的应用 9.3 鸽巢原理 9.4 二项式定理和二项式系数 9.4.1 二项式定理 9.4.2 Pascal三角形和组合等式 9.4.3 二项式系数的推广和Newton二项式定理 9.5 集合的分划与第二类Stirling数 9.6 正整数的分拆 9.7 分配问题 习题九第10章 生成函数、递推关系与Polya计数 10.1 生成函数 10.1.1 离散数值函数 10.1.2 生成函数及其性质 10.1.3 用生成函数法解组合问题 10.1.4 指数型生成函数 10.2 递推关系 10.2.1 两个递推关系的实例 10.2.2 递推关系和常系数线性递推关系 10.2.3 利用特征方程求解常系数线性递推关系 10.2.4 利用生成函数法求解常系数线性递推关系 10.3 Polya计数 10.3.1 引论 10.3.2 计数问题的数学模型 10.3.3 Burnside引理 10.3.4 映射的等价类 10.3.5 Polya计数定理 习题十参考文献

本书为普通高等教育“十一五”规划教材。 全书共分为五篇，主要内容包括命题逻辑和谓词逻辑的基本概念和推理理论：集合的基本知识、关系和函数；半群与群、环与域、格与布尔代数等代数系统的基本概念与性质；欧拉图、哈密尔顿图、二部图、平面图及树的基本概念和表示；基本计数原理、容斥原理、鸽巢原理、二项式定理、生成函数、递推关系和Polya计数定理。 本书知识面广，内容深入浅出、文字浅显易懂，适合作为高等院校计算机科学技术等相关专业的本科生和研究生的教学用书，也可供计算机工程技术和研究人员学习离散数学的参考用书。

本书是“普通高等教育十一五规划教材”之一，全书共分10个章节，主要对离散数学的基础知识作了介绍，具体内容包括命题逻辑、谓词逻辑、集合与关系、函数、典型代数系统等。该书可供各大专院校作为教材使用，也可供从事相关工作的人员作为参考用书使用。