基本信息
- 原书名:Discrete Mathematics and Its Applications, Seventh Edition, Chinese Abridgement

内容简介
作译者
Discrete Mathematics and Its Applications,7E
Kenneth H.Rosen 作为位于新泽西州蒙茅斯县的AT&T实验室杰出技术会员已经拥有一段很长的职业生涯。目前他在蒙茅斯大学任访问研究教授,为研究生讲授计算机科学课程。
Rosen博士于1972年获得位于安娜堡的密歇根大学数学学士学位,1976年获得麻省理工学院数学博士学位,在哈罗德·斯塔克(Harold Stark)的指导下他撰写了数论方面的博士论文。1982年加入贝尔实验室之前,他曾就职于科罗拉多大学博尔德分校;哥伦布市的俄亥俄州立大学;在欧洛诺市的缅因大学任数学副教授。在AT&T工作时,他在蒙茅斯大学任教,教授离散数学、编码理论和数据安全方面的课程。他目前教授算法设计以及计算机安全和密码学方面的课程。
Rosen博士在数论及数学建模的专业期刊上发表了大量论文。他是《初等数论及其应用》(Elementary Number Theory and Its Applications)的作者,该书由Pearson(培生)出版并广为采用,目前第6版也已经翻译成了中文。他也是《离散数学及其应用》(Discrete Mathematics and Its Applications)的作者,该书由McGraw-Hill(麦格劳希尔)出版,目前是第7版。《离散数学及其应用》(Discrete Mathematics and Its Applications)自出版以来在北美发行超过350 000册,在世界其余各地发行成千上万册。这本书也已经被翻译成法文、希腊文、中文、越南文和韩文。他还是《UNIX:参考大全》(UNIX:The Complete Reference)、《UNIX系统V版本4:简介》(UNIX System V Release4:An Introduction)、《最佳UNIX小技巧》(Best UNIX Tips Ever)的合著者,这些书均由奥斯本/麦格劳希尔出版。这些书发行超过150 000册,并翻译成中文、德文、西班牙文和意大利文。Rosen博士还是由CRC出版社出版的《离散及组合数学手册》(Handbook of Discrete and Combinatorial Mathematics)的编辑,他是CRC离散数学丛书的顾问编辑,丛书包括超过55卷论述离散数学的不同方面,其中大多数内容在这本手册中有介绍。Rosen博士现任《离散数学》(Discrete Mathematics)期刊副主编,负责审阅提交的论文,涉及离散数多个领域,包括图论、枚举和数论。他对将数学软件集成到教育和专业环境中很有兴趣,并在这些方面参与和Waterloo Maple Inc.的MapleTM软件的一些合作项目。Rosen博士还和多家出版公司合作开发作业交付平台。
在贝尔实验室和AT&T实验室期间,Rosen博士所从事的项目涉猎广泛,包括运筹学研究、计算机和通信设备的产品线规划和技术评估。他帮助规划AT&T在多媒体领域的产品和服务,包括视频会议、语音识别、语音合成和图像联网。他为AT&T使用新技术做评估,并在图像联网领域从事标准化工作。他还发明了许多新服务,并持有超过55项专利。他的一个最有趣的项目涉及帮助评估AT&T为提高吸引力而采用的技术,这也是EPCOT中心的一部分。
目录
改编者序
译者序
前言
配套网站
致学生
关于作者
符号表
第1章 基础:逻辑和证明1
1.1 命题逻辑1
1.1.1 引言1
1.1.2 命题1
1.1.3 条件语句4
1.1.4 复合命题的真值表7
1.1.5 逻辑运算符的优先级7
1.1.6 逻辑运算和位运算7
练习8
1.2 命题逻辑的应用11
1.2.1 引言11
1.2.2 语句翻译11
前言
对教师而言,我的目的是要利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具,希望为教师提供能够以最适合特定学生特点的方式高效地教授离散数学的教材。希望本书能够达到这些目标。
我为本教材在过去所取得的巨大成功而感到非常欣慰。根据北美600多所学校以及全球各地许多大学成功采用了本书的大批师生的反馈和建议,此次第7版进行了许多改进。
本教材是为一至两个学期的离散数学入门课程而设计的,适用于数学、计算机科学和工程等各类专业的学生。虽然唯一的先修课程要求是大学代数,但是要想真正学好离散数学还需要掌握更多的数学知识。
离散数学课程的目标
离散数学课程有多个目标。学生不仅要学会一些特定的数学知识并知道怎样应用,更重要的是,这样一门课应培养学生的数学逻辑思维。为此,本教材特别强调数学推理以及用不同的方法解题。本书中五个重要主题交织在一起:数学推理、组合分析、离散结构、算法思维、应用与建模。成功的离散数学课程应该努力使这五个主题相互融合、平衡。
1.数学推理:学生必须理解数学推理,以便阅读、领会并构造数学论证。本书以数理逻辑开篇,在后面证明方法的讨论中,数理逻辑是基础。本书描述了构造证明的方法与技巧。本书特别强调数学归纳法,不仅给出了这种证明的许多不同类型的实例,还详细地解释了数学归纳法为什么是有效的证明技术。
2.组合分析:一个重要的解题技巧就是计数或枚举对象。本书中,对枚举的讨论从计数的基本技术着手,重点是用组合分析方法来解决计数问题并分析算法,而不是简单地应用公式。
3.离散结构:离散数学课程应该教会学生如何处理离散结构,即表示离散对象以及对象之间关系的抽象数学结构。离散结构包括集合、置换、关系、图、树和有限状态机等。
4.算法思维:有些问题可以通过详细说明其算法来求解。在清楚地描述算法后,就可以构造一个计算机程序来实现它。这一过程中涉及的数学部分包括算法的详细说明、正确性验证以及执行算法所需要的计算机内存和时间的分析等,这些内容在本书中均有介绍。算法是用英语译著中采用汉语。——译者注和一种易于理解的伪代码来描述的。
5.应用与建模:离散数学几乎在每个可以想象到的研究领域中都有应用,本书介绍了其在计算机科学和数据网络中的许多应用,还介绍了在其他各种领域中的应用,如化学、植物学、动物学、语言学、地理学、商业以及因特网等。这些均是离散数学的实际而又重要的应用,而不是编造的。用离散数学来建模是十分重要的问题求解技巧,本书中的一些练习让学生有机会通过自己构造模型掌握这一技巧。
本书特色
易理解性:本书对于初学者来说已被实践证明是易读易懂的。绝大部分内容不需要读者具备比大学代数更多的数学预备知识。需要额外帮助的学生可以在配套网站找到相应工具将数学水平提升到本书的水准。本书中少数几个需要参考微积分的地方也已显式注明。大多数学生应该很容易理解书中用来表示算法的伪代码,无论他们是否正式学过程序设计语言。本书不要求正规计算机科学方面的预备知识。
每章都是从易于理解和领会的水平开始。一旦详细介绍了基本数学概念,就会给出稍难一些的内容以及在其他研究领域中的应用。
灵活性:本书为能灵活使用做了精心设计。各章对其前面内容的依赖程度都降到最低。每章分成长度大致相等的若干节,每节又根据内容划分成若干小节以方便教学。教师可以根据这些分块灵活地安排讲课进度。
写作风格:本书的写作风格是直接而又实用的。使用准确的数学语言,但没有采用过多的形式化与抽象。在数学命题中的记号和词语表达之间做了精心的平衡。
数学严谨性和准确性:本书中所有定义和定理的陈述都十分仔细,这样学生可以欣赏语言的准确性和数学所需的严谨性。证明则先是动机再缓慢展开,每一步都经过了详细论证。证明中用到的公理及其所导出的基本性质在附录中均有显式描述,这呈现给学生一个清晰的概念,即在一个证明中他们能够作何种假设。本书解释并大量使用了递归定义。
实例:通过许多例子阐述概念、建立不同主题之间的关联,并介绍应用。在大部分例子中,首先提出问题,然后再以适量的细节给出其解。
应用:本书中所含的应用展示了离散数学在解决现实世界中的问题时的实用性。本书包含的应用涉及广泛的领域,包括计算机科学、数据网络、心理学、化学、工程学、语言学、生物学、商业和因特网。
算法:离散数学的结论常常要用算法来表述,因此本书每章都介绍一些关键算法。这些算法采用文字叙述,同时也采用一种易于理解的结构化伪代码来描述。简要分析了书中所有算法的计算复杂性。
序言
编著的《离散数学及其应用》一书包括计算机专业学生必须掌握的数学基础知识,并且给出许多应用离散数学解决现实问题的实例,一些知识点给出相关的历史背景知识,配有大量计算、研究和实践的题目及推荐参考读物。该书内容全面,由浅入深,通俗易懂,被全球很多大学使用,是一本非常优秀的教材。
近年来,国内的许多高校都采用国外的优秀原版书作为教材。而《离散数学及其应用》原版书篇幅较长,使得部分中国学生难以阅读。为了将这本优秀教材介绍给更多的中国学生,在保留原作者写作风格的前提下,我们删减了部分章节内容编成此本科教学版,以适合中国学生的使用和阅读。
原书中的一些内容,如第3、4、5、7、13章(算法、数论和密码学、归纳与递归、离散概率、计算模型),在其他课程中已有讲授或单独作为一门课程讲授,我们在本科教学版中将这些内容删除,保留了逻辑和证明、集合、函数、计数和高级计数技术、关系、图、树和布尔代数等内容。
原书有4000多道各种类型的练习题,其中包括帮助学生掌握基本概念的练习、提高应用离散数学知识解决问题的计算机课题及计算和探索题目,以及需要查阅课外资料扩展学习的写作课题。题目按难易程度分级,分为简单、难度适中和难度较大各种类型。为了保持原书的特点,对于保留的章节,我们删去了每节后的偶数练习题,这样可以使得原书的各种类型、不同难度的习题都得以保留。关于一些知识点的相关历史背景知识未作保留,目的是减少本书的篇幅。
感谢原书作者Kenneth H.Rosen教授和McGraw-Hill出版社的授权,感谢机械工业出版社的努力,使更多的中国学生可以使用这本优秀教材。感谢同行和读者提出的宝贵建议。本科教学版力求保持原书的特点并符合本科离散数学教学大纲的要求,但难免存在不足之处,可能会给读者阅读造成一定影响,欢迎广大师生和读者提出宝贵意见。
陈琼
2016年11月于华南理工大学
译者序
离散数学一直被IEEE & ACM确定为计算机专业最核心的课程(最新版CC2005),也是《中国计算机科学与技术学科教程2002》中界定的计算机科学与技术专业的核心基础课程。当你学习离散数学时,你会发现离散数学为许多计算机专业课程提供理论基础,尤其是为大多数计算机算法提供基础。
本书清晰地介绍了离散数学中的概念和技术,并向读者展示其相关性和实用性,给计算机科学专业的学生将来的学习提供一切必需的数学基础。
本书的优秀之处不仅在于作者对离散数学知识点精心编排,而且其行文流畅、通俗易懂,拥有大量有趣而实用的例子,推荐读物吸引读者广泛的好奇心,丰富的练习帮助读者掌握离散数学的概念和技巧。本书最大的优势在于它的配套网站中给出了一系列丰富的课外资源,既可以辅助教师根据实际情况安排教学活动,又能够帮助学生评估自身学习状况,学习撰写证明并避免常见错误,从各个方面提高学生学习和解决问题的能力,引领学生探索离散数学的新应用。
本书译自Kenneth H. Rosen所著的《Discrete Mathematics and Its Applications, Seventh Edition》。这本书在北美及全球有600多所大学采用,在中国也已经被多所大学采纳作为计算机系的离散数学教材。作者一直根据广大教师和学生的反馈意见不断完善这本书,使其能适应计算机科学及应用的发展。自出版以来这本书在北美发行超过350 000册,同时这本书也已经被翻译成法文、希腊文、中文、越南文和韩文等。因此,本书是一本不俗的教科书。
如果你有幸读到本书,那恭喜你了。你可以参考作者的建议或按自己的兴趣阅读本书,我相信你一定能从本书中获益匪浅。
本书第7版做了重大修订,翻译工作是在第6版译稿的基础上进行的。感谢第6版的译者袁崇义、屈婉玲、张桂芸。第7版翻译分工如下:作者简介、前言、配套网站、致学生,以及第1章和第2章(含练习答案)、推荐读物由徐六通(本书英文原版第7版正式评阅人之一)翻译,第3章和第4章(含练习答案)由吴斌翻译,第5章至第8章(含练习答案)由杨娟翻译。由于译者水平所限,本书难免有不妥的地方,敬请读者不吝赐教。
译者
2014年10月于北京