311019040离散数学_A闭_2010-2011-2

《311019040离散数学_A闭_2010-2011-2》由会员分享，可在线阅读，更多相关《311019040离散数学_A闭_2010-2011-2（5页珍藏版）》请在金锄头文库上搜索。

1、 311019040 离散数学离散数学（A 闭闭） 2010-2011-2 一、单项选择题（本大题共一、单项选择题（本大题共 1515 小题，每小题小题，每小题1 1 分，共分，共1515 分）分）提示：在每小题列出的四个备选项 中只有一个是符合题目要求的，请将其代码填写在下表中。错选、多选或未选均无分。 1.下列式子不是不是 谓词合式公式的是( ) A.(x)(P(x,y)Q(x,z)(z)R(x,z) B.( x)( y)P(x,y) Q(x,z) ( x)P(x,y) C. (x)(P(x)Q(x) (x)( P(x) Q(x) D. (x)P(x)Q(y,z) 2.下列关系矩阵所对应的

2、关系具有反自反性的是( ) A. 001 110 101 B. 101 110 001 C. 001 010 101 D. 001 100 100 3. 某市举行中学数学、物理、化学三科竞赛，结果是数学和物理均优者11人，物理和化学均 优者10人， 数学和化学均优者9人， 至少有两科优秀者共22人， 则三科均优者有( ) A.6人 B.3人 C.4人 D.8人 4.设R是实数集合， 在上定义二元运算*： a， bR， a*b=a+b-ab， 则下面的论断中正确的是 （） 。 A、0是*的零元 B、1是*的幺元 C、0是*的幺元 D、*没有等幂元 5.G是一棵根树，则（ ） 。 A、G一定是连通

3、的 B、G一定是强连通的 C、G只有一个顶点的出度为0 D、G只有一个顶点的入度为1 6. 下列各组数中，哪个可以构成无向图的度数列（ ） 。 A.1，1，1，2，2 B.2，2，2，2，3 C.1，2，2，4，6 D.2，3，3，3 7下列命题公式中是永假式的有（ ） 。 A.ppp)( B.ppq)( C.)()(pqqp D.rqp )( 311019040 离散数学离散数学（A 闭闭） 2010-2011-2 8.设图G的相邻矩阵为 01101 10101 11011 00101 11110 ，则G的顶点数与边数分别为( ). (A)4, 5 (B)5, 6 (C)4, 10 (D)5

4、, 8. 9.连通图G是一棵树当且仅当G中（ ） 。 (A) 有些边是割边 (B) 每条边都是割边 (C) 所有边都不是割边 (D) 图中存在一条欧拉路径 10.设G是连通平面图，有5个顶点，6个面，则G的边数是( ). (A) 9条 (B) 5条 (C) 6条 (D) 11条. 11.设 I 是如下一个解释：Da,b, 0 1 0 1 b) P(b,a) P(b,b) P(a,),(aaP 则在解释 I 下取真值为 1 的公式是( ). (A)xyP(x,y) (B)xyP(x,y) (C)xP(x,x) (D)xyP(x,y). 12. 一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，

5、则其1度顶点为（ ） 。 (A) 5 (B) 7 (C) 8 (D) 9 13.在0（ ）之间写上正确的符号 ( ) 。 (A) = (B) (C) (D) 14.设A=1，2，3，4，下列关系中( )为等价关系。 （A）R1=，; （B）R2=，; （C）R3=，; （D）R4=，. 15、设集合A=1,2,3,10，下面定义的哪种运算关于集合A是不封闭的？（ ） A、 x*y=maxx,y B、 x*y=GCD(x,y)，即x,y的最大公约数 C、 x*y=minx,y D、 x*y=LCM(x,y)，即x,y的最小公倍数 311019040 离散数学离散数学（A 闭闭） 2010-201

6、1-2 二、多二、多项选择题项选择题（本大（本大题题共共5 5小小题题，每小，每小题题3 3分，共分，共1 15 5分）分）提示：在每小题列出的五个备选项中 有二个至五个是符合题目要求的，请将其代码填写在下表中。错选、多选、少选或未选均无分。 1设R和S是集合A上的任意关系，下列命题不 成立（ ） 。 A.若R和S是自反的，则RS也是自反的。 B.若R和S是反自反的，则RS也是反自反的。 C.若R和S是对称的，则RS也是对称的。 D. 若R和S是反对称的，则RS也是反对称的。 E.若R和S是传递的，则RS也是传递的。 2.设A1,2,3，则右图所示A上的关系具有（ ） 。 A.自反性 B.反自

7、反性 C.对称性 D.反对称性 E.传递性 3下列公式中哪些是永真式？( ) (A)(PQ)(QR) (B)P(QQ) (C)(PQ)P (D)P(PQ) 4. 一棵非平凡的外向树，其对应矩阵满足（ ） 。 A.对角线全为零 B.仅有一行全为零 C.仅有一列全为零 D.至少有二行全为零 E.至少有二列全为零 5、设有如下命题 A)如果地上有水，则天上下雨 B)如果天上下雨，则地上有水 C)如果地上没有水，则天上不下雨 D)如果天上不下雨，则地上没有水 哪些命题等价的（ ） 。 A). A)与B)等价 ； B). A)与D)等价； C). A)与C)等价 ； D). B)与C)等价； E). C

8、)与D)等价 三、判三、判断断改改错错题题（本大（本大题题共共1 1小小题题，共，共1 10 0分）分） 指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 1) (x)P(x)(x)Q(x) P 2) (x)P(x) T,1),I 3) P(c) ES,2) 4) (x)Q(x) T,1),I 5) Q(c) ES,4) 3 1 2 311019040 离散数学离散数学（A 闭闭） 2010-2011-2 6) (P(c)Q(c) T,3),4),I 7）(x)(P(x)Q(x) EG,6) 四四、填空、填空题题（本大本大题题共共1010空空，每空每空1 1分分，共共1010分

9、分） 。 1设R是A = 2, 3, 12, 18, 24上的整除关系, 偏序集的极小元 ，极大 元是 。 2 R是实数集合， R中的关系g= _ _ 从R到R的函数 （填 “是” 或 “不是” ） 。 3设G是有n个结点，m条边的连通图，要确定G的一颗生成树，必须删去G的 条边 4. 在一棵二元树中，若每个结点的出度为 ，则称该树为完全二元树。 5. 设p：小明拿一个广柑，q：小明拿一个苹果。命题“小明只能拿一个广柑或一个苹果。 ”的 符号化形式为 。 6. 设谓词的定义域为a, b，将表达式xR(x)xS(x)中量词消除，写成与之对应的命题公式 是_ _ _。 7. 设集合A=a,b,c,

10、d，A上的关系R=(a,a),(a,c),(b,d) ，则关系R2= _。 8. 任何有限布尔代数都是与某个 格同构的，其元素个数都是 。 五五、计算题计算题（本大题共（本大题共4 4小题，每小题小题，每小题5 5分，共分，共2 20 0分） 。分） 。 1有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的道路的总数和回路总数。 2. 求下列公式的主析取范式和主合取范式： (PR)(QR)P。 3、某班有学生 60 人，其中有 38 人学习 PASCAL 语言，有 16 人学习C 语言，有 21 人学习 COBOL语言；有3个人这三种语言都学习，有2个人这三种语言都不学习，问仅学习两

11、门语 言的学生数是多少？ 4.写出如图所示的格的所有4元子格。 311019040 离散数学离散数学（A 闭闭） 2010-2011-2 六六、证明题证明题（本大（本大题题共共2 2小小题题，每小，每小题题1010分，共分，共2 20 0分） 。分） 。 1 设R是集合A上的一个具有传递和自反性质的关系， T是A上的关系， 使得TR且R，证明T是一个等价关系。 2. 设(B， ，0，1)是布尔代数，证明对B中任意元素a，b，baba 0。 七七、分析推理题分析推理题（本大（本大题题共共1 1小小题题，每，每小小题题1010分，共分，共1 10 0分）分） 。 某项工作需要派A、 B、 C和D 4个人中的2个人去完成， 按下面3个条件， 有几种派法？ 如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去；(3)若C去，则D留下。