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

北 京 交 通 大 学 2006-2007学年第一学期《离散数学》期末考试试卷（A） 学院_ ____________ 专业___________________ 班级_____ _______ 学号_______________ 姓名___________ __ 题号 一 二 三 四 五 总分 得分 阅卷人 填空题（共10分，每空1分） 命题公式G=（PùQ）?R，则G共有 个不同的解释； 在命运题逻辑中，任何命题公式的主析取范式都存在并且 。 设R 是集合A上的二元关系，如果关系R同时具有 性、对称性和传递性，则称R是等价关系。 设R 是集合A上的二元关系，如果R是反自反的，则它的关系矩阵的主对角线元素 。 设G=(n，m)是树，则其顶点个数与边数之间的关系是 。 设G=K5是由5个顶点构成的完全图，则G的边数为 。 如果简单无向图的每个结点与其余的结点邻接，则称该图为 。 k-正则图是指 的图。 Hamilton图是指 的图。 Euler通路是指 的通路。 确定下列各命题（或公式）的真值（填F或T)（共10分，每小题2分） 设G是图，如果P(G)1，则G是连通图。 ( ) 偏序的逆不是偏序。 ( ) 集合A上的传递闭包ρ+是可传递的。 ( ) (（P→Q）∧（Q→R）)→（P→R）。 ( ) 设集合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分） 由集合运算定义，下列各式正确的有（ ）。 XíXèY (B) XêXèY (C) XíX?Y (D) X?XèY 下列命题中正确的是（ ）。 (A) a?{{a}}； (B) {a}?{{a}}； (C) {a}?{{a}}； (D) ??{{a}}。 设G是由5个顶点组成的完全图，则从G中删去（ ）条边可以得到树。 (A) 4 (B) 5 (C) 6 (D) 10 下列命题公式不是重言式的是（ ）。 (A) Q→(P∨Q)； (B) (P∧Q)→P；(C) （P∧Q）；(D) （P∧0）。 在有n个结点的连通图G中，其边数（ ）。 (A) 最多有n-1条; (B) 至少有n-1条; (C) 最多有n条; (D) 至少有n条. 给定下列序列,可构成简单无向图的度数序列的是（ ）。 (A) (1,1,2,2,3); (B) (1,1,2,2,2); (C) (0,2,3,3,3); D(1,3,4,4,5). 设A={a，b，c}，B={1，2}，作函数f : A→B，则不同函数的个数为（ ）。 (A) 2×3 ; (B) 22； (C) 23 ；(D) 32。 （9-10题的条件：,） （ ）。 （A）; （B）; （C）; （D）. （ ）。 （A）单射非满射; （B）满射非单射; （C）不是单射也非满射; （D）双射. 计算题（共30分，每小题6分） 构造命题公式 (P→Q)→(PQ)的真值表，并求其主析取范式。 用等价变换将公式P?((P?Q)??(?Q??P))化为主析取范式和主合取范式： 化简（A?B?C）?（（A?B）?C）?（A?B?C）?（A?B?C） 写出下面有向图（关系图）所表示的关系R的关系矩阵，并求出R的自反闭包和对称闭包。 设图G中各点的度都是3，且点数n与边数m满足2n-3=m。问：G中点数n和边数m各为多少？ 证明题（共30分，每小题10分） 用逻辑推理方法证明：{P?Q， R?S，PúR }蕴涵QúS。 将