离散数学综合练习题.pdf

集合 数理逻辑 图部分的综合练习题 一 单选题 1 设A B为集合 则下列命题为真的是 A 若 则 B 若 则 C 若 则 D 若 则 2 设R是实数集 其子集 X x 3 x 0 Y x 1 x 5 Z x x 1 则 X Y Z A B x 1 x 0 C x 3 x 1 或 1 x 5 D x 3 x 5 3 若A B 则必有 A B B B C D 4 0与 间的关系是0 A B C D 5 设关系R S 则R S A B C D 6 设X 1 2 R x y X x y 3 则关系R在X上 A 是自反的 但不是对称的 B 是对称的 但不是自反的 C 既是对称的 又是自反的 D 既不是对称的 又不是自反的 7 设X a b c R 则关系R的自反且传递的闭包是 A B C D 8 设X a 则P X X A B C D 9 设R和S是集合A上的关系 则下列命题为真的是 A 若R和S都是自反的 R S也是自反的 B 若R和S都是对称的 R S也是对称的 C 若R和S都是反对称的 R S也是反对称的 D 若R和S都是传递的 R S也是传递的 10 设A a b c d 下列 是A的一个划分 A a b b c c d B a b c d a b c d C a b c d D a b c 11 下列句子中 是命题 A B 将手机关掉 C 是有理数 D 天气真冷啊 12 下列命题中 是简单命题 A 张三和李四都是大学生 B 张三和李四是同学 C 张三和李四不是同学 D 如果张三是二年级的 则李四就是三年级的 13 下列推理依据 蕴涵式 不正确的是 A B C D 14 以下公式中不是可满足式的是 A Q P P B P Q P C P Q Q D Q P P 15 在P Q R为原子生成的极小项中 对应于二进制数101的是 A P Q R B P Q R C P Q R D P Q R 16 设P 天下雨 Q 我骑自行车上班 命题 除非天下雨 否则我骑 自行车上班 可符号化为 A P Q B Q P C P Q D Q P 17 设P 2是素数 Q 3是素数 R 是有理数 下列公式中为真的是 A P Q R B R P Q C R P Q D R P Q 18 在下列各组公式中 不是等值式 A 与 B 与 C 与 D 与 19 设I是如下的解释 个体域D 1 2 F 1 2 F 2 2 0 F 1 1 F 2 1 1 在I下 下列公式真值为1的是 A B C D 20 由n个命题原子组成的不等值的命题公式的个数是 A 2n B 2n C n2 D 21 下列四组数中 可以对应做4阶图 无向 简单 四个点的度的是 A 1 2 3 4 B 0 2 2 3 C 1 1 2 2 D 1 3 3 3 22 设G为7阶图 则下列命题可能为真的是 A G的每个点的度都是3 B G的每个点的度都是5 C G的每个点的度都是6 D G的每个点的度都是7 23 在有n个点的连通图中 其边数 A 最多有n 1条 B 最多有n条 C 最少有n 1条 D 最少有n条 24 下列图中 不是树 A 无回路的连通图 B 有n个点n 1条边的连通图 C 每对点之间都有通路的图 D 连通但任意删去一条边就不连通的图 二 填空题 1 设A 0 1 3 B 0 3 6 R是A到B的关系 R x y A B 则R 的关系矩阵是 2 设集合A 1 2 3 4 5 6 7 8 9 10 11 12 R是A上的 整除关系 子集 B 2 4 6 的最大元是 最小元是 上界是 下界是 3 设集合A 1 2 3 4 5 6 8 10 24 36 R是A上的整除关 系 子集 B 1 2 3 4 的上界是 下界是 上确界是 下确界是 4 设集合A 2 3 4 5 6 8 10 12 R是A上的整除关系 A的 极大元是 极小元是 5 设非空集合A满足 A n 则从A到A的双射函数有 个 6 设A a a a B a a 则 7 设A B是集合 则命题A B A B的真值是 8 P Q的主合取范式中含 个极大项 9 设F x x是人 G x x呼吸 命题 所有人都呼吸 可符号化为 10 设F x x是实数 G x x是有理数 H x x是无理数 命题 实数 不是有理数就是 无理数 可符号化为 11 设F x x是熊猫 G x x产在中国 命题 熊猫都产在中国 可符 号化为 12 在个体域D 1 2 3 中 公式消去量词后的形式是 13 公式p q在联结词完备集 中的等值式是 14 n阶m条边得到图G是树的充分必要条件是G连通 且m 15 完全图Kn的边数为 16 n阶k度正则图的边数为 17 n阶图 无向简单图 中各点度的最大值不超过 18 设图G有12条边 有6个度为3的点 其余点的度都小于3 则G至少 有 个点 三 计算题 1 设集合A 1 2 3 4 5 6 7 8 9 10 12 画出A上整除关 系的哈斯图 2 设f R R f x x2 1 g R R g x x 2 求f g 3 求p p q r 的主析取范式和主合取范式 4 构造下面推理的证明 要求每步都写出依据 前提 p q q r r 结论 p s 5 化简公式 P Q Q P R 6 用真值表判断 P Q Q R P R 是否重言 式 7 写出的前束范式 8 设有向图G 其中 V a b c d e A 写出G的邻接矩阵 9 对下图 求v1到其余各点的最短路径 v2 7 v4 2 v6 3 1 8 v1 2 5 4 9 7 9 v3 4 v5 v7 10 求上图的最小生成树 最优树 四