大学离散数学总复习题.doc

离散数学期末复习题一选择题：1.下列句子为真命题的是 （） A (a) 能整除7 的正整数只有1 和7 本身。(b) 胡戈由于导演了“无极”而于2005年获得奥斯卡金像奖。(c) 买两张星期五去“大剧院”音乐会的票。(d) 地球是宇宙中惟一存在生命的星球。2下列语句中是真命题的是（） DA我正在说谎 B严禁吸烟C如果1+2=3，那么雪是黑的D如果1+2=5，那么雪是黑的3设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） BA P Q B P QC（PQ） D（ P Q）4命题公式（P（PQ）Q是（） BA矛盾式 B蕴含式C重言式 D等价式5在公式（）F（x，y）（ y）G（x，y）中变元x是（） BA自由变元B约束变元C既是自由变元，又是约束变元 D既不是自由变元，又不是约束变元6、下列语句不是命题的是（） AA. xP(x,y)B. xP(x)C. （）F（x，y）（ y）G（x，y）D. x (x2 - 1 0)7.集合X = a, b, c, d上的关系R = (a, a), (b, c), (c, b), (d, d) 是（） DA) 自反的、 B) 传递的、 C) 等价的 D) 对称的8、 设R 是X = 1, 2, 3, 4上的关系，x, y X，如果x y，则(x, y) R。下列关于关系R的说法错误的是：（） AA) 关系R是等价关系，B) 关系R 是自反的 C) 关系R 是传递的 D) 以上都不是。9、 集合X = a, b, c上的关系 R = (a, a), (b, b), (c, c)是（） DA) 自反的、非对称的；B) 自反的、非传递的C) 对称的、非传递的；D) 自反的、对称的和传递的10、 令X=1,2,10。 定义xRy的意义是3整除x-y。则关系R是 （） DA) 自反的、非对称的；B) 自反的、非传递的C) 对称的、非传递的D) 自反的、对称的和传递的11、下列S不是集合X1, 2, 3, 4, 5, 6, 7, 8的一个划分的是 （） DA) S1, 4, 5, 2, 6, 3, 7, 8B) S1, 4, 2, 6, 3,5, 7, 8C) S1, 4, 5, 2,3, 6, 7, 8D) S1, 4, 2, 6, 3, 7, 812、从X = 1, 2, 3到Y = a, b, c, d的函数 f = (1, b), (3, a), (2, c) 是( ) AA) 一对一的 B) 映上的C) 双射 D) 都不是 13、设R是X1, 2, 3, 4上的关系，x, yX，如果xy，则(x,y)R。关系R是（） BA) 对称的B) 自反的和传递的C) 等价关系D) 对称的但不是等价关系14.偏序关系具有性质（） DA.自反、对称、传递B.自反、反对称C.反自反、对称、传递D.自反、反对称、传递15.对公式的说法正确的是（）AA.x是约束出现，y是约束出现，z是自由出现B.x是约束出现，y既是约束出现又是自由出现，z是自由出现C.x是约束出现，y既是约束出现又是自由出现，z是约束出现D.x是约束出现，y是约束出现，z是约束出现16.在简单无向图G=中，如果V中的每个结点都与其余的所有结点邻接，则该图称为（） BA.正则图B.完全图C.连通图D.强连通图17.给定n个结点的一个图，它还是一个树的下列说法中，（）是不对的。 DA.无回路的连通图B.无回路但若增加一条新边就会变成回路C.连通且e=v-1，其中e是边数，v是结点数D.所有结点的度数218.设p 为真 q为假，r为真，下列为假的式子为 （）BA) (p q) r 为（）真B) (p q) r为（） 假C) p (q r) 为（）真D) p (q r)为（） 真19.从X = 1, 2, 3到Y = a, b, c的函数 f = (1, a), (2, c), (3, b) 是A) 一对一的，并且是对Y 映上的。 （）真B) 一对一的，但不是对Y映上的。C) 不是一对一的。D) 不是对Y映上的。20.仅由孤立点组成的图称为 （ A ）A. 零图； B平凡图； C. 完全图； D. 多重图.21.仅由一个孤立点组成的图称为 （ B ）A. 零图； B平凡图； C.多重图； D. 子图.22.在任何图中必有偶数个 （ B ）A. 度数为偶数的结点； B度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点.23.设为有个结点的无向完全图，则的边数为 （ C ）A. B C. D. 24.在有个结点的连通图中，其边数 （ B ）A. 最多条； B至少条；C. 最多条； D. 至少条.25.任何无向图中结点间的连通关系是 （ B ）A. 偏序关系； B等价关系；C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系.26.对于无向图，下列说法中正确的是. （ B ）A不含平行边及环的图称为完全图B任何两个不同结点都有边相连且无平行边及环的图称为完全图C具有经过每条边一次且仅一次回路的图称为哈密尔顿图D具有经过每个结点一次且仅一次回路的图称为欧拉图27.设D是有向图，则D强连通的充分必要条件为. ( C )A略去D中各边方向后所得到的无向图是连通的BD是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图CD的任意两个不同的结点都可以相互到达DD是完全图28.对于无向图G，以下结论中不正确的是. （ A ）A如果G的两个不同结点是连接的，则这两个结点之间有初级回路B如果G的两个不同结点是连接的，则这两个结点之间至少有一条短程C如果G是树，则任何两个不同结点之间有且仅有一条初级通路 D如果G是欧拉图，则G有欧拉回路29.命题公式是( B )。(A) 矛盾式 (B) 重言式 (C) 非永真的可满足式 (D) 以上都不对30. 设个体域为全体自然数集合，下列公式中真值为T是( C )。(A) (B) (C) (D) 31.谓词公式，以下陈述错误的是（ C ）。(A) x的辖域是(B) $x的辖域是Q(x,y) (C) R(x,y)中的x是自由出现(D)此公式等值于 32.设A,B,C为任意集合,下列表达正确的是( A )。(A) (B) AB AB(C)ABAC BC (D) ABA AB=A 33. 设A1,2,B=a,d,c,C=c,d, 则(BC)A= ( C )。(A), (B),(C), (D), 34.设N是自然数集合，则下列四个陈述不对是( B )。(A) 是N上的偏序关系 (B) =不是N上的等价关系(C) 是N上的偏序关系 (D) 是N上的线序关系 35.下面四个图中，哪个是欧拉图( D )。36.设个体域，与公式等价的命题公式是( )AB CD37.设A=a,b,c，则下列是集合A的划分的是( )A.B. C.D. 38.下列谓词公式中是前束范式的是（ ）。A B CD39.下列公式是前束范式的是（ ）。ABC D二、填空题 1 设集合A,B，其中A1,2,3, B= 1,2, 则A - B_3 ; r(A) - r(B) _3,1,3,2,3,1,2,3. 2. 设有限集合A, |A| = n, 则|r(AA)| = _. 3. 设R是集合A上的等价关系，则R所具有的关系的三个特性是答案： 自反性；对称性；传递性.4. 设集合A1,2,3,4, A上的关系R1 = (1,4),(2,3),(3,2), R1 = (2,1),(3,2),(4,3), 则R1R2=_(1,3),(2,2),(3,1); R2R1 =_(2,4),(3,3),(4,2); R12=_(2,2),(3,3).5. 设有限集A, B，|A| = m, |B| = n, 则| |r(AB)| = _2mn._6. 设G是具有8个顶点的树，则G中增加_21_条边才能把G变成完全图。7. 设集合A1, 2, 3, 4，A上的二元关系R(1,1),(1,2),(2,3),S(1,3),(2,3),(3,2)。则RS_(1, 3),(2, 2); R2_(1, 1),(1, 2),(1, 3). 8、使命题公式P (PQ)成假的赋值是 10 设 天气很冷，老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 .9.设天下雨， 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 .10. 设的真值为0，的真值为1，则命题公式的真值为 .011.设的真值为0，的真值为1，则命题公式的真值为 .012. 设树T中有7片树叶，3个3度结点，其余都是4度结点，则T中有 个4度结点.解 用握手定理和树的性质列出方程求解，设有个4度结点，13.设A1,2,B=x,y,则AB=,。14.集合的 ； 。15.设表示“会飞”，论述域为鸟，则命题“一切鸟都会飞”可译为：；16.若集合A上的二元关系R的关系矩阵主对角线上元素全是1，则关系R具有 自反 性质。17.连通无向图G有9个顶点14条边，要得到G的一棵生成树，必须删去 6 条边。18.设为树，中有4度，3度，2度分支点各1个，问中有 片叶。解 与上题解法相同，设有片树叶，19如A=a,b,c,P(A)的成员 ,a,b,c,a,b,a,c,b,c,a,b,c , |P(A)|= _8_ |A|=_3_X=1,2,3 Y=a,b,则XY=_=1,a,1,b,2,a,2,b,3,a,3,b_二综合题：1.用符号形式写出下列命题 a) 假如上午不下雨,我去看电影;否则就在家里读书或看报. b) 我今天进城,除非下雨. c) 仅当你走,我将留下. 解a)设P:上午天下雨. Q:我去看电影 R:我在家读书 S:我在家看报 原命题可译为:(PQ)(P(RS) b)设:P:我今天进城 Q:天下雨 原命题可译为:QP c)设:P:你走 Q:我留下，原命题可译为:QP2.（2.1 集合）如果X1, 2, 3，Ya, b，写出：XY， YX，XX，YY解：XY(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)YX(a,1), (b,1), (a,2), (b,2), (a,3), (b,3)XX(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)YY(a, a), (a, b), (b, a), (b, b)3.（3.1 关系）从集合X2, 3, 4到Y3, 4, 5, 6, 7的关系R定义为(x,y)R 如果x整除y，写出关系R，及R-1解：R(2,4), (2,6), (3,3), (3,6), (4,4)。R-1(4,2), (6,2), (3,3), (6,3), (4,4)。这种关系可用文字描述为“被整除”。 4. 偏序集的哈斯图如下所示。试写出A和R的集合表达式；求A的子集B=b,c,d的极大元,最大元和上界。解： A=a,b,c,d,e, R=, B的极大元b,c,无最大元，上界是a。 5.设A=a,b,c,d，A上的二元关系R=,画出R的关系图，求出R的逆关系；求R的对称闭包s(R) 解：R的关系图 R的逆关系, s(R)=, ,。 6.设集合A1, 2, 3, 4, 6, 8, 9, 12，R为整除关系。(1) 画出半序集(A,R)的哈斯图；(2) 写出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界；(3) 写出A的最大元，最小元，极大元，极小元。答案： (1)(2) B无上界，也无最小上界。下界1, 3; 最大下界是3.(4)7. 设集合A1, 2, 4, 6, 8, 12，R为A上整除关系。（1）画出半序集(A,R)的哈斯图；（2）写出A的最大元，最小元，极大元，极小元；（3） 写出A的子集B = 4, 6, 8,