离散数学自学考试复习题.pdf

离散数学 复习题 1 设A和B都是命题 则A B的真值为假当且仅当 A A为假 B为真 B A为假 B为假 C A为真 B为真 D A为真 B为假 学号 2 下列公式中为重言式的是 A P P Q R B Q P P C P Q Q P D P P Q 3 设A a a P A 表示A的幂集 下面各式中错误的 是 A a P A B a P A C a P A D a P A 4 设A 1 2 3 4 5 6 上的关系为R x y 则R 1具有 A 对称性 B 自反性 C 反自反性 反对称性 传递性 D 以上都不对 5 设R是非空集合A上的二元关系 则R的对称闭包S R A R IA B R RC C R IA D R RC 6 映射的复合运算满足 A 交换律 B 结合律 C 幂等 律 D 分配律 班级 7 设R I分别是实数集合和整数集合 分别是 普通的减法 乘法 和除法运算 则 是半群 A B C D 8 在一个格中 对任意的a b c A 都有 A a b c a b a c B a b c a b a c C a b c a b a c D A B C都正确 9 无向简单图G中结点间的连通关系是 A 偏序关系 B 等价关系 C 既是偏序关系又是等价关系 D A B C都错误 10 设G是一个有v个结点e条边的连通简单平面图 若v 3 则 A v 3e 6 B e 3v 6 C v 3e 6 D e 3v 6 11 设P和Q是命题 P P QQ 12 设A和B是集合 A B A当且仅当B 13 一个不是自反的关系 一定是反自反 的 14 若A和B是任意两个集合 则A B B A 15 关系f m n N m n 10 是函数 其中N是自然数 集合 16 集合B是集合A的真子集 则K B K A 17 整环一定是 域 18 任何两个具有2n个元素的有限布尔代数都是同构 的 19 已知无向连通图G中有n个结点 m条边 G中无回路 则m n 1 20 如果两个图的结点数相同 边数相等 度数相同的结点数 目也相等 那么这两个图是同构 的 21 设命题P表示 我今天将去公园 命题Q表示 天下 雨 则命题 我今天去公园 除非下雨 可以符号化为 1 22 命题 只有教师才有教师资格证 T x C x 可符号 为 2 23 设P A 是集合A的幂集 如果 A n 则 P A 3 A P A 4 24 设A a b c P A 为A的幂集 P A 是偏序集 则 P A 的子集 a b a b b c 的极大元 是 5 最大元是 6 上界是 7 下确界 是 8 25 设f和g是从整数集到整数集合的函数 其定义为f x 2x 3和g x 3x 2 则gf x 9 fg x 10 26 设是一个代数系统 并设R是A上的一个等价关系 如果和 R时 11 则称R为A上的同 余关系 27 设是一个格 由它诱导的代数系统为 如果对于任意的a b c A 当b a时 有 12 则称为模格 28 一个图是平面图 当且仅当它不包含与 13 或 14 在2 度结点内同构的子图 29 无向图G具有一条欧拉路 当且仅当G是 15 且有 16 奇数度结点 30 无向图G如右图所示 则G的点连通度 17 边连通度为 18 它的生成树有 19 条树枝和 20 条弦 31 求 A B C A B C 的主析取范式和主 合取范式 32 将下列推理形式化 并推证其结论 所有牛都有角 有些动物是牛 所以有些动物有角 33 设正整数的序偶集合A 在A上定义的二元关系R如下 R 当且仅当xv yu 证明R是一个等价关 系 34 设是群 S是G的非空子集 如果对于S中的任意元素 a和b 有a b 1 S 则是的子群 35 令gf是一个复合函数 若g和f是双射的 则gf是双射的 36 判断彼德森 Petersen 图是否为汉密尔顿图 若是 请写 出汉密尔顿回路 若不是 请予以证明 37 下列是两个命题变元p q的小项是 A p p q B p q C p q D p p q 38 令p 今天下雪了 q 路滑 则命题 虽然今天下雪了 但是路不 滑 可符号化为 A p q B p q C p q D p q 39 下列语句中是命题的只有 A 1 1 10 B x y 10 C sinx siny 0 D x mod 3 2 40 下列等值式不正确的是 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 41 谓词公式 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 42 设R为实数集 函数f R R f x 2x 则f是 A 满射函数 B 入射函数 C 双射函数 D 非入射非满射 43 设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 44 设A B P P A 以下正确的式子是 A B B B C B D B 45 设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 46 设 是集合A上的二元运算 称Z是A上关于运算 的零元 若 A 有x Z Z x Z B ZA 且有x Z Z x Z C ZA 且有x Z Z x x D ZA 且有x Z Z x Z 47 在自然数集N上 下列定义的运算中不可结合的只有 A a b min a b B a b a b C a b GCD a b a b的最大公约数 D a b a mod b 48 设R为实数集 R x x R x 0 是数的乘法运算 是一 个群 则下列集合关于数的乘法运算构成该群的子群的是 A R 中的有理数 B R 中的无理数 C R 中的自然数 D 1 2 3 49 设是环 则下列正确的是 A 是交换群 B 是加法群 C 对 是可分配的 D 对是可分配的 50 下列各图不是欧拉图的是 51 设G是连通平面图 G中有6个顶点8条边 则G的面的数目是 A 2个面 B 3个面 C 4个面 D 5个面 52 一公式为 之充分必要条件是其析取范式之每一析取项中均必同 时包含一命题变元及其否定 一公式为 之充分必要条件是其合取范 式之每一合取项中均必同时包含 一命题变元及其否定 53 前束范式具有形式 Q1V1 Q2V2 QnVn A 其中Qi 1 i n 为 A 为 的谓词公式 54 设论域是 a b c 则 x S x 等价于命题公式 S x 等价于命题公 式 55 设R为A上的关系 则R的自反闭包r R 对称闭包s R 56 某集合A上的二元关系R具有对称性 反对称性 自反性和传递性 此关系R是 其关系矩阵是 57 设是一个偏序集 如果S中的任意两个元素都有 和 则 称S关于 构成一个格 58 设Z是整数集 在Z上定义二元运算 为a b a b a b 其中 和 是数 的加法和乘法 则代数系统的幺元是 零元是 59 如下平面图有2个面R1和R2 其中deg R1 deg R2 60 无向图G具有一条欧拉回路 当且仅当G是 并且所有结点的度 数都是 61 在下图中 结点v2的度数是 结点v5的度数是 62 4分 求出从A 1 2 到B x y 的所有函数 并指出哪些是双射函 数 哪些是满射函数 63 4分 如果论域是集合 a b c 试消去给定公式中的量词 64 5分 设A a b c P A 是A的幂集 是集合对称差运算 已 知是群 在群中 找出其幺元 找出任一元素的 逆元 求元素x使满足 a x b 65 6分 用等值演算法求公式 p q p q 的主合取范式 66 5分 画出5个具有5个结点5条边的非同构的无向连通简单图 67 6分 在偏序集中 其中Z 1 2 3 4 6 8 12 14 是Z中的整 除关系 求集合D 2 3 4 6 的极大元 极小元 最大元 最小元 最小上界和最大下界 68 6分 用等值演算法证明 q s r s p r s p q r 69 6分 设n阶无向树G 中有m条边 证明m n 1 70 8分 设P 1 1 2 1 2 3 是集合P上的包含关系 1 证明 是偏序集 2 在 1 的基础上证明是全序集 71 设集合A 2 a 3 4 B a 3 4 1 E为全集 则下列命题正确 的是 A 2 A B a A C a BE D a 1 3 4 B 72 设集合A 1 2 3 A上的关系R 1 1 2 2 2 3 3 2 3 3 则R不 具备 A 自反性 B 传递性 C 对称性 D 反对称性 73 设半序集 A 关系 的哈斯图如下所示 若A的子集B 2 3 4 5 则 元素6为B的 74 设I是如下一个解释 D a b 则在解释I下取真值为1的公式是 A xyP x y B xyP x y C xP x x D xyP x y 75 若供选择答案中的数值表示一个简单图中各个顶点的度 能画出图 的是 A 1 2 2 3 4 5 B 1 2 3 4 5 5 C 1 1 1 2 3 D 2 3 3 4 5 6 76 设G H是一阶逻辑公式 P是一个谓词 G xP x H xP x 则一阶 逻辑公式GH是 A 恒真的 B 恒假的 C 可满足的 D 前束范式 77 设命题公式G PQ H P QP 则G与H的关系是 A GH B HG C G H D 以上都不是 78 设A B为集合 当 时A B B A A B B AB C BA D A B 79 设集合A 1 2 3 4 A上的关系R 1 1 2 3 2 4 3 4 则R具有 A 自反性 B 传递性 C 对称性 D 以上答案都不对 80 下列关于集合的表示中正确的为 A a a b c B a a b c C a b c D a b a b c 81命题公式P Q R的对偶式为 A P Q R B P Q R C P Q R D P Q R 82 设G是连通平面图 有5个顶点 6个面 则G的边数是 A 9条 B 5条 C 6条 D 11条 83 设G是5个顶点的完全图 则从G中删去 条边可以得到树 A 6 B 5 C 10 D 4 84 设图G的相邻矩阵为 则G的顶点数与边数分别为 A 4 5 B 5 6 C 4 10 D 5 8 85 设集合A B 其中A 1 2 3 B 1 2 则A B A B 86 设有限集合A A n 则 A A 87 已知命题公式G PQ R 则G的主析取范式是 88 设G是完全二叉树 G有7个点 其中4个叶点 则G的总度数为 分枝点数为 89 设A B为两个集合 A 1 2 4 B 3 4 则从AB AB A B 90 设R是集合A上的等价关系 则R所具有的关系的三个特性是 91 设命题公式G P QR 则使公式G为真的解释有 92 设集合A 1 2 3 4 A上的关系R1 1 4 2 3 3 2 R1 2 1 3 2 4 3 则 R1R2 R2R1 R12 93 设A B R是三个集合 其中R是实数集 A x 1 x 1 xR B x 0 x 2 xR 则A B B A A B 94 设集合A 2 3 4 5 6 R是A上的整除 则R以集合形式 列举法 记为 95 设集合A 1 2 3 4 6 8 9 12 R为整除关系 1 画出半序集 A R 的哈斯图 2 写出A的子集B 3 6 9 12 的上界 下界 最小上界 最大下 界 3 写出A的最大元 最小元 极大元 极小元 96 设集合A 1 2 3 4 A上的关系R x y x yA 且 x y 求 4 画出R的关系图 5 写出R的关系矩阵 97 设R是实数集合 是R上的三个映射 x x 3 x 2x x x 4 试求复合映射 98 设I是如下一个解释 D 2 3 abf 2 f 3 P 2 2 P 2 3 P 3 2 P 3 3 32320011 试求 1 P a f a P b f b 2 xy P y x 99 设集合A 1 2