离散数学习题解答.docx
《离散数学习题解答.docx》由会员分享,可在线阅读,更多相关《离散数学习题解答.docx(60页珍藏版)》请在冰点文库上搜索。
离散数学习题解答
离散数学习题答案
习题一
1.判断下列句子是否为命题?
若是命题说明是真命题还是假命题。
(1)3是正数吗?
(2)x+1=0。
(3)请穿上外衣。
(4)2+1=0。
(5)任一个实数的平方都是正实数。
(6)不存在最大素数。
(7)明天我去看电影。
(8)9+5≤12。
(9)实践出真知。
(10)如果我掌握了英语、法语,那么学习其他欧洲语言就容易多了。
解:
(1)、
(2)、(3)不是命题。
(4)、(8)是假命题。
(5)、(6)、(9)、(10)是真命题。
(7)是命题,只是现在无法确定真值。
2.设P表示命题“天下雪”,Q表示命题“我将去书店”,R表示命题“我有时间”,以符号形式写出下列命题。
(1)如果天不下雪并且我有时间,那么我将去书店。
(2)我将去书店,仅当我有时间。
(3)天不下雪。
(4)天下雪,我将不去书店。
解:
(1)(┐P∧R)→Q。
(2)Q→R。
(3)┐P。
(4)P→┐Q。
3.将下列命题符号化。
(1)王皓球打得好,歌也唱得好。
(2)我一边看书,一边听音乐。
(3)老张和老李都是球迷。
(4)只要努力学习,成绩会好的。
(5)只有休息好,才能工作好。
(6)如果a和b是偶数,那么a+b也是偶数。
(7)我们不能既游泳又跑步。
(8)我反悔,仅当太阳从西边出来。
(9)如果f(x)在点x0处可导,则f(x)在点x0处可微。
反之亦然。
(10)如果张老师和李老师都不讲这门课,那么王老师就讲这门课。
(11)四边形ABCD是平行四边形,当且仅当ABCD的对边平行。
(12)或者你没有给我写信,或者信在途中丢失了。
解:
(1)P:
王皓球打得好,Q:
王皓歌唱得好。
原命题可符号化:
P∧Q。
(2)P:
我看书,Q:
我听音乐。
原命题可符号化:
P∧Q。
(3)P:
老张是球迷,Q:
老李是球迷。
原命题可符号化:
P∧Q。
(4)P:
努力学习,Q:
成绩会好。
原命题可符号化:
P→Q。
(5)P:
休息好,Q:
工作好。
原命题可符号化:
Q→P。
(6)P:
a是偶数,Q:
b是偶数,R:
a+b是偶数。
原命题可符号化:
(P∧Q)→R。
(7)P:
我们游泳,Q:
我们跑步。
原命题可符号化:
┐(P∧Q)。
(8)P:
我反悔,Q:
太阳从西边出来。
原命题可符号化:
P→Q。
(9)P:
f(x)在点x0处可导,Q:
f(x)在点x0处可微。
原命题可符号化:
P→←Q。
(10)P:
张老师讲这门课,Q:
李老师讲这门课,R:
王老师讲这门课。
原命题可符号化:
(┐P∧┐Q)→R。
(11)P:
四边形ABCD是平行四边形,Q:
四边形ABCD的对边平行。
原命题可符号化:
P→←Q。
(12)P:
你给我写信,Q:
信在途中丢失了。
原命题可符号化:
┐P←∣→(P∧Q)。
4.判断下列公式哪些是合式公式,哪些不是合式公式。
(1)(Q→R∧S)
(2)(P→←(R→S))
(3)((┐P→Q)→(Q→P)))
(4)(RS→F)
(5)((P→(Q→R))→((P→Q)→(P→R)))
解:
(1)、
(2)、(5)是合式公式,(3)、(4)不是合式公式。
5.否定下列命题:
(1)桂林处处山清水秀。
(2)每一个自然数都是偶数。
解:
(1)桂林并非处处山清水秀。
(2)并不是每一个自然数都是偶数。
或:
有些自然数不是偶数。
6.给出下述每一个命题的逆命题、否命题和逆否命题。
(1)如果天下雨,我将不去。
(2)仅当你去我才不去。
(3)如果Δ=b2−4ac<0,则方程ax2+bx+c=0无实数解。
(4)如果我不获得奖学金,我就不能完成学业。
解:
(1)逆命题:
如果我不去,那么天下雨。
否命题:
如果天不下雨,我就去。
逆否命题:
如果我去,那么天不下雨。
(2)逆命题:
如果你去,我将不去。
否命题:
如果我去,你将不去。
逆否命题:
如果你不去,我就去。
(3)逆命题:
如果方程ax2+bx+c=0无实数解,则Δ=b2−4ac<0。
否命题:
如果Δ=b2−4ac≥0,则方程ax2+bx+c=0有实数解。
逆否命题:
如果方程ax2+bx+c=0有实数解,则Δ=b2−4ac≥0。
(4)逆命题:
如果我不能完成学业,那么我没有获得奖学金。
否命题:
如果我获得奖学金,我就能完成学业。
逆否命题:
如果我就能完成学业,那么我就获得奖学金。
7.求下列各式的真值表。
(1)P→(R∨S)
(2)(P∧R)∨(P→Q)
(3)(P∨Q)→←(Q∨P)
(4)(P∨┐Q)∧R
(5)(P→(Q→R))→((P→Q)→(P→R))
解:
(1)P→(R∨S)
P
R
S
R∨S
P→(R∨S)
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
0
0
0
0
0
1
1
1
1
0
1
0
1
1
0
0
1
1
1
0
0
0
0
1
(2)(P∧R)∨(P→Q)
P
Q
R
P∧R
P→Q
(P∧R)∨(P→Q)
1
1
1
1
1
1
1
1
0
0
1
1
1
0
1
1
0
1
1
0
0
0
0
0
0
1
1
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
0
0
0
0
1
1
(3)(P∨Q)→←(Q∨P)
P
Q
P∨Q
Q∨P
(P∨Q)→←(Q∨P)
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
0
0
0
0
1
(4)(P∨┐Q)∧R
P
Q
R
┐Q
P∨┐Q
(P∨┐Q)∧R
1
1
1
0
1
1
1
1
0
0
1
0
1
0
1
1
1
1
1
0
0
1
1
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
1
0
(5)(P→(Q→R))→((P→Q)→(P→R))
P
Q
R
Q→R
P→(Q→R)
P→Q
P→R
(P→Q)→(P→R)
原公式
1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
0
0
1
1
0
1
1
1
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
1
1
1
1
1
1
1
0
1
0
0
1
1
1
1
1
0
0
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
8.用真值表判断下列公式的类型:
(1)P∨┐Q→Q
(2)((P→Q)∨(R→S))→((P∨R)→(Q∨S))
解:
(1)P∨┐Q→Q
P
Q
┐Q
P∨┐Q
P∨┐Q→Q
1
1
0
1
1
1
0
1
1
0
0
1
0
0
1
0
0
1
1
0
(1)为可满足式。
(2)((P→Q)∨(R→S))→((P∨R)→(Q∨S))
P
Q
R
S
P→Q
R→S
(P→Q)∨(R→S)
P∨R
Q∨S
(P∨R)→(Q∨S)
原公式
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
0
1
0
0
1
1
0
0
1
0
1
1
1
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
0
0
1
1
1
1
0
1
0
1
1
1
1
0
1
1
1
0
1
0
0
1
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
1
1
0
0
1
0
1
0
1
1
0
0
0
0
0
0
1
1
1
1
0
1
1
1
0
0
0
0
1
1
1
0
0
1
1
(2)为可满足式。
9.证明下列等价式。
(1)P→(Q→P)┐P→(P→┐Q)
(2)┐(P→←Q)(P∨Q)∧┐(P∧Q)
(3)┐(P→Q)P∧┐Q
(4)┐(P→←Q)(P∧┐Q)∨(┐P∧Q)
(5)P→(Q∨R)(P∧┐Q)→R
(6)(P→R)∧(Q→R)(P∨Q)→R
(7)((P∧Q)→R)∧(Q→(S∨R))(Q∧(S→P))→R
证明:
(1)P→(Q→P)┐P∨(┐Q∨P)P∨(┐P∨┐Q)┐P→(P→┐Q)
(2)┐(P→←Q)┐((P∧Q)∨(┐P∧┐Q))┐(P∧Q)∧┐(┐P∧┐Q))(P∨Q)∧┐(P∧Q)
(3)┐(P→Q)┐(┐P∨Q)P∧┐Q
(4)┐(P→←Q)┐((P→Q)∧(Q→P))┐(┐P∨Q)∨┐(┐Q∨P)(P∧┐Q)∨(┐P∧Q)
(5)P→(Q∨R)┐P∨(Q∨R)┐(P∧┐Q)∨R(P∧┐Q)→R
(6)(P→R)∧(Q→R)(┐P∨R)∧(┐Q∨R)(┐P∧┐Q)∨R┐(P∨Q)∨R(P∨Q)→R
(7)((P∧Q)→R)∧(Q→(S∨R))(┐(P∧Q)∨R)∧(┐Q∨(S∨R))┐Q∨(┐P∧S)∨R
┐(Q∧(┐S∨P))∨R┐(Q∧(S→P))∨R(Q∧(S→P))→R
10.使用恒等式证明下列各式,并写出它们对偶的公式。
(1)(┐(┐P∨┐Q)∨┐(┐P∨Q))⇔P
(2)(P∨┐Q)∧(P∨Q)∧(┐P∨┐Q)⇔┐(┐P∨Q)
(3)Q∨┐((┐P∨Q)∧P)⇔T
证明:
(1)(┐(┐P∨┐Q)∨┐(┐P∨Q))⇔(P∧Q)∨(P∧┐Q)⇔P∧(Q∨┐Q)⇔P∧T⇔P
(2)(P∨┐Q)∧(P∨Q)∧(┐P∨┐Q)⇔P∨(┐Q∧Q)∧(┐P∨┐Q)⇔P∨F∧(┐P∨┐Q)⇔P∧(┐P∨┐Q)⇔(P∧┐P)∨(P∧┐Q)⇔F∨(P∧┐Q)⇔(P∧┐Q)⇔┐(┐P∨Q)
(3)Q∨┐((┐P∨Q)∧P)⇔Q∨(┐(┐P∨Q)∨┐P)⇔Q∨(P∧┐Q)∨┐P
⇔(Q∨┐P∨P)∧(Q∨┐P∨┐Q)⇔T∨T⇔T
11.试证明{∨},{→}不是全功能联结词集合。
证明:
若{∨}是最小联结词组,则┐P⇔(P∨...)
对所有命题变元指派T,则等价式左边为F,右边为T,等价式矛盾。
若{→}是最小联结词组,则┐P⇔P→(P→(P→...)...)
对所有命题变元指派T,则等价式左边为F,右边为T,等价式矛盾。
12.证明下列蕴涵式:
(1)P∧Q⇒(P→Q)
(2)P⇒(Q→P)
(3)(P→(Q→R))⇒(P→Q)→(P→R)
证明:
(1)P∧Q→(P→Q)⇔┐(P∧Q)∨(P→Q)⇔(┐P∨┐Q)∨(┐P∨Q)⇔┐P∨(┐Q∨Q)⇔T
因为P∧Q→(P→Q)为永真式,所以P∧Q⇒(P→Q)。
(2)P→(Q→P)⇔┐P∨(┐Q∨P)⇔┐Q∨(┐P∨P)⇔T
因为P→(Q→P)为永真式,所以P⇒(Q→P)。
(3)(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∨R)∧(┐Q∨┐P∨R))
⇔(P∧Q∧┐R)∨(┐P∨┐Q∨R)
⇔((P∨(┐P∨┐Q∨R))∧(Q∨(┐P∨┐Q∨R))∧(┐R∨(┐P∨┐Q∨R))⇔T
因为(P→(Q→R))→((P→Q)→(P→R))为永真式,所以(P→(Q→R))⇒(P→Q)→(P→R)。
13.对下列各公式,试仅用↑或↓表示。
(1)┐P
(2)P∧Q
(3)P∨Q
(4)P→Q
解:
(1)┐P⇔┐(P∧P)⇔P↑P
(2)P∧Q⇔(P↑Q)↑(P↑Q)
(3)P∨Q⇔┐(┐P∧┐Q)⇔(┐P↑┐Q)⇔(P↑P)↑(Q↑Q)
(4)P→Q⇔┐P∨Q⇔(P↑P)∨Q⇔((P↑P)↑(P↑P))↑(Q↑Q)
14.将下列公式化成与之等值且仅含{┐,→}中联结词的公式。
(1)(P→┐Q)∧R
(2)P→←(Q∧R)∨P
解:
(1)(P→┐Q)∧R⇔(┐P∨┐Q)∧R⇔(┐P∧R)∨(┐Q∧R)⇔┐(P∨┐R)∨┐(Q∨┐R)
⇔┐(R→P)∨┐(R→Q)⇔(R→P)→┐(R→Q)
(2)P→←(Q∧R)∨P⇔(P→((Q∧R)∨P))∧(((Q∧R)∨P)→P)⇔(┐P∨((Q∧R)∨P))∧(┐((Q∧R)∨P)∨P)⇔T∧(((┐Q∨┐R)∧┐P)∨P)⇔((┐Q∨┐R)∨P)⇔P∨(┐Q∨┐R)⇔P∨(Q→┐R)⇔┐P→(Q→┐R)
15.如果A(P,Q,R)由R↑(Q∧┐(R↓P))给出,求它的对偶A*(P,Q,R),并求出与A及A*等价且仅包含联接词“∧”,“∨”及“┐”的公式。
解:
A*(P,Q,R):
R↓(Q∨┐(R↑P))
R↑(Q∧┐(R↓P))⇔┐(R∧(Q∧(R∨P)))⇔┐R∨┐Q∨(┐R∧┐P)
R↓(Q∨┐(R↑P))⇔┐R∧┐Q∧(┐R∨┐P)
16.把P↑Q表示为只含有“↓”的等价公式。
解:
P↑Q┐(P∧Q)┐((P↓P)↓(Q↓Q))((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q))
17.证明:
(1)┐(P↑Q)┐P↓┐Q
(2)┐(P↓Q)┐P↑┐Q
证明:
(1)┐(P↑Q)┐(┐(P∧Q))(P∧Q)┐(┐P∨┐Q)┐P↓┐Q
(2)┐(P↓Q)┐(┐(P∨Q))(P∨Q)┐(┐P∧┐Q)┐P↑┐Q
18.求公式P∧(P→Q)的析取范式和合取范式。
解:
P∧(P→Q)P∧(┐P∨Q)合取范式
(P∧┐P)∨(P∧Q)析取范式
19.求下列公式的主析取范式和主合取范式。
(1)(┐P→Q)→(┐Q∨P)
(2)(P→(P∨Q))∨R
(3)(P→Q∧R)∧((┐P→(┐Q∧┐R))
解:
(1)真值表法
P
Q
┐P→Q
┐Q∨P
(┐P→Q)→(┐Q∨P)
1
1
1
1
1
1
0
1
1
1
0
1
1
0
0
0
0
0
1
1
主析取范式为:
(P∧Q)∨(P∧┐Q)∨(┐P∧┐Q)
主合取范式为:
P∨┐Q
公式化归法
(┐P→Q)→(┐Q∨P)┐(P∨Q)∨(┐Q∨P)(┐P∧┐Q)∨(┐Q∨P)
(┐P∨┐Q∨P)∧(┐Q∨┐Q∨P)P∨┐Q主合取范式
(P∧Q)∨(P∧┐Q)∨(┐P∧┐Q)主析取范式
(2)真值表法(P→(P∨Q))∨R
P
Q
R
P∨Q
P→(P∨Q)
(P→(P∨Q))∨R
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
0
0
0
0
1
1
原式为永真式,其主析取范式为所有小项的析取,即:
m000∨m001∨m010∨m011∨m100∨m101∨m110∨m111
不能表示为主合取范式。
公式化归法
(P→(P∨Q))∨R(┐P∨(P∨Q))∨RT∨RT
(3)真值表法(P→Q∧R)∧((┐P→(┐Q∧┐R))
P
Q
R
Q∧R
P→Q∧R
┐Q∧┐R
┐P→(┐Q∧┐R)
原公式
1
1
1
1
1
0
1
1
1
1
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
0
0
0
1
1
0
0
1
1
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
1
1
主析取范式为:
(P∧Q∧R)∨(┐P∧┐Q∧┐R)m111∨m000m7∨m0
主合取范式为:
M1∧M2∧M3∧M4∧M5∧M6M001∧M010∧M011∧M100∧M101∧M110(P∨Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R)∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)
20.求下列公式的主析取范式和主合取范式,并指出该公式的类型。
(1)(┐P∨┐Q)→(P→←┐Q)
(2)Q∧(P∨┐Q)
(3)P∨(┐P→(Q∨(┐Q→R)))
(4)(P→(Q∧R))∧(┐P→(┐Q∧┐R))
(5)P→(P∧(Q→P))
(6)(Q→P)∧(┐P∧Q)
解:
(1)
P
Q
┐P∨┐Q
P→←┐Q
(┐P∨┐Q)→(P→←┐Q)
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
0
0
1
0
0
主析取范式为:
(P∧Q)∨(P∧┐Q)∨(┐P∧Q)
主合取范式为:
P∨Q
公式为可满足式。
(2)
P
Q
P∨┐Q
Q∧(P∨┐Q)
1
1
1
1
1
0
1
0
0
1
0
0
0
0
1
0
主析取范式为:
P∧Q
主合取范式为:
(┐P∨Q)∧(P∨┐Q)∧(P∨Q)
公式为可满足式。
(3)P∨(┐P→(Q∨(┐Q→R)))P∨(P∨(Q∨(Q∨R)))
P∨Q∨R主合取范式
M000M0m1∨m2∨m3∨m4∨m5∨m6∨m7主析取范式
公式为可满足式。
(4)(P→(Q∧R))∧(┐P→(┐Q∧┐R))(┐P∨(Q∧R))∧(P∨(┐Q∧┐R))(┐P∨Q)∧(┐P∨R)∧(P∨┐Q)∧(P∨┐R)(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R)∧(P∨Q∨┐R)M100∧M101∧M111∧M010∧M011∧M001M4∧M5∧M7∧M2∧M3∧M1主合取范式
m0∨m6m000∨m110主析取范式
公式为可满足式。
(5)P→(P∧(Q→P))┐P∨(P∧(┐Q∨P))(┐P∨P)∧(┐P∨(┐Q∨P))T
主析取范式为:
m0∨m1∨m2∨m3
公式为永真式。
(6)(Q→P)∧(┐P∧Q)(┐Q∨P)∧(┐P∧Q)(┐Q∧┐P∧Q)∨(P∧┐P∧Q)F
主合取范式为:
M0∧M1∧M2∧M3
公式为永假式。
21.用将合式公式化为范式的方法证明下列各题中两式是等价的。
(1)(P→Q)∧(P→R),P→(Q∧R)
(2)(P→Q)→(P∧Q),(┐P→Q)∧(Q→P)
(3)P∧Q∧(┐P∨┐Q),┐P∧┐Q∧(P∨Q)
(4)P∨(P→(P∧Q)),┐P∨┐Q∨(P∧Q)
证明:
(1)(P→Q)∧(P→R)(┐P∨Q)∧(┐P∨R)
P→(Q∧R)┐P∨(Q∧R)(┐P∨Q)∧(┐P∨R)
(2)(P→Q)→(P∧Q)┐(┐P∨Q)∨(P∧Q)(P∧┐Q)∨(P∧Q)P∧(┐Q∨Q)P
(┐P→Q)∧(Q→P)(P∨Q)∧(┐Q∨P)P∨(Q∧┐Q)P
(3)P∧Q∧(┐P∨┐Q)(P∧Q∧┐P)∨(P∧Q∧┐Q)F
┐P∧┐Q∧(P∨Q)(┐P∧┐Q∧P)∨(┐P∧┐Q∧Q)F
(4)P∨(P→(P∧Q))P∨(┐P∨(P∧Q))T∨(P∧Q)T
┐P∨┐Q∨(P∧Q)(┐P∨┐Q∨P)∧(┐P∨┐Q∨Q)T
22.用推理规则证明以下各式。
(1)┐(P∧┐Q),┐Q∨R,┐R⇒┐P
(2)A→(B∨C),(D∨E)→A,D∨E⇒B∨C
(3)B∧C,(B→←C)→(D∨E)⇒D∨E
(4)P→Q,(┐Q∨R)∧┐R,┐(┐P∧S)⇒┐S
证明:
(1)┐(P∧┐Q),┐Q∨R,┐R⇒┐P
证明:
(1)┐RP
(2)┐Q∨RP
(3)┐QT
(1)
(2)I
(4)┐(P∧┐Q)P
(5)┐P∨QT(4)E
(6)┐PT(3)(5)I
(2)A→(B∨C),(D∨E)→A,D∨E⇒B∨C
证明:
(1)D∨EP
(2)(D∨E)→AP
(3)AT
(1)
(2)I
(4)A→(B∨C)P
(5)B∨CT(3)(4)I
(3)B∧C,(B→←C)→(D∨E)⇒D∨E
证明:
(1)B∧CP
(2)B→←CT
(1)I
(3)(B→←C)→(D∨E)P
(4)D∨ET
(2)(3)I
(4)P→Q,(┐Q∨R)∧┐R,┐(┐P∧S)⇒┐S
证明:
(1)(┐Q∨R)∧┐RP
(2)┐Q∨RT
(1)I
(3)┐RT
(1)I
(4)┐QT
(2)(3)I
(5)┐(┐P∧S)P
(6)S→PT(5)E
(7)P→QP
(8)S→QT(6)(7)I
(9)┐Q→┐ST(8)E
(10)┐ST(4)(8)I
23.仅用规则P和T,推证以下公式。
(1)┐A∨B,C→┐B⇒A→┐C
(2)A→(B→C),(C∧D)→E,┐F→(D∧┐E)⇒A→(B→F)
(3)A∨B→C∧D,D∨E→F,⇒A→F
(4)A→(B∧C),┐B∨D,(E→┐F)→┐D,B→(A∧┐E)⇒B→E
(5)(A→B)∧(C→D),(B→E)∧(D→F),┐(E∧F),A→C⇒