离散数学第二章课后题目讲解.pdf

第二章谓词逻辑 2 1 1 将下列命题用谓词表达式符号化 a 小张不是工人 b 他是田径或球类运动员 c 小莉是非常聪明和美丽的 d 若 m是奇数 则 2m不是奇数 e 直线 A 与直线 B 平行当且仅当直线 A 与直线 B 不相交 f 全教练既不老但也不健壮 g 如果 5 大于 4 则 4 大于 6 解 a 设 W x x 是工人 c 小张 原命题可符号化为 W c b 设 S x x 是田径运动员 B x x 是球类运动员 h 他 原命题可符号化为 S h B h c 设 C x x 是聪明的 B x x 是美丽的 l 小莉 原命题可符号化为 C l B l d 设 O x x 是奇数 原命题可符号化为 O m O 2m e 设 P x y 直线 x 平行于直线 y G x y 直线 x 相交于直线 y 原命题可符号化为 P x y G x y f 设 O x x 是老的 V x x 是健壮的 j 全教练 原命题可符号化为 O j V j 2 1 2 将下列命题符号化 a 所有的教练员是运动员 J x L x b 某些运动员是大学生 S x c 某些教练是年老的 但是健壮的 x V x d 不是所有的运动员都是教练 e 所有的运动员都钦佩某些教练 A x y f 有些大学生不钦佩运动员 解 a 设 J x x 是教练员 L x x 是运动员 符号化 x J x L x b 设 S x x 是大学生 符号化 x L x S x c 设 O x x 是老的 V x x 是健壮的 符号化 x J x O x V x d 符号化 x L x J x e 设 A x y x 钦佩 y 符号化 x L x y J y A x y f 符号化 x S x y L y A x y 2 3 1 将下列命题符号化为谓词公式 a 兔子比乌龟跑得快 b 有的兔子比所以的乌龟跑得快 c 并不是所有的兔子都比乌龟跑得快 d 不存在跑得同样快的两只兔子 解 设 R x x 是兔子 T x x 是乌龟 F x y x 比 y 跑得快 S x y x 比 y 跑得同样快 a xy R x T y F x y b x R x y T y F x y c xy R x T y F x y d xy R x R y S x y 2 3 2 设 P x x 是质数 E x x 是偶数 O x x 是奇数 D x y y 被 x 除尽 将下列谓词公式翻译成汉语 a P 5 b E 2 P 2 c x D 2 x E x d x E x D x 6 e x E x D 2 x f x E x y D x y E y g x P x y E y D x y h x O x y P y D x y 解 a 5 是质数 b 2 是偶数且 2 是质数 a 所有能被 2 除尽的数必是偶数 b 存在 6 能被其除尽的偶数 c 不是偶数的数 必不能被 2 除尽 d 对所有 x 若 x 是偶数 则对任意 y 若 y 能被 x 除尽 则 y 也是偶数 e 对任意质数 x 必存在偶数 y 且 y 能被 x 除尽 f 对任意奇数 所有的质数均不能被它除尽 2 3 3 设 Q x y z x y z 其中 x y z 均为实数 试确定如下两个命题的真假值 xyz Q x y z zxy Q x y z 解 xyz Q x y z 表示对任意实数 x y 必存在实数 z 使 x y z 显然是真 命题 zxy Q x y z 表示存在实数 z 对任意实数 x y 必有 x y z 当然这样 z 是不存在的 所以是假命题 2 3 4 用谓词公式符号化下列命题 a 有一数比任何数都大 b 对于每一个实数 x 存在一个更大的实数 y c 存在实数 x y 和 z 使得 x 与 y 之和大于 x 与 z 之积 解 a 设 N x x 是数 G x y x 大于 y 符号化 x N x y N y G x y b 设 R x x 是实数 G x y x 大于 y 符号化 x R x y G y x R y c 设 R x x 是实数 G x y x 大于 y 符号化 xyz R x R y R z G x y xz 2 4 1 对下面每个公式指出约束变元和自由变元 a x x y b x x x x x c xy x y x x d xy x y z e x x y y x x y z 解 a x 是约束变元 y 是自由变元 b x 是约束变元 其中 x x 中的 x 受全称量词约束 x 中的 x 受存在量词约束 c x y 均是约束变元 其中 x 中的 x 受存在量词约束 x 中的 x 受全 称量词约束 d x y 是约束变元 z 是自由变元 e x y 中的 x 约束出现 y 自由出现 x x y z 中 y 约束出现 x z 自由出现 2 4 2 下列谓词公式中的约束变元进行换名 解 a xy x z y x y b x x x x x x z x z a uv u z v x y b u u u u v v w x w 2 4 3 对下列谓词公式中的自由变元进行代入 a y x y x x z xz x y z b y x y x z x x y 解 a y u y x x v xz x t z b y u y u z x x t 2 4 4 如果论域是 a b c 试消去下面公式中的量词 a x x b x x x x c x x x d x x x x e x x x x 解 a x x a b c b x x x x a b c a b c c x x x a a b b c c d x x x x a b c a b c e x x x x a b c a b c 2 4 5 考虑以下赋值 论域 D 1 2 指定常数 a 和 b a b 1 2 指定函数 f f 1 F 2 2 1 指定谓词 求下列各式的真假值 a a f a b f b b xy y x c xy x y f x f y 解 a a f a b f b 1 f 1 2 f 2 1 2 2 1 b xy y x x x x c xy x y f x f y x x f x f x f x f f f f f f f f f 2 5 1 判断下列谓词公式哪些是永真式 哪些是永假式 说明理由 a x A x x A x b x x x Q y x Q y x x c x x y y d F x y G x y F x y 解 a 为永真式 因为 x A x x A x x A x x A x x A x x A x x A x A x T b 为永假式 因为原公式是 A B A B 的代换实例 c 为永假式 因为 x x y y x x y y x x x x F d 永真式 因为 F x y G x y F x y F x y G x y F x y T 2 5 2 现定义一个新的量词 称为存在一个且仅有一个 其定义为 x x 为真 当且仅当存在一个且仅有一个 x 使 x 为真 试写出与 x x 等价并 只包含量词 和 的谓词公式 解 x x x x y y x y 2 5 3 设个体域为 0 1 将谓词公式 x y G x y 转换成不含量词的形式 解 x y G x y x G x 0 G x 1 G 0 0 G 0 1 G 1 0 G 1 1 G 1 0 G 1 1 G 0 0 G 0 1 2 5 4 自然数有三条公理 a 每个数都有唯一的一个数是它的后继数 b 没有一个数 使 1 是它的后继 c 每个不等于 1 的数 都有唯一的一个数是它的直接先行者 用谓词公式符号化上述三条公理 解 设 N x x 是一个数 S x y y 是 x 的后继数 即 x 是 y 的直接先行者 例如 z 的直接先行者是 1 于是 a x N x y N y S x y b x N x S x 1 c x N x S x z y N y S y x 2 5 5 证明如下等价式 a x A x B x x A x x B x b xy x y x x y y 证 a 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 b xy x y xy x y x x y y x x y y x x y y x x y y 2 5 6 判断下列推证是否正确 并说明理由 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 B x x A x x B x 2 6 1 求下列公式的前束范式 a xA x xB x b xA x xB x 解 a xA x xB x xA x yB y x A x yB y xy A x B y b xA x xB x xA x yB y xA x y B y x A x y B y xy A x B y 2 6 2 求下列公式的前束范式 a x x y x y b x y x y z z x c xy z x y z u x u v y v 解 a x x y x y x x y x y xy x x y b x y x y z z x x y x y z z x x y x y z z x x y x y z z x xyz x y z x c xy z x y z u x u v y v xy z x y z u x u v y v xy z x y z u x u v y v xyzuv x y z x u y v 1 6 3 求公式 x x y z x y z y x 的前束合取范式和 前束析取范式 解 x x y z x y z y x x x y x y y x x x y x y y x xy x x y y x 前束合取范式 xy x x y y x x x y y x x x y y x x x y y x x x y y x x x y y x x x y y x 前束析取范式 2 7 1 用推理规则证明下列各式 a x x a x x a b x x x x x a c x x x x x x x x x d x x x x x x x 证 a 1 x x a 2 x x a T 1 E8 3 x x 附加前提 4 a T 3 2 I10 5 x x a CP b 1 x x x 2 a a US 1 3 x x 4 a US 3 5 a T 4 2 I12 c 1 x x x 2 a a US 1 3 x x x 4 a a US 3 5 a a T 4 2 I13 6 x x x UG 5 d 1 x x x 2 a a US 1 3 x x 4 a US 3 5 a T 4 2 I10 6 x x EG 5 2 7 2 用推理规则证明以下各式 a x A x B x x B x x A x b x A x x B x x A x B x c x A x B x x x B x x x A x d x A x B x x B x x x x x A x 证 a 1 x A x B x 2 A a B a US 1 3 x B x 4 B a US 3 5 A a T 4 2 I12 6 xA x EG 5 b 1 x A x B x 附加前提 2 x A x B x T 1 E26 3 A a B a ES 2 4 A a T 3 I7 5 B a T 3 I8 6 xA x EG 4 7 xA x x B x 8 x B x T 6 7 I11 9 B a US 8 10 B a B a 矛盾 T 9 5 I9 c 1 x A x B x 2 A a B a US 1 3 x x B x 4 a B a US 3 5 B a A a T 2 E18 6 a A a T 4 5 I13 7 x x A x UG 6 d 1 x B x x 2 B a a US 1 3 x x 4 a US 3 5 B a T 4 2 I12 6 x A x B x 7 A a B a US 6 8 B a A a T 7 E3 9 A a T 5 8 I10 10 xA x UG 9 2 7 3 用 CP 规则证明下列各式 a x x x x x x x b x x x x x x x 证 a 1 x x 附加前提 2 a US 1 3 x x x 4 a a US 3 5 a T 4 2 I11 6 x x UG 5 7 x x x x CP b 因为 x x x x x x x x 所以本题可证 x x x x x x x 1 x x 附加前提 2 x x T 1 E26 3 a ES 2 4 x x x 5 a a US 4 6 a T 3 5 I10 7 x x EG 6 8 x x x x CP 2 7 4 用推理规则证明 x x x x x x x x x x xy x y 证 1 x x 2 x x x x x x T 1 E26 3 x x x x T 1 2 I11 4 a ES 1 5 a a a US 3 6 a a T 4 I3 7 a T 6 5 I11 8 x x 9 b ES 8 10 b b T 9 I4 11 b b b US 3 12 b T 10 11 I11 13 a b T 7 12 I9 14 y a y EG 13 15 xy x y EG 14 2 7 5 用推理规则证明 x x x y y y y y y x x x 证 1 y y y 2 a a US 1 3 a a