离散数学课后习题答案 (左孝凌版)
1-1,1-2
(1) 解:
a) 是命题,真值为 T。
b) 不是命题。
c) 是命题,真值要根据具体情况确定。
d) 不是命题。
e) 是命题,真值为 T。
f) 是命题,真值为 T。
g) 是命题,真值为 F。
h) 不是命题。
i) 不是命题。
(2) 解:
原子命题:我爱北京天安门。
复合命题:如果不是练健美操,我就出外旅游拉。
(3) 解:
a)
b)
(┓P ∧R)→Q
Q→R
c) ┓P
d)
P→┓Q
(4) 解:
a)设 Q:我将去参加舞会。R:我有时间。P:天下雨。
Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。
b)设 R:我在看电视。Q:我在吃苹果。
R∧Q:我在看电视边吃苹果。
c) 设 Q:一个数是奇数。R:一个数不能被 2 除。
(Q→R)∧(R→Q):一个数是奇数,则它不能被 2 整除并且一个数不能被 2 整除,则它是奇数。
(5) 解:
a) 设 P:王强身体很好。Q:王强成绩很好。P∧Q
b) 设 P:小李看书。Q:小李听音乐。P∧Q
c) 设 P:气候很好。Q:气候很热。P∨Q
d) 设 P: a 和 b 是偶数。Q:a+b 是偶数。P→Q
e) 设 P:四边形 ABCD 是平行四边形。Q :四边形 ABCD 的对边平行。PQ
f) 设 P:语法错误。Q:程序错误。R:停机。(P∨ Q)→ R
(6) 解:
a)
b)
c)
d)
e)
f)
g)
P:天气炎热。Q:正在下雨。 P∧Q
P:天气炎热。R:湿度较低。 P∧R
R:天正在下雨。S:湿度很高。 R∨S
A:刘英上山。B:李进上山。 A∧B
M:老王是革新者。N:小李是革新者。 M∨N
L:你看电影。M:我看电影。 ┓L→┓M
P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R
h)
P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q
1-3
(1)解:
a) 不是合式公式,没有规定运算符次序(若规定运算符次序后亦可作为合式公式)
b) 是合式公式
c) 不是合式公式(括弧不配对)
d) 不是合式公式(R 和 S 之间缺少联结词)
e) 是合式公式。
(2)解:
a) A 是合式公式,(A∨B)是合式公式,(A→(A∨B)) 是合式公式。这个过程可以简记为:
A;(A∨B);(A→(A∨B))
同理可记
b) A;┓A ;(┓A∧B) ;((┓A∧B)∧A)
c) A;┓A ;B;(┓A→B) ;(B→A) ;((┓A→B)→(B→A))
d) A;B;(A→B) ;(B→A) ;((A→B)∨(B→A))
(3)解:
a) ((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C))
b) ((B→A)∨(A→B))。
(4)解:
a) 是由 c) 式进行代换得到,在 c) 中用 Q 代换 P, (P→P)代换 Q.
d) 是由 a) 式进行代换得到,在 a) 中用 P→(Q→P)代换 Q.
e) 是由 b) 式进行代换得到,用 R 代换 P, S 代换 Q, Q 代换 R, P 代换 S.
(5)解:
a) P: 你没有给我写信。 R: 信在途中丢失了。 P
Q
b) P: 张三不去。Q: 李四不去。R: 他就去。 (P∧Q)→R
c) P: 我们能划船。 Q: 我们能跑步。 ┓(P∧Q)
d) P: 你来了。Q: 他唱歌。R: 你伴奏。 P→(QR)
∨
(6)解:
P:它占据空间。 Q:它有质量。 R:它不断变化。 S:它是物质。
这个人起初主张:(P∧Q∧R) S
后来主张:(P∧QS)∧(S→R)
这个人开头主张与后来主张的不同点在于:后来认为有 P∧Q 必同时有 R,开头时没有这样的主张。
(7)解:
a) P: 上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。(┓P→Q)∧(P→(R∨S))
b) P: 我今天进城。Q:天下雨。┓Q→P
c) P: 你走了。 Q:我留下。Q→P
1-4
(4)解:a)
P
Q
R
Q∧R
P∧(Q∧R)
P∧Q
(P∧Q)∧R
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
所以,P∧(Q∧R) (P∧Q)∧R
T
F
F
F
T
F
F
F
T
F
F
F
F
F
F
F
T
T
F
F
F
F
F
F
T
F
F
F
F
F
F
F
b)
Q
T
T
F
F
T
T
F
F
R
T
F
T
F
T
F
T
F
P
T
T
T
T
F
F
F
F
Q∨R
P∨(Q∨R)
P∨Q
(P∨Q)∨R
T
T
T
F
T
T
T
F
T
T
T
T
T
T
T
F
T
T
T
T
T
T
F
F
T
T
T
T
T
T
T
F
所以,P∨(Q∨R) (P∨Q)∨R
c)
P Q R Q∨R P∧(Q∨R) P∧Q P∧R (P∧Q)∨(P∧R)
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
T
T
T
F
T
T
T
F
T
T
T
F
F
F
F
F
T
T
F
F
F
F
F
F
T
F
T
F
F
F
F
F
T
T
T
F
F
F
F
F
所以,P∧(Q∨R) (P∧Q)∨(P∧R)
d)
Q
T
F
T
F
P
T
T
F
F
┓P
F
F
T
T
┓Q
┓P∨┓Q
┓(P∧Q)
┓P∧┓Q
┓(P∨Q)
F
T
F
T
F
T
T
T
F
T
T
T
F
F
F
T
F
F
F
T
所以,┓(P∧Q) ┓P∨┓Q, ┓(P∨Q) ┓P∧┓Q
(5)解:如表,对问好所填的地方,可得公式 F1~F6,可表达为
P
Q
R
F1
F2
F3
F4
F5
F6
T
T
T
T
F
F
F
F
T
T
F
F
T
T
F
F
T
F
T
F
T
F
T
F
T
F
T
F
T
T
T
F
F1:(Q→P)→R
F2:(P∧┓Q∧┓R)∨(┓P∧┓Q∧┓R)
F3:(P←→Q)∧(Q∨R)
F4:(┓P∨┓Q∨R)∧(P∨┓Q∨R)
F5:(┓P∨┓Q∨R)∧(┓P∨┓Q∨┓R)
F6:┓(P∨Q∨R)
(6)
1
F
F
F
F
P
F
F
T
T
Q
F
T
F
T
2
T
F
F
F
3
F
T
F
F
4
T
T
F
F
5
F
F
T
F
6
T
F
T
F
7
F
T
T
F
解:由上表可得有关公式为
1.F
2.┓(P∨Q)
3.┓(Q→P)
F
F
F
T
F
F
F
T
8
T
T
T
F
T
T
F
F
F
F
T
F
T
F
T
T
T
F
T
T
F
F
T
T
T
T
T
T
F
F
F
F
F
F
F
T
9
F
F
F
T
10
11
12
13
14
15
16
T
F
F
T
F
T
F
T
T
T
F
T
F
F
T
T
T
F
T
T
F
T
T
T
T
T
T
T
4.┓P
8.┓(P∧Q)
12.P→Q
5.┓(P→Q)
9.P∧Q
13.P
6.┓Q
10.PQ
7.┓(PQ)
11.Q
14.Q→P
15.P∨Q
16.T
(7) 证明:
a) A→(B→A) ┐A∨(┐B∨A)
A∨(┐A∨┐B)
A∨(A→┐B)
┐A→(A→┐B)
b) ┐(AB) ┐((A∧B)∨(┐A∧┐B))
┐((A∧B)∨┐(A∨B))
(A∨B)∧┐(A∧B)
或 ┐(AB) ┐((A→B)∧(B→A))
┐((┐A∨B)∧(┐B∨A))
┐((┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A))
┐((┐A∧┐B)∨(B∧A))
┐(┐(A∨B))∨(A∧B)
(A∨B)∧┐(A∧B)
c) ┐(A→B) ┐(┐A∨B) A∧┐B
d) ┐(AB)┐((A→B)∧(B→A))
┐((┐A∨B)∧(┐B∨A))
(A∧┐B)∨(┐A∧B)
e) (((A∧B∧C)→D)∧(C→(A∨B∨D)))
(┐(A∧B∧C)∨D)∧(┐C∨(A∨B∨D))
(┐(A∧B∧C)∨D)∧(┐(┐A∧┐B∧C)∨D)
(┐(A∧B∧C)∧┐(┐A∧┐B∧C))∨D
((A∧B∧C)∨(┐A∧┐B∧C))→D
(((A∧B)∨(┐A∧┐B))∧C)→D
((C∧(AB))→D)
f) A→(B∨C) ┐A∨(B∨C)
(┐A∨B)∨C
┐(A∧┐B)∨C
(A∧┐B)→C
g) (A→D)∧(B→D)(┐A∨D)∧(┐B∨D)
(┐A∧┐B)∨D
┐(A∨B)∨D
(A∨B)→D
h) ((A∧B)→C)∧(B→(D∨C))
(┐(A∧B)∨C)∧(┐B∨(D∨C))
(┐(A∧B)∧(┐B∨D))∨C
(┐(A∧B) ∧┐(┐D∧B))∨C
┐((A∧B)∨(┐D∧B))∨C
((A∨┐D)∧B)→C
(B∧(D→A))→C
(8)解:
a) ((A→B) (┐B→┐A))∧C
((┐A∨B) (B∨┐A))∧C
((┐A∨B) (┐A∨B))∧C
T∧C C
b) A∨(┐A∨(B∧┐B)) (A∨┐A)∨(B∧┐B) T∨F T
c) (A∧B∧C)∨(┐A∧B∧C)
(A∨┐A) ∧(B∧C)
T∧(B∧C)
B∧C
(9)解:1)设 C 为 T,A 为 T,B 为 F,则满足 A∨CB∨C,但 AB 不成立。
2)设 C 为 F,A 为 T,B 为 F,则满足 A∧CB∧C,但 AB 不成立。
3)由题意知┐A 和┐B 的真值相同,所以 A 和 B 的真值也相同。
习题 1-5
(1) 证明:
a) (P∧(P→Q))→Q
(P∧(┐P∨Q))→Q
(P∧┐P)∨(P∧Q)→Q
(P∧Q)→Q
┐(P∧Q)∨Q
┐P∨┐Q∨Q
┐P∨T
T
b) ┐P→(P→Q)
c)
d)
P∨(┐P∨Q)
(P∨┐P)∨Q
T∨Q
T
((P→Q)∧(Q→R))→(P→R)
因为(P→Q)∧(Q→R)(P→R)
所以 (P→Q)∧(Q→R)为重言式。
((a∧b)∨(b∧c) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a)
因为((a∧b)∨(b∧c)∨(c∧a))
((a∨c)∧b)∨(c∧a)
((a∨c)∨(c∧a))∧(b∨(c∧a))
(a∨c)∧(b∨c)∧(b∨a)
所以((a∧b)∨(b∧c) ∨(c∧a))(a∨b)∧(b∨c)∧(c∨a) 为重言式。
(2) 证明:
a)(P→Q)P→(P∧Q)
解法 1:
设 P→Q 为 T
(1)若 P 为 T,则 Q 为 T,所以 P∧Q 为 T,故 P→(P∧Q)为 T
(2)若 P 为 F,则 Q 为 F,所以 P∧Q 为 F,P→(P∧Q)为 T
命题得证
解法 2:
设 P→(P∧Q)为 F ,则 P 为 T,(P∧Q)为 F ,故必有 P 为 T,Q 为 F ,所以 P→Q 为 F。
解法 3:
(P→Q) →(P→(P∧Q))
┐(┐P∨Q)∨(┐P∨(P∧Q))
┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q))
T
所以(P→Q)P→(P∧Q)
b)(P→Q)→QP∨Q
设 P∨Q 为 F,则 P 为 F,且 Q 为 F,
故 P→Q 为 T,(P→Q)→Q 为 F,
所以(P→Q)→QP∨Q。
c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q
设 R→Q 为 F,则 R 为 T,且 Q 为 F,又 P∧┐P 为 F
所以 Q→(P∧┐P)为 T,R→(P∧┐P)为 F
所以 R→(R→(P∧┐P))为 F,所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))为 F
即(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q 成立。
(3) 解:
a)
P→Q 表示命题“如果 8 是偶数,那么糖果是甜的”。
b) a)的逆换式 Q→P 表示命题“如果糖果是甜的,那么 8 是偶数”。
c) a)的反换式┐P→┐Q 表示命题“如果 8 不是偶数,那么糖果不是甜的”。
d)
a)的逆反式┐Q→┐P 表示命题“如果糖果不是甜的,那么 8 不是偶数”。
(4) 解:
a) 如果天下雨,我不去。
设 P:天下雨。Q:我不去。P→Q
逆换式 Q→P 表示命题:如果我不去,则天下雨。
逆反式┐Q→┐P 表示命题:如果我去,则天不下雨
b) 仅当你走我将留下。
设 S:你走了。R:我将留下。R→S
逆换式 S→R 表示命题:如果你走了则我将留下。
逆反式┐S→┐R 表示命题:如果你不走,则我不留下。
c) 如果我不能获得更多帮助,我不能完成个任务。
设 E:我不能获得更多帮助。H:我不能完成这个任务。E→H
逆换式 H→E 表示命题:我不能完成这个任务,则我不能获得更多帮助。
逆反式┐H→┐E 表示命题:我完成这个任务,则我能获得更多帮助
(5) 试证明 PQ,Q 逻辑蕴含 P。
证明:解法 1:
本题要求证明(PQ) ∧QP,
设(PQ) ∧Q 为 T,则(PQ)为 T,Q 为 T,故由的定义,必有 P 为 T。
所以(PQ) ∧QP
解法 2:
由体题可知,即证((PQ)∧Q)→P 是永真式。
((PQ)∧Q)→P
(((P∧Q) ∨(┐P∧┐Q)) ∧Q)→P
(┐((P∧Q) ∨(┐P∧┐Q)) ∨┐Q) ∨P
(((┐P∨┐Q) ∧(P∨Q)) ∨┐Q) ∨P
((┐Q∨┐P∨┐Q) ∧(┐Q∨P∨Q)) ∨P
((┐Q∨┐P) ∧T) ∨P
┐Q∨┐P∨P
┐Q∨T
T
(6) 解:
P:我学习
Q:我数学不及格
R:我热衷于玩扑克。
Q
R
如果我学习,那么我数学不会不及格:
如果我不热衷于玩扑克,那么我将学习:
P→┐Q
┐R→P
但我数学不及格:
因此我热衷于玩扑克。
即本题符号化为:(P→┐Q)∧(┐R→P)∧QR
证:
证法 1:((P→┐Q)∧(┐R→P)∧Q)→R
┐((┐P∨┐Q)∧(R∨P)∧Q) ∨R
(P∧Q)∨(┐R∧┐P)∨┐Q∨R
((┐Q∨P)∧(┐Q∨Q))∨((R∨┐R)∧(R∨┐P))
┐Q∨P∨R∨┐P
T
所以,论证有效。
证法 2:设(P→┐Q)∧(┐R→P)∧Q 为 T,
则因 Q 为 T,(P→┐Q) 为 T,可得 P 为 F,
由(┐R→P)为 T,得到 R 为 T。
故本题论证有效。
(7) 解:
P:6 是偶数
Q:7 被 2 除尽
R:5 是素数
R
┐P
如果 6 是偶数,则 7 被 2 除不尽
或 5 不是素数,或 7 被 2 除尽
P→┐Q
┐R∨Q
5 是素数
所以 6 是奇数
即本题符号化为:(P→┐Q)∧(┐R∨Q)∧R ┐P
证:
证法 1:((P→┐Q)∧(┐R∨Q)∧R)→┐P
┐((┐P∨┐Q) ∧(┐R∨Q) ∧R) ∨┐P
((P∧Q) ∨(R∧┐Q) ∨┐R) ∨┐P
((┐P∨P) ∧(┐P∨Q)) ∨((┐R∨R) ∧(┐R∨┐Q))
(┐P∨Q) ∨(┐R∨┐Q)
T
所以,论证有效,但实际上他不符合实际意义。
证法 2:(P→┐Q)∧(┐R∨Q)∧R 为 T,
则有 R 为 T,且┐R∨Q 为 T,故 Q 为 T,
再由 P→┐Q 为 T,得到┐P 为 T。
(8) 证明:
a) P(┐P→Q)
设 P 为 T,则┐P 为 F,故┐P→Q 为 T
b) ┐A∧B∧CC
假定┐A∧B∧C 为 T,则 C 为 T。
c) CA∨B∨┐B
因为 A∨B∨┐B 为永真,所以 CA∨B∨┐B 成立。
d) ┐(A∧B) ┐A∨┐B
设┐(A∧B)为 T,则 A∧B 为 F。
若 A 为 T,B 为 F,则┐A 为 F,┐B 为 T,故┐A∨┐B 为 T。
若 A 为 F,B 为 T,则┐A 为 T,┐B 为 F,故┐A∨┐B 为 T。
若 A 为 F,B 为 F,则┐A 为 T,┐B 为 T,故┐A∨┐B 为 T。
命题得证。
e) ┐A→(B∨C),D∨E,(D∨E)→┐AB∨C
设┐A→(B∨C),D∨E,(D∨E)→┐A 为 T,
则 D∨E 为 T,(D∨E)→┐A 为 T,所以┐A 为 T
又┐A→(B∨C)为 T,所以 B∨C 为 T。命题得证。
f) (A∧B)→C,┐D,┐C∨D┐A∨┐B
设(A∧B)→C,┐D,┐C∨D 为 T,则┐D 为 T,┐C∨D 为 T,所以 C 为 F
又(A∧B)→C 为 T,所以 A∧B 为 F,所以┐A∨┐B 为 T。命题得证。
(9)解:
a) 如果他有勇气,他将得胜。
P:他有勇气
Q:他将得胜
原命题:P→Q
逆反式:┐Q→┐P 表示:如果他失败了,说明他没勇气。
b) 仅当他不累他将得胜。
P:他不累
原命题:Q→P
Q:他得胜
逆反式:┐P→┐Q 表示:如果他累,他将失败。
习题 1-6
(1)解: