离散数学

出版时间：2009  出版社：机械工业出版社  作者：董晓蕾,曹珍富  页数：312  
Tag标签：无  

前言

顾名思义，离散数学是研究离散对象及其相互间关系的一个数学分支，它的基本内容已出现在现代科学技术的各个领域。例如，计算机科学、程序设计、计算机网络、信息论与编码、通信理论、现代密码学、数字信号处理和形式语言等都与离散数学密切相关。正因为如此，离散数学在国际上已受到高度重视，在我国也已成为理工科高等院校各专业的重要基础课，尤其是计算机和应用数学专业。离散数学的内容非常广泛，它至少包含了数理逻辑、集合论、代数学、组合数学、数论、图论、计算理论和复杂性理论、复杂网络以及协同网络计算等内容。这些内容里面又细分了许多个分支学科，包含了当前国际前沿的数学和科学技术理论研究课题。在已出版的众多离散数学教科书及其习题解答中，大部分都是介绍那些应用广泛且易理解、可接受的基本知识和方法。我们也出版了一本《离散数学学习指导》，该书的写作风格类似于国外流行的Schaum’s Outline Series教材，在内容上则增加了“密码学”或“信息安全理论”的数学基础内容，使离散数学的基本内容有了一些扩展。而本书是在《离散数学学习指导》的基础上编写的一本适应面广、内容适中的离散数学教材。全书共五篇，依次为数理逻辑、集合论、代数系统、组合分析与算法数论、图论，分成14章：命题逻辑，谓词逻辑，集合，关系，函数，半群、语言和自动机，群、环和域，格与布尔代数，组合分析，算法数论，无向图，平面图与图着色，有向图，树。各章都尽量安排了“应用”，试图让学生学以致用。其中，有些应用是对科技进步产生重要作用的，例如，自动定理证明、数字电路、语言与有限自动机、基于身份的密码设计等；有些应用在科学理论上意义重大，例如，超越数无穷的集合论证明等。另外，第10章（算法数论）还引进了最新的研究成果，特别是近几年才产生的“双线性配对与基于身份的密码”，供读者选学。

内容概要

　　全书共14章，第1～2章为数理逻辑，第3～5章为集合论，第6～8章为代数系统，第9～10章为组合分析与算法数论，第11～14章为图论。每部分内容尽量由浅人深，同时都尽量安排了“应用”，试图让读者懂得“学以致用”。其中有些应用对科技进步产生重要作用，有些应用在科学理论上意义重大。　　本书内容丰富翔实，条理清晰，可作为高等院校计算机、电类及相关专业“离散数学”课程的教材，也可作为相关科研人员的参考书。

作者简介

董晓蕾，2001年在哈尔滨工业大学获理学博士学位，同年到上海交通大学做博士后，2003年出站留校。主要研究数论、密码学和可信计算等，发表40余篇学术论文，其中SCI和EI检索的论文有30余篇（次）。主持国家自然科学基金等多项科研项目，获得教育部和上海市自然科学一、二等奖各一项。曾赴日本筑波大学和香港浸会大学访问研究。曹珍富，上海交通大学电信学院一级责任教授、博士生导师。中科院青年奖励研究基金、国家杰出青年基金和国务院政府特殊津贴获得者。主要研究数论、密码学和通信网安全等。1981年以来发表300多篇期刊论文，被SCI和EI检索的分别超过100和130篇，出版5部著作。主持国家和省部级科研项目40余项，获得省部级奖7项。曾6次去日本、中国香港和中国台湾等地的大学访问研究或讲学。

书籍目录

出版者的话序言前言教学建议第一篇 数理逻辑第1章 命题逻辑1.1 命题与联结词1.1.1 命题基本概念1.1.2 命题联结词1.1.3 复合命题1.2 命题公式1.2.1 定义1.2.2 赋值1.2.3 真值表技术1.3 等值演算1.3.1 基本等值式1.3.2 等值演算过程1.3.3 对偶公式和内否公式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.8 命题逻辑归结推理法1.9 命题逻辑推理的机械化方法第2章 谓词逻辑2.1 谓词逻辑的基本概念2.1.1 谓词的概念2.1.2 量词的概念2.2 谓词逻辑公式2.2.1 合式公式2.2.2 约束变元和自由变元2.2.3 赋值2.2.4 换名规则和替换规则2.3 谓词逻辑的等值演算与前束范式2.3.1 基本等值式2.3.2 前束范式2.4 Skolem 标准型2.4.1 前束范式2.4.2 无前束范式2.5 谓词逻辑的推理理论2.5.1 基本永真蕴涵式2.5.2 推理规则2.5.3 推理实例2.6 谓词逻辑的归结推理法2.6.1 归结证明过程2.6.2 归结证明实例第二篇 集合论第3章 集合3.1 集合的定义3.2 集合的基本运算3.3 有限集合的计数3.4 集合表达式的相等与包含3.5 集合的特征函数第4章 关系4.1 二元关系4.2 二元关系的表示及按性质分类4.2.1 二元关系的关系矩阵和关系图表示4.2.2 二元关系的按性质分类4.3 二元关系的运算4.4 二元关系的合成4.5 关系的闭包4.6 等价关系和偏序关系4.6.1 等价关系4.6.2 偏序关系第5章 函数5.1 函数的基本概念5.2 函数的性质5.3 函数的复合与反函数5.4 可逆函数集与置换5.5 二元运算5.6 基数第三篇 代数系统第6章 半群、语言和自动机6.1 半群与语言6.2 语言和文法6.3 有限状态机6.4 有限状态自动机6.5 语言与自动机的关系第7章 群、环和域7.1 群的基本概念7.2 子群7.3 群的同态与同构7.4 子群的陪集7.5 对称群、置换群、正规性与商群7.6 群在集合上的作用7.7 同态基本定理与同构定理7.8 环的基本概念7.9 子环、理想与商环7.10 交换环中的因子分解7.11 多项式环7.12 多项式环的因子分解7.13 域的基本概念7.14 分裂域7.15 有限域第8章 格与布尔代数8.1 格的概念8.2 分配格8.3 有补格8.4 布尔代数8.5 布尔表达式8.6 数字电路与最小化第四篇 组合分析与算法数论第9章 组合分析9.1 计数9.2 排列与组合9.3 递推序列9.4 抽屉原理9.5 生成函数第10章 算法数论10.1 整数论10.2 与整数有关的典型算法10.3 素性测试、因数分解与公钥密码学10.3.1 素性测试10.3.2 因数分解10.3.3 公钥密码10.4 有限域上的椭圆曲线算术和ECC10.5 配对和基于身份的公钥密码体制10.5.1 双线性配对10.5.2 基于身份的密码第五篇 图论第11章 无向图11.1 无向图的基本概念11.2 无向图的表示11.3 无向图的连通性11.4 欧拉图与哈密顿图11.4.1 欧拉图11.4.2 哈密顿图11.5 最短通道问题第12章 平面图与图着色12.1 平面图的基本概念12.2 欧拉公式和极大平面图12.3 平面图的对偶图12.4 图着色第13章 有向图13.1 有向图的基本概念13.2 有向图的连通性第14章 树14.1 基本定义和性质14.2 生成树与最小生成树14.3 有根树14.4 二叉树和哈夫曼树参考文献

章节摘录

第1章 命题逻辑本章介绍命题逻辑的基本知识、基本思想和方法。命题逻辑又称命题演算，是以命题为研究对象、以推理中前提和结论之间的形式关系为研究目的的逻辑学科，包括命题与联结词、命题公式（特别是真值表技术）、等值演算、命题公式的范式、联结词的功能完全集、永真蕴涵式、命题逻辑的推理理论、命题逻辑推理的机械化方法等。1.1 命题与联结词1.1.1 命题基本概念命题对于命题逻辑来说是一个原始的概念，因此不能在命题逻辑的范围内给出它的精确定义，只能描述它的性质。【定义1.1】在经典命题逻辑中，把能判断真假但不能既真又假的陈述句的内容称为命题。命题必须为陈述句的内容，而不是陈述语句。有关语句的介绍可见第6章。为了说明命题是陈述语句的内容，通常在陈述语句外面加引号来表示命题。例如，陈述语句：3是素数。构成的命题是“3是素数”，即3是素数是语句（不是命题），“3是素数”是命题。命题必须具有真假值。疑问句、祈使句、感叹句的内容没有真假之分，所以它们不是命题。例如，“北京是中国的首都”是命题；“关门！”，“你上哪里？”这种命令和问话语句其内容不能判断真假，所以不是命题；“太阳系外有外星人”，目前人类尚无法确定其真假，但从事物的本质而论，该语句的内容是可分辨真假的，所以它也是命题。

编辑推荐

《离散数学》具有以下特点：讲解透彻：深入浅出地介绍离散数学所包含的基本知识。内容新颖：融合了作者自己的理解、体会、方法和结果。注重应用：介绍了一些相关知识在现代科学技术领域的应用。〈br〉习题适中：便于学生巩固所学知识、加深理解，学以致用。