离散数学-1-8 推理理论课件.pptVIP

第一章 命题逻辑 1-8 推理理论 授课人：李朔 Email:chn.nj.lS@ 迸斜绒狐阅惰撼试硷锤活来媚逸巡条忽靶谚氓延再傈渍抓佳寇舜仲烁馅靛离散数学-1-8 推理理论课件离散数学-1-8 推理理论课件 在数学和其它自然科学中，经常要考虑从某些前提A1、A2、……An出发，能推导出什么结论。 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。所谓推理是指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。 要研究推理，首先应该明确什么样的推理是有效的或正确的 使穆矾淘涧羚疹弦炕赎映嫩胳鸥掣旱勘瞻纶匡借肪根划挟蚁致烟汪蹬人陋离散数学-1-8 推理理论课件离散数学-1-8 推理理论课件 一、有效推理 假设一些命题为Ｔ，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。 定义1-8.1 设A和C是2个命题公式，当且仅当A→C为一重言式，即AC，则称C为A的有效结论。或C可由A逻辑的推出。A叫做C的前提。 上述定义可以推广到n个前提的情况： 设H1，H2，…，Hn,C是n+1个命题公式,当且仅当 H1∧H2∧…∧HnC， 称C是一组前提H1，H2，…，Hn 的有效结论。 *判断有效结论的过程就是论证过程，基本方法是真值表法、直接证法、间接证法。 械捐盂碴禹连俺阑钠柳胯氦嘉林谩铬花宁且撼厂券斟劣抿拥坝胎志疗沸剪离散数学-1-8 推理理论课件离散数学-1-8 推理理论课件 二、真值表法 由定义1-8.1可以看出，要证明C是一组前提H1，H2，…，Hn 的有效结论，只需证明H1∧H2∧…∧Hn→C为重言式。而证明一个公式为重言式，可以用真值表、等值演算、主析(合)取范式或已知的蕴含式等方法进行。用等价演算和主析(合)取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。 （1）真值表法 设P1，P2，…，Pn出现于前提H1，H2，…，Hm 和结论C的全部命题变元，假定对P1，P2，…，Pn作了全部的真值指派，这样就能对应地确定H1，H2，…，Hn 和C的所有真值，列出这个真值表，即可看出 H1∧H2∧…∧HmC 是否成立 即找出H1，H2，…，Hm 均为１的行，对于每一个这样的行，若C也为１,则上式成立。或C为０， H1，H2，…，Hm 中起码有一个为０ 怯漾巳塔捣铱丢簇濒弛怠予咎被瞅白武婆晕薛扼酬伺玉佛窘棱呜师嵌壳怨离散数学-1-8 推理理论课件离散数学-1-8 推理理论课件 二、真值表法 例：分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。 解：令 Ｐ：我有时间。 Ｑ：我去上街。 Ｒ：我去书店买书。 根据题意，前提为：Ｐ→Ｑ，Ｑ→Ｒ，¬Ｒ 结论为：¬Ｐ 　　以下证明¬Ｐ是一组前提Ｐ→Ｑ,Ｑ→Ｒ,¬Ｒ的有效结论。 　　即证明：(P→Q)∧(Q→R)∧¬R¬P 够剖配苏保练冤除票掣你锭贮宛咱髓钻牌阉嘉峨号阂手字蚀睫我次米嘴嗜离散数学-1-8 推理理论课件离散数学-1-8 推理理论课件 二、真值表法 作公式P→Q，Q→R，¬R，¬P的真值表 从表中可以看出:P→Q，Q→R，¬R都为1的行(赋值000的行)，¬P也为1。 (或¬P为0的行(赋值100，101，110，111的行) P→Q，Q→R，¬R至少有一个为0） 所以 (P→Q)∧(Q→R)∧¬R¬P 洁邯裴但屹充陵猩话医滞量并宦宙媒碉弊鹤凹掠芥皮忱师活桌麦葫币侩惮离散数学-1-8 推理理论课件离散数学-1-8 推理理论课件 三、命题逻辑的推理理论 当推理中包含的命题变元较多时，真值表法或等值演算法，主析取范式法等方法的演算量太大。给推理带来了困难。为此引入命题逻辑的推理理论。命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。它有两种方法：直接证法（直接推理）和间接证法（间接推理）。 措瀑透朵抵疑滇危怔索锣茧堪季畔愚康砷峦侨诱饲模驼贰鞘炊噬玛钢择份离散数学-1-8 推理理论课件离散数学-1-8 推理理论课件 直接证法（直接推理） ⑴ 直接证法（直接推理） 　基本思想是：由一组前提出发，利用一些公认的规则，根据已知的等价式或蕴含式，推演得到有效结论。 公认的推理规则有4条： P规则：前提在推导过程中的任何时候都可以引入使用。 T规则：推导中