离散数学谓词逻辑推理.ppt

第二章谓词逻辑 第3节一阶逻辑推理理论 推理的定义 称蕴涵式 A1 A2 Ak B为推理的形式结构 A1 A2 Ak为推理的前提 B为推理的结论 若 A1 A2 Ak B为永真式 则称从前提A1 A2 Ak推出结论B的推理正确 或说有效 B是A1 A2 Ak的逻辑结论或称有效结论 否则称推理不正确 若从前提A1 A2 Ak推出结论B的推理正确 则记为 A1 A2 Ak B 推理规则 在证明中常用的推理规则有 1 前提引入规则P 在证明的任何步骤都可以引入已知的前提 2 结论引入规则 在证明的任何步骤都可以引入这次已经得到的结论作为后续证明的前提 3 置换规则E 在证明的任何步骤上 一阶公式中的任何子公式都可用与之等值的公式置换 得到证明的公式序列的另一公式 以及CP规则 和 的合取 永真蕴涵I等 使用一阶逻辑公式进行推理还有其他一些推理规则 这些规则建立在下面一些推理定律上 一阶逻辑的永真蕴涵式 推理定律是一阶逻辑的一些永真蕴涵式 重要的推理定律有 1 附加律 A A B 或称为析取的引入 2 化简律 A B A A B B 或称为合取的消除 3 假言推理 A B A B 或称为分离规则 4 拒取式 A B B A 5 析取三段论 A B B A 6 假言三段论 A B B C A C 或称为传递规则 一阶逻辑的永真蕴涵式 续 7 等价三段论 A B B C A C 8 构造性二难 A B C D A C B D 一阶逻辑中特有的推理定律 1 x A x B x xA x xB x 2 x A x B x xA x xB x 3 x A x B x xA x xB x 4 x A x B x xA x xB x 一阶逻辑中特有的推理规则 1 全称量词消除规则 UI规则 i xA x A y ii xA x A c 成立的条件是 1 x是A x 的自由变元 2 在 i 中 y为不在A x 中约束出现的变元 y可以在A x 中自由出现 也可在证明序列中前面的公式中出现 3 在 ii 中 c是任意的个体常项 可以是证明序列中前面公式所指定的个体常项 举例 全称量词消除规则 指出下列推导中的错误 并加以改正 A 1 x P x Q x 前提 2 P a Q b 全称量词消除规则 解 在使用量词消除规则时 应使用个体替换量词所约束的变元在公式中的所有出现 正确的推理是 1 x P x Q x 前提 2 P a Q a 全称量词消除规则 举例 全称量词消除规则 指出下列推导中的错误 并加以改正 B 1 xP x Q x 前提 2 P y Q y 全称量词消除规则量词 x的辖域为P x 而非P x Q x 所以不能直接使用全称量词消除规则 一阶逻辑中特有的推理规则 续 2 全称量词引入规则 UG规则 A y xA x 成立的条件是 1 y在A y 中自由出现 2 替换y的x要选择在A y 中不出现的变元符号 一阶逻辑中特有的推理规则 续 3 存在量词引入规则 EG规则 A c xA x 成立的条件是 1 c在是特定的个体常项 2 替换c的x要选择在A c 中不出现的变元符号 举例 存在量词引入规则 指出下列推导中的错误 并加以改正 A 1 P a Q b 前提 2 x P x Q x 存在量词引入规则 前提中的个体a和b不同 不能一次同时使用存在量词引入规则 正确的推理可以为 1 P a Q b 前提 2 x P x Q b 存在量词引入规则 3 y x P x Q y 存在量词引入规则 举例 存在量词引入规则 指出下列推导中的错误 并加以改正 B 1 P x Q c 前提 2 x P x Q x 存在量词引入规则 在使用存在量词引入规则时 替换个体c的变元应选择在公式中没有出现的变元符号 正确的推理是 1 P x Q c 前提 2 y P x Q y 存在量词引入规则 一阶逻辑中特有的推理规则 续 4 存在量词消除规则 EI规则 xA x A c 成立的条件是 1 c是特定的个体常项 是使得A c 为真的个体常项 c不能在前面的公式序列中出现 2 c不在A x 中出现 3 A x 中自由出现的个体变元只有x 举例 存在量词消除规则 指出下列推导中的错误 并加以改正 A 1 xP x 前提 2 P c 存在量词消除规则 3 xQ x 前提 4 Q c 存在量词消除规则 A解 第二次使用存在量词消除规则时 所指定的特定个体应该在证明序列以前的公式中不出现 正确的推理是 1 xP x 前提 2 P c 存在量词消除规则 3 xQ x 前提 4 Q d 存在量词消除规则 举例 指出下列推导中的错误 并加以改正 1 x y x y 前提 2 y z y 全称量词消除规则 3 z c 存在量词消除规则 4 x x c 全称量词引入规则 5 c c 全称量词消除规则 由 2 得到 3 不能使用存在量词消除规则 因为 2 中含有除y以外的自由变元z 推理举例1 每一个大学生不是文科生就是理科生 有的大学生是优等生 小张不是文科生但他是优等生 因此 如果小张是大学生 他就是理科生 个体域取全总域 要引入的谓词包括 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 S c 证明 1 x P x Q x S x P规则 2 P c Q c S c 全称量词消除规则 3 P c CP规则 4 Q c S c 2 3 I 5 Q c T c P规则 6 Q c 5 I 7 S c 4 和 6 I 推理举例2 每个旅客或者坐头等舱或者坐二等舱 每个旅客当且仅当他富裕时坐头等舱 有些旅客富裕但并非所有的旅客都富裕 因此 有些旅客坐二等舱 解 P x x是旅客 Q x x坐头等舱 R x x坐二等舱 S x x是富裕的 前提 x P x Q x R x x P x Q x S x x P x S x x P x S x 结论 x P x R x 前提 x P x Q x R x x P x Q x S x x P x S x x P x S x 结论 x P x R x 证明 1 x P x S x P规则 2 x P x S x 1 E 3 P c S c 全称量词消除规则 4 P c 3 I 5 S c 3 I 6 x P x Q x R x P规则 7 P c Q c R c 6 全称量词消除规则 使用 3 中个体c 8 Q c R c 4 7 I 9 x P x Q x S x P规则 10 P c Q c S c 全称量词消除规则 使用 3 中个体c 11 Q c S c 4 11 I 12 Q c S c 11 I 13 Q c 12 5 I 14 R c 13 8 I 15 P c R c 4 和 14 的合取 16 x P x R x 15 存在量词的引入