离散数学复习题

1、离散数学复习题一、单项选择题1.下列命题公式为重言式的是【 a 】。ap (pq)b(pp)qcqqdpq2下列语句中不是命题的是【 a 】。a这个语句是假的。b1+1=1.0c飞碟来自地球外的星球。d凡石头都可练成金。3设a=，1，1，3，1，2，3，则a上包含关系“”的哈斯图为【 c 】4在公式中变元y是【 b 】。a自由变元b约束变元c既是自由变元，又是约束变元d既不是自由变元，又不是约束变元5设a=1，2，3，a上二元关系s=，则s是【 d 】。a自反关系b反自反关系c对称关系d传递关系6图 中 从v1到v3长度为3 的通路有【 d 】条。 a0； b1； c2； d3。7在下列代数系

2、统中，不是环的只有【 c 】。az，+，*)，其中z为整数集，+，*分别为整数加法和乘法。b(q，+，*)，其中q为有理数集，+，*分别为有理数加法和乘法。c，其中r为实数集，+为实数加法，a*b=a+2b。d，其中mn(r)为实数集nn阶矩阵结合，+，*是矩阵加法和乘法。8下列整数集对于整除关系都构成偏序集，而能构成格的是【 b 】。al，2，3，4，5b1，2，3，6，12c2，3，7dl，2，3，79结点数为奇数且所有结点的度数也为奇数的连通图必定是【 d 】。a欧拉图b汉密尔顿图c非平面图d不存在的10无向图g是欧拉图当且仅当g是连通的且【 c 】。ag中各顶点的度数均相等bg中各顶点

3、的度数之和为偶数cg中各顶点的度数均为偶数dg中各顶点的度数均为奇数11.设s=0，1，*为普通乘法，则是【 b 】。 a.半群，但不是独异点； b.只是独异点，但不是群； c.群 ； d.环，但不是群；12设（a，+，）是代数系统，其中+，是普通的加法和乘法运算，能使（a，+，）成为环的集合a是【 a 】。a所有偶数组成的集合； b所有奇数组成的集合； c所有正整数组成的集合； d所有非负整数组成的集合。13设a=1，2，3，则a上的二元关系有【 c 】个。 a 23 ； b 32 ； c ； d 。14在【 a 】下有。a； b、c、； d、15下列结果正确的是【 b 】。a； b；c；

4、d。 16设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是【 b 】。apqbpqcpqdpq 17下列函数是双射的为【 a 】af : ie , f (x) = 2x ； bf : nnn, f (n) = ；cf : ri , f (x) = x ； df :in, f (x) = | x | 。（注：i整数集，e偶数集， n自然数集，r实数集）18有向图中d= ，则长度为2的通路有【 d 】条。a0； b1； c2； d3 。19在一棵树中有7片树叶，3个度为3的结点，其余都是度为4的结点，则该树有【 a 】个度为4的结点。a1； b2； c3； d4 。

5、20下图中既不是eular图，也不是hamilton图的图是【 b 】二、填空题请在每小题的空格中填上正确答案。错填、不填均无分。1.命题逻辑与谓词逻辑的区别是。2.谓词逻辑中，命题被分解为_, _两部分。3.集合的常用表示方法有_, _, _和图示法四种。4.具有_, _和_ 三种性质的二元关系叫等价关系。5.n阶有向完全图的边数为_, n阶无向完全图的边数为_。6.如果一个图的每条边都是_称为有向图，每条边都是 称为无向图。7.若图中存在_的通路， 该图称为半欧拉图。8.有向图树t中，_称为根，_称为树叶。9.设r是a上的二元关系，当有（a,b）r和（b,c）r时，必有 ,则称r为可传递的

6、二元关系。abca b cb b cc c b10.设代数系统，其中a=a，b，c,则幺元是 ；是否有幂等性 ；是否有对称性 。 11.能够判断_称为命题。 12.不包含任何联结词的命题叫做_命题, 至少包含一个联结词的命题叫做_命题。 13.二元关系的表示方法有_, _, _ 三种。 14.（1）a，b，c表示三个集合，文图中阴影部分的集合表达式为 a b c 。（2）设p，q 的真值为0，r，s的真值为1，则的真值= 。（3）公式的主合取范式为 。 15.，*表示求两数的最小公倍数的运算（z表示整数集合），对于*运算的幺元是 ，零元是 。 16.将有向图d各边的方向去掉得无向图g, 称g为

7、d的_。 17.若图中存在_回路， 该图称为欧拉图。 18.拉格朗日定理说明若是群的子群，则可建立g中的等价关系r= 。若|g|=n, |h|=m 则m和n关系为 。19根据入射函数，满射函数，双射函数的定义填空。设n是自然数集合，z是整数集合，r是实数集合，则f1（nn, f1（n）= n2）是 函数；f2（nn, f2（n）= n + 10）是 函数；f3（zz, f3（z）= z + 10）是 函数；f4（rr, f4（r）= r +5.6）是 函数；f5（z0,1,当z为偶数时，f5(z)=1;当z为奇数时，f5(z)=0。）是 函数。填空题参考答案：1.在命题逻辑中，原子命题是进行演

8、算的基本单位，不再研究命题的内部结构。而谓词逻辑的任务就是对原子命题作进一步的分析，研究其内部的逻辑结构。2.个体词和谓词两部分。 3.列举法、叙述法、特定字母集和图表法。4自反性、对称性和传递性 5. n2和n(n-1)/26有向边和无向边 7一条通过图中各边一次且仅一次的通路。8入度为零的顶点称为根，出度为零的顶点称为叶子。9（a,c）r 10. a、 否、 有 11能够判断内容真假的语句称为命题。12原子和复合。 13表格法、矩阵法和图表法。 14.(1)；(2)1；(3) 15不存在、e 16.底图 17一条通过图中各边一次且仅一次的回路。 18、 19入射、入射、双射、双射、满射。三

9、、判断说明题判断下列各题正误，正确的在题后括号内打“”，错误的打“”，并说明其正确或错误的理由。（一） 判断下列语句那些是命题1我是工程师。 【 】2计算机有空吗？ 【 】36是奇数。 【 】4太美妙了！ 【 】5.雪是白的。 【 】6.我是大学生 【 】7.雪是黑的。 【 】8.外星人是存在的。 【 】9.请打开门！ 【 】10.这束花多么好看啊！ 【 】（二）下列函数中（15小题），哪些是单射函数，满射函数，双射函数。其中n是自然数集合，i是整数集合，r是实数集合。已知集合a =a, b, c，集合b =1, 2, 3, 下列ab的二元关系中，r1r5哪些可以构成函数。1f：nn, f（n

10、）= 2n 【单射 】2f：ab,a=0,1,2,b=0,1,2,3,4,f(a)=a2 【单射 】3f：ii, f（i）= i + 10 【 双射 】 4f: ii, f(i)=|i| 【 既不是单射，也不是满射】 5.f: i0,1,当i为偶数时，f(i)=0;当i为奇数时，f(i)=1。 【满射 】 6.r1 = （a, 1）,（b, 2）,（c, 3） 【 】 7.r2 = （a, 3）,（c, 2）,（c, 1） 【 】 8.r3 = （a, 2）,（b, 1）,（b, 2）,（c, 3） 【 】 9.r4 = （b, 1）,（c, 3） 【 】 10.r5 = （a, 1）,（b,

11、 1）,（c, 3） 【 】 四、表述题：将下列命题符号化（一） 命题逻辑符号化1.我美丽而又快乐。2.如果老张和老李都不去，他就去。3.电灯不亮，当且仅当灯泡或开关发生故障。 4.王强工作努力且身体好。 5.我是本次校运动会的跳远或100米短跑的冠军。 6.只要有学习机会，我一定用功读书。 7.两个三角形全等，当且仅当它们的三个对应边相等。 8.如果不下雨，我不乘公交车上班。（二） 谓词逻辑符号化（论域为全部个体域） 1.小张不是学生。 2.所有的有理数都是实数。 3.小张大于18岁，身体健康，无色盲，大学毕业，则他可参加飞行员考试。 4.小王不是研究生。37他是跳高或篮球运动员38.晓莉非

12、常聪明和能干39.若m是奇数，则2m是偶数。四、参考答案：（一）1.设p表示命题“我美丽”，q表示命题“我快乐”。则用符号表示命题为：pq2.p表示“老张去”；q表示“老李去”；r表示“他去”。则（pq）r。3.设p表示“电灯不亮”，q表示“灯泡发生故障”；r表示“开关发生故障”。则p（qr）。 4.设p表示命题王强工作努力，q表示命题王强身体好。则用联结词表示复合命题为：pq 5.设p：我是本次校运动会的跳远冠军q：我是本次校运动会的100米短跑的冠军，则pq。 6.设p：有学习机会，q：我一定用功读书，则pq。 7.设p：两个三角形全等，q：三个对应边相等，则pq 8.p：下雨，q：我不乘

13、公交车上班。则pq。 （二） 1.令s（x）:x是学生；a:小张；则s(a) 2. 设q(x):x是有理数；r(x):x是实数，则符号化为：x(q(x) r(x) 3.设a(x):x超过18岁；b(x):x身体健康；c(x):x 色盲；d(x):x大学毕业 e(x):x参加飞行员考试；a:小张；则a(a)b(a)c(a)d(a) e(a)。 4.设a(x):x是研究生；a:小王，则a(a)。 5.设a(x):x是跳高运动员；b(x):x是篮球运动员；a：他；则a(a)b(a) 6.设a(x):x非常聪明；b(x): x能干；a: 晓莉；则a(a)b(a) 7.a(x):x是奇数；b(x): x

14、 是偶数；m:某整数；则a(m) b(2m)。五、计算题1构造 公式：p q的真值表2.已知集合a =1, 2, 求集合a的幂集p（a）。3. 已知集合a =a, b, 求集合a 上的笛卡尔积aa.4. 知集合a =a, b, c, d, r=（a, a）,（a, c）,（a,d）,（b,a）,（b,b）,（b,d）,（c,a）,（d,b）,（d,c） 是a上的关系，试用矩阵表示法表示r。5. 试画出树叶权为1，2，3，5，7，12的最优二元树，并求出该树的权。 6.求公式( p q ) ( p q )的真值表。 7已知集合a =1, 2, 3, 求集合a的幂集p（a）。8已知集合a =a,

15、b, c, 求集合a 上的笛卡尔积aa. 9画出一个3阶有向完全图10（a，r）是偏序集，a=2，3，4，5，6，8，12，16，24，r是a上的整除关系。试写出a中的所有极大元和极小元，它有没有最大元和最小元？ 五、参考答案： 1.pqp qfftftttffttt2.因为a2，所以a的幂集p（a）224。p（a），1,2,1,2 3.aa=a,ba,b=(a,a),(a,b),(b,a),(b,b), 4.a =a, b, c, d, r=（a, a）,（a, c）,（a,d）,（b,a）,（b,b）,（b,d）,（c,a）,（d,b）,（d,c） 矩阵表示：101111011000011

16、01811633001275312 5. 最优二元树为：最优二元树的权为： w=12+18+2*(7+11)+3*(5+6)+4*(3+3)+5*(1+2)=138 6.pqpqp qp q( p q ) ( p q )ttffffftfftfttfttftftffttfff 7.因为a3，所以a的幂集p（a）238。p（a），1,2,3,1,21,3,2,3,1,2,3 8aa=a,b,ca,b,c=(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)v1v3v1 9. 10极大元为：5，16，24；极小元为：2，3，5。无最大和最小元。六、证明题1设r是a上的反自反关系和可传递关系，证明r是a上的反对称关系。2. 若图g中恰有两个奇数顶点，则这两个顶点是连通的。3.设a和b是集合，证明a（b-a）=ab。4r是集合x上的一个自反关系，求证：r是对称和传递的，当且仅当 和在r中，则有在r中。六、参考答案：1.证：因为当ab，且（a,b）r时