离散数学试卷A-(2008)

《离散数学》试卷A第1页共6页诚信应考,考试作弊将带来严重后果！华南理工大学期末考试《离散数学》试卷A注意事项：1.考前请将密封线内填写清楚；2.所有答案请直接答在试卷上；3．考试形式：闭卷；4.本试卷共五大题，满分100分，考试时间120分钟。题号一二三四五总分得分评卷人一、填空题(本大题共12小题，每小题2分，共24分)1．求合式公式xP(x)→xQ(x,y)的前束范式________________。2．设集合A={a,b,{a,b},},B={{a,b},}，求B-A=_____________．3．设p与q的真值为0,,rs的真值为1则命题((()))()sqrprp的真值是__________.4．设R是在正整数集合Z上如下定义的二元关系,(,)(10)RxyxyZxy，则它一共有个有序对，且有自反性、对称性、传递性、反自反性和反对称性各性质中的性质。5．公式x(P(x)→Q(x,y))→S(x)中的自由变元为________________，约束变元为________________。6．设有命题T(x):x是火车，C(x):x是汽车，Q(x,y):x跑得比y快，那么命题“有的汽车比一些火车跑得快”的逻辑表达式是______________________.7．设G是n阶m条边的无向图，若G连通且m=__________则G是无向树.8．设X={1，2，3}，f：X→X，g：X→X，f={1,2,2,3,3,1},g={1,2,2,3,3,3}，则f-1g=________________，gf=________________。9.不能再分解的命题称为________________，至少包含一个联结词的命题称为_____________________…姓名学号学院专业座位号(密封线内不答题)……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………《离散数学》试卷A第2页共6页________________．10.连通无向图G含有欧拉回路的充分必要条件是.11．设集合A={,{a}}，则A的幂集P(A)=，|P(A)|=_____________________________。12.设G=V,E,G’=V’,E’为两个图(同为无向图或有向图),若E’E且_______________,则称G’是G的子图,若E’E且_______________,则称G’是G的生成子图。二、单选题(本大题共12小题，每小题2分，共26分)1．下列命题公式为重言式的是（）A.(p∨┐p)→q．B．p→(p∨q)C．q∧┐qD．(p→p)→q2．下列语句中为命题的是()A．你好吗？B．人有6指.C．我所说的是假的.D．明天是晴天.3.设D=V,E为有向图，V={a,b,c,d,e,f},E={a,b,b,c,a,d,d,e,f,e}是（）A．强连通图B．单向连通图C．弱连通图D．不连通图4．集合A＝{a，b，c}上的下列关系矩阵中符合偏序关系条件的是()A．1010011000111101B．101010101C．101110001D．1110100115．设A={1，2，3}，A上二元关系S={1，1，1，2，3，2，3，3}，则S是（）A．自反关系B．传递关系C．对称关系D．反自反关系6.设A={a,b,c,d}，A上的等价关系R={a,b,b,a,c,d,d,c}∪IA，则对应于R的A的划分是（）A．{{a},{b,c},{d}}B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}}D．{{a,b},{c,d}}《离散数学》试卷A第3页共6页7.以下非负整数列可简单图化为一个欧拉图的是()A.{2,2,2,2,0}B.{4,2,6,2,2}C.{2,2,3,4,1}D.{4,2,2,4,2}8.设论域D＝{a，b}，与公式xA(x)等价的命题公式是()A．A(a)∧A(b)B．A(a)→A(b)C．A(a)∨A(b)D．A(b)→A(a)9.一棵树有3个4度顶点，4个2度顶点其余都是树叶，求这棵树有多少个树叶顶点()A.12B.8C.10D.1310.有ABC三个人猜测甲乙丙三个球队中的冠军.各人的猜测如下:A:冠军不是甲,也不是乙.B:冠军不是甲,而是丙.C:冠军不是丙,而是甲.已知其中有一个人说的完全正确.一个人说的都不对,而另外一人恰有一半说对了.据此推算,冠军应该是()A．甲B.乙C.丙D.不确定11．如第11题图所示各图，其中存在哈密顿回路的图是()12．设C(x):x是国家级运动员，G(x):x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为()))()(()A(xGxCx))()(()B(xGxCx))()(()C(xGxCx))()(()D(xGxCx三．计算题(30分)1．用等值演算法求取求下列公式：(PQ)(P∨Q)的合取范式（5分）(A)(B)(C)(D)第11题图《离散数学》试卷A第4页共6页2．图G如下图所示，求图G的最小生成树.（5分）3．有向图D如图所示，求D的关联矩阵M(D)（5分）4.化简表达式)()))(()))((((ACABBACBA（7分）5．设R={2，1，2，5，2，4，3，4，4，4，5，2}，求r(R)和s(R)，并作出它们及R的关系图(8分)3410799712685《离散数学》试卷A第5页共6页五．证明题(22分)1．构造下面推理的证明(5分)前提：pq，pr，st，sr，t结论：q2．设A={1,2,3,4},在AA定义的二元关系R，,,,AA,,R,+=+uvxyuvxyuyxv证明R是AA上的等价关系。(5分)3．已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C)（6分）《离散数学》试卷A第6页共6页4．无向图G=V,E，且|V|=n,|E|=m,试证明以下两个命题是等价命题1）G中每对顶点间具有唯一的通路，2）G连通且n=m+1。（6分）