离散数学习题与解答.docx

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

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

2、1000111111111所以公式(pq)(qr)(pr)为永真式21、(1)解答:(pq)r 真值表如下:pqrprpq(pq)(pq)r0001101100110011010111010111010010001011101000111100101111100011所以成假赋值为:01121、(2)解答:(qr)(pq)真值表如下:pqrqqrpq(qr)(pq)00011110011111010001001101111001100101110011000101110111所以成假赋值为:010,100,101,11021、(3)解答:(pq)(pr)p)真值表如下:pqrpqpr(pr)(

3、pr)p(pq)(pr)p)0001011100110111010101110111011110000110101010101101011111111011所以成假赋值为:100,101第二章5、(1) (2) (3)6、(1) (2) (3)7、(1) (2)8、(1) (2) (3)5、求以下公式主析取范式,并求成真赋值(1)(pq)(qp)(pq) (qp)(p) q) (qp)(p q) (qp)(p q) (p q)(p q)m0 m 2m3，所以 00，10，11 为成真赋值。(2)(pq)(qr)(pq)(qr)(pq)(qr)(pqr)(qr)(pqr)(pqr)(pqr)(p

4、qr)(pqr)m3m 7，所以 011，111 为成真赋值。(3)(p(qr)(pqr)(p(qr)(pqr)(p (qr)(pqr)(pq)(pr)(pqr)(pq)(pr)(pqr)(pq)(ppqr)(rpqr) )(pq)(11)(pq)11m0m1m 2 m3m4m5m 6 m 7，所以 000, 001, 010, 011, 100, 101, 110, 111 为成真赋值。7、求以下公式主析取范式，再用主析取范式求主合取范式(1)(pq)r( pqr)( pqr)(pr)(pr)( pqr)( pqr)(prq)(prq)(prq)(prq)( pqr)( pqr)(pqr)(

5、pqr)(pqr)m1m3m5m6m7 由主析取范式和主合取范式之间关系，所以公式主合 取范式为：(pq)r M0M2M4(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由主析取范式和主合取范式之间关系，所以公式主合取范式为：(pq)(qr) M2M4M5M68、求以下公式主合取范式，再用主合取范式求主析取范式 (1) (pq)q(pq )q(pq )qp(qq)p11 该公式无主合取范式，所以公式 主析取范

6、式为：(pq)q m0m1m2m3 (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 由主合取范式和主析取范式之间关系，所以公式主析 取范式为：(pq)r m1m2m3m4m5m7(3) (rp)pq(rp)pq(rp)pqr(pp)qr0q0M0M1M2M3M4M5M6M7该公式无主析取范式第三章14(2)、(4)、(5)15(1)、(2)16(1)14、在自然推理系统 P 中构造下面推理证明 (2) 前提：pq, (qr), r结论：p证明：(qr)前提引入qr置换r前提引入q

7、析取三段论pq前提引入p拒取式4前提：qp, qs, st, tr结论：pq证明：st前提引入(st)(ts)置换ts化简tr前提引入t化简s假言推理qs前提引入(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附加前提引入sp前提引入p假言推理p(qr) 前提引入qr假言推理q前提引入r假言推理 (2) 前提：(pq)(rs), (s

8、t)u结论：pu证明：p附加前提引入pq附加(pq)(rs)前提引入rs假言推理s化简st附加(st)u前提引入 u假言推理16、在自然推理系统 P 中用归谬法证明下面推理： (1) 前提：pq, rq, rs结论：p证明: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)：y 是轮船，H(x,y):x 比

9、 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)或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

10、=NN 为自然数。b D 中特定元素 =2。c D 上函数(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),此公式为矛盾式，所以原谓词公式为矛盾式。(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)结论：$x(F

12、(x)R(x)证明： $xF(x)前提引入 F(c)$- x(F(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)-x(F(x)G(x)前提引入F(c)G(c)-F(c)析取三段论$xF(x)+(4) 前提: x(F(x)G(y), x(G(x)R(x), xR(x) 结论：$xF(x)证明：xR(x)前提引入 R(c)-x(G(x)R(x)前提引入G(c)R(c)-G(c)析

13、取三段论x(F(x)G(y)前提引入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)- 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 中，证明下

14、面推理： (1)每个有理数都是实数，有有理数是整数，因此有实数是整数。设 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)化简 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)为虚数

15、前提：x(F(x)G(x)R(x), x(H(x)R(x) 结论：x(H(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)置换假言三段论置换+第六章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)=(A

16、B)(BA)=(AB)(BA)=(AB)(AB)=(AB)-(AB) 所以原式成立。32、设 A、B、C 为任意集合，证明：1(A-B)-C=A-(BC)证明：由于 (A-B)-C = (AB)C= A(BC)= A(BC) = A (BC)所以原式成立。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、

17、B、C 为任意集合，证明： ACBC A-CB-C AB 证明：xA(1) 假设 xC所以 xBC因此 xB (2) 假设 xC那么 xA-C ，而 A-CB-C 所以 xB-C因此 xB 综上所述，AB42、设 A、B、C 为任意集合，证明： AB=ACAB=AC B=C 证明：(1)先证BCxB 假设 xA那么 xAB，而 AB=AC 所以 xAC因此 xC 假设 xA所以 xAC因此 xC 综上所述知 BC(2)再证 CB同理可证 所以 B=C45、设 A、B 为任意任意集合，证明：(1)P(A)P(B)=P(AB)(2)P(A)P(B)P(AB)(3)针对(2)举一反例，说明 P(A)

18、P(B)=P(AB)对某些集合A 和 B 是不成立。证明：(1) 先证P(A)P(B) P(AB)xP(A)P(B)那么 xP(A) xP(B) 所以 xA xB所以 x AB 所以 xP(AB)因此 P(A)P(B) P(AB)xP(AB)那么 x AB所以 xA xB所以 xP(A) xP(B) 所以 xP(A)P(B)因此 P(AB) P(A)P(B) 综上所述 P(AB) = P(A)P(B)(2) xP(A)P(B)那么 xP(A) xP(B) 所以 xA xB 假设 xA那么 x AB所以 xP(AB) 假设 xB那么 x AB所以 xP(AB)(3) 举例：令 A=1,B=2那么

19、 AB=1，2那么 P(A)=，1，P(B)=，2 而 P(AB)=，1,2,1,2显然 P(A)P(B)= P(AB)不成立.第七章20、25、32、36、38、40、41、42、48、49、5020、设 R1 R2 为 A 上关系，证明:2-1(1) (R1 R2)=R1-1 R -1-1-1-1(2) (R1 R2)=R1 R2-1证明:(1) (R1 R2)R1 R2R1R22R1-1R -1-1-1R1 R2-1-1-1所以(R1 R2)=R1 R2-1(2) (R1 R2)R1 R2R1R22R1-1R -1-1-1R1 R2-1-1-1所以(R1 R2)=R1 R225 设 R

20、关系图如下图，试给出 r(R), s(R),t(R)关系图abde cR 关系图解：abde cr(R)关系图abde cs(R)关系图abde ct(R)关系图32、对于给 A 和 R，判断 R 是否为 A 上等价关系。(1) A 为为实数集，x,yA, xRy x-y=2 . 解: R 不是 A 上等价关系，因为 R 不自反.(2) A=1,2,3,x,yA, xRy x+y3解: R 不是 A 上等价关系，因为 R 不传递.(3) A=Z+ ,即正整数集，x,yA, xRy xy 是奇数。 解: R 不是 A 上等价关系，因为 R 不自反.(4) A=P(X), |X|2, x,yA,

21、xRy xyyx解: R 不是 A 上等价关系，因为 R 不传递. (5) A=P(X),CX, x,yA, xRy xyC解: R 是 A 上等价关系.36、设 A=1，2，3，4，在 AA 上定义二元关系 R, AA, Ru+y=x+v(1) 证明 R 是 AA 上等价关系。 (2) 确定由 R 引起对 AA 划分。证明：(1) 先证 R 具有自反性AA由于 x+y=x+y再根据 R 定义知 ,R 所以 R 具有自反性.再证 R 具有对称性, AA, 假设,R 那么由 R 定义知：u+y=x+v所以 x+v = u+y再由 R 定义知 ,R 所以 R 具有对称性.再证 R 具有传递性, ,

22、AA, 假设,R 并且,R那么由 R 定义知：u+y=x+v 并且 x+t=s+y根据上述两式知: u+t= s+v再根据 R 定义知 ,R 所以 R 具有传递性。综上所述 R 为 AA 上等价关系。(2) AA/R=,38、设 R 为 A 上自反和传递关系，证明 RR-1 是 A 上等价关系。 证明： 先证 RR-1 具有自反性xA由于 R 为 A 上自反关系所以R , 再由逆关系定义知R-1所以RR-1因此 R 具有自反性。 再证 RR-1 具有对称性RR-1所以R 并且R-1 由逆关系定义知R-1 并且R 所以R-1R即RR-1所以 R 具有对称性。 再证 R 具有有传递性x, y, z

23、A，并且, RR-1所以R 并且R-1并且R 并且R-1所以R 并且R 并且R 并且R由 R 传递性知R 并且R 所以R 并且R-1所以RR-1所以 RR-1 具有传递性。综上所述知 RR-1 为 A 上等价关系。40、设 R 为 NN 上二元关系，, NNR b=d(1) 证明 R 为等价关系 (2) 求商集 NN/R证明：(1) 先证 R 具有自反性NN 因为 b=b由 R 定义知 R所以 R 具有自反性。 再证 R 具有对称性, NN，假设R 由 R 定义知 b=d再由 R 定义知R 所以 R 具有对称性。 再证 R 具有传递性, ，NN， 假设R并且R 由 R 定义知 b=d, d=f

24、所以 b=f再由 R 定义知R 所以 R 具有传递性综上所述知 R 为 NN 上等价关系。 (2) NN/R= , 41、设 A=1，2，3，4，在 AA 上定义二元关系 R, AA, Ra+b=c+d(1)证明 R 为等价关系。 (2)求 R 导出划分。证明：(1) 先证 R 具有自反性AA 由于 a+b=a+b再根据 R 定义知 ,R 所以 R 具有自反性.再证 R 具有对称性, AA, 假设,R 那么由 R 定义知：a+b=c+d所以 c+d = a+b再由 R 定义知 ,R 所以 R 具有对称性., ,AA, 假设,R并且,R那么由 R 定义知：a+b=c+d 并且 c+d=e+f根据

25、上述两式知: a+b = e+f再根据 R 定义知 ,R 所以 R 具有传递性。综上所述 R 为 AA 上等价关系。(2) AA/R=,42、设 R 是 A 上自反和传递关系，如下定义 A 上关系 T，使得x, yAT R R 证明：T 是 A 上等价关系。证明： 先证 T 具有自反性xA由于 R 是 A 上自反关系即R R由 T 定义知：T 所以 T 具有自反性 再证 T 具有对称性x,yA ,假设T由 T 定义知：R R 即 R R再由 T 定义知： T 所以 T 具有对称性 再证 T 具有传递性x, y，zA ,假设T T 由 T 定义知：R R 并且R R再由 R 具有传递性知: R

26、R 再根据 T 定义知: T所以 T 具有传递性。综上所述知 T 为 A 上等价关系。48、设和为偏序集，在集合 AB 上定义关系 T 如下：, AB,T a1Ra2 b1Sb2证明：T 为 AB 上偏序关系 证明： 先证 T 具有自反性AB所以 a1 A 并且 b1 B由于 R 和 S 分别是 A 和 B 上偏序关系, 所以 R 和 S 具有自反性所以 a1Ra1 b1Sb1由 T 定义知: T 所以 T 具有自反性。 再证 T 具有反对称性, AB,假设T 并且T 那么由 T 定义知: a1Ra2 b1Sb2 并且 a2Ra1 b2Sb1由于 R 和 S 是偏序关系，所以 R 和 S 反对称所以 a1 = a2 并且 b1 = b2 所以 = 因此 T 具有反对称性。 再证 T 具有传递性, ，AB,假设T 并且T 由 T 定义知: a1Ra2 b1Sb2 并且 a2Ra3 b2Sb3 由于 R 和 S 是偏序关系,所以 R 和 S 具有传递性所以 a1Ra3 b1Sb3再由 T 定义知: T 所以 T 具有传递性。综上所述 T 为 A 上偏序关