离散数学期末考试试题(有几套带答案1)

离散试卷及答案离散试卷及答案 第 1 页 共 5 页 离散数学试题 A 卷及答案 一 证明题 一 证明题 1010 分 分 1 P Q R Q R P R R 证明 左端 P Q R Q P R P Q R Q P R P Q R Q P R P Q Q P R P Q P Q R T R 置换 R 2 x A x B x xA x xB x 证明 x A x B x x A x B x x A x xB x xA x xB x xA x xB x 二 求命题公式二 求命题公式 P Q R P Q R P Q R P Q R 的主析取范式和主合取范式 的主析取范式和主合取范式 1010 分 分 证明 P Q R P Q R P Q R P Q R P Q R P Q R P Q P R P Q R P Q R P Q R P Q R P Q R P Q R m0 m1 m2 m7 M3 M4 M5 M6 三 推理证明题 三 推理证明题 1010 分 分 1 1 C D C D C D C D E E E E A A B B A A B B R S R S R SR S 证明 1 C D E 2 E A B 3 C D A B 4 A B R S 5 C D R S 6 C D 7 R S 2 2 x P x x P x Q y R x Q y R x xP x xP x Q y Q y x P x x P x R x R x 证明 1 xP x 2 P a 3 x P x Q y R x 4 P a Q y R a 5 Q y R a 6 Q y 7 R a 8 P a 9 P a R a 10 x P x R x 11 Q y x P x R x 五 已知五 已知 A A B B C C 是三个集合 证明是三个集合 证明 A B C A B A C A B C A B A C 1515 分 分 证明证明 x A B C x A x B C x A x B x C x A x B x A x C x A B x A C x A B A C A B C A B A C 六 已知六 已知 R R S S 是是 N N 上的关系 其定义如下 上的关系 其定义如下 R R x yx y N y xN y x2 2 S S x yx y N y x 1 N y x 1 求 求 R R 1 1 R SR S S RS R R R 1 2 1 2 S 1 2 S 1 2 1010 分 分 解 R 1 x y N y x2 R S x y N y x2 1 S R x y N y x 1 2 七 若七 若 f A Bf A B 和和 g B Cg B C 是双射 则 是双射 则 gfgf 1 1 f f 1 1g g 1 1 1010 分 分 证明 因为 f g 是双射 所以 gf A C 是双射 所以 gf 有逆函数 gf 1 C A 同理可推 f 1g 1 C A 是双射 因为 f 1g 1 存在 z g 1 f 1 存在 z f g 离散试卷及答案离散试卷及答案 第 2 页 共 5 页 gf gf 1 所以 gf 1 f 1g 1 R 1 2 S 1 2 1 4 离散数学试题离散数学试题 B B 卷及答案 卷及答案 一 证明题 一 证明题 1010 分 分 1 P Q 1 P Q P P Q Q R R P P Q Q P P R R T T 证明证明 左端 P Q P Q R P Q P R 摩根律 P Q P Q P R P Q P R 分配律 P Q P R P Q P R 等幂律 T 代入 2 2 x P x x P x Q x Q x xP x xP x x P x Q x x P x Q x 证明证明 x P x Q x xP x x P x Q x P x x P x Q x P x x P x Q x xP x xQ x x P x Q x 二 求命题公式二 求命题公式 P P Q Q P P Q Q 的主析取范式和主合取范式 的主析取范式和主合取范式 1010 分 分 解 P Q P Q P Q P Q P Q P Q P Q P Q P P Q Q P Q P Q M1 m0 m2 m3 三 推理证明题 三 推理证明题 1010 分 分 1 P1 P Q Q S S R P QR P Q R R S S 证明 1 R 附加前提 2 R P P 3 P T 1 2 I 4 P Q S P 5 Q S T 3 4 I 6 Q P 7 S T 5 6 I 8 R S CP 2 2 x P x Q x x P x Q x x x P x P x x x Q x Q x 证明 1 x P x P 2 P c T 1 US 3 x P x Q x P 4 P c Q c T 3 US 5 Q c T 2 4 I 6 x Q x T 5 EG 五 已知五 已知 A A B B C C 是三个集合 证明是三个集合 证明 A B C A B A C A B C A B A C 1010 分 分 证明 证明 x A B C x A x B C x A x B x C x A x B x A x C x A B x A C x A B A C A B C A B A C 六 六 A A1 1 A A2 2 A An n 是集合是集合 A A 的一个划分 定义的一个划分 定义 R aR ab a b Ab Ai i I 1I 1 2 2 n n 则 则 R R 是是 A A 上的等价关系 上的等价关系 1515 分 分 证明 证明 a A 必有 i 使得 a Ai 由定义知 aRa 故 R 自反 a b A 若 aRb 则 a b Ai 即 b a Ai 所以 bRa 故 R 对称 a b c A 若 aRb 且 bRc 则 a b Ai及 b c Aj 因为 i j 时 Ai Aj 故 i j 即 a b c Ai 所以 aRc 故 R 传递 总之 R 是 A 上的等价关系 七 若七 若 f A Bf A B 是双射 则是双射 则 f f 1 1 B A B A 是双射 是双射 1515 分 分 证明证明 对任意的 x A 因为 f 是从 A 到 B 的函数 故存在 y B 使 f f 1 所以 f 1是满射 对任意的 x A 若存在 y1 y2 B 使得 f 1且 f 1 则有 f 且 f 因为 f 是函数 则 y1 y2 所以 f 1是单射 因此 f 1是双射 一 一 选择题选择题 每小题每小题 2 2 分 总计分 总计 30 30 离散试卷及答案离散试卷及答案 第 3 页 共 5 页 1 给定语句如下 1 15 是素数 质数 2 10 能被 2 整除 3 是偶数 3 你下午有会吗 若无会 请到我这儿来 4 2x 3 0 5 只有 4 是偶数 3 才能被 2 整除 6 明年 5 月 1 日是晴天 以上 6 个语句中 是简单命题的为 A 是复合命题的为 B 是真命题的为 C 是假命题的是 D 真值待定的命题是 E A 1 3 4 6 1 4 6 1 6 B 2 4 2 4 6 2 5 C 1 2 5 6 无真命题 5 D 1 2 无假命题 1 2 4 5 E 4 6 6 无真值待定的命题 2 将下列语句符号化 1 4 是偶数或是奇数 A 设 p 4 是偶数 q 4 是奇数 2 只有王荣努力学习 她才能取得好成绩 B 设 p 王荣努力学习 q 王荣取得好成绩 3 每列火车都比某些汽车快 C 设 F x x 是火车 G y y 是汽车 H x y x 比 y 快 A p q p q p q B p q q p p q C x x y y F x G y H x y x x F x y y G y H x y x x F x y y G y H x y 3 设 S 1 2 3 下图给出了 S 上的 5 个关系 则它们只具有以下性质 R1是 A R2是 B R3是 C A B C 自反的 对称的 传递的 反自反的 对称的 自反的 反对称的 对称的 自反的 对称的 反对称的 传递的 4 设S 1 1 2 则有 1 A S S 2 B S S 3 P S 有 C 个元数 4 D 既是S的元素 又是S的子集 A 1 2 1 B 1 2 1 C 3 6 7 8 D 1 二 证明 本大题共二 证明 本大题共 2 2 小题 第小题 第 1 1 小题小题 1010 分 第分 第 2 2 小题小题 1010 分 总计分 总计 2020 分 分 1 用等值演算算法证明等值式 p q p q p 2 构造下面命题推理的证明 如果今天是星期三 那么我有一次英语或数学测验 如果数学老师有事 那么没有数学测验 今天是星期三且数学老师有事 所以我有一次英语测验 三 计算 本大题共三 计算 本大题共 4 4 小题 第小题 第 1 1 小题小题 5 5 分 第分 第 2 2 小题小题 1010 分 第分 第 3 3 小题小题 1515 分 分 总计总计 3030 分 分 1 设 求公式 212 个体域为为 整除为 xxQyxyxP 的真值 xQyxPyx 2 设集合上的关系 求出它的自反闭包 对称闭包和传递闭包 AA 4 3 2 1 4 3 3 2 1 2 2 1 1 1 R 离散试卷及答案离散试卷及答案 第 4 页 共 5 页 3 设上的整除关系 是否为上的偏序关系 若是 则 24 12 8 4 2 1 A 212121 aaAaaaaR整除 RA 1 画出的哈斯图 1010 分 分 R 2 求它的极小元 最大元 极大元 最大元 5 5 分 分 四 四 用推导法求公式的主析取范式和主合取范式 本大题 本大题 1010 分 分 pqp 答案 答案 一 选择题 1 A B C D E 2 A B C 3 A B C 4 A B C D 二 证明题 1 证明 左边 p q p p q q 分配律 p p q q 吸收律 p p q q q 分配律 p p q 1 排中律 p p q 同一律 p 吸收律 2 解 p 今天是星期三 q 我有一次英语测验 r 我有一次数学测验 s 数学老师有事 前提 p q r s r p s 结论 q 证明 p s 前提引入 p 化简 p q r 前提引入 q r 假言推理 s 化简 s r 前提引入 r 假言推理 q 析取三段论 推理正确 三 计算 1 1 12 2 1 112 121 212 22 xyP x yQ x yPyQPyQ PQPQPQPQ 1 11 1 21 2 10 2 21 11 20 11001110 1 PPPPQQ 该公式的真值是 1 真命题 离散试卷及答案离散试卷及答案 第 5 页 共 5 页 或者 TTTFTTT FT