!离散数学习题2010习题课1-4章含答案.

离散数学课后习题及答案离散数学是计算机科学与数学的重要基础课程之一，它涵盖了很多重要的概念和理论。

为了更好地掌握离散数学的知识，课后习题是必不可少的一部分。

本文将介绍一些常见的离散数学课后习题，并提供相应的答案，希望对读者有所帮助。

一、集合论1. 设A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。

答案：A∪B={1,2,3,4}，A∩B={2,3}2. 设A={1,2,3}，B={2,3,4}，C={3,4,5}，求(A∪B)∩C的结果。

答案：(A∪B)∩C={3,4}二、逻辑与命题1. 判断下列命题的真假：a) 若2+2=5，则地球是平的。

b) 若今天下雨，则我会带伞。

c) 若x>0，则x^2>0。

答案：a)假，b)真，c)真。

2. 用真值表验证下列命题的等价性：a) p∧(q∨r) ≡ (p∧q)∨(p∧r)b) p→q ≡ ¬p∨q答案：a)等价，b)等价。

三、关系与函数1. 给定关系R={(1,2),(2,3),(3,4)}，求R的逆关系R^-1。

答案：R^-1={(2,1),(3,2),(4,3)}2. 设函数f(x)=x^2，g(x)=2x+1，求复合函数f(g(x))的表达式。

答案：f(g(x))=(2x+1)^2=4x^2+4x+1四、图论1. 给定图G，其邻接矩阵为：0 1 11 0 11 1 0求图G的度数序列。

答案：度数序列为(2,2,2)2. 判断下列图是否为连通图：a) G1的邻接矩阵为：0 1 11 0 01 0 0b) G2的邻接矩阵为：0 1 01 0 10 1 0答案：a)不是连通图，b)是连通图。

五、组合数学1. 从10个不同的球中，任选3个，求共有多少种选法。

答案：C(10,3)=120种选法。

2. 求下列排列的循环节：a) (123)(45)(67)b) (12)(34)(56)(78)答案：a)循环节为(123)(45)(67)，b)循环节为(12)(34)(56)(78)。

离散数学课后答案(第1-2-4章)武汉大学出版社习题1.11、（1）否（2）否（3）是，真值为0（4）否（5）是，真值为12、（1）P：天下雨Q：我去教室┐P →Q（2）P：你去教室Q：我去图书馆P →Q （3）P，Q同（2）Q →P（4）P：2是质数Q：2是偶数P∧Q3、（1）0（2）0（3）14、（1）如果明天是晴天，那么我去教室或图书馆。

（2）如果我去教室，那么明天不是晴天，我也不去图书馆。

（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。

习题1.21、（1）是（2）是（3）否（4）是（5）是（6）否2、（1）(P →Q) →R，P →Q，R，P，Q （2）(┐P∨Q) ∨（R∧P），┐P ∨Q，R∧P，┐P，Q，R，P（3）((P →Q) ∧(Q →P)) ∨┐(P →Q))，(P →Q) ∧(Q →P)，┐(P →Q)，P →Q，(Q →P)，P →Q，P，Q，Q，P，P，Q3、（1）((P →Q) →(Q →P)) →(P →Q) （2）((P →Q) ∨((P →Q) →R))→((P →Q) ∧((P →Q) →R))（3）(Q →P∧┐P) →(P∧┐P →Q)4、(P →Q) ∨((P∧Q) ∨(┐P∧┐Q)) ∧(┐P∨Q)习题1.31、（1）I(P∨(Q∧R)) = I(P)∨(I(Q)∧I(R)) = 1∨(1∧0) = 1（2）I((P∧Q∧R)∨(┐(P∨Q)∧┐(R∨S))) = (1∧1∧0)∨(┐(1∨1)∧┐(0∨1)) = 0∨(0∧0) = 0 （3）I((P←→R)∧(┐Q→S)) = (1←→0)∧(┐1→1) = 0∧1 = 0（4）I((P∨(Q→R∧┐P))←→(Q∨┐S)) = (1∨(1→(0∧┐1)))←→(1∨┐1) = 1←→1 = 1（5）I(┐(P∧Q)∨┐R∨((Q←→┐P)→R∨┐S)) = ┐(1∧1)∨┐0∨((1←→┐1)→(0∨┐1)) = 0∨1∨1 = 12、（1）P Q P→Q Q∧(P→Q) Q∧(P→Q)→P0 0 1 0 10 1 1 1 01 0 0 0 11 1 1 1 1（2）P Q R Q∧R ┐(P∨(Q∧R)) P∨Q P∨R（2）原式<=> ┐T∨(┐(┐P∨Q)∨(┐┐Q∨┐P)) <=> (P∧┐Q)∨(Q∨┐P)<=> (P∧┐Q)∨┐(P∧┐Q) <=> T 原式为永真式（3）原式<=> ┐(P∧Q) ←→┐(P∧Q) <=> T 原式为永真式（4）原式<=> P∧(Q∨R) ←→P∧(Q∨R) <=> T 原式为永真式（5）原式<=> ┐(P∨┐Q)∨Q <=> (┐P∧Q)∨Q <=> Q 原式为可满足式（6）原式<=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> T 原式为永真式（7）原式<=> (┐P∨P∨Q)∧┐P <=> (T∨Q)∧┐P<=> T∧┐P <=> ┐P 原式为可满足式（8）原式<=> ┐((P∨Q) ∧(┐Q∨R))∨(┐P ∨R) <=> (P∧┐Q)∨(Q∧┐R)∨(┐P∨R)<=> ((P∧┐Q)∨┐P)∨((Q∧┐R)∨R)<=>(( P∨┐P)∧(┐Q∨┐P))∨(( Q∨R)∧(┐R ∨R))<=> (┐Q∧┐P)∨( Q∨R) <=> T 原式为永真式4、（1）左<=> ┐P∨┐Q∨P <=> ┐┐P∨(┐P ∨┐Q) <=> 右（2）左<=> ┐(┐P∨Q) <=> 右（3）左<=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> 右（4）左<=> ┐(P→Q)∨┐(Q→P) <=> (P∧┐Q)∨(Q∧┐P) <=> 中<=> ((P∧┐Q)∨Q)∧((P∧┐Q)∨┐P)<=> (P∨Q)∧(┐Q∨Q)∧(P∨┐P)∧(┐Q∨┐P)<=> (P∨Q)∧┐(P∧Q) <=> 右(5)左( P Q) ( R Q) (P Q) Q 右5.(1)左Q P Q 右(2)(P (Q R)) ((P Q) (P R))( P Q R) ( P Q) ( P R)(P Q R) (P Q) P R(P Q R) ((P P) ( Q P)) R(P Q R) ( Q P R)(P Q R) (P Q R)T故P (Q R) (P Q) (P R)(3).(P Q) (P P Q)( P Q) P (P Q)( P Q) ( P P) ( P Q)( P Q) ( P Q)T故P Q P P Q(4).((P Q) Q) P Q( ( P Q) Q) P Q(( P Q) Q) P Q( P Q) (Q Q) P Q(P Q) (P Q)T故(P Q) Q P Q(5).((P P) Q) ((P P) R) (Q R) (( T Q) ( T R)) Q R(Q R) Q RQ R Q RQ TT故((P P) Q) ((P P) R) Q R(6)左(Q F) (R F)( Q F) ( R F)Q RRR Q 右6.(1)原式( P Q R)(2)原式P Q P (P Q P)(3)原式P (Q R P) P Q R ( P Q R)7.(1)原式( P Q P)(2)原式( P Q R) P Q ( ( P Q R) P Q)(3)原式P Q (R P) (P Q (R P))8. (1) (P Q) (( P ( P Q)) R) P(2)(P Q R) ( P R)(3)(P F) (Q T)习题1.41.(1)原式( P Q) (( P Q) (Q P))( P Q) (Q P)(P Q) Q PQ P,既是析取范式又是合取范式(2)原式(( P Q) ( P Q)) ( ( P Q) ( P Q))(P Q) (P Q) 析取范式P (Q Q)合取范式(3)原式P Q S ( P Q)析取范式( P ( P Q)) Q SP Q S合取范式(4)原式P P Q Q R既是析取范式又是合取范式2.(1)原式P Q R为真的解释是：000，001，011，100，101，110，111故原式的主析取范式为:( P Q R) ( P Q R) ( P Q R) (P Q R) (P QR) (P Q R) (P Q R)(2)原式(P Q) R(P Q (R R)) ((P P) R)(P Q R) (P Q R) (P Q) ( P R)(P Q R) (P Q R) (P (Q Q) R) ( P (Q Q) R)(P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)(P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)为真的解释是101，100，111，011，001(3)原式( P (Q R)) (P ( Q R))(( P (Q R)) P) (( P (Q R)) ( Q R))( P P) (Q P R) ( P Q R) (Q R Q R)(P Q R) ( P Q R)为真的解释是：000,111(4)原式P P Q Q R P Q R为真的解释是：001，010，011，100，101，110，111故原式的主析取范式为：( P Q R) ( P Q R) ( P Q R) (P Q R) (P QR) (P Q R) (P Q R)3.(1)原式P Q P Q T主合取范式，无为假的解释。

P F F T T Q F T F T P↔Q T F F T
每当Ｐ和Ｑ的真值相同时，则（Ｐ↔Ｑ）的真值 为“Ｔ”，否则（Ｐ↔Ｑ）的真值为“Ｆ”。
（３）举例：
▪ 春天来了当且仅当燕子飞回来了。 ▪平面上二直线平行，当且仅当这二直线不相交。 ▪２＋２＝４当且仅当雪是白色的。 （两者没有关系，但是确实命题）
举例： （a）P：王华的成绩很好 Q：王华的品德很好。 则ＰΛＱ：王华的成绩很好并且品德很好。 （b P：我们去种树 Q：房间里有一台电视机 则ＰΛＱ：我们去种树与房间里有一台电视机。 (c) P：今天下大雨 Q：3+3=6 则ＰΛＱ：今天下大雨和3+3=6
３．析取词（或运算） （１）符号“∨” 设Ｐ、Ｑ为二个命题，则 （Ｐ∨Ｑ）称作Ｐ与Ｑ的“析取”，读作： “Ｐ或Ｑ”。
（a）P：我拿起一本书 Q：我一口气读完了这本书 P→Q：如果我拿起一本书，则我一口气读完了这本书。 （b）P：月亮出来了 Q：3×3=9 P→Q：如果月亮出来了，则 3×3=9。（善意推定）
５．双条件联结词（“等价”词、“同”联结词、 “等同”词） （１）符号“↔”设Ｐ、Ｑ为二个命题，则Ｐ↔ Ｑ读作：“Ｐ当且仅当Ｑ”，“Ｐ等价 Ｑ”,“Ｐ是Ｑ的充分必要条件”。 （２）定义（见真值表）：
（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、Ｑ 交换位置不会改变真值表中的值。
６．命题联结词在使用中的优先级 （１）先括号内，后括号外 （２）运算时联结词的优先次序为： ¬ Λ → ↔ （由高到低） （３）联结词按从左到右的次序进行运算
∨
¬Ｐ∨（Ｑ∨Ｒ）可省去括号，因为“Ｖ”运算是可结合的。 （ ¬Ｐ∨Ｑ）∨Ｒ可省去括号，因为符合上述规定 而Ｐ→（Ｑ→Ｒ）中的括号不能省去，因为“→”不满足结合律。

离散数学课后习题答案第四章离散数学课后习题答案第四章第⼗章部分课后习题参考答案4．判断下列集合对所给的⼆元运算是否封闭：（1）整数集合Z 和普通的减法运算。

封闭,不满⾜交换律和结合律，⽆零元和单位元（2）⾮零整数集合普通的除法运算。

不封闭（3）全体n n ?实矩阵集合（R ）和矩阵加法及乘法运算，其中n2。

封闭均满⾜交换律，结合律，乘法对加法满⾜分配律；加法单位元是零矩阵，⽆零元；乘法单位元是单位矩阵，零元是零矩阵；（4）全体n n ?实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。

不封闭（5）正实数集合和运算，其中运算定义为：不封闭因为 +?-=--?=R 1111111ο（6）n关于普通的加法和乘法运算。

封闭，均满⾜交换律，结合律，乘法对加法满⾜分配律加法单位元是0，⽆零元；乘法⽆单位元（1>n ），零元是0；1=n 单位元是1 （7）A = {},,,21n a a a Λ n运算定义如下：封闭不满⾜交换律，满⾜结合律，（8）S =关于普通的加法和乘法运算。

封闭均满⾜交换律，结合律，乘法对加法满⾜分配律（9）S = {0,1},S 是关于普通的加法和乘法运算。

加法不封闭，乘法封闭；乘法满⾜交换律，结合律（10）S = ,S 关于普通的加法和乘法运算。

加法不封闭，乘法封闭，乘法满⾜交换律，结合律10．令S={a ，b}，S 上有四个运算：*，分别有表10.8确定。

(a) (b) (c) (d)(1)这4个运算中哪些运算满⾜交换律，结合律，幂等律？(a) 交换律，结合律，幂等律都满⾜，零元为a,没有单位元； (b)满⾜交换律和结合律，不满⾜幂等律，单位元为a,没有零元b b a a ==--11,(c)满⾜交换律,不满⾜幂等律,不满⾜结合律 a b a b b a b a a b b a ====οοοοοο)(,)(b b a b b a οοοο)()(≠ 没有单位元, 没有零元(d) 不满⾜交换律，满⾜结合律和幂等律没有单位元, 没有零元 (1) 求每个运算的单位元，零元以及每⼀个可逆元素的逆元。