本科1009离散数学

本科：1009离散数学第1页共12页一、单项选择题1．设P：a是偶数，Q：b是偶数。R：a+b是偶数，则命题“若a是偶数，b是偶数，则a+b也是偶数”符号化为（D．PQ→R）。2．表达式x（P（x，y）Q（z））y（Q（x，y）→zQ（z））中x的辖域是（P（x，y）Q（z））。3．设)(}),({},{,4321PSPSSS则命题为假的是（42SS）。4．设G是有n个结点的无向完全图，则G的边数（1/2n（n-1））。5．设G是连通平面图，有v个结点，e条边，r个面，则r=（e-v+2）。6．若集合A={1，{2}，{1，2}}，则下列表述正确的是({1}A)．7．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为(5)．8．设无向图G的邻接矩阵为0101110011000011100111110则G的边数为(7)．9．设集合A={a}，则A的幂集为({，{a}})．10．下列公式中(AB(AB))为永真式．11．若G是一个汉密尔顿图，则G一定是(连通图)．12．集合A={1,2,3,4}上的关系R={x，y|x=y且x,yA}，则R的性质为（传递的）．13．设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集A，上的元素5是集合A的（极大元）．14．图G如图一所示，以下说法正确的是({(a,d),(b,d)}是边割集)．图一15．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（(x)(A(x)∧B(x))）．16．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是(AB，且AB)．17．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是(（d）是强连通的)．18．设图G的邻接矩阵为0101010010000011100100110则G的边数为(5)．19．无向简单图G是棵树，当且仅当(G连通且边数比结点数少1)．20．下列公式((P(QP))(P(PQ)))为重言式．21．若集合A＝{a，{a}，{1，2}}，则下列表述正确的是({a}A)．22．设图G＝V,E，vV，则下列结论成立的是(EvVv2)deg()．本科：1009离散数学第2页共12页23．命题公式（P∨Q）→R的析取范式是(（P∧Q）∨R)24．下列等价公式成立的为(P(QP)P(PQ))．25．设A={a,b}，B={1,2}，R1，R2，R3是A到B的二元关系，且R1={a，2,b，2}，R2={a，1,a，2,b，1}，R3={a，1,b，2}，则（R2）不是从A到B的函数．26．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为(无、2、无、2)．27．若集合A的元素个数为10，则其幂集的元素个数为（1024）．28．如图一所示，以下说法正确的是(e是割点)．图一29．设完全图Kn有n个结点(n≥2)，m条边，当（n为奇数）时，Kn中存在欧拉回路．30．已知图G的邻接矩阵为，则G有（5点，7边）．二、填空题（每小题3分，共15分）1．设A，B为任意命题公式，C为重言式，若ACBC，那么AB是重言式（重言式、矛盾式或可满足式）。2．命题公式（P→Q）P的主合取范式为)()(QPQP。3．设集合A={，{a}}，则P（A）=}}}{,{}},{{},{,{aa。4．设图G=〈V，E〉，G′=〈V′，E′〉，若V′=V,E′E,则G′是G的生成子图。5．在平面G=〈V，E〉中，则riir1)deg(=2|E|，其中ir（i=1，2，…，r）是G的面。6．命题公式PP的真值是假（或F，或0）．7．若无向树T有5个结点，则T的边数为4．8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i=t-1．9．设集合A={1，2}上的关系R＝{1,1,1,2}，则在R中仅需加一个元素2,1，就可使新得到的关系为对称的．10．(x)(A(x)→B(x，z)∨C(y))中的自由变元有z，y．11．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B=空集（或）．12．设集合A={1，2，3}上的函数分别为：f={1,2,2,1,3,3,}，g={1,3,2,2,3,2,}，则复合函数gf={1,2,2,3,3,2,}．13．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”）．14．无向连通图G的结点数为v，边数为e，则G当v与e满足e=v-1关系时是树．15．设个体域D＝{1,2,3}，P(x)为“x小于2”，则谓词公式(x)P(x)的真值为假（或F，或0）．16．命题公式)(PQP的真值是T（或1）．17．若图G=V,E中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|．本科：1009离散数学第3页共12页18．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素0，则该序列集合构成前缀码．19．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为5．20．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y)中的y．21．设集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元关系，},,{BAyxByAxyxR且且则R的有序对集合为{2,2，2,3，3,2}，3,3．22．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2．23．设G＝V,E是有6个结点，8条边的连通图，则从G中删去3条边，可以确定图G的一棵生成树．24．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数．25．设个体域D＝{1,2}，则谓词公式)(xxA消去量词后的等值式为A(1)A(2)．26．设集合A＝{a，b}，那么集合A的幂集是{,{a,b},{a},{b}}．27．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有2个．28．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．29．设连通平面图G的结点数为5，边数为6，则面数为3．30．设个体域D＝{a,b}，则谓词公式(x)A(x)∧（x）B（x）消去量词后的等值式为(A(a)∧A(b))∧(B（a）∨B（b）)．31.设集合A={0，1，2}，B={l，2，3，剖，R是A到B的二元关系，R={x,y|x∈A且y∈B且x，y∈A∩B}则R的有序对集合为___{1,1,1,2,2,1,2,2}___32.设G是连通平面图，v，e，r分别表示G的结点数，边数和面数，则v，e和r满足的关系式__v-e+r=2_____33.G=V,E是有20个结点，25条边的连通图,则从G中删去__6__条边，可以确定图G的一棵生成树.34.无向图G存在欧拉回路，当且仅当G所有结点的度数全为偶数且_连通____35.设个体域D={1,2}，则谓词公式xA(x)消去量词后的等值式为__A(1)∧A(2)___三、化简解答题11．设集合A={1，2，3，4}，A上的二元关系R，R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，3〉，〈3，2〉，〈3，3〉，〈4，1〉，〈4，4〉}，说明R是A上的等价关系。解从R的表达式知，,),(,RxxAx即R具有自反性；三、逻辑公式翻译1．将语句“今天上课．”翻译成命题公式．设P：今天上课，则命题公式为：P．2．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．设P：他去操场锻炼，Q：他有时间，则命题公式为：PQ．3．将语句“他是学生．”翻译成命题公式．设P：他是学生，则命题公式为：P．4．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．设P：明天下雨，Q：我们就去郊游，则命题公式为：PQ．5．将语句“他不去学校．”翻译成命题公式．设P：他去学校，P．6．将语句“他去旅游，仅当他有时间．”翻译成命题公式．设P：他去旅游，Q：他有时间，PQ．7．将语句“所有的人都学习努力．”翻译成命题公式．设P(x)：x是人，Q(x)：x学习努力，（x）(P(x)Q(x))．8．将语句“如果你去了，那么他就不去．”翻译成命题公式．设P：你去，Q：他去，PQ．9．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．本科：1009离散数学第4页共12页设P：小王去旅游，Q：小李去旅游，PQ．10．将语句“所有人都去工作．”翻译成谓词公式．设P(x)：x是人，Q(x)：x去工作，(x)(P(x)Q(x))．11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．设P：所有人今天都去参加活动，Q：明天的会议取消，PQ．12．将语句“今天没有人来．”翻译成命题公式．设P：今天有人来，P．13．将语句“有人去上课．”翻译成谓词公式．设P(x)：x是人，Q(x)：x去上课，(x)(P(x)Q(x))．11.将语句如果小李学习努力，那么他就会取得好成绩.翻译成命题公式.设P：小李学习努力，Q:小李会取得好成绩，P→Q12.将语句小张学习努力,小王取得好成绩.翻译成命题公式.设P：小张学习努力，Q:小王取得好成绩，P∧Q四、判断说明题1．设集合A={1，2}，B={3，4}，从A到B的关系为f={1,3}，则f是A到B的函数．错误．因为A中元素2没有B中元素与之对应，故f不是A到B的函数．2．设G是一个有4个结点10条边的连通图，则G为平面图．错误．不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”3．设N、R分别为自然数集与实数集，f：N→R，f(x)=x+6，则f是单射．正确．设x1，x2为自然数且x1x2，则有f(x1)=x1+6x2+6=f(x2)，故f为单射．4．下面的推理是否正确，试予以说明．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．错误．（2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．5．如图二所示的图G存在一条欧拉回路．图二错误．因为图G为中包含度数为奇数的结点．6．设G是一个有6个结点14条边的连通图，则G为平面图．错误．不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”7．如果R1和R2是A上的自反关系，则R1∪R2是自反的．正确．R1和R2是自反的，xA，x,xR1，x,xR2，则x,xR1R2，所以R1∪R2是自反的．8．如图二所示的图G存在一条欧拉回路．v1v2v3v5v4dbacefghn图二本科：1009离散数学第5页共12页正确．因为图G为连通的，且其中每个顶点的度数为偶数．9．┐P∧（P→┐Q）∨P为永真式．正确．┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，如果P的值为真，则┐P∧（P→┐Q）∨P为真，如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，也即┐P∧（P→┐Q）∨P为真，所以┐P∧（P→┐Q）∨P是永真式．另种说明：┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，只要其中一项为真，则整个公式为真．可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真，所以┐P∧（P→┐Q）∨P是永真式．或用等价演算┐P∧（P→┐Q）∨PT10．若偏序集A，R的哈斯图如图一所示，