离散数学试卷B.docVIP

计算机应用专业 《离散数学》试题B 2005年3月 一、填空题 (每小题3分，本题共15分) 1 设R是集合A上的等价关系，则R所具有的关系的三个特性是_______________________________________________________. 2. 设命题公式，则公式G的合取范式是_____________________。 3. 设A是集合，且A = {1, 2}，则A上的全关系A2 = _____________________________________________________. 4. 有限图G是树的一个等价定义是：______________________________________ . 5. 设K5 是有5个点的完全图，则K5有____________条边。 二、选择题 (每小题3分，本题共15分) 1 在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 (A)3 (B)8 (C) 9 (D) 512 2 设R为实数集合，映射则? 是( ). (A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 3 设命题公式，，则G与H的关系是( )。 (A) (B) (C) (D)以上都不是. 4 已知命题，则所有使G取真值为1的解释是 ( )。 (A)(0, 0, 0), (0, 0, 1), (1, 0, 0); (B) (0, 1, 0), (1, 0, 1), (1, 1, 0); (C) (1, 0, 0), (1, 0, 1), (1, 1, 0); (D) (1, 1, 0), (1, 0, 1), (1, 1, 1). 5 设I是如下一个解释：D = {a, b}，，则在解释I下取真值的公式是 ( ). . (B) . (C) . (D) . 三、计算题 (本题共60分) (本题12分)设集合A＝{1, 2, 3}，A上的关系R＝{(1, 1),(1, 2),(2, 2),(3, 2),(3, 3)}, 画出R的关系图； 写出R的关系矩阵. 问R具有关系的哪几种性质(自反、对称、传递、反对称). (本题12分) 设集合A＝{1, 2, 3, 4, 6, 8, 12}，R是A上的整除关系， 画出半序集(A, R)的哈斯图； 写出A的子集{2, 4, 6, 8}的上界，下界，最小上界，最大下界； (3) 写出集合A的最大元，最小元，极大元，极小元。 (本题12分)用迪克斯特拉算法求下面有限权图中从A到B的最短路，要求用图示给出求解过程，并计算它们的权值。 4. (本题12分)试判断命题公式的公式类型。 5. (本题12分)设一阶逻辑公式 试将G化成与其等价的前束范式。 四 证明题(本题10分) 设R和S是二元关系，证明：. １ A B 1 4 2 2 4 1 6 3 1 8 9 2