命题逻辑的推理理论ppt课件

第三章命题逻辑的推理理论 推理的形式结构自然推理系统P 关于 推理 推理 指从前提出发推出结论的思维过程 前提是已知命题公式集合 结论是从前提出发应用推理规则推出的命题公式 数理逻辑的主要任务是用数学的方法来研究数学中的推理 推理的形式结构 问题的引入 推理举例 1 正项级数收敛当且仅当部分和上有界 2 若A C B D 则A B且C D 推理 从前提出发推出结论的思维过程上面 1 是正确的推理 而 2 是错误的推理 证明 描述推理正确或错误的过程 推理的形式结构 定义设A1 A2 Ak B都是命题公式 若对于A1 A2 Ak B中出现的命题变项的任意一组赋值 A1 A2 Ak均为假 或当A1 A2 Ak为真时 B也为真 则称由A1 A2 Ak推B的推理正确 并称B是有效的结论 否则推理不正确 错误 说明 1 由前提A1 A2 Ak推结论B的推理是否正确与诸前提的排列次序无关 因而前提中的公式不一定是序列 而是一个有限公式集合 记为 可将由 推B的推理记为 B 若推理是正确的 则记为 B 否则记为 B 这里可以称 B和 A1 A2 Ak B为推理的形式结构 说明 2 设A1 A2 Ak B中共出现n个命题变项 对于任一组赋值a1a2 an ai 0或1 i 1 2 n 前提和结论的取值情况有以下四种 1 A1 A2 Ak为0 B为0 2 A1 A2 Ak为0 B为1 3 A1 A2 Ak为1 B为0 4 A1 A2 Ak为1 B为1 由定义可知 只要不出现 3 中的情况 推理就是正确的 因而判断推理正确与否 就是判断是否会出现 3 中的情况 例3 1判断下列推理是否正确 1 p p q q 2 p q p q解 只要写出前提的合取式与结论的真值表 看是否出现前提为真 而结论为假的情况即可 由下面真值表可看出 1 推理正确 2 推理不正确 pqp p q q0000010110001111pqp q p q0000010110101111 定理3 1命题公式A1 A2 Ak推B的推理正确当且仅当 A1 A2 Ak B为重言式 证明 必要性若命题公式A1 A2 Ak推B的推理正确 则不会出现A1 A2 Ak为真 而B为假的情况 因而在任何赋值下 蕴涵式 A1 A2 Ak B均为真 故为重言式 证明 充分性若蕴涵式 A1 A2 Ak B为重言式 则对于任何赋值此重言式均为真 因而不会出现前件为真后件为假的情况 即在任何赋值下 或者A1 A2 Ak为假 或者A1 A2 Ak和B同时为真 这正符合定义3 1中推理正确的定义 分析 由定理3 1可知 可以将由前提A1 A2 Ak推B的推理的形式结构 A1 A2 Ak B转换成蕴涵式 A1 A2 Ak B推理前提的合取式成了蕴涵式的前件 结论成了蕴涵式的后件 并将推理正确 A1 A2 Ak B转换成A1 A2 Ak B其中 是一种元语言符号 表示蕴涵式为重言式 判断推理是否正确的方法 真值表法等值演算法主析取范式法构造证明法说明 当命题变项比较少时 用前3个方法比较方便 此时采用形式结构 A1 A2 Ak B 而在构造证明时 采用 前提 A1 A2 Ak 结论 B 例3 2判断下面推理是否正确 解上述类型的推理问题 首先应将简单命题符号化 然后分别写出前提 结论 推理的形式结构 接着进行判断 1 设p a能被4整除q a能被2整除前提 p q p结论 q推理的形式结构 p q p q可知此推理正确 即 p q p q 1 若a能被4整除 则a能被2整除 a能被4整除 所以a能被2整除 2 若a能被4整除 则a能被2整除 a能被2整除 所以a能被4整除 2 设p a能被4整除q a能被2整除前提 p q q结论 p推理的形式结构 p q q p可知上式不为重言式 所以此推理不正确 即 p q p q 3 下午马芳或去看电影或去游泳 她没去看电影 所以 她去游泳了 3 设p 马芳下午去看电影q 马芳下午去游泳前提 p q p 结论 q推理的形式结构 p q p q用等值演算法可知上市为重言式 所以 推理正确 4 若下午气温超过30度 则王小燕必去游泳 若她去游泳 她就不去看电影 所以 若王小燕没去看电影 下午气温必超过了30度 4 设p 下午气温超过30度q 王小燕去游泳r 王小燕去看电影前提 p q q r结论 r p推理的形式结构 p q q r r p 用主析取范式法可知上式不是重言式 所以推理不正确 重要的推理定律 重言蕴涵式 A A B 附加律 A B A化简律 A B A B假言推理 A B B A拒取式 A B B A析取三段论 A B B C A C 假言三段论 A B B C A C 等价三段论 A B C D A C B D 构造性二难 推理定律 续 A B A B A A B构造性二难 特殊形式 A B C D B D A C 破坏性二难 说明 1 A B C为元语言符号 代表任意的命题公式 2 若某推理符合某条推理定律 则它自然是正确的 3 A B产生两条推理定律 A B B A 实例 例判断下面推理是否正确 1 若今天是1号 则明天是5号 今天是1号 所以明天是5号 解设p 今天是1号 q 明天是5号 证明的形式结构为 p q p q证明 用等值演算法 p q p q p q p q p q q 1得证推理正确 实例 续 2 若今天是1号 则明天是5号 明天是5号 所以今天是1号 解设p 今天是1号 q 明天是5号 证明的形式结构为 p q q p证明 用主析取范式法 p q q p p q q p p q q p q p p q p q p q p q m0 m2 m3结果不含m1 故01是成假赋值 所以推理不正确 重要的推理定律 重言蕴涵式 A A B 附加律 A B A化简律 A B A B假言推理 A B B A拒取式 A B B A析取三段论 A B B C A C 假言三段论 A B B C A C 等价三段论 A B C D A C B D 构造性二难 推理定律 续 A B A B A A B构造性二难 特殊形式 A B C D B D A C 破坏性二难 说明 A B C为元语言符号若某推理符合某条推理定律 则它自然是正确的A B产生两条推理定律 A B B A 3 2自然推理系统P 判断推理是否正确的三种常用方法 1 真值表技术2 演绎法3 间接证明方法当命题变项较多时 以上三种方法的演算量太大 此时可考虑推理证明的方法 而要构造严谨的证明必须要在形式系统中进行 形式系统的定义 一个形式系统I由下面四个部分组成 1 非空的字母表 记做A I 2 A I 中符号构造的合式公式集 记做E I 3 E I 中一些特殊的公式组成的公理集 记做Ax I 4 推理规则集 记做R I 可以将I记为4元组 其中是I的形式语言系统 而为I的形式演算系统 形式系统的分类 1 自然推理系统它的特点是从任意给定的前提出发 应用系统中的推理规则进行推理演算 得到的最后命题公式是推理的结论 可能是重言式 也可能不是 2 公理推理系统它的特点是只能从若干条给定的公理出发 应用系统中的推理规则进行演算 得到的是系统中的定理 是重言式 定义3 3自然推理系统P定义如下 1 字母表 1 命题变项符号 p q r 2 联结词符号 3 括号与逗号 2 合式公式 参见定义1 6P10 3 推理规则 推理规则 1 前提引入规则 在证明的任何步骤上都可以引入前提 2 结论引入规则 在证明的任何步骤上所得到的结论都可以做为后续证明的前提 3 置换规则 在证明的任何步骤上所得到的结论都可以作为后续证明的前提 推理规则 续 4 假言推理规则A BA B 5 附加规则A A B 推理规则 续 构造证明 直接证明法 例3 3在自然推理系统P中构造下面推理的证明 1 前提 p q q r p s s结论 r p q 2 前提 p q r q r s结论 p s 1 前提 p q q r p s s结论 r p q 证明 1 p s前提引入 2 s前提引入 3 p 1 2 拒取式 4 p q前提引入 5 q 3 4 析取三段论 6 q r前提引入 7 r 5 6 假言推理 8 r p q 7 4 合取 2 前提 p q r q r s结论 p s 证明 1 p q前提引入 2 p q 1 置换 3 r q前提引入 4 q r 3 置换 5 p r 2 4 假言三段论 6 r s前提引入 7 p s 5 6 假言三段论 构造证明 直接证明法 例3 4在自然推理系统P中构造下面推理的证明 若a是实数 则它不是无理数就是有理数 若a不能表示成分数 则它不是有理数 a是实数且它不能表示成分数 所以a是无理数 解 首先将简单命题符号化 p a是实数 q a是有理数 r a是无理数 S a能表示成分数 则可知 前提 p q r s q p s结论 r 前提 p q r s q p s结论 r 证明 1 p s前提引入 2 p 1 化简 3 s 1 化简 4 p q r 前提引入 5 q r 2 4 假言推理 6 s q前提引入 7 q 3 6 假言推理 8 r 5 7 析取三段论 构造证明 附加前提证明法 欲证明前提 A1 A2 Ak结论 C B等价地证明前提 A1 A2 Ak C结论 B理由 A1 A2 Ak C B A1 A2 Ak C B A1 A2 Ak C B A1 A2 Ak C B 将C称为附加前提 附加前提证明法 例3 5在自然推理系统P中构造下面推理的证明 如果小张和小王去看电影 则小李也去看电影 小赵不去看电影或小张去看电影 小王去看电影 所以 当小赵去看电影时 小李也去 解 将简单命题符号化 p 小张去看电影q 小王去看电影r 小李去看电影s 小赵去看电影 前提 p q r s p q结论 s r 证明 1 s附加前提引入 2 s p前提引入 3 p 1 2 析取三段论 4 p q r前提引入 5 q前提引入 6 p q 3 5 合取 7 r 4 6 假言推理 附加前提证明法 续 例构造下面推理的证明 2是素数或合数 若2是素数 则是无理数 若是无理数 则4不是素数 所以 如果4是素数 则2是合数 用附加前提证明法构造证明解设p 2是素数 q 2是合数 r 是无理数 s 4是素数形式结构前提 p q p r r s结论 s q 附加前提证明法 续 证明 s附加前提引入 p r前提引入 r s前提引入 p s 假言三段论 p 拒取式 p q前提引入 q 析取三段论请用直接证明法证明之 构造证明 归谬法 反证法 欲证明前提 A1 A2 Ak结论 B将 B加入前提 若推出矛盾 则得证推理正确 理由 A1 A2 Ak B A1 A2 Ak B A1 A2 Ak B 括号内部为矛盾式当且仅当 A1 A2 Ak B 为重言式 归谬法 续 例3 6在自然推理系统p中构造下面推理的证明 如果小张守第一垒并且小李向B队投球 则A队将取胜 或者A队未取胜 或者A队成为联赛第一名 A队没有成为联赛的第一名 小张守第一垒 因此 小李没有向B队投球 解 先将简单命题符号化p 小张守第一垒q 小李向B队投球r A队取胜s A队成为联赛第一名 前提 p q r r s s p结论 q 证明 1 q结论的否定引入 2 r s前提引入 3 s前提引入 4 r 2 3 析取三段论 5 p q r前提引入 6 p q 4 5 拒