离散数学

出版时间：2012-4  出版社：清华大学出版社  作者：王岚 编  页数：250  

内容概要

　　本书包括离散数学课程的标准内容：数理逻辑中的命题逻辑、一阶谓词逻辑、集合论、代数系统、图论等.特别是丰富了集合论的内容，将数学归纳法、计数以及组合论中的一些广泛应用的方法纳入集合论中.另外，书末附录中还讲述了离散数学在关系数据库中的应用.
　　本书力求做到简洁明了、易懂易学，注重理论与实际的结合，注意与后续课程的衔接.适合作为普通高等院校数学、计算机科学与技术等专业的本科生教材，也可供高职高专院校的师生参考使用.

书籍目录

第1章 集合论
　1.1 集合的概念与运算
　1.1.1 集合的概念
　1.1.2 集合之间的关系
　1.1.3 集合的运算
　1.1.4 集合的运算性质
　1.1.5 序偶与笛卡儿积
　1.2 二元关系
　1.2.1 二元关系及其表示
　1.2.2 二元关系的运算
　1.3 关系的性质
　1.4 关系的闭包运算
　1.5 序关系
　1.6 等价关系
　1.7 映射
　*1.8 数学归纳法
　*1.9 计数
　1.9.1 帕斯卡三角形和二项式定理
　1.9.2 鸽巢原理
　.1.9.3 乘法法则和加法法则
　1.9.4 排列和组合
　*1.10 排列组合生成算法
　*1.11 离散概率简介
　习题
第2章 命题逻辑
　2.1 命题与联结词
　2.1.1 命题与真值
　2.1.2 命题联结词
　2.2 命题公式、指派及真值表
　2.2.1 命题公式
　2.2.2 命题的符号化
　2.2.3 公式的指派(赋值)及真值表
　2.3 命题公式的等值式，蕴含关系式
　2.3.1 命题公式的等值式
　2.3.2 代入规则与替换规则
　2.3.3 对偶式
　2.3.4 蕴含关系式
　2.4 主析取范式和主合取范式
　2.4.1 合取范式与析取范式
　2.4.2 主范式
　*2.5 联结词完备集
　2.6 可满足性问题与消解法
　2.7 推理的形式结构
　2.8 自然推理系统n中的形式证明
　习题
第3章 谓词逻辑
　3.1 基本概念
　3.1.1 个体词、谓词
　3.1.2 量词
　3.2 一阶逻辑公式及解释
　3.3 一阶逻辑等值式
　3.4 前束范式与斯科林范式
　3.4.1 前束范式
　3.4.2 斯科林范式
　3.5 谓词演算的推理理论
　3.6 数理逻辑在计算机科学中的应用
　3.6.1 “钥匙在点火开关中”报警蜂鸣器
　3.6.2 构造自锁控制安全带的电路
　3.6.3 构造一个拿子游戏装置
　3.6.4 构造电路： 专用装置和程序化计算机
　习题
第4章 公理系统下的形式证明
　4.1 命题逻辑的公理推理系统
　4.1.1 公理推理系统p
　4.1.2 公理推理系统p的可靠性、和谐性和完备性
　4.2 谓词逻辑的公理系统
　4.3 定理的机器证明
第5章 图论
　5.1 图的基本概念
　5.1.1 图及其图形表示
　5.1.2 顶点的度
　5.1.3 完全图和补图
　5.1.4 子图
　5.1.5 图的同构
　5.2 通路、回路与连通性
　5.2.1 通路和回路
　5.2.2 无向图的连通性
　5.2.3 有向图的连通性
　5.2.4 门格定理
　5.3 欧拉图与中国邮递员问题
　5.3.1 哥尼斯堡七桥问题
　5.3.2 欧拉图
　5.3.3 中国邮递员问题
　5.4 哈密尔顿图与旅行售货商问题
　5.4.1 哈密尔顿图
　5.4.2 旅行售货商问题
　5.5 树
　5.5.1 树的定义及其基本性质
　5.5.2 生成树
　5.5.3 最小生成树问题
　5.5.4 根树及其应用
　5.6 图的矩阵表示
　5.6.1 关联矩阵
　5.6.2 邻接矩阵
　5.6.3 可达矩阵
　5.6.4 图的运算
　5.7 平面图与图的着色
　5.7.1 平面图
　5.7.2 对偶图与图着色
　习题
第6章 代数系统
　6.1 二元运算与代数系统
　6.1.1 二元运算
　6.1.2 代数系统
　6.2 群和半群
　6.2.1 群和半群的定义
　6.2.2 关于逆元的性质
　6.2.3 群的几个等价性质
　6.3 子群和元素的阶
　6.3.1 子群
　6.3.2 元素的阶
　6.4 循环群和生成群、群的同构
　6.4.1 循环群和生成群
　6.4.2 群的同构
　6.4.3 循环群的性质
　6.5 变换群和置换群、凯莱定理
　6.5.1 置换群
　6.5.2 凯莱定理
　6.6 子群的陪集和拉格朗日定理
　6.6.1 子群的陪集
　6.6.2 子群的指数和拉格朗日定理
　6.7 正规子群和商群
　6.7.1 正规子群的概念
　6.7.2 正规子群的性质
　6.7.3 商群
　6.8 共轭元和共轭子群
　6.8.1 中心和中心化子
　6.8.2 共轭元和共轭类
　6.8.3 共轭子群与正规化子
　6.9 群的同态
　6.9.1 群的同态定义
　6.9.2 同态基本定理
　6.10 环与域
　*6.11 代数系统在计算机科学中的应用
　6.11.1 通信模型的基本概念
　6.11.2 纠错编码的基本概念
　6.11.3 线性分组码和汉明码
　习题
第7章 格与布尔代数
　7.1 格
　7.2 格同态
　7.3 分配格和有补格
　7.4 布尔代数
　7.5 布尔函数及其表达式
　习题
附录a 离散数学在关系数据库中的应用
　a.1 关系数据库简介
　a.2 关系代数与数据子语言
参考文献251

章节摘录

版权页：   插图：   思考题1 边远村庄的每个人要么总是说真话，要么总是说谎。对旅游者的问题，村民要么回答“是”，要么回答“不”。假定你在这一地区旅游，走到了一个岔路口，一条岔路通向你想去的遗址，另一岔路通向丛林深处。此时恰有一村民站在岔路口，问村民什么样的一个问题就能决定走哪条路？答案 “如果我问你右边的路是否通向废墟，你会说是吗？” 思考题2 斯蒂夫想用两个事实来判断三位工作伙伴的相对薪水。首先，他知道如果傅雷德的薪水不是三个人中最高的，那么杰尼斯的最高；其次，他知道如果杰尼斯的薪水不是最低的，那么罗杰斯的最高。从以上斯蒂夫知道的事实，有可能决定傅雷德、罗杰斯和杰尼斯的相对薪水吗?如果能，谁的最高，谁的最低？答案 按薪水减少的顺序：傅雷德、罗杰斯、杰尼斯。 思考题3 侦探调查了罪案的四位证人。从证人的话侦探得出的结论是：如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁说的不可能都是真话；园丁和杂役不可能都在说谎；如果杂役说真话，那么厨师在说谎。侦探能判定这四位证人分别是在说谎还是在说真话吗？答案 侦探可以断定男管家和厨师说谎，但不能判断究竟是园丁还是杂役说真话。 思考题4 试求解下面这个由爱因斯坦提出的著名的逻辑难题（也称为斑马难题）。5个不同国家且工作各不相同的人分别住在一条街上的5所房子里，每所房子的颜色不同，每个人都有自己养的不同的宠物，喜欢喝不同的饮料。根据以下提示，你能告诉我哪个房子里的人养斑马，哪个房子里的人喝矿泉水吗？英国人住在红色的房子里。西班牙人养了一条狗。日本人是一个油漆工。意大利人喜欢喝茶。挪威人住在左边的第一个房子里。绿房子在白房子的右边。摄影师养了一只蜗牛。外交官住在黄房子里。中间那个房子里的人喜欢喝牛奶。喜欢喝咖啡的人住在绿房子里。挪威人住在蓝色的房子旁边。小提琴家喜欢喝橘子汁。养狐狸的人所住的房子与医师的房子相邻。养马的人所住的房子与外交官的房子相邻。 （提示：绘一张表，其中行表示每个人，列表示他们所住的房子的颜色、他们的工作、他们养的宠物以及他们喜欢喝的饮料，用逻辑推理来判断表中正确的项。） 答案 日本人养斑马，挪威人喝矿泉水。 2．4 主析取范式和主合取范式 本节给出命题公式的两种规范表示方法，这种规范的表达式能表达真值表所能提供的一切信息。

用户评论 (总计1条)

•   内容较为全面，但不够详细，没有明确指出在计算机科学中的应用层面