离散数学结构习题与解答 (2010 年度畅销榜NO.54785 )

本书是作者编写的《离散数学结构》一书的习题与解答，对离散数学涉及的各部分内容，从集合、序列、整数除法、矩阵、关系、函数等基础知识到数学结构、图论、群、语言和有限状态机等高级内容，都提供了相应的丰富习题及解答，使读者在学习理论知识的基础上，通过知识的实际运用进一步将其消化、理解，融会贯通，从而在需要时可熟练应用数学知识来解决计算机领域内的实际问题。
本书既可与《离散数学结构》一书配套使用，也可作为独立的习题集使用。

第1章基础知识
练习1.1集合与子集
练习1.2序列
练习1.3整数的除法
练习1.4矩阵
练习1.5数学结构
自测题1
第2章逻辑
练习2.1命题和逻辑运算
练习2.2条件命题
练习2.3证明方法
练习2.4数学归纳法
自狈g题2
第3章计数
练习3.1叠力D原理
练习3.2排列
练习3.3组合
练习3.4鸽巢原理
练习3.5概率基础
练习3.6递归关系
自测题3
第4章关系
练习4.1乘积集合
练习4.2关系和有向图.
练习4.3关系和有向图中的路径
练习4.4关系的性质
练习4.5等价关系
练习4.6关系的计算机表示
练习4.7关系的运算
练习4.8闭包
自测题4
第5章函数
练习5.1函数
练习5.2计算机科学中的函数
练习5.3函数的增长
练习5.4排列函数
自测题5
第.6章序关系和结构
练习6.1偏序集合
练习6.2偏序集合的极值元素
练习6.3格
练习6.4有限布尔代数
练习6.5布尔代数上的函数
练习6.6电路设计
自测题6
第7章树
练习7.1树
练习7.2标记树
练习7.3树搜索
练习7.4无向树
练习7.5最小生成树
自测题7
第8章图论
练习8.1图
练习8.2欧拉路径和回路
练习8.3哈密尔顿路径及回路
练习8.4运输网
练习8.5图着色
自测题8
第9章半群和群
练习9.1二元运算回顾
练习9.2半群
练习9.3半群的积和商
练习9.4群
练习9.5群的积和商
自测题9
第10章语言和有限状态机
练习10.1语言
练习10.2语法和语言的表示
练习10.3有限状态机
练习10.4半群、机器和语言
练习10.5机器和正则语言
练习10.6机器简化
自测题10
第11章群和编码
练习11.1二进制编码和错误检测
练习11.2解码和纠错
自测题11

2002年，中国计算机学会、全国高校计算机教育研究会、清华大学出版社共同组织专家和教授，提出了《中国计算机科学与技术学科教程2002》。该教程主要参考了IEEE和ACM推出的“ComputingCurricula 2001”，提出了计算机学科的教学计划，包括课程设置、课程结构、课时内容、实验学时等内容。该教程把数学方法作为计算机学科的学科方法之一，要求用数学语言表示事物的状态、关系和过程，建立抽象而严谨的数学模型，通过推导进行解释和判断。 计算机学科的基础理论主要包括数学分析、高等代数、数值分析、概率与统计、集合与图论、近世代数、数理逻辑、形式语言与自动机、数学建模等。这些基础理论可以分为三部分：连续数学、离散数学、计算模型。连续数学部分的代表是数学分析，加之高等代数、概率与统计，这些都是公共基础理论，是所有理工学科的公共基础课。连续数学为物理学等众多学科提供了建模的数学工具，但是不能直接用于建模计算机内部的数据、功能和过程。计算模型部分包括数值分析和数学建模。它将连续数学模型与计算数学模型联系起来，为用计算机解决实际问题建起了桥梁。离散数学部分提供了在计算机内部建立数学模型的数学工具，包括集合论与图论、近世代数、数理逻辑、形式语言与自动机等分支。 由此可见，离散数学在计算机学科基础理论中占有重要地位。它的特点之一是实用性。离散数学是一门数学，但是作为计算机学科的一门基础课程，目的十分明确，就是应用于计算机领域。不仅用于计算机内部的数据，还用于算法和过程，用于系统结构，用于通信和网络；不仅用于硬件系统，还用于软件系统。因此，理论与实践的结合，是离散数学教学中的重点之一。它的另一个特点是综合性。离散数学包括多个彼此独立的数学分支，它们的知识点具有或多或少的联系，但是又自成体系。有机地组合这些数学知识，成为合理、完善的体系，这是离散数学课程在内容组织编排上的要点。课程内容的合理编排必定有助于教师的教学和学生的学习。 近年来，教育主管部门推荐了一批信息领域的英文原版教材，这些教材为我国相关学科的教材建设，提供了很好的参考和借鉴。其中有的原版教材包括了计算机学科需要的离散数学结构知识，并对多个数学分支的知识进行合理的组织。《中国计算机科学与技术学科教程2002》中，相关知识领域的名称也是“离散结构”。用这个名称代替常用的“离散数学”，自有一番用意。这或许表示，该课程不是注重数学知识的系统、完整、严谨，而是注重离散结构需要的数学，也就是计算机需要的数学。离散结构不仅涉及计算机中的数据结构，也涉及算法和程序结构、系统体系结构、通信系统和网络结构。随着信息技术的快速发展，这门课程的内容也在发展和更新。 本书是编者撰写的教材《离散数学结构》的配套资料，提供了该书全部习题和自测题的解答。 《离散数学结构》的基本编著思想是选取计算机学科需要的离散结构的数学知识，并进行合理的组织。同时关注知识在计算机学科中的应用，注重理论与实际的结合。《离散数学结构》一书中，理论和实际的结合体现在，大量例题和练习都与计算机学科相关。 本书的基本内容为前9章。习题的解答过程中利用了《离散数学结构》中的知识。不同的离散数学教材中，知识的表示形式和采用的符号可能稍有差别，所以，参阅《离散数学结构》一书，有助于理解本书的解答。 编者