离散数学第2章习题解答.doc

第 2 章 习题解答 1 习题 2 1 1 将下列命题符号化 1 4 不是奇数 解 设 A x x 是奇数 a 4 4 不是奇数 符号化为 A a 2 2 是偶数且是质数 解 设 A x x 是偶数 B x x 是质数 a 2 2 是偶数且是质数 符号化为 A a B a 3 老王是山东人或河北人 解 设 A x x 是山东人 B x x 是河北人 a 老王 老王是山东人或河北人 符号化为 A a B a 4 2 与 3 都是偶数 解 设 A x x 是偶数 a 2 b 3 2 与 3 都是偶数 符号化为 A a A b 5 5 大于 3 解 设 G x y x 大于 y a 5 b 3 5 大于 3 符号化为 G a b 6 若 m 是奇数 则 2m 不是奇数 解 设 A x x 是奇数 a m b 2m 若 m 是奇数 则 2m 不是奇数 符号化为 A a A b 7 直线 A 平行于直线 B 当且仅当直线 A 不相交于直线 B 解 设 C x y 直线 x 平行于直线 y 设 D x y 直线 x 相交于直线 y a 直线 A b 直 线 B 直线 A 平行于直线 B 当且仅当直线 A 不相交于直线 B 符号化为 C a b D x y 8 小王既聪明又用功 但身体不好 解 设 A x x 聪明 B x x 用功 C x x 身体好 a 小王 小王既聪明又用功 但身体不好 符号化为 A a B a C a 9 秦岭隔开了渭水和汉水 解 设 A x y z x 隔开了 y 和 z a 秦岭 b 渭水 c 汉水 秦岭隔开了渭水和汉水 符号化为 A a b c 10 除非小李是东北人 否则她一定怕冷 解 设 A x x 是东北人 B x x 怕冷 a 小李 除非小李是东北人 否则她一定怕冷 符号化为 B a A a 2 将下列命题符号化 并讨论它们的真值 1 有些实数是有理数 解 设 R x x 是实数 Q x x 是有理数 有些实数是有理数 符号化为 x R x Q x 第 2 章 习题解答 2 它的真值为 真 2 凡是人都要休息 解 设 R x x 是人 S x x 要休息 凡是人都要休息 符号化为 x R x S x 它的真值为 真 3 每个自然数都有比它大的自然数 解 设 N x x 是自然数 G x y x 比 y 大 每个自然数都有比它大的自然数 符号化为 x N x y N y G y x 它的真值为 真 4 乌鸦都是黑的 解 设 A x x 是乌鸦 B x 是黑的 乌鸦都是黑的 符号化为 x A x B x 它的真值为 真 5 不存在比所有火车都快的汽车 解 设 A x x 是汽车 B x 是火车 K x y x 比 y 快 不存在比所有火车都快的汽车 符号化为 x A x y B y K x y 它的真值为 真 6 有些大学生不佩服运动员 解 设 S x x 是大学生 L x 是运动员 B x y x 佩服 y 有些大学生不佩服运动员 符号化为 x S x L y B x y 它的真值为 真 7 有些女同志既是教练员又是运动员 解 设 W x x 是女同志 J x x 是教练员 L x x 是运动员 有些女同志既是教练员又是运动员 符号化为 x W x J x L x 它的真值为 真 8 除 2 以外的所有质数都是奇数 解 设 A x x 是质数 B x x 是奇数 C x y x 不等于 y 除 2 以外的所有质数都是奇数 符号化为 x A x C x 2 B x 它的真值为 真 3 指出一个个体域 使下列被量化谓词的真值为真 该个体域是整数集合的最大子集 在 以下各题中 A x 表示 x 0 B x 表示 x 5 C x y 表示 x y 0 1 x A x 解 正整数集合 Z 2 x A x 解 整数集合 Z 3 x B x 解 集合 5 4 x B x 解 整数集合 Z 第 2 章 习题解答 3 5 x y C x y 解 整数集合 Z 4 分别在全总个体域和实数个体域中 将下列命题符号化 1 对所有的实数 x 都存着实数 y 使得 x y 0 解 设 R x x 是实数 B x y x y 0 在实数个体域符号化为 x y B x y 在全总个体域符号化为 x R x y R y B x y 2 存在着实数 x 对所有的实数 y 都有 x y 0 解 设 R x x 是实数 B x y x y 0 在实数个体域符号化为 x y B x y 在全总个体域符号化为 x R x y R y B x y 3 对所有的实数 x 和所有的实数 y 都有 x y y x 解 设 R x x 是实数 B x y x y 在实数个体域符号化为 x y B x y y x 在全总个体域符号化为 x R x y R y B x y y x 4 存在着实数 x 和存在着实数 y 使得 x y 100 解 设 R x x 是实数 B x y x y 100 在实数个体域符号化为 x y B x y 在全总个体域符号化为 x R x y R y B x y 习题 2 2 1 指出下列公式中的约束变元和自由变元 1 x P x Q y 解 约束变元 x 自由变元 y 2 x P x R x x P x Q x 解 约束变元 x 自由变元 x 3 x P x x Q x x R x y Q z 解 约束变元 x 自由变元 y z 4 x y R x y Q z 解 约束变元 x y 自由变元 z 5 z P x x R x z y Q x y R x y 解 约束变元 x y z 自由变元 x y 2 对下列谓词公式中的约束变元进行换名 1 x y P x z Q x y R x y 解 将约束变元 x 换成 u u y P u z Q u y R x y 将约束变元 y 换成 v x v P x z Q x v R x y 2 x P x R x Q x y x R x z S x z 解 将前面的约束变元 x 换成 u 后面的约束变元 x 换成 v 第 2 章 习题解答 4 u P u R u Q u y v R v z S x z 将约束变元 z 换成 w x P x R x Q x y x R x w S x w 3 对下列谓词公式中的自由变元进行代入 1 y Q z y x R x y x S x y z 解 将自由变元 z 用 u 代入 y Q u y x R x y x S x y u 将自由变元 y 用 v 代入 y Q z y x R x v x S x v z 2 y P x y z Q x z x R x y 解 将自由变元 x 用 u 代入 y P u y z Q u z x R x y 将自由变元 y 用 v 代入 y P x y z Q x z x R x v 4 利用谓词公式对下列命题符号化 1 每列火车都比某些汽车快 解 设 A x x 是火车 B x x 是汽车 C x y x 比 y 快 每列火车都比某些汽车快 符号化为 x A x y B y C x y 2 某些汽车比所有火车慢 解 设 A x x 是火车 B x x 是汽车 C x y x 比 y 快 某些汽车比所有火车慢 符号化为 x B x y A y C y x 3 对每一个实数 x 存在一个更大的实数 y 解 设 R x x 是实数 G x y x 比 y 大 对每一个实数 x 存在一个更大的实数 y 符号化为 x R x y R y G y x 4 存在实数 x y 和 z 使得 x 与 y 之和大于 x 与 z 之积 解 设 R x x 是实数 G x y x 比 y 大 存在实数 x y 和 z 使得 x 与 y 之和大于 x 与 z 之积 符号化为 x y z R x R y R z G x y xz 5 所有的人都不一样高 解 设 R x x 是人 G x y x 和 y 一样高 所有的人都不一样高 符号化为 x y R x R y G x y 5 自然数一共有下述三条公理 a 每个数都有惟一的一个数是它的后继数 b 没有一个数使数 1 是它的后继数 c 每个不等于 1 的数都有惟一的一个数是它的直接先驱数 用两个谓词表达上述三条公理 注 设 n 是不等于 1 的自然数 则 n 1 是 n 的后继数 n 1 是 n 的先驱数 解 设 A x x 是数 B x y x 是 y 后继数 根据定义 也可理解为 y 是 x 先驱数 a 每个数都有惟一的一个数是它的后继数 符号化为 x A x y A y B y x z A z B z x z y b 没有一个数使数 1 是它的后继数 符号化为 x A x B 1 x c 每个不等于 1 的数都有惟一的一个数是它的直接先驱数 符号化为 x A x x 1 y A y B x y z A z B x z z y 6 取个体域为实数集 R 函数 f 在 a 点连续的定义是 对每个 0 存在一个 0 使 第 2 章 习题解答 5 得对所有 x 若 x a 则 f x f a 试把此定义用符号化的形式表达出来 解 0 0 x x a f x f a 7 若定义惟一性量词 x 为 存在惟一的一个 x 则 x P x 表示 存在惟一的一个 x 使 P x 为真 试用量词 谓词及逻辑运算符表示 x P x 解 x P x x P x y P y y x 习题 2 3 1 设个体域为 D 1 2 3 试消去下列各式的量词 1 x P x 解 x P x P 1 P 2 P 3 2 x P x y Q y 解 x P x y Q y P 1 P 2 P 3 Q 1 Q 2 Q 3 3 x P x y Q y 解 x P x y Q y P 1 P 2 P 3 Q 1 Q 2 Q 3 4 x P x Q x 解 x P x Q x P 1 Q 1 P 2 Q 2 P 3 Q 3 5 x P x y Q y 解 x P x y Q y P 1 P 2 P 3 Q 1 Q 2 Q 3 2 求下列各式的真值 1 x y H x y 其中 H x y x y 个体域为 D 4 2 解 x y H x y y H 2 y y H 4 y H 2 2 H 2 4 H 4 2 H 4 4 0 0 1 0 0 1 0 2 x S x Q a p 其中 S x x 3 Q x x 5 a 3 p 5 3 个体域为 D 1 3 6 解 x S x Q a p S 1 Q 3 S 3 Q 3 S 6 Q 3 5 3 0 0 0 0 1 0 1 1 1 0 1 1 1 1 3 x x2 2x 1 0 其中个体域为 D 1 2 解 x x2 2x 1 0 1 2 2 1 1 0 22 2 2 1 0 4 0 1 0 0 0 0 3 证明下列各式 其中 B 是不含变元 x 的谓词公式 1 x S x R x x S x x R x 证明 x S x R x x S x R x x S x x R x x S x x R x x S x x R x 2 x y S x R y x S x y R y 第 2 章 习题解答 6 证明 x y S x R y x y S x R y x S x y R y x S x y R y x S x y R y 3 x A x B x A x B 证明 x A x B x A x B x A x B x A x B x A x B 4 x B A x B x A x 证明 x B A x x B A x B x A x B x A x 5 x A x B x x A x x B x 证明 因为 x A x B x 所以对于任意个体 c A c B c 和 A c 从而有 B c 由 c 的任意性有 x B x 根据 CP 规则 x A x B x x A x x B x 6 x A x B x x A x x B x 证明 x A x B x x A x B x B x A x x A x B x x B x A x x A x B x x B x A x x A x B x x A x x B x 同理 x A x B x x B x A x x B x x A x 所以 x A x B x x B x A x x A x x B x x B x x A x 而 x A x x B x x B x x A x x A x x B x 故有 x A x B x x A x x B x 4 判断下列证明是否正确 x A x B x x A x B x x A x B x x A x B x x A x x B x x A x x B x x A x x B x x A x x B x 解 下列的推理是错的 x A x B x x A x x B x 习题 2 4 1 求下列各式的前束范式 1 x P x x Q x 解 x P x x Q x x P x x Q x x P x Q x 2 x P x x Q x 解 x P x x Q x x P x x Q x x P x y Q y x y P x Q y 3 x y z A x y z u B x u v B x v 解 x y z A x y z u B x u v B x v x y z u A x y z B x u v B x v 第 2 章 习题解答 7 x y z u v A x y z B x u B x v 4 x y z A x z B x z u R x y u 解 x y z A x z B x z u R x y u x y z u A x z B x z R x y u 5 x y A x y x y B x y y A y x B x y 解 x y A x y x y B x y y A y x B x y x y A x y x y B x y z A z x B x z x y A x y u v z B u v A z u B u z x y u v z A x y B u v A z u B u z x y u v z A x y B u v A z u B u z 2 求下列各式的前束合取范式 1 x P x z Q z y y R x y 解 x P x z Q z y y R x y x z P x Q z y y R x y x z P x Q z y u R x u x z u P x Q z y R x u x z u P x Q z y R x u x z u P x Q z y R x u x z u P x R x u Q z y R x u 2 x y P x y Q y z x R x y 解 x y P x y Q y z x R x y x u P x u Q u z v R v y x u v P x u Q u z R v y x u v P x u R v y Q u z R v y 3 y Q z y x R x y x S x y z 解 y Q z y x R x y x S x y z u Q z u x R x y v S v y z u x v Q z u R x y S v y z u x v Q z u R x y S v y z 3 求下列各式的前束析取范式 1 x P x y x Q x y z R x y z 解 x P x y x Q x y z R x y z x P x y x Q x y z R x y z x P x y u z Q u y R x y z x y u z P x Q u y R x y z x y u z P x Q u y R x y z 2 x y P x y Q y z x R x y 解 x y P x y Q y z x R x y x u P x u Q u z v R v y 第 2 章 习题解答 8 x u v P x u Q u z R v y x u v P x u R v y Q u z R v y 3 y Q z y x R x y x S x y z 解 y Q z y x R x y x S x y z u Q z u x R x y x S x y z u x Q z u R x y x S x y z u x Q z u R x y v S v y z u x v Q z u R x y S v y z 习题 2 5 1 证明下列各式 1 x F x G y R x x F x x F x R x 证明 x F x P F c ES x F x G y R x P F c G y R c US G y R c T 假言推理 R c T 化简律 F c R c T 合取引入 x F x R x EG 2 x F x G x x R x G x x R x F x 证明 x R x G x P R c G c US x F x G x P F c G c US G c F c T 假言易位式 R c F c T 假言三段论 x R x F x UG 3 x F x G x x G x R x x R x x F x 证明 x R x P R c US x G x R x P G c R c US G c T 拒取式 x F x G x P F c G c US F c T 析取三段论 第 2 章 习题解答 9 x F x UG 4 x F x y F y G y R y x F x x R x 证明 x F x P F c ES x F x y F y G y R y P y F y G y R y T 假言推理 F c G c R c US F c G c T 附加律 R c T 假言推理 x R x UG 2 用 CP 规则证明下列各式 1 x F x R x x F x x R x 证明 x F x P 附加前提 F c US x F x R x P F c R c US R c T 假言推理 x R x UG x F x x R x CP 2 x F x G x x G x R x x R x x F x 证明 x R x P 附加前提 R c US x G x R x P x G x R x T 量词否定等价式 G c R c US G c R c T 德摩根律 G c T 析取三段论 x F x G x P F c G c US F c T 析取三段论 x F x UG x R x x F x CP 3 x F x G x x G x R x x R x x F x 证明 x R x P 附加前提 x R x T 量词否定等价式 R c ES x G x R x P 第 2 章 习题解答 10 G c R c US G c T 析取三段论 x F x G x P F c G c US F c T 拒取式 x F x EG x R x x F x CP 3 用归谬法证明下列各式 1 x F x G x x F x x G x 证明 x F x x G x P 附加前提 x F x x G x T 德摩根律 x F x x G x T 量词否定等价式 x F x T 化简律 F c ES x G x T 化简律 G c US x F x G x P F c G c US F c T 析取三段论 F c F c 矛盾 T 合取引入 2 x F x G x x G x R x x R x x F x 证明 x F x P 附加前提 x F x T 量词否定等价式 F c ES x F x G x P F c G c US G c T 析取三段论 x G x R x P G c R c US R c T 假言推理 x R x P R c US R c R c 矛盾 T 合取引入 3 x F x G x x G x R x x R x x F x 证明 x R x P R c ES x F x P 附加前提 x F x T 量词否定等价式 第 2 章 习题解答 11 F c US x F x G x P F c G c US G c T 假言推理 x G x R x P G c R c US R c T 析取三段论 R c R c 矛盾 T 合取引入 4 证明下面推理 1 每个有理数都是实数 有的有理数是整数 因此 有的实数是整数 解 首先将命题符号化 Q x x 是有理数 R x x 是实数 Z x x 是整数 本题要证明 x Q x R x x Q x Z x x R x Z x 证明 x Q x Z x P Q c Z c ES Q c T 化简律 Z c