离散数学习题与解答.doc

作业题与解答第一章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)0001111100111111010101010111111110001001101011011101000111111111所以公式(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)(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)(pqr)(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)(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 该公式无主合取范式，所以公式的 主析取范式为：(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析取三段论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), (st)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 比 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=N（N 为自然数）。（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 的代换实例，而该命 题公式是矛盾式，所以此谓词公式是矛盾式。第五章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(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)析取三段论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 中，证明下面推理： (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)为虚数 前提：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)=(AB)(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、B、C 为任意集合，证明： ACBC A-CB-C AB 证明：xA(1) 若 xC则 xAC，而 ACBC所以 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则 xAB ，而 AB=AC所以 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)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) 再证 P(AB) P(A)P(B)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)因此 P(A)P(B) P(AB)(3) 举例：令 A=1,B=2则 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 的关系图如图所示，试给出 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, 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 具有传递性, ,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, zA，并且, 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所以 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 具有对称性.再证 R 具有传递性, ,AA, 若,R并且,R则由 R 的定义知：a+b=c+d 并且 c+d=e+f根据上述两式知: 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 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 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 上的偏序关系。49、设为偏序集，在 A 上定义新的关系 S 如下：x, yAxSy xRy称 S 为 R 的对偶关系 (1) 证明 S 也是 A 上的偏序关系。(2) 如果 R 是整数集合上的小于或等于关系，那么 S 是什么关系？如果 R 是正整数集合上的整除关系，那么 S 是什么关系?(3) 偏序集和中的极大元、极小元、最大元、最小元 等之间有什么关系？证明：(1) 先证 S 具有自反性xA由于 R 具有自反性，所以 R 由 S 的定义知：S所以 S 具有自反性。 再证 S 具有反对称性x，y A,若S 并且S 那么由 S 的定义知：R 并且R 由于 R 是偏序关系，所以 R 具有反对称性所以 x=y所以 S 具有反对称性。 再证 S 具有传递性x，y，zA,若S 并且S 由 S 的定义知：R 并且R又因 R 为偏序关系，所以 R 具有传递性所以 R再由 S 的定义知：S 所以 S 具有传递性。综上所述 S 为 A 上的偏序关系。(2) 如果 R 是整数集合上的小于或等于关系，那么 S 是 A 上的大 于或等于关系。如果 R 是正整数集合上的整除关系，那么 S 是正整数集合上的倍数关系。(3) 偏序集极大元是中的极小元，偏序集 极小元是中的极大元、偏序集最大元是 中的最小元，偏序集最小元是中的最大元。第八章21、22、25、29、30、34、3521、设 f:NNN, f(x)=(1)说明 f 是否为单射和满射并说明理由；(2)f 的反函数是否存在，如果存在，求出 f 的反函数； (3)求 ranf解: (1)f 为单射，证明如下： x1, x2N, 若 f(x1)=f(x2) 则 = 根据有序对相等的概念知：x1=x2所以 f 为单射，但 f 不是满射，因为 ranf(2) f 的反函数不存在 (3)ranf=|nN 22、设 f:ZZ，f(x)=(x)mod n ,在 Z 上定义等价关系 R， x, yZRf(x)=f(y) (1)计算 f(Z)；(2)确定商集 Z/R解: (1)f(Z)=0，1，.,n-1(2)Z/R=nk+i|kZ|i=0,1,.n-125、设 f:RRRR, f()= 证明 f 是双射证明：（1）先证 f 是单射 ，RR , 若 f()= f()则 = 所以 (x+y)/2=(u+v)/2(x-y)/2=(u-v)/2 所以 x=u ,y=v所以= 所以 f 为单射（2）再证 f 是满射 RR 存在RR 且f= 所以 f 为满射 综上所述 f 为双射。29、设 A=a,b,c,B=2A ,由定义证明 P(A)2A证明:方法一:P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c2A=f , ff , f , f , f , f , f 01234567f0=,f1=,f2=, f3=, f4=,f5=, f6=,f7=, 如下构造双射函数 ff()=f0 , f(a)=f1 , f(b)=f2 , f(c)=f3 , f(a,b)=f4 , f(a,c)=f5 , f(b,c)=f6 , f(a,b,c)=f7 ,根据等势定义有 P(A)2A方法 2证明：构造函数 f: P(A) 2A A1 P(A), f(A1) = xA1可以证明 f 为一一映射。先证 f 为单射 A1 ， A2，若 A1 A2则存在元素 x, xA1 ,且 xA2 或者 xA1 ,且 xA2不论那种情况，则 xA1 , xA2 至少有一个元素对应不同。 所以 xA1 xA2所以 f 为单射。再证 f 为满射2A，则为 A 到0，1的函数， 构造集合 A3= x| xA (x)=1 显然 A3P(A),且 f(A3)= xA3 = 所以 f 为满射。所以 f 为一一映射，因此 P(A)2A30、设1,2和0,1是实数区间，由定义证明1,20,1 证明：令 f: 1,2 0,1, f(x)=x-1,而 f 为双射函数（显然成立） 所以1,20,134、设 A、B、C、D 是集合，且 AC,BD ,证明:ABCD 证明: 由于 AC，所以存在一一映射 f 。由于 BD，所以存在一一映射 g 。构造 AB 到 CD 函数：ABCDAB,()= 显然 CD，下面证明为双射函数 先证为单射,AB,若()=() 即 = 所以 f(x) = f(u) 且 g(y) = g(v)而 f,g 为一一映射，所以 x=u 且 y=v所以 = 所以为单射 再证为满射CD 则 sC ,tD由于 f,g 是一一函数，所以存在 xA, yB,使得f(x)=s ,g(y)=t显然AB, 且()= 所以为满射。因此为双射函数。 所以 ABCD35、找出三个不同的 N 的真子集，使得它们都与 N 等势 解:A=2n|nNB=2n+1|nN C=2n|nN则 A,B,C 是三个不同的 N 的真子集,且它们都与 N 等势第九章4、11、15、164、判断下列集合对所给的二元运算是否封闭： (1) 整数集合 Z 和普通的减法运算(2) 非零整数集合 Z*和普通的除法运算(3) 全体 nn 实矩阵集合 Mn(R)和矩阵加法及乘法运算，其中 n2 (4) 全体 nn 实可逆矩阵集合关于矩阵加法和乘法运算，其中 n