离散数学-(第2版)

内容简介

　　离散数学是数学中专门用来研究离散对象及其关系的一个分支，是计算机科学与技术专业的一门重要基础课。它所研究的对象是离散的数量关系和离散的数学结构模型。全书共10章，主要包含数理逻辑、集合与关系、函数、组合计数、图和树、代数系统、自动机和初等数论等内容。本书中的“历史注记”可以帮助读者理解数学，洞察内在本质。
　　《离散数学(第2版)》体系严谨，选材精炼，讲解翔实，例题丰富，注重理论与计算机科学技术的实际问题相结合，书中选配了大量难度适当的习题，并给出奇数题的答案，适合教学。本书适合作为计算机和相关专业本科生“离散数学”的教学用书，亦可作为对离散数学感兴趣的人员的参考书。

目录

第1章 命题逻辑1

　1.1 现代逻辑学的基本研究方法1

　1.2 命题及其表示法3

　　1.2.1 命题的概念3

　　1.2.2 联结词4

　1.3 命题公式与语句形式化7

　　1.3.1 命题公式的定义7

　　1.3.2 公式的层次8

　　1.3.3 语句形式化8

　　1.3.4 复合命题真假值9

　　1.3.5 真值表10

　1.4 重言式11

　　1.4.1 重言式概述11

　　1.4.2 逻辑等价式13

　　1.4.3 等值演算15

　1.5 对偶与范式16

　　1.5.1 对偶16

　　1.5.2 简单合取式和简单析取式16

　　1.5.3 范式17

　　1.5.4 范式的性--主范式19

　1.6 其他联结词24

　　1.6.1 n元真值函数24

　　1.6.2 真值函数与命题公式的关系25

　　1.6.3 联结词完备集25

　　1.6.4 单元素联结词构成的联结词完备集26

　1.7 命题演算的推理理论27

　　1.7.1 有效推理27

　　1.7.2 有效推理的等价定理29离散数学（第2版）

　　1.7.3 重言蕴涵式31

　　1.7.4 形式推理系统32

　　1.7.5 自然推理系统p235

　1.8 命题演算中的归结推理42

　　1.8.1 归结推理规则42

　　1.8.2 归结反演43

　　1.8.3 命题逻辑归结反演的合理性和完备性44

　　习题44

第2章 谓词逻辑53

　2.1 谓词逻辑的基本概念53

　　2.1.1 个体词54

　　2.1.2 谓词54

　　2.1.3 量词55

　2.2 谓词逻辑公式与翻译56

　　2.2.1 一阶语言56

　　2.2.2 自由与约束57

　　2.2.3 闭公式58

　　2.2.4 谓词逻辑公式的解释59

　　2.2.5 谓词逻辑命题符号化60

　　2.2.6 一阶公式的分类63

　2.3 谓词逻辑等值演算64

　　2.3.1 基本等价式与置换规则64

　　2.3.2 谓词逻辑前束范式68

　2.4 谓词演算的推理理论69

　　2.4.1 推理定律69

　　2.4.2 量词消去与引入规则70

　　2.4.3 一阶谓词演算公理系统f171

　　2.4.4 自然推理系统f272

　2.5 谓词演算中的归结推理74

　　2.5.1 子句型74

　　2.5.2 置换和合一76

　　2.5.3 合一算法78

　　2.5.4 归结式79

　　2.5.5 归结反演及其完备性80

　2.6 逻辑在计算机科学中的作用81

　　2.6.1 逻辑与计算81

　　2.6.2 逻辑与计算机的起源82

　　2.6.3 逻辑与程序设计83

　　习题84

第3章 集合与关系90

　3.1 集合的概念和表示法90

　　3.1.1 集合的表示90

　　3.1.2 基本概念92

　3.2 集合的运算93

　　3.2.1 集合的基本运算93

　　3.2.2 有穷计数集93

　　3.2.3 广义交和广义并95

　3.3 有序对与笛卡儿积97

　3.4 关系及其表示99

　　3.4.1 基本概念99

　　3.4.2 关系表示法100

　3.5 关系的运算102

　　3.5.1 基本概念102

　　3.5.2 复合关系103

　　3.5.3 逆关系104

　　3.5.4 关系幂106

　　3.5.5 幂运算的性质107

　3.6 关系的性质109

　　3.6.1 关系的5种基本性质109

　　3.6.2 关系性质的等价描述 110