离散数学期末复习.doc
word离散数学期末复习一、选择题1、 如下各选项错误的答案是A、Æ Í ÆB、Æ Ì Æ C、Æ Î ÆD、Æ Í Æ 2、命题公式 (pq) p 是A、矛盾式 B、重言式C、可满足式 D、等值式3、如果是R是A上的偏序关系，R-1是R的逆关系，如此RR-1是 A、等价关系B、偏序关系 C、全序关系D、都不是4、如下句子中那个是假命题？A、是无理数. B、2 + 5 8. C、x + 5 3 D、请不要讲话！5、如下各选项错误的答案是？A、Æ Í Æ B、Æ Í Æ C、Æ Î ÆD、Æ Í Æ6、命题公式 ppÚqÚr是？A、重言式B、矛盾式 C、可满足式 D、等值式7、函数f : NN, f(x)=x+5,函数f是A、单射B、满射C、双射D、都不是8、设D=<V,E>,如此V=a,b,c,d,e,f,R=<a,b> ,<b,c>,<a,d>,<d,e>,<f,e>,有向图D为A、强连通B、单向连通C、弱连通 D、不连通的9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是A、R1 ÈR2B、R1-1C、R1 °R2 D、R1 -R210、连通平面图G有4个结点，3个面，如此G有 条边。A、7B、6C、5D、4二、填空题1、将下面命题符号化。设 p:天冷，q:小王穿羽绒服。 只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设 p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服. 符号化为 3、将下面命题符号化，设 p:天冷，q:小王穿羽绒服。假设小王不穿羽绒服，如此天不冷.符号化为4、将下面命题符号化，设 p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为 5、将下面命题符号化，设 p:天冷，q:小王穿羽绒服。除非天冷，小王才穿羽绒服.符号化为 6、将下面命题符号化，设 p:天冷，q:小王穿羽绒服。除非小王穿羽绒服，否如此天不冷.符号化为 7、将下面命题符号化，设 p:天冷，q:小王穿羽绒服。小王穿羽绒服仅当天冷的时候.符号化为 8、将下面命题符号化，设 p:天冷，q:小王穿羽绒服。如果天不冷，如此小王不穿羽绒服.符号化为 9、设p:王蓉努力学习，q：王蓉取得好成绩。如此1命题“只要王蓉努力学习，她就会取得好成绩。符号化为 。2命题“王蓉取得好成绩，如果她努力学习。符号化为 。3命题“只有王蓉努力学习，她才能取得好成绩。符号化为 。4命题“除非王蓉努力学习，否如此她不能取得好成绩。符号化为 。5命题“假设王蓉不努力学习，她就不能取得好成绩。符号化为 。6命题“王蓉取得好成绩，仅当她努力学习了。符号化为 。10、公式xF(x)xF(x)的类型为 11、公式xF(x)(xyG(x,y)xF(x)的类型为 12、公式xF(x)(xF(x)yG(y)的类型为 13、公式Ø(F(x,y)R(x,y)R(x,y)的类型14、公式xyF(x,y)xyF(x,y)的类型为 15、公式xF(x,y)的类型16、令F(x)：x是人，G(x)：x犯错误.如此命题“没有不犯错误的人符号化为 17、令F(x)：x是人，G(x)：爱看电影.如此命题“不是所有的人都爱看电影符号化为 18、公式Ø$x(M(x)ÙF(x)的前束式为： 19、公式"xF(x)ÙØ$xG(x)的前束式为： 20、公式$xF(x)ÚØ"xG(x)的前束式为 21、公式"xF(x)®$y(G(x,y)ÙØH(y)的前束式为 22、公式"x(F(x,y)®$y(G(x,y)ÙH(x,z)的前束式为 23、集合A=Ø,B=1,a,b,C=Ø,Ø,D=2,2,2,3;如此幂集P(A)= P(B)= P(C)= P(D)= 24、设A=1,2,3, B=a,b,c如此 A´B= ；B´A = 。25、设集合A=Æ, 如此P(A)´A= 。26、设|A|=n, 如此|A×A|= , A×A的子集有 个. 集合A上有 个不同的二元关系.27、设A=1,2, 如此EA= ；IA= 。28、集合A=2，3，4，5，6，10，12，24，R是A上的整除关系，如此R的极大元是 ，极小元是 。29、设A=1，2，3上的关系 R=<1，1>，<1，2>，<1，3>，<3，3> ，如此关系R具备 性质。30、设集合A=1,2,3,关系R=<1,2>, < 2,1>, <2,3>，<3,3>, 如此自反闭包r(R)= , 对称闭包s(R)= 。31、图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有 个顶点。32、n阶无向完全图Kn，边数m= 。33、n阶有向完全图Kn，边数m= 。34、设无向图 G 有 10 条边, 3 度与 4 度顶点各 2 个, 其余顶点的度数均小于3, 如此G 中至少有 个顶点，在最少顶点的情况下, 图G 的度数列 ， (G)= , d (G)= .35、设无向图中有6 条边, 3 度与 5 度顶点各一个, 其余的都是 2 度顶点, 如此该图有 个顶点。36、n阶连通平面图G有r个面，如此G的边数m= 。37、设A=1，2，3上的关系 R=<1，2>，<2，3>，<3，1> ，如此R°R= 。38、 设F(x)：x是兔子，M(x)：y是乌龟，H(x,y): x比y跑得快,如此命题“兔子比乌龟跑得快符号为 三、计算题1、给出公式A= (q®p) Ùq®p的真值表。2、 给出公式A= (q®p) Ùq®p的真值表。3、 给出公式C= (pÚq) ®Ør的真值表4、 用等值演算法判断公式 qÙØ(p®q)的类型5、 求公式A=(p®Øq)ÚØr的析取式与合取式。6、 求公式B=(p®Øq)®r的析取式与合取式。7、 求公式 A=(p®Øq)®r的主析取式与主合取式.8、在一阶逻辑中将下面命题符号化(1) 人都爱美; (2) 有人用左手写字分别取(a) D为人类集合, (b) D为全总个体域 .9、在一阶逻辑中将下面命题符号化(1) 正数都大于负数10、在一阶逻辑中将下面命题符号化(1) 有的无理数大于有的有理数11、试画出4阶3条边的所有非同构的无向简单图12、画出所有 K4的所有非同构的生成子图。 13、给定下面的图(前两个为无向图, 后两个为有向图)的集合表示, 画出它们的图形表示G1 = áV1, E1ñ, 其中, V1 = v1, v2, v3, v4, v5, E1 = (v1, v2), (v2, v3), (v3, v4), (v3, v3), (v4, v5);G2 = áV2, E2ñ, 其中 V2 = V1, E2 = (v1, v2), (v2, v3), (v3, v4), (v4, v5), (v5, v1);D1 = áV3, E3ñ, 其中 V3 = V1, E3 = áv1, v2ñ, áv2, v3ñ, áv3, v2ñ, áv4, v5ñ, áv5, v1ñ D2 = áV4, E4ñ, 其中 V4 = V1, E4 = áv1, v2ñ, áv2, v5ñ, áv5, v2ñ, áv3, v4ñ, áv4, v3ñ.14、先将图中各图的顶点标定顺序, 然后写出各图的集合表示.15、写出图中各图的度数列, 对有向图还要写出出度列和入度列.16、画一个简单无向图，使它是欧拉图，但不是哈密顿图。17、集合A=a, b, c, d, e, f和关系R=<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f> IA，请画出偏序集<A,R>的哈斯图。18、设A=a, b, c, d, R=<a, a>,<a, b>,<a, c>,<b, a>,<d, b>,求R的关系矩阵 MR 和关系图 GR。19、有向图D如下列图，写出D的邻接矩阵和可达矩阵20、设A=Z+×Z+，在A上定义二元关系R如下：<<x,y>,<u,v>>R当且仅当xv=yu，证明R是一个等价关系。21、求公式PQR的主析取式。22、求公式$x(F(x)"yG(x,y,z)® "xH(x,y,z)的前束式。23、偏序集<A,R>的哈斯图如如下图所示, 试求出集合A和关系R的表达式.24、设A=1,2,3,4, 定义A上的关R=<1,1>,<1,2>,<2,3>,<2,4>,<4,2>。求R的关系矩阵MR和关系图GR？14 / 14
