离散数学复习题

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

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

3、为偶数d.中各顶点的度数均为奇数11设s=0,1，*为普通乘法,则是【 b 】。 a.半群，但不是独异点； 只是独异点,但不是群; c.群 ; d环,但不是群；1.设（a，)是代数系统，其中，是普通的加法和乘法运算,能使（，+，）成为环的集合a是【 a 】。a.所有偶数组成的集合； 所有奇数组成的集合； c所有正整数组成的集合; .所有非负整数组成的集合。13设a=，2,则a上的二元关系有【 c 】个。 a23 ； . 2 ； c. ; . 。14.在【 】下有。a.; 、c、; d、5.下列结果正确的是【 b】。a.； b;c； 。6.设p：我很累，q:我去学习，命题：“除非我很累，否则我就

4、去学习”的符号化正确的是【 b】。a.pqb.pqq 7.下列函数是双射的为【 a 】a.f : i , （x) = 2x ； b : , f (n) ；c. ： ri , f (x) = x ; .:in,(x) | x 。(注：i整数集,偶数集, n自然数集,r实数集)18有向图中dv , ，则长度为的通路有【 d 】条。a.0； b.1; c.2; d.3 。1在一棵树中有7片树叶，3个度为3的结点,其余都是度为4的结点，则该树有【 】个度为4的结点。a1； b.2; 3； d4 。0下图中既不是elar图，也不是hmito图的图是【 】二、填空题请在每小题的空格中填上正确答案。错填、不

5、填均无分。.命题逻辑与谓词逻辑的区别是 。2谓词逻辑中，命题被分解为_，_两部分。集合的常用表示方法有_， _， _和图示法四种。4.具有_, _和_ 三种性质的二元关系叫等价关系。5.n阶有向完全图的边数为_,n阶无向完全图的边数为_。6.如果一个图的每条边都是_称为有向图,每条边都是 称为无向图。7.若图中存在_的通路， 该图称为半欧拉图。.有向图树t中，_称为根,_称为树叶。9.设r是上的二元关系，当有(a,)r和（b,c)时，必有 ,则称为可传递的二元关系。ca b c c b10.设代数系统，,其中a=a,b,c,则幺元是 ;是否有幂等性 ;是否有对称性 。 1.能够判断_称为命题。

6、 12.不包含任何联结词的命题叫做_命题, 至少包含一个联结词的命题叫做_命题。 3.二元关系的表示方法有_， _,_三种。 4（1)a,b，表示三个集合,文图中阴影部分的集合表达式为 a b c 。(2)设p,q的真值为0,r，s的真值为1，则的真值= 。(3）公式的主合取范式为 。 15.，表示求两数的最小公倍数的运算（z表示整数集合）,对于*运算的幺元是 ,零元是 。 .将有向图各边的方向去掉得无向图, 称为d的_。 17.若图中存在_回路， 该图称为欧拉图。 1拉格朗日定理说明若的子群,则可建立g中的等价关系r= 。若g|, h|= 则m和n关系为 。1.根据入射函数,满射函数，双射函

7、数的定义填空。设n是自然数集合,z是整数集合,r是实数集合，则f1(nn,f1（n)n2)是 函数；f2（nn， f2（n） n 0）是 函数;f3（z, f3(z）=z 10)是 函数；f4(rr， f(r)= r +5.）是 函数;f(0,当z为偶数时,f(z)=1;当z为奇数时,(z）=0。)是 函数。填空题参考答案:1.在命题逻辑中，原子命题是进行演算的基本单位,不再研究命题的内部结构。而谓词逻辑的任务就是对原子命题作进一步的分析,研究其内部的逻辑结构。2.个体词和谓词两部分。 .列举法、叙述法、特定字母集和图表法。4.自反性、对称性和传递性 5. n和n(n)/2有向边和无向边 7.

8、一条通过图中各边一次且仅一次的通路。.入度为零的顶点称为根，出度为零的顶点称为叶子。9.(a,c) . a、 否、有 11.能够判断内容真假的语句称为命题。.原子和复合。1.表格法、矩阵法和图表法。 4.(1);(2)1；（3) 15不存在、e 6.底图 17一条通过图中各边一次且仅一次的回路。 18.、 19入射、入射、 双射 、双射 、满射。三、判断说明题判断下列各题正误,正确的在题后括号内打“”,错误的打“”,并说明其正确或错误的理由。（一） 判断下列语句那些是命题1.我是工程师。 【 】2计算机有空吗? 【 】36是奇数。 【 】太美妙了！ 【 】5.雪是白的。 【 】6我是大学生 【

9、 】7.雪是黑的。 【 】.外星人是存在的。 【 】9.请打开门! 【 】0.这束花多么好看啊! 【 】（二）下列函数中（15小题)，哪些是单射函数,满射函数,双射函数。其中n是自然数集合,i是整数集合，r是实数集合。已知集合a , b, c，集合b=, 2， ， 下列的二元关系中，r1r哪些可以构成函数。1.：nn, f(n）= 2n 【单射 】2f：ab,a=0，1,b0,1,3，4,f（a)=2 【单射 】3.f:ii, () i + 10 【双射 】 4: ii, f()i| 【 既不是单射，也不是满射】 5f: i，1,当i为偶数时，f(i)=0；当i为奇数时，f()1。 【满射 】

10、 r1 = （，1)，(b, ）,(，3） 【 】 7.r2 = (, 3）,（c， 2）,(c, 1） 【 】 8r3 = (a, 2),(b， 1),（b, 2）,(c, 3） 【 】 .r = (b， ),（c，） 【 】 10.r5 = （, 1）,（, 1），(c, ) 【 】 四、表述题:将下列命题符号化（一） 命题逻辑符号化1.我美丽而又快乐。2.如果老张和老李都不去，他就去。.电灯不亮，当且仅当灯泡或开关发生故障。 4.王强工作努力且身体好。 5.我是本次校运动会的跳远或米短跑的冠军。 6.只要有学习机会,我一定用功读书。 7.两个三角形全等，当且仅当它们的三个对应边相等。 .

11、如果不下雨，我不乘公交车上班。（二） 谓词逻辑符号化(论域为全部个体域) 小张不是学生。 2.所有的有理数都是实数。 3.小张大于岁，身体健康，无色盲,大学毕业,则他可参加飞行员考试。 .小王不是研究生。37.他是跳高或篮球运动员38.晓莉非常聪明和能干39若m是奇数，则m是偶数。四、参考答案:(一)1设p表示命题“我美丽”，q表示命题“我快乐”。则用符号表示命题为：pq2.p表示“老张去”;q表示“老李去”；r表示“他去”。则（q）r。3.设p表示“电灯不亮”,表示“灯泡发生故障”;表示“开关发生故障”。则p（r)。 .设p表示命题王强工作努力，q表示命题王强身体好。则用联结词表示复合命题为

12、：p 5.设p:我是本次校运动会的跳远冠军q:我是本次校运动会的100米短跑的冠军，则pq。 6.设p：有学习机会，q:我一定用功读书，则pq。 7.设：两个三角形全等,q:三个对应边相等,则q p:下雨，q:我不乘公交车上班。则pq。 （二） 1.令s(x）：x是学生；：小张;则s（a) 设q（)：x是有理数;r():x是实数,则符号化为：(q(x) （)） 3设a(x)：x超过18岁;b(）：身体健康；c(x): 色盲；（x):x大学毕业 e():x参加飞行员考试；a：小张；则a(a)b（a)c()d(a)e(a)。 4.设a():x是研究生;a:小王，则a(a)。 5.设(x):x是跳高

13、运动员；b(x):是篮球运动员;a：他;则a(a）(a) 6设a（x):非常聪明;b():x能干;a: 晓莉；则()b(a） .a(x):x是奇数；b(x): x 是偶数；m:某整数;则a（m) b(2m)。五、计算题1.构造 公式:p 的真值表已知集合a =1, 2, 求集合a的幂集(a)。3. 已知集合a =a, b, 求集合 上的笛卡尔积aa.4.知集合a =a， b,c， d,r=（, a）,（a,c)，（，d），（b,a）,（,b),(b，d)，（c,a)，（,b)，（，c) 是a上的关系，试用矩阵表示法表示。5. 试画出树叶权为1，2,，5，7，2的最优二元树,并求出该树的权。 .

14、求公式( p q ) （ pq )的真值表。 7.已知集合a=1,2， 求集合a的幂集p（a）。已知集合 =a, b, c, 求集合a 上的笛卡尔积aa.9画出一个3阶有向完全图10.（a，r)是偏序集，a2,3,4,，6,，12，6,24，r是上的整除关系。试写出a中的所有极大元和极小元,它有没有最大元和最小元? 五、参考答案: 1.qpqftfttfft.因为a|,所以a的幂集|(a）|224。p（）,1,2,2.aaa,ba,b=(a,a）,(a,b)，(b,a),(b,）， 4a =a, b, c， d, r=(a， a),(a, c),（,d）,（b，）,(b,b）,（b,)，(,a

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