离散数学模拟题

1、离散数学模拟测试题B一、选择题(每题1分，共12分)，下列每题只有一个正确答案, 选择正确答案并将序号填写在括号内。1. 设A,B,C是任意三个集合，下列关于集合的命题中正确的是（ ）(A) 如果且，则(B) 如果且，则(C) 如果且，则 (D) 如果且，则2.下列各关系中具有自反性和反对称性的关系是（）(A) 是自然数集合上的关系，且当且仅当或(B) 是自然数集合上的关系，且当且仅当(C) 是有理数集合上的关系，且当且仅当(D) 是自然数集合上的关系，且当且仅当3.设集合，下列关系中不是等价关系的是（ ）(A) (B) (C) (D) 4.设为任意集合，且，若，则一定有( )(A) (B)

2、(C) (D) 5.下列命题为假的是（ ）(A) (B) (C) (D) 6.下面哪个公式是重言式（ ）(A) (B) (C) (D) 7.谓词公式中的是（ ）(A) 自由变元(B) 约束变元(C) 既是自由变元又是约束变元(D) 既不是自由变元又不是约束变元8.设为整数集，下面哪个序偶不构成偏序集（ ）(A) （ 小于关系 ） (B) （ 小于等于关系 ）(C) （ 等于关系 ） (D) （整除关系 ）9.任何图中必有偶数个（ ）(A) 度数为偶数的结点 (B) 入度为奇数的结点(C) 度数为奇数的结点 (D) 出度为奇数的结点10.给定无向图如图1所示，下面哪个边集不是其边割集（ ）(A)

3、 (B) (C) (D) 图11.设图为无向图，则一定是（） (A) 完全图 (B) 树 图1(C) 简单图 (D)多重图12. 下图中是哈密尔顿图的是（ ）二、填空题(每空1分，共12分)，请将正确的答案填在横线内。1设是字母表，表示由上的字符构成的有限长度的串的集合（包含长度为0的字符串，即空串在内）。，则= 。2. 设，则幂集= 。3. 在1到1000的整数内（含1与1000在内）既不被6整除也不被10整除的数有 个。4. 设，则上的自反关系，对称关系有 个。5. 设偏序集中，其中，表示整除关系，该偏序集所有极大元构成的集合是 。6设解释I为：个体域，与为两个一元谓词，且，。在I下，公式

4、的真值是 。7. 令：为苹果，：与完全相同，：。则命题“没有完全相同的苹果”的符号化形式为： 。8. 无向图G有11条边，4个3度顶点，其余均为5度顶点，G的阶数n= 。9. ,的邻接矩阵，则的入度= ，的出度= ，到长度为2的路有 条。10. 有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，则一共有 种药品。三、计算题(要求写出计算过程，每题5分，共35分)1. 用等值演算法求下面公式的主析取范式2. 找出下列集合等式成立的充分必要条件，并简单说明理由3. 求下面公式的前束范式4. 设，为上的等价关系，且当且仅当。(1) 设I为上的恒等关系，求；(2) 求对应的的划分。5

5、. 图G是连通简单平面图，阶数，边数，求G的各面的次数。6. 集合上的偏序关系为整除关系。设，试画出的哈斯图，并求的最大元，极大元，最小元，极小元。7.设，求四、证明题(每题5分，共20分)1.设，在上定义关系当且仅当，证明是的等价关系。2.R为集合上二元关系，如果R是反自反的和传递的，则R一定是反对称的。3.若有n个人，每个人都有恰有5个朋友，则n必为偶数。4. 利用推理规则证明，前提：，结论：。五、综合题(每题7分，共21分)1.一个学校有507，292，312，和344位学生分别选了微积分、离散数学、数据结构和程序设计语言课，且有14人选了微积分和数据结构课，213人选了微积分和程序设计语言课，211人选了离散数学和数据结构课，43人选了离散数学和程序设计语言课，没有学生同时选择微积分和离散数学课，也没有学生同时选数据结构和程序设计语言课，问有多少学生在微积分，离散数学，数据结构或程序设计语言中选了课？2.令P(x),Q(x)和R(x)分别为语句“x是教授”，“x无知”，“x爱慕虚荣”。用量词、逻辑联结符和P(x),Q(x)，R(x)表示下列语句。假定论域是所有人集合。(1) 没有无知的教授。(2) 所有无知者均爱慕虚荣。(3) 没有爱慕虚荣的教授。(4) 能从(1)和(2)推出(3)吗？为什么？3. 某中学，张、王、李、赵4