离散数学

出版时间：2009-5  出版社：清华大学出版社有限公司  作者：陈敏，罗庆云 主编  页数：191  

前言

　　离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。离散数学研究的对象是各种各样的离散量的结构及离散量之间的关系，并且一般是有限个或者可数个元素。因此它充分描述了计算机科学离散性的特点，计算机科学中的程序设计语言、数字电路、数据结构、操作系统、数据库技术、编译原理、算法的分析与设计、计算机网络、可计算性与计算复杂性理论、逻辑设计、系统结构、人工智能等理论课程都是以离散数学为基础的。同时，通过学习离散数学培养和提高了学生的抽象思维能力、逻辑推理能力和归纳构造能力，也有益于学生严谨、完整、规范的科学态度的培养。为学生今后继续学习和工作，参加科学研究，攀登科技高峰，打下坚实的数学基础。　　离散数学包括4大部分，各部分内容都十分丰富，自成体系。本书将这4大体系中最基本、最重要的内容选人，并努力做到简明扼要、深入浅出，既保持各体系的独立性，又展现出它们的密切联系。本教材的主要特色是：　　1.通过大量的实例从不同的角度对一些抽象的概念进行诠释，使其易于被学生理解和接受；　　2.强化基本概念的描述，注重基本理论的证明方法，淡化大量烦琐的、含有特殊技巧的、不带普遍意义的理论证明方法；　　3.精心安排各部分内容的先后顺序，使教材的结构更合理，内容更充实，语言更通俗易懂；　　4.内容涉猎面广，可满足不同层面学生的需求。　　总之，本教材在内容的组织上，力求提供培养学生抽象思维、缜密概括和严密的逻辑推理能力知识的同时，注重展现离散数学在计算机科学及信息科学中的应用，以增强学生使用离散数学知识分析问题和解决问题的能力，为今后处理离散信息，从事计算机软件的开发与设计以及计算机科学及信息科学中的其他实际应用打好数学基础。　　本书的主要内容包括命题逻辑、一阶逻辑、集合与关系、函数、代数结构和图论等知识，可作为计算机科学本科专业的基础理论教材，也可供有关技术人员学习参考。　　本书由陈敏、罗庆云任主编，任长安、李泽军、蒋瀚洋、徐雨明任副主编。具体分工如下。陈敏撰写第工章和第2章，并对全书进行了修改、统稿和定稿；罗庆云撰写第6章，并对全书的内容进行了认真审阅；任长安撰写第3章和第4章；戴成秋撰写第5章；蒋瀚洋撰写第7章；桂友武撰写第8章；李泽军撰写第9章；徐雨明撰写第10章。魏书对全书的内容进行了认真审阅，并提出了许多修改意见，在此深表谢意。　　在编写本书的过程中参阅了许多国内外离散数学教材及专著，在此对这些作者们表示衷心的感谢。在本书的编写过程中，得到了北京交通大学出版社领导和编辑的大力支持，在此表示深深的谢意。　　由于我们的水平和经验有限，难免会有不足与疏漏之处，恳请同行专家与广大读者批评指正。

内容概要

本书介绍了离散数学基础知识和应用方法，全书共分为4篇，第1篇为数理逻辑，内容包括命题逻辑和一阶逻辑；第2篇为集合论，内容包括集合的基本概念、二元关系、函数等；第3篇为代数系统，内容包括代数系统的基本概念、半群、群、环、域、格与布尔代数；第4篇为图论，内容包括图的基本概念、几类重要的图、最短路径、关键路径等。　　本书在内容安排上，突出由浅入深、循序渐进、通俗易懂的特点，另外各章配备了大量的例题，其内容与计算机科学的理论与实践密切结合，便于自学。本书适合作为高等院校计算机及相关专业本科生的教材，也可供计算机专业的科技人员使用或参考。

书籍目录

第1篇 数理逻辑　第1章 命题逻辑　　1.1 命题与联结词　　　1.1.1 命题　　　1.1.2 联结词　　1.2 命题公式及其分类　　　1.2.1 合式公式及层次　　　1.2.2 真值赋值及公式分类　　1.3 真值表和真值函数　　　1.3.1 真值表　　　1.3.2 真值函数　　1.4 等值式与等值演算　　1.5 联结词完备集　　1.6 范式　　1.7 命题逻辑的推理理论　　　1.7.1 推理的形式结构　　　1.7.2 自然推理系统　　习题　第2章 一阶逻辑　　2.1 谓词与量词　　2.2 一阶语言　　　2.2.1 一阶语言　　　2.2.2 解释和赋值　　　2.2.3 公式的分类    2.3 一阶逻辑的等值演算　　　2.3.1 等值演算　　　2.3.2 前束范式　　2.4 一阶逻辑的推理理论　　　2.4.1 推理定律　　　2.4.2 推理规则　　习题第2篇 集合论　第3章 集合　　3.1 集合的概念及其表示　　3.2 集合的基本运算　　3.3 有限集计数问题　　习题　第4章 二元关系　　4.1 有序对与笛卡儿积　　4.2 二元关系及其表示　　4.3 二元关系的性质　　4.4 二元关系的运算　　　4.4.1 关系的基本运算　　　4.4.2 关系的闭包　　　4.4.3 闭包的复合　　4.5 特殊关系及其性质　　　4.5.1 等价关系　　　4.5.2 相容关系　　　4.5.3 序关系　　习题　第5章 函数　　5.1 函数的基本概念　　5.2 逆函数与复合函数　　　5.2.1 逆函数　　　5.2.2 复合函数　　习题第3篇 代数系统　第6章 代数结构　　6.1 代数系统的基本概念　　　6.1.1 代数运算　　　6.1.2 代数运算的性质　　　6.1.3 代数系统　　6.2 半群与群　　　6.2.1 半群与含幺半群　　　6.2.2 群的基本概念与性质　　　6.2.3 特殊群　　6.3 环与域　　　6.3.1 环　　　6.3.2 域　　习题　第7章 格与布尔代数第4篇 图论　第8章 图的基本概念及表示　第9章 图的应用　第10章 树参考文献

章节摘录

　　在自然语言中，用联结词可以将若干简单陈述句组合成复合陈述句。如“张三和李四都考了90分”，实际上是由联结词“和”将两个简单命题“张三考了90分”和“李四考了90分”复合而成的.像这样的联结词称为逻辑联结词（logical connectives），而把由简单命题和联结词共同组成的命题称为复合命题（compositive propositions）。　　1.1.2 联结词　　既然命题逻辑是一种符号化的逻辑演算，那么首先要作的是将有关的各种命题符号化，即用命题标识符表示命题.对于简单命题，一般用小写字母声，p，q，r，s，t，…表示，并将符号放在其表示的命题前面，如：　　p：北京是中国的首都；　　q：地球是圆的。　　简单命题的真值通常都是确定的，因此其相应的命题标识符称为命题常项或命廬常元（propositionconstant）。然而有时仅用命题标识符来表示简单命题的位置标志，如同在代数运算中不对任意的J给定确定的值一样，并没有指定其确定的真值，即其真值可能为真也可能为假，这样的命题标识符称命题变项或命题变元（propositionval“iable），通常也用小写字母户，g，r，s，t，…表示.一个标识符，例如声，到底表示的是命题常项还是命题变项，一般可由上、下文确定，不会发生混淆。　　……