《离散数学自学考试复习题.pdf》由会员分享，可在线阅读，更多相关《离散数学自学考试复习题.pdf（11页珍藏版）》请在金锄头文库上搜索。
1、离散数学 复习题 1 设A和B都是命题，则AB的真值为假当且仅当 。 A. A为假，B为真 B. A为假，B为假 C. A为真，B为真 D. A为真，B为假 学号： 2 下列公式中为重言式的是 。 A. P(PQR) B. (QP)P C. (PQ)(QP) D. (PP) Q 3 设Aa，a，P(A)表示A的幂集，下面各式中错误的 是 。 A. aP(A) B. aP(A) C. a P(A) D. aP(A) 4 设A1,2,3,4,5,6上的关系为R|xy，则R- 1具有 。 A. 对称性 B. 自反性 C. 反自反性、反对称性、传递性 D. 以上都不对 5 设R是非空集合A上的二元关系
2、，则R的对称闭包S(R) 。 A. RIA B. RRC C. R- IA D. RRC 6 映射的复合运算满足 。 A. 交换律 B. 结合律 C. 幂等 律 D. 分配律 班级： 7 设R、I分别是实数集合和整数集合，-、/ 分别是 普通的减法、乘法 和除法运算，则 是半群。 A. B. C. D. 8 在一个格中，对任意的a，b，cA，都有 。 A. a(bc)(ab)(ac) B. a(bc)(ab)(ac) C. a(bc)(ab)(ac) D. A、B、C都正确 9 无向简单图G中结点间的连通关系是 。 A. 偏序关系 B. 等价关系 C. 既是偏序关系又是等价关系 D. A、B、
3、C都错误 10.设G是一个有v个结点e条边的连通简单平面图，若v3，则 。 A. v3e-6 B. e3v-6 C. v3e+6 D. e3v+6 11设P和Q是命题，P，PQQ。 ( ) 12设A和B是集合，A-BA当且仅当B。 ( ) 13一个不是自反的关系，一定是反自反 的。 ( ) 14若A和B是任意两个集合，则AB BA。 ( ) 15关系f|m,nN,m+n10是函数，其中N是自然数 集合。 ( ) 16集合B是集合A的真子集，则KB KA。 ( ) 17整环一定是 域。 18任何两个具有2n个元素的有限布尔代数都是同构 的。 ( ) 19已知无向连通图G中有n个结点，m条边，G中
4、无回路，则m n-1。( ) 20.如果两个图的结点数相同、边数相等、度数相同的结点数 目也相等，那么这两个图是同构 的。 21.设命题P表示“我今天将去公园”，命题Q表示“天下 雨”，则命题“我今天去公园，除非下雨”可以符号化为 (1) 。 22.命题“只有教师才有教师资格证(T(x)，C(x)”可符号 为： (2) 。 23.设P(A)是集合A的幂集，如果|A|n，则|P(A)| (3) ，|AP(A)| (4) 。 24.设Aa,b,c，P(A)为A的幂集，P(A)，是偏序集。则 P(A)的子集，a，b，a,b，b,c的极大元 是 (5) ，最大元是 (6) ，上界是 (7) ，下确界
5、是 (8) 。 25.设f和g是从整数集到整数集合的函数，其定义为f(x) 2x+3和g(x)3x+2，则gf(x) (9) ，fg(x) (10) 。 26.设是一个代数系统，并设R是A上的一个等价关系， 如果和R时， (11) ，则称R为A上的同 余关系。 27.设是一个格，由它诱导的代数系统为，如果对于任意的a,b,cA，当ba时，有 (12) ， 则称为模格。 28.一个图是平面图，当且仅当它不包含与 (13) 或 (14) 在2 度结点内同构的子图。 29.无向图G具有一条欧拉路，当且仅当G是 (15) ，且有 （16） 奇数度结点。 30.无向图G如右图所示，则G的点连通度 (17
6、) ，边连通度为 (18) ，它的生成树有 (19) 条树枝和 (20) 条弦。 31.求(A(BC)(A (BC)的主析取范式和主 合取范式。 32.将下列推理形式化，并推证其结论 所有牛都有角，有些动物是牛，所以有些动物有角。 33.设正整数的序偶集合A，在A上定义的二元关系R如下： ,R，当且仅当xvyu，证明R是一个等价关 系。 34.设是群，S是G的非空子集，如果对于S中的任意元素 a和b，有a*b-1S，则是的子群。 35.令gf是一个复合函数，若g和f是双射的，则gf是双射的。 36.判断彼德森(Petersen)图是否为汉密尔顿图？若是，请写 出汉密尔顿回路。若不是，请予以证明
7、。 37下列是两个命题变元p，q的小项是（ ） Appq Bpq Cpq Dppq 38令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不 滑”可符号化为（ ） Apq Bpq Cpq Dpq 39下列语句中是命题的只有（ ） A1+1=10 Bx+y=10 Csinx+siny0 Dx mod 3=2 40下列等值式不正确的是（ ） A(x)A(x)A B(x)(BA(x)B(x)A(x) C(x)(A(x)B(x)(x)A(x)(x)B(x) D(x)(y)(A(x)B(y)(x)A(x)(y)B(y) 41谓词公式(x)P(x,y)(x)(Q(x,z)(x)(y)R(x,y,z
8、)中量词x的辖域是（ ） A(x)Q(x,z)(x)(y)R(x,y,z) BQ(x,z)(y)R(x,y,z) CQ(x,z)(x)(y)R(x,y,z) DQ(x,z) 42设R为实数集，函数f：RR，f(x)=2x，则f是（ ） A满射函数 B入射函数 C双射函数 D非入射非满射 43设A=a,b,c,d，A上的等价关系R=,IA，则 对应于R的A的划分是（ ） Aa,b,c,d Ba,b,c,d Ca,b,c,d Da,b,c,d 44设A=，B=P(P(A)，以下正确的式子是（ ） A,B B,B C,B D,B 45设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ ）
9、A(X-Y)-Z=X-(YZ) B(X-Y)-Z=(X-Z)-Y C(X-Y)-Z=(X-Z)-(Y-Z) D(X-Y)-Z=X-(YZ) 46设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ） A有x*Z=Z*x=Z BZA，且有x*Z=Z*x=Z CZA，且有x*Z=Z*x=x DZA，且有x*Z=Z*x=Z 47在自然数集N上，下列定义的运算中不可结合的只有（ ） Aa*b=min(a,b) Ba*b=a+b Ca*b=GCD(a,b)(a,b的最大公约数) Da*b=a(mod b) 48设R为实数集，R+=x|xRx0，*是数的乘法运算，是一 个群，则下列集合关于数的乘法
10、运算构成该群的子群的是（ ） AR+中的有理数 BR+中的无理数 CR+中的自然数 D1，2，3 49设是环，则下列正确的是（ ） A是交换群 B是加法群 C对*是可分配的 D*对是可分配的 50下列各图不是欧拉图的是（ ） 51设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ） A2个面 B3个面 C4个面 D5个面 52一公式为 之充分必要条件是其析取范式之每一析取项中均必同 时包含一命题变元及其否定；一公式为 之充分必要条件是其合取范 式之每一合取项中均必同时包含 一命题变元及其否定。 53前束范式具有形式(Q1V1)(Q2V2)(QnVn)A，其中Qi(1in)为 ，A 为
11、 的谓词公式。 54设论域是a,b,c，则(x)S(x)等价于命题公式 ；()S(x)等价于命题公 式 。 55设R为A上的关系，则R的自反闭包r(R)= ，对称闭包s(R)= 。 56某集合A上的二元关系R具有对称性，反对称性，自反性和传递性， 此关系R是 ，其关系矩阵是 。 57设是一个偏序集，如果S中的任意两个元素都有 和 ，则 称S关于构成一个格。 58设Z是整数集，在Z上定义二元运算*为a*b=a+b+ab，其中+和是数 的加法和乘法，则代数系统的幺元是 ，零元是 。 59如下平面图有2个面R1和R2，其中deg(R1)= ，deg(R2)= 。 60无向图G具有一条欧拉回路，当且仅
12、当G是 ，并且所有结点的度 数都是 。 61在下图中，结点v2的度数是 ，结点v5的度数是 。 62（4分）求出从A=1,2到B=x,y的所有函数，并指出哪些是双射函 数，哪些是满射函数。 63（4分）如果论域是集合a,b,c，试消去给定公式中的量词：。 64（5分）设A=a,b,c ，P（A）是A的幂集，是集合对称差运算。已 知是群。在群中，找出其幺元。找出任一元素的 逆元。求元素x使满足ax=b。 65（6分）用等值演算法求公式(pq)(pq)的主合取范式 66（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。 67（6分）在偏序集中，其中Z=1,2,3,4,6,8,12,14，
13、是Z中的整 除关系，求集合D=2,3,4,6的极大元，极小元，最大元，最小元， 最小上界和最大下界。 68（6分）用等值演算法证明(qs)r)(s(pr)(s(pq)r 69（6分）设n阶无向树G=中有m条边，证明m=n-1。 70（8分）设P=,1,1,2,1,2,3，是集合P上的包含关系。 （1）证明：是偏序集。 （2）在（1）的基础上证明是全序集 71 设集合A=2,a,3,4，B = a,3,4,1，E为全集，则下列命题正确 的是( )。 (A)2A (B)aA (C)aBE (D)a,1,3,4B. 72 设集合A=1,2,3,A上的关系R(1,1),(2,2),(2,3),(3,2
14、),(3,3)，则R不 具备( ). (A)自反性 (B)传递性 (C)对称性 (D)反对称性 73 设半序集(A,)关系的哈斯图如下所示，若A的子集B = 2,3,4,5,则 元素6为B的( )。 74 设I是如下一个解释：Da,b, 则在解释I下取真值为1的公式是( ). (A)xyP(x,y) (B)xyP(x,y) (C)xP(x,x) (D)xyP(x,y). 75. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图 的是( ). (A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6). 76. 设G、H是一阶逻辑公式，P是一个谓词，GxP(x), HxP(x),则一阶 逻辑公式GH是( ). (A)恒真的 (B)恒假的 (C)可满足的 (D)前束范式. 77 设命题公式G(PQ)，HP(QP)，则G与H的关系是( )。 (A)GH (B)HG (
