离散数学课后作业参考答案慕课电子科技大学

作业-集合论by王丽杰1.用描述法写出下列集合。(1)从0到1000的整数；(2)所有实数集上一元一次方程的解组成的集合；(3)能被100整除的整数集合；(4)直角坐标系中，单位元(不包括单位圆周)的点集。2.试用2,,和=来描述以下各组两个集合间的关系。(1)A=f2g，B=f2xj(1⩽x⩽3)g(2)C=f2;3g，D=ff2;3gg(3)E=fxjx2Z;x2+x+1=0g，F=ff2;3gg(4)G=f3;3;2;1;2g，H=fxjx36x2+11x6=0g3.设A=∅,B=f∅;ag，C=f∅;fag;bg，求幂集P(A),P(P(A)),P(B),P(C)。4.给定自然数集合N的下列子集：A=f1;2;7;8g,B=fiji250g,C=fiji可被3整除;0⩽i⩽30g,D=fiji=2k;k2Z+;1⩽k⩽6g,求下列集合：(1)A[(B[(C[D));(2)A\(B(C\D));(3)B–(A[C);(4)(A\B)D。5.证明分配律公式A[(B\C)=(A[B)\(A[C)。6.证明：整数集是可数集合。1作业-集合论——11.(1)A=fxj(x2Z)并且(0⩽x⩽1000)g(2)B=fxj(x2R)并且(a2R)并且(a̸=0)并且(b2R)并且(ax+b=0))g(3)C=fxj(k2Z)并且(x=100k)g(4)D=fx;yj(x;y2R)并且(x2+y21)g。2.(1),(2)2(3),(4)=,3.P(A)=f∅g,P(P(A))=f∅;f∅gg,P(B)=f∅;f∅g;fag;f∅;agg,P(C)=f∅;f∅g;ffagg;fbg;f∅;fagg;f∅;bg;ffag;bg;f∅;fag;bgg。4.因为A=f1;2;7;8g,B=f0;1;2;3;4;5;6;7g,C=f0;3;6;9;12;15;18;21;24;27;30g,D=f2;4;6;8;10;12g,所以(1)A[(B[(C[D))=f0;1;2;3;4;5;6;7;8;9;10;12;15;18;21;24;27;30g;(2)A\(B(C\D))=f1;2;7g;(3)B–(A[C)=f4;5g;(4)(A\B)D=f0;2;3;5;8;10;12g。5.由于8x2A[(B\C),x2A或x2B\C,x2A或(x2B并且x2C),(x2A或x2B)并且(x2A或x2C),x2(A[B)\(A[C)。即左右两边的集合相互包含，所以二者相等，即：A[(B\C)=(A[B)\(A[C)6.在整数集Z与自然数集合N之间建立一个一一对应关系φ:N!Z如下:01234


2n2n+1


?y?y?y?y?y?y?y01122


nn+1


所以Z是可数集合。1作业-命题逻辑第一部分by王丽杰1.判断下列语句哪些是命题。(1)看电影去!(2)离散数学是计算机系的一门必修课。(3)明天有空吗?(4)2是素数，当且仅当三角形有三条边。(5)明天我要和你出去旅游。(6)不存在最大的质数。(7)7+14=31。(8)小红生病了，所以她没有去上学。(9)x=y+3。2.设命题P：天在下雪；Q：我将进城；R：我有空。符号化下列命题。(1)我将进城去当且仅当我有空且天不下雪。(2)虽然天在下雪，但我将进城去。(3)如果天不下雪且我有空，我将进城去。(4)除非天不下雪，否则我将不进城。3.利用真值表或公式转换方法，判断下列公式的类型（永真公式，永假公式，可满足公式）。(1)P!(P_Q_R)(2)((P_Q)^R)$Q(3)(P_Q)^(:P_Q)^(P_:Q)^(:P_:Q)4.利用基本等价公式证明：P!(Q!R)=Q!(P!R)。1作业答案——2-命题逻辑第一部分1.(2)(4)(5)(6)(7)(8)是命题。2.(1)Q$(R^:P)(2)P^Q(3):P^R!Q(4)Q!:P3.(1)真值表如下，可见为永真公式。PQRP!(P_Q_R)00010011010101111001101111011111(2)真值表如下，可见为可满足公式。PQR((P_Q)^R)$Q00010011010001111001101011001111(3)真值表如下，可见为永假公式。1PQ(P_Q)^(:P_Q)^(P_:Q)^(:P_:Q)0000000000004.证明P!(Q!R)=:P_(Q!R)=:P_(:Q_R)=:Q_(:P_R)=:Q_(P!R)=Q!(P!R)2作业-命题逻辑第二部分by王丽杰1.求公式:((P^Q)_R)!R所对应的主合取范式和主析取范式。2.用演绎法证明下述论断的正确性。(1)P_Q;Q!R;P!M;:M)R^(P_Q)(2)P;P!(Q!(R^S)))Q!S3.符号化下列论断，并用演绎法证明。(1)如果A地发生了交通事故，则小李的通行会发生困难；如果小李按指定的时间到达了，则他的通行没有发生困难；小李按指定的时间到达了。所以A地没有发生交通事故.(2)如果乙不参加蓝球赛，那么甲就不参加；如果乙参加篮球赛，那么甲和丙就参加。因此，如果甲参加球赛，那么丙就参加。1作业——3-命题逻辑第二部分1.G=(P^Q)_R_R=(P^Q)_R=(P_R)^(Q_R)=(P_(:Q^Q)_R)^((:P^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^M2^M4—主合取范式从而,主析取范式为：G=m1_m3_m5_m6_m7=(:P^:Q^R)_(:P^Q^R)_(P^:Q^R)_(P^Q^:R)_(P^Q^R)2.第(1)小题(1)P!MP(2):MP(3):PT;(1);(2);I(4)P_QP(5)QT;(3);(4);I(6)Q!RP(7)RT;(5);(6);I(8)R^(P_Q)T;(4);(7);I第(2)小题(1)PP(2)P!(Q!(R^S))P(3)Q!(R^S)T;(1);(2);I(4)QP(附加)(5)R^ST;(3);(4);I(6)ST;(5);I(7)Q!SCP;(4);(6)13.第(1)小题设命题P:A地发生了交通事故;Q:小李的通行发生困难;R:小李按指定的时间到达:则推理符号化成：P!Q;R!:Q;R):P(1)R!:QP(2)RP(3):QT;(1);(2);I(4)P!QP(5):PT;(3);(4);I第(2)小题设命题P:甲参加篮球赛;Q:乙参加篮球赛;R:丙参加篮球赛:则推理符号化成：:Q!:P;Q!P^R)P!R(1)PP(附加)(2):Q!:PP(3)QT;(1);(2);I(4)Q!P^RP(5)P^RT;(3);(4);I(6)RT;(5);I(7)P!RCP;(1);(6)2作业-谓词逻辑第一部分by王丽杰1.用谓词和量词，将下列命题符号化。(1)每一个有理数都是实数。(2)某些实数是有理数。(3)并非每一个有理数都是实数。(4)会叫的狗未必会咬人。(5)有些液体能溶解任何金属。(6)小莉是非常聪明和美丽的。2.指出下列各式的自由变元和约束变元，并决定量词的辖域。(1)(8x)(F(x)^G(x;y))!((9y)F(y)^R(x;y;z))(2)(9x)(P(x)^Q(x))!(8x)P(x)_Q(x)3.符号化下列复合命题。(1)每个旅客或者坐头等舱或者坐二等舱。(2)有些旅客富裕但并非所有的旅客都富裕。1作业——4-谓词逻辑第一部分1.(1)设Q(x):x是有理数;R(x):x是实数:则命题符号化成：(8x)(Q(x)!R(x))(2)设Q(x):x是有理数;R(x):x是实数:则命题符号化成：(9x)(R(x)^Q(x))(3)设Q(x):x是有理数;R(x):x是实数:则命题符号化成：:(8x)(Q(x)!R(x))(4)设D(x):x是会叫的狗;B(x):x是会咬人的狗:则命题符号化成：:(8x)(D(x)!B(x))(5)设L(x):x是液体;M(x):x是金属;D(x;y):x能溶解y:则命题符号化成：(9x)(L(x)^(8y)(M(y)!D(x;y)))(6)设C(x):x是聪明的;B(x):x是美丽的;a:小莉:则命题符号化成：C(a)^B(a)2.(1)(8x)的辖域为(F(x)^G(x;y))，F(x)，G(x;y)中的x是约束变元；G(x;y)中的y是自由变元；(9y)的辖域为F(y)，F(y)中的y是约束变元；R(x;y;z)中的x;y;z都是自由变元；(2)(9x)的辖域为(P(x)^Q(x))，P(x)，Q(x)中的x是约束变元；(8x)的辖域为P(x)，P(x)中的x是约束变元；第二个Q(x)中的x是自由变元；3.(1)设P(x):x是旅客;Q(x):x坐头等舱;R(x):x坐二等舱:则命题符号化成：(8x)(P(x)!Q(x)_R(x))(2)设P(x):x是旅客;F(x):x是富裕的:则命题符号化成：(9x)(P(x)^F(x))^:(8x)(P(x)!F(x))1作业-谓词逻辑第二部分by王丽杰1.设I是如下的一个解释：D=f1;2g;a=1;b=2;f(1)=2;f(2)=1;P(1;1)=1;P(1;2)=1;P(2;1)=0;P(2;2)=0￿试求出下列公式在I下的真值。（1）P(a;f(a))^P(b;f(b))（2）(8x)(9y)P(y;f(x))2.将下列命题符号化，并用演绎法证明。(1)没有不守信用的人是可以信赖的；有些可以信赖的人是受过教育的。因此，有些受过教育的人是守信用的。(2)所有的舞蹈者都很有风度；王英是个学生并且是个舞蹈者。因此，有些学生很有风度。1作业参考答案——5-谓词逻辑第二部分1.（1）P(a;f(a))^P(b;f(b))=P(1;f(1))^P(2;f(2))=P(1;2)^P(2;1)=1^0=0（2）(8x)(9y)P(y;f(x))=(P(1;f(1))_P(2;f(1)))^(P(1;f(2))_P(2;f(2)))=(P(1;2)_P(2;2))^(P(1;1)_P(2;1))=(1_0)^(1_0))=12.将下列命题符号化，并用演绎法证明。(1)个体域为所有人。设P(x):x是守信用的;Q(x):x是可信赖的;R(x):x是受过教育的:则推理符号化成：:(9x)(:P(x)^Q(x));(9x)(Q(x)^R(x)))(9x)(R(x)^P(x))演绎法证明过程如下：(1)(9x)(Q(x)^R(x))P(2)Q(c)^R(c)ES;(1)(3)Q(c)T;(2);I(4)R(c)T;(2);I(5):(9x)(:P(x)^Q(x))P(6)(8x):(:P(x)^Q(x))T;(5);E(7):(:P(c)^Q(c))US;(6)(8)P(c)_:Q(c)T;(7);E(9)P(c)T;(3);(8);I(10)R(c)^P(c)T;(4);(9);I(11)(9x)(R(x)^P(x))EG;(11)(2)1设P(x):x是是舞蹈家;Q(x):x是有风度的;S(x):x是学生;a:王英:则推理符号化成：(8x)(P(x)!Q(x));S(a)^P(a))(9x)(S(x)^Q(x))演绎法证明过程如下：(1)S(a)^P(a)P(2)S(a)T;(1);I(3)P(a)T;(1);I(4)(8x)(P(x)!Q(x))P(5)P(a)!Q(a)US;(4)(6)Q(a)T;(3);(5);I(7)S(a)^Q(a)T;(2);(6);I(8)(9x)(S(x)^Q(x))EG;(7)2作业-二元关系by王丽杰1.设A=f1;2;2;4;3;3g;B=f1;3;2;4;4;2g。求dom(A[B),ran(A\B).2.设A=f0;1;2;3g,R和S是A上的二元关系，R=fi;jj(j=i+1)或j=i/2g;S=fi;jj(i=j+2)g.(1)用关系矩阵法求R◦S；(2)用关系图法求S◦