离散数学课后习题答案_(左孝凌版)
习题 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)
?P∨(┐P∨Q)
? (P∨┐P)∨Q
?T∨Q
?T
c)((P→Q)∧(Q→R))→(P→R)
因为(P→Q)∧(Q→R)?(P→R)
所以 (P→Q)∧(Q→R)为重言式。
d)((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)→Q?P∨Q
设P∨Q为F，则P为F，且Q为F，
故P→Q为T，(P→Q)→Q为F，
所以(P→Q)→Q?P∨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）试证明P?Q，Q逻辑蕴含P。
证明：解法1：
本题要求证明(P?Q) ∧Q?P,
设(P?Q) ∧Q为T，则(P?Q)为T，Q为T，故由?的定义，必有P为T。所以(P?Q) ∧Q?P
解法2：
由体题可知，即证((P?Q)∧Q)→P是永真式。
((P?Q)∧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：我热衷于玩扑克。
如果我学习，那么我数学不会不及格：P→┐Q
如果我不热衷于玩扑克，那么我将学习: ┐R→P
但我数学不及格: Q
因此我热衷于玩扑克。 R
即本题符号化为：(P→┐Q)∧(┐R→P)∧Q?R
证：
证法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是素数
如果6是偶数，则7被2除不尽P→┐Q
或5不是素数，或7被2除尽┐R∨Q
5是素数 R
所以6是奇数┐P
即本题符号化为：（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∧C?C
假定┐A∧B∧C为T，则C为T。
c)C?A∨B∨┐B
因为A∨B∨┐B为永真，所以C?A∨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)→┐A?B∨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：他得胜
原命题：Q→P逆反式：┐P→┐Q 表示：如果他累，他将失败。
习题 1-6
(1)解：
a)(P∧Q)∧┐P?(P∧┐P)∧Q?┐(T∨Q)
b)(P→(Q∨┐R)) ∧┐P∧Q
? (┐P∨(Q∨┐R))∧┐P∧Q
?(┐P∧┓P∧Q)∨(Q∧┓P∧Q)∨(┓R∧┓P∧Q)
?(┓P∧Q)∨(┓P∧Q)∨(┓P∧┓R∧Q)
?┓P∧Q
?┐(P∨┐Q)
c)┐P∧┐Q∧(┐R→P)
?┐P∧┐Q∧(R∨P)
?(┐P∧┐Q∧R)∨(┐P∧┐Q∧P)
?(┐P∧┐Q∧R)∨F
?┐P∧┐Q∧R
?┐(P∨Q∨┐R)
(2) 解：
a)┐P? P↓P
b)P∨Q?┐(P↓Q) ? (P↓Q)↓(P↓Q)
c)P∧Q?┐P↓┐Q? (P↓P)↓(Q↓Q)
(3)解：
P→(┐P→Q)
?┐P∨(P∨Q)
?T
?┐P∨P
?(┐P↑┐P)↑(P↑P)
?P↑(P↑P)
P→(┐P→Q)
?┐P∨(P∨Q)
?T
?┐P∨P
?┐(┐P↓P)
?┐((P↓P)↓P)
?((P↓P)↓P)↓((P↓P)↓P)
(4)解：
P↑Q
?┐(┐P↓┐Q)
?┐((P↓P)↓(Q↓Q))
? ((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q))
(5)证明：
┐(B↑C)
?┐(┐B∨┐C)
?┐B↓┐C
┐(B↓C)
?┐(┐B∧┐C)
?┐B↑┐C
(6)解：联结词“↑”和“↓”不满足结合律。举例如下：
a)给出一组指派：P为T，Q为F，R为F，则(P↑Q)↑R为T，P↑(Q↑R)为F
故 (P↑Q)↑R P↑(Q↑R).
b)给出一组指派：P为T，Q为F，R为F，则(P↓Q) ↓R为T，P↓(Q↓R)为F
故(P↓Q)↓R P↓(Q↓R).
?
?
(7)证明：
设变元P，Q，用连结词?,┐作用于P，Q得到：P，Q，┐P，┐Q，P?Q，P?P，Q?Q，Q?P。但P?Q?Q?P，P?P?Q?Q，故实际有：
P，Q，┐P，┐Q，P?Q，P?P（T）（A）
用┐作用于（A）类，得到扩大的公式类（包括原公式类）：
P，Q，┐P，┐Q，┐（P?Q）， T，F， P?Q （B）
用?作用于（A）类，得到：
P?Q，P?┐P?F，P?┐Q?┐（P?Q），P?（P?Q）?Q，P?（P?P）?P，
Q?┐P?┐（P?Q），Q?┐Q?F，Q?（P?Q）?P，Q?T?Q,
┐P?┐Q?P?Q，┐P?（P?Q）?┐Q，┐P?T?┐P,
┐Q?（P?Q）?┐P，┐Q?T?┐Q,
（P?Q）?（P?Q）?P?Q.
因此，（A）类使用运算后，仍在（B）类中。
对（B）类使用┐运算得：
┐P，┐Q，P，Q， P?Q， F，T，
┐（P?Q），
仍在（B）类中。
对（B）类使用?运算得：
P?Q，P?┐P?F，P?┐Q?┐（P?Q），P?┐（P?Q）?┐Q，P?T?P，P?F?┐P，P?（P?Q）?Q，
Q?┐P?┐（P?Q），Q?┐Q?F，Q?┐（P?Q）?┐P，Q?T?Q, Q?F?┐Q， Q?（P?Q）?P，
┐P?┐Q?P?Q，┐P?┐（P?Q）?Q，┐P?T?┐P, ┐P?F?P,┐P?（P?Q）?┐Q，
┐Q?┐（P?Q）?P，┐Q?T?┐Q, ┐Q?T?┐Q,┐Q?（P?Q）?┐P，
┐（P?Q）?T?┐（P?Q），┐（P?Q）?F?P?Q，┐（P?Q）?（P?Q）?F
T?F?F，T?（P?Q）? P?Q
F?（P?Q）?┐（P?Q）
（P?Q）?（P?Q）?P?Q.
故由（B）类使用?运算后，结果仍在（B）中。
由上证明：用?,┐两个连结词，反复作用在两个变元的公式中，结果只能产生（B）类中的公式，总共仅八个不同的公式，故{?,┐}
已证{┐（P?Q），故任何命题公式中的联结词，
┐}表达，则必可用{?,
┐}也必不是最小联结
词组。
(8)证明{∨}，{∧}和{→}不是最小联结词组。
证明：若{∨}，{∧}和{→}是最小联结词，则
┐P?（P∨P∨……）
┐P?（P∧P∧……）
┐P?P→(P→(P→……)
对所有命题变元指派T，则等价式左边为F，右边为T，与等价表达式矛盾。
所以{∨}，{∧}和{→}不是最小联结词。
(9)证明{┐,→}和{┐, }是最小联结词组。
证明：因为{┐,∨}为最小联结词组，且P∨Q?┐P→Q
所以{┐,→}是功能完备的联结词组，又{┐},{→}都不是功能完备的联结词组。
所以{┐,→}是最小联结词组。
又因为P→Q?┐(P Q)，所以{┐, }是功能完备的联结词组，又{┐},{ }不是功能完备的
联结词组，
所以{┐, }是最小联结词组。
习题 1-7
(1) 解：
P∧(P→Q)
?P∧(┐P∨Q)
?(P∧┐P)∨(P∧Q)
P∧(P→Q)
?(P∨(┐Q∧Q))∧(┐P∨Q)
?(P∨┐Q)∧(P∨Q)∧(┐P∨Q)
(2) 解：
a)(┐P∧Q)→R
?┐(┐P∧Q)∨R
?P∨┐Q∨R
?(P∧Q)∨(P∧┐Q)∨(┐Q∧R)∨(┐Q∧┐R)∨(R∧P)∨(R∧┐P)
b)P→((Q∧R)→S)
?┐P∨(┐(Q∧R)∨S)
?┐P∨┐Q∨┐R∨S
?(┐P∧Q)∨(┐P∧┐Q)∨(┐Q∧R)∨(┐Q∧┐R)∨(┐R∧S)∨(┐R∧┐S)∨(S∧P)∨(
→
c
→
c
→
c
→
c
→
c
S∧┐P)
c)┐(P∨┐Q)∧(S→T)
?(┐P∧Q)∧(┐S∨T)
?(┐P∧Q∧┐S)∨(┐P∧Q∧T)
d)(P→Q)→R
?┐(┐P∨Q)∨R
?(P∧┐Q)∨R
?(P∨R)∧(┐Q∨R)
e)┐(P∧Q)∧(P∨Q)
?(┐P∨┐Q)∧(P∨Q)
?(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q)
?(┐P∧Q)∨(┐Q∧P)
(3) 解：
a)P∨(┐P∧Q∧R)
?(P∨┐P)∧(P∨Q)∧(P∨R)
?(P∨Q)∧(P∨R)
b)┐(P→Q)∨(P∨Q)
?┐(┐P∨Q)∨(P∨Q)
?(P∧┐Q)∨(P∨Q)
?(P∨P∨Q)∧(┐Q∨P∨Q)
c)┐(P→Q)
?┐(┐P∨Q)
?P∧┐Q
?(P∨Q)∧(P∨┐Q)∧(┐Q∨┐P)
d)(P→Q)→R
?┐(┐P∨Q)∨R
?(P∧┐Q)∨R
?(P∨R)∧(┐Q∨R)
e)(┐P∧Q)∨(P∧┐Q)
?(┐P∨P)∧(┐P∨┐Q)∧(Q∨P)∧(Q∨┐Q)
?(┐P∨┐Q)∧(Q∨P)
(4) 解：
a)(┐P∨┐Q)→(P?┐Q)
?┐(┐P∨┐Q) ∨(P?┐Q)
?(P∧Q) ∨(P∧┐Q)∨(┐P∧Q)
?∑1，2，3
?P∨Q=∏0
b)Q∧(P∨┐Q)
? (P∧Q)∨(Q∧┐Q)
? P∧Q =∑3
?∏0，1，2
?(P∨Q)∧(P∨┐Q) ∧(┐P∨Q)
c)P∨(┐P→(Q∨(┐Q→R))
?P∨(P∨(Q∨(Q∨R))
?P∨Q∨R=∏0
?∑1，2，3,4,5,6,7
=(┐P∧┐Q∧R) ∨(┐P∧Q∧┐R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R)
∨(P∧Q∧┐R)∨(P∧Q∧R)
d)(P→(Q∧R) )∧(┐P→(┐Q∧┐R))
?(┐P∨(Q∧R)) ∧(P∨(┐Q∧┐R))
?(P∧┐P) ∨(P∧(Q∧R)) ∨ ((┐Q∧┐R) ∧┐P) ∨((┐Q∧┐R) ∧(Q∧R))
?(P∧Q∧R) ∨(┐P∧┐Q∧┐R) =∑0,7
?∏1，2，3,4,5,6
?(P∨Q∨┐R) ∧(P∨┐Q∨R) ∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R) ∧(┐P∨Q∨┐R)
∧(┐P∨┐Q∨R)
e)P→(P∧(Q→P)
?┐P∨(P∧(┐Q∨P)
?(┐P∨P)∧(┐P∨┐Q∨P)
?T∨(T∧┐Q) ?T
?∑0,1,2,3= (┐P∧┐Q) ∨(┐P∧Q) ∨(P∧┐Q) ∨(P∧Q)
f)(Q→P) ∧(┐P∧Q)
?(┐Q∨P) ∧┐P∧Q
?(┐Q∨P) ∧┐(P∨┐Q) ?F
?∏0,1，2，3= (P∨Q) ∧(P∨┐Q) ∧(┐P∨Q) ∧(┐P∨┐Q)
(5) 证明：
a)
(A→B) ∧(A→C)
?(┐A∨B) ∧(┐A∨C)
A→(B∧C)
?┐A∨(B∧C)
?(┐A∨B) ∧(┐A∨C)
b)
(A→B) →(A∧B)
?┐(┐A∨B) ∨(A∧B)
?(A∧┐B) ∨(A∧B)
?A∧(B∨┐B)
?A∧T
?A
(┐A→B) ∧(B→A)
?(A∨B) ∧(┐B∨A)
?A∨(B∧┐B)
?A∨F
?A
c)
A∧B∧(┐A∨┐B)
?((A∧┐A)∨(A∧┐B))∧B ?A∧B∧┐B
?F
┐A∧┐B∧(A∨B)
?((┐A∧A)∨(┐A∧B))∧┐B ?┐A∧┐B∧B
?F
d)
A∨(A→(A∧B)
?A∨┐A∨(A∧B)
?T
┐A∨┐B∨(A∧B)
?┐(A∧B) ∨(A∧B)
?T (6)解：A?R↑(Q∧┐(R↓P)),则A*?R↓(Q∨┐(R↑P))
A?R↑(Q∧┐(R↓P))
?┐(R∧(Q∧(R∨P)))
?┐R∨┐Q∨┐(R∨P)
?┐(R∧Q) ∨┐(R∨P)
A*?R↓(Q∨┐(R↑P))
?┐(R∨(Q∨(R∧P))
?┐R∧┐Q∧┐(R∧P)
?┐(R∨Q) ∧┐(R∧P)
(7) 解：设A：A去出差。B：B去出差。C：C去出差。D：D去出差。
若A去则C和D中要去一个。A→(C V D)
B和C不能都去。┐(B∧C)
C去则D要留下。C→┐D
按题意应有：A→(C V D)，┐(B∧C)，C→┐D必须同时成立。
因为C V D ?(C∧┐D) ∨(D∧┐C)
故(A→(C V D))∧┐(B∧C) ∧(C→┐D)
?(┐A∨(C∧┐D) ∨(D∧┐C)) ∧┐(B∧C) ∧(┐C∨┐D)
?(┐A∨(C∧┐D) ∨(D∧┐C)) ∧(┐B∨┐C) ∧(┐C∨┐D)
?(┐A∨(C∧┐D) ∨(D∧┐C)) ∧((┐B∧┐C) ∨(┐B∧┐D) ∨(┐C∧┐D) ∨┐C)?(┐A∧┐B∧┐C) ∨(┐A∧┐B∧┐D) ∨(┐A∧┐C∧┐D) ∨(┐A∧┐C)
∨(┐B∧┐C∧D) ∨(┐C∧D∧┐B∧┐D)∨(┐C∧D∧┐C∧┐D)
∨(┐C∧D∧┐C) ∨(┐D∧C∧┐B∧┐C) ∨(┐D∧C∧┐B∧┐D)
∨(┐D∧C∧┐C∧┐D) ∨(┐D∧C∧┐C)
在上述的析取范式中，有些（画线的）不符合题意，舍弃，得
(┐A∧┐C) ∨(┐B∧┐C∧D) ∨（┐C∧D）∨(┐D∧C∧┐B)
故分派的方法为：B∧D ,或D∧A,或C∧A。
(8)解：设P：A是第一。Q：B是第二。R：C是第二。S：D是第四。E：A是第二。
由题意得 (P V Q) ∧(R V S) ∧(E V S)
?((P∧┐Q) ∨(┐P∧Q)) ∧((R∧┐S) ∨(┐R∧S)) ∧((E∧┐S) ∨(┐E∧S)) ?((P∧┐Q∧R∧┐S) ∨(P∧┐Q∧┐R∧S) ∨(┐P∧Q∧R∧┐S)
∨(┐P∧Q∧┐R∧S))∧((E∧┐S)∨(┐E∧S))
因为(P∧┐Q∧┐R∧S)与(┐P∧Q∧R∧┐S)不合题意，所以原式可化为
((P∧┐Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S) ∨(┐E∧S))
?(P∧┐Q∧R∧┐S∧E∧┐S) ∨(P∧┐Q∧R∧┐S∧┐E∧S)
∨(┐P∧Q∧┐R∧S∧E∧┐S)∨(┐P∧Q∧┐R∧S∧┐E∧S)
?(P∧┐Q∧R∧┐S∧E) ∨(┐P∧Q∧┐R∧S∧┐E)
因R与E矛盾，故┐P∧Q∧┐R∧S∧┐E为真，
即A不是第一，B是第二，C不是第二，D为第四，A不是第二。
于是得：A是第三B是第二C是第一D是第四。
习题1-8
(1)证明：
a)┐(P∧┐Q)，┐Q∨R，┐R?┐P
(1) ┐R P
(2) ┐Q∨R P
(3) ┐Q (1)(2)T,I
(4) ┐(P∧┐Q) P
(5) ┐P∨Q (4)T,E
(6) ┐P (3)(5)T,I
b)J→(M∨N)，(H∨G)→J，H∨G?M∨N
(1) (H∨G) →J P
(2) (H∨G) P
(3) J (1)(2)T,I
(4) J→(M∨N) P
(5) M∨N (3)(4)T,I
c)B∧C，(B?C)→(H∨G)?G∨H
(1) B∧C P
(2) B (1)T,I
(3) C (1)T,I
(4) B∨┐C (2)T,I
(5) C∨┐B (3)T,I
(6) C→B (4)T,E
(7) B→C (5)T,E
(8) B?C (6)(7)T,E
(9) (B?C) →(H∨G) P
(10) H∨G (8)(9)T,I
d)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S)?┐S
(1) (┐Q∨R) ∧┐R
(2) ┐Q∨R (1)T,I
(3) ┐R (1)T,I
(4) ┐Q (2)(3)T,I
(5) P→Q P
(6) ┐P (4)(5)T,I
(7) ┐(┐P∧┐S) P
(8) P∨┐S (7)T,E
(9) ┐S (6)(8)T,I
(2) 证明：
a)┐A∨B，C→┐B?A→┐C
(1) ┐(A→┐C) P
(2) A (1)T,I
(3) C (1)T,I
(4) ┐A∨B P
(5) B (2)(4)T,I
(6) C→┐B P
(7) ┐B (3)(6)T,I
(8) B∧┐B 矛盾。(5),(7)
b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E)?A→(B→F)
(1) ┐(A→(B→F)) P
(2) A (1)T,I
(3) ┐(B→F) (1)T,I
(4) B (3)T,I
(5) ┐F (3)T,
(6) A→(B→C) P
(7) B→C (2)(6)T,I
(8) C (4)(7)T,I
(9) ┐F→(D∧┐E) P
(10) D∧┐E (5)(9)T,I
(11) D (10)T,I
(12) C∧D (8)(11)T,I
(13) (C∧D) →E P
(14) E (12)(13)T,I
(15) ┐E (10)T,I
(16) E∧┐E 矛盾。(14),(15)
c)A∨B→C∧D，D∨E→F?A→F
(1) ┐(A→F) P
(2) A (1)T,I
(3) ┐F (1)T,I
(4) A∨B (2)T,I
(5) (A∨B) →C∧D P
(6) C∧D (4)(5)T,I
(7) C (6)T,I
(8) D (6)T,I
(9) D∨E (8)T,I
(10) D∨E→F P
(11) F (9)(10)T,I
(12) F∧┐F 矛盾。(3),(11)
d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)?B→E
(1) ┐(B→E) P
(2) B (1)T,I
(3) ┐E (1)T,I
(4) ┐B∨D P
(5) D (2)(4)T,I
(6) (E→┐F) →┐D P
(7) ┐(E→┐F) (5)(6)T,I
(8) E (7)T,I
(9) E∧┐E 矛盾
e)(A→B)∧(C→D)，(B→E)∧(D→F)，┐(E∧F)，A→C?┐A
(1) (A→B) ∧(C→D) P
(2) A→B (1)T,I
(3) (B→E) ∧(D→F) P
(4) B→E (3)T,I
(5) A→E (2)(4)T,I
(6) ┐(E∧F) P
(7) ┐E∨┐F (6)T,E
(8) E→┐F (7)T,E
(9) A→┐F (5)(8)T,I
(10) C→D (1)T,I
(11) D→F (3)T,I
(12) C→F (10)(10)T,I
(13) A→C P
(14) A→F (13)(12)T,I
(15) ┐F→┐A (14)T,E
(16) A→┐A (9)(15)T,I
(17) ┐A∨┐A (16)T,E
(18) ┐A (17) T,E
(3)证明：
a)┐A∨B，C→┐B?A→┐C
(1) A P
(2) ┐A∨B P
(3) B (1)(2)T,I
(4) C→┐B P
(5) ┐C (3)(4)T,I
(6) A→┐C CP
b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E)?A→(B→F)
(1) A P
(2) A→(B→C) P
(3) B→C (1)(2)T,I
(4) B P
(5) C (3)(4)T,I
(6) (C∧D) →E P
(7) C→(D→E) (6)T,E
(8) D→E (5)(7)T,I
(9) ┐D∨E (8)T,E
(10) ┐(D∧┐E) (9)T,E
(11) ┐F→(D∧┐E) P
(12) F (10)(11)T,I
(13) B→F CP
(14) A→(B→F) CP
c)A∨B→C∧D，D∨E→F?A→F
(1) A P
(2) A∨B (1)T,I
(3) A∨B→C∨D P
(4) C∧D (2)(3)T,I
(5) D (4)T,I
(6) D∨E (5)T,I
(7) D∨E→F P
(8) F (6)(7)T,I
(9) A→F CP
d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)?B→E
(1) B P(附加前提)
(2) ┐B∨D P
(3) D (1)(2)T,I
(4) (E→┐F)→┐D P
(5) ┐(E→┐F) (3)(4)T,I
(6) E (5)T,I
(7) B→E CP
(4)证明：
a)R→┐Q，R∨S，S→┐Q，P→Q?┐P
(1) R→┐Q P
(2) R∨S P
(3) S→┐Q P
(4) ┐Q (1)(2)(3)T,I
(5) P→Q P
(6) ┐P (4)(5)T,I
b)S→┐Q，S∨R，┐R，┐P?Q?P
证法一：
(1) S∨R P
(2) ┐R P
(3) S (1)(2)T,I
(4) S→┐Q P
(5) ┐Q (3)(4)T,I
(6) ┐P?Q P
(7)(┐P→Q)∧(Q→┐P) (6)T,E
(8) ┐P→Q (7)T,I
(9) P (5)(8)T,I
证法二：（反证法）
(1) ┐P P（附加前提）
(2) ┐P?Q P
(3)（┐P→Q）∧（ Q→┐P） (2)T，E
(4) ┐P→Q (3)T,I
(5) Q (1)(4)T,I
(6) S→┐Q P
(7) ┐S (5)(6)T,I
(8) S∨R P
(9) R (7)(8)T,I
(10) ┐R P
(11) ┐R∧R 矛盾（9）（10）T，I
c)┐(P→Q)→┐(R∨S)，((Q→P)∨┐R)，R?P?Q
(1) R P
(2) (Q→P) ∨┐R P
(3) Q→P (1)(2)T,I
(4)┐(P→Q) →┐(R∨S) P
(5) (R∨S) →(P→Q) (4)T,E
(6) R∨S (1)T,I
(7) P→Q (5)(6)
(8) (P→Q) ∧(Q→P) (3)(7)T,I
(9) P?Q (8)T,E
(5) 解：
a)设P：我跑步。Q：我很疲劳。
前提为：P→Q，┐Q
(1) P→Q P
(2) ┐Q P
(3) ┐P (1)(2)T,I
结论为：┐P，我没有跑步。
b)设S：他犯了错误。 R：他神色慌张。
前提为：S→R，R
因为（S→R）∧R?（┐S∨R）∧R?R。故本题没有确定的结论。
实际上，若S →R为真，R为真,则S可为真，S也可为假，故无有效结论。
c)设P：我的程序通过。 Q：我很快乐。
R：阳光很好。 S：天很暖和。（把晚上十一点理解为阳光不好）
前提为：P→Q，Q→R，┐R∧S
(1) P→Q P
(2) Q→R P
(3) P→R (1)(2)T,I
(4) ┐R∨S P
(5) ┐R (4)T,I
(6) ┐P (3)(5)T,I
结论为：┐P，我的程序没有通过
习题2-1,2-2
（1）解：
a)设W（x）：x是工人。c：小张。
则有?W（c）
b)设S（x）：x是田径运动员。B（x）：x是球类运动员。h：他
则有 S（h）∨B（h）
c) 设C（x）：x是聪明的。B（x）：x是美丽的。l：小莉。
则有 C（l）∧ B（l）
d）设O（x）：x是奇数。
则有 O（m）→? O（2m）。
e)设R（x）：x是实数。Q（x）：x是有理数。
则有（?x）（Q（x）→R（x））
f) 设R（x）：x是实数。Q（x）：x是有理数。
则有（?x）（R（x）∧Q（x））
g) 设R（x）：x是实数。Q（x）：x是有理数。
则有?（?x）（R（x）→Q（x））
h)设P（x，y）：直线x平行于直线y
G（x，y）：直线x相交于直线y。
则有 P（A，B） ?G（A，B）
（2）解：
a)设J(x)：x是教练员。L(x)：x是运动员。
则有（?x）（J（x）→L（x））
b)设S(x)：x是大学生。L(x)：x是运动员。
则有（?x）（L（x）∧S（x））
c)设J(x)：x是教练员。O(x)：x是年老的。V（x）：x是健壮的。
则有（?x）（J（x）∧O（x）∧V（x））
d)设O(x)：x是年老的。V（x）：x是健壮的。j：金教练
则有? O（j）∧?V（j）
e)设L(x)：x是运动员。J(x)：x是教练员。
则?（?x）（L（x）→J（x））
本题亦可理解为：某些运动员不是教练。
故（?x）（L（x）∧?J（x））
f)设S（x）：x是大学生。L（x）：x是运动员。C（x）：x是国家选手。
则有（?x）（S（x）∧L（x）∧C（x））
g)设C（x）：x是国家选手。V（x）：x是健壮的。
则有（?x）（C（x）→V（x））或?（?x）（C（x）∧?V（x））
h)设C（x）：x是国家选手。O（x）：x是老的。L（x）：x 是运动员。
则有（?x）（O（x）∧C（x）→L（x））
i) 设W（x）：x是女同志。H（x）：x是家庭妇女。C（x）：x是国家选手。
则有?（?x）（W（x）∧C（x）∧H（x））
j）W（x）：x是女同志。J（x）：x是教练。C（x）：x是国家选手。
则有（?x）（W（x）∧J（x）∧C（x））
k）L（x）：x 是运动员。J（y）：y是教练。A(x,y)：x钦佩y。
则有（?x）（L（x）→（?y）（J（y）∧A（x，y）））
l）设S（x）：x是大学生。L（x）：x 是运动员。A(x,y)：x钦佩y。
则（?x）（S（x）∧（?y）（L（y）→? A(x,y)））
习题2-3
（1）解：
a）5是质数。
b）2是偶数且2是质数。
c）对所有的x，若x能被2除尽，则x是偶数。
d）存在x，x是偶数，且x能除尽6。（即某些偶数能除尽6）
e）对所有的x，若x不是偶数，则x不能被2除尽。
f）对所有的x，若x是偶数，则对所有的y，若x能除尽y，则y也是偶数。
g）对所有的x，若x是质数，则存在y，y是偶数且x能除尽y（即所有质数能除尽某些偶数）。
h）对所有的x，若x是奇数，则对所有y，y是质数，则x不能除尽y（即任何奇数不能除尽任何质数）。
（2）解：（?x）(?y)((P(x)∧P(y)∧┐E(x,y)→(?!z)(L(z)∧R(x,y,z)))
或（?x）(?y)((P(x)∧P(y)∧┐E(x,y)→(?z)(L(z)∧R(x,y,z) ∧┐(?u)(┐E(z,u) ∧L(u)∧R(x,y,u))))
（3）解：
a) 设N(x):x是有限个数的乘积。z(y):y为0。
P(x):x的乘积为零。F(y):y是乘积中的一个因子。
则有(?x)((N(x)∧P(x)→(?y)(F(y)∧z(y)))
b) 设R(x):x是实数。Q(x,y):y大于x。故(?x)(R(x)→(?y)(Q(x,y)∧R(y)))
c) R(x):x是实数。G(x,y):x大于y。则
(?x)(?y)(?z)(R(x)∧R(y)∧R(z)∧G(x+y,x·z)
（4）解：设G(x,y):x大于y。则有(?x)(?y)(?z)(G(y,x) ∧G(0,z)→G(x·z,y·z))
（5）解：设N(x):x是一个数。S(x,y):y是x的后继数。E(x,y)：x=y.则
a)(?x)(N(x)→(?!y)(N(y)∧S(x,y)))
或(?x)(N(x)→(?y)(N(y)∧S(x,y) ∧┐(?z)(┐E(y,z) ∧N(z)∧S(x,z))))
b) ┐(?x)(N(x)∧S(x,1))
c) (?x)(N(x)∧┐S(x,2)→(?!y)(N(y) ∧S(y,x)))
或(?x)(N(x)∧┐S(x,2)→(?y)(N(y) ∧S(y,x) ∧┐(?z)(┐E(y,z) ∧N(z)∧S(z,x))))（6）解：设S(x):x是大学生。E(x):x是戴眼睛的。
F(x):x是用功的。R(x,y):x在看y。
G(y):y是大的。K(y):y是厚的。J(y):y是巨著。a:这本。b:那位。
则有E(b)∧F(b)∧S(b)∧R(b,a)∧G(a)∧K(a)∧J(a)
（7）解：设P(x,y):x在y连续。Q(x,y):x>y。则
P(f,a) ((?ε)(?δ)(?x)(Q(ε,0)→(Q(δ,0)∧Q(δ,|x-a|)→Q(ε,|f(x)-f(a)|))))
习题2-4
(1) 解：a) x是约束变元，y是自由变元。
b) x是约束变元，P(x)∧Q(x)中的x受全称量词?的约束，S(x)中的x受存在量词?的约束。
c) x，y都是约束变元,P(x)中的x受?的约束，R(x)中的x受?的约束。
d) x，y是约束变元，z是自由变元。
(2)解：a) P(a)∧P(b)∧P(c)
b) R(a)∧R(b)∧R(c)∧S(a)∧S(b)∧S(c)
c) (P(a)→Q(a))∧(P(b)→Q(b))∧(P(c)→Q(c)
d) (┐P(a)∧┐P(b)∧┐P(c))∨(P(z)∧P(b)∧P(c))
e) (R(a)∧R(b)∧R(c))∧(S(a)∨S(b)∨S(c))
(3)解：
a) (?x)(P(x)∨Q(x))?(P(1)∨Q(1))∧(P(2)∨Q(2))，
但P(1)为T，Q(1)为F，P(2)为F，Q(2)为T,所以
(?x)(P(x)∨Q(x))?(T∨F)∧(F∨T) ?T。
b) (?x)(P→Q(x))∨R(a)?((P→Q(-2))∧(P→Q(3))∧(P→Q(6)))∨R(a)
因为P 为T，Q(-2)为T，Q(3)为T，Q(6)为F，R(5)为F，所以
(?x)(P→Q(x))∨R(a)? ((T→T)∧(T→T)∧(T→F))∨F? F
(4) 解：a) (?u)(?v)(P(u，z)→Q(v)) S(x，y)
b) (?u)(P(u)→ (R(u)∨Q(u))∧(?v)R(v))→(?z)S(x,z)
(5) 解：a) ((?y)A(u，y)→(?x)B(x，v))∧(?x)(?z)C(x，t，z)
b) ((?y)P(u，y)∧(?z)Q(u，z))∨(?x)R(x，t)
习题2-5
（1）解：a) P(a,f(a))∧P(b,f(b))?P(1,f(1))∧P(2,f(2))?P(1,2)∧P(2,1) ?T∧F?F
b) (?x)(?y)P(y,x)? (?x) (P(1,x)∨P(2,x))? (P(1,1)∨P(2,1))∧(P(1,2)∨P(2,2))
? (T∨F)∧(T∨F) ? T
c) (?x)( ?y)(P(x,y)→P(f(x),f(y)))
? (?x) ((P(x,1)→P(f(x),f(1)))∧(P(x,2) →P(f(x)f(2))))
?(P(1,1)→P(f(1),f(1)))∧(P(1,2)→P(f(1),f(2)))
∧(P(2,1)→P(f(2),f(1)))∧(P(2,2) →P(f(2),f(2)))
?(P(1,1)→P(2,2))∧(P(1,2)→P(2,1))∧(P(2,1)→P(1,2))∧(P(2,2)→P(1,1))
?(T→F∧(T→F)∧(F→T)∧(F→T)?F∧F∧T∧T?F
（2）解：a) (?x)(P(x)→Q(f(x),a))
?(P(1)→Q(f(1),1))∧(P(2)→Q(f(2),1))
?(F→Q(2,1))∧(T→Q(1,1))
?(F→F)∧(T→T) ?T
b) (?x)(P(f(x))∧Q(x,f(a))
? (P(f(1))∧Q(1,f(1)))∨(P(f(2))∧Q(2,f(1)) ? (T∧T)∨(F∧F) ?T
c) (?x)(P(x)∧Q(x,a))
? (P(1)∧Q(1,a))∨(P(2)∧Q(2,a))
? (P(1)∧Q(1,1))∨(P(2)∧Q(2,1))
? (F∧T)∨(T∧F) ?F
d) (?x)( ?y)(P(x)∧Q(x,y))
? (?x) (P(x)∧(?y)Q(x,y))
? (?x) (P(x)∧(Q(x,1)∨Q(x,2)))
? (P(1)∧(Q(1,1)∨Q(1,2)))∧(P(2)∧(Q(2,1)∨Q(2,2)))
? (F∧(T∨T))∧(T∧(F∨F)) ?F
(3) 举例说明下列各蕴含式。
a)?((?x)(P(x)∧Q(a))? (?x)P(x)→?Q(a)
b)(?x) (? P(x) →Q(x)), (?x) ?Q(x)?P(a)
c)(?x) (P(x) →Q(x)), (?x) (Q(x) →R(x))? (?x) (P(x) →R(x))
d)(?x) (P(x) ∨Q(x)), (?x) ?P(x)? (?x)Q (x)
e)(?x) (P(x) ∨Q(x)), (?x) ?P(x)? (?x)Q (x)
解：a）因为?((?x)(P(x)∧Q(a)) ??(?x)P(x)∨?Q(a)
故原式为?(?x)P(x)∨?Q(a) ? (?x)P(x)→?Q(a)
设P（x）：x是大学生。Q（x）：x是运动员
前提或者不存在x，x是大学生，或者a是运动员
结论如果存在x是大学生，则必有a是运动员。b)设P（x）：x是研究生。Q（x）：x是大学生。a：论域中的某人。
前提：对论域中所有x，如果x不是研究生则x是大学生。
对论域中所有x，x不是大学生。
结论：对论域中所有x都是研究生。
故，对论域中某个a，必有结论a是研究生，即P（a）成立。
c）设P（x）：x是研究生。Q（x）：x曾读过大学。R（x）：x曾读过中学。
前提对所有x，如果x是研究生，则x曾读过大学。
对所有x，如果x曾读过大学，则x曾读过中学。
结论：对所有x，如果x是研究生，则x曾读过中学。
d）设P（x）：x是研究生。Q（x）：x是运动员。
前提对所有x，或者x是研究生，或者x是运动员。
对所有x，x不是研究生
结论必存在x，x是运动员。
e）设P（x）：x是研究生。Q（x）：x是运动员。
前提对所有x，或者x是研究生，或者x是运动员。
对所有x，x不是研究生
结论对所有x，x是运动员。
（4）证明：(?x)(A(x)→B(x))? (?x) (┐A(x)∨B(x)) ? (?x)┐A(x)∨(?x) B(x)?┐(?x)A(x)∨(?x) B(x) ? (?x)A(x)→(?x) B(x)
（5）设论域D={a，b，c}，求证(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x))
证明：因为论域D={a，b，c}，所以
(?x)A(x)∨(?x)B(x) ?(A(a) ∧A(b) ∧A(c)) ∨(B(a) ∧B(b) ∧B(c))
?(A(a) ∨B(a)) ∧(A(a) ∨B(b)) ∧(A(a) ∨B(c)) ∧(A(b) ∨B(a)) ∧(A(b) ∨B(b)) ∧(A(b)∨B(c)) ∧(A(c) ∨B(a)) ∧(A(c) ∨B(b)) ∧(A(c) ∨B(c))
?(A(a) ∨B(a)) ∧(A(b) ∨B(b))∧(A(c) ∨B(c))
?( ?x)(A(x)∨B(x))
所以(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x))
（6）解：推证不正确，因为
┐(?x)(A(x)∧┐B(x))?┐((?x)A(x)∧(?x)┐B(x))
（7）求证(?x)( ?y)(P(x)→Q(y)) ? ( ?x)P(x)→(?y)Q(y)
证明：(?x)( ?y)(P(x)→Q(y))
?(?x)( ?y)( ┐P(x) ∨Q(y))
?(?x) ┐P(x) ∨( ?y)Q(y)
?┐(?x)P(x) ∨( ?y)Q(y)
? ( ?x)P(x)→(?y)Q(y)
习题2-6
（1）解：a) (?x)(P(x)→(?y)Q(x,y))
?(?x)( ┐P(x) ∨(?y)Q(x,y))
?(?x) (?y) (┐P(x) ∨Q(x,y))
b)(?x)(┐((?y)P(x,y))→((?z)Q(z)→R(x)))
?(?x)((?y)P(x,y)∨((?z)Q(z)→R(x)))
?(?x)((?y)P(x,y) ∨(┐(?z)Q(z) ∨R(x)))
?(?x)((?y)P(x,y) ∨((?z)┐Q(z) ∨R(x)))
?(?x) (?y) (?z) ( P(x,y) ∨┐Q(z) ∨R(x))
c)(?x)( ?y)(((?zP(x,y,z)∧(?u)Q(x,u))→(?v)Q(y,v))
?(?x)( ?y)( ┐((?z)P(x,y,z)∧(?u)Q(x,u))∨(?v)Q(y,v))
?(?x)( ?y)( (?z)┐P(x,y,z) ∨(?u)┐Q(x,u)∨(?v)Q(y,v))
?(?x)( ?y)( (?z)┐P(x,y,z) ∨(?u)┐Q(x,u)∨(?v)Q(y,v))
?(?x)( ?y) (?z) (?u) (?v) (┐P(x,y,z) ∨┐Q(x,u)∨Q(y,v)) （2）解：a)((?x)P(x)∨(?x)Q(x))→(?x)(P(x)∨Q(x))
?┐((?x)P(x)∨(?x)Q(x))∨(?x)(P(x)∨Q(x))
?┐(?x) (P(x)∨Q(x))∨(?x)(P(x)∨Q(x))?T
b)(?x)(P(x)→(?y)((?z)Q(x,y)→┐(?z)R(y,x)))
?(?x)(┐P(x)∨(?y)( Q(x,y)→┐R(y,x)))
?(?x) (?y) (┐P(x)∨┐Q(x,y)∨┐R(y,x))
前束合取范式
?(?x) (?y)( (P(x)∧Q(x,y)∧R(y,x))
∨(P(x)∧Q(x,y)∧┐R(y,x))
∨(P(x)∧┐Q(x,y)∧R(y,x))
∨(┐P(x)∧Q(x,y)∧R(y,x))
∨(┐P(x)∧┐Q(x,y)∧R(y,x))
∨( (P(x)∧┐Q(x,y)∧┐R(y,x))
∨(┐P(x)∧Q(x,y)∧┐R(y,x)))
前束析取范式
c)(?x)P(x)→(?x)((?z)Q(x,z)∨(?z)R(x,y,z))
?┐(?x)P(x)∨(?x)((?z)Q(x,z)∨(?z)R(x,y,z))
?(?x)┐P(x)∨(?x)((?z)Q(x,z)∨(?u)R(x,y,u))
?(?x)(┐P(x)∨(?z)Q(x,z)∨(?u)R(x,y,u))
?(?x) (?z) (?u)(┐P(x)∨Q(x,z)∨R(x,y,u))
前束合取范式
?(?x) (?z) (?u)(( P(x)∧Q(x,z) ∧R(x,y,u))
∨(P(x)∧Q(x,z) ∧┐R(x,y,u))
∨(P(x)∧┐Q(x,z) ∧R(x,y,u))
∨(P(x)∧┐Q(x,z) ∧┐R(x,y,u))
∨(┐P(x)∧Q(x,z) ∧┐R(x,y,u))
∨(┐P(x)∧┐Q(x,z) ∧R(x,y,u))
∨(┐P(x)∧┐Q(x,z) ∧┐R(x,y,u)))
前束析取范式
d)(?x)(P(x)→Q(x,y))→((?y)P(y)∧(?z)Q(y,z))
?┐(?x)(┐P(x)∨Q(x,y))∨((?y)P(y)∧(?z)Q(y,z))
?(?x)(P(x)∧┐Q(x,y))∨((?u)P(u)∧(?z)Q(y,z))
?(?x) (?u) (?z) ((P(x)∧┐Q(x,y))∨(P(u)∧Q(y,z)))
前束析取范式
?(?x) (?u) (?z) ((P(x)∨P(u)) ∧(P(x)∨Q(y,z)) ∧(┐Q(x,y)∨P(u)) ∧(┐Q(x,y)∨Q(y,z)))
前束合取范式
习题2-7
(1)证明：
(2)a) ①(?x)(┐A(x)→B(x)) P
②┐A(u)→B(u) US①
③( ?x)┐B(x) P
④┐B(u) US③
⑤A(u)∨B(u) T②E
⑥A(u) T④⑤I
⑦( ?x)A(x) EG⑥
b) ①┐( ?x)(A(x)→B(x)) P（附加前提）
②( ?x)┐(A(x)→B(x)) T①E
③┐(A(c)→B(c)) ES②
④A(c) T③I
⑤┐B(c) T③I
⑥( ?x)A(x) EG④
⑦(?x)A(x)→(?x)B(x) P
⑧(?x)B(x) T⑥⑦I
⑨B(c) US⑧
⑩B(c)∧┐B(c) T⑤⑨矛盾
c）①(?x)(A(x)→B(x)) P
②A(u)→B(u) US①
③( ?x)(C(x)→┐B(x)) P
④C(u)→┐B(u) US③
⑤┐B(u) →┐A(u) T②E
⑥C(u)→┐A(u) T④⑤I
⑦(?x)(C(x)→┐A(x)) UG⑥
d) (?x)(A(x)∨B(x)),( ?x)(B(x)→┐C(x)),( ?x)C(x)? (?x)A(x)
①( ?x)(B(x)→┐C(x)) P
②B(u)→┐C(u) US①
③( ?x)C(x) P
④C(u) US③
⑤┐B(u) T②④I
⑥ (?x)(A(x)∨B(x)) P
⑦A(u)∨B(u) US
⑧A(u) T⑤⑦I
⑨(?x)A(x) UG⑧
(2) 证明：
a)①( ?x)P(x) P（附加前提）
②P(u) US①
③(?x)(P(x)→Q(x)) P
④P(u)→Q(u) US③
⑤Q(u) T②④I
⑥(?x)Q(x) UG⑤
⑦( ?x)P(x)→(?x)Q(x) CP b)因为(?x)P(x)∨(?x)Q(x)?┐(?x)P(x) →(?x)Q(x)
故本题就是推证(?x)(P(x)∨Q(x)) ?┐(?x)P(x) →(?x)Q(x)
①┐(?x)P(x) P（附加前提）
②( ?x)┐P(x) T①E
③┐P(c) ES②
④(?x)(P(x)∨Q(x)) P
⑤P(c)∨Q(c) ES④
⑥Q(c) T③⑤I
⑦( ?x) Q(x) EG⑥
⑧┐(?x)P(x) →(?x)Q(x) CP
(3)
解：a)设R（x）：x是实数。Q（x）：x是有理数。I（x）：x是整数。
本题符号化为：
(?x)(Q(x) →R(x)) ∧(?x)(Q(x)∧I(x)) ? (?x)(R(x)∧I(x))
①(?x)(Q(x)∧I(x)) P
②Q(c)∧I(c) ES①
③(?x)(Q(x) →R(x)) P
④Q(c) →R(c) US③
⑤Q(c) T②I
⑥ R(c) T④⑤I
⑦I(c) T②I
⑧R(c)∧I(c) T⑥⑦I
⑨(?x)(R(x)∧I(x)) EG⑧
b)设P（x）：x喜欢步行。Q（x）：x喜欢乘汽车。R（x）：x喜欢骑自行车本题符号化为：
(?x)(P(x) →┐Q(x)), (?x)(Q(x) ∨R(x)) , (?x) ┐R(x) ? (?x) ┐P(x)
①(?x) ┐R(x) P
②┐R (c) ES①
③(?x)(Q(x) ∨R(x)) P
④Q(c) ∨R(c) US③
⑤Q(c) T②④I
⑥ (?x)(P(x) →┐Q(x)) P
⑦P(c) →┐Q(c) US⑥
⑧┐P (c) T⑤⑦I
⑨(?x) ┐P(x) EG⑧
c) 每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。
设G（x）：x是大学生。L（x）：x是文科学生。P（x）：x是理工科学生。
S（x）：x是优秀生。c：小张。
本题符号化为：
(?x)(G(x) →L(x)∨P(x)), (?x)(G(x)∧S(x)), ┐P (c) , S(c) ?G(c) →L(c)
①G(c) P（附加前提）
②(?x)(G(x) →L(x)∨P(x))P
③G(c) →L(c)∨P(c)US②
④L(c)∨P(c)T①③I
⑤┐P (c) P
⑥ L(c) T④⑤I
⑦G(c) →L(c) CP
注意：本题推证过程中未用到前提(?x)(G(x)∧S(x))以及S(c)。主要是S（x）：x是优秀生，这个条件与其他前提的联系对证明结论没有影响，因S（x）与其他前提不矛盾，故本题的推证仍是有效的。
屈婉玲版离散数学课后习题答案【3】
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) xG ?，在（a）(b)中均为真命题。 (x 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ ?? x ? ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) F ?? x x→ (x ( H ) ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F y x G ? y ? ∧ x→ , ( )) ( H ) x ((y ( (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快
命题符号化为: ))),()(()((y x H x F x y G y →?∧?? 9.给定解释I 如下: (a) 个体域D 为实数集合R. (b) D 中特定元素=0. (c) 特定函数(x,y)=xy,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论 离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素； 7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}} 习题参考解答 习题 1、（3）P：银行利率降低 Q：股价没有上升 P∧Q （5）P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 Q P? （7）P：不识庐山真面目 Q：身在此山中 Q→P，或～P→～Q （9）P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 P→Q∧R ，Q→T 2、（1）T （2）F （3）F （4）T （5）F （6）T （7）F （8）悖论 习题 1（3） ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ → （4） ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不， 不， 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解：根据给定的条件有下述命题公式： （A →（CD ））∧～（B ∧C ）∧～（C ∧D ） （～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） （（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ） 习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （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是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为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) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表： 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式//最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （6）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p) 第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每 一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故 G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)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的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解：、- a)(┓P ∧R)→Q b)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的对边平行。 P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可 作为合式公式） b)是合式公式 c)不是合式公式（ d)） e)不是合式公式（R和S之间缺少联结词） f)是合式公式。 （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. 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 离散数学第四版课后答案 第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9）， （10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： 1-1，1-2 （1）解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)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的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨Q）→R (6) 解： a)P:天气炎热。Q:正在下雨。P∧Q b)P:天气炎热。R:湿度较低。P∧R c)R:天正在下雨。S:湿度很高。R∨S d)A:刘英上山。B:李进上山。A∧B e)M:老王是革新者。N:小李是革新者。M∨N f)L:你看电影。M:我看电影。┓L→┓M g)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. 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略 1.10．略 1.11．略 1.12．将下列, 并给出各命题的: (1)2+2＝4 当且仅 当3+3＝6. (2)2+2＝4 的充要 条件是3+3 6. (3)2+2 4 与3+3 ＝6 互为充要条件. (4)若2+24, 则 3+36, 反之亦然. (1)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. (2)p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (3) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为0. (4) p q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为1. 1.13．将下列命题符号化, 并给出各命题的真值:(1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p q 1. (2) q p 1. (3) p q 1. (4) p r 当p 0 时为真; p 1 时为假. 1.14．将下 列 . (1) 刘 晓月跑得快, 跳得高. (2) 老王是山东 人或河北人. (3)因为天气冷, 所以我穿了羽 绒服. (4)王欢与李乐组成一个 小组. (5)李辛与李末是兄弟. (6)王强与刘威都学 过法语. (7)他一面 吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他 迟到了. (12)2 与4 都是素数, 这是不对的. (13)“2或4 是素数, 这是不对的”是不对的. 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： 证明 设A 上定义的二元关系R 为： ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ① 对任意＜x,y ＞∈A ，因为x y =x y ，所以 ＜＜x,y ＞, ＜x,y ＞＞∈R 即R 是自反的。 ② 设＜x,y ＞∈A ，＜u,v ＞∈A ，若 ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ?u v =x y ?＜＜u,v ＞,＜x,y ＞＞∈R 即R 是对称的。 ③ 设任意＜x,y ＞∈A ，＜u,v ＞∈A ，＜w,s ＞∈A ，对 ＜＜x,y ＞, ＜u,v ＞＞∈R ∧＜＜u,v ＞, ＜w,s ＞＞∈R ?（x y =u v ）∧（u v =w s ）?x y =w s ?＜＜x,y ＞, ＜w,s ＞＞∈R 故R 是传递的，于是R 是A 上的等价关系。 3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使 离散数学课后习题答案(左孝凌版) １-1，１-2解： a)是命题，真值为T。 b)不是命题。 c)是命题,真值要根据具体情况确定。 d)不是命题。 e)是命题,真值为T。 f)是命题，真值为T。 g)是命题,真值为F。 h)不是命题。 i)不是命题。 （2）解: 原子命题:我爱北京天安门。 复合命题：如果不是练健美操,我就出外旅游拉。 （3）解: a)(┓P ∧R）→Q b)Ｑ→R c)┓P d)Ｐ→┓Q （4）解： a)设Q:我将去参加舞会。R：我有时间。Ｐ:天下雨。 Q (R∧┓P）:我将去参加舞会当且仅当我有时间和天不下雨。 b)设R：我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→Ｒ）∧(R→Ｑ)：一个数是奇数，则它不能被2整除并且一个数不能被2整除,则它是奇数。 (5) 解: a)设Ｐ：王强身体很好。Q：王强成绩很好。P∧Ｑ b)设P:小李看书。Q:小李听音乐。Ｐ∧Q c)设P:气候很好。Q：气候很热。P∨Ｑ d)设Ｐ：ａ和ｂ是偶数。Q:a+b是偶数。P→Q e)设Ｐ:四边形ＡBCD是平行四边形。Q ：四边形AＢCＤ的对边平行。P Q f)设Ｐ：语法错误。Q:程序错误。R：停机。(P∨ Q）→ R (6) 解: a)Ｐ:天气炎热。Ｑ：正在下雨。 P∧Ｑ b)P:天气炎热。R:湿度较低。P∧R c)R:天正在下雨。Ｓ:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N：小李是革新者。 M∨N f)L：你看电影。M:我看电影。┓Ｌ→┓Ｍ g)P:我不看电视。Q：我不外出。Ｒ:我在睡觉。Ｐ∧Q∧R h)P:控制台打字机作输入设备。Ｑ:控制台打字机作输出设备。P∧Q 1-3 (1)解：离散数学第三版课后习题答案
离散数学课后习题答案
离散数学习题解答
屈婉玲版离散数学课后习题答案【1】
吉林大学离散数学课后习题答案
离散数学课后习题答案(左孝凌版)
离散数学课后习题答案左孝凌版
离散数学课后答案
离散数学第四版课后标准答案
最新离散数学习题答案
离散数学课后习题答案_(左孝凌版)
离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案
离散数学最全课后答案(屈婉玲版)
离散数学习题详细答案
离散数学课后习题答案_(左孝
离散数学课后习题答案左孝凌版
- 离散数学课后习题答案(第一章)
- 离散数学课后习题答案(左孝凌版)
- 离散数学课后习题答案
- 离散数学课后习题答案-(左孝凌版)
- 离散数学课后习题答案
- 屈婉玲版离散数学课后习题答案【3】
- 离散数学课后习题答案_(左孝凌版)
- 离散数学(左孝凌)课后习题解答(详细)
- 离散数学课后习题答案-(左孝凌版)
- 离散数学课后习题答案(左孝凌版)
- 离散数学课后习题答案(第三章)
- 离散数学课后习题答案_(左孝
- 离散数学课后习题答案
- 离散数学答案屈婉玲版第二版课后答案
- 离散数学课后习题答案(左孝凌版)
- 离散数学课后习题答案第二章
- 离散数学课后习题答案.pdf
- 离散数学课后习题答案_(左孝凌版)
- 离散数学课后习题答案第一章
- 离散数学课后习题答案第三章