离散数学模拟试卷(I 卷).pdf

第 1 页 共 4 页 离散数学模拟试卷 I 卷 一 选择题 每题一 选择题 每题 1 分 共分 共 15 分 分 1 下列命题联结词集合中 下列命题联结词集合中 是最小联结词组 是最小联结词组 A B C D 2 如果如果 A B 成立 则以下各种蕴含关系中 成立 则以下各种蕴含关系中 是成立的 是成立的 A B A B A B C B A D A B 3 若个体域为整数集 下列公式中 若个体域为整数集 下列公式中 真值为真 真值为真 A 0yx y x B 0yx x y C 0yx y x D 0yx y x 4 下列各选项中错误的是 下列各选项中错误的是 A B C D 5 设设 R 和和 S 是集合是集合 A 上的任意关系 则下列命令中真值为真的是 上的任意关系 则下列命令中真值为真的是 A 若 R 和 S 是自反的 则 R S 是自反的 B 若 R 和 S 是反自反的 则 R S 是反 自反的 C 若 R 和 S 是对称的 则 R S 是对称的 D 若 R 和 S 是传递的 则 R S 是传递 的 6 集合集合 A 上的关系上的关系 R 是相容关系的必要条件是 是相容关系的必要条件是 A 自反 反对称的 B 反自反 对称的 C 传递 自反的 D 自反 对称的 7 任何无向图中结点间的连通关系是 任何无向图中结点间的连通关系是 A 偏序关系 B 等价关系 C 相容关系 D 拟序关系 8 若图若图 G 具有汉密尔顿回路 则对具有汉密尔顿回路 则对 V 的每个非空子集的每个非空子集 S 那么 那么 G S 的连通分支数的连通分支数 W G S 应满足 应满足 A W G S S B W G S S 第 2 页 共 4 页 C W G S S D W G S S 9 在有在有 n 个结点的连通图中 其边数 个结点的连通图中 其边数 A 最多有 n 1 条边 B 至少有 n 1 条边 C 最多有 n 条边 D 至少有 n 条边 10 一棵树有一棵树有 2 个个 2 度结点 度结点 1 个个 3 度结点 度结点 3 个个 4 度结点 那么树中应含有 度结点 那么树中应含有 个 个 1 度结点度结点 A 5 B 7 C 8 D 9 11 在自然数集在自然数集 N 上 下列运算 上 下列运算 不是可结合的 不是可结合的 A a b a b 3 B a b min a b C a b a 2b D a b a b mod 3 12 运算如下表所示 运算如下表所示 能使 能使成为独异点成为独异点 A B a b a a b b a b C D a b a a a b a a 13 在代数系统中 整环和域的关系是 在代数系统中 整环和域的关系是 A 整环一定是域 B 域不一定是整环 C 域一定是整环 D 域一定不是整环 14 下列偏序中不能构成格的是 下列偏序中不能构成格的是 A B C D a b a a a bb b a b a a b bb a 第 3 页 共 4 页 15 模格与分配格的关系是 模格 模格与分配格的关系是 模格 A 一定是分配格 B 不是分配格 C 不一定是分配格 二 填空题 每空二 填空题 每空 1 分 共分 共 10 分 分 1 命题 如果太阳从西边出来 那么地球自转 的真值为 2 设 A 2 3 5 7 11 B 1 2 4 8 则 A B 3 设 A a 则 A 的幂集为 4 设 A a b c B 1 2 令 f A B 则从 A 到 B 的函数个数为 5 已知集合 A 1 2 3 4 5 上的划分为 S 1 2 3 4 5 则由划分 S 导出的 A 上的等价 关系为 6 设 R 为非空集合 A 上的等价关系 其等价类记为 x R x y A 若 R 则 x R与 y R 的关系是 而若 R 则 x R y R 7 n 阶无向完全图应含有 条边 8 设 G 是连通简单平面图 G 中有 11 个顶点 5 个面 则 G 中有 边 9 设是一个代数系统 如果满足 则称是环 三 判断改错题 每题三 判断改错题 每题 2 分 共分 共 10 分 分 1 命题公式 P Q P 是重言式 2 设 R1 和 R2 为集合 A 上的相容关系 则 R1 R2 也是 A 上的相容关系 3 设函数 f A B g B C 则 g f 1 g 1 f 1 4 有割点的连通图可能是汉密尔顿图 5 任何一个循环群必定是 Abel 群 四 简答题 共四 简答题 共 40 分 分 1 用等式演算法求公式 P Q P Q 的主析取范式和主合取范式 并写出编码形 式 8 分 2 求公式 z y x H z z y x G y x f x 的前束范式 5 分 3 设集合 A a b c A 中的关系 R 6 分 a 求 r R 和 s R b 利用矩阵方法求 R 的传递闭包 t R 4 在偏序集中 其中 A 1 2 3 4 6 8 是 Z 中的整除关系 7 分 a 求出 COV A b 画出哈斯图 c 求集合 D 2 3 4 6 的极大元 极小元 最大元 最小元 最小上界和最大下界 5 设图 G 的邻接矩阵为 001 011 110 M 8 分 a 画出邻接矩阵对应的图 G 第 4 页 共 4 页 b 求出 G 的可达性矩阵 c 求 G 中长度为 2 的回路有多少条 6 设 S 是代数系统 其中 S a b c 的运算表为 6 分 a 讨论 S 是否构成独异点 并验证你的结论 b 指出有逆元的元素 五 证明题 共五 证明题 共 25 分 分 1 对下面推理进行符号化 并作证明 所有运动员都很健壮 李珊是个学生 并且是个运动 员 因此有些