本书共8章,以数理逻辑为基础,介绍命题逻辑、谓词逻辑、集合论基础、关系、函数、运算与代数系统、图和初等数论基础的相关内容,配套微课视频、电子课件、知识导图、部分习题解答等。本书内容不求大求全,根据工程教育的要求,着重介绍有应用价值的理论,避免理论上的缠绕,内容讲解通俗明了,同时还增加了相当数量的工程应用方面的简介,使学习者能够快速了解这些理论的实际工程用途。 本书可作为高等学校计算机科学与技术、软件工程、信息与计算科学以及其他信息领域相关专业离散数学课程的教材,也可供相关领域读者自学使用。

目 录 第1章 命题逻辑1 1.1 命题1 思考与练习1.13 1.2 逻辑联结词3 1.2.1 基本联结词3 1.2.2 其他联结词6 思考与练习1.26 1.3 命题公式与真值表7 1.3.1 命题公式7 1.3.2 真值表8 思考与练习1.38 1.4 命题翻译9 1.4.1 命题的合取9 1.4.2 命题的析取9 1.4.3 条件句复合命题10 1.4.4 多联结词构成的复合命题11 思考与练习1.412 1.5 命题公式的分类与逻辑等价13 1.5.1 命题公式的分类13 1.5.2 命题公式等价14 1.5.3 联结词的功能完备集16 1.5.4 对偶原理17 思考与练习1.518 1.6 范式18 1.6.1 简单的范式18 1.6.2 小项与大项19 1.6.3 主析取范式与主合取范式20 思考与练习1.623 1.7 推 理 理 论24 1.7.1 蕴含与论证24 1.7.2 自然推理系统26 思考与练习1.733 第2章 谓词逻辑34 2.1 谓词、个体词与量词34 2.1.1 个体词和谓词34 2.1.2 量词与量化36 思考与练习2.137 2.2 谓词逻辑的命题翻译38 2.2.1 特殊化个体词的命题38 2.2.2 量词量化的命题38 思考与练习2.241 2.3 量词约束与谓词公式的解释42 2.3.1 量词对个体词变元的作用42 2.3.2 谓词公式的解释与求值42 2.3.3 量词与联结词的搭配44 ���考与练习2.344 2.4 谓词公式的等价和蕴含45 2.4.1 基本等价与蕴含关系45 2.4.2 利用等价关系计算前束范式48 思考与练习2.449 2.5 谓词逻辑的推理理论50 2.5.1 推理定律50 2.5.2 量词的消除与产生规则50 2.5.3 谓词逻辑的自然推理示例52 思考与练习2.555 2.6 *数学证明初步56 2.6.1 数学论题的描述56 2.6.2 证明方法56 2.6.3 证明策略58 思考与练习2.659 第3章 集合论基础61 3.1 集合的概念和表示方法61 3.1.1 集合描述61 3.1.2 集合的包含与相等62 3.1.3 空集和全集63 3.1.4 集合的幂集65 思考与练习3.166 3.2 集合运算66 3.2.1 基本运算66 3.2.2 多集合的交与并68 思考与练习3.270 3.3 集合运算的性质71 3.3.1 集合算律与恒等变换71 3.3.2 基于定义的运算性质验证72 思考与练习3.374 3.4 集合划分和计数74 3.4.1 集合的划分与覆盖75 3.4.2 *集合计数的容斥原理76 思考与练习3.477 3.5 序偶与笛卡儿积78 3.5.1 序偶和元组78 3.5.2 笛卡儿积79 思考与练习3.581 第4章 关系82 4.1 二元关系的含义与表示82 4.1.1 二元关系82 4.1.2 关系的矩阵和图表示法84 思考与练习4.185 4.2 关系运算86 4.2.1 关系的逆与复合86 4.2.2 关系运算的性质87 4.2.3 关系运算的图和矩阵实现88 4.2.4 关系的幂90 思考与练习4.292 4.3 关系的性质93 4.3.1 自反与反自反关系93 4.3.2 对称与反对称关系94 4.3.3 传递关系95 4.3.4 关系性质的等价描述与判定95 思考与练习4.397 4.4 关系的闭包98 4.4.1 闭包的概念98 4.4.2 闭包计算99 思考与练习4.4102 4.5 等价关系102 4.5.1 等价与相容102 4.5.2 等价类103 4.5.3 划分与等价关系的对应104 思考与练习4.5106 4.6 序关系107 4.6.1 体现部分序的偏序关系107 4.6.2 哈斯图108 4.6.3 链与全序关系109 4.6.4 偏序集的特殊元素111 思考与练习4.6112 第5章 函数114 5.1 从关系到函数114 5.1.1 函数的概念114 5.1.2 函数集115 5.1.3 函数的性质与特殊函数116 思考与练习5.1118 5.2 函数的逆与复合119 5.2.1 双射的反函数119 5.2.2 函数复合119 5.2.3 函数运算的性质121 思考与练习5.2122 5.3 集合的基数122 5.3.1 集合等势122 5.3.2 有限集与无限集123 5.3.3 可数集与不可数集123 5.3.4 基数比较125 思考与练习5.3126 第6章 运算与代数系统127 6.1 运算及其性质127 6.1.1 运算的概念127 6.1.2 二元运算的性质128 思考与练习6.1129 6.2 二元运算中的特殊元素130 6.2.1 幺元130 6.2.2 零元131 6.2.3 逆元132 思考与练习6.2133 6.3 代数系统133 6.3.1 代数与子代数133 6.3.2 同态与同构134 思考与练习6.3135 6.4 半群与独异点136 思考与练习6.4137 6.5 群与子群138 6.5.1 群的概念138 6.5.2 群的性质139 6.5.3 子群140 思考与练习6.5141 6.6 循环群与置换群142 6.6.1 循环群142 6.6.2 置换群143 思考与练习6.6145 6.7 群的陪集分解145 6.7.1 陪集146 6.7.2 拉格朗日定理147 思考与练习6.7148 6.8 环和域148 6.8.1 环与整环148 6.8.2 域150 思考与练习6.8150 6.9 格151 6.9.1 格与其诱导的代数系统151 6.9.2 子格153 6.9.3 几种特殊格153 思考与练习6.9155 6.10 布尔代数156 6.10.1 布尔代数的定义156 6.10.2 二值布尔代数157 思考与练习6.10159 第7章 图160 7.1 图的基本概念160 7.1.1 图及其组成160 7.1.2 结点的度与握手定理161 7.1.3 完全图与正则图163 7.1.4 子图、补图与图同构163 思考与练习7.1165 7.2 图的连通性165 7.2.1 路与回路165 7.2.2 无向图的连通性166 7.2.3 有向图的连通性167 思考与练习7.2168 7.3 图的矩阵表示168 7.3.1 邻接矩阵168 7.3.2 关联矩阵170 思考与练习7.3170 7.4 几种特殊的图171 7.4.1 二部图171 7.4.2 欧拉图173 7.4.3 汉密尔顿图175 思考与练习7.4176 7.5 平面图177 7.5.1 平面图与欧拉定理177 7.5.2 平面图着色179 思考与练习7.5180 7.6 树180 7.6.1 无向树180 7.6.2 生成树182 7.6.3 *单源*短路径184 7.6.4 根树186 思考与练习7.6189 第8章 初等数论基础190 8.1 整数除法与素数190 8.1.1 整数除法与整除190 8.1.2 素数与合数191 8.1.3 *大公约数与*小公倍数193 思考与练习8.1196 8.2 同余与同余方程196 8.2.1 模算术与同余196 8.2.2 一次同余方程及方程组198 思考与练习8.2200 8.3 费马小定理与欧拉定理201 8.3.1 费马小定理201 8.3.2 *欧拉函数与欧拉定理202 8.3.3 *RSA密码系统原理202 思考与练习8.3204 附录 符号索引205 参考文献207