离散数学同步练习-解答.pdf

华南理工大学网络教育学院华南理工大学网络教育学院 离散数学 练习题 离散数学 练习题 第一章命题逻辑 一填空题 1 设 p 派小王去开会 q 派小李去开会 则命题 派小王或小李中的一人去开会 可符号化 为 p q p q 2 设A B都是命题公式 A B 则A B的真值是 T 3 设 p 刘平聪明 q 刘平用功 在命题逻辑中 命题 刘平不但不聪明 而且不用功 可符号化为 p q 4 设 A B 代表任意的命题公式 则蕴涵等值式为 A B A B 5 设 p 径一事 q 长一智 在命题逻辑中 命题 不径一事 不长一智 可符号化为 p q 6 设 A B 代表任意的命题公式 则德 摩根律为 A B A B 7 设 p 选小王当班长 q 选小李当班长 则命题 选小王或小李中的 一人当班长 可符号化为 p q p q 8 设 P 他聪明 Q 他用功 在命题逻辑中 命题 他既聪明又用功 可符号化为 P Q 9 对于命题公式 A B 当且仅当 A B 是重言式时 称 A 蕴含 B 并记为 A B 10 设 P 我们划船 Q 我们跑步 在命题逻辑中 命题 我们不能既划船又跑步 可符号化为 P Q 11 设 P Q 是命题公式 德 摩根律为 P Q P Q 12 设 P 你努力 Q 你失败 在命题逻辑中 命题 除非你努力 否则 你将失败 可符号化为 P Q 13 设 p 小王是 100 米赛跑冠军 q 小王是 400 米赛跑冠军 在命题逻 辑中 命题 小王是 100 米或 400 米赛跑冠军 可符号化为 p q 14 设 A C 为两个命题公式 当且仅当 A C 为一重言式 时 称 C 可由 A 逻辑地推出 二 判断题 1 设 A B 是命题公式 则蕴涵等值式为 A B A B 2 命题公式 p q r 是析取范式 3 陈述句 x y 5 是命题 4 110 p 1 q 1 r 0 是命题公式 p q r q 的成真赋值 5 命题公式 p p q 是重言式 6 设 A B 都是合式公式 则 A B B 也是合式公式 7 A B C A B A C 8 陈述句 我学英语 或者我学法语 是命题 9 命题 如果雪是黑的 那么太阳从西方出 是假命题 10 请不要随地吐痰 是命题 11 P Q P Q 12 陈述句 如果天下雨 那么我在家看电视 是命题 13 命题公式 P Q R T 是析取范式 14 命题公式 P Q R P Q 是析取范式 三 选择题 在每小题的备选答案中只有一个正确答案 将正确答案序号填入 下列叙述中的 内 1 设 P 天下雪 Q 他走路上班 则命题 只有天下雪 他才走路上班 可符号化为 2 1 P Q 2 Q P 3 Q P 4 Q P 2 1 明年国庆节是晴天 2 在实数范围内 x y 3 3 请回答这个问题 4 明天下午有课吗 在上面句子中 是命题的只有 1 3 命题公式 A 与 B 是等值的 是指 4 1 A 与 B 有相同的命题变元 2 A B 是可满足式 3 A B 为重言式 4 A B 为重言式 4 1 雪是黑色的 2 这朵花多好看呀 3 请回答这个问题 4 明天下午有会吗 在上面句子中 是命题的是 1 5 设 P 天下大雨 Q 他乘公共汽车上班 则命题 只要天下大雨 他就 乘公共汽车上班 可符号化为 2 1 Q P 2 P Q 3 Q P 4 Q P 6 设 P 你努力 Q 你失败 则命题 除非你努力 否则你将失败 在命题逻辑中可符号化为 3 1 Q P 2 P Q 3 P Q 4 Q P 7 1 现在开会吗 2 在实数范围内 x y 5 3 这朵花多好看呀 4 离散数学是计算机科学专业的一门必修课 在上面语句中 是命题的只有 4 8 设 P 天气好 Q 他去郊游 则命题 如果天气好 他就去郊游 可符号化为 1 1 P Q 2 Q P 3 Q P 4 Q P 9 下列式子是合式公式的是 2 1 P Q 2 P Q R 3 P Q 4 Q R 10 1 1 101 110 2 中国人民是伟大的 3 全体起立 4 计算机机房有空位吗 在上面句子中 是命题的是 2 11 设 P 他聪明 Q 他用功 则命题 他虽聪明但不用功 在命题逻辑中可符号化为 3 1 P Q 2 P Q 3 P Q 4 P Q 12 1 如果天气好 那么我去散步 2 天气多好呀 3 x 3 4 明天下午有会吗 在上面句子中 1 是命题 13 设 P 王强身体很好 Q 王强成绩很好 命题 王强身体很好 成 绩也很好 在命题逻辑中可符号化为 4 1 P Q 2 P Q 3 P Q 4 P Q 四 解答题 1 设命题公式为 p q q p 1 求此命题公式的真值表 2 给出它的析取范式 1 p q p p q q p p q q p T T F T F F T F F T T T F T T T T T F F T F T T 2 p q q p p q q p p q q p p q q p 2 设命题公式为 p q p r 1 求此命题公式的真值表 2 给出它的析取范式 1 p q r p q p r p q p r T T T T T T T T F T T T T F T F T F T F F F T F F T T T T T F T F T F F F F T T T T F F F T F F 2 p q p r p q p r p q p p q r p p q p p r q r q p p r q r 3 设命题公式为 Q P Q P 1 求此命题公式的真值表 2 求此命题公式的析取范式 1 P Q Q P Q P Q P Q Q P Q P T T F T F F T T F T F F F T F T F T T F T F F T T T T T 2 解 Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P 4 完成下列问题 求命题公式 P Q R S 的析取范式 解 P Q R S P Q R S P Q R S P Q R S P Q R S P Q R S 5 设命题公式为 P P Q Q 1 求此命题公式的真值表 2 求此命题公式的析取范式 1 P Q P Q P P Q P P Q Q T T T T T T F F F T F T T F T F F T F T 2 解 P P Q Q P P Q Q P P Q Q P P Q Q P P Q Q P P Q Q 6 设命题公式为 P Q P Q 1 求此命题公式的真值表 2 给出它的析取范式 1 P Q P Q P P Q P P Q P Q T T T F F T T F T F F T F F F T F T F T T T T T 2 解 P Q P Q P Q P Q P Q P Q P Q P Q T 7 用直接证法证明 前提 P Q P R Q S 结论 S R 证明 1 P Q P 2 P Q T 1 E 3 Q S P 4 P S T 2 3 I 5 S P T 4 E 6 P R P 7 S R T 5 6 I 8 S R T 7 E 8 用直接证法证明 前提 P Q R S Q P S 结论 R 证明 1 P Q R P 2 P P 3 Q R T 2 3 I 4 S Q P 5 S P 6 Q T 4 5 I 7 R T 3 6 E 第二章谓词逻辑 一填空题 1 若个体域是含三个元素的有限域 a b c 则 xA x A a A b A c 2 取全总个体域 令 F x x 为人 G x x 爱看电影 则命题 没有不爱 看电影的人 可符号化为 x F x G x 3 若个体域是含三个元素的有限域 a b c 则 xA x A a A b A c 4 取全总个体域 令 M x x 是人 G y y 是花 H x y x 喜欢 y 则命 题 有些人喜欢所有的花 可符号化为 x M x y G y H x y 5 取个体域为全体人的集合 令 F x x 在广州工作 G x x 是广州人 在一阶逻辑中 命题 在广州工作的人未必都是广州人 可符号化为 x F x G x 6 P x x 是学生 Q x x 要参加考试 在谓词逻辑中 命题 每个学生都要参加考试 可符号化为 x P x Q x 7 M x x 是人 B x x 勇敢 则命题 有人勇敢 但不是所有的人都勇 敢 谓词符号化为 x M x B x x M x B x 8 P x x 是人 M x x 聪明 则命题 尽管有人聪明 但不是一切人都 聪明 谓词符号化为 x P x M x x P x M x 9 I x x 是实数 R x x 是正数 N x x 是负数 在谓词逻辑中 命题 任何实数或是正的或是负的 可符号化为 x I x R x N x 10 P x x 是学生 Q x x 要参加考试 在谓词逻辑中 命题 每个学生都要参加考试 可符号化为 x P x Q x 11 令 M x x 是大学生 P y y 是运动员 H x y x 钦佩 y 则命题 有 些大学生不钦佩所有运动员 可符号化为 x M x y P y H x y 二 判断题 1 设 A B 都是谓词公式 则 x A B 也是谓词公式 2 设 c 是个体域中某个元素 A 是谓词公式 则 A c xA x 3 x yA x y y xA x y 4 x yA x y y xA x y 5 取个体域为整数集 则谓词公式 x y x y y 是假命题 6 x P x Q x x P x Q x 7 命题公式 P Q R P Q 是析取范式 8 谓词公式 x A x B x y R x 的自由变元为 x y 9 x A x B x A x B 10 R x x 是大学生 是命题 三 选择题 在每小题的备选答案中只有一个正确答案 将正确答案序号填入 下列叙述中的 内 1 设F x x是火车 G x x是汽车 H x y x比y快 命题 某些汽 车比所有火车慢 的符号化公式是 2 1 y G y x F x H x y 2 y G y x F x H x y 3 x y G y F x H x y 4 y G y x F x H x y 2 设个体域为整数集 下列真值为真的公式是 3 1 y x x y 2 2 x y x y 2 3 x y x y 2 4 x y x y 2 3 设 F x x 是人 G x x 早晨吃面包 命题 有些人早晨吃面包 在谓 词逻辑中的符号化公式是 4 1 x F x G x 2 x F x G x 3 x F x G x 4 x F x G x 5 下列式子中正确的是 1 1 x P x x P x 2 x P x x P x 3 x P x x P x 4 x P x x P x 6 下面谓词公式是永真式的是 b a P x Q x b x P x x P x c P a x P x d P a x P x 5 设S x x是运动员 J y y是教练员 L x y x钦佩y 命题 所有 运动员都钦佩一些教练员 的符号化公式是 c a x S x y J y L x y b x y S x J y L x y c x S x y J y L x y d y x S x J y L x y 6 下列式子是合式公式的是 2 1 P Q 2 P Q R 3 P Q 4 Q R 7 下列式子中正确的是 1 1 x P x x P x 2 x P x x P x 3 x P x x P x 4 x P x x P x 四 解答题 1 构造下面推理的证明 前提 x F x y F y G y R y x F x 结论 x R x 证明 1 x F x y F y G y R y 前提引入 2 x F x 前提引入 3 y F y G y R y 1 2 假言推理 4 F c 2 EI 5 F c G c 4 附加 6 F c G c R c 3 UI 7 R c 5 6 假言推理 8 x R x 7 EG 2 在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车 每个人或者喜欢坐汽车或者喜欢骑 自行车 有的人不喜欢骑自行车 因而有的人不喜欢步行 令 F x x 喜欢步行 G x x 喜欢坐汽车 H x x 喜欢骑自行车 前提 x F x G x x G x H x x H x 结论 x F x 证明 1 x H x 前提引入 2 H c 1 EI 3 x G x H x 前提引入 4 G c H c 3 UI 5 G c 6 x F x G x 前提引入 7 F c G c 6 UI 8 F c 9 x F x 8 EG 3 在命题逻辑中构造下面推理的证明 如果他是理科学生 他必须学好数学 如果他不是文科学生 他必是理 科学生 他没学好数学 所以他是文科学生 令 F x x 是理科学生 G x x 学好数学 H x x 是文科学生 前提 x F x G x x H x F x x G x 结论 x H x 证明 1 x F x G x 前提引入 2 x G x 前提引入 3 x F x T 1 2 I 4 x H x F x 前提引入 5 x H x T 3 4 I 4 用直接证法证明 前提 x C x W x R x x C x Q x 结论 x Q x R x 推理 1 x C x W x R x P 2 x C x Q x p 3 C a Q a ES2 4 C a W a R a US1 5 C a T3 I 6 W a R a T4 5 I 7 Q a T3 I 8 R a T6 I 9 Q a R a T7 8 I 10 x Q x R x EG9 第三章集合与关系 一填空题 1 如果 A n 那么 A A n 2 A上的二元关系有 个 2 2n 2 集合 A 上关系 R 的自反闭包 r R R I 3 设集合A上的关系R和S R 1 2 1 3 3 2 S 1 3 2 1 3 2 则S R 1 2 2 2 2 3 4 如果 A n 那么 P A 2 n 5 设集合A上的关系R和S R S 则R S 6 设集合 E a b c E 的幂集 P E 7 设 R 是定义在集合 X 上的二元关系 如果对于每个 x y X 则称集合 X 上的关系 R 是对称的 8 设关系 R 和 S 为 R S 则 R S 9 设 R 是定义在集合 X 上的二元关系 如果对于每个 x y X 则称集合 X 上的关系 R 是自反的 二 判断题 1 设 A B C 为任意的三个集合 则 A B C A B C 2 设 S T 是任意集合 如果 S T 则 S T 3 集合 A 1 2 3 4 上的关系 是一个函数 4 集合 A 1 2 3 4 上的整除关系是等价关系 5 集合 A 的幂集 P A 上的包含关系是偏序关系 6 设 A a b c R A A 且 R 则 R 是传递的 6 设 A B 是任意集合 如果 B 则 A B A 7 集合 A 1 2 3 上的关系 是传递的 8 集合 A 1 2 3 4 上的小于关系是等价关系 9 关系 x1 x2 N x1 x2 6 能构成一个函数 10 集合 A 上的恒等关系是偏序关系 11 集合 A 1 2 3 上的关系 S 是自反的 12 设 X 1 2 3 Y a b c 函数 F 是双射 13 集合 A 上的关系 R 的自反闭包 r R R IA 14 集合 A 上的偏序关系 R 是自反的 对称的 传递的 15 设 A B 是任意集合 则 A B A B B A 三 选择题 在每小题的备选答案中只有一个正确答案 将正确答案序号填入 下列叙述中的 内 1 设A a b c B a b 则下列命题不正确的是 a a A B a b b A B a b c A B c d B A 2 设 A a b c d A 上的关系R 则它的对 称闭包为 c a R b R c R d R 3 对于集合 1 2 3 4 上的关系是偏序关系的是 a a R b R c R d R 4 设A 1 2 3 4 5 B 6 7 8 9 10 以下哪个关系是从A到B的 单射函数 b a f b f c f d f 5 设 A a b c 要使关系 R 具有对称性 则 d a R b R c R d R 6 设S 1 1 2 则S的幂集P S 有 4 个元素 1 3 2 6 3 7 4 8 7 设 R 为定义在集合 A 上的一个关系 若 R 是 2 则 R 为等价关系 1 反自反的 对称的和传递的 2 自反的 对称的和传递的 3 自反的 反对称的和传递的 4 对称的 反对称的和传递的 8 设S T M为任意集合 下列命题正确的是 c a 如果 S T S M 则 T M b 如果 S T 则 S T c S T S d S S S 9 设 A a b c 要使关系 R 具有对 性 则 4 1 R 2 R 3 R 4 R 10 设A 1 2 3 4 5 B a b c d e 以下哪个函数是从A到B的 入射函数 b a F b F c F d F 四 解答题 1 已知偏序集 A 其中 A a b c d e 为 a b a c a d c e b e d e a e IA 1 画出偏序集 A 的哈斯图 2 求集合 A 的极大元 极小元 最大元 最小元 1 e 2 集合 A 的极大元是 e 极小元 a 最大元 e 最小元 a 2 设 R 是集合 A 1 2 3 4 5 6 7 8 9 上的整除关系 1 给出关系 R 2 画出关系 R 的哈斯图 3 指出关系 R 的最大 最小元 极大 极小元 1 R d a b c 4 5 1 2 3 6 8 9 2 7 3 关系 R 的无最大 最小元是 1 极大元是 8 和 9 极小元是 1 3 设 R 是集合 A 1 2 3 4 6 12 上的整除关系 2 给出关系 R 2 给出 COV A 3 画出关系 R 的哈斯图 4 给出关系 R 的极大 极小元 最大 最小元 1 R 2 COV A 3 12 4 关系 R 的极大 最大元是 12 极小元 最小元是 1 4 3 1 2 6 第五章代数结构 一填空题 1 集合 S 的幂集 P S 关于集合的并运算 的零元为 S 2 集合 S 的幂集 P S 关于集合的并运算 的零元为 3 集合 S 的幂集 P S 关于集合的并运算 的么元为 4 一个代数系统 S 其中S是非空集合 是S上的一个二元运算 如 果 在S上是封闭的 则称代数系统 S 为广群 二 判断题 1 含有零元的半群称为独异点 2 运算 是整数集 I 上的普通加法 则群的么元是 1 三 填空题 在每小题的备选答案中只有一个正确答案 将正确答案序号填入 下列叙述中的 内 1 下列群一定为循环群的是 e e 运算 是整数集 I 上的普通加法 f R 是实数集 是普通乘法 g 运算 是有理数集 Q 上的普通加法 h P S 是集合 S 的幂集 为对称差 2 运算 是整数集 I 上的普通减法 则代数系统 满足下列 性质 3 1 结合律 2 交换律 3 有零元 4 封闭性 3 设 I 是整数集 N 是自然数集 P S 是 S 的幂集 是普通 的乘法 加法和集合的交运算 下面代数系统中 2 是群 1 2 3 4 4 下列代数系统不是群的是 2 1 运算 是整数集 I 上的普通加法 2 P S 是集合 S 的幂集 为交运算 3 运算 是有理数集 Q 上的普通加法 4 P S 是集合 S 的幂集 为对称差 第七章图论 一填空题 1 一个无向图G V E 是二部图当且仅当G中无 奇数 长度的回路 2 任何图 无向的或有向的 中 度为奇数的顶点个数为 偶数 3 设 D 是一个有向图 若 D 中任意一对顶点都是相互可达的 则称 D 是 双向连通的 4 既不含平行边 也不含环的图称为 简单图 5 经过图中 每条边 一次且仅一次并的回路 称为欧 拉回路 6 一棵有 n 个顶点的树含有 n 1 边 7 设 G V E G V E 是两个图 若 V V 且 E E 称 G 是 G 的生成子图 8 经过图中 每个结点 一次且仅一次的回路 称为哈密 尔顿回路 二 判断题 1 5 个顶点的有向完全图有 20 条边 2 连通无向图的欧拉回路经过图中的每个顶点一次且仅一次 3 图中的初级通路都是简单通路 4 已知 n n 2 阶无向简单图 G 有 n 1 条边 则 G 一定为树 5 n 阶无向完全图 Kn的每个顶点的度都是 n 6 一个无向图是二部图当且仅当它没有奇数度的顶点 7 任何图都有一棵生成树 8 连通无向图的哈密尔顿回路经过图中的每条边一次且仅一次 9 图中的初级回路都是简单回路 10 任一图 G V E 的顶点的最大度数必小于 G 的顶点数 11 欧拉图一定是汉密尔顿图 12 无向连通图 G 的任意两结点之间都存在一条路 13 根树中除一个结点外 其余结点的入度为 1 三 选择题 在每小题的备选答案中只有一个正确答案 将正确答案序号填入 下列叙述中的 内 1 下列为欧拉图的是 4 2 下列各图为简单图的是 3 1 2 3 4 3 设无向图 G 有 12 条边 已知 G 中 3 度顶点有 6 个 其余顶点的度数都小 于 3 则该图至少有 3 个顶点 1 6 2 8 3 9 4 12 4 下列四个有 6 个结点的图 3 是连通图 1 2 3 4