下载文档原格式
离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科，它研究离散对象及其关系、结构和运算方法。
离散数学的应用非常广泛，包括计算机科学、信息科学、密码学、人工智能等领域。
而离散数学第2版是一本经典的教材，它系统地介绍了离散数学的基本概念、原理和方法。
本文将为读者提供离散数学第2版课后习题的答案，帮助读者更好地理解和掌握离散数学的知识。
第一章：基本概念和原理1.1 命题逻辑习题1：命题逻辑的基本符号有哪些？它们的含义是什么？答：命题逻辑的基本符号包括命题变量、命题联结词和括号。
命题变量用字母表示，代表一个命题。
命题联结词包括否定、合取、析取、条件和双条件等，分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。
括号用于改变命题联结词的优先级。
习题2：列举命题逻辑的基本定律。
答：命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。
1.2 集合论习题1：什么是集合？集合的基本运算有哪些？答：集合是由一些确定的对象组成的整体，这些对象称为集合的元素。
集合的基本运算包括并、交、差和补等。
习题2：列举集合的基本定律。
答：集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。
第二章：数理逻辑2.1 命题逻辑的推理习题1：什么是命题逻辑的推理规则？列举几个常用的推理规则。
答：命题逻辑的推理规则是用来推导命题的逻辑规则。
常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。
习题2：使用推理规则证明以下命题：如果A成立，则B成立；B不成立，则A不成立。
答：假言推理规则可以用来证明该命题。
根据假言推理规则，如果A成立，则B成立。
又根据假言推理规则，如果B不成立，则A不成立。
2.2 谓词逻辑习题1：什么是谓词逻辑？它与命题逻辑有何区别？答：谓词逻辑是一种扩展了命题逻辑的逻辑系统，它引入了谓词和量词。
与命题逻辑不同，谓词逻辑可以对个体进行量化和描述。
离散数学课后答案第2章习题解答2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x(是鸟F:)x(会飞翔.G:)xx命题符号化为xFx→∀.))G((x)((2)令x(为人.xF:)(爱吃糖G:)xx命题符号化为GxFx→⌝∀(x))()(或者xFx⌝∧∃(xG))(()(3)令xF:)(为人.xG:)(爱看小说.xx命题符号化为xF∃.Gx∧(x()))((4) x(为人.xF:)G:)(爱看电视.xx命题符号化为Fx⌝⌝∃.x∧(x))()G(分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。
（1）-（4）中的)(x F 都是特性谓词。
2° 初学者经常犯的错误是，将类似于（1）中的命题符号化为))()((x G x F x ∧∀即用合取联结词取代蕴含联结词，这是万万不可的。
将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。
”因而符号化应该使用联结词→而不能使用∧。
若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。
”这显然改变了原命题的意义。
3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。
2.2 (1)d (a),(b),(c)中均符号化为)(x xF ∀其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。
（2） 在)(),(),(c b a 中均符号化为)(x xG ∃其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。
（3）在)(),(),(c b a 中均符号化为)xH∃(x其中.1(ba中均为假命题，在(c)中为真H此命题在)(),xx5:)(=命题。
分析 1°命题的真值与个体域有关。
离散数学习题答案解析(总16页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p：李辛与李末是兄弟，则命题符号化的结果是p（6）王强与刘威都学过法语∧解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是p q（9）只有天下大雨，他才乘班车上班→解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是q p （11）下雪路滑，他迟到了解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是()∧→p q r 15、设p：2+3=5.q：大熊猫产在中国.r：太阳从西方升起.求下列复合命题的真值：（4）()(())∧∧⌝↔⌝∨⌝→p q r p q r解：p=1，q=1，r=0，∧∧⌝⇔∧∧⌝⇔，p q r()(110)1p q r⌝∨⌝→⇔⌝∨⌝→⇔→⇔(())((11)0)(00)1∴∧∧⌝↔⌝∨⌝→⇔↔⇔()(())111p q r p q r19、用真值表判断下列公式的类型：（2）()→⌝→⌝p p q解：列出公式的真值表，如下所示：由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。
20、求下列公式的成真赋值： （4）()p q q ⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒0p q ⇔⎧⎨⇔⎩ 所以公式的成真赋值有：01，10，11。
习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ⌝→∧∧解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨，此即公式的主析取范式， 所以成真赋值为011，111。
*6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨⌝∨解：原式()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔，此即公式的主合取范式， 所以成假赋值为100。
离散数学课后答案1. 集合论1.1. 集合的基本概念•问题1：什么是集合？如何表示一个集合？集合是由一些确定的元素构成的整体。
可以使用以下方式表示一个集合：–列举法：将集合的所有元素逐一列举出来，并用大括号{}包括起来。
–描述法：使用一种公式或条件来描述集合中的元素的特点，并用大括号{}包括起来。
–空集：不包含任何元素的集合，用符号∅表示。
•问题2：集合的关系有哪些？集合的关系有以下几种：–包含关系（⊆）：集合A的所有元素都属于集合B，则称集合A是集合B的子集，表示为A⊆B。
–真包含关系（⊂）：集合A是集合B的子集，且A≠B，则称集合A是集合B的真子集，表示为A⊂B。
–并集（∪）：将两个集合中的所有元素合并在一起，去除重复元素。
–交集（∩）：将两个集合中共有的元素提取出来。
–差集（-）：从一个集合中去掉与另一个集合中相同的元素。
–互斥关系：两个集合没有共同的元素，即交集为空集。
1.2. 集合的运算•问题1：集合的运算有哪些？集合的运算有以下几种：–并集运算（∪）：将两个集合中的所有元素合并在一起，去除重复元素。
–交集运算（∩）：将两个集合中共有的元素提取出来。
–差集运算（-）：从一个集合中去掉与另一个集合中相同的元素。
–补集运算（C）：对于给定的全集U，集合A 在U中的补集就是U中除去集合A中的所有元素所构成的集合，表示为A’。
–笛卡尔积（×）：将两个集合的元素按照有序对的形式进行组合，构成一个新的集合。
•问题2：集合运算的性质有哪些？集合运算的性质有以下几种：–交换律：A∪B = B∪A，A∩B = B∩A。
–结合律：(A∪B)∪C = A∪(B∪C)，(A∩B)∩C = A∩(B∩C)。
–分配律：A∪(B∩C) = (A∪B)∩(A∪C)，A∩(B∪C) = (A∩B)∪(A∩C)。
–吸收律：A∪(A∩B) = A，A∩(A∪B) = A。
–互补律：A∪A’ = U，A∩A’ = ∅。
离散数学第二版最全课后习题答案详解离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、电气工程等领域都有着广泛的应用。
对于学习离散数学的同学们来说，课后习题的解答是巩固知识、加深理解的重要环节。
本文将为您提供离散数学第二版的最全课后习题答案详解，希望能对您的学习有所帮助。
在开始讲解具体的习题答案之前，让我们先简要回顾一下离散数学的主要内容。
离散数学包括集合论、数理逻辑、图论、代数结构等几个部分。
集合论是离散数学的基础，它研究集合的性质、运算和关系。
在集合论的习题中，常见的问题包括集合的表示、集合的运算（并集、交集、补集等）、集合的包含关系以及集合的基数等。
例如，有这样一道习题：设集合 A ＝｛1, 2, 3}，B ＝｛2, 3, 4}，求 A ∪ B 和A ∩ B。
答案是：A ∪ B ＝｛1, 2, 3, 4}，A ∩ B ＝｛2, 3}。
这是因为并集是包含两个集合中所有元素的集合，而交集是同时属于两个集合的元素组成的集合。
数理逻辑是研究推理和证明的工具，它包括命题逻辑和谓词逻辑。
在数理逻辑的习题中，需要掌握命题的符号化、逻辑公式的等价变换、推理规则的应用等。
比如，给出这样一个命题：“如果今天下雨，那么我就不去公园”，将其符号化。
我们可以设“今天下雨”为 P，“我去公园”为 Q，那么这个命题可以符号化为P → ¬Q。
图论是研究图的性质和应用的分支。
图的概念在计算机网络、交通运输等领域有着重要的应用。
图论的习题常常涉及图的表示、顶点的度、路径、连通性、图的着色等问题。
假设有这样一道题：一个无向图有 10 个顶点，每个顶点的度都为 6，求这个图的边数。
根据顶点度数之和等于边数的两倍这个定理，我们可以计算出边数为 30。
代数结构则包括群、环、域等概念，在这部分的习题中，需要理解和运用代数结构的定义和性质来解决问题。
接下来，我们具体来看一些习题的详细解答。
例 1：设集合 A ＝｛x ｜ x 是小于 10 的正奇数}，B ＝｛x ｜ x 是小于 10 的正偶数}，求 A B。
§1.1 命题和逻辑连接词习题1.11. 下列哪些语句是命题，在是命题的语句中，哪些是真命题，哪些是假命题，哪些命题的真值现在还不知道？（1）中国有四大发明。
（2）你喜欢计算机吗？ （3）地球上海洋的面积比陆地的面积大。
（4）请回答这个问题！ （5）632=+。
（6）107<+x 。
（7）园的面积等于半径的平方乘以圆周率。
（8）只有6是偶数，3才能是2的倍数。
（9）若y x =，则z y z x +=+。
（10）外星人是不存在的。
（11）2020年元旦下大雪。
（12）如果311=+，则血就不是红的。
解是真命题的有：（1）、（3）、(7)、 (9) 、（12） ；是假命题的有：（5）、 (8) ；是命题但真值现在不知道的有： (10)、 (11)；不是命题的有：（2）、（4）、（6）。
2. 令p 、q 为如下简单命题：p ：气温在零度以下。
q ：正在下雪。
用p 、q 和逻辑联接词符号化下列复合命题。
（1）气温在零度以下且正在下雪。
（2）气温在零度以下，但不在下雪。
（3）气温不在零度以下，也不在下雪。
（4）也许在下雪，也许气温在零度以下，也许既下雪气温又在零度以下。
（5）若气温在零度以下，那一定在下雪。
（6）也许气温在零度以下，也许在下雪，但如果气温在零度以上就不下雪。
（7）气温在零度以下是下雪的充分必要条件。
解 （1）q p ∧；（2）q p ⌝∧；（3）q p ⌝∧⌝；（4）q p ∨； （5）q p →；（6）)()(q p q p ⌝→⌝∧∨；（7）q p ↔。
3. 令原子命题p ：你的车速超过每小时120公里，q ：你接到一张超速罚款单，用p 、q 和逻辑联接词符号化下列复合命题。
（1）你的车速没有超过每小时120公里。
（2）你的车速超过了每小时120公里，但没接到超速罚款单。
（3）你的车速若超过了每小时120公里，将接到一张超速罚款单。
（4）你的车速不超过每小时120公里，就不会接到超速罚款单。
离散数学课后习题答案1. 第一章习题答案1.1 习题一答案1.1.1 习题一.1 答案根据题意，设集合A和B如下：Set A and BSet A and B在此情况下，我们可以得出以下结论：•A的幂集为{ {}, {a}, {b}, {a, b} }；•B的幂集为{ {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }；•A和B的笛卡尔积为{ (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }。
因此，习题一.1的答案为：•A的幂集为{ {}, {a}, {b}, {a, b} }；•B的幂集为{ {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }；•A和B的笛卡尔积为{ (a, 1), (a, 2), (a, 3), (b, 1), (b,2), (b, 3) }。
1.1.2 习题一.2 答案根据题意，集合A和B如下所示：Set A and BSet A and B根据集合的定义，习题一.2要求我们判断以下命题的真假性：a)$A \\cap B = \\{ 2, 3 \\}$b)$\\emptyset \\in B$c)$A \\times B = \\{ (a, 2), (b, 1), (b, 3) \\}$d)$B \\subseteq A$接下来，我们来逐个判断这些命题的真假性。
a)首先计算集合A和B的交集：$A \\cap B = \\{ x\\,|\\, x \\in A \\, \\text{且} \\, x \\in B \\} = \\{ 2, 3 \\}$。
因此，命题a)为真。
b)大家都知道，空集合是任意集合的子集，因此空集合一定属于任意集合的幂集。
根据题意，$\\emptyset \\in B$，因此命题b)为真。
c)计算集合A和B的笛卡尔积：$A \\times B = \\{ (x, y) \\,|\\, x \\in A \\, \\text{且} \\, y \\in B \\} = \\{ (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) \\}$。
第二章 谓词逻辑习题与解答1. 将下列命题符号化：(1) 所有的火车都比某些汽车快。
(2) 任何金属都可以溶解在某种液体中。
(3) 至少有一种金属可以溶解在所有液体中。
(4) 每个人都有自己喜欢的职业。
(5) 有些职业是所有的人都喜欢的。
解 (1) 取论域为所有交通工具的集合。
令x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。
“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧∃→∀。
(2) 取论域为所有物质的集合。
令x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。
“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧∃→∀。
(3) 论域和谓词与(2)同。
“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →∀∧∃。
(4) 取论域为所有事物的集合。
令x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。
“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧∃→∀(5)论域和谓词与(4)同。
“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →∀∧∃。
2. 取论域为正整数集，用函数+（加法），•（乘法）和谓词<，=将下列命题符号化：(1) 没有既是奇数，又是偶数的正整数。
(2) 任何两个正整数都有最小公倍数。
(3) 没有最大的素数。
(4) 并非所有的素数都不是偶数。
解 先引进一些谓词如下：x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =•∃。
x x J :)(是奇数，)(x J 可表示为)2(x v v =•⌝∃。
x x E :)(是偶数，)(x E 可表示为)2(x v v =•∃。
x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=↔=•∃∀∧=⌝。
(1) “没有既是奇数，又是偶数的正整数”可表示为))()((x E x J x ∧⌝∃，并可进一步符号化为))2()2((x v v x v v x =•∃∧=•⌝∃⌝∃。
(2) “任何两个正整数都有最小公倍数”可表示为))),(),((),(),((u z u z y u D x u D u y z D x z D z y x =∨<→∧∀∧∧∃∀∀，并可进一步符号化为)))()(()()((u z u z u y v v u x v v u z y v v z x v v z y x =∨<→=•∃∧=•∃∀∧=•∃∧=•∃∃∀∀(3) “没有最大的素数”可表示为)))(()((x y x y y P y x P x =∨<→∀∧⌝∃，并可进一步符号化为)))1)(()1(()1)(()1((x y x y y u u y u v v u y y x u u x u v v u x x =∨<→=∨=↔=•∃∀∧=⌝∀∧=∨=↔=•∃∀∧=⌝⌝∃ (4) “并非所有的素数都不是偶数”可表示为))()((x E x P x ⌝→⌝∀，并可进一步符号化为))2()1)(()1((x v v x u u x u v v u x x =•⌝∃→=∨=↔=•∃∀∧=⌝⌝∀3. 取论域为实数集合，用函数+，－（减法）和谓词<，=将下列命题符号化：(1) 没有最大的实数。
(2) 任何两个不同的实数之间必有另一实数。
(3) 函数)(x f 在点a 处连续。
(4) 函数)(x f 恰有一个根。
(5) 函数)(x f 是严格单调递增函数。
解 (1) “没有最大的实数”符号化为)(x y x y y x =∨<∀⌝∃。
(2) “任何两个不同的实数之间必有另一实数”符号化为))((y z z x z y x y x <∧<∃→<∀∀。
(3) “函数)(x f 在点a 处连续”的定义是：任给0>ε，总可以找到0>δ，使得只要δ<-||a x 就有ε<-|)()(|a f x f 。
“函数)(x f 在点a 处连续”符号化为))))()()()((0(0(εεδδδδεε+<∧<-→+<∧<-∀∧<∃→<∀a f x f x f a f a x x a x(4) “函数)(x f 恰有一个根”符号化为))0)((0)((x y y f y x f x =→=∀∧=∃。
(5) “函数)(x f 是严格单调递增函数”符号化为))()((y f x f y x y x <→<∀∀。
4. 指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。
(1) )),(),((a x P x y P x →∀(2) ),()(y x zQ x xP ∀→∀(3) )()())()((x Q x xP x R x P x ∧∀→∧∀(4) ))),(,()),,(((y x g z xP x y x f P y ∀→∀(5) )())()()((x R x xR x Q x P x ∧∃∧→∀解 (1) 变元 x 在)),(),((a x P x y P x →∀中三次出现都是约束出现，∀x 的唯一出现的辖域是 P (y , x ) → P (x , a )。
(2) 变元 x 在),()(y x zQ x xP ∀→∀中的头两次出现是约束出现，第三次出现是自由出现。
变元 y 在),()(y x zQ x xP ∀→∀中的唯一出现是自由出现。
变元 z 在),()(y x zQ x xP ∀→∀中的唯一出现是约束出现。
∀x 的唯一出现的辖域是 P (x )，∀z 的唯一出现的辖域是Q (x , y )。
(3) 变元 x 在)()())()((x Q x xP x R x P x ∧∀→∧∀中的头五次出现是约束出现，第六次出现是自由出现。
∀x 的第一次出现的辖域是P (x ) ∧ R (x )，第二次出现的辖域是P (x )。
(4) 变元 x 在))),(,()),,(((y x g z xP x y x f P y ∀→∀中的头两次出现是自由出现，后两次出现是约束出现。
∀x 的唯一出现的辖域是 P (z , g (x , y ))， ∀y 的唯一出现的辖域是 P (f (x , y ), x ) → ∀xP (z , g (x , y ))。
(5) 变元 x 在)())()()((x R x xR x Q x P x ∧∃∧→∀中的头五次出现是约束出现，第六次出现是自由出现。
∀x 的唯一出现的辖域是P (x ) → Q (x ) ∧ ∃xR (x )，∃x 的唯一出现的辖域是R (x )。
5. 归纳证明：若t ，t '是项，则x t t '也是项。
证明 ① 若t 是x ，则x t t '是t '，x t t '是项。
② 若t 是不同于x 的变元y ，则x t t '仍是y ，x t t '是项。
③ 若t 是常元a ，则x t t '仍是a ，x t t '是项。
④若t 是),,(1n t t f ，则x t t '是))(,,)((1x t n x t t t f '' ，由归纳假设知x t n x t t t '')(,,)(1 都是项，所以x t t '是项。
6. 归纳证明：若t 是项，A 是公式，则x t A 也是公式。
证明 ① 若A 是),,(1n t t P ，则x t A 是))(,,)((1x t n x t t t P ，由上题知x t n x t t t )(,,)(1 都是项，所以x t A 是公式。
② 若A 是B ⌝，则x t A 是x t B ⌝，由归纳假设知x t B 是公式，所以x t A 是公式。
③ 若A 是C B →，则x t A 是x t x t C B →，由归纳假设知x t B 和x t C 都是公式，所以x t A 是公式。
④ 若A 是xB ∀，则x t A 仍是A ，x t A 是公式。
⑤ 若A 是yB ∀，其中y 是不同于x 的变元，则x t A 是x t yB ∀，由归纳假设知x t B 是公式，所以x t A 是公式。
7. 给定解释I 和I 中赋值v 如下：}2,1{=I D ，1=I a ，2=I b ，2)1(=I f ，1)2(=I f1)2,1()1,1(==I I P P ，0)2,2()1,2(==I I P P ，1)(=x v ，1)(=y v计算下列公式在解释I 和赋值I 中v 下的真值。
(1) )),(())(,())(,(x y f P b f x P x f a P ∧∧(2) ),(x y yP x ∃∀(3) )))(),((),((y f x f P y x P y x →∀∀解 (1))))(),(())(,())(,((v x y f P b f x P x f a P I ∧∧))()),((())(),(()))((,(x v y v f P b f x v P x v f a P I I I I I I I I ∧∧=)1),1(())2(,1())1(,1(I I I I I I f P f P f P ∧∧=0011)1,2()1,1()2,1(=∧∧=∧∧=I I I P P P (2))))(,((v x y yP x I ∃∀])2/[))(,((])1/[))(,((x v x y yP I x v x y yP I ∃∧∃= ]))2/][1/[))(,((])1/][1/[))(,(((y x v x y P I y x v x y P I ∨=]))2/][2/[))(,((])1/][2/[))(,(((y x v x y P I y x v x y P I ∨∧))2,2()2,1(())1,2()1,1((I I I I P P P P ∨∧∨= 1)01()01(=∨∧∨=(3) )))))((),((),(((v y f x f P y x P y x I →∀∀)))2(,)1(()2,1(()))1(,)1(()1,1((I I I I I I I I f f P P f f P P →∧→=)))2(,)2(()2,2(()))1(,)2(()1,2((I I I I I I I I f f P P f f P P →∧→∧))1,1()2,2(())2,1()1,2(())1,2()2,1(())2,2()1,1((I I I I I I I I P P P P P P P P →∧→∧→∧→=01100)10()10()01()01(=∧∧∧=→∧→∧→∧→=7. 给定解释I 如下：},{b a D I =， 1),(),(==b b P a a P I I ， 0),(),(==a b P b a P I I判断I 是不是以下语句的模型。
