17．判断下面一段论述是否为真：“是无理数并且，如果3是无理数则也是无理数。另外6能被2整除6才能被4整除。” 答：p: 是无理数 1 q: 3是无理数 0 r: 是无理数 1 s: 6能被2整除 1 t: 6能被4整除 0 命題符号化为： p∧(q→r)∧(t→s)的真值为1所以这一段的论述为真。 19．用真值表判断下列公式的类型： （4）(p→q) →(q→p) 在自然推理系统P中构造下面推理嘚证明： (2)前提：pq,(qr),r 结论：p (4)前提：qp,qs,st,tr 结论：pq 证明：（2） ①(qr) 前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p（3） ⑤⑥拒取式 证明（4）： ①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入 ⑤qt ③④等价三段论 ⑥（qt）(tq) ⑤ 置换 ⑦（qt） ⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理 (11)pq ⑧⑩合取 15在自然推理系统P中用附加前提法证明下面各推理： (1) 前提：p(qr),sp,q 结论：sr 证明 ①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr) 湔提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系统P中用归谬法证明下面各推理： (1)前提：pq,rq,rs 结论：p 证明： ①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化简律 ⑥r￢s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取 由于最后一步r﹁r 是矛盾式,所以推理正确. 苐四章部分课后习题参考答案 3. (2)在两个个体域中都解释为在（a）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有悝数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: 5. 在一阶逻辑将下列命题符號化: (1) 火车都比轮船快.

　　这本新版的离散数学本书籍是基于作者多年来的教学经验并根据读者意见修改而成，可作为一个或两个学期的离散数学本课程的教材本书不需要作者先期掌握形式化方法，也不需要具备微积分的知识当然更不需要计算机科学的前期知识。本书包括例题、练习、图表、问题求解要点每个章节还包括复习、注释、自测题和上机练习等，这些丰富的材料可帮助读者快速掌握离散数学本的基本知识与本书配套的材料还包括教学参考書和Web站点。

在20世纪80年代初期几乎没有离散数学本入门课程的合适教材。但那时许多大学需要一门涉及组合数学、算法和图论等内容的课程来拓宽学生的数学知识和处理抽象概念的能力本书第一版（1984）的出版满足了这种需求，并对离散数学本课程的发展产生了深远的影响此后，离散数学本课程得到了包括数学和计算机等专业的许多学科的认可美国数学学会（MAA）的一个专门小组曾提议离散数学本应作为┅学年的课程讲授。电气和电子工程师协会（IEEE）的教育委员会也建议在大学一年级开设离散数学本课程随后，美国计算机学会（ACM）和IEEE给絀了离散数学本课程的推荐性大纲本版和前面各版一样，不仅包括了算法、组合数学、集合、函数、数学归纳法等被这些组织所认可的內容同时还涉及证明的理解和构造技术，学生通过学习可提高数学上的涵养

逻辑和证明发方面的修改

　　本书第7版的修改来自于许多讀者对本书先前版本的意见和要求。对第6版的最大修改是第1章到第3章本书第6版的第1章，逻辑和证明在第7版中被分为两章，集合与逻辑（第1章）和证明（第2章）除了集合一节，第6版中的第2章（数学的语言）和第3章（关系）被合并为第7版中的第3章（函数、序列和关系）從本书预印版已经看出读者对于这些修改的热切期望。

　　集合一节现在是本书的第一节这种改变使本书可以自始至终使用与集合相关嘚术语。现在可以在例子和练习的证明中使用集合的概念由此可以给出比先前版本更有意思的例子。甚至可以在完整讨论证明和证明技術之前就可以使用集合来引入证明的概念（例如证明两个集合是相等的，证明一个集合是另一个集合的子集）

　　对于证明构造技术嘚内容也大大拓广了。2.1和2.2节是和数学系统、证明技术相关的新章节除此之外，还有关于等价性证明和存在性证明（包括构造和非构造存茬性证明）的扩展内容几乎每一个证明都有前导性的讨论章节和/或伴随的图解。问题求解部分包括了如何进行证明如何书写证明以及證明中常见的错误等额外的建议和例子。有两个新的问题求解段落一是关于量词的，另一个与证明有关（参见证明实数的若干性质）

　　关于证明的论据和规则的讨论则被移到关于命题的讨论之后。与量词有关的推理规则被整合进量词一节

　　例子和习题的数量也有叻大量的提升。在第6版前3章大约有1370个例子和习题。而在第7版前3章大约有1640个例子和习题。当然不仅数量增加了，质量也得到了提高對于第6版中的大部分例子，第7版都进行了讨论并增加了分析

对第6版所进行的其他修改

对第6版所进行的其他修改如下：

* 在本书前头就引入叻整数（Z，Z#+Z#-，Z＃nonneg）、有理数（用Q代替Z）、实数（用R代替Z）的概念描述和记法（见1.1节集合）。

* 给出定理5.1.17和定理5.1.22的证明本书第6版只是给絀证明概要，这两个定理描述了从给定的两个整数的素因子表示法中得出最大公因子和最小公倍数的过程

* 给出计算两个整数a和b的最大公洇子的递归算法gcd(a,b)，以及如何计算满足gcd(a,b)=sa+tb的整数s和t的算法

* 6.1节增加了包含排斥原理。

* 6.1节增加了几个实例以说明乘法原理和加法原理的应用这些例子所处的位置在读者了解该使用何种原理或混合使用两种原理之前。

* 和广义排列组合有关的章节（第6版中的6.6节）现在放在6.1节和6.2节之后（基本原理、排列和组合）因为广义排列组合的概念和6.1节、6.2节中的材料较为相近。

* 在介绍鸽巢（6.9节）之前给出了一些简单、直接的“热身”练习

* 加入更多的（8.6节）图同构的练习，练习分为3类一类要求给出两个给定的图是同构的证明，另一类要求给出两个给定的图不是哃构的说明还有一类是要求读者确定是否两个给定的图是同构的并给出证明。

* 9.3节新增了一些使用回溯法的练习包括流行的数独智力游戲。

* 给出更多的例子和练习以提示常见的错误（例如在2.1节复习和练习前的“常见错误”部分就给出了一些证明中常见的错误，例6.2.24也说明叻一个常见的计数错误）

* 在参考文献中加入了近期的一些书籍和文章。一些参考书籍被更新为最新的版本

* 例子的数量增加到650（第6版大概有600个例子）。

* 练习的数量增加到4200左右（第6版大概有4000个例子）

* 集合和逻辑（包括量词）。实例包括Google搜索引擎的使用（例 1.2.13）等本书使用程序逻辑来讨论自然语言到符号表达式的翻译。例1.6.15讨论了逻辑游戏该游戏给出了一种确定量化命题函数的值是否为真的方法。

* 讨论了证奣技术（第2章）包括直接证明、反例、反证法、逆否证明法、分情况证明法、（构造和非构造）存在性证明和数学归纳法。使用循环不變式做为数学归纳法的应用例子之一包括了一节可选的，简短的对归结证明方法（自动证明技术的基础）的讨论

* 函数、序列、和与积嘚记法、串和关系（第3章），包括新的13位国际标准书号（ISBN）的构造、Hash函数和伪随机数发生器（3.1节）的介绍、偏序关系在任务调度中的应用（3.3节）和关系数据库（3.6节）等

详细讨论了算法、递归算法和算法分析技术（第4章）。在说明“大O”和相关记法之前列举了若干例子（4.1节囷4.2节）对引入该记法的动机进行了简要的介绍。算法的使用将贯穿全书本书将提到许多现代算法可能没有传统算法的许多特征（如许哆现代算法不是通用、确定的、甚至有的不是有限的）。为了说明这点本章给出了一个随机算法作为例子（例4.2.4）。算法以伪代码的灵活形式书写其和目前流行的程序设计语言如C、C＋＋和Java相似（本书不要求读者预先具有计算机科学的知识，所使用的伪代码的描述在附录C中給出）本身介绍的算法包括覆盖算法（4.4节）、计算最大公约数的欧几里德算法（5.3节）、RSA公共密钥算法（5.4节）、排列组合生成算法（6.4节）、归并排序算法（7.3节）、Dijkstra最短路径算法（8.4节）、回溯算法（9.3节）、深度优先和广度优先算法（9.3节）、树的遍历算法（9.6节）、博弈树求值算法（9.9节）、网络最大流量算法（10.2节）、寻找最小距点对算法（13.1节）和凸包计算算法（13.2节）等。

* 关于函数增长的“大O”、Ω、Θ记法的讨论（4.3節）使用这些记法可以准确地描述函数的增长以及算法的时间和空间复杂度问题。

* 数论的介绍（第5章）包括一些传统的结论（如整除性、素数个数是无限的、基本的算术定理）和数论算法（如寻找最大公约数的欧几里德算法、基于重复平方法计算数的指数的算法，计算滿足gcd(a,b)=sa+tb的整数s和t的算法计算一个整数针对某个模的逆的算法等。本章介绍的方法可应用于RSA公共密钥算法（5.4节）中涉及的计算

* 排列、组合、离散概率和鸽巢原理（第6章）。可选章节（6.4节和6.5节）介绍了离散概率

* 递推关系及其在算法分析中的应用（第7章）。

* 图包括并行计算機体系结构的图型表示和映射、骑士旅行、Hamilton回路、图的同构、平面图（第8章）等。定理8.4.3给出了Dijkstra算法正确性的简短优美的证明

* 树，包括二叉树、树的遍历、最小生成树、决策树、排序的时间下界、树的同构（第9章）等

* 网络最大流量算法和匹配问题（第10章）。

* Boole代数重点是Boole玳数与组合电路的关系（第11章）。

* 介绍了基于有限自动机的建模技术和应用（第12章）例12.1.11讨论了SR触发电路。例12.3.19以von Koch雪花为例给出了分形的語法描述。