离散数学

第1章 命题逻辑11.1现代逻辑学的基本研究方法11.1.1思维： 感知的概念化和理性化11.1.2现代逻辑学求助数学——符号化21.1.3现代逻辑学追随数学——公理化21.1.4现代逻辑学改造数学——形式化31.2命题及其表示法41.2.1命题的概念41.2.2复合命题41.2.3联结词51.2.4复合命题真假值71.3命题公式与翻译91.3.1命题公式的定义91.3.2公式的层次101.3.3翻译101.4真值表与等价公式111.4.1真值表111.4.2等价公式121.5重言式与等值演算121.5.1重言式121.5.2等值演算141.6对偶与范式161.6.1对偶161.6.2简单合取式和简单析取式171.6.3范式181.6.4范式的唯一性——主范式201.7其他联结词251.7.1n元真值函数261.7.2真值函数与命题公式的关系261.7.3联结词完备集271.7.4单元素联结词构成的联结词完备集281.8推理理论291.8.1有效推理291.8.2有效推理的等价定理301.8.3重言蕴涵式321.8.4形式推理系统P1341.8.5自然推理系统P235习题41第2章 谓词逻辑512.1谓词逻辑的基本概念512.1.1个体词522.1.2谓词522.1.3量词532.2谓词逻辑公式与翻译542.2.1一阶语言542.2.2自由与约束552.2.3闭公式562.2.4谓词逻辑公式的解释572.2.5谓词逻辑命题符号化582.2.6谓词逻辑公式的分类612.3谓词逻辑等值演算622.3.1基本等价式与置换规则622.3.2谓词逻辑前束范式662.4谓词演算的推理理论682.4.1推理定律682.4.2量词消去与引入规则692.4.3一阶谓词演算公理系统F1692.4.4自然推理系统F2712.5逻辑在计算机科学中的作用732.5.1逻辑与计算732.5.2逻辑与计算机的起源742.5.3逻辑与程序设计75习题76离散数学目录第3章 集合与关系823.1集合的概念和表示法823.1.1集合的表示823.1.2集合的基本概念843.2集合的运算853.2.1集合的基本运算853.2.2有穷计数集863.2.3广义交和广义并873.3有序对与笛卡儿积893.4关系及其表示913.4.1关系的基本概念913.4.2关系表示法923.5关系的运算943.5.1基本概念943.5.2复合关系953.5.3逆关系963.5.4关系幂983.5.5幂运算的性质993.6关系的性质1013.6.1关系的五种基本性质1013.6.2关系性质的等价描述1023.7关系的闭包1063.7.1闭包的基本概念1063.7.2闭包的性质1103.8集合的划分与覆盖1113.9等价关系和等价类1123.9.1等价关系1123.9.2等价类的性质1143.9.3商集与划分1153.10偏序关系1163.11偏序集与哈斯图1173.12包含排斥原理120习题121第4章 函数1284.1函数的定义1284.1.1函数和像1284.1.2函数的性质1304.1.3常用函数1314.2复合函数和反函数1324.2.1复合函数1324.2.2反函数1344.3特征函数与模糊子集1364.3.1特征函数1364.3.2模糊集合1374.4基数的概念1384.4.1后继与归纳集1384.4.2自然数，有穷集，无穷集1394.4.3基数1444.5可数集与不可数集1444.6数学归纳法1464.6.1归纳法证明1464.6.2数学归纳法第一原理1464.6.3数学归纳法第二原理147习题149第5章 图论1535.1图的基本概念1535.1.1图的定义和表示1535.1.2图的同构1575.1.3完全图与正则图1595.1.4子图与补图1595.1.5通路与回路1615.2图的连通性1635.2.1无向图的连通性1635.2.2有向图的连通性1655.3图的矩阵表示1655.3.1关联矩阵1655.3.2有向图的邻接矩阵1665.3.3有向图的可达矩阵1685.4二部图1685.4.1二部图及判别定理1685.4.2完备匹配1695.5欧拉图1715.6哈密顿图1745.7平面图1775.7.1平面图及其判定定理1775.7.2平面图的对偶图1835.8带权图184习题185第6章 树及其应用1936.1树的术语和性质1936.1.1树的定义及相关术语1936.1.2树的性质1956.2生成树1966.3最小生成树1996.4树的遍历2026.5二叉树2046.5.1二叉树的性质2046.5.2二叉搜索树2056.5.3赫夫曼树2066.6决策树2076.6.1决策树的定义2076.6.2最短时间排序2096.7树的同构2096.8博弈树2136.8.1博弈树的概念2136.8.2极大极小分析法2136.8.3α拨录糁技术216习题218第7章 计数方法与鸽巢原理2227.1基本原理2227.1.1加法原理2227.1.2乘法原理2237.2排列与组合2247.2.1排列2247.2.2组合2247.3排列组合生成算法2257.3.1排列生成算法2257.3.2组合生成算法2267.4离散概率论2297.4.1离散概率简介2297.4.2有限概率2307.4.3条件概率与独立性2327.4.4Bayes定理2337.5广义的排列和组合2347.6二项式系数和组合恒等式2367.6.1二项式定理2367.6.2组合恒等式2387.7鸽巢原理2397.7.1鸽巢原理的简单形式2397.7.2鸽巢原理的一般形式240习题241第8章 数论与递归关系2438.1素数2438.2最大公约数与最小公倍数2448.3同余2478.4一次同余方程和中国剩余定理2498.4.1一次同余方程2498.4.2中国剩余定理2508.5数论在密码学中的应用2518.5.1公钥密码学2518.5.2RSA密码2528.6递归关系简介2528.6.1递归定义函数2528.6.2递归定义集合2548.6.3递推关系模型2558.7求解递归关系2578.8递归在算法分析中的应用259习题262第9章 代数系统2649.1二元运算及其性质2649.1.1定义和表示2649.1.2二元运算的性质2669.2代数系统2689.2.1定义和实例2689.2.2子代数系统2709.2.3代数系统的同态与同构2709.3半群与独异点2719.3.1定义与性质2719.3.2子系统与直积2729.4群2739.4.1群的定义2739.4.2群的性质2759.4.3子群的定义2779.4.4正规子群与商群2789.4.5群的同态与同构实例2819.4.6循环群与置换群2849.5环与域2869.5.1环2869.5.2域2879.6格与布尔代数2889.6.1格2889.6.2布尔代数2929.7组合电路295习题297第10章 自动机、文法和语言30510.1串和语言30510.2形式文法30610.3有限状态机30910.4有限状态自动机31110.5不确定有限状态自动机31410.6语言和自动机之间的关系317习题318附录A 历史注记322参考文献332