北京交通大学离散数学期末考试题-06-07-1-A-试卷-公选

北京交通大学2006-2007学年第一学期《离散数学》期末考试试卷（A）学院_____________专业___________________班级____________学号_______________姓名_____________题号一二三四五总分得分阅卷人一、填空题（共10分，每空1分）1.命题公式G=（PQ）R，则G共有个不同的解释；2.在命运题逻辑中，任何命题公式的主析取范式都存在并且。3.设R是集合A上的二元关系，如果关系R同时具有性、对称性和传递性，则称R是等价关系。4.设R是集合A上的二元关系，如果R是反自反的，则它的关系矩阵的主对角线元素。5.设G=(n，m)是树，则其顶点个数与边数之间的关系是。6.设G=K5是由5个顶点构成的完全图，则G的边数为。7.如果简单无向图的每个结点与其余的结点邻接，则称该图为。8.k-正则图是指的图。9.Hamilton图是指的图。10.Euler通路是指的通路。二、确定下列各命题（或公式）的真值（填F或T)（共10分，每小题2分）1.设G是图，如果P(G)1，则G是连通图。()2.偏序的逆不是偏序。()3.集合A上的传递闭包ρ+是可传递的。()4.(（P→Q）∧（Q→R）)→（P→R）。()5.设集合A={1,2,3,4}.A上二元关系R,R={(1,1)(1,4)(2,2)(2,3)(3,2)(3,3)(4,1)(4,4)}是等价关系。()三、选择一个正确答案的代号，填入括号中（共20分，每小题2分）1.由集合运算定义，下列各式正确的有（）。(A)XXY(B)XXY(C)XXY(D)XXY2.下列命题中正确的是（）。(A)a{{a}}；(B){a}{{a}}；(C){a}{{a}}；(D){{a}}。3.设G是由5个顶点组成的完全图，则从G中删去（）条边可以得到树。(A)4(B)5(C)6(D)104.下列命题公式不是重言式的是（）。(A)Q→(P∨Q)；(B)(P∧Q)→P；(C)（P∧Q）；(D)（P∧0）。5.在有n个结点的连通图G中，其边数（）。(A)最多有n-1条;(B)至少有n-1条;(C)最多有n条;(D)至少有n条.6.给定下列序列,可构成简单无向图的度数序列的是（）。(A)(1,1,2,2,3);(B)(1,1,2,2,2);(C)(0,2,3,3,3);D(1,3,4,4,5).7.设A={a，b，c}，B={1，2}，作函数f:A→B，则不同函数的个数为（）。(A)2×3;(B)22；(C)23；(D)32。（9-10题的条件：3,23,)(,:2xxxxfRRf设,则,2)(,:xxgRRg）8.))((xgf（）。（A）121)2(2xxx;（B）323)2(xxx;（C）121)2(2xxx;（D）303)2(2xxx.9.是RRxgf:))((（）。（A）单射非满射;（B）满射非单射;（C）不是单射也非满射;（D）双射.四、计算题（共30分，每小题6分）1.构造命题公式(P→Q)→(PQ)的真值表，并求其主析取范式。2.用等价变换将公式P((PQ)(QP))化为主析取范式和主合取范式：3.化简（ABC）（（AB）C）（ABC）（ABC）4.写出下面有向图（关系图）所表示的关系R的关系矩阵，并求出R的自反闭包和对称闭包。5.设图G中各点的度都是3，且点数n与边数m满足2n-3=m。问：G中点数n和边数m各为多少？五、证明题（共30分，每小题10分）1.用逻辑推理方法证明：{PQ，RS，PR}蕴涵QS。2.将集合M中元素映射到自身的变换成为同一变换，记为I。设，是集合M上的两个变换。证明，如果•=•=I，则，是1–1变换，并且=-1。3.设R是一个关系，用R-1表示R的逆关系，s(R)表示S的对称闭包，证明s(R)=R∪R-1。abc