离散数学课后习题答案左孝凌版.docx
《离散数学课后习题答案左孝凌版.docx》由会员分享，可在线阅读，更多相关《离散数学课后习题答案左孝凌版.docx（32页珍藏版）》请在冰点文库上搜索。
离散数学课后习题答案左孝凌版
习题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）→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：
我热衷于玩扑克。
如果我学习，那么我数学不会不及格：
P→┐Q
如果我不热衷于玩扑克，那么我将学习:
┐R→P
但我数学不及格:
Q
因此我热衷于玩扑克。
R
即本题符号化为：
（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是素数
如果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∧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：
他得胜
原命题：
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）┐PP↓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）↑RP↑（Q↑R）.
b）给出一组指派：
P为T，Q为F，R为F，则（P↓Q）↓R为T，P↓（Q↓R）为F
故（P↓Q）↓RP↓（Q↓R）.
（7）证明：
设变元P，Q，用连结词,┐作用于P，Q得到：
P，Q，┐P，┐Q，PQ，PP，QQ，QP。
但PQQP，PPQQ，故实际有：
P，Q，┐P，┐Q，PQ，PP（T）（A）
用┐作用于（A）类，得到扩大的公式类（包括原公式类）：
P，Q，┐P，┐Q，┐（PQ），T，F，PQ（B）
用作用于（A）类，得到：
PQ，P┐PF，P┐Q┐（PQ），P（PQ）Q，P（PP）P，
Q┐P┐（PQ），Q┐QF，Q（PQ）P，QTQ,
┐P┐QPQ，┐P（PQ）┐Q，┐PT┐P,
┐Q（PQ）┐P，┐QT┐Q,
（PQ）（PQ）PQ.
因此，（A）类使用运算后，仍在（B）类中。
对（B）类使用┐运算得：
┐P，┐Q，P，Q，PQ，F，T，
┐（PQ），
仍在（B）类中。
对（B）类使用运算得：
PQ，P┐PF，P┐Q┐（PQ），P┐（PQ）┐Q，PTP，PF┐P，P（PQ）Q，
Q┐P┐（PQ），Q┐QF，Q┐（PQ）┐P，QTQ,QF┐Q，Q（PQ）P，
┐P┐QPQ，┐P┐（PQ）Q，┐PT┐P,┐PFP,┐P（PQ）┐Q，
┐Q┐（PQ）P，┐QT┐Q,┐QT┐Q,┐Q（PQ）┐P，
┐（PQ）T┐（PQ），┐（PQ）FPQ，┐（PQ）（PQ）F
TFF，T（PQ）PQ
F（PQ）┐（PQ）
（PQ）（PQ）PQ.
故由（B）类使用运算后，结果仍在（B）中。
由上证明：
用,┐两个连结词，反复作用在两个变元的公式中，结果只能产生（B）类中的公式，总共仅八个不同的公式，故{,┐}不是功能完备的，更不能是最小联结词组。
已证{,┐}不是最小联结词组，又因为PQ┐（PQ），故任何命题公式中的联结词，如仅用{,┐}表达，则必可用{,┐}表达，其逆亦真。
故{,┐}也必不是最小联结词组。
（8）证明{∨}，{∧}和{→}不是最小联结词组。
证明：
若{∨}，{∧}和{→}是最小联结词，则
┐P（P∨P∨……）
┐P（P∧P∧……）
┐PP→（P→（P→……）
对所有命题变元指派T，则等价式左边为F，右边为T，与等价表达式矛盾。
所以{∨}，{∧}和{→}不是最小联结词。
（9）证明{┐,→}和{┐,}是最小联结词组。
证明：
因为{┐,∨}为最小联结词组，且P∨Q┐P→Q
所以{┐,→}是功能完备的联结词组，又{┐},{→}都不是功能完备的联结词组。
所以{┐,→}是最小联结词组。
又因为P→Q┐（PQ），所以{┐,}是功能完备的联结词组，又{┐},{}不是功能完备的联结词组，
所以{┐,}是最小联结词组。
习题 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）∨（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）解：
AR↑（Q∧┐（R↓P））,则A*R↓（Q∨┐（R↑P））
AR↑（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
D）
B和C不能都去。
┐（B∧C）
C去则D要留下。
C→┐D
按题意应有：
A→（C
D），┐（B∧C），C→┐D必须同时成立。
因为C
D（C∧┐D）∨（D∧┐C）
故（A→（C
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
Q）∧（R
S）∧（E
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∨GM∨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，（BC）→（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）BC （6）（7）T,E
（9）（BC）→（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→┐BA→┐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
升级会员 