离散数学及编程实践(计算机科学与技术面向新工科专业建设计算机系列教材)

本书阐述了离散数学中 基本而重要的理论，让读者 方便、快捷、系统地掌握“ 离散数学”课程的核心、精 髓及程序代码背后的算法原 理；同时，本书采用问题驱 动或案例式的编写方式，利 用C或C++程序设计语言， 编写出详细的程序代码，将 “离散数学”中的抽象知识具 体化、实战化、趣味化。 本书可作为高等学校相 关专业课程的教材或辅导用 书，也可作为相关科技工作 者的参考用书。

第1章 数理逻辑理论 1.1 命题逻辑的基本概念 1.1.1 命题及联结词 1.1.2 命题公式与解释 1.2 命题公式的等值演算及其范式 1.2.1 命题公式等值的概念及基本等值式 1.2.2 简单析取式与简单合取式 1.2.3 析取范式与合取范式 1.2.4 主析取范式和主合取范式 1.3 命题逻辑的推理理论 1.3.1 基于等值演算的命题逻辑推理 1.3.2 基于推理规则的命题逻辑推理 1.4 一阶逻辑的基本概念 1.4.1 个体词、量词和谓词 1.4.2 一阶逻辑公式及解释 1.5 一阶逻辑的等值演算 1.5.1 一阶逻辑的等值概念及基本等值式 1.5.2 一阶逻辑的前束范式 1.6 一阶逻辑的推理与应用 1.6.1 一阶逻辑的自然演绎推理 1.6.2 一阶逻辑的归结反演推理 习题 第2章 数理逻辑程序实践 实验1 命题逻辑联结词 实验2 公式合法性判断 实验3 命题公式真值表生成 实验4 基于真值表的主析取(合取)范式获取 实验5 命题逻辑推理——电路开关表决离散数学及编程实践 实验6 命题逻辑推理——谁是作案者 实验7 命题逻辑推理——某件事是谁干的 实验8 命题逻辑推理——王教授是哪里人 实验9 命题逻辑推理——班委会选举 实验10 命题逻辑推理——谁在说谎 实验11 基于一阶逻辑的自然演绎推理 实验12 基于一阶逻辑的归结反演推理 第3章 集合、二元关系与函数 3.1 集合的基本概念 3.2 并查集 3.3 关系的定义与表示 3.3.1 序偶、笛卡儿积的概念 3.3.2 二元关系的定义 3.3.3 二元关系的表示 3.4 关系的运算 3.5 关系的性质 3.6 关系的闭包 3.7 关系的应用 3.8 相容关系 3.9 等价关系 3.9.1 等价关系的定义 3.9.2 等价关系的应用 3.10 偏序关系 3.10.1 偏序关系的定义 3.10.2 偏序关系的哈斯图 3.10.3 偏序集中的特殊元素 3.10.4 偏序关系图在课程设置中的应用 3.11 格的概念 3.12 特殊的二元关系——函数 3.12.1 函数的概念与分类 3.12.2 函数应用——哈希函数 3.13 计数问题 3.13.1 包含排斥原理 3.13.2 鸽笼原理 3.13.3 排列与组合 3.13.4 二项式定理 3.13.5 母函数及其应用 习题 第4章 集合、二元关系与函数程序实践 实验1 集合运算 实验2 元素归属合并——并查集算法 实验3 笛卡儿积及关系的复合 实验4 二元关系及其性质 实验5 二元关系的闭包运算 实验6 等价关系判定 实验7 偏序关系上的特异元素 实验8 求函数的定义域和值域 实验9 函数中单射、满射、双射判断 实验10 集合计数——容斥原理 实验11 组合计数 实验12 排列计数 实验13 母函数组合计数 实验14 指母函数排列计数 第5章 代数系统与数论 5.1 代数系统的概念 5.2 代数系统的运算及其性质 5.3 半群与含么半群 5.4 群与子群 5.5 交换群与循环群 5.6 陪集与拉格朗日定理 5.7 数论基础知识 5.7.1 素数 5.7.2 辗转相除法 5.7.3 同余及同余方程 5.7.4 欧拉函数及欧拉定理 5.7.5 中国剩余定理 5.8 数论与密码学 习题 第6章 代数系统与数论程序实践 实验1 判断二元运算是否满足结合律 实验2 判断代数系统是否为群 实验3 判断整数能否被给定数整除 实验4 利用埃氏筛选法筛选素数 实验5 求一个数的所有因子及因子数目 实验6 算术基本定理——正整数唯一分解定理 实验7 利用辗转相除法求两个数的最大公约数和最小公倍数 实验8 线性同余方程求解 实验9 利用中国剩余定理求解线性同余方程组 实验10 利用中国剩余定理加快RSA加密解密 第7章 图论理论 7.1 图的基本概念 7.2 通路、回路、图的连通性 7.3 点割集、割点、边割集、桥 7.4 图的矩阵表示 7.4.1 关联矩阵 7.4.2 邻接矩阵 7.4.3 可达矩阵 7.5 最短路径和关键路径 7.5.1 迪杰斯特拉算法 7.5.2 弗洛伊德算法 7.6 最小生成树及其求法 7.6.1 最小生成树定义 7.6.2 普里姆算法 7.6.3 克鲁斯卡尔算法 7.7 二叉树及哈夫曼编码 7.7.1 二叉树的定义及性质 7.7.2 哈夫曼树的概念及构造 7.7.3 哈夫曼编码 7.8 欧拉图与哈密顿图 7.8.1 欧拉图 7.8.2 哈密顿图 7.9 着色及其应用 7.10 匹配及其应用 习题 第8章 图论程序实践 实验1 图的度和可达矩阵计算以及连通性判断 实验2 求图的所有割点 实验3 求图的所有割边 实验4 可图化、可简单图化、连通图和欧拉图的判断 实验5 哈密顿图的判断 实验6 图中两个顶点间通路数计算 实验7 利用迪杰斯特拉算法求最短路径 实验8 利用弗洛伊德算法求最短路