离散数学习题答案

习题一

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。

Q。 （9）P：f(x)在点x0处可导， Q：f(x)在点x0处可微。原命题可符号化：P←→（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)

(R→S)) （2）(P←→

（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)

(Q∨（3）(P∨Q) ←P) →

（4）(P∨┐Q) ∧R

（5）(P→(Q→R))→((P→Q) →(P→R)) 解：

（1）P→(R∨S)

P 1 1 1 1 0 0 0 0 （2）(P∧R) ∨(P→Q) P 1 1 1 1 0 0 0 0 (Q∨（3）(P∨Q) ←P) →

Q 1 1 0 0 1 1 0 0 P 1 1 0 0 （4）(P∨┐Q) ∧R P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 ┐Q 0 0 1 1 0 0 1 1 P∨┐Q 1 1 1 1 0 0 1 1 (P∨┐Q) ∧R 1 0 1 0 0 0 1 0 R 1 0 1 0 1 0 1 0 Q 1 0 1 0 P∧R 1 0 1 0 0 0 0 0 P∨Q 1 1 1 0 P→Q 1 1 0 0 1 1 1 1 (P∧R) ∨(P→Q) 1 1 1 0 1 1 1 1 R 1 1 0 0 1 1 0 0 S 1 0 1 0 1 0 1 0 R∨S 1 1 1 0 1 1 1 0 P→(R∨S) 1 1 1 0 1 1 1 1 Q∨P 1 1 1 0 (Q∨(P∨Q) ←P) →1 1 1 1 （5）(P→(Q→R))→((P→Q) →(P→R))

P Q R Q→R P→(Q→R) P→Q P→R 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 8. 用真值表判断下列公式的类型：

(1) P∨┐Q→Q

(2) ((P→Q)∨(R→S))→((P∨R)→(Q∨S)) 解：

(1) P∨┐Q→Q

P 1 1 0 0 Q 1 0 1 0 ┐Q 0 1 0 1 P∨┐Q 1 1 0 1 (P→Q) →(P→R) 1 0 1 1 1 1 1 1 原公式 1 1 1 1 1 1 1 1 P∨┐Q→Q 1 0 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 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 1 （2）为可满足式。 9. 证明下列等价式。

（1）P→(Q→P) ?┐P→(P→┐Q)

Q)? (P∨（2）┐(P←Q) ∧┐(P∧Q) →

（3）┐(P→Q)? P∧┐Q

Q)? (P∧（4）┐(P←┐Q) ∨ (┐P∧Q) →

原公式 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 （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)

Q)?┐((P∧（2）┐(P←Q) ∨(┐P∧┐Q)) ?┐(P∧Q) ∧┐(┐P∧┐Q)) ? (P∨Q) ∧┐(P∧Q) →

（3）┐(P→Q)? ┐(┐P∨Q) ?P∧┐Q

Q)? ┐((P→Q)∧（4）┐(P←(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)。