离散数学第1-2章参考答案-命题逻辑谓词逻辑

Page49第17题解：（1）令①P：李明学习努力；②Q：李明成绩好；③R：李明不热衷于玩扑克；（2）已知条件符号化，即①P→Q：如果李明学习努力，那么他成绩好；②R→P：如果李明不热衷于玩扑克，那么他就努力学习；（3）所求结论符号化，即①¬Q→¬R：李明成绩不好，所以李明热衷于玩扑克；（4）证明：原命题符号化为P→Q，R→P¬Q→¬R；①P→QP规则；②R→PP规则；③R→QT规则①②；④Q∨¬RT规则③；⑤¬Q→¬RT规则④；（5）得证。Page50第32题（2）解：P∨(¬P→(Q∨(¬Q→R)))；⇔P∨(P∨(Q∨(Q∨R)))；⇔P∨Q∨R；①主合取范式为：P∨Q∨R；因为P∨Q∨R⇔∏M0⇔∑m1,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)；Page50第32题（4）解：(P∧¬Q∧R)∨(¬P∧Q∧¬S)；⇔((P∧¬Q∧R)∧(S∨¬S))∨((¬P∧Q∧¬S)∧(R∨¬R))；⇔(P∧¬Q∧R∧S)∨(P∧¬Q∧R∧¬S)∨(¬P∧Q∧R∧¬S)∨(¬P∧Q∧¬R∧¬S)；①主析取范式为：(¬P∧Q∧¬R∧¬S)∨(¬P∧Q∧R∧¬S)∨(P∧¬Q∧R∧¬S)∨(P∧¬Q∧R∧S)⇔∑m4,6,10,11⇔∏M0,1,2,3,5,7,8,9,12,13,14,15；②主合取范式为：(¬P∨¬Q∨¬R∨¬S)∧(¬P∨¬Q∨¬R∨S)∧(¬P∨¬Q∨R∨¬S)∧(¬P∨¬Q∨R∨S)∧(¬P∨Q∨¬R∨S)∧(¬P∨Q∨R∨S)∧(P∨¬Q∨¬R∨¬S)∧(P∨¬Q∨¬R∨S)∧(P∨Q∨¬R∨¬S)∧(P∨Q∨¬R∨S)∧(P∨Q∨R∨¬S)∧(P∨Q∨R∨S)；Page50第32题（6）解：(P→Q)→(P∨R)；⇔¬(¬P∨Q)∨(P∨R)；⇔(P∧¬Q)∨(P∨R)；⇔(P∨R)∧(P∨¬Q∨R)；⇔((P∨R)∨(¬Q∧Q))∧(P∨¬Q∨R)；⇔(P∨¬Q∨R)∧(P∨Q∨R)∧(P∨¬Q∨R)；⇔(P∨¬Q∨R)∧(P∨Q∨R)；①主合取范式为：(P∨¬Q∨R)∧(P∨Q∨R)；⇔∏M0,2；⇔∑m1,3,4,5,6,7；①主合取范式为：(¬P∨¬Q∨R)∧(¬P∨Q∨R)∧(P∨¬Q∨¬R)∧(P∨¬Q∨R)∧(P∨Q∨¬R)∧(P∨Q∨R)；Page51第37题（2）解：P→QP→(P∧Q)①PP规则（附加前提）；②P→QP规则；③QT规则①，②，I；④P∧QT规则①，③，I；⑤P→(P∧Q)CP规则；Page51第37题（4）解：(P∨Q)→R(P∧Q)→R①P∧QP规则（附加前提）；②PT规则①，I；③P∨QT规则②，I；④(P∨Q)→RP规则；⑤RT规则③，④，I；⑥(P∧Q)→RCP规则；Page51第38题（3）解：﹁(P→Q)→﹁(R∨S),((Q→P)∨﹁R),RPQ①﹁(PQ)P规则（假设前提）；②﹁((P→Q)∧(Q→P))T规则①，I；③RP规则；④((Q→P)∨﹁R)P规则；⑤R→(Q→P)T规则④，I；⑥(Q→P)T规则③⑤，I；⑦R∨ST规则③，I；⑧﹁(P→Q)→﹁(R∨S)P规则；⑨(R∨S)→(P→Q)T规则⑧，I；⑩(P→Q)T规则⑦⑨，I；⑪(P→Q)∧(Q→P)T规则⑥⑩，I；⑫得证间接证明法②⑪；Page51第39题（1）解：（1）符号化已知命题①P：明天是晴天；②Q：明天下雨；③R：我去看电影；④S：我不看书；条件符号化：P∨Q，P→R，R→S；结论符号化：①﹁S→Q（2）证明：P∨Q，P→R，R→S﹁S→Q①P→RP规则；②R→SP规则；③P→ST规则①②；④﹁S→﹁PT规则③，I；⑤P∨QP规则；⑥﹁P→QT规则⑤，I；⑦﹁S→QT规则④⑥，I；Page51第39题（2）解：（1）符号化已知命题①P：明天不下雨；②Q：能够买到车票；③R：我去参观计算机展览会；条件符号化：P∧Q→R；结论符号化：①﹁R→﹁P（2）证明：P∨Q，P→R，R→S﹁S→Q①P∧Q→RP规则；②﹁RP规则（附加前提）；③﹁(P∧Q)T规则①②；④﹁P∨﹁QT规则③，I；⑤也就是说或者明天下雨或者买不到票，所以原命题说不能参加计算机展览的原因只是明天下雨是不完全的，故原命题无效。Page51第39题（3）解：（1）符号化已知命题①P：今天我没课；②Q：我去机房上机；③R：我去图书馆查资料；④S：机房没有空机器；条件符号化：P→(Q∨R)，S→﹁Q；结论符号化：①P∧S→R；（2）证明：P→(Q∨R)，S→﹁Q(P∧S)→R；①(P∧S)P规则（附加前提）；②PT规则①；③ST规则①；④P→(Q∨R)P规则；⑤(Q∨R)T规则②④；⑥S→﹁QP规则；⑦﹁QT规则③⑥；⑧RT规则⑤⑦；⑨得证CP规则。Page81第7题（2）解：(X)(P(X)∧Q(X))∨(X)R(X,Y)X的辖域为(P(X)∧Q(X))，其中X为约束变元；X的辖域为R(X,Y)，其中X为约束变元，Y为自由变元；Page81第7题（3）解：(X)(Y)(P(X,Y)∨Q(Y,Z))X的辖域为(Y)(P(X,Y)∨Q(Y,Z))，其中X为约束变元，Y、Z为自由变元；Y的辖域为(P(X,Y)∨Q(Y,Z))，其中Y为约束变元，X、Z为自由变元；Page82第16题（1）解：(X)(P(X)→(Y)Q(X,Y))⇔(X)(﹁P(X)∨(Y)Q(X,Y))⇔(X)(Y)(﹁P(X)∨Q(X,Y))Page82第16题（2）解：(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))Page82第16题（3）解：(X)(Y)((X)(P(X,Y,Z)∧(U)Q(X,U))→(U)Q(Y,U)⇔﹁(x)(y)((z)P(x,y,z)∧(u)Q(x,u))∨(u)Q(y,u)⇔(x)(y)(﹁(z)P(x,y,z)∨﹁(u)Q(x,u))∨(u)Q(y,u)⇔(x)(y)((z)﹁P(x,y,z)∨(u)﹁Q(x,u))∨(u)Q(y,u)⇔(x)(y)(z)(u)(﹁P(x,y,z)∨﹁Q(x,u))∨(r)Q(s,r)⇔(x)(y)(z)(u)(r)(﹁P(x,y,z)∨﹁Q(x,u)∨Q(s,r))18、（2）证明：1、（x）（P（x）∨Q（x））P2、P（y）∨Q（y）US（1）3、（x）┐P（x）P4、┐P（y）US（1）5、Q（y）T（2，4），I6、（x）Q（x）UG（5）（4）证明：1、（x）P（x）P2、P（a）ES（1）3、（x）Q（x）P4、Q（b）ES（3）5、（x）P（x）→（x）（（P（x）∨Q（x））→R（x））P6、┐（x）P（x）∨（x）（┐（P（x）∨Q（x））∨R（x））T（5），E7、（x）┐P（x）∨（x）（（┐P（x）∨R（x））∧（┐Q（x）∨R（x）））T（6），E8、┐P（a）∨（（┐P（a）∨R（a））∧（┐Q（b）∨R（b）））US（7）9、（┐P（a）∨R（a））∧（┐Q（b）∨R（b））T（2，8），I10、┐P（a）∨R（a）T（9），I11、R（a）T（2，10），I12、┐Q（b）∨R（b）T（9），I13、R（b）T（4，13），I14、R（a）∧R（b）T（11，13），I15、（x）（y）（R（x）∧R（y））EG（14）19、（1）证明：1、（x）┐B（x）P2、┐B（y）US（1）3、（x）（┐A（x）→B（x））P4、┐A（y）→B（y）US（3）5、┐┐A（y）∨B（y）T（4），E6、A（y）∨B（y）T（5），E7、A（y）T（2，6），I8、（x）A（x）EG（7）（3）证明：1、（x）C（x）P2、C（y）US（1）3、（x）（B（x）→┐C（x））P4、B（y）→┐C（y）US（3）5、C（y）→┐B（y）T（4），E6、┐B（y）T（3，5），I7、（x）（A（x）∨B（x））P8、A（y）∨B（y）US（7）9、A（y）T（6，8），I10、（x）（A（x））UG（9）22、（1）解：设P（x）：x是自然数；Q（x）：x是整数；R（x）：x是奇数；S（x）：x是偶数。则原命题可符号化为：（x）（P（x）→Q（x）），（x）（Q（x）→（R（x）∨S（x））），┐（x）（P（x）∧R（x）），（x）P（x）=（x）（P（x）∧S（x））证明：1、┐（x）（P（x）∧R（x））P2、（x）（┐P（x）∨┐R（x））T（1），E3、┐P（a）∨┐R（a）ES（2）4、（x）P（x）P5、P（a）US（4）6、┐R（a）T（3，5），I7、（x）（P（x）→Q（x））P8、P（a）→Q（a）US（7）9、（x）（Q（x）→（R（x）∨S（x）））P10、Q（a）→（R（a）∨S（a））US（9）11、P（a）→（R（a）∨S（a））T（8，10），I12、R（a）∨S（a）T（5，11），I13、S（a）T（6，12），I14、P（a）∧S（a）T（5，13），I15、（x）（P（x）∧S（x））EG（14）所以结论是前提的有效结论。（4）解：设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）证明：1、（x）┐R（x）P2、┐R（a）ES（1）3、（x）（Q（x）∨R（x））P4、Q（a）∨R（a）US（3）5、Q（a）T（2，4），I6、┐┐Q（a）T（5），E7、（x）（P（x）→┐Q（x））P8、P（a）→┐Q（a）US（7）9、┐P（a）T（6，8），I10、（x）┐P（x）EG（9）所以结论是前提的有效结论。