离散数学试题与答案

1、离散数学试题与答案【篇一：离散数学试题及答案】一、填空题1 设集合 a,b ,其中 a= 1,2,3, b= 1,2, 则 a- b =; = .3. 设集合 a = a, b, b = 1, 2, 则从 a 到 b 的所有映射是, 其中双射的是4. 已知命题公式g = ?(p?q) Ar,则g的主析取范式是5. 设 g 是完全二叉树，g 有 7 个点，其中4 个叶点，则g 的总度数为 ，分枝点数为.7 . 设 r 是集合 a 上的等价关系，则r 所具有的关系的三个特性是8 .设命题公式g = ?(p?(q?r),则使公式g为真的解释有9 .设集合 a = 1,2,3,4, a 上的关系 ri

2、 = (1,4),(2,3),(3,2), ri =(2,1),(3,2),(4,3), 则 r1?r2 = ,r2?r110 . 设有限集a, b ， |a| = m, |b| = n, 则 | |?(a?b)| =11设a,b,r是三个集合，其中r是实数集，a = x | - 1<x< 1, x?r, b =x | 0< x 2, x?则 a-b =, b-a =, aA b =,.13 .设集合a = 2, 3, 4, 5, 6，是a上的整除，则r以集合形式(列举法)记为 14 . 设一阶逻辑公式g = ?xp(x)?xq(x) ，则 g 的前束范式是15 .设 g 是

3、具有 8 个顶点的树，则g 中增加 条边才能把g变成完全图。?(a) - ?(b) r1216 .设谓词的定义域为a, b,将表达式？xr(x) -?xs(x)中量词消除， 写成与之对应的命题公式是17 .设集合 a = 1, 2, 3, 4 , a 上的二元关系 r = (1,1),(1,2),(2,3), s =(1,3),(2,3),(3,2)。则 r?s = r2 =二、选择题1设集合a=2,a,3,4 , b = a,3,4,1 , e为全集，则下列命题正确的是 ( )。(a)2?a(b)a?a(c)?a?b?e (d)a,1,3,4?b.2 设集合 a=1,2,3,a 上的关系 r

4、= (1,1),(2,2),(2,3),(3,2),(3,3),则 r 不具备 ( ).(a)自反性(b)传递性(c)对称性(d)反对称性则元3设半序集(a, w菠系 啪哈斯图如下所示，若 a的子集素6为b的()。(a)下界(b)上界(c)最小上界(d)以上答案都不对4下列语句中，()是命题。(a)请把门关上(b)地球外的星球上也有人(c)x + 5 6 (d) 下午有会吗？5 设 i 是如下一个解释：d = a,b, p(a,a) p(a,b) p(b,a) p(b,b) 1 01 0则在解释i 下取真值为1 的公式是( ).(a)?x?yp(x,y)(b)?x?yp(x,y)(c)?xp(

5、x,x) (d)?x?yp(x,y).6 . 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是 ( ).(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).7 .设g、h是一阶逻辑公式，p是一个谓词，g = ?xp(x), h =?xp(x), 则一阶逻辑公式g?h 是 ( ).(a)恒真的(b)恒假的可满足的(d)前束范式.8设命题公式g = ?(p?q) , h = p?(q?p)，则g与h的关系是()。(a)g?h(b)h?g(c)g = h (d)以上都不是.9设a, b为集合,当()时a b =

6、 b.(a)a = b (b)a?b (c)b?a (d)a = b = ?.10 设集合 a = 1,2,3,4, a 上的关系 r=(1,1),(2,3),(2,4),(3,4), 则 r 具有 ( )。(a)自反性(b)传递性 对称性(d)以上答案都不对11 下列关于集合的表示中正确的为( )。(a)a?a,b,c (b)a?a,b,c (c)?a,b,c (d)a,b?a,b,c12 命题 ?xg(x) 取真值 1 的充分必要条件是( ).(a)对任意x, g(x)都取真值1.(b)有一个x0,使g(x0)取真值1.有某些x,使g(x0)取真值1.(d)以上答案都不对.13 . 设 g

7、 是连通平面图，有5 个顶点，6 个面，则g 的边数是( ).(a) 9 条 (b) 5 条 (c) 6 条 (d) 11 条 .14 . 设 g 是 5 个顶点的完全图，则从g 中删去 ( )条边可以得到树.(a)6(b)5(c)10 (d)4.1111?0100? ，则 1011?0101?0110?0?1 的相邻矩阵为 ?1?1?115. 设图 gg 的顶点数与边数分别为( ).(a)4, 5 (b)5, 6 (c)4, 10 (d)5, 8.三、计算证明题(1) 集合 a = 1, 2, 3, 4, 6, 8, 9, 12 , r 为整除关系。(1)画出半序集(a,r)的哈斯图；(2)

8、 写出 a 的子集 b = 3,6,9,12 的上界，下界，最小上界，最大下界；(3) 写出 a 的最大元，最小元，极大元，极小元。2.设集合 a = 1, 2, 3, 4 , a 上的关系 r = (x,y) | x, y?a 且 x ? y,求1) ) 画出 r 的关系图；2) ) 写出 r 的关系矩阵.3) 设 r 是实数集合，?,?,? 是 r 上的三个映射，?(x) = x+3, ?(x) =2x, ?(x) = x/4,试求复合映射 ? ， ?, ?, ? ， ?.4) 设 i 是如下一个解释：d = 2, 3,a3 b 2 f (2) 3 f (3) 2 p(2, 2) p(2,

9、 3) p(3, 2) p(3, 3) 0 0 1 1试求(1) p(a, f (a) A p(b, f (b);(2) ?x?y p (y, x).5.设集合a = 1, 2,4, 6, 8,12，为a上整除关系。(1)画出半序集(a,r)的哈斯图；(2) 写出 a 的最大元，最小元，极大元，极小元；(3) 写出 a 的子集 b = 4, 6, 8, 12 的上界，下界，最小上界，最大下界 .6 .设命题公式g = ?(p f q)V (q A (?p f r),求g的主析取范式。7 . (9 分)设一阶逻辑公式：g = (?xp(x) V ?yq(y) f ?xr(x)，把 g 化成前束范

10、式.9. 设 r 是集合 a = a, b, c, d. r 是 a 上的二元关系, r = (a,b), (b,a),(b,c), (c,d),(1) 求出r(r), s(r), t(r) ；(2) 画出r(r), s(r), t(r) 的关系图.11. 通过求主析取范式判断下列命题公式是否等价：(1) g = (p A q) V (?p A q A r)(2) h = (p V (q A r) A (q V (?p A r)13.设r和s是集合a = a, b, c, d上的关系，其中r = (a, a),(a, c),(b, c),(c, d), s = (a, b),(b, c),(b

11、, d),(d, d).(1) 试写出 r 和 s 的关系矩阵；(2)计算 r?s, r Us, r1, s1?r1.四、证明题1 .利用形式演绎法证明：pfq, r s, pV r蕴涵qVs。2 .设a,b为任意集合，证明：(a-b)-c = a-(b U c).3 .(本题10分)利用形式演绎法证明：?a V b, ?c ?b, c d1涵 a d o4 . ( 本题 10 分 )a, b 为两个任意集合，求证：a (a Ab) = (aU b) b .参考答案一、填空题1. 3; 3,1,3,2,3,1,2,3.2. 2.n23. ?1= (a,1), (b,1), ?2= (a,2),

12、 (b,2),?3= (a,1), (b,2), ?4=(a,2), (b,1); ?3, ?4.4. (p A ?q A r).5. 12, 3.6. 4, 1, 2, 3, 4, 1, 2. 7. 自反性；对称性；传递性.8. (1, 0, 0),(1, 0, 1), (1, 1, 0).9. (1,3),(2,2),(3,1); (2,4),(3,3),(4,2); (2,2),(3,3).10. 2m?n.11. x | - 1<x 0, x?r; x | 1 x 2, x?r; x | 0<x< 1, x?r.12. 12; 6.13. (2, 2),(2, 4),

13、(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6,6).14. ?x(?p(x) Vq(x).15. 21.【篇二：离散数学练习题及答案】的表示方法有两种：法。请把“奇整数集合”表示出， k?z 来 。 1、列举；描述；x|x?2k?12 、无向连通图g 含有欧拉回路的充分必要条件是2*、连通有向图d 含有欧拉回路的充分必要条件是d 中每个结点的入度=出度.3 、设 r 是集合 a 上的等价关系，则r 所具有的关系的三个特性是自反性、对称性、传递性.4 、有限图g 是树的一个等价定义是：.5、设n(x) ： x 是自然数，z(y)； y 是整数，则命题“自然数都是整数

14、，而有的整数不是自然数 ”符号化为?x(n(x)?z(x)?x(z(x)?n(x)6 、在有向图的邻接矩阵中，第i 行元素之和,第 j 列元素之和分别为结点 v 的出度和结点v 的入度7 、设 a， b 为任意命题公式，c 为重言式，若a?c?b?c ，那么命题a?b 是重言式的真值是1 8 、命题公式?(p?q) 的主析取范式为9、设图g =v, e和g? = v?,e?,若g?是g的真子图，若，贝U g?是g的生成子图.v?v或e?e;v?v,e?e10、在平面图g?v,e? 中 ,则11、设 a?a,b,?deg(r)=淇中 r(i=1,2,rig 的面 iiri?1b?1,2 ，则从

15、a 到 b 的所有映射是11 、 ?1= ( a， 1)，( b， 1) ； ?2= ( a， 2)，(b， 2) ； ?3=( a， 1)，( b，2) ； ?4= ( a，2 )，( b ， 1 ) 12、表达式？x?yl (x, y)中谓词的定义域是a, b, c,将其中的 量词消除，写成与之等价的命题公式为12、(l(a，a)?l (a，b)?l (a，c)?( l( b， a) ?l (b，b) ?l(b，c)?(l(c，a)?l(c，b)?l( c， c)12*、设个体域d = a,b,公式？x(g(x)?yh(x,y)消去量词化为13、含有三个命题变项p， q， r 的命题公式p

16、?q 的主析取范式是14、设r， s 都是集合a 上的等价关系，则对称闭包s(r?s)=15 、设g 是连通平面图，v,e,r 分别表示g 的结点数，边数和面数，则v,e和 r 满足的关系式是 v?r?e?16、设g是n个结点的简单图，若g,则g 一定是哈密顿图.17、一个有向树t 称为根树，若称为树叶. 若有向图t 恰有一个结点的入度为0，其余结点入度为1 ；入度为 0 的结点；出度为0 的结点 .18 、图的通路中边的数目称为结点不重复的通路是通路. 边不重复的通路是 通路 . 通路长度；初级；简单.19、设 a 和 b 为有限集，|a|=m ， |b|=n ，则有个从 a 到 b 的关系

17、，有 个从 a 到 b 的函数，其中当m?n 时有 个入射，当m=n 时，有个双射。19、 2m*nm,nm,cn?m!,m!2a?n|n?n (是/不是)可数的。是20、集合21 、设 l?1,2,3,4,12? 上的整除关系?a1,a2a1,a2?l,a1 整除 a2 ?在 l 上定义两个二元运算? 和 ? ：对任意a,b?l ， a?b?glb(a,b) ，a?b?lub(a,b)。请填空(在横线上填是或不是)：是 是 是不是代数系统?l,?,? 格。 代数系统?l,?,? 有界格。代数系统 ?l,?,? 有补格。代数系统?l,?,? 分配格。二、单项选择题(选择一个正确答案的代号，填入

18、括号中)1 、设命题公式g= ?( p?q )， h=p? ( q? ?p )，则 g 与 h 的关系是( a )。a g?hb h?g c g=h d 以上都不是2 、下列命题公式等值的是( c )(a)?p?q,p?q(c)q?(p?q),?q?p?q(b)a?(a?b),?a?(a?b)(d)?a?(a?b),b3、设v = a,b,c,d,与v能构成强连通图的边集e = ( a )(a) a,b,a,c,d,a,b,d,c,d (b) a,d,b,a,b,c,b,d,d,c(c) a,c,b,a,b,c,d,a,d,c (d) a,d,b,a,b,d,c,d,d,c4、设 l(x) ：

19、 x 是演员， j(x) ： x 是老师，a(x,y) ： x 佩服 y. 那么命题“所有演员都佩服某些老师 ”符号化为( b )(a) ?xl(x)?a(x,y)(b) ?x(l(x)?y(j(y)?a(x,y)(c) ?x?y(l(x)?j(y)?a(x,y)(d) ?x?y(l(x)?j(y)?a(x,y)5 、在由 3 个元素组成的集合上，可以有(d ) 种不同的关系。(a)3 (b)8(c) 9 (d) 5126、设 s1=?,s2=?,s3=p(?),s4=p(?) 则命题为假的是( a ) (a)s2?s4(b) s1?s3 (c) s2?s4 (d) s4?s37 、设 g 是

20、连通平面图，有v 个结点，e 条边， r 个面，则r= ( a )(a) e v 2(b)v e 2(c)e v 2(d) e v 28 、下列命题正确的是(a )。a ?=? b ?=?c a?a ， b， c d ?a ， b， c9、设a, b, c都是集合，如果 a?c =b?c ,则有(c )(a) a = b (b) a?b (c) 当 a c = b c 时，有 a=b (d)当 c=u 时，有a?b10、设 (b,?,?,0,1) 是布尔代数，?a,b?b,a?b ，则下式不成立的是(d ) (a)ab?0(b)a?b?1(c)a?b?a(d)a?b?111 、下面给出的一阶逻

21、辑等价式中，(a )是错的。a?x ( a(x)?b (x)=?xa(x)?xb(x)b a?xb(x)=?x(a?b ( x)c ?x ( a(x)?b (x)=?xa(x)?xb(x)d ?xa ( x) =?x ( ?a( x)三、多重选择题(每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)1、命题公式(pA(pfq)fq是 式。(1) 重言 (2) 矛盾 (3) 可满足 (4) 非永真的可满足2、给定解释i=(d,ic)=( 整数集，f(x,y):f(x,y)=x-y ；g(x,y):g(x,y)=x+y ；p(x,y):xy)

22、，下列公式中在解释 i 下为真。(1) p(f(x,y),g(x,y) (2) ?x?y p(f(x,y),g(x,y)？x?y(p(x,y)- p(f(x,y),x) (4) ?x?y p(f(x,y),g(x,y)3、A 是集合，a =10,则 p(a)= 。(1) 100(2) 99 (3) 2048 (4) 1024(5) 5124、集合A =x|x 是整数，x230 , B =x|x 是质数，x20 , c=1,3,5, 则 (a?b)?c=; (b?a)?c=; (c?a)?(b?a)=; (b?c)?a= 。(1) 1,2,3,5(2) ? (3) 0 (4) 1,3,5,7,1

23、1,13,17,19(5) 1,3,5,7 (6) 7,11,13,17,195、设a、 b、 c 是集合，下列四个命题中，在任何情况下都是正确的。(1)若 a?b 且 b G c,贝fj a G c (2)若 a?b 且 b G c,贝fj a?c(3)若 a G b 且 b?c ,则 a?c (4)若 a G b 且 b?c，则 a G c6、设集合A =a,b,c,d,e,f,g , A 的一个划分？=a,b,c,d,e,f,g, 则?所对应的等价关系有个二元组。(1) 14 (2) 15(3) 16 (4) 17 (5) 8 (6) 49 (7) 5127、s =1,2,3,4,5,6

24、,7,8,9,10,11,12, 逗 s 上的整除关系。s 的子集B =2,4,6 ,则在 s, w中，B的最大元是 ; B的最小元是 ;B的上确界是 ; B的下确界是 。(1) 不存在的(2) 36(3) 24 (4) 12 (5) 6 (6) 1 (7) 28、设有有限布尔代数(b,+,*, ,0,1，则 )b= 能成立。(1) 1 (2) 2 (3) 3 (4) 4 (5) 5(6) 8(7) 99、g =0,1,2,?,n , n Gn,定义？为模 n 加法，即 x?y =(x+y) modn ，则代数系统(g， ?) 。(1) 是半群但不是群(2) 是无限群(3) 是循环群(4) 是

25、变换群(5)是交换群10、仅有一个结点的图称为()，当然也是( )(1) 零图 (2) 平凡图 (3) 补图 (4) 子图1. 1 、3。2.4。3. 4。4.1 ；4； 2；2。5. 4。7. 1 ；7；4；7。8. 2、4、6。9. 3、5。10. 2； 1。四、化简解答题1、(1)设图g(如第1题图)，作图g的嵌入图，说明图g是平面图.第 1 题图 1 、 (1)图 g 的嵌入图，如第12 题答案图.故图g 为平面图(4 分 )第 12 题答案图(2)在具有 n 个顶点的完全图kn 中删去多少条边才能得到树？解： n 个顶点的完全图kn 中共有 6. 4。 n?(n?1) 条边， n 个

26、顶点的树应有 n?1 条边，于是，删2n?(n?1)(n?1)?(n?2)?(n?1)? 去的边有：。222、判别谓词公式?x?yf(x,y)?y?xf(x,y) 的类型 .2 、设 i 为任意一个解释，d 为 i 的个体域. 若在解释i 下，该公式的前件为0，无论?y?xf(x,y) 如何取值，?x?yf(x,y)?y?xf(x,y) 为 1 ；若在解释i 下，该公式的前件为1 ，则 ?x0?d, 使得 ?yf(x,y) 为 1，它蕴含着？y?d,f(x0,y?)为1?xf(x,y?)为1,由y?的任意性，必有 ?y?xf(x,y) 为 1 ，于是 ?x?yf(x,y)?y?xf(x,y)

27、为 1.所以， ?x?yf(x,y)?y?xf(x,y) 是永真式3、化简集合表达式：(a?b?c)?(a?c) (c?(c b) a)3、(a?b?c)?(a?c) (c?(c b)?a)= (a?c) (c?a)(两次用吸收律)=(a?c)?(c?a)=(a?c)?(c?c)?a?(a?c)=(a?c)?a=a4 、判断下列哪些运算结果是对的？哪些是错的？请将错误的运算结果更正过来(1) ? (2) ?(3) ?,? (4) ?,?,?( 5) (a?b)?b?a ( 6) (a?b)?b?a( 7) a?a?a ( 8) (a?b)?a?4、 (1) 对 (2) 错应为? (3) 对 (

28、4) 错应为?( 5)错应为a?b ( 6)错应为a?b( 或 a?b 或a ab)( 7)错应为?，即 a?a?a?a?a?a?( 8)对5、将命题公式?p?q?(?r?p) 化为只含?和 ?的尽可能简单的等值式 5、 ?p?q?(?r?p)?(p?q)?(r?p) (优先级有误)?(p?q)?(?p?r) 不惟一 .(1) v1e5 v5e7 v2e2 v3 (2) v5e6 v2e2 v3e3 v4e8 v2e7 v5 v254 (3) v2e7 v5e6 v2 (4) v1e1 v2e2 v3e3 v4e8 v2e6 v5ev46、 (1) 初级通路；(2) 简单回路；(3) 初级回路

29、；(4) 简单通路.e3v ev 7 、试问 n 取何值时，无向完全图kn ，存在一条欧拉回路？6 、设图 g 如右图 . 已知通路7 、由于 kn 有 n 个结点，并且每个结点的度数均为n 1，于是，当 n 为奇数时，kn 的每个结点的度数都是偶数，所以存在一条欧拉回路8、已知 (l ， *， ?)是格，且二元运算*和 ?满足分配律，?a,b,c?l ，化简表达式(a*b)?(a*c)* (a*b)?(b*c)解答： (a*b)?(a*c)*(a*b)?(b*c)=(a*b)? ( (a*c)* (b*c)( 分配律)=(a*b) ?(a*b)*c) ( 幂等律 )=a*b( 吸收律 )9

30、、化简 (?p?(?q?r)?(q?r)?(p?r)。9、 (?p?(?q?r)?(q?r)?(p?r)=(?p?q?q?p)?r=(?p?q?p)?r=r10、试将一阶逻辑公式?x?yp?x,y?yq?y?r?x? 化成前束范式。 解：【篇三：离散数学试卷及答案】t> 一、填空20% (每小题2分)1.设 a?x|(x?n)且(x?5),b?x|x?e 且 x?7 (n：自然数集，e+ 正 偶数) 则 a?b? 。 2 a， b， c 表示三个集合，文图中阴影部分的集合表达式为。3设p ， q 的真值为0， r， s 的真值为1 ，则?(p?(q?(r?p)?(r?s) 的真值 = 。

31、4 公式 (p?r)?(s?r)?p 的主合取范式为。5 若解释i 的论域 d 仅包含一个元素，则?xp(x)?xp(x) 在 i 下真值为 。6 设 a=1 ， 2， 3， 4， a 上关系图为则 r2 = 。7 .设a=a , b, c, d,其上偏序关系r的哈斯图为则 r= 。8 图的补图为。9设 a=a ， b， c， d ， a 上二元运算如下：那么代数系统a， *的幺元是，它们的逆元分别为。10下图所示的偏序集中，是格的为。二、选择20% （每小题2 分）1 、下列是真命题的有（）aa?a ；b ?,? ；c?,? ； d ? 。 2、下列集合中相等的有（）a 4， 3? ； b?

32、，3，4； c 4， ?， 3，3；d3， 4。3、设 a=1 ， 2， 3，则 a 上的二元关系有（）个。 a 23 ； b 32 ； c 23?3； d 3 2?2。4、设r, s是集合a上的关系，则下列说法正确的是（）a.若r, s是自反的，则r?s是自反的；b .若r, s是反自反的， 则r?s是 反自反的；c.若r, s是对称的，则r?s是对称的；d .若r, s是 传递的，则 r?s 是传递的。5、设a=1 , 2, 3, 4, p （a）（ a的窑集）上规定二元系如下r?s,t?|s,t?p（a）?（|s|?|t| 则 p（ a） / r=（）a a ； b p（a） ； c1

33、，1 ，2， 1， 2，3， 1 ， 2，3，4； d ? ， 2，2， 3，2，3， 4，a6、设a=? , 1, 1 , 3, 1 , 2, 3则a上包含关系“？的哈斯图为（ ）7 、下列函数是双射的为（）a f : i?e , f （x） = 2x ； b f : n?n?n, f （n） = n , n+1；c f :r?i , f （x） = x； d f :i?n, f （x） = | x |。 （注： i 整数集，e偶数集，n 自然数集，r 实数集）8、图 中 从 v1 到 v3 长度为 3的通路有（）条。a 0；b1；c2；d3。9 、下图中既不是eular 图，也不是hamilton 图的图是（）10、在一棵树中有7 片树叶，3 个 3 度结点，其余都是4 度结点则该树有（）个 4度结点。a 1； b 2；c 3； d 4 。三、证明26%1、r是集合x上的一个自反关系，求证：r是对称和传递的，当且仅当a, b 和 a , c 在 r 中有 .b , c 在 r 中。(