离散数学第二版课后答案.docx
《离散数学第二版课后答案.docx》由会员分享，可在线阅读，更多相关《离散数学第二版课后答案.docx（20页珍藏版）》请在冰点文库上搜索。
离散数学第二版课后答案
离散数学第二版课后答案
【篇一：
离散数学答案屈婉玲版第二版高等教育出版社课后答案】
>第二版高等教育出版社课后答案
第一章部分课后习题参考答案
16设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨（q∧r）?
0∨（0∧1）?
0
（2）（p?
r）∧（﹁q∨s）?
（0?
1）∧（1∨1）?
0∧1?
0.
（3）（?
p∧?
q∧r）?
（p∧q∧﹁r）?
（1∧1∧1）?
（0∧0∧0）?
0
（4）（?
r∧s）→（p∧?
q）?
（0∧1）→（1∧0）?
0→0?
1
17．判断下面一段论述是否为真：
“?
是无理数。
并且，如果3是无理数，则2也是无理数。
另外6能被2整除，6才能被4整除。
”
答：
p:
?
是无理数1
q:
3是无理数0
r:
2是无理数1
s:
6能被2整除1
t:
6能被4整除0
命题符号化为：
p∧（q→r）∧（t→s）的真值为1，所以这一段的论述为真。
19．用真值表判断下列公式的类型：
（4）（p→q）→（?
q→?
p）
（5）（p∧r）?
（?
p∧?
q）
（6）（（p→q）∧（q→r））→（p→r）
答：
（4）
pqp→q?
q?
p?
q→?
p（p→q）→（?
q→?
p）0011111011011110010011110011所以公式类型为永真式
（5）公式类型为可满足式（方法如上例）
（6）公式类型为永真式（方法如上例）
第二章部分课后习题参考答案
3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
（1）?
（p∧q→q）
（2）（p→（p∨q））∨（p→r）
（3）（p∨q）→（p∧r）
答：
（2）（p→（p∨q））∨（p→r）?
（?
p∨（p∨q））∨（?
p∨r）?
?
p∨p∨q∨r?
1所以公式类型为永真式
（3）pqrp∨qp∧r（p∨q）→（p∧r）
000001
001001
010100
011100
100100
101111
110100
111111
所以公式类型为可满足式
4.用等值演算法证明下面等值式：
（2）（p→q）∧（p→r）?
（p→（q∧r））
（4）（p∧?
q）∨（?
p∧q）?
（p∨q）∧?
（p∧q）
证明
（2）（p→q）∧（p→r）
?
（?
p∨q）∧（?
p∨r）
?
?
p∨（q∧r））
?
p→（q∧r）
（4）（p∧?
q）∨（?
p∧q）?
（p∨（?
p∧q））∧（?
q∨（?
p∧q）
?
（p∨?
p）∧（p∨q）∧（?
q∨?
p）∧（?
q∨q）
?
1∧（p∨q）∧?
（p∧q）∧1
?
（p∨q）∧?
（p∧q）
5.求下列公式的主析取范式与主合取范式，并求成真赋值
（1）（?
p→q）→（?
q∨p）
（2）?
（p→q）∧q∧r
（3）（p∨（q∧r））→（p∨q∨r）
解：
（1）主析取范式
（?
p→q）→（?
q?
p）
?
?
（p?
q）?
（?
q?
p）
?
（?
p?
?
q）?
（?
q?
p）
?
（?
p?
?
q）?
（?
q?
p）?
（?
q?
?
p）?
（p?
q）?
（p?
?
q）
?
（?
p?
?
q）?
（p?
?
q）?
（p?
q）
?
m0?
m2?
m3
?
∑（0,2,3）
主合取范式：
（?
p→q）→（?
q?
p）
?
?
（p?
q）?
（?
q?
p）
?
（?
p?
?
q）?
（?
q?
p）
?
（?
p?
（?
q?
p））?
（?
q?
（?
q?
p））
?
1?
（p?
?
q）
?
（p?
?
q）?
m1
?
∏
（1）
（2）主合取范式为：
?
（p→q）?
q?
r?
?
（?
p?
q）?
q?
r
?
（p?
?
q）?
q?
r?
0
所以该式为矛盾式.
主合取范式为∏（0,1,2,3,4,5,6,7）
矛盾式的主析取范式为0
（3）主合取范式为：
（p?
（q?
r））→（p?
q?
r）
?
?
（p?
（q?
r））→（p?
q?
r）
?
（?
p?
（?
q?
?
r））?
（p?
q?
r）
?
（?
p?
（p?
q?
r））?
（（?
q?
?
r））?
（p?
q?
r））
?
1?
1
?
1
所以该式为永真式.
永真式的主合取范式为1
主析取范式为∑（0,1,2,3,4,5,6,7）
第三章部分课后习题参考答案
14.在自然推理系统p中构造下面推理的证明：
（2）前提：
p?
q,?
（q?
r）,r
结论：
?
p
（4）前提：
q?
p,q?
s,s?
t,t?
r
结论：
p?
q
证明：
（2）
①?
（q?
r）前提引入
②?
q?
?
r①置换
③q?
?
r②蕴含等值式
④r前提引入
⑤?
q③④拒取式
⑥p?
q前提引入
⑦￢p（3）⑤⑥拒取式
证明（4）：
①t?
r前提引入
②t①化简律
③q?
s前提引入
④s?
t前提引入
⑤q?
t③④等价三段论
⑥（q?
t）?
（t?
q）⑤置换
⑦（q?
t）⑥化简
⑧q②⑥假言推理
⑨q?
p前提引入
⑩p⑧⑨假言推理
（11）p?
q⑧⑩合取
15在自然推理系统p中用附加前提法证明下面各推理：
（1）前提：
p?
（q?
r）,s?
p,q
结论：
s?
r
证明
①s附加前提引入
②s?
p前提引入
③p①②假言推理
④p?
（q?
r）前提引入
⑤q?
r③④假言推理
⑥q前提引入
⑦r⑤⑥假言推理
16在自然推理系统p中用归谬法证明下面各推理：
（1）前提：
p?
?
q,?
r?
q,r?
?
s
结论：
?
p
证明：
①p结论的否定引入
②p?
﹁q前提引入
③﹁q①②假言推理
④￢r?
q前提引入
⑤￢r④化简律
⑥r?
￢s前提引入
⑦r⑥化简律
⑧r?
﹁r⑤⑦合取
由于最后一步r?
﹁r是矛盾式,所以推理正确.
第四章部分课后习题参考答案
3.在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为（a）,（b）条件时命
【篇二：
离散数学课后答案（第1,2,4章）武汉大学出版社】
）否
（2）否
（3）是，真值为0
（4）否
（5）是，真值为1
2、
（1）p：
天下雨q：
我去教室┐p→q
（2）p：
你去教室q：
我去图书馆p→q
（3）p，q同
（2）q→p
（4）p：
2是质数q：
2是偶数p∧q
3、
（1）0
（2）0
（3）1
4、
（1）如果明天是晴天，那么我去教室或图书馆。
（2）如果我去教室，那么明天不是晴天，我也不去图书馆。
（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。
习题1.2
1、
（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，q
3、
（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.3
1、
（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=1
2、
（1）
pqp→qq∧（p→q）q∧（p→q）→p
00101
01110
10001
11111
（2）
pqrq∧r┐（p∨（q∧r））p∨qp∨r（p∨q）∧（p∨r）原式000010000
001010100
010011000
011101110
100001110
101001110
110001110
111101110
（3）
pqrp∨qq∧pp∨q→q∧pp∧┐r原式
00000100
00100100
01010001
01110001
10010011
10110001
11011111
11111100
3、
（1）原式=f→q=t原式为永真式
（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）左（pq）（rq）（pq）q右
5.
（1）左qpq右
（2）（p（qr））（（pq）（pr））
（pqr）（pq）（pr）
（pqr）（pq）pr
（pqr）（（pp）（qp））r
（pqr）（qpr）
（pqr）（pqr）
t
故p（qr）（pq）（pr）
（3）.（pq）（ppq）
（pq）p（pq）
（pq）（pp）（pq）
（pq）（pq）
t
故pqppq
（4）.（（pq）q）pq
（（pq）q）pq
（（pq）q）pq
（pq）（qq）pq
（pq）（pq）
t
故（pq）qpq
（5）.（（pp）q）（（pp）r）（qr）
（（tq）（tr））qr
（qr）qr
qrqr
qt
t
故（（pp）q）（（pp）r）qr
（6）左（qf）（rf）
（qf）（rf）
qr
r
rq右
6.
（1）原式（pqr）
（2）原式pqp（pqp）
（3）原式p（qrp）pqr（pqr）
7.
（1）原式（pqp）
（2）原式（pqr）pq（（pqr）pq）
（3）原式pq（rp）（pq（rp））
8.
（1）（pq）（（p（pq））r）p
（2）（pqr）（pr）
（3）（pf）（qt）
习题1.4
1.
（1）原式（pq）（（pq）（qp））
（pq）（qp）
（pq）qp
qp,既是析取范式又是合取范式
（2）原式（（pq）（pq））（（pq）（pq））
（pq）（pq）析取范式
p（qq）合取范式
（3）原式pqs（pq）析取范式
（p（pq））qs
pqs合取范式
（4）原式ppqqr既是析取范式又是合取范式
2.
（1）原式pqr为真的解释是：
000，001，011，100，101，110，111
故原式的主析取范式为:
（pqr）（pqr）（pqr）（pqr）（pqr）（pqr）（pqr）
（2）原式（pq）r
（pq（rr））（（pp）r）
（pqr）（pqr）（pq）（pr）
（pqr）（pqr）（p（qq）r）（p（qq）r）
（pqr）（pqr）（pqr）（pqr）（pqr）（pqr）
（pqr）（pqr）（pqr）（pqr）（pqr）为真的解释是101，100，111，011，001
（3）原式（p（qr））（p（qr））
（（p（qr））p）（（p（qr））（qr））
（pp）（qpr）（pqr）（qrqr）
（pqr）（pqr）
为真的解释是：
000,111
（4）原式ppqqrpqr为真的解释是：
001，010，011，100，101，110，111
故原式的主析取范式为：
（pqr）（pqr）（pqr）（pqr）（pqr）（
pqr）（pqr）
3.
（1）原式pqpqt主合取范式，无为假的解释。
（2）原式（pqr）（pqr）（pqr）（pqr）
为真的解释为：
111，011，001，000，故为假的解释为：
010，100，101，110
原式的主合取范式为：
（pqr）（pqr）（pqr）（pqr）
（3）由2.
（2）知，原式为真的解释是：
101，100，111，011，001，故为假的解释是：
000，010，110.
故原式的主合取范式为：
（pqr）（pqr）（pqr）
（4）由2.（4）知，原式为假的解释是：
000，故原式的主合取范式为：
pq
r
4.
（1）左式（pq）（pr）
（pq（rr））（p（qq）r）
（pqr）（pqr）（pqr）
右式p（qr）（pq）（pr）
（pqr）（pqr）（pqr）
故原式成立。
（2）左式（p∧┐q）∨（p∧q），
右式（p∨p）∧（┐q∨p）p∧（p∨┐q）p（p∧┐q）∨（p∧q），
故原式成立
（3）左式（p∧q）∧┐（p∧q）f，主析取范式
右式┐（p∨q）∧（p∨q）f，
故原式成立
（4）左式t∨（p∧q）t，主合取范式
右式┐（p∧q）∨（p∧q）t，
故原式成立
习题1.5
1.
（1）①p∧q前提
②p①，化简
③p→（q→r）前提
④q→r②，③，mp
⑤q①，化简
⑥r④，⑤，mp
【篇三：
离散数学课后习题答案二】
列出关系{?
a，b，c，d?
|a，b，c，d?
z且a?
b?
c?
d?
6}中所有有序4元解{?
a，b，c，d?
|a，b，c，d?
z且a?
b?
c?
d?
6}
?
?
组。
?
{?
1,1,1,6?
?
1,1,6,1?
?
1,6,1,1?
?
6,1,1,1?
?
1,1,2,3?
?
1,1,3,2?
?
1,2,1,3?
?
1,3,1,2?
?
1,2,3,1?
?
1,3,2,1?
?
2,3,1,1?
?
3,2,1,1?
?
2,1,3,1?
?
3,1,2,1?
?
2,1,1,3?
?
3,1,1,2?
2.列出二维表3.18所表示的多元关系中所有5元组。
假设不增加新的5元组，找出二维表3.18所有的主键码。
表3.18航班信息
解略
3.当施用投影运算?
2,3,5到有序5元组?
a，b，c，d?
时你能得到什么？
解略
4.哪个投影运算用于除去一个6元组的第一、第二和第四个分量？
解略
5.给出分别施用投影运算?
1,2,4和选择运算?
航空公司＝nadir到二维表3.18以后得到的表。
解?
2,3,5
对航班信息二维表进行选择运算?
航空公司＝nadir后得到的二维表
6.把连接运算j3用到5元组二维表和8元组二维表后所得二维表中有序多元组有多少个分量？
解略
7.构造把连接运算j2用到二维表3.19和二维表3.20所得到的二维表。
解零件供应商二维表与零件数量和颜色代码二维表连接运算2结果
第4章：
群、环、域
习题4.1
1.判断下列集合对所给的二元运算是否封闭。
（1）集合nz?
{n?
z|z?
z}关于普通加法和普通乘法运算，其中n是正整数。
，n?
z}关于普通加法和普通乘法运算。
（2）集合s?
{x|x?
2n?
1
1}关于普通加法和普通乘法运算。
（3）集合s?
{0，
n?
s?
{x|x?
2，n?
z}关于普通加法和普通乘法运算。
（4）集合
?
（5）n阶（n?
2）实可逆矩阵集合mn（r）关于矩阵加法和矩阵乘法运算。
?
对于封闭的二元运算，判断它们是否满足交换律、结合律和分配律，并在存在的情况下求出它们的单位元、零元和所有可逆元素的逆元。
解略
2.判断下列集合对所给的二元运算是否封闭。
（1）正实数集合r和*运算，其中*运算定义为：
?
?
a，b?
r?
，a?
b?
a?
b?
a?
b
?
，an}，n?
2。
*运算定义为：
（2）a?
{a1，a2，
?
a，b?
a，a?
b?
b
对于封闭的二元运算，判断它们是否满足交换律、结合律和等幂律，并在存在的情况下求出它们的单位元、零元和所有可逆元素的逆元。
解
（1）不封闭，例如：
0.5?
0.5?
0.5?
0.5?
0.5?
0.5?
?
0.75?
r
（2）封闭。
不满足交换律：
?
a,b?
a，a?
b?
b?
a?
b?
aa?
b?
bb?
a?
a满足结合律：
?
a,b?
a（a?
b）?
c?
b?
c?
c，a?
（b?
c）?
a?
c?
c满足等幂律：
?
a?
aa?
a?
a
?
a1，a2，?
，an都是左单位元，但无右单位元。
a1，a2，?
，an都是右零元，但无左零元。
因为无单位元，所以无逆元。
3.设s?
q?
q，这里q是有理数集合，*为s上的二元运算，
?
?
u，v?
，?
x，y?
?
s，
?
u，v?
?
?
x，y?
＝?
ux，uy?
v?
（1）*运算在s上是否可交换、可结合？
是否为等幂的？
（2）*运算是否有单位元、零元？
如果有，请指出，并求s中所有可逆元素的逆元。
（3）*运算在s上是否满足消去律？
解略
?
，f6。
?
x，y?
r有4.r为实数集合，定义以下六个函数f1，
f1（?
x，y?
）?
x?
yf3（?
x，y?
）?
|x?
y|
f2（?
x，y?
）?
x?
yf4（?
x，y?
）?
xyf6（?
x，y?
）?
max（x，y）
f5（?
x，y?
）?
min（x，y）
（1）指出哪些函数是r上的二元运算。
（2）若是r上的二元运算，说明是否是可交换的、可结合的、等幂的？
（3）若是r上的二元运算，在存在的情况下求出单位元、零元以及每个可逆元素的逆元。
（4）若是r上的二元运算，说明是否满足消去律。
解略
，2，?
，10}，问下面定义的运算*在g上是否封闭？
对于封闭的二元运5.设g?
{1
算，请说明运算是否满足交换律、结合律，并并在存在的情况下求出运算的单位元、零元和所有可逆元素的逆元。
（1）x?
y?
gcd（x，y），gcd（x，y）表示x与y的最大公因数。
（2）x?
y?
lcm（x，y），lcm（x，y）表示x与y的最小公倍数。
（3）x?
y?
大于等于x和y的最小整数。
（4）x?
y?
质数p的个数，其中x?
p?
y。
解
（1）封闭。
满足交换律，满足结合律，满足等幂律。
无单位元，1是零元。
因为无单位元，所以无逆元。
5）?
15?
g
（2）不封闭，例如：
3?
5?
lcm（3，
（3）封闭。
满足交换律，满足结合律，满足等幂律。
1是单位元，10是零元。
1的逆元为1，其他无逆元。
（4）封闭。
不满足交换律，不满足结合律，不满足等幂律。
无单位元，无零元。
因为无单位元，所以无逆元
4.2半群与群
习题4.2
1.设g是所有形如
a12?
?
0?
?
?
?
是半群吗？
是有么半群吗？
这里的矩阵组成的集合，*表示矩阵乘法。
试问?
g，
?
a11
?
?
0?
a11、a12是实数。
?
a11a12?
?
b11b12?
?
?
?
?
0?
?
00?
?
0g?
?
?
?
、a?
b?
解任取中的2个元素、
?
a11a12?
?
b11b12?
?
a11b11a11b12?
?
?
?
?
?
?
?
0?
?
?
?
0?
?
?
00?
＝?
00?
?
?
ga?
b?
?
∵
?
g，?
?
是一个代数系统。
?
?
是∴且因为矩阵的乘法满足结合律，所以?
g，
半群。
又因为，只要a11＝1，则
?
a11
?
?
a?
b?
?
0a12?
?
b11b12?
?
a11b11
?
?
?
00?
?
?
?
0?
?
*?
?
＝?
0a11b12?
?
b11b12?
?
?
?
00?
?
0?
?
＝?
?
?
b
?
1a12?
?
?
00?
?
?
是左单位元（不论a12取什么值）对任何的b?
g成立，即?
。
但右单位元不存在，
因为不论b11，b12取什么值，
?
a11a12?
?
b11b12?
?
a11b11?
?
?
?
?
?
0?
?
?
0?
?
?
00?
＝?
?
0a?
b?
?
不可能对任何的a?
g成立。
?
?
不是有么半群。
所以?
g，
2.在正实数集合r上定义运算*如下
?
a11b12?
?
a1
升级会员 