离散数学习题及解答.doc

《离散数学习题及解答.doc》由会员分享，可在线阅读，更多相关《离散数学习题及解答.doc（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. .作业题与解答第一章19(2)、(4)、(6)21(1)、(2)、(3)19、(2)解答:(pp)q真值表如下:pqpqpp(pp)q001111011010100101110001. .word. .19、(4)所以公式(pq)q为可满足式. .word. .解答:(pq)(qp)真值表如下:pqpqpqqp(pq)(qp)0011111011011110010011100111所以公式(pq)(qp)为永真式. .word. .19、(6)解答:(pq)(qr)(pr)真值表如下:pqrpqqrpr(pq)(qr)(pq)(qr)(pr)000111110011111101010101

2、0111111110001001101011011101000111111111所以公式(pq)(qr)(pr)为永真式21、(1)解答:(pq)r真值表如下:pqrprpq(pq)(pq)r0001101100110011010111010111010010001011101000111100101111100011所以成假赋值为:011. .word. .21、(2)解答:(qr)(pq)真值表如下:pqrqqrpq(qr)(pq)00011110011111010001001101111001100101110011000101110111所以成假赋值为:010,100,101,1102

3、1、(3)解答:(pq)(pr)p)真值表如下:pqrpqpr(pr)(pr)p(pq)(pr)p)0001011100110111010101110111011110000110101010101101011111111011所以成假赋值为:100,101. .word. .第二章5、(1)(2)(3)6、(1)(2)(3)7、(1)(2)8、(1)(2)(3)5、求以下公式的主析取X式,并求成真赋值(1)(pq)(qp)(pq)(qp)(p)q) (qp)(pq)(qp)(pq)(pq)(pq)m0 m2m3，所以00，10，11为成真赋值。(2)(pq)(qr)(pq)(qr)(pq)(

4、qr)(pqr)(qr)(pqr)(pqr)(pqr)(pqr)(pqr)m3m7，所以011，111为成真赋值。(3)(p(qr)(pqr)(p(qr)(pqr)(p(qr)(pqr)(pq)(pr)(pqr)(pq)(pr)(pqr)(pq)(ppqr)(rpqr)(pq)(11)(pq)1. .word. .1m0m1m2m3m4m5m6 m7，所以000,001,010,011,100,101,110,111为成真赋值。7、求以下公式的主析取X式，再用主析取X式求主合取X式(1)(pq)r(pqr)(pqr)(pr)(pr)(pqr)(pqr)(prq)(prq)(prq)(prq)(

5、pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7 由主析取X式和主合取X式之间的关系，所以公式的主合取X式为：(pq)rM0M2M4(2)(pq)(qr)(pq)(qr)(p(qr)(q(qr)(pq)(pr)(qq)(qr)(pq)(pr)(qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m3m7由主析取X式和主合取X式之间的关系，所以公式的. .word. .主合取X式为：(pq)(qr)M2M4M5M68、求以下公式的主合取X式，再用主合取X式求主析取X式(1)(pq)q(pq)q(pq)qp(qq)p

6、11该公式无主合取X式，所以公式的主析取X式为：(pq)qm0m1m2m3 (2)(pq)r(pq)(pq)r(pq)(pq)r(p(pq)(q(pq)r(pp)(pq)(qp)(qq)r(pq)(qp)r(pqr)(pqr)M0M6 由主合取X式和主析取X式之间的关系，所以公式的主析取X式为：(pq)rm1m2m3m4m5m7(3)(rp)pq(rp)pq(rp)pqr(pp)qr0q0. .word. .M0M1M2M3M4M5M6M7该公式无主析取X式第三章14(2)、(4)、(5)15(1)、(2)16(1)14、在自然推理系统P中构造下面推理的证明(2)前提：pq,(qr),r结论：

7、p证明：(qr)前提引入qr置换r前提引入q析取三段论pq前提引入p拒取式4前提：qp,qs,st,tr结论：pq证明：st前提引入(st)(ts)置换ts化简tr前提引入t化简s假言推理qs前提引入. .word. .(sq)(qs)置换sq化简q假言推理qp前提引入p假言推理pq合取5前提：pr,qs,pq结论：rs证明:pq前提引入p化简q化简pr前提引入r假言推理qs前提引入s假言推理rs合取15、在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p(qr),sp,q结论：sr证明：s附加前提引入. .word. .sp前提引入p假言推理p(qr)前提引入qr假言推理q前提引入

8、r假言推理(2)前提：(pq)(rs),(st)u结论：pu证明：p附加前提引入pq附加(pq)(rs)前提引入rs假言推理s化简st附加(st)u前提引入 u假言推理16、在自然推理系统P中用归谬法证明下面推理：(1)前提：pq,rq,rs结论：p证明:. .word. .p结论否认引入pq前提引入q假言推理rq前提引入r析取三段论rs前提引入r化简rr合取(矛盾)为矛盾式，由归谬法可知，推理正确。第四章5、(1)(2)(3)(4)10、(2)(4)11、(2)(6)5、在一阶逻辑中将以下命题符号化：(1)火车都比轮船快。xy(F(x)G(y)H(x,y)，其中，F(x)：x是火车，G(y)

9、：y是轮船，H(x,y):x比y快。(2)有的火车比有的汽车快。$x$y(F(x)G(y)H(x,y)，其中，F(x):x是火车，G(y)：y是汽车，H(x,y):x比y快。(3)不存在比所有火车都快的汽车。$x(F(x)y(G(y)H(x,y). .word. .或x(F(x)$y(G(y)H(x,y)，其中，F(x):x是汽车，G(y)：y是火车，H(x,y):x比y快。(4)说但凡汽车就比火车慢是不对的。xy(F(x)G(y)H(x,y) 或$x$y(F(x)G(y)H(x,y)，其中，F(x):x是汽车，G(y)：y是火车，H(x,y):x比y慢。10、给定解释I如下：a个体域D=NN

10、为自然数。bD中特定元素=2。cD上函数(x,y)=xy，(x,y)=xy。D上谓词(x,y)：x=y。(2)xy(F(f(x,a),y)F(f(y,a),x)xy(x+2=y)(y+2=x)，真值为0。(4)$xF(f(x,x),g(x,x)$x(x+x=xx),真值为1。11、判断以下各式的类型(2)x(F(x)F(x)$y(G(y)G(y) 此谓词公式前件永为真，而后件永为假，即公式为(10). .word. .,此公式为矛盾式，所以原谓词公式为矛盾式。(6)(xF(x)$yG(y)$yG(y) 此谓词公式是命题公式(pq)q的代换实例，而该命题公式是矛盾式，所以此谓词公式是矛盾式。第五

11、章15(1)(2)(3)(4)20 (1)(2)23(1)(2)15、在自然推理系统F中构造下面推理的证明：(1)前提:$xF(x)y(F(y)G(y)R(y),$xF(x) 结论：$xR(x)证明：$xF(x)y(F(y)G(y)R(y)(前提引入)$xF(x)(前提引入)y(F(y)G(y)R(y)(假言言推理)F(c)(EI规那么)F(c)G(c)R(c)(UI规那么F(c)G(c)(附加律)R(c)(假言言推理)$xR(x)(EG规那么) (2)前提：x(F(x)(G(a)R(x)，$xF(x). .word. .结论：$x(F(x)R(x)证明：$xF(x)前提引入F(c)$-x(F

12、(x)(G(a)R(x)前提引入F(c)(G(a)R(c)-G(a)R(c)假言推理R(c)化简F(c)R(c)合取$x(F(x)R(x)$+(3)前提：x(F(x)G(x)，$xG(x) 结论：$xF(x)证明:$xG(x)前提引入xG(x)置换G(c)-. .word. .x(F(x)G(x)前提引入. .word. .F(c)G(c)-F(c)析取三段论$xF(x)+(4)前提:x(F(x)G(y),x(G(x)R(x),xR(x) 结论：$xF(x). .word. .证明：xR(x)前提引入R(c)-x(G(x)R(x)前提引入G(c)R(c)-G(c)析取三段论x(F(x)G(y)

13、前提引入F(c)G(c)-F(c)析取三段论$xF(x)+20、在自然推理系统F中，构造下面推理的证明：(可以使用附加前提证明法)(1)前提：x(F(x)G(x) 结论：xF(x)xG(x)证明：xF(x)附加前提F(y)-x(F(x)G(x)前提引入F(y)G(y)-. .word. .G(y)假言推理xG(x)+ (2)前提：x(F(x)G(x)结论：xF(x)$xG(x)证明：xF(x)附加前提$xF(x)等值演算F(c)$-x(F(x)G(x)前提引入F(c)G(c)-G(c)析取三段论$xG(x)$+23、在自然推理系统F中，证明下面推理：(1)每个有理数都是实数，有的有理数是整数，

14、因此有的实数是整数。设F(x):x为有理数，R(x):x为实数，G(x):x是整数。前提：x(F(x)R(x)，$x(F(x)G(x) 结论：$x(R(x)G(x)证明：$x(F(x)G(x)前提引入F(c)G(c)$-F(c)化简. .word. .G(c)化简x(F(x)R(x)前提引入F(c)R(c)-R(c)假言推理R(c)G(c)合取$x(R(x)G(x)$+(2)有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不是无理数。设：F(x):x为有理数，G(x):x为无理数，R(x)为实数，H(x)为虚数前提：x(F(x)G(x)R(x),x(H(x)R(x) 结论：x(H

15、(x)(F(x)G(x)证明：x(F(x)G(x)R(x)前提引入F(y)G(y)R(y)-x(H(x)R(x)前提引入H(y)R(y)-R(y)(F(y)G(y)H(y)(F(y)G(y) H(y)(F(y)G(y)x(H(x)(F(x)G(x)置换假言三段论置换+. .word. .第六章31，32、(1)(2)(3)，41，42，4531、设A、B为任意集合，证明：(A-B)(B-A)=(AB)-(AB) 证明：由于(A-B)(B-A)=(AB)(BA)=(AB)B)(AB)A)=(AB)(BB)(AA)(BA)=(AB)(BA)=(AB)(BA)=(AB)(AB)=(AB)-(AB)

16、所以原式成立。32、设A、B、C为任意集合，证明：1(A-B)-C=A-(BC)证明：由于(A-B)-C= (AB)C=A(BC)=A(BC)= A (BC)所以原式成立。. .word. .2(A-B)-C=(A-C)-(B-C)证明：由于(A-C)-(B-C)=(AC)(BC)=(AC)(BC)= (AC)B)(AC)C)=(AC)B=(AB)C=(A-B)C=(A-B)-C所以原式成立。3(A-B)-C=(A-C)-B证明:由于(A-B)-C=(AB)C=(AC)B=(A-C)-B 所以原式成立。41、设A、B、C为任意集合，证明：ACBCA-CB-CAB 证明：xA(1)假设xC. .word. .所以xBC因此xB (2)假设xC那么xA-C，而A-CB-C 所以xB-C因此xB 综上所述，AB42、设A、B、C为任意集合，证明：AB=ACAB=ACB=C 证明：(1)先证BCxB假设xA那么xAB，而AB=AC 所以xAC因此xC假设xA. .word.