离散数学复习题及答案

第1页，共24页1.写出命题公式﹁（P→（P∨Q））的真值表。答案：2.证明答案：3.证明以下蕴涵关系成立：答案：4.写出下列式子的主析取范式：答案：)()(QPQPQPQ)P(Q)(PP)(QP)P(Q)(QQ)P(P)Q)P((Q)Q)P(P)Q(Q)P(QPQQPP)()()(RPQP第2页，共24页5.构造下列推理的论证：p∨q,p→r,s→t,s→r,tq答案：①s→t前提②t前提③s①②拒取式I12④s→r前提⑤r③④假言推理I11⑥p→r前提⑦p⑤⑥拒取式I12⑧p∨q前提⑨q⑦⑧析取三段论I106.用反证法证明：p→((r∧s)→q),p,sq)()(RPQP)()(RPQP))(())(RQPPQP)()()()(RQRPPQPP)()()(QRPRPQRPQ)()()(PRQPRQQRP)()()(QRPRPQRPQ)(QRP第3页，共24页7.请将下列命题符号化：所有鱼都生活在水中。答案：令F(x)：x是鱼W(x)：x生活在水中))((W(x)F(x)x8.请将下列命题符号化：存在着不是有理数的实数。答案：令Q(x)：x是有理数R(x)：x是实数Q(x))x)(R(x)(9.请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令M(x)：x是人C(x)：x是聪明的则上述命题符号化为10.请将下列命题符号化：对于所有的正实数x,y，都有x+y≥x。答案：令P(x):x是正实数S(x,y):x+y≥x11.请将下列命题符号化：每个人都要参加一些课外活动。答案：令P(x):x是人Q(y):y是课外活动S(x,y):x参加y)))()((())()((xCxMxxCxMx)),()()((yxSyPxPyx))(),()((yQyxSxPyx第4页，共24页12.请将下列命题符号化：某些人对某些药物过敏。答案：令P(x):x是人Q(y):y是药S(x,y):x对y过敏13.求)())()((yyRyQxPy的对偶式:答案：14.求下列谓词公式的前束范式：答案：15.证明：答案：),,()),(),((uyxuQzyPzxzPyx),,()),(),((uyxuQzyPzxzPyx),,()),(),((uyxuQzyPzxPzyx),,()),(),((utsuQzyPxPyx)),,(),(),((utsQzyPxPuyx))(),()((yQyxSxPyx),,()),(),((uyxuQzyPzxzPyx第5页，共24页16.用反证法证明：x(P(x)∧Q(x)),xP(x)xQ(x)答案：17.证明：前提：x(C(x)W(x)∧R(x)),x(C(x)∧Q(x)).结论：x(Q(x)∧R(x)).答案：(1)x(C(x)∧Q(x))前提引入(2)C(a)∧Q(a)(1)ES(3)C(a)(2)化简规则(4)x(C(x)W(x)∧R(x))前提引入(5)C(a)W(a)∧R(a)(4)US(6)W(a)∧R(a)(3)(5)假言推理(7)R(a)(6)化简规则(8)Q(a)(2)化简规则(9)R(a)∧Q(a)(7)(8)合取引入规则(10)x(Q(x)∧R(x))(9)EG18.判断：下列命题是否正确？第6页，共24页答案：(1)√(2)×(3)√(4)√(5)√(6)√(7)√(8)×19.列出下列集合的元素(1){x|x∈N∧t(t∈{2,3}∧x=2t)}(2){x|x∈N∧ts(t∈{0,1}∧s∈{3,4}∧txs)}(3){x|x∈N∧t(t整除2x≠t)}答案：(1){4,6}(2){1,2,3}(3){3,4,5…}20.S={0,1,2,3,4,5,6,7,8,9}，A={2,4,5,6,8}B={1,4,5,9}，C={x|x∈Z+,2≤x≤5}答案：21.一个学校有507，292，312和344个学生分别选择了A,B,C,D四门课程。有14人选了第7页，共24页A和B，213人选了A和D，211人选了B和C，43人选了C和D。没有学生同时选择A和C，也没有学生同时选择B和D。问共有多少学生在这四门课程中选了课？答案：解：画文氏图280+87+38+88+14+211+213+43=97422.分别求下列集合的幂集(1)Ø(2){Ø}(3){1,{Ø,1}}答案：解:(1)ρ(Ø)={Ø}空集Ø的幂集的基数为1(2)ρ({Ø})={Ø,{Ø}}幂集的基数为2(3)ρ({1,{Ø,1}})={Ø,{1},{{Ø,1}},{1,{Ø,1}}}23.A={0,1},B={1,2},C={3,4,5},求A×B,B×A,A×B×C,A2,C2.答案：A×B={(0,1),(0,2),(1,1),(1,2)}B×A={(1,0),(2,0),(1,1),(2,1)}A×B×C={(0,1,3),(0,1,4),(0,1,5),(0,2,3),(0,2,4),(0,2,5),(1,1,3),(1,1,4),(1,1,5),(1,2,3),(1,2,4),(1,2,5)}A2={(0,0),(0,1),(1,0),(1,1)}C2={(3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)}24.1.设A={{1,2,3},{4,5},{6,7,8}},下列选项正确的是（C）A.1∈AB.{1,2,3}AC.{{4,5}}AD.Ø∈A2.设A={x|x3–x=0},B={x|x2–40,x∈z},C={x|y=2x-1},D={x|x+y=5,xy=6}则有（A）A.A=BB.A=CC.C=DD.C=A第8页，共24页25.求关系的定义域和值域：设A={2，4，6，8}，R是A上的小于关系，即当a,b∈A且ab时，（a,b）∈R，求R及D(R),C(R)答案：R={（2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）}.R的定义域D(R)={2，4，6}，R的值域C(R)={4，6，8}。26.设A={a,b,c,d},求A上的恒等关系。答案：IA={(a,a),(b,b),(c,c),(d,d)}。27.设A={1,2,3,4,5},R是A上的小于等于关系,即当a≤b时,(a,b)∈R。求R的关系矩阵和关系图。答案：解:易知A上的小于等于关系为R={（1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)}其关系矩阵为1000011000111001111011111RM第9页，共24页28.X={a,b,c}，Y={1,2}，关系R={(a,1),(b,2),(c,1)}S={(a,1),(b,1),(c,1)}求R∪S、R∩S和R的补答案：29.设A={1，2，3}，B={a,b,c,d},C={x,y,z}，R是A到B的二元关系，R={(1,a),(1,b),(2,b),(3,c)}，S是B到C的二元关系，S={(a,x),(b,x),(b,y),(b,z)}。求复合关系RοS的关系矩阵.答案：30.答案：31.设A={a,b,c}，R是A上的二元关系，R={(a,a),(b,b),(a,b),(a,c),(c,a)}，问：R是自反的吗？是反自反的吗？是对称的吗？是反对称的吗？是可传递的吗？答案：由于c∈A，而(c,c)，所以R不是自反的。×由于(a,a)∈R，(b,b)∈R，所以R不是反自反的。×由于(a,b)∈R，而(b,a)，所以R不是对称的。×由于(a,c)∈R，且(c,a)∈R，所以R不是反对称的。×由于(c,a)∈R，且(a,c)∈R，但(c,c)，所以R不是可传递的。×RRR第10页，共24页32.设A={1,2,3}，分析A上的下述5个关系具有哪些性质：L={1,1,1,2,2,1,2,2,3,3}N={1,3,2,3}S={1,2,2,1,1,3}G={1,1,1,2,2,3}答案：33.设A={a,b,c,d}，A上的关系，R={(a,b),(b,a),(b,c),(c,d)}求r(R)、s(R)、t(R)答案：34.A={a,b,c},R={(a,b),(b,c),(c,a)}，求r(R),S(R)和t(R)答案：c)}(d,b),d),(c,(c,c),(b,a),(b,b),{(a,c)}(d,b),(c,b),(a,a),{(b,d)}(c,c),(b,a),(b,b),{(a,RRS(R)d)}(d,c),b),(c,(b,a),(a,d),(c,c),(b,a),(b,b),{(a,IRr(R)A~234232432Rd)}(b,b),(b,c),(a,a),{(a,RRRc)}(b,a),(b,d),(a,b),{(a,RRRd)}(b,b),(b,c),(a,a),{(a,RRR而RRRRt(R)第11页，共24页35.A={1,2,3,4}，R={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)},判断R是否是等价的。答案：36.判断下列关系是否为等价关系？(1)A={a,b,c,d}，R={(a,a),(b,a),(b,b),(c,c),(d,d),(d,c)}(2)A={1,2,3,4}，R={(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(2,3),(3,3),(4,4),(3,2)}答案：（1）×（2）√37.A={1,2,3,4}在幂集ρ(A)上定义的二元关系如下：R={(S,T)|S,T∈ρ(A)，|S|=|T|}，写出商集ρ(A)/R。答案：解：首先求ρ(A)。ρ(A)={Ø,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}共16个元素！第12页，共24页38.设集合X={2166，243，375，648，455}X中的关系R为：R={(x,y)|x,y∈X，并且x和y中有相同数字}问：R是不是相容关系？答案：39.A={1，2，3，4，5，6，8，10，12，16，24}，R是A上的整除关系，请画出Ｒ的哈斯图。答案：40.已知偏序集A,R的哈斯图如图所示,试求出集合A和关系R的表达式.求A的极小元、最小元、极大元、最大元.设B＝{b,c,d},求B的下界、上界、最大下界、最小上界.答案：极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在,上界有d和f,最小上界为d.第13页，共24页41.以下关系矩阵所代表的关系是什么关系？答案：相容关系42.设集合A={1，2，3，4，5，6，8，10，12，16，24}，R是A上的整除关系，请问关系R是否是偏序关系？是否是全序关系？画出Ｒ的哈斯图，并根据图求集合A的极大极小元、最大最小元，设B={2，3，4}，求集合B的上界、最小上界、下界、最大下界。答案：是偏序关系，不是全序关系。A的极大元：24,16,10A的极小元：1A的最大元：没有A的最小