离散数学(刘任任版)第14章答案.ppt

离散数学 习题解答 1 2 指出下列命题的真值 3 在一阶逻辑中 将下列命题符号化 1 凡有理数均可表示为分数 解 P x x是有理数 Q x x可表示为分数 在谓词逻辑中基本语句的形式化 1 D中所有x都有性质F 2 D中有的x具有性质F 3 D中所有x而言 如果x有性质F 则x就有性质G 4 D中有的x具有性质F 又有性质G 设D是论域 5 对于D中的所有x和y而言 若x有性质F y有性质G 则x与y有关系H 6 对于D中的所有x而言 若x有性质F 就存在y有性质G 并且x与y有关系H 7 存在D中的x有性质F 并且对D中所有y而言 如果y有性质G 则x与y就有关系H 8 D中存在着x与y x有性质F y有性质G 并且x与y有关系H 解 自由变元z 约束为元 x y 第一个的作用域为 2 第二个的作用域为第二个P x 第二个的作用域的作用域为Q y 3 解 自由变元z 约束为元 x y 的作用域为R y 解 无自由变元 约束为元 x y 4 的作用域为 的作用域为 H x y 5 解 自由变元 y与G x y 中的x 约束变元 F x 中的x 解 自由变元 Z与H x y 中的y 约束变元 x y 的作用域 F x 6 和 的作用域 的作用域 5 设谓词公式 判定以下改名是否正确 1 2 3 4 5 错误 正确 错误 错误 错误 6 1 解 真 2 解 假 3 解 真 4 解 真 7 判断下列公式的恒真性和恒假性 1 解 恒真 2 解 恒真 3 解 恒真 4 解 恒假 5 解 满足 8 1 2 证明 1 证明 2 9 证 设D是论域 I是G x y 的一个解释 a 若 1 在I下的为真 则在I下 对任意的 即 是真命题 b 若 在I下的为假 则在I下 必存在 使得G x0 y 或G x y0 为假 于是 此xo或yo亦弄假 证 设D是论域 I是G x y 的一个解释 2 a 若 也是真命题 反之亦然 在I下的为真 则在I下 有 使G x0 y0 为真命题 于是 3 解 4 解 11 给出下面公式的skolem范式 1 所求为 解 原式 2 即为所求 3 解 12 假设是公式G的前束范式 其中M x y 是仅仅包含变量x y的母式 设f是不出现在M x y 中的函数符号 证明 G恒真当且仅当恒真 证 设恒真 若不真 则存在一个解释I 使得对任意的 论域 为假 于是 G在I下也为假 此为矛盾 反之 设恒真 若不是恒真 则存在一个解释I 使得对任意 存在 使为假 由于f是不出现在中的函数符号 故可定义函数 使得 于是 在I 下为假 矛盾 故结论成立 证明 1 2 3 4 5 6 前提引入 13 证明 假言推理 2 4 UG 5 US 1 前提引入 US 3 前提 结论 证明 1 2 等值替换 1 3 4 5 6 前提引入 14 构造下面推理的证明 US 5 假言推理 2 4 等值替换 2 US 3 解 4 错误 F y 中的变元y与 2 中的变元重名 15 指出下面两个推理的错误 1 6 5 G y 假言推理 2 4 3 2 UG 5 前提引入 US 1 前提引入 4 F y ES 3 解 3 错误 在 2 中还有自由变元y 1 5 3 2 EG 4 前提引入 US 1 4 ES 2 US 3 在推理过程中 指出下面各证明序列中的错误 F c G c 1 F x 2 F y G y F c G c 3 前提引入 EG规则 前提引入 ES规则 前提引入 ES规则 4 F c G b 5 F c G c 前提引入 前提引入 UG规则 EG规则 16 每个学术会的成员都是知识分子并且是专家 有些成员是青年人 证明 有的成员是青年专家 解 P x x是学术会的成员 E x x是专家 G x x是知识分子 Y x x是青年人 前提 结论 前提 结论 1 前提引入 2 US 1 3 4 5 P c 6 7 E c 8 Y c 9 10 前提引入 ES 3 化简 4 假言推理 2 5 化简 6 化简 4 合并 7 8 EG 9