离散数学

出版时间：2010-2  出版社：水利水电出版社  作者：邱晓红 编  页数：324  

前言

　　离散数学是计算机学科的核心课程，是一门理论抽象、内容广泛、结构严谨的计算机相关专业的基础课程。它不仅与后续课程，如数据结构、数据库原理、操作系统、人工智能等有紧密联系，而且对于训练和培养学生的抽象和逻辑思维能力，提高学生的科研素质方面都有着十分重要的作用。　　为了适应省级示范性软件学院及计算机相关专业《离散数学》教学改革的需要，提高学生应用理论知识解决实际问题能力的需要，根据教育部高等学校计算机科学与技术教学指导委员会颁布的计算机相关专业教学基本要求，针对地方院校的教学对象、教学特点和方法进行研究，我们提出了“《离散数学》软件工程化教学改革”研究课题和编写应用型《离散数学》教材任务，并得到教育主管部门的立项支持。为了编写好本教材，参考了美国俄克拉荷马（Oklahoma）大学的Beseme项目出版的《软件工程数学》等教材。编写教材内容注重理论知识的讲解和逻辑推理的训练，也注重应用离散数学知识分析专业课程的实际问题，讨论离散数学对后续专业课的影响，引入软件工程化应用范例和实践性内容，加强实践能力的培养。　　本书包含数据逻辑、集合论、代数结构、图论四部分内容。每部分内容结合建构主义教学理论，设计不同离散数学应用案例，提供学习《离散数学》的应用场景。每一章选择了有意义的范例和实验项目，有利于学生通过编程实践增进对离散数学知识的理解和应用，提高学生的学习兴趣。全书体系严谨、叙述深入浅出。每部分内容都分为基础知识章节和高级应用章节（带*部分），便于教师根据学时要求选讲章节内容，适合不同学时的授课（删除带**章节，可采用90学时教学，再删除带*章节，可采用70学时教学），也方便软件开发人员参考应用。　　本书的数理逻辑部分（第1～3章）由邱晓红编写，集合论部分（第四4～7章）由李光泉编写，代数结构部分（第8～10章）由艾施荣编写，图论部分（第11～13章）由熊焕亮编写。全书由邱晓红教授进行组织整理和统一风格。本书配套的实验程序源代码和演示范例，很多出自教学过程中指导学生参加各类软件大赛的作品，有些内容是“《离散数学》软件工程化教学改革”（JXJG-08-4-28）、“教学与科研有机结合提高教学质量和学生综合素质的研究”（200882ZB04）、“实施本科生全程导师制教育培养模式的研究——以江西省高校软件学院为例”（08YB078）等教改课题的研究成果，在此特别感谢有关单位领导和作者的支持。

内容概要

本书包含四部分内容：数理逻辑、集合论、代数结构、图论。每部分内容结合建构主义教学理论，设计不同离散数学应用案例，提供学习《离散数学》知识点的应用场景。每一章选择有意义的范例和实验项目，有利于学生通过编程实践增进对离散数学知识的理解和应用，提高学生的学习兴趣。全书体系严谨、叙述深入浅出。    每部分内容都分为基础知识章节和高级应用章节(带*部分)，便于教师根据学时要求选讲章节内容，适合不同学时的授课，也方便软件开发人员参考应用。    本书可作为普通高等学校计算机及相关专业本科生“离散数学”课程的教材，也可供其他专业学生、工作人员及软件开发人员阅读和参考。有些高级应用范例还可供硕士研究生学习参考。

书籍目录

前言第一部分  数理逻辑第1章  命题逻辑  1．1  命题及其表示    1．1．1  命题的基本概念    1．1．2  命题分类    1．1．3  命题标识符  1．2  逻辑联结词    1．2．1  否定联结词    1．2．2  合取联结词    1．2．3  析取联结词    1．2．4  条件联结词    1．2．5  双条件联结词    1．2．6  字位运算与布尔检索  1．3  命题公式与解释    1．3．1  命题公式    1．3．2  命题的符号化  1．4  真值表与等价公式    1．4．1  真值表    1．4．2  等价公式  1．5  命题公式的分类与蕴含式    1．5．1  命题公式的分类    1．5．2  重言式与矛盾式的性质    1．5．3  蕴含式  1．6  其他逻辑联结词和最小功能完备联结词组    1．6．1  其他逻辑联结词    1．6．2 最小功能完备联结词组    1．6．3  联结词的逻辑电路表示  1．7  对偶与范式    1．7．1  对偶式与对偶原理    1．7．2  命题公式的范式    1．7．3  命题公式的主析取范式和主合取范式  1．8  推理理论    1．8．1  直接证法    1．8．2  间接证法    习题一    实验一  真值表的程序计算  第2章  谓词逻辑  第3章  基于归结原理的推理证明料第二部分  集合论  第4章  集合及其运算  第5章  二元关系  第6章  函数  第7章  集合的基数第三部分  代数结构  第8章  半群、语言和自动机  第9章  代数系统  第10章  格与布尔代数第四部分  图论  第11章  图的基本概念  第12章  树  第13章  支配集、覆盖集、独立集与匹配理论《离散数学》常用符号表参考文献

章节摘录

　　第1章 命题逻辑　　逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。辩证逻辑是研究反映客观世界辩证发展过程的人类思维形态的科学。形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究。因此数理逻辑也称为符号逻辑。数理逻辑的基础部分是命题逻辑和谓词逻辑。　　本章首先介绍命题逻辑，谓词逻辑将在第2章讨论。　　命题逻辑是研究命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。命题是指具有具体意义且又能判断它是真还是假的句子。　　如果把命题看做运算的对象，如同代数中的数字、字母或代数式，而把逻辑连接词看做运算符号，就像代数中的“加、减、乘、除”那样，那么由简单命题组成复合命题的过程就可以当作逻辑运算的过程，也就是命题的演算。　　逻辑运算同代数运算一样具有一定的性质，满足一定的运算规律。例如满足交换律、结合律、分配律，同时还满足逻辑上的同一律、吸收律、双重否定律、德·摩根定律等。利用这些定律，就可以进行逻辑推理，可以简化复合命题，可以推证两个复合命题是否等价等。这些推理和证明在计算机程序设计、程序正确性证明和程序设计语言以及人工智能等诸多方面都得到了应用。　　1.1 命题及其表示　　1.1.1 命题的基本概念　　数理逻辑研究的中心问题是推理（Inference），而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。在数理逻辑中，将能够判断真假的陈述句称为命题。因此命题就成为推理的基本单位。在命题逻辑中，对命题的组成部分不再进一步细分。　　定义1.1.1 能够判断真假的陈述句称为命题（Proposition）。命题的判断结果称为命题的真值，常用T（True或1）表示真，F（False或0）表示假。真值为真的命题称为真命题，真值为假的命题称为假命题。　　从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句；二是能否判定真假，二者缺一不可。