离散数学习题答案126789章1217.docx
《离散数学习题答案126789章1217.docx》由会员分享，可在线阅读，更多相关《离散数学习题答案126789章1217.docx（23页珍藏版）》请在冰点文库上搜索。
离散数学习题答案126789章1217
习题1：
1.解
（1）{2，3，5，7，11，13，17，19}
（2）{x|x=20*k,k是自然数}
（3）{2，-1}
2.解
（1）{2，4}
（2）{1，2，3，4，5}
（3）{1，3}
（4）{1，3，5}
3.解
（1）{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
（2）
（3）全体自然数
（4）{0，2，4，6，8，10，12，14，16，18，20}
（5）1，3，5，7，9，11，13，15，17，19}
4.解
（1）正确
（2）正确
（3）错误
（4）正确
5.解
（1）A={1}，B={{1}}，C={{1}}
（2）A={1}，B={{1}}，C={{{1}}}
6.解
（1）正确。
由子集的定义。
（2）不一定。
如：
A={1}，B={{1}}，C={{1}}。
（3）不一定。
如：
A={1}，B={1，2}，C={{1，2}}
（4）不一定。
如：
A={1}，B={1，2}，C={{1，2}}。
7.解A={1，2}，B={1}，C={2}，有
，但是
成立。
A={1，2}，B={1}，C={1}，有
，但是
成立。
8.解
（1）
（2）{}
（3）{{}}
（4）{，{}}
9.解
（1）{1,2,3,4,5,6,7,8,9}
（2）{0,1,2,3,4,5,6,7,8,9,10}
（3）{0,3,6,7,8,9}
10.解333
11.解25
12.解
（1）454
（2）124
（3）220
13.解
（1）{}
（2）{，{a}}
（3）{，{}，{a}，{,a}}
（4）{，{}，{{}}，{{},}}
（5）{，{{}}，{}，{a}，{{},}，{{},a}，{,a}，{{},,a}}
14.证明：
假设BC，则至少存在一元素xB且xC。
（1）若xA，因为xB，所以xAB；因为xC，所以xAC，则ABAC，与已知条件AB=AC矛盾。
（2）若xA，因为xB，所以xAB；因为xC，所以xAC，则ABAC，与已知条件AB=AC矛盾。
由
（1），
（2）可知，假设不成立，因此B=C成立。
15.证明：
（1）左边=（AB’）C’=AB’C’=A（B’C’）=A（BC）’=A-BC=右边.
（2）左边=（AB）C’=（AC’）（BC’）=（A-C）（B-C）
（3）左边=A（BC）’=AB’C’=（AB’）（AC’）=（A-B）（A-C）
16.证明：
（1）反证法，假设BC,则至少存在一元素xB且xC。
若xA，因为xB，所以xAB；因为xC，所以xAC，则ABAC，与已知条件AB=AC矛盾。
若xA，因为xB，所以xA’B；因为xC，所以xA’C，则A’BA’C，与已知条件A’B=A’C矛盾。
所以，假设不成立，因此B=C成立。
（2）因为AB=AC，AB=AC，所以AB-AB=AC-AC，即AB=AC，由第14题可得，B=C。
习题二：
1.原题改为：
设
，
，计算P（A）,P（B）,AB,P（A）P（B）。
解P（A）={,{1},{2},{1,2}};P（B）={,{a},{b},{a,b}};
AB={（1,a）,（1,b）,（2,a）,（2,b）};
P（A）P（B）={（,）,（,{a}）,（,{b}）,（,{a,b}）,（{1},）,（{1},{a}）,（{1},{b}）,（{1},{a,b}）,
（{2},）,（{2},{a}）,（{2},{b}）,（{2},{a,b}）,（{1,2},）,（{1,2},{a}）,（{1,2},{b}）,
（{1,2},{a,b}）}
2.略
3.解
（1）成立
（2）不一定成立。
反例：
A={1，2}，B={2}，C={a，b}，D={b}
（3）不一定成立。
反例：
A={1，2}，B={2}，C={a，b}，D={b}
（4）不一定成立。
反例：
A={1}，B={2}，C={a}，D={b}
4.解，{（1,3）},{（2,3）},{（1,3）,（2,3）}
5．解IA={（1,1）,（2,2）,（3,3）}UA={（1,1）,（1,2）,（1,3）,（2,1）,（2,2）,（2,3）,（3,1）,（3,2）,（3,3）}
6.解
（1）
（2）略
（3）domR={1,2,3};ranR={a,b,c}
7.解RS={（1,a）,（1,b）,（1,c）,（2,a）,（2,c）,（3,a）,（3,b）}
R∩S={（1,a）,（2,c）,（3,a）}
R-S={（1,b）}
R-1={（a,1）,（b,1）,（c,2）,（a,3）}
8.解R.S={（a,a）,（b,b）,（b,d）}
S.R={（a,a）,（a,b）,（b,a）,（b,b）,（c,c）}
R-1.S-1={（a,a）,（a,b）,（b,a）,（b,b）,（c,c）}
S-1.R-1={（a,a）,（b,b）,（d,b）}
9.解R={（a,a）,（b,b）,（c,c）}
10.解
（1）R={（a,a）,（b,b）,（c,c）,（a,b）,（b,a）,（b,c）}
（2）R={（a,b）,（b,a）}
（3）R={（a,b）}
11.解设集合A={1,2,3,4,5}
（1）正确。
（2）不成立。
反例：
R={（1,2）},S={（2,1）}
（3）不成立。
反例：
R={（1,2）,（2,1）},S={（2,3）,（3,2）}
（4）不成立。
反例：
R={（1,2）,（3,4）},S={（2,3）,（4,5）}
12.解r（R）={（a,b）,（b,a）,（b,c）,（c,d）,（a,a）,（b,b）,（c,c）,（d,d）}
s（R）={（a,b）,（b,a）,（b,c）,（c,b）,（c,d）,（d,c）}
t（R）={（a,a）,（a,b）,（a,c）,（a,d）,（b,a）,（b,b）,（b,c）,（b,d）,（c,d）}
13.证明：
直接利用闭包的构造式即可得证。
14.解等价关系是{（a,a）,（b,b）,（c,c）,（d,d）,（a,c）,（c,a）,（b,d）,（d,b）}
15.证明:
必要性：
R是一个等价关系，则当（a,b）R，（a,c）R必有（b,c）R。
因为R对称，所以当（a,b）R时，有（b,a）R，因为R传递，所以当（b,a）R，（a,c）R时有（b,c）R。
充分性：
R是A上的一个自反关系，当（a,b）R，（a,c）R必有（b,c）R，证明R是等价关系。
自反:
条件已知；
对称:
若（a,b）R,因为R自反,故（a,a）R,现在（a,b）R,（a,a）R,则根据条件（b,a）R；
传递:
若（a,b）R,（b,c）R
因为（a,b）R,（b,c）R,而R对称,所以（b,a）R,现在（b,a）R,（b,c）R,所以根据条件有（a,c）R
16.解15。
17.解A/R={{a,b},{c},{d}}。
18.解R={（a,a）,（b,b）,（c,c）,（d,d）,（b,c）,（c,b）}
19.解最大元是e，最小元是a，极大元是e，极小元是a。
20.解
21.是全序、良序。
习题六：
1.解
（1）不是命题
（2）是命题，（看具体日期确定）。
（3）是命题，（看具体情况）。
（4）若进行的布尔运算，则是真命题；若十进制运算则是假命题。
（5）不是命题。
（6）是真命题。
（7）是真命题。
（8）不是命题。
（9）是命题。
目前不能知道真值。
（10）是命题变元。
根据x，y的取值确定真值。
（11）不是命题。
2.解
（1）P：
付出劳动；Q：
有收获。
则命题符号化为：
PQ
（2）P：
今天下雨；Q：
我去看电影。
则命题符号化为：
PQ
（3）P：
a是奇数；Q：
b是奇数；R：
a与b的和是偶数。
则命题符号化为：
PQR
（4）P：
小明学习好；Q：
小明乐于助人。
则命题符号化为：
PQ
（5）P：
小明骑自行车；Q：
小明听音乐。
则命题符号化为：
PQ
（6）P：
今天是周二；Q：
我准备下周开会的材料。
则命题符号化为：
PQ
3.解
（1）pq
（2）pr
（3）prq
4.解
（1）可满足式
（2）可满足式
（3）可满足式
（4）可满足式
（5）重言式
5.证明
（1）左边PQPP（PQ）P（PQ）右边。
（2）左边（PQ）PQ右边。
（3）左边P（PQ）P（QP）P（QP）右边。
（4）右边（PR）（QR）PQR（PQ）R（PQ）R左边。
6.解此题答案不唯一。
（1）合取范式与析取范式都可以是PQ。
（2）原式是重言式。
合取范式与析取范式都可以是1。
（3）合取范式可以是（PQ）（PQ）
析取范式可以是（PQ）（PQ）
（4）原式是重言式。
合取范式与析取范式都可以是1。
7.解
（1）主析取范式：
（PQ）（PQ）
主合取范式：
（PQ）（PQ）
（2）主析取范式：
（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）
主合取范式：
空
（3）主析取范式：
（PQ）（PQ）
主合取范式：
（PQ）（PQ）
（4）主析取范式：
（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）
主合取范式：
PQR
8.证明
（1）利用真值表可知：
左边的主合取范式（PQRS）（PQRS）（PQRS）
右边的主合取范式（PQRS）（PQRS）（PQRS）
因此
（1）成立。
（2）利用真值表可知“
左边的主合取范式PQ
右边的主合取范式PQ
因此
（2）成立。
（3）利用真值表可知“
左边的主合取范式（PQR）（PQR）（PQR）
右边的主合取范式（PQR）（PQR）（PQR）
因此（3）成立。
9.证明
（1）（（PQ）（PR）（QS））（SR）
（（PQ）（PR）（QS））（SR）
（PQ）（PR）（QS）（SR）
（PR）QSSR
1
因此，原推理成立。
（2）（（PQ）（QR）R）P
（（PQ）（QR）R）P
（（PQ）（QR）R）P
（PQ）（QR）RP
（PQRP）（PRRP）（QQRP）（QRRP）
1111
1
因此，原推理成立。
10.证明
（1）①RP
②RSP
③S①,②,I
④SQP
⑤Q③,④,I
⑥PQP
⑦P⑤,⑥,I
（2）①CP
②（BA）CP
③BA①,②,I
④（AB）（CD）P
⑤（AB）（CD）④,E
⑥AB①,⑤,I
⑦AB③,⑥,I
11.证明
（1）①ABCP
②A①,I
③B①,I
④A（BC）P
⑤C②,③,④,I
⑥（CD）EP
⑦CDE⑥,E
⑧DE⑤,⑦,I
⑨DEHP
⑩H⑧,⑨,I
11）ABH①,⑩,CP
（2）①PCP
②QCP
③P（QR）P
④QR①,③,I
⑤R②,④,I
⑥R（QS）P
⑦QS⑤,⑥,I
⑧P（QS）①,⑦,CP
12.解：
P：
他是计算机系的本科生；Q：
他一定学过C语言R：
他学过Java语言；S：
他会编程序。
则原命题符号化为：
前提：
P（QR）；（QR）S。
结论：
PS
证明过程如下：
①PCP
②P（QR）P
③QR①,②,I
④（QR）SP
⑤S③,④,I
⑥PS①,⑤,CP
13.解：
P：
6是偶数；Q：
2整除7；R：
7是素数。
则原命题符号化为：
前提：
PQ；RQ；R。
结论：
P。
证明过程如下：
①RP
②RQP
③Q①,②,I
④PQP
⑤P③,④,I
习题七：
1.解
（1）G（x，y）：
x>y，N（x）：
x是自然数。
则原命题符号化为：
x（N（x）y（N（y）G（x,y）））
（2）M（x）：
x是人；N（x）：
x爱看科幻片。
则原命题符号化为：
x（M（x）N（x））
（3）M（x）：
x是人；N（x）：
x喜欢吃甜食
则原命题符号化为：
x（M（x）N（x））
（4）M（x）：
x是人；N（x）：
x是药品；P（x，y）：
x对y过敏。
则原命题符号化为：
x（M（x）x（N（x）P（x,y）））
（5）M（x）：
x是人；N（x）：
x来参加这次会议。
则原命题符号化为：
x（M（x）N（x））
（6）M（x）：
x是大学生；N（x）：
x热爱祖国。
批评；
则原命题符号化为：
x（M（x）N（x））
2.解
（1）xL（x,0）（x（L（0,x）y（L（y,x）G（x,y））））
（2）xy（G（x,y）L（x,y））
（3）x（yS（x,y,x）G（y,0））
3．解
（1）x（P（x）yQ（y））中的x，y均为约束变元，x的辖域为P（x）yQ（y），y的辖域为Q（y）；xR（x,y）中x为约束变元,y为自由变元，x的辖域为R（x,y）.
（2）xP（x）中的x为约束变元，x的辖域为P（x）；Q（x）中的x为自由变元。
（3）xy（（P（x）Q（x））R（x,y））中的x,y均为约束变元，其中x的辖域为y（（P（x）Q（x））R（x,y）），y的辖域为（P（x）Q（x）R（x,y）
（4）xy（P（x）Q（x,y））中的x,y均为约束变元，其中x的辖域为y（P（x）Q（x,y））,y的辖域为Q（x,y）；x（P（x）R（x,y））中的x为约束变元，y为自由变元，x的辖域为P（x）R（x,y）。
4.解
（1）xP（x）yQ（y）
（2）z（P（z）Q（z））R（x,y）
（3）xP（x）zy（Q（z）R（z,y））
5.解
（1）xP（x）Q（y）
（2）xP（x,z）y（Q（y）R（u,y））
（3）xP（x,u）（zQ（v,z）yR（v,y））
6.解
（1）P
（1）P
（2）Q
（1）Q
（2）
（2）（P
（1）P
（2））（Q
（1）Q
（2））
（3）（P
（1）P
（2））（Q
（1）Q
（2））
7.解
（1）1
（2）0
8．解
（1）xy（P（x）Q（x,y））
（2）xyz（（P（x,y）Q（y））R（x,y,z））
（3）xyuzv（P（x,y）Q（u,z）R（v））
（4）xzu（（P（x,y）G（z,y））H（u））
9.解
（1）前束合取范式：
xyz（（P（x）Q（x,y））（P（x）Q（x,z）））
前束析取范式：
xyz（（P（x）Q（x,z））（P（x）Q（x,y）））
（2）前束合取范式：
xyz（（P（x,y）R（u,y,z））（Q（y）R（u,y,z）））
前束析取范式：
xyz（（P（x,y）Q（y））R（u,y,z））
（3）前束合取范式：
xyuzv（（P（x,y）Q（u,z））（P（x,y）R（v）））
前束析取范式：
xyuzv（P（x,y）（Q（u,z）R（v）））
10.证明
（1）①xG（x）P
②xG（x）①,E
③G（a）②,ES
④x（G（x）Q（x））P
⑤G（a）Q（a）④,US
⑥Q（a）③,⑤,I
⑦xQ（x）⑥,EG
（2）①xP（x）P
②P（u）①,US
③x（P（x）（Q（y）R（x）））P
④P（u）（Q（y）R（u））③,US
⑤Q（y）R（u）②,④,I
⑥Q（y）⑤,I
⑦R（u）⑤,I
⑧P（u）R（u）②,⑦,I
⑨x（P（x）R（x））⑧,UG
⑩Q（y）x（P（x）R（x））⑥,⑨,I
11.证明①xF（x）P
②F（a）①,ES
③x（R（x）T（x））P
④R（b）T（b）③,ES
⑤R（b）④,I
⑥T（b）⑤,I
⑦z（（F（z）xyQ（x,y））y（R（x）T（y）））P
⑧（F（a）xyQ（x,y））（R（b）T（b））⑦,US
⑨（R（b）T（b））⑥,⑧,I
⑩xyQ（x,y）⑧,⑨,I
⑾yxQ（x,y）⑩,E
12.解前提：
x（H（x）（F（x）G（x）））；x（H（x）F（x））
结论：
x（H（x）G（x））
证明如下：
①x（H（x）F（x））P
②H（a）F（a）①,ES
③H（a）②,I
④F（a）②,I
⑤x（H（x）（F（x）G（x）））P
⑥H（a）（F（a）G（a））⑤,US
⑦F（a）G（a）③,⑥,I
⑧G（a）④,⑦,I
⑨H（a）G（a）③,⑧,I
⑩x（H（x）G（x））⑨,EG
13.解
（1）设个体域为人。
F（x）:
x喜欢玩电子游戏，M（x）:
x喜欢看电影，G（x）:
x喜欢逛街。
则原命题符号化为：
前提：
x（F（x）M（x））；x（M（x）G（x））；xG（x）
结论：
xF（x）
证明如下：
①xG（x）P
②G（a）①,ES
③x（F（x）M（x））P
④F（a）M（a）③，US
⑤x（M（x）G（x））P
⑥M（a）G（a）⑤,US
⑦M（a）②,⑥,I
⑧F（a）④,⑦,I
⑨xF（x）⑧,EG
（2）设个体域为人。
F（x）:
x是学术委员会成员，P（x）:
x是教授，B（x）:
x是博士生导师，C（x）:
x是院士。
则原命题符号化为：
前提：
x（F（x）（B（x）P（x）））；x（F（x）C（x））
结论：
x（F（x）B（x）C（x））
证明如下：
①x（F（x）C（x））P
②F（a）C（a）①,ES
③F（a）②,I
④C（a）②,I
⑤x（F（x）（B（x）P（x）））P
⑥F（a）（B（a）P（a））⑤,US
⑦B（a）P（a）③,⑥,I
⑧B（a）⑦,I
⑨F（a）B（a）C（a）③,⑧,④,I
⑩x（F（x）B（x）C（x））⑨,EG
习题八：
1.证明：
假设图有两个或更多个孤立点，那么这些孤立点便是具有相同的度的两个顶点，命题得证。
如果图正好有一个孤立点，那么对有n-1个顶点且没有孤立点的子图，则这n-1个顶点的度数应是1，2，…，n-1，而这不可能，因为这n-1个顶点是简单图，最大度不能大于等于n-1。
所以，必定有两个顶点的度数相同。
2.解
（1）可简单图化
（2）不可图化
（3）可简单图化
（4）可简单图化
（5）可简单图化
3.解4个顶点的完全图有6条边，只需取由6条边构成的任意一个子集加上4个顶点构成的简单图，即可形成G的所有生成子图。
其中互不同构子图有：
0条边的不同构子图：
1个
1条边的不同构子图：
1个
2条边的不同构子图：
2个
3条边的不同构子图：
3个
4条边的不同构子图：
2个
5条边的不同构子图：
1个
4.
解
（1）
（2）
（3）证明：
根据自补图的定义，该自补图应同构他的补图，则他们应该具有相同的边数，而他们的和在一定是偶数，即该补图对应的完全图的边数为偶数。
5.解（24-1*2-2*1-3*1-5*1）/4=3个4度顶点。
6.原题改为：
证明在简单无向图
中，从顶点
到顶点
，如果既有奇数长度的通路又有偶数长度的通路，则
中必有一条奇数长度的回路。
证明设从u到v长度为偶数的路径为ue1u1e2…e2kv，长度为奇数的路径为ue1’u1’
e2’…e2n+1’v。
因为G是无向图，所以ue1u1e2…e2kve2n+1’…e1’u就是一个长度为奇数的回路。
7.证明设图G中有n个顶点v1，v2，…，vn。
由于v1的度数大于等于2，所以v1一定与v2，…，vn中的某些点相邻。
假设v1和v2相邻，于是得到由2个点构成的基本通路v1v2；又由于v2的度数大于等于2，所以v2一定与v3，…，vn中的某一点相邻，不放设为v3，于是得到由3个点构成的基本通路v1v
升级会员 