天大《离散数学(2)-1》学习笔记十.pdf

离散数学 2 1 学习笔记十 主 题 主 题 离散数学 2 1 学习笔记 内 容 内 容 离散数学 2 1 学习笔记十 谓词逻辑的推理演算 离散数学 2 1 学习笔记十 谓词逻辑的推理演算 教学目的 要求 教学目的 要求 掌握 掌握 谓词逻辑的推理定律 推理规则 推理方法 理解 理解 U I U G E I E G 规则的不同 了解 了解 谓词逻辑是命题逻辑推理的异同 教学内容 基本内容 教学内容 基本内容 谓词逻辑的推理定律 推理规则 推理方法 重点 重点 谓词逻辑的推理方法 难点 难点 对谓词公式的推理 基本要求 1 了解谓词逻辑是命题逻辑推理的异同 2 熟练运用谓词逻辑的推理定律 3 正确使用 U I U G E I E G 规则 给正确的推理给出证明 2 4 谓词逻辑的推理演算2 4 谓词逻辑的推理演算 谓词逻辑是命题逻辑的进一步深化和发展 因此命题逻辑的推理理论在谓词 逻辑仍然有效 只不过这时涉及的公式不是命题公式而是谓词公式 2 4 1 推理定律 2 4 1 推理定律 下面列出一些常用的推理定律 同命题逻辑一样 在后面的推理演算中以大 写字母 I 加以引用 1 由命题逻辑推理定律推广而来的谓词逻辑推理定律 1 由命题逻辑推理定律推广而来的谓词逻辑推理定律 利用代入定理将命题逻辑中的推理定律推广而得到谓词逻辑中的推理定律 如在命题逻辑中有公式 可推广而得 x A x y B y x A x x A x x A x y B y 等等 2 由基本等值式生成的推理定律 2 由基本等值式生成的推理定律 2 3 节给出的等值式中的每个等值式可生成两个推理定律 例如 x A x x A x x A x x A x 和 x A x x A x x A x x A x 等等 3 一些特有的重要推理定律 3 一些特有的重要推理定律 1 x A x x B x x A x B x 2 x A x B x x A x x B x 3 x A x B x x A x x B x 4 x A x B x x A x x B x 等等 2 4 2 推理规则 2 4 2 推理规则 命题逻辑中所使用的推理规则 都可以应用于谓词逻辑的推理中 除此以外 由于谓词逻辑中引进了个体 谓词和量词等 因此又增加了一些推理规则 下面 离散数学 2 1 学习笔记十 介绍几个与量词有关的推理规则 1 全称量词消去规则 U S 全称量词消去规则 U S 1 x A x A y 或 2 x A x A c 两式成立的条件是 x 是 A x 的自由变元 在 1 中 y 为不在 A x 中约束出现的变元 y 可以在 A x 中自由出现 也可在证明序列中前面的公式中出现 在 2 中 c 为任意的个体常元 可以是证明序列中前面公式所指定的 个体常元 2 全称量词引入规则 U G 2 全称量词引入规则 U G A y x A x 该式成立的条件是 y 在 A y 中自由出现 且 y 取任何值时 A 均为真 替换 y 的 x 要选择在 A y 中不出现的变元符号 3 存在量词消去规则 E S 3 存在量词消去规则 E S x A x A c 该式成立的条件是 c 是使 A 为真特定的个体常元 c 不能在前面的公式序列中出现 c 不曾在 A x 中出现 A x 中除 x 外还有其它自由出现的个体变元时 不能用此规则 4 4 存在量词引入规则 E G 存在量词引入规则 E G A c x A x 该式成立的条件是 c 是特定的个体常元 替换 c 的 x 要选择在 A c 中没有出现过的变元符号 需要注意的是 以上四条规则只能对前束范式使用 2 4 3 推理方法2 4 3 推理方法 在谓词逻辑中 常用的推理方法有两种 直接证法和间接证法 其内容与命 题逻辑中的类似 下面分别举例说明 1 直接证法1 直接证法 例 2 1 3例 2 1 3 证明苏格拉底三段论 人都是要死的 苏格拉底是人 所以苏格 拉底是要死的 解解 个体域取全总个体域 令 F x x 是人 G x x 是要死的 a 苏格拉 底 则 前提 x F x G x F a 结论 G a 推理形式 x F x G x F a G a 1 x F x G x P 2 F a G a U S 1 3 F a P 4 G a T I 2 3 例 2 1 4例 2 1 4 指出下列推导中的错误 并加以改正 1 x P x P 2 P c E S 1 3 x Q x P 离散数学 2 1 学习笔记十 4 Q c E S 2 解解 第二次使用存在量词消去规则时 所指定的特定个体应该是证明序列以 前公式中没有出现过的 正确的推理是 1 x P x P 2 P c E S 1 3 x Q x P 4 Q d E S 2 2 间接证法2 间接证法 间接证法主要有两种 反证法和 C P 规则 1 反证法 例 2 1 5例 2 1 5 将下列推理符号化并给出形式证明 晚会上所有人都唱歌或跳舞了 因此或者所有人都唱歌了 或者有些人跳舞 了 个体域为参加晚会的人 解解 设 P x x 唱歌了 Q x x 跳舞了 则 前提 x P x Q x 结论 x P x x Q x 推理形式 x P x Q x x P x x Q x 1 x P x x Q x P 附加 2 x P x x Q x R E 1 3 x P x T I 2 4 P a E S 3 5 x Q x T I 2 6 Q a U S 5 7 x P x Q x P 8 P a Q a U S 7 9 Q a T I 4 8 1 0 Q a Q a T I 6 9 矛盾 因此 假设不成立 原推理形式正确 2 C P 规则 例 2 1 6例 2 1 6 将下列推理符号化并给出形式证明 每一个大学生不是文科生就是理科生 有的大学生是优等生 小张不是文科 生但他是优等生 因此 如果小张是大学生 他就是理科生 解解 个体域取全总个体域 设 P x x 是大学生 Q x x 是文科生 S x x 是理科生 T x x 是优等生 c 小张 则 前提 x P x Q x S x x P x T x Q c T c 结论 P c S c 推理形式 x P x Q x S x x P x T x Q c T c P c