离散复习总结1

一、选择题（10题，共20分）（1）判断哪个是命题：3.下列语句中，(D)是命题(A)请不要随地丢垃圾！(B)离散数学难学吗？(C)y+24(D)2020年的春节会下雪。3.下列语句中，(C)是命题(A)开车请不要超速(B)你明天去游泳吗(C)2020年春节是星期五(D)x+50（2）命题符号化：1.设P：天下雨，Q：我有时间，R：我将进城里．命题“如果天不下雨而我又有时间的话，我就进城”符号化为(C)RQPRQPRQPRQP)()D()C()B()A(2.设P：我有时间，Q：我去打球．则命题“除非我没有时间，否则我将去打球”符号化为（B）(A)Q→P(B)P→Qaa(C)P→Q(D)Q→P1.设P：2能整除4；Q：2能整除7．则命题“虽然2能整除4，但2不能整除7符号化为：（B）(A)P→Q(B)P∧Q(C)P∨Q(D)Q→P1．设P：我a将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符号化为(B)．A．PQB．QPC．QPD．QP扩展：P26习题2连接词先转换为确定性的描述，如上文“除非我没有时间”相当于“只要我有时间”。十分确定的表述，比如仅当、只有等语句部分的条件为必要条件。（3）求命题成假赋值求p→（q^r)的成假赋值。A：000001010B：100C：101D：100101110答案：D扩展：P27习题6（4）判断哪个为真命题2.前提条件QQP,的有效结论是(B)(A)P(B)P(C)Q(D)Q5.下列式子错误的是(C)(A){a}{{a}}(B){a}{{a}，a}(C){a}{{a}}(D){a}{{a}，a}7.如果A∩B=A∩C，则下述结论成立的是(D)A.B=CB.BA且CAC.B∪A=C∪AD.以上结论都不对9.判断下列给定的集合和运算能构成群的是(C)(A)S={n2︱n∈Z}，S上的普通乘法，其中Z为整数(B)整数集Z上的运算，)(2,,babaZbao(C)整数集Z上的运算*，2,,babaZba(D)集合S={1,3,5,7,…}上的普通加法运算8.设A={a,b,c,d}，B={x,y}，f={a,x,b,x,c,y}，则下面命题正确的是(D)(A)f是从A到B的函数，但不是满射，也不是单射(B)f是从A到B的函数，是满射，不是单射(C)f是从A到B的函数，不是满射，是单射(D)f不是从A到B的函数9.判断下列给定的集合和运算能构成群的是(C)(A)S={n5︱n∈Z}，S上的普通乘法，其中Z为整数(B)S={m+n5︱m,n∈Z}，S上的普通乘法，其中Z为整数(C)a是正实数，S={an︱n∈Z}，运算是S上的普通乘法，其中Z为整数(D)整数集Z上的运算*，babaZba2*,,10.以下说法错误的是(B)(A)公式(p∨q)∧(p∨q)的成真赋值是：00、11(B)一个关系如果不是自反的就一定是反自反的(C)存在函数即不是单射的也不是满射的(D)当n等于奇数时，完全图Kn既是欧拉图又是哈密顿图扩展：P26习题1P66习题3(5)求三个集合间的并和对称差运算结果6.设A={1，2，3}，B={2，3，4，5}，C={2，3}，则（A∩B）（A∪C）等于（C）(A){1，3，4}(B){2，3}(C){1}(D){1，2，3}扩展：P67习题9(6)判断关系的性质（自反、对称、传递等）扩展：P73例4.9自反：包含所有恒等关系反自反：不包含任何恒等关系对称：对于所有x,y，存在y,x反对称：对于所有x,y，不存在y,x，除非x=y传递：如果存在x,y，y,z，那么存在x,z(7)集合A-B的二元关系有多少个？7.设集合A=n，则A上的关系有（C）种A．2nB．n2C．22nD．2nA上的关系即为A到A的关系，对应AxA的子集。扩展：P93习题7对比：集合A-B的函数，A为m个元素，B为n个元素，函数有nm个。设A={a,b,c},B={0,1}.从A到B的函数有以下8个。即23=8.F1={a,0,b,0,c,0}F2={a,0,b,0,c,1}F3={a,0,b,1,c,0}F4={a,1,b,1,c,1}F5={a,0,b,0,c,0}F6={a,1,b,0,c,1}F7={a,1,b,1,c,0}F8={a,1,b,1,c,1}（8）函数性质：8.若f是A到B的满射非单射函数，其中A=m，B=n，则下列选项正确的是(B)(A)mn(B)mn(C)m=n(D)m与n的大小关系不确定扩展：P95习题42（9）代数系统的子代数（注意封闭性）扩展：P106习题14、15（10）知图顶点、度数，如何变成树。10.设图G是n阶连通图，总度数为d，则从G中删去)1n(2d条边后可以使之成为树。二、填空（10题，共20分）（1）求命题公式成假赋值1.设命题公式G=（P→（Q∧R）），则G的成假赋值有000、001、010、011、111。（2）集合幂集集合A={,{}}，则P(A)={,{},{{}},{,{}}}。3.设集合A={1,4}，B={2,4,5}则P(A)-P(B)={{1},{1,4}}。扩展：P67习题5（3）判断命题公式类型(永真式、永假式、可满足式)1.设命题公式A=（P→Q）∧Q，则A的公式类型是永假式。5.设命题公式A=（P→Q）∨Q则A是(A)(A)重言式（永真式）(B)矛盾式（永假式）(C)可满足式(D)以上都不对扩展：P27习题4（4）根据主合取范式求主析取范式4.公式A含有3个命题变项，若A的主合取范式为M1∧M3∧M4∧M6，则A的主析取范式为(B)(A)m1∨m3∨m4∨m6(B)m0∨m2∨m5∨m7(C)m1∧m3∧m4∧m6(D)m0∧m2∧m5∧m7扩展：P18例1.25、例1.26（5）关系的复合运算5.R1,R2为二元关系，其中R1={1,1,2,1,3,2,4,2},R2={1,2,2,3,2,2,3,1,3,2}，则R1-1oR2={1,2,1,3,2,1}。注：R-1={x,y|y,xR}扩展：P74例4.13、P94习题23（6）二元运算，求单位元（幺元）7.设Z为整数集，对于a,b∈Z，a*b=a+b-2，a∈Z，a的逆元1a=4-b。6、设代数系统A，*，其中A={a，b，c},则幺元是a；是否有幂等性有；是否有对称性有。（7）知图的边数，几度顶点多少个，。。。，求顶点数8．设无向图G中的顶点数与边数相等，其中2度和3度顶点各a个，其余顶点均为悬挂顶点，则G中的边数是3a。（8）知道图的顶点数、边数，求非同构情况（9）n阶k正则图，求边、顶点数关系。9.n阶k-正则图G的边数是nk。*abcabcabcbbcccb（10）求树叶数（边数为顶点数减一）扩展：P154习题2、3三、判断题（10题，共10分）（1）判断联结词全功能集┐,^,V、┐,V、┐,^、┐,-是全功能集。见P12~13（2）判断集合间运算，充分必要条件3.X∪Y=Y的充分必要条件是X=。（F）（3）命题公式、主析取范式。。。概念6.某公式，用不同方法有可能求出不同的主合取范式。（F）1.在求某一个命题公式的主析取范式时，不同方法有可能求出不同的主析取范式。（F）（4）集合运算1.若A∩B=A∩C，则B=C不一定。（F）（5）反函数存在条件7.某些函数可能不存在逆。（T）（只有双射函数才有反函数）（6）图同构概念见P125（7）点连通度、边连通度、最小度数10.任何无向图的点连通度都小于边连通度。（T）注：无向图的点连通度边连通度最小度数（8）（9）（10）欧拉图和哈密顿图关系10.当n等于奇数时，完全图kn既是欧拉图又是哈密顿图。（T）见P156、P158四、计算与证明（5道题，共50分）