离散数学(第二版)最全课后习题答案详解.pdf
《离散数学(第二版)最全课后习题答案详解.pdf》由会员分享，可在线阅读，更多相关《离散数学(第二版)最全课后习题答案详解.pdf（59页珍藏版）》请在冰点文库上搜索。
习题一1.下列句子中,哪些是命题？
在是命题的句子中,哪些是简单命题？
哪些是真命题？
哪些命题的真值现在还不知道？
（1）中国有四大发明.答：
此命题是简单命题，其真值为1.
（2）5是无理数.答：
此命题是简单命题，其真值为1.（3）3是素数或4是素数.答：
是命题，但不是简单命题，其真值为1.（4）2x+35答：
不是命题.（5）你去图书馆吗？
答：
不是命题.（6）2与3是偶数.答：
是命题，但不是简单命题，其真值为0.（7）刘红与魏新是同学.答：
此命题是简单命题，其真值还不知道.（8）这朵玫瑰花多美丽呀！
答：
不是命题.（9）吸烟请到吸烟室去！
答：
不是命题.（10）圆的面积等于半径的平方乘以.答：
此命题是简单命题，其真值为1.（11）只有6是偶数，3才能是2的倍数.答：
是命题，但不是简单命题，其真值为0.（12）8是偶数的充分必要条件是8能被3整除.答：
是命题，但不是简单命题，其真值为0.（13）2008年元旦下大雪.答：
此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解:
（1）p：
中国有四大发明.
（2）p:
是无理数.（7）p:
刘红与魏新是同学.（10）p:
圆的面积等于半径的平方乘以.（13）p:
2008年元旦下大雪.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.
（1）5是有理数.答：
否定式：
5是无理数.p：
5是有理数.q：
5是无理数.其否定式q的真值为1.
（2）25不是无理数.答：
否定式：
25是有理数.p：
25不是无理数.q：
25是有理数.其否定式q的真值为1.（3）2.5是自然数.答：
否定式：
2.5不是自然数.p：
2.5是自然数.q：
2.5不是自然数.其否定式q的真值为1.（4）ln1是整数.答：
否定式：
ln1不是整数.p：
ln1是整数.q：
ln1不是整数.其否定式q的真值为1.4.将下列命题符号化，并指出真值.
（1）2与5都是素数答：
p：
2是素数，q：
5是素数，符号化为pq，其真值为1.
（2）不但是无理数，而且自然对数的底e也是无理数.答：
p：
是无理数，q：
自然对数的底e是无理数，符号化为pq，其真值为1.（3）虽然2是最小的素数，但2不是最小的自然数.答：
p：
2是最小的素数，q：
2是最小的自然数，符号化为pq，其真值为1.（4）3是偶素数.答：
p：
3是素数，q：
3是偶数，符号化为pq，其真值为0.（5）4既不是素数，也不是偶数.答：
p：
4是素数，q：
4是偶数，符号化为pq，其真值为0.5.将下列命题符号化，并指出真值.
（1）2或3是偶数.
（2）2或4是偶数.（3）3或5是偶数.（4）3不是偶数或4不是偶数.（5）3不是素数或4不是偶数.答:
p：
2是偶数，q：
3是偶数，r:
3是素数，s:
4是偶数,t:
5是偶数
（1）符号化:
pq，其真值为1.
（2）符号化：
pr，其真值为1.（3）符号化：
rt，其真值为0.（4）符号化：
qs，其真值为1.（5）符号化：
rs，其真值为0.6.将下列命题符号化.
（1）小丽只能从筐里拿一个苹果或一个梨.答：
p：
小丽从筐里拿一个苹果，q：
小丽从筐里拿一个梨，符号化为:
pq.
（2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：
p：
刘晓月选学英语，q：
刘晓月选学日语，符号化为:
（pq）（pq）.7.设p：
王冬生于1971年，q：
王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化答:
列出两种符号化的真值表：
pq0000011110111101根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式.8.将下列命题符号化,并指出真值.
（1）只要；
（2）如果；（3）只有；（4）除非；（5）除非；（6）.答:
设p:
.符号化真值
（1）1
（2）1（3）0（4）0（5）0,则:
;设q:
则:
仅当,否则,才有,才有,则,就有（6）19.设p：
俄罗斯位于南半球,q：
亚洲人口最多,将下面命题用自然语言表述,并指出其真值：
（1）；
（2）；（3）；（4）；（5）；（6）；（7）.答:
根据题意,p为假命题,q为真命题.自然语言真值
（1）只要俄罗斯位于南半球,亚洲人口就最多1
（2）只要亚洲人口最多,俄罗斯就位于南半球0（3）只要俄罗斯不位于南半球,亚洲人口就最多1（4）只要俄罗斯位于南半球，亚洲人口就不是最多1（5）只要亚洲人口不是最多，俄罗斯就位于南半球1（6）只要俄罗斯不位于南半球，亚洲人口就不是最多0（7）只要亚洲人口不是最多，俄罗斯就不位于南半球110设p：
9是3的倍数,q：
英国与土耳其相邻,将下面命题用自然语言表述,并指出真值：
（1）；
（2）；（3）；（4）.答:
根据题意,p为真命题,q为假命题.自然语言真值
（1）9是3的倍数当且仅当英语与土耳其相邻0
（2）9是3的倍数当且仅当英语与土耳其不相邻1（3）9不是3的倍数当且仅当英语与土耳其相邻1（4）9不是3的倍数当且仅当英语与土耳其不相邻011将下列命题符号化,并给出各命题的真值：
（1）若2+2=4,则地球是静止不动的；
（2）若2+2=4,则地球是运动不止的；（3）若地球上没有树木,则人类不能生存；（4）若地球上没有水,则是无理数.答:
命题1命题2符号化真值
（1）p:
2+2=4q:
地球是静止不动的0
（2）p:
2+2=4q:
地球是静止不动的1（3）p:
地球上有树木q:
人类能生存1（4）p:
地球上有树木q:
人类能生存112.将下列命题符号化,并给出各命题的真值：
（1）2+2=4当且仅当3+3=6；
（2）2+2=4的充要条件是3+36；（3）2+24与3+3=6互为充要条件；（4）若2+24,则3+36,反之亦然.答:
设p:
2+2=4,q:
3+3=6.符号化真值
（1）1
（2）0（3）0（4）113.将下列命题符号化,并讨论各命题的真值：
（1）若今天是星期一,则明天是星期二；
（2）只有今天是星期一,明天才是星期二；（3）今天是星期一当且仅当明天是星期二；（4）若今天是星期一,则明天是星期三.答:
设p:
今天是星期一,q:
明天是星期二,r:
明天是星期三.符号化真值讨论
（1）不会出现前句为真,后句为假的情况
（2）不会出现前句为真,后句为假的情况（3）必然为1（4）若p为真,则真值为0;若p为假,则真值为114.将下列命题符号化：
（1）刘晓月跑得快,跳得高；
（2）老王是山东人或者河北人；（3）因为天气冷,所以我穿了羽绒服；（4）王欢与李乐组成一个小组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他一面吃饭,一面听音乐；（8）如果天下大雨,他就乘班车上班；（9）只有天下大雨,他才乘班车上班；（10）除非天下大雨,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2与4都是素数,这是不对的；（13）“2或4是素数,这是不对的”是不对的.答:
命题1命题2命题3符号化
（1）p:
刘晓月跑得快q:
刘晓月跳得高-
（2）p:
老王是山东人q:
老王是河北人-（3）p:
天气冷q:
我穿羽绒服-（4）p:
王欢与李乐组成一个小组-p:
王欢与李乐组成一个小组（5）p:
李辛与李末是兄弟-p:
李辛与李末是兄弟（6）p:
王强学过法语q:
刘威学过法语-（7）p:
他吃饭q:
他听音乐-（8）p:
天下大雨q:
他乘车上班-（9）p:
天下大雨q:
他乘车上班-（10）p:
天下大雨q:
他乘车上班-（11）p:
下雪q:
路滑r:
他迟到了（12）p:
2是素数q:
4是素数-（13）p:
2是素数q:
4是素数-15.设p：
2+3=5.q：
大熊猫产在中国.r:
太阳从西方升起.求下列符合命题的真值：
（1）
（2）（3）（4）解：
p真值为1，q真值为1，r真值为0.
（1）0，
（2）0，（3）0，（4）116.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值：
（1）
（2）（3）（4）解：
（1）0，
（2）0，（3）0，（4）117.判断下面一段论述是否为真：
“是无理数.并且,如果3是无理数,则也是无理数.另外,只有6能被2整除,6才能被4整除.”是无理数s:
6能被2整除t：
6能被4整除符号化为:
，该式为重言式，所以论述为真。
18.在什么情况下,下面一段论述是真的:
“说小王不会唱歌或小李不会跳舞是正确的,而说如果小王会唱歌,小李就会跳舞是不正确的.”解：
p:
小王会唱歌。
q:
小李会跳舞。
真值为1.真值为0.可得，p真值为1，q真值为0.所以，小王会唱歌，小李不会跳舞。
19.用真值表判断下列公式的类型:
（1）
（2）p（3）（4）（5）（6）（7）.解：
（1）pqr00010011010101111001解：
p:
是无理数q:
3是无理数r:
101111011111此式为重言式
（2）pq（p001010101111此式为可满足式（3）qr000010100110此式为矛盾式（4）pq001011101111此式为重言式（5）pqr00000010010101111001101011011110此式为可满足式（6）pqr00010011010101111001101111011111此式为重言式（7）pqrs00001000100010000111010010101001100011111000010010101011011111001110101110011111此式为可满足式20.求下列公式的成真赋值：
（1）
（2）（3）（4）解：
pq000110011011101111111101由真值表得：
（1）的成真赋值是01，10,11
（2）的成真赋值是00，10,11（3）的成真赋值是00，01,10（4）的成真赋值是01，10,1121.求下列各公式的成假赋值：
（1）
（2）（3）解：
pqr000111001111010101011011100110101110110101111111由真值表得：
（1）的成假赋值是011
（2）的成假赋值是010,110（3）的成假赋值是100,10122.已知公式是矛盾式，求公式成真和成假赋值.解：
是矛盾式也是矛盾式。
由此可得：
该式无成真赋值。
而成假赋值为：
000,001,010,011,100,101,110,11123.已知公式是重言式,求公式的成真和成假赋值.解：
是重言式，也是重言式。
由此可得：
该式无成假赋值。
而成真赋值为：
000,001,010,011,100,101,110,11124.已知是重言式，试判断公式及的类型.解：
是重言式，而要使该式为重言式，其成真赋值只有11，都是重言式。
25.已知是矛盾式，试判断公式及的类型.解：
是矛盾式，而要使该式为矛盾式，其成假赋值只有00，都是重言式。
26.已知是重言式，是矛盾式，试判断的类型.解：
是矛盾式。
是重言式。
27.设A、B都是含命题变量项p1,p2,pn的公式,证明:
是重言式当且仅当A和B都是重言式.及解：
AB000010100111由真值表可得，当且仅当A和B都是重言式时，是重言式。
28.设A、B都是含命题变量项p1,p2,pn的公式,已知是矛盾式,能得出A和B都是矛盾式的结论吗?
为什么?
解：
AB000010100111同样由真值表可得，的成假赋值有00,01,10.所以无法得到A和B都是矛盾式。
29.设A、B都是含命题变量项p1,p2,pn的公式,证明:
是矛盾式当且仅当A和B都是矛盾式.解：
AB000011101111由真值表可得，当且仅当A和B都是矛盾式时，是矛盾式。
30.设A、B都是含命题变量项p1,p2,pn的公式,已知是重言式,能得出A和B都是重言式的结论吗?
解：
AB000011101111由真值表可得的成真赋值有01,10，11.所以无法得到A和B都是重言式。
习题二1.设公式Apq=,Bpq=，用真值表验证公式A和B适合德摩根律：
（AB）ABpqAB（AB）AB0010110110001001001110002.公式A和B同题
（1），用真值表验证公式A和B适合蕴涵等值式.ABABpqABABAB0010000110001001111110003用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
（1）（pqq）答：
原式=（pqq）=（pqq）=0是矛盾式.4.用等值演算法证明下面等值式.
（1）p（pqpq）（）答：
右式=pqq（）=p1=p
（2）（pq）（pr）（p（qr）答：
右式=pqr（）=（pq）（pr）=（pqpr）（）=左式（3）（pq）（pq）（pq）答：
左式=（pq）（pq）=（p（pq）（q（pq）=（pq）（pq）（4）（pq）（pq）（pq）（pq）答：
左式=（p（pq）（q（pq）=（pq）（pq）5.求下列公式的主析取范式，并求成真赋值：
（1）（pq）（qp）答：
（=pq）（qp）（pq）（qp）（pq）（qp）=（pq）（qpp（）（pqq（）=（pq=）（pp）（pqmmm）023成真赋值为00,10,11.
（2）（pq）qr答：
=（pqqr）（pqqrpqq）0所以为矛盾式。
（3）（pqr（）（pqr）答（pqr=（）（pqr）（pqr（）（pqr）（p（qr）（pqr）=（=p（qr）（pqr）（pq）（pr）（pqr）=（pqrr（）（pqq（）r）（pqqrr（）（）（ppqrr）（）（ppqqr）（）=（pqr）（pqr）（pqr）（pqr）（pqr）（pqr=）（pqr）（pqrmmmmmmmm）01234567所以是重言式，真值为000,001,010,011,100,101,110,111.6.求下列公式的主析取范式，并求成真赋值：
（1）（qp）p答：
=（qp）p（qp）pqpp0，是矛盾式，所有赋值均为成真赋值。
（2）（pq）（pr）答：
（pq=）（pr）（pprqpr）（）（pqrM）4，成假赋值为100.（3）（p（pq）r答：
（p=（pqr）（ppqr（）（ppqr1，所以为重言式。
所有赋值均为成真赋值。
7.求下列公式的主析取范式，再用主析取范式求主合取范式：
（1）（pq）r答：
（pqrpqrr=）（）（ppqqr）（）=（pqrr（）（ppqqr）（）=（pqr）（pqr）（pqr）（pqr）（pqr）=mmmmmMMM13567=024
（2）（pq）（qr）答：
（pqqr=）（）（pq）（qr）（pq）（prqqqr）（）（）=（pqrr（）（pqqr（）（ppqr）=（pqr）（pqr）（pqr）（pqr）=mmmmMMMM0137=24568.求下列公式的主合取范式，再用主合取范式求主析取范式：
（1）（pq）q答：
（pq=）q（pqqpqq）1mmmm0123为重言式。
（2）（pq）r答：
（pq=）r（pq）（pqr）（pq）（pqr）=（=pq）（pqr）（pqr）（pqrMM）=06=mmmmmm123457（3）（rppq）答：
=（rppqrppq）=MMMMMMMM01234567=0因此为矛盾式.9.用真值表求下面的公式的主析取范式.
（1）（pq）（pr）答：
公式的真值表如下：
pqrppqpr（pq）（pr）00010000011011010110101111111000101101010111001011110101其成真赋值为001,010,011,100,101,110,111，所以其主析取范式为mmmmmmm1234567
（2）（pq）（pq）答：
公式的真值表如下：
pqqpqpq（pq）（p001100010111101011110100（pq=）（pq）（pq）（pq）（pq）=（pq）（pq）故其成真赋值为001，010.所以其主析取范式为mm12.10.用真值表求下面公式的主合取范式.
（1）（pqr）答：
（pqrprqr=）（）（）=MMM024
（2）（pqqr）（）答：
（pqqr=）（）（pq）（qr）=MMMM245611.用真值表求下面公式的主析取范式和主合取范式.
（1）（pqr）
（2）p（pqr）（3）（qp）ppqr（pqr）p（pqr）（qp）p000010001010010010011110100010101110110010111110答：
（1）由真值表可得成真赋值为011,101,111，故主析取范式为mmm357，主合取范式为MMMMM01246
（2）由真值表可得无成假赋值，故主析取范式为mmmmmmmm01234567，主合取范式为1.（3）由真值表可得无成真赋值，故主析取范式为0，主合取范式为MMMM0123.12.已知公式A含3个命题变项pqr,，并且它的成真赋值为000，011，110，求A的主合取范式和主析取范式.答：
由题意得，A的主主合取范式为MMMMM12457，主析取范式mmm036.13.已知公式A含3个命题变项pqr,，并且它的成真赋值为000，011，110，求A的主合取范式和主析取范式.答：
由题意得，A的主主合取范式为MMMM2367，主析取范式mmmm0157.14.已知公式A含n个命题变相pp1,2,.,pn，并且无成假赋值，求A的主合取范式.答：
A的主合取范式为1.15.用主析取范式判断下列公式是否等值：
（1）（pqr）与q（pr）答：
（pq=）rpqr（）=mmmmm13457q=（pr）pqr=mmmmmmm0123457所以上述公式不等值.
（2）（pq）与（pq）答：
=（pq）pq=mmm012=（pq）pq=m016.用主合取范式判断下列公式是否等值.
（1）p（qr）与（pqr）答：
p=（qrM）6（pqrM）=6
（2）p（qr）与（pq）r答：
p=（qrM）6（pq）rMMM=02617.将下列公式化成与之等值且仅含,中联结词的公式：
（1）（pq（qr）答：
（p（q（qr）=（pq（qr）=p（qr）=p（qqr（）（q（qr）
（2）（pq）r答：
（pq）r，原式已满足题目要求.（3）p（qr）答：
p=（qr）（p（qr）（r）p）=（p（qrqr）（）（qrqr）（）p）18.将下列公式化成与之等值且仅含,中联结词的公式：
（1）pqr答：
此公式已经符合题目要求.
（2）（prq）答：
（prq=）（prrpq）（）=（pr）（rpq）=（pr）（rpq）（3）（pqrq（）答：
（p=（qrq）（pqr（）p=（p（qr）p=（p（qr）p）19.将下列公式化成与之等值且仅含,中联结词的公式.
（1）（pqr）答：
（=pqr）（pq）r）
（2）（p（qpqr）答：
（p=（qpqr）（p（qp）qr）（3）pqr答：
pqr=（pqr）20将下列公式化成与之等值且仅含，中联结词的公式：
（1）（pq）r
（2）（pq）r（3）（pq）r答：
（pqr）（pqr）（pqr）（pqr）
（2）（pqr）答：
（pqr）（pq）r）（pq）r）（3）（pq）r答：
（pq）r（pq）rr）（pq）（pqr）（r（pq）（pqr）（r（pq）21证明：
（1）（pq）（qp），（pq）（qp）.
（2）（p（qr）（pq）r），（p（qr）（pq）r）.证明：
（1）pq（pq）（qp）qp；pq（pq）（qp）qp
（2）令p=0,q=0,r=1则pqr=（）1,（pqr=）0，pqr=（）1,（pqr=）0.，可知（pqr（）（pqrpqr）（，（）（pqr）.22.从表2.6中，找出与下列公式等值的真值函数：
（1）pq
（2）pq（3）（pq）（pq）（4）（pq）答：
（1）F14
（2）;
（2）F8
（2）;（3）F6
（2）;（4）F2
（2）23设A、B、C为任意的命题公式，证明：
（1）等值关系有自反性：
AA
（2）等值关系有对称性：
若AB,则BA（3）等值关系有传递性：
若AB且BC，则AC答：
（1）AA（AAAA）（）AAAA1
（2）BA（BA）（AB）（AB）（BA）AB（3）若ABBC且（ABBABCCB）（）（）（）（ABBCCBBA）（）（）（）（ACCA）（）AC即AC24设A、B为任意的命题公式，证明：
AB当且仅当AB答：
AB（ABBA）（）（ABBA）（）AB.因此AB当且仅当AB。
25设A、B、C为任意的命题公式，
（1）若ACBC，举例说明AB不一定成立。
（2）若ACBC，举例说明AB不一定成立。
由
（1）
升级会员 