离散数学第二版最全课后习题答案详解.docx
《离散数学第二版最全课后习题答案详解.docx》由会员分享，可在线阅读，更多相关《离散数学第二版最全课后习题答案详解.docx（99页珍藏版）》请在冰点文库上搜索。
离散数学第二版最全课后习题答案详解
习题一
1.下列句子中,哪些是命题？
在是命题的句子中,哪些是简单命题？
哪些是真命题？
哪些命题的
真值现在还不知道？
（1）中国有四大发明.
答：
此命题是简单命题，其真值为1.
（2）5是无理数.
答：
此命题是简单命题，其真值为1.
（3）3是素数或4是素数.
答：
是命题，但不是简单命题，其真值为1.
（4）2x+<3
5答：
不是命题.
（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
年”既可以化答:
列出两种符号化的真值表：
p
q
0
0
1
1
0
1
0
1
0
1
1
0
0
1
1
1
根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结
合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式.
8.将下列命题符号化,并指出真值.
就有
（1）只要
（2）如果
（3）只有
（4）除非
（5）除非
（6）
；
则
；
才有
才有
否则
；
；
；
仅当
.
则
:
;设q:
则
:
答:
设p:
.
符号化
真值
（1）
（2）
（3）
（4）
（5）
1
1
0
0
0
（6）
1
9.设p：
俄罗斯位于南半球,q：
亚洲人口最多,将下面命题用自然语言表述,并指出其真值：
（1）
（2）
；
；；
（3）
（4）
；
；
（5）
（6）
（7）
；
；
.
答:
根据题意,p为假命题,q为真命题.
自然语言
真值
（1）
（2）
（3）
（4）
（5）
（6）
（7）
只要俄罗斯位于南半球,亚洲人口就最多
只要亚洲人口最多,俄罗斯就位于南半球
1
0
1
1
1
0
1
只要俄罗斯不位于南半球,亚洲人口就最多
只要俄罗斯位于南半球，亚洲人口就不是最多
只要亚洲人口不是最多，俄罗斯就位于南半球
只要俄罗斯不位于南半球，亚洲人口就不是最多
只要亚洲人口不是最多，俄罗斯就不位于南半球
10．设p：
9是3的倍数,q：
英国与土耳其相邻,将下面命题用自然语言表述,并指出真值：
（1）
（2）
（3）
（4）
；
；
；
.
答:
根据题意,p为真命题,q为假命题.
自然语言
真值
（1）
（2）
（3）
9是3的倍数当且仅当英语与土耳其相邻
9是3的倍数当且仅当英语与土耳其不相邻
9不是3的倍数当且仅当英语与土耳其相邻
0
1
1
（4）
9不是3的倍数当且仅当英语与土耳其不相邻
0
11．将下列命题符号化,并给出各命题的真值：
（1）若2+2=4,则地球是静止不动的；
（2）若2+2=4,则地球是运动不止的；
（3）若地球上没有树木,则人类不能生存；
（4）若地球上没有水,则是无理数.
答:
命题1
命题2
符号化
真值
（1）
（2）
（3）
（4）
p:
2+2=4
q:
地球是静止不动的
q:
地球是静止不动的
q:
人类能生存
0
p:
2+2=4
1
1
1
p:
地球上有树木
p:
地球上有树木
q:
人类能生存
12.将下列命题符号化,并给出各命题的真值：
（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）
（2）
（3）
（4）
1
0
0
1
13.将下列命题符号化,并讨论各命题的真值：
（1）若今天是星期一,则明天是星期二；
（2）只有今天是星期一,明天才是星期二；
（3）今天是星期一当且仅当明天是星期二；
（4）若今天是星期一,则明天是星期三.
答:
设p:
今天是星期一,q:
明天是星期二,r:
明天是星期三.
符号化
真值讨论
（1）
（2）
（3）
（4）
不会出现前句为真,后句为假的情况
不会出现前句为真,后句为假的情况
必然为1
若p为真,则真值为0;若p为假,则真值为1
14.将下列命题符号化：
（1）刘晓月跑得快,跳得高；
（2）老王是山东人或者河北人；
（3）因为天气冷,所以我穿了羽绒服；
（4）王欢与李乐组成一个小组；
（5）李欣与李末是兄弟；
（6）王强与刘威都学过法语；
（7）他一面吃饭,一面听音乐；
（8）如果天下大雨,他就乘班车上班；
（9）只有天下大雨,他才乘班车上班；
（10）除非天下大雨,否则他不乘班车上班；
（11）下雪路滑,他迟到了；
（12）2与4都是素数,这是不对的；
（13）“2或4是素数,这是不对的”是不对的.
答:
命题1
命题2
命题3
符号化
（1）
（2）
（3）
（4）
（5）
p:
刘晓月跑得快
q:
刘晓月跳得高
-
p:
老王是山东人
p:
天气冷
q:
老王是河北人
-
-
-
-
q:
我穿羽绒服
p:
王欢与李乐组成
p:
王欢与李乐组成一个
-
-
一个小组
小组
p:
李辛与李末是兄
p:
李辛与李末是兄弟
弟
（6）
（7）
p:
王强学过法语
p:
他吃饭
q:
刘威学过法语
q:
他听音乐
q:
他乘车上班
q:
他乘车上班
q:
他乘车上班
q:
路滑
-
-
（8）
p:
天下大雨
p:
天下大雨
p:
天下大雨
p:
下雪
-
（9）
-
（10）
（11）
（12）
（13）
-
r:
他迟到了
p:
2是素数
p:
2是素数
q:
4是素数
-
-
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）1
16.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值：
（1）
（2）
（3）
（4）
解：
（1）0，
（2）0，（3）0，（4）1
17.判断下面一段论述是否为真：
“是无理数.并且,如果3是无理数,则
外,只有6能被2整除,6才能被4整除.”
也是无理数.另
解：
p:
是无理数q:
3是无理数r:
是无理数s:
6能被2整除t：
6能被4整除
符号化为:
，该式为重言式，所以论述为真。
18.在什么情况下,下面一段论述是真的:
“说小王不会唱歌或小李不会跳舞是正确的,而说如
果小王会唱歌,小李就会跳舞是不正确的.”解：
p:
小王会唱歌。
q:
小李会跳舞。
真值为1.
真值为0.可得，p真值为1，q真值为0.
所以，小王会唱歌，小李不会跳舞。
19.用真值表判断下列公式的类型:
（1）
（2）
（3）
（4）
（5）
（6）
（7）
p
.
解：
（1）
p
q
r
0
0
0
0
1
0
0
1
1
0
0
1
0
1
0
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
此式为重言式
（2）
p
q
（p
0
0
1
1
0
1
0
1
1
0
1
1
此式为可满足式
（3）
q
r
0
0
1
1
0
1
0
1
0
0
0
0
此式为矛盾式
（4）
p
q
0
0
1
1
0
1
0
1
1
1
1
1
此式为重言式
（5）
p
q
r
0
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
0
1
1
1
1
1
1
0
1
1
1
0
1
0
1
0
此式为可满足式
（6）
p
q
r
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
此式为重言式
（7）
p
q
r
s
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
0
1
1
1
0
0
1
此式为可满足式
20.求下列公式的成真赋值：
（1）
（2）
（3）
（4）
解：
p
q
0
0
1
1
0
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
0
1
1
1
由真值表得：
（1）的成真赋值是01，10,11
（2）的成真赋值是00，10,11
（3）的成真赋值是00，01,10（4）的成真赋值是01，10,11
21.求下列各公式的成假赋值：
（1）
（2）
（3）
解：
p
q
r
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
0
0
1
1
由真值表得：
（1）的成假赋值是011
（2）的成假赋值是010,110
（3）的成假赋值是100,101
22.已知公式
是矛盾式，求公式
成真和成假赋值.
解：
∵
是矛盾式∴
也是矛盾式。
由此可得：
该式无成真赋值。
而成假赋值为：
000,001,010,011,100,101,110,111
23.已知公式
是重言式,求公式
的成真和成假赋值.
解：
∵
是重言式，∴
也是重言式。
由此可得：
该式无成假赋值。
而成真赋值为：
000,001,010,011,100,101,110,111
24.已知
是重言式，试判断公式
及
的类型.
解：
∵
是重言式，而要使该式为重言式，其成真赋值只有
都是重言式。
11，∴
25.已知
是矛盾式，试判断公式
及
的类型.
解：
∵
是矛盾式，而要使该式为矛盾式，其成假赋值
都是重言式。
只有00，∴
26.已知
是重言式，
是矛盾式，试判断
及
的类型.
解：
是矛盾式。
是重言式。
27.设A、B都是含命题变量项p1,p2,…,pn的公式,证明:
重言式.
是重言式当且仅当A和B都是
解：
A
B
0
0
1
1
0
1
0
1
0
0
0
1
由真值表可得，当且仅当A和B都是重言式时，
是重言式。
28.设A、B都是含命题变量项p1,p2,…,pn的公式,已知
是矛盾式,能得出A和B都是
矛盾式的结论吗?
为什么?
解：
A
B
0
0
1
1
0
1
0
1
0
0
0
1
同样由真值表可得，
的成假赋值有00,01,10.所以无法得到A和B都是矛盾式。
29.设A、B都是含命题变量项p1,p2,…,pn的公式,证明:
是矛盾式当且仅当A和B都
是矛盾式.
解：
A
B
0
0
1
1
0
1
0
1
0
1
1
1
由真值表可得，当且仅当A和B都是矛盾式时，
是矛盾式。
30.设A、B都是含命题变量项p1,p2,…,pn的公式,已知
重言式的结论吗?
是重言式,能得出A和B都是
解：
A
B
0
0
1
1
0
1
0
1
0
1
1
1
由真值表可得
的成真赋值有01,10，11.所以无法得到A和B都是重言式。
习题二
1.设公式Apq=→,Bpq=∧¬，用真值表验证公式A和B适合德摩根律：
¬∨⇔¬∧¬（AB）
AB
p
q
A
B
¬∧¬AB
¬∨（AB）
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
1
1
1
0
1
1
0
1
2.公式A和B同题
（1），用真值表验证公式A和B适合蕴涵等值式.
AB→⇔¬∨AB
p
q
A
B
AB→
¬∨AB
0
0
1
0
0
0
0
1
1
1
0
1
1
0
1
0
1
0
0
1
0
0
1
0
3．用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出
成真赋值.
（1）¬∧→（pqq）
答：
原式=¬¬∧∨（（pqq）
=¬¬∨¬∨（pqq）
）
=0是矛盾式.
4.用等值演算法证明下面等值式.
（1）
p⇔∧∨∧¬（pqpq）（
）答：
右式=pqq∧∨¬（）=p∧1=p
（（pq→∧→⇔→∧）（pr））（p（qr））
（2）
答：
右式=¬∨∧pqr（）=（¬∨∧¬∨pq）（p
r）=（pqpr→∧→）（））=左式
（3）
¬↔⇔∨∧¬∧（pq）（pq）（pq）答：
左式=¬¬∨∨¬∨¬（pq）（pq）
=（p∨¬∧∧¬∨¬∧（pq））（q（pq））
=（pq∨∧¬∧）（pq）
（4）
（pq∧¬∨¬∧⇔∨∧¬∧）（pq）（p
q）（pq）答：
左式=（p∨¬∧∧¬∨¬∧（pq））
（q（pq））
=（pq∨∧¬∧）（pq）
5.求下列公式的主析取范式，并求成真赋值：
（1）（¬p→q）→（¬q∨p）
答：
（¬→→¬∨=∨→¬∨=¬∨∨¬∨pq）
（qp）（pq）
（pqq（）
（qp）（pq）（qp）
=（¬∧¬∨¬∧∨¬∨∧∨¬pq）（qpp（
））
=（pq∧∨∨¬∨¬∧¬=∨∨）（pp）
（pqmmm）0
2
3
成真赋值为00,10,11.
（2）¬（p→q）∧q∧r答：
¬→∧∧=¬¬∨∧∧=∧¬∧∧=（pqqr）（pqqrpq
q）
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）（pqrmmmmmm
mm）
7所以是重言式，真值为
0
1
2
3
4
5
6
000,001,010,011,100,101,110,111.
6.求下列公式的主析取范式，并求成真赋值：
（1）
¬（q→¬p）∧¬p答：
¬→¬∧¬=¬¬∨¬∧¬=∧∧¬=（qp）p（qp）pq
pp0，是矛盾式，所有赋值均为成真赋值。
（2）
（p∧q）∨（¬p∨r）答：
（pq∧∨¬∨=∨¬∨∧∨¬∨=¬∨∨=）（p
r）（pprqpr）（
）
（pqrM）4，成假赋值为100.
（3）
（p→（p∨q））∨r答：
（p→∨∨=¬∨∨∨=¬∨∨∨=（pqr））（ppq
r（））（ppqr1，所以为重言式。
所
有赋值均为成真赋值。
7.求下列公式的主析取范式，再用主析取范式求主合取范式：
（1）（p∧q）∨r答：
（pqrpqrr∧∨=∧∧∨¬∨）（
（（ppqqr∨¬∧∨¬∧）（
=（pqrr∧∧∨¬∨（））（（ppqqr∨¬∧∨¬∧）
（
））
（
）
）
）
）
=（pqr∧∧∨∧∧¬∨∧¬∧∨¬∧∧∨¬∧¬∧）（pqr）（pqr）（pqr）（pqr）
=mmmmmMMM1∨∨∨∨3
7=0∧2∧4
5
6
（2）（p→q）∧（q→r）
答：
（pqqr→∧→=¬∨∧¬∨=¬∧¬∨¬∧∨∧¬∨∧）
qqqr）
=（¬∧¬∧∨¬∨¬∧∨¬∧∨pqrr（））
（
）（pq）（qr）（pq）（pr
（
）
（
）
（pqqr（
））（（ppqr∨¬∧∧）
）
=（¬∧¬∧∨¬∧¬∧¬∨¬∧∧∨∧∧pqr）（pqr）（pqr）（pqr）
=mmmmMMMM0∨∨∨137=2∨4∨5∨6
8.求下列公式的主合取范式，再用主合取范式求主析取范式：
（1）
（p∧q）→q答：
（pq∧→=¬∧∨=¬∨¬∨==∨∨∨）q
（pqqpqq）1mmmm01
2
3
为重言式。
（2）
（pq↔→）r答：
（pq↔→=¬∧∨¬∧¬∨=¬∧∧¬¬
∧¬∨）r（（pq）（pqr））（（pq）（pqr））
=（（¬∨¬∧∨∨=¬∨¬∨∧∨∨pq）
（pqr））（pqr）（pqrMM）=0
∧6
=mmmmmm1∨∨∨∨∨2
3
4
5
7
（3）
¬→∧∧（rp
升级会员 