推理规则与证明方法.ppt

推理是由一个或几个判断得出另一个新的判断的思维 形式(思维过程)。其中已知的判断前提 新的判断结论 列出前提H1,H2, ,Hm与结论C论证 逻辑的主要功能是提供推理的规则或论证的原理。从一 组给定的前提出发，根据推理规则得到的结论称为有效 结论，论证才是有效的。 建立逻辑学的主要目的在于探索出这一套完整的规则， 按照这些规则，就可以确定任何特定论证是否有效。,1.5 推理规则与证明方法,设H1,H2,Hm()和都是命题公式。 若( H1H2 Hm ) 为永真式， 即 H1H2 Hm ， 称由前提H1,H2, ,Hm推出结论C的推理正确(有效)。 称为前提H1,H2, ,Hm的有效结论或逻辑结果。 H1H2 Hm 称为 由前提H1,H2, ,Hm推出结论C的推理的形式结构。,一、推理的基本概念,例1-5-1 1 如果天下雨，小王就不去跑步。 今天天下雨，所以小王没去跑步。 解： 设 P：天下雨。 Q：小王去跑步。 前提：PQ， P 结论： Q 推理的形式结构为：(PQ)P Q 2 如果我上街，我一定去新华书店。 我没上街，所以我没去新华书店。 解： 设P：我上街。 Q：我去新华书店。 前提：PQ， P 结论： Q 推理的形式结构为： (PQ)P Q,推理的符号化实例,根据定义：由前提H1,H2, ,Hm推结论C的推理正确(有效)即： ( H1H2 Hm ) 为永真式， 即 H1H2 Hm 可知，判断推理是否正确的方法就是判断永真式 或永真蕴含式的方法。 基本方法有： 1 真值表法 2 等值演算法 3 主析取范式法 4 指派分析法(永真蕴含式),二、基于定义的推理,例1-5-2 判断下列推理是否正确： 如果天下雨，小王就不去跑步。 今天天下雨，所以小王没去跑步。 解：设 P：天下雨。 Q：小王去跑步。 前提：PQ，P 结论：Q 推理的形式结构为：(PQ)P Q 判断(PQ)P) Q (*) 是否为永真式 或 (PQ)P Q 是否成立。,步骤： 先将命题符号化 然后写出前提、结论和推理的形式结构 最后进行判断,1 真值表法,真值表的最后一列全为1，因而(*)是永真式。 所以推理正确。,真值表技术：给定一个前提集合和一个结论，用构成真值表 的方法，在有限步骤内判定给定前提是否能推 导出该结论的这种方法，称为真值表技术 。,(PQ)P) Q (PQ)P) Q (PQ)P)Q (PPQ)(QPQ) TT T 因而(P Q)P) Q (*)是永真式，推理正确。,2 等值演算法,(PQ)P) Q (PQ)P) Q (PQ) P Q (PQ)(P(QQ) )( (PP)Q) (PQ)(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) (0,1,2,3 ) 因而 (*) 是永真式，推理正确。,3 主析取范式法,即要判断(PQ)P Q 证明：假设前件(PQ)P 为真， 则P为真，且(PQ)为真，所以Q 为真。 故(PQ)P Q成立， 推理正确。,4 指派分析法 (永真蕴含式),基于定义进行推理的不足： 1 如果命题公式的变元较多，以上四种方法都不方便 。 (n个变元， 2n种指派) 2 与自然生活和传统数学中的推理形式无相同之处。 3 过于机械，对培养推理能力和推理技巧毫无帮助。,形式证明：对由前提H1，H2， ，Hm推结论C的推理， 构造一个描述推理过程的命题公式序列，其中 每个命题公式或者是已知的前提，或者是由某 些前提应用公认的推理规则所得到的结论，序 列中最后一个命题公式是所要求的结论。 这样的命题公式序列称为形式证明。 形式证明的格式：形式证明是按行进行的，而且每行只能 写一个命题公式。一般为： 标号部分 命题公式 说明部分,三、基于规则的推理,推理过程中使用的构造公式序列的规则： 规则P（前提引入规则）：在推导的任何步骤上，都可以引入前提。 规则T（结论引入规则）：在推导过程中，如果前面有一个或多个命题公式永真蕴含命题公式 S，那么就可以把公式 S 引进推导过程中。 代入规则：在推导的任何步骤上，永真式中的任一命题变元都可以用任一命题公式代入，代入后得到的仍是永真式。 置换规则：在推导的任何步骤上，命题公式中的任何子公式都可以用与之等值的命题公式置换。 常用的推理公式： 在表1.2-2中列出的永真蕴含式。 在表1.2-1中列出的逻辑等价式。,常用的推理规则,1直接证明法 由已知的前提H1,H2, Hm出发，利用一些公认的推理规则，根据已知的逻辑等价式和永真蕴含式，推导出有效结论C。,证明方法,推理：H1H2 Hm C,2间接证明法 将已知的前提和结论进行适当的改造， 转化为对新的前提和结论进行推理证明。 常用的技巧有：附加前提证明法和反证法。,例1-5-3 检验下列推理的有效性。 如果马会飞或羊吃草，则母鸡就会是飞鸟； 如果母鸡是飞鸟，那么煮熟的鸭子还会跑； 煮熟的鸭子不会跑，所以羊不吃草。 解：设P：马会飞。 Q：羊吃草。 R：母鸡是飞鸟。S：煮熟的鸭子会跑 则前提为：(PQ)R ， RS ，S 结论为：Q 推理的形式结构为： (PQ)R)(RS)(S) Q,1. 直接证明法,证明： (1) S 规则P (2) RS 规则P (3) R (1)(2) 拒取式，规则T (4) (PQ)R 规则P (5) (PQ) (3)(4) 拒取式，规则T (6) PQ (5) 德摩根律，替换规则，规则T (7) Q (6) 简化式，规则T 所以推理正确 Q：羊不吃草有效结论，但不是正确的结论。 P：马不会飞有效结论，而且是正确的结论。,有效是指结论的推出是合乎推理规则的，并不在于 结论是否真实。,第一列是步骤列, 将各次操作按先后排序; 第二列是断言列或命题公式列, 内容可以是前提, 中间结论或最终结论; 第三列是注释列或根据列,表明所引用的推理规则及与之有关的行的编号. 第三列是形式推理的特点与优点.,例1-5-4 证明 RS是前提CD，CR，DS的 有效结论，即证明： (CD)(CR)(DS)(RS)。 证明: (1) CD 规则P (2) CD (1)蕴含等价式，规则T (3) DS 规则P (4) CS (2)(3)前提三段论，规则T (5) CR 规则P (6) RC (5) 逆反律，规则T (7) RS (4)(6)前提三段论，规则T (8) RS (7)蕴含等价式，规则T,2. 间接证明法,附加前提法（CP规则） 当待证的有效结论是一个PQ 类型的条件命题时， 可以将有效结论中的前提P 单独提出来加到前提中去， 然后证明剩下的后件Q 是附加了前提之后的新的一组前提 的有效结论。这种附加前提的证明方法称为 CP规则。 即：H1H2 Hm (PQ)的充要条件是 H1H2 Hm PQ。,证明： 要证 H1H2 Hm (PQ) 即证(H1H2 Hm) (PQ) T 同样，要证 H1H2 HmP Q 即证(H1H2 HmP)Q T 而( H1H2 Hm )(PQ) (H1H2 Hm P)Q （输出律）,例1-5-5 证明：RP是前提PQ，QR的有效结论。 分析：要证明：(PQ)(QR) RP 采用附加前提证明法，转化为证明： (PQ)(QR)R P 证明： (1) R 规则P(附加前提) (2) QR 规则P (3) Q (1),(2)拒取式，规则T (4) PQ 规则P (5) P (3),(4)拒取式，规则T (6) RP CP规则 由CP 规则，得： (PQ)(QR) RP,课内练习 1-5-1 证明推理：P(QR)，Q(RS) P(QS) 分析：由CP规则 P(QR)，Q(RS) P(QS) 等价于 P(QR)，Q(RS)，P QS 再由CP规则，等价于 P(QR)，Q(RS)，P，Q S,证明： (1) P 规则P(附加前提) (2) P(QR) 规则P (3) QR (1),(2)假言推理，规则T (4) Q 规则P(附加前提) (5) R (3),(4)假言推理，规则T (6) Q(RS) 规则P (7) RS (4) (6）假言推理，规则T (8) S (5),(7)假言推理，规则T (9) P(QS) CP规则 由CP 规则，有： P(QR)，Q(RS) P(QS),例1-5-6 采用附加前提法证明例1-5-4 ： (CD)(CR)(DS)(RS)。 分析：由PQ PQ， 得 RS RS 由CP规则，等价于要证明 CD，CR，DS，R S 证明: (1) R 规则P(附加前提) (2) CR 规则P (3) C (1),(2)拒取式，规则T (4) CD 规则P (5) D (3),(4)析取三段论，规则T (6) DS 规则P (7) S (5)，(6)前提三段论，规则T (8) RS CP规则 (9) RS (8)蕴含等价式，规则T,CP规则的适用范围： 待证的有效结论是PQ 或 PQ 型的命题。,(2)反证法(归谬法) 将结论C的否定C 做为假设前提推出矛盾 的证明方法称为反证法或归谬法。 即：H1H2 Hm C 的充要条件是 H1H2 Hm C F。,证明： 要证 H1H2 Hm C 即证(H1H2 Hm)C T 同样，要证 H1H2 HmC F 即证(H1H2 HmC)F T 而(H1H2 Hm)C (H1H2 Hm)C (H1H2 HmC) 上式左边是永真式， 当且仅当H1H2 HmC是永假式。,例1-5-7 证明 (PQ)是PQ 的有效结论。 即证： PQ (PQ) 分析：用反证法，将 (PQ)作为假设前提去证: PQ (PQ) F 证明： (1) (PQ) 规则P（假设前提） (2) PQ (1) 双重否定律，规则T (3) P (2)简化式,，规则T (4) PQ 规则P (5) P (4)简化式，规则T (6) PP （矛盾） (3)(5)合取式,，规则T 由反证法得：PQ (PQ),设P1,P2,Pn为命题公式H1,H2,Hm中的命题变元。 相容：如果对于P1,P2,Pn的某一真值指派， H1H2Hm 的真值为， 则称命题公式H1, H2,Hm