普通高校本科计算机专业特色教材.数理基础-离散数学

\\\"内容 第一部分数理逻辑部分，将选取生活中的逻辑案例和公务员考试题目为引入点，逐步分解数理逻辑中涉及到的命题、谓词、范式及推理理论。一方面可以弘扬优秀的中华传统文化，另一方面可以改变目前教材中的国外案例居多的状况。 拓展环节能够对所选案例进行理论推导、Python程序实现并形成最终报告。 第二部分集合论，通过学习集合论的经典知识，如关系的性质、集合之间的关系，以及无穷级数之间的比较等内容。使学生明白如何正确处理个人与集体、局部与整体之间利益的关系，从而树立正确的全局观。拓展部分主要涉及到对偏序关系深层次探究。 图论部分 从一带一路战略中的路网规划建设作为图论的切入点，解决生活中遇到的最短路径，平面图，四色原理等问题，将理论与实践相结合，每一类问题将会形成一个完整的理论+实践的解决方案。 第四部分对称是一种美，群论部分通过介绍中国在量子通信领域领先全球作为切入点，以增强学生的民族自信心，从同学熟知的整数集内的加法和除法谈起，进一步展开封闭性、幺元、独异点、阿贝尔群及同态/同构的学习和讨论， 拓展部分要求学生查阅相关文献资料，结合量子力学、量子通信与本部分的相关知识，形成完整学术调查报告。\\\"

王建芳,男，教授，硕士生导师，西北工业大学计算机科学与技术专业博士，爱尔兰利莫瑞克大学访学学者，校二级“元培名师”，河南理工大学“学生最喜爱的教师”。主要讲授本科课程《离散数学》、《数据结构》，研究生课程《算法设计与分析》。主要研究领域：人工智能，大数据分析及数据挖掘。目前研究方向：智能推荐系统、深度学习、知识图谱等。主持及参与国家、省部级及厅级项目12项，申请国家发明专利3项、新型实用专利1项，出版教材及专著4部。在国内外重要期刊及国际会议上发表学术论文30余篇（SCI/EI收录20余篇）。有6项科研成果通过省部级鉴定，主持及参与省级教研教改项目4项，获得厅级二等奖及以上奖励3项，获得计算机软件著作权20余项。

目录CONTENTS 第1部分数 理 逻 辑 第0章逻辑绪论40.1逻辑4 0.2形式逻辑5 0.3推理分类5 第1章命题8 1.1命题8 1.2命题的表示10 第2章联结词11 2.1否定11 2.2合取11 2.3析取12 2.4条件14 2.5双条件16 2.6小结16 2.7联结词的应用17 2.8布尔代数17 第3章命题合式公式及符号化20 3.1命题合式公式20 3.2命题符号化的方法20 习题22 第4章等价公式25 4.1真值表25 4.2等价公式27 4.2.1等价27 4.2.2从真值表到等价式27 4.2.3等价公式27 4.3等价公式的应用28 4.3.1证明28 4.3.2化简29 4.3.3综合应用29 4.4公式类型30 4.5逻辑三大定律30 习题32 第5章范式34 5.1范式35 5.1.1基本概念35 5.1.2范式35 5.1.3性质36 5.1.4求范式的基本步骤36 5.1.5范式的应用37 5.2主范式38 5.2.1主析取范式38 5.2.2主析取范式的求法39 5.2.3主合取范式40 5.2.4主合取范式的求法42 5.3主析取范式与主合取范式的关系43 习题45 第6章主范式的应用46 6.1赋值46 6.2判断公式的类型47 6.3判断公式是否等价47 6.4实际应用48 习题51 第7章蕴含54 7.1重言式54 7.2蕴含式55 7.2.1蕴含55 7.2.2蕴含式的证明55 7.2.3常见的蕴含式56 7.3应用56 习题57 第8章命题逻辑推理58 8.1推理及分类58 8.2直接推理58 8.3条件论证60 8.4反证法61 8.5应用63 习题64 第9章谓词68 9.1谓词68 9.2谓词的表示68 9.3命题函数69 9.4量词70 习题70 第10章谓词公式及符号化72 10.1谓词合式公式72 10.2特性谓词73 10.3谓词符号化75 习题77 第11章谓词等价式与蕴含式78 11.1公式的分类78 11.2公式的等价79 11.3等价式和蕴含式79 11.4谓词公式赋值84 习题85 第12章前束范式87 12.1量词辖域87 12.2约束变元的改名89 12.3自由变元的代入89 12.4前束范式90 12.5前束析(合)取范式91 习题92 第13章谓词推理93 13.1推理规则94 13.2直接推理95 13.3条件论证96 13.4反证法97 13.5三段论98 13.5.1基本概念98 13.5.2三段论规则98 习题101 第14章综合应用——动物识别103 第2部分集合论 第15章集合10915.1基本概念109 15.2集合的性质110 15.3集合的运算110 习题111 第16章序偶与笛卡儿积113 16.1序偶113 16.2笛卡儿积114 16.2.1笛卡儿积的定义114 16.2.2笛卡儿积的性质116 16.2.3笛卡儿积的应用117 习题118 第17章二元关系及其表示119 17.1关系的表示120 17.2特殊关系121 习题122 第18章关系的性质123 18.1自反性124 18.2反自反性124 18.3对称性125 18.4反对称性125 18.5传递性126 习题128 第19章关系的运算131 19.1基本概念131 19.2复合运算132 19.2.1计算方法133 19.2.2性质134 19.3逆运算135 19.4幂运算136 习题136 第20章关系闭包138 20.1定义139 20.2自反闭包139 20.3对称闭包139 20.4传递闭包139 20.5传递闭包的求法140 20.5.1定义法140 20.5.2有向图法140 20.5.3Warshall算法141 习题146 第21章等价关系148 21.1等价关系148 21.2等价类149 21.3商集150 习题150 第22章相容关系153 22.1相容关系153 22.2简化图和简化矩阵154 22.3相容类及最大相容类155 22.4覆盖与划分155 22.5完全覆盖156 习题156 第23章偏序关系157 23.1偏序157 23.2哈斯图158 23.3重要元素160 23.3.1极小元与极大元160 23.3.2最小元与最大元161 23.3.3上界与下界161 23.3.4上确界与下确界162 习题162 第24章综合应用——家族族谱管理系统165 第25章函数168 25.1基本概念169 25.2函数的映射171 25.3复合函数173 25.4逆函数174 25.5函数运算的应用176 习题177 第26章康托尔定理179 26.1基数179 26.1.1集合的势180 26.1.2有限集与无限集182 26.1.3集合的基数183 26.2可数集与不可数集185 26.3康托尔定理186 26.4ZFC公理188 26.4.1康托尔悖论188 26.4.2罗素悖论188 26.4.3ZFC公理体系189 26.4.4三次数学危机190 习题190 第3部分代 数 系 统 第27章代数系统19527.1基本概念195 27.2运算符与运算表196 27.3特殊运算197 27.3.1模k加法197 27.3.2模k乘法197 习题198 第28章运算及性质202 28.1运算性质203 28.2特殊元素204 习题207 第29章群209 29.1群的定义210 29.2子群212 29.3阿贝尔群与循环群213 29.4拉格朗日定理215 29.4.1陪集215 29.4.2拉格朗日定理216 29.5置换群218 29.6群与对称性220 29.6.1对称221 29.6.2对称的数学表示223 习题225 第30章同态与同构228 习题230 第31章环与域232 31.1基本概念232 31.2环在密码学中的应用234 习题234 第32章格238 32.1格的概念238 32.2格的对偶原理240 32.3格的性质240 32.4格的同态与同构243 32.5子格245 第33章分配格247 33.1分配格247 33.2模格249 第34章有补格251 34.1有界格251 34.2有补格252 第35章布尔代数253 35.1布尔代数253 35.2布尔表达式254 35.3布尔表达式的范式256 习题258 第4部分图论 第36章基本概念26636.1图的基本概念266 36.2通路与回路271 36.3图的连通性272 习题274 第37章图的矩阵存储275 37.1关联矩阵275 37.2邻接矩阵276 37.3可达矩阵277 习题278 第38章欧拉图280 38.1无向欧拉图281 38.2一笔画284 38.3有向欧拉图286 习题287 第39章哈密顿图289 39.1基本概念290 39.2判断方法290 39.3旅行商问题292 习题293 第40章二分图294 40.1基本概念294 40.2匈牙利算法295 40.3推荐系统297 40.3.1基于用户的协同过滤算法298 40.3.2基于项目的协同过滤算法300 习题305 第41章平面图及着色306 41.1平面图306 41.2对偶图310 41.3图的着色311 习题313 第42章最小生成树314 42.1基本概念314 42.2Kruskal算法315 42.3Prim算法319 习题322 第43章最短路径323 43.1基本概念323 43.2Dijkstra算法324 43.3FloydWarshall算法330 43.3.1传递闭包Warshall算法331 43.3.2FloydWarshall算法331 43.4FloydWarshall算法与Dijkstra算法比较332 习题333 参考文献334