安阳工学院离散数学

离散数学 200 题 一 单项选择题 1 下列是两个命题变元 p q 的小项是 A p p q B p q C p q D p p q 2 令 p 今天下雪了 q 路滑 则命题 虽然今天下雪了 但是路不滑 可符号化为 A p q B p q C p q D p q 3 下列语句中是命题的只有 A 1 1 10 B x y 10 C sinx siny 0 D x mod 3 2 4 下列等值式不正确的是 A x A x A B x B A x B x A x C x A x B x x A x x B x D x y A x B y x A x y B y 5 谓词公式 x P x y x Q x z x y R x y z 中量词 x 的辖域是 A x Q x z x y R x y z B Q x z y R x y z C Q x z x y R x y z D Q x z 6 设 R 为实数集 函数 f R R f x 2x 则 f 是 A 满射函数 B 入射函数 C 双射函数 D 非入射非满射 7 设 A a b c d A 上的等价关系 R IA 则对应于 R 的 A 的 划分是 A a b c d B a b c d C a b c d D a b c d 8 设 A B P P A 以下正确的式子是 A B B B C B D B 9 无向树 T 中有 3 个 3 度 2 个 2 度顶点 其余顶点都是树叶 T 有几片树叶 A 8 B 6 C 4 D 5 10 设 A a b c 则下列哪个是集合 A 的划分 A b c c B a b a c C a b c D a b c 11 设集合 X 0 1 2 3 R 是 X 上的二元关系 R 则哪个是 R 的关系矩阵 MR A B C D 12 从下列描述中 指出不正确的表述 A P a b c a b c a b c B P C D P a b c a b c a b c 13 从下列图中找出欧拉图 14 令 F x x 是金属 G y y 是液体 H x y x 可以溶解在 y 中 则命题 任何金属可以溶 解在某种液体中 可符号化为什么逻辑表达式 A x F x y G y H x y B x x F x G y H x y C x F x y G y H x y D x F x y G y H x y 15 在个体域 D a b 中 指出与公式 x A x 等价又不含量词的公式 A A a A b B A a A b C A a A b D A b A a 16 指出下列是命题的句子 A 水开了吗 B x 1 5 C 再过 9000 年 地球上就没水了 D 我没讲真话 17 给定算式 a b c d e f g h i j 找出与此算式对应的波兰符号表 示式 A a bc def g hij B abc d e fg hi j C a bcde fg hij D ab c de fgh ij 18 设 N 是自然数集 函数 f N N N f n n n 1 f 5 是什么 A 满射函数 B 单射函数 C D 双射函数 19 已知 p q r 的主析取范式是 m1 m3 m4 m7 指出与其对应的主合取范式 A m1 m2 m5 m7 B M0 M2 M5 M6 C m0 m3 m5 m6 D M1 M3 M5 M6 20 设 T x x 具有性质 T S y y 具有性质 S 命题 若存在 x 具有性质 T 则所有的 y 都没有性质 S 的符号化形式是什么 A x T x S x B x T x S x C x T x y S y D xT x y S y 21 判断下列各非负整数列哪个不是可图化的 A 5 5 4 4 2 1 B 4 4 2 1 3 C 5 4 3 2 2 D 3 3 1 1 22 设 Z N 分别为整数和自然数集 函数 g Z N g x x g 是什么函数 A 满射函数 B 满射非单射 C 单射函数 D 单射非满射 23 给定下列各图 判断哪 些为简单图 G1 其中 V1 a b c d e E1 a b b c c d a e G2 其中 V2 V1 E2 a b b e e b a e d e D3 其中 V3 V1 E3 D4 其中 V4 V1 E4 A G1 D4 B G1 D3 C G2 D3 D4 D G2 D4 24 下列哪个不是平面图 25 设 A a b c B 1 2 3 以下哪一个关系是从 A 到 B 的双射函数 A f B f C f D f 26 给定命题公式如右 p q r 指出公式的成真赋值 A 无 B 全体赋值 C 000 100 101 111 D 010 110 27 设 S 1 1 2 则 P S 有几个元素 A 3 B 6 C 7 D 8 28 下述哪一个不是命题 A 离散数学是计算机系的一门必修课 B 不存在最大偶数 C 若我有空 我就看书 D 请勿随地叶痰 29 无向图 G 中有 16 条边 且每个结点的度数均为 2 则结点数是多少 A 8 B 16 C 4 D 32 30 设集合 X 0 1 2 3 R 是 X 上的二元关系 R 则哪个是 R 的关系矩阵 MR A B C D 31 在个体域 D a b 中 指出与公式 x A x 等价又不含量词的公式 A A a A b B A a A b C A a A b D A b A a 32 指出下列是命题的句子 A 今天出太阳了吗 B Y 3 14 C 再过 8000 年 地球上就没生命了 D 我在说谎话 33 给定算式 a b c d e f g h i j 找出与此算式对应的波兰符号表 示式 A a bc def g hij B abc d e fg hi j C a bcde fg hij D ab c de fgh ij 34 设 N 是自然数集 函数 f N N N f n n n 1 f 6 是什么 A 满射函数 B 单射函数 C D 双射函数 35 已知 p q r 的主合取范式是 M0 M2 M5 M6 指出与其对应的主析取范式 A m1 m2 m5 m7 B m1 m3 m4 m7 C M0 M3 M5 M6 D M1 M3 M5 M6 36 判断下列各非负整数列哪个不是可图化的 A 5 5 4 4 2 3 B 4 4 2 1 3 C 5 4 3 2 2 D 3 3 1 1 37 设 Z N 分别为整数和自然数集 函数 g Z N g x x g 是什么函数 A 满射函数 B 满射非单射 C 单射函数 D 单射非满射 38 设 A a b c B 1 2 3 以下哪一个关系是从 A 到 B 的双射函数 A f B f C f D f 39 设 P 2 是素数 Q 3 是素数 R 是有理数 下列复合命题中假命题为哪 一个 A P Q R B R P Q C P Q P D R P Q 40 设有集合 A a b c 为空集 则下列哪一个表示是正确的 A a A B a A C a A D A 41 称由前提 Ak 推出结论 B 的推理正确 则 Ak B 应为下列表述中的哪 一个 A 重言式或可满足式 B 可满足式 C 矛盾式 D 重言式 42 若 P 他聪明 Q 他用功 则 他虽聪明 但不用功 可符号化为 A P Q B P Q C P Q D P Q 43 以下命题公式中 为永假式的是 A P P Q R B P P P C Q P P D P P P P 44 求一棵带权为 1 5 2 5 3 4 5 6 的最优 3 元树 其权为 A 30 B 35 C 37 D 45 45 给定命题公式如右 p q r 则公式的成真赋值为 公式的类型为 A 无 B 全体赋值 C 010 100 101 111 D 010 100 101 110 111 A 重言式 B 矛盾式 C 可满足式 D 以上都不对 46 设 S 1 2 10 是 S 上的整除关系 其中最大元是 最小元是 A 1 B 10 C 6 D 不存在 47 设有无向图 1 则 是一条哈密顿通路 A V7V1V6V5V4V3V2 B V1V2V3V4V5V6V7 C V1V2V4V5V6 D V2V3V4 48 在个体域 D a b 中 与公式 x A x 等价又不含量词的公式是 A A a A b B A a A b C A a A b D A b A a 49 下列是命题公式 p q r 的成真指派的是 A 110 111 100 B 110 101 011 C 所有指派 D 无 50 给定命题公式如右 p q r 则公式的成真赋值为 公式的类型为 A 无 B 全体赋值 C 010 100 101 111 D 010 100 101 110 111 A 重言式 B 矛盾式 C 可满足式 D 以上都不对 51 设 S 1 1 2 则 P S 有 个元素 A 3 B 6 C 7 D 8 52 设 S 1 2 10 是 S 上的整除关系 则的哈斯图是 其中 最大元是 最小元是 A 一棵树 B 一条链 C 有向图 D 以上都不对 A 1 B 10 C 6 D 不存在 53 给定序列 1 2 2 2 2 2 2 1 1 2 2 3 3 1 1 2 2 2 4 0 1 3 3 3 5 1 3 4 4 5 可以构成无向简单图的度数序列为 A 1 3 4 B 1 2 C 1 3 D 3 4 5 54 在一棵无向树中有 7 片树叶 3 个 3 度顶点 其余都是 4 度顶点 则该树有 个 4 度顶点 A 1 B 3 C 5 D 6 55 设个体域是正整数集 则下列公式中真值为真的公式是 A x y x y 0 B x y x y 1 C x y x y 2 D x y z x y z 56 一棵无向树有 2 个 4 度顶点 3 个 3 度顶点 其余的都是树叶 则该树有 片树叶 A 7 B 8 C 9 D 10 57 下列语句中 是命题 A 请把门关上 B 地球外的星球上也有人 C x 5 6 D 下午有会吗 58 命题公式 B A 等价于 A A B B A B C A B D A B 59 下列说法正确的是 A 若 B 若 C 若 D 若 60 下列说法错误的是 A B C D 61 设 P A 为 A 的幂集 则 P A 的元素个数为 A 3 B 6 C 7 D 8 62 集合 A 的一个划分 确定 A 的元素间的关系为 A 全序关系 B 等价关系 C 偏序关系 D 拟序关系 63 设命题公式 P Q P 记作 G 使 G 的真值指派为 F 的 P Q 的真值是下列 4 个中的哪一个 A T F B F T C T F D F T 64 命题公式 P Q P 是下列 4 个中的哪一个 A 永真式 B 永假式 C 可满足式 D 合取范式 65 谓词公式 xA x xA x 的类型是下列 4 个中的哪一个 A 永真式 B 矛盾式 C 非永真式的可满足式 D 不属于 A B C 任何类型 66 对任意集合 S S S 满足下面哪一个定律 A 等幂律 B 零一律 C 同一律 D 互补律 67 设 A 1 2 3 B 1 2 3 4 5 C 2 3 则 A B C A 1 2 B 2 3 C C 1 4 5 D 1 2 3 68 当且仅当为下面 4 个中的哪一个时 无向图 G 是欧拉图 A G 的所有结点的次数为偶数 B G 的所有结点的次数为奇数 C G 连通且所有结点的次数为偶数 D G 连通且所有结点的次数为奇数 69 设集合 A a1 a2 a3 a4 B b1 b2 b3 是从 A 到 B 的函数 a1 b2 a2 b2 a3 b1 a4 b3 则 是下面 4 个中的哪一种 A 双射 B 满射但不是单射 C 单射但不是满射 D 非单射也非满射 70 设 G 为无向简单图 V n G 为图 G 中结点的最大次数 请指出下面 4 个中哪个不等式是正确的 A G n D G n 71 设 S1 S2 S3 S4 以下命题为假的是哪一个 A S2 S4 B S1 S3 C S4 S2 D S4 S3 72 设 V a b c d 则与 V 能构成强连通图的边集合是下面 4 个中哪一个 A E a d b a b d c b d c B E a d b a b c b b d c C E a c b a b c d a d c D E a d a c a d b d c d 73 设集合 A a1 a2 a3 a4 B b1 b2 b3 是从 A 到 B 的函数 a1 b2 a2 b2 a3 b1 a4 b3 则 是下面 4 个中的哪一种 A 双射 B 满射但不是单射 C 单射但不是满射 D 非单射也非满 射 74 当且仅当为下面 4 个中的哪一个时 无向图 G 是欧拉图 A G 的所有结点的次数为偶数 B G 的所有结点的次数为奇数 C G 连通且所有结点的次数为偶数 D G 连通且所有结点的次数为奇数 75 79 75 个学生去书店买语文 数学 英语书 每种书每个学生至多买 1 本 已知 20 个学生每 人 买 3 本书 55 个学生每人至少买 2 本书 每本书的价格都是 1 元 所有学生总共花费 140 元 恰好买 2 本书的有 多少个学生 至少买 2 本书的学生花费 元 买 1 本书的有 个学生 至少买 1 本书的有 个学生 没买书的有 个学生 A 55 B 40 C 35 D 15 E 30 F 130 G 65 H 140 J 60 K 10 80 86 为每个逻辑断言选择正确的解释 T x x 今天来上课 S x x 学计算机专业的学 生 P x x 编程序 G x x 玩游戏 个体域是殷都大学 x T x 表示 x T x 表示 x T x 表示 x S x P x 表示 x S x G x 表示 x S x P x 表示 x S x G x 表示 A 学计算机专业的学生会编程序 B 殷都大学的学生都是计算机专业且会编程序 C 有些计算机专业的学生玩游戏 D 所有同学今天都来上课了 E 今天有同学没来上课 F 计算机专业的学生玩游戏 G 今天没有同学来上课 87 91 对 60 个人的调查表明有 25 人阅读 News 26 人阅读 Times 26 人阅读 Happy 9 人 阅读 News 和 Happy 11 人阅读 News 和 Times 8 人阅读 Times 和 Happy 还有 8 人什么杂志也不阅读 问阅读全部 3 种杂志的有 人 只阅读 News 的有 人 只阅读 Times 的有 人 只阅读 Happy 的有 人 只阅读一本杂志的有 人 A 5 B 8 C 3 D 15 E 30 F 13 G 65 H 12 J 60 K 10 92 设个体域是正整数集 则下列公式中真值为真的公式是 A x y x y 0 B x y x y 1 C x y x y 2 D x y z x y 2 93 设 A a b c R 是 A 的关系且 R 则 R 是的 A 传递 B 自反 C 对称 D 反自反 94 下述不是命题的是 A 做人真难啊 B 后天是阴天 C 2 是偶数 D 地球是方的 95 命题公式 P P Q R 是 A 恒真的 B 恒假的 C 可满足的 D 合取范式 96 设有 A a b c 上的关系 R 则 R 不具有 A 自反性 B 对称性 C 传递性 D 反对称性 97 下列等值式不正确的是 A x A x A B x B A x B x A x C x A x B x x A x x B x D x y A x B y x A x y B y 98 谓词公式 x P x y x Q x z x y R x y z 中量词 x 的辖域是 A x Q x z x y R x y z B Q x z y R x y z C Q x z x y R x y z D Q x z 99 设 X Y Z 是集合 一是集合相对补运算 下列等式不正确的是 A X Y Z X Y Z B X Y Z X Z Y C X Y Z X Z Y Z D X Y Z X Y Z 100 设 G 是连通平面图 G 中有 6 个顶点 8 条边 则 G 的面的数目是 A 2 个面 B 3 个面 C 4 个面 D 5 个面 二 填空题 101 设 p 天下雨 q 天刮风 r 我去书店 则命题 如果天不下雨并且不刮风 我就去 书店 的符号化形式为 102 设 F x x 是人 H x y x 与 y 一样高 在一阶逻辑中 命题 人都不一样高 的符号 化形式为 103 设 A a b 则 A 上共有 个不同的二元关系 104 设 A 1 2 B 2 3 C a b c 则 A B C 105 无环有向图的关联矩阵的所有元素之和为 106 设 G 是完全二叉树 G 有 15 个点 其中 8 个叶子 则 G 的总度数为 107 设 则 domR 108 设简单图 G 所有结点的度之和为 12 则 G 一定有 条边 109 图 4 中结点 V6 的度数为 110 p q r 的主合取范式为 111 p q r 的成真赋值为 112 p q r 的主合取范式为 113 设 A 2 3 6 12 是 A 上的整除关系 则偏序集 A 的最大元是 114 设 A B 0 1 从 A 到 B 的双射函数有 个 115 设 G 是完全二叉树 G 有 15 个点 其中 8 个叶点 则 G 的分枝点数为 116 一棵无向树有 2 个 4 度顶点 3 个 3 度顶点 其余的都是树叶 则该树有 片树 叶 117 设 A a b c B 1 2 3 则 A 到 B 共可产生 个不同的双射函数 118 某公司有销售人员 82 人 维修人员 191 人 既做销售又搞维修的人员 20 人 既非销 售人员又非维修人员有 912 人 则该公司总人数为 119 设个体域是 a b c 则 x S x 等价于命题公式 120 一公式为 之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变 元及其否定 一公式为 之充分必要条件是其合取范式之每一合取项中均必同时包含 一命题变元及其否定 121 前束范式具有形式 Q1V1 Q2V2 QnVn A 其中 Qi 1 i n 为 A 为 的谓词公式 122 设论域是 a b c 则 x S x 等价于命题公式 S x 等价于命题公式 123 设 R 为 A 上的关系 则 R 的自反闭包 r R 对称闭包 s R 124 某集合 A 上的二元关系 R 具有对称性 反对称性 自反性和传递性 此关系 R 是 其关系矩阵是 125 设是一个偏序集 如果 S 中的任意两个元素都有 和 则称 S 关于 构成一个格 126 设 Z 是整数集 在 Z 上定义二元运算 为 a b a b a b 其中 和 是数的加法和乘法 则代数系统的幺元是 零元是 127 如下平面图有 2 个面 R1 和 R2 其中 deg R1 deg R2 128 无向图 G 具有一条欧拉回路 当且仅当 G 是 并且所有结点的度数都是 129 设 p 小王走路 q 小王听音乐 在命题逻辑中 命题 小王边走路边听音乐 的符号化形 式为 130 设 F x x 是人 H x y x 与 y 一样高 在一阶逻辑中 命题 人都不一样高 的符号化 形式为 131 设 G 是 n 阶无向带权边通图 各变的权均为 a a 0 设 T 是 G 的一棵最小生成树 则 T 的权 W T 132 设 G1 G2 G3 G4 都是 4 阶 3 条边的无向简单图 则它们之间至少有 个是同构的 133 设 G 是 n n2 阶二部图 又是平面图 则命题 G 的对偶图是欧拉图 的真值为 134 设为整数集 则 f 的值域 ranf 135 设则 A 上共有 个不同的等价关系 136 设 恒等关系 IA 的传递闭包 t IA 137 在实数集合 R 上定义二元运算如下 其中 为普通的减法 命题 是 代数系统 的真值为 138 在一阶逻辑中将命题 鸟都会飞翔 符号化 139 在一阶逻辑中将命题 没有不爱看电影的人 符号化 140 将命题 如果今天是 1 号 则明天是 2 号 符号化 141 R 是 A 1 2 上的二元关系 则 R 具有哪些性质 141 设 p 小王走路 q 小王听音乐 在命题逻辑中 命题 小王边走路边听音乐 的符号化形 式为 142 设 F x x 是人 H x y x 与 y 一样高 在一阶逻辑中 命题 人都不一样高 的符号化 形式为 143 p q 的成真赋值为 144 设 f 为整数集 则 f 的值域 ranf 145 设 A 3 则 A 上共有 个不同的二元关系 146 命题公式 p q r 的成真指派的是 147 q 的主合取范式为 148 A ab 则 A 上共有 个不同的偏序关系 149 设 A a b c B 1 2 3 则 A 到 B 共可产生 个不同的双射函数 150 设 A 是 n n 1 元集 则 A 上共有 22n 个二元运算 其中有 个是 A 到 A 的函数 三 计算与应用题 151 求出从 A 1 2 到 B x y 的所有函数 并指出哪些是双射函数 哪些是满射函数 152 如果论域是集合 a b c 试消去给定公式中的量词 153 设 A a b c P A 是 A 的幂集 是集合对称差运算 已知是群 在群 中 找出其幺元 找出任一元素的逆元 求元素 x 使满足 a x b 154 用等值演算法求公式 p q p q 的主合取范式 155 画出 5 个具有 5 个结点 5 条边的非同构的无向连通简单图 156 在偏序集中 其中 Z 1 2 3 4 6 8 12 14 是 Z 中的整除关系 求集合 D 2 3 4 6 的极大元 极小元 最大元 最小元 最小上界和最大下界 设为一个偏序集 其中 A 1 2 3 4 6 9 24 54 R 是 A 上的整除关系 157 画出的哈斯图 158 求 R 关于 A 的极大元 159 求 B 4 6 9 的最小上界和最大下界 160 设 7 个字母在通信中出现的频率如下 a 30 b 20 c 15 d 10 e 15 f 5 g 5 编一个最佳 2 元前缀码 在这个前缀码中 a b c d e f g 的码长分别是多少 传输 10000 个按上 述比例出现的字母需要多少个二进制数字 161 设 A a b c d R IA 是 A 上的等价关系 求商集 A R 及各元素的等价类 162 求公式 p q r p q r 的主析取范式 163 判断推理是否正确 设 y 2 x x 为实数 推理如下 若 y 在 x 0 可导 则 y 在 x 0 连续 y 在 x 0 连续 所以 y 在 x 0 可导 在偏序集中 其中 Z 1 2 3 4 6 8 12 24 是 Z 中的整除关系 163 求集合 D 2 3 4 6 的极大元 极小元 164 求集合 D 2 3 4 6 的最大元 最小元 165 求集合 D 2 3 4 6 的最小上界和最大下界 166 设集合 A 1 3 5 7 9 11 13 15 A 上的一个划分 S 1 15 3 9 11 13 5 7 试求由 S 导出的 A 上的等价关系 R 167 求出从 A 1 2 到 B x y 的所有函数 并指出哪些是双射函数 哪些是满射函数 168 用等值演算法求公式 p q p q 的主合取范式 169 在偏序集中 其中 Z 1 2 3 4 6 8 12 14 是 Z 中的整除关系 求集合 D 2 3 4 6 的极大元 极小元 最大元 最小元 最小上界和最大下界 设二元关系 R 求 171 计算 domR 172 计算 ranR 173