推理规则与证明方法学习教案.pptx

《推理规则与证明方法学习教案.pptx》由会员分享，可在线阅读，更多相关《推理规则与证明方法学习教案.pptx（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、推理推理(tul)规则与证明方法规则与证明方法第一页，共24页。设设H1,H2,Hm(H1,H2,Hm()和都是命题公式。和都是命题公式。若若(H1H2 Hm)(H1H2 Hm)为永真式，为永真式，即即 H1H2 Hm H1H2 Hm，称由前提称由前提(qint)H1,H2,Hm(qint)H1,H2,Hm推出结论推出结论C C的推理正确的推理正确(有效有效)。称为前提称为前提(qint)H1,H2,Hm(qint)H1,H2,Hm的有效结论或逻辑结果。的有效结论或逻辑结果。H1H2 Hm H1H2 Hm 称为称为 由前提由前提(qint)H1,H2,Hm(qint)H1,H2,Hm推出结论推

2、出结论C C的推理的形式结的推理的形式结构。构。一、推理(tul)的基本概念第1页/共24页第二页，共24页。例例1-5-1 1-5-1 1 1 如果天下雨，小王就不去跑步。如果天下雨，小王就不去跑步。今天天下雨，所以小王没去跑步。今天天下雨，所以小王没去跑步。解：解：设设 P P：天下雨。：天下雨。Q Q：小王去跑步。：小王去跑步。前提：前提：PPQ Q，P P 结论：结论：Q Q 推理的形式结构为：推理的形式结构为：(P(PQ)P Q)P Q Q2 2 如果我上街如果我上街(shn ji)(shn ji)，我一定去新华书店。，我一定去新华书店。我没上街我没上街(shn ji)(shn ji

3、)，所以我没去新华书店。，所以我没去新华书店。解：解：设设P P：我上街：我上街(shn ji)(shn ji)。Q Q：我去新华书店。：我去新华书店。前提：前提：PQPQ，P P 结论：结论：Q Q 推理的形式结构为：推理的形式结构为：(PQ)(PQ)P P Q Q推理(tul)的符号化实例第2页/共24页第三页，共24页。根据定义：由前提根据定义：由前提H1,H2,HmH1,H2,Hm推结论推结论C C的推理正确的推理正确(有效有效)即：即：(H1H2 Hm)(H1H2 Hm)为永真式，为永真式，即即 H1H2 Hm H1H2 Hm 可知，判断可知，判断(pndun)(pndun)推理是否

4、正确的方法就是判断推理是否正确的方法就是判断(pndun)(pndun)永永真式真式 或永真蕴含式的方法。或永真蕴含式的方法。基本方法有：基本方法有：1 1 真值表法真值表法2 2 等值演算法等值演算法3 3 主析取范式法主析取范式法4 4 指派分析法指派分析法(永真蕴含式永真蕴含式)二、基于(jy)定义的推理第3页/共24页第四页，共24页。例例例例1-5-2 1-5-2 1-5-2 1-5-2 判断下列推理是否正确判断下列推理是否正确判断下列推理是否正确判断下列推理是否正确(zhngqu)(zhngqu)(zhngqu)(zhngqu)：如果天下雨，小王就不去跑步。如果天下雨，小王就不去跑

5、步。如果天下雨，小王就不去跑步。如果天下雨，小王就不去跑步。今天天下雨，所以小王没去跑步。今天天下雨，所以小王没去跑步。今天天下雨，所以小王没去跑步。今天天下雨，所以小王没去跑步。解：设解：设解：设解：设 P P P P：天下雨。：天下雨。：天下雨。：天下雨。Q Q Q Q：小王去跑步。：小王去跑步。：小王去跑步。：小王去跑步。前提：前提：前提：前提：PPPPQ Q Q Q，P P P P 结论：结论：结论：结论：Q Q Q Q 推理的形式结构为：推理的形式结构为：推理的形式结构为：推理的形式结构为：(P(P(P(PQ)P Q)P Q)P Q)P Q Q Q Q 判断判断判断判断(P(P(P(

6、PQ)P)Q)P)Q)P)Q)P)Q(*)Q(*)Q(*)Q(*)是否为永真式是否为永真式是否为永真式是否为永真式 或或或或(P(P(P(PQ)PQ)PQ)PQ)P Q Q Q Q 是否成立。是否成立。是否成立。是否成立。步骤(bzhu)：先将命题符号化然后写出前提、结论和推理的形式结构最后进行判断第4页/共24页第五页，共24页。1 真值表法 真值表的最后一列全为1，因而(*)是永真式。所以(suy)推理正确。v 真值表技术(jsh)：给定一个前提集合和一个结论，用构成真值表v 的方法，在有限步骤内判定给定前提是否能推v 导出该结论的这种方法，称为真值表技术(jsh)。第5页/共24页第六页

7、，共24页。(P(PQ)P)Q)P)Q Q (PPQ)P)Q)P)Q Q (PQ)(PQ)P)P)Q Q (P(PPPQ)(QQ)(QPPQ)Q)TT TT T T因而因而(yn r)(P(yn r)(P Q)P)Q)P)Q(*)Q(*)是永真式，推理正确。是永真式，推理正确。2 2 等值演算法第6页/共24页第七页，共24页。(P(P(P(PQ)P)Q)P)Q)P)Q)P)Q Q Q Q (PPPPQ)P)Q)P)Q)P)Q)P)Q Q Q Q (PQ)(PQ)(PQ)(PQ)P P P P Q Q Q Q (PQ)(PQ)(PQ)(PQ)(P(QP(QP(QP(QQ)(PQ)(PQ)(PQ

8、)(PP)P)P)P)Q)Q)Q)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PPPPQ)(PQ)(PQ)(PQ)(PQ)(Q)(Q)(Q)(PPPPQ)Q)Q)Q)(PPPPQ)(Q)(Q)(Q)(PQ)(PPQ)(PPQ)(PPQ)(PQ)(PQ)Q)(PQ)Q)(PQ)Q)(PQ)(0,1,2,3)(0,1,2,3)(0,1,2,3)(0,1,2,3)因而因而因而因而(yn r)(*)(yn r)(*)(yn r)(*)(yn r)(*)是永真式，推理正确。是永真式，推理正确。是永真式，推理正确。是永真式，推理正确。3 3 主析取范式法第7页/共24页第八页，共

9、24页。即要判断(PQ)P Q证明：假设前件(PQ)P 为真，则P为真，且(PQ)为真，所以(suy)Q 为真。故(PQ)P Q成立，推理正确。4 指派(zhpi)分析法(永真蕴含式)基于定义进行推理的不足：基于定义进行推理的不足：1 1 如果命题公式的变元较多，以上四种方法如果命题公式的变元较多，以上四种方法(fngf)(fngf)都不方便都不方便 。(n (n个变元，个变元，2n 2n种指派种指派)2 2 与自然生活和传统数学中的推理形式无相同之处。与自然生活和传统数学中的推理形式无相同之处。3 3 过于机械，对培养推理能力和推理技巧毫无帮助。过于机械，对培养推理能力和推理技巧毫无帮助。第

10、8页/共24页第九页，共24页。形式证明形式证明(zhngmng)(zhngmng)：对由前提：对由前提H1H1，H2H2，HmHm推结论推结论C C的推理，的推理，构造一个描述推理过程的命题公式序列，其中构造一个描述推理过程的命题公式序列，其中 每个命题公式或者是已知的前提，或者是由某每个命题公式或者是已知的前提，或者是由某 些前提应用公认的推理规则所得到的结论，序些前提应用公认的推理规则所得到的结论，序 列中最后一个命题公式是所要求的结论。列中最后一个命题公式是所要求的结论。这样的命题公式序列称为形式证明这样的命题公式序列称为形式证明(zhngmng)(zhngmng)。形式证明形式证明(

11、zhngmng)(zhngmng)的格式：形式证明的格式：形式证明(zhngmng)(zhngmng)是按行进行的，是按行进行的，而且每行只能而且每行只能 写一个命题公式。一般为：写一个命题公式。一般为：标号部分标号部分 命题公式命题公式 说明部分说明部分三、基于(jy)规则的推理第9页/共24页第十页，共24页。推理过程中使用推理过程中使用(shyng)(shyng)的构造公式序列的规则：的构造公式序列的规则：规则规则P P（前提引入规则）：在推导的任何步骤上，都可以引入前提。（前提引入规则）：在推导的任何步骤上，都可以引入前提。规则规则T T（结论引入规则）：在推导过程中，如果前面有一个或

12、多个（结论引入规则）：在推导过程中，如果前面有一个或多个命题公式永真蕴含命题公式命题公式永真蕴含命题公式 S S，那么就可以把公式，那么就可以把公式 S S 引进推引进推导过程中。导过程中。代入规则：在推导的任何步骤上，永真式中的任一命题变元都可代入规则：在推导的任何步骤上，永真式中的任一命题变元都可以用任一命题公式代入，代入后得到的仍是永真式。以用任一命题公式代入，代入后得到的仍是永真式。置换规则：在推导的任何步骤上，命题公式中的任何子公式都可置换规则：在推导的任何步骤上，命题公式中的任何子公式都可以用与之等值的命题公式置换。以用与之等值的命题公式置换。常用的推理公式：常用的推理公式：在表在

13、表1.2-21.2-2中列出的永真蕴含式。中列出的永真蕴含式。在表在表1.2-11.2-1中列出的逻辑等价式。中列出的逻辑等价式。常用的推理(tul)规则第10页/共24页第十一页，共24页。1 1直接证明法直接证明法 由已知的前提由已知的前提(qint)H1,H2,Hm(qint)H1,H2,Hm出发，利用一些出发，利用一些公认的推理规则，根据已知的逻辑等价式和永真蕴含公认的推理规则，根据已知的逻辑等价式和永真蕴含式，推导出有效结论式，推导出有效结论C C。证明证明(zhngmng)方法方法 推理(tul)：H1H2 Hm C 2间接证明法间接证明法 将已知的前提和结论进行适当的改造，转化为

14、对新的前提和结论进行推理证明。常用的技巧有：附加前提证明法和反证法。第11页/共24页第十二页，共24页。例例1-5-3 1-5-3 检验下列检验下列(xili)(xili)推理的有效性。推理的有效性。如果马会飞或羊吃草，则母鸡就会是飞鸟；如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么煮熟的鸭子还会跑；如果母鸡是飞鸟，那么煮熟的鸭子还会跑；煮熟的鸭子不会跑，所以羊不吃草。煮熟的鸭子不会跑，所以羊不吃草。解：设解：设P P：马会飞。：马会飞。Q Q：羊吃草。：羊吃草。R R：母鸡是飞鸟。：母鸡是飞鸟。S S：煮熟的鸭子会跑：煮熟的鸭子会跑则前提为：则前提为：(PQ)R(PQ)R，RS

15、 RS，S S 结论为：结论为：Q Q 推理的形式结构为：推理的形式结构为：(PQ)R)(RS)(PQ)R)(RS)(S)S)Q Q1.1.直接证明直接证明(zh ji zhn mn)(zh ji zhn mn)法法第12页/共24页第十三页，共24页。证明：证明：(1)(1)S S 规则规则P P(2)RS (2)RS 规则规则P P(3)(3)R (1)(2)R (1)(2)拒取式，规则拒取式，规则T T(4)(PQ)R (4)(PQ)R 规则规则P P(5)(5)(PQ)(3)(4)(PQ)(3)(4)拒取式，规则拒取式，规则T T(6)(6)PPQ (5)Q (5)德摩根律，替换规则，

16、规则德摩根律，替换规则，规则T T(7)(7)Q (6)Q (6)简化式，规则简化式，规则T T 所以推理正确所以推理正确 Q Q：羊不吃草：羊不吃草有效结论，但不是有效结论，但不是(b shi)(b shi)正确的结论。正确的结论。P P：马不会飞：马不会飞有效结论，而且是正确的结论。有效结论，而且是正确的结论。v 有效是指结论的推出是合乎推理规则的，并不在于v 结论是否(sh fu)真实。第一列是步骤列第一列是步骤列,将各次操作按先后排序将各次操作按先后排序;第二列是断言列或命题公式列第二列是断言列或命题公式列,内容可以是前提内容可以是前提,中间结论或最终结论中间结论或最终结论;第三列是注

17、释列或根据列第三列是注释列或根据列,表明所引用的推理规则表明所引用的推理规则及与之有关及与之有关(y(yugun)ugun)的行的编号的行的编号.第三列是形式推理的特点与优点第三列是形式推理的特点与优点.第13页/共24页第十四页，共24页。例1-5-4 证明 RS是前提CD，CR，DS的 有效(yuxio)结论，即证明：(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

18、)蕴含等价式，规则T 第14页/共24页第十五页，共24页。2.2.间接间接(jin ji)(jin ji)证明法证明法(1)附加前提法（CP规则）(2)当待证的有效结论是一个PQ 类型的条件命题时，(3)可以将有效结论中的前提P 单独提出来加到前提中去，(4)然后证明(zhngmng)剩下的后件Q 是附加了前提之后的新的一组前提(5)的有效结论。这种附加前提的证明(zhngmng)方法称为 CP规则。(6)即：H1H2 Hm(PQ)的充要条件是(7)H1H2 Hm PQ。证明：要证 H1H2 Hm (PQ)即证(H1H2 Hm)(PQ)T 同样(tngyng)，要证 H1H2 HmP Q 即

19、证(H1H2 HmP)Q T 而(H1H2 Hm)(PQ)(H1H2 Hm P)Q （输出律）第15页/共24页第十六页，共24页。例例1-5-5 1-5-5 证明：证明：RRP P是前提是前提PQPQ，QRQR的有效结论。的有效结论。分析：要证明：分析：要证明：(PQ)(QR)(PQ)(QR)RRP P 采用附加采用附加(fji)(fji)前提证明法，转化为证明：前提证明法，转化为证明：(PQ)(QR)(PQ)(QR)R R P P证明：证明：(1)(1)R R 规则规则P(P(附加附加(fji)(fji)前前提提)(2)QR (2)QR 规则规则P P (3)(3)Q (1),(2)Q (

20、1),(2)拒取式，规则拒取式，规则T T (4)PQ (4)PQ 规则规则P P (5)(5)P (3),(4)P (3),(4)拒取式，规则拒取式，规则T T (6)(6)RRP CPP CP规则规则 由由CP CP 规则，得：规则，得：(PQ)(QR)(PQ)(QR)RRP P第16页/共24页第十七页，共24页。课内练习课内练习 1-5-1 1-5-1 证明推理：证明推理：P(QR)P(QR)，Q(RS)Q(RS)P(QS)P(QS)分析：由分析：由CPCP规则规则(guz)(guz)P(QR)P(QR)，Q(RS)Q(RS)P(QS)P(QS)等价于等价于 P(QR)P(QR)，Q(

21、RS)Q(RS)，P P QS QS再由再由CPCP规则规则(guz)(guz)，等价于，等价于 P(QR)P(QR)，Q(RS)Q(RS)，P P，Q Q S S第17页/共24页第十八页，共24页。证明证明证明证明(zhngmng)(zhngmng)(zhngmng)(zhngmng)：(1)P (1)P (1)P (1)P 规则规则规则规则P(P(P(P(附加前提附加前提附加前提附加前提)(2)P(QR)(2)P(QR)(2)P(QR)(2)P(QR)规则规则规则规则P P P P(3)QR (1),(2)(3)QR (1),(2)(3)QR (1),(2)(3)QR (1),(2)假言

22、推理，规则假言推理，规则假言推理，规则假言推理，规则T T T T(4)Q (4)Q (4)Q (4)Q 规则规则规则规则P(P(P(P(附加前提附加前提附加前提附加前提)(5)(5)(5)(5)R (3),(4)R (3),(4)R (3),(4)R (3),(4)假言推理，规则假言推理，规则假言推理，规则假言推理，规则T T T T(6)(6)(6)(6)Q(RS)Q(RS)Q(RS)Q(RS)规则规则规则规则P P P P(7)RS (4)(6(7)RS (4)(6(7)RS (4)(6(7)RS (4)(6）假言推理，规则）假言推理，规则）假言推理，规则）假言推理，规则T T T T(

23、8)S (5),(7)(8)S (5),(7)(8)S (5),(7)(8)S (5),(7)假言推理，规则假言推理，规则假言推理，规则假言推理，规则T T T T(9)P(QS)CP(9)P(QS)CP(9)P(QS)CP(9)P(QS)CP规则规则规则规则由由由由CP CP CP CP 规则，有：规则，有：规则，有：规则，有：P(QR)P(QR)P(QR)P(QR)，Q(RS)Q(RS)Q(RS)Q(RS)P(QS)P(QS)P(QS)P(QS)第18页/共24页第十九页，共24页。例例1-5-6 1-5-6 采用采用(ciyng)(ciyng)附加前提法证明例附加前提法证明例1-5-4

24、1-5-4：(CD)(CR)(DS)(CD)(CR)(DS)(RS)(RS)。分析：由分析：由PQ PQ PQPQ，得得 RS RS RSRS 由由CPCP规则，等价于要证明规则，等价于要证明 CD CD，CRCR，DSDS，R R S S证明证明:(1):(1)R R 规则规则P(P(附加前提附加前提)(2)CR (2)CR 规则规则P P (3)(3)C (1),(2)C (1),(2)拒取式，规则拒取式，规则T T (4)CD (4)CD 规则规则P P (5)D (3),(4)(5)D (3),(4)析取三段论，规则析取三段论，规则T T (6)DS (6)DS 规则规则P P (7)

25、S (5)(7)S (5)，(6)(6)前提三段论，规则前提三段论，规则T T (8)(8)RS CPRS CP规则规则 (9)RS (8)(9)RS (8)蕴含等价式，规则蕴含等价式，规则T T v CP规则(guz)的适用范围：v待证的有效结论是PQ 或 PQ 型的命题。第19页/共24页第二十页，共24页。(2)(2)反证法反证法(归谬法归谬法)将结论将结论C C的否定的否定C C 做为假设前提做为假设前提(qint)(qint)推出矛盾推出矛盾的证明方法称为反证法或归谬法。的证明方法称为反证法或归谬法。即：即：H1H2 Hm H1H2 Hm C C 的充要条件是的充要条件是 H1H2

26、Hm H1H2 Hm C C F F。证明(zhngmng)：要证 H1H2 Hm C 即证(H1H2 Hm)C T 同样，要证 H1H2 HmC F 即证(H1H2 HmC)F T 而(H1H2 Hm)C (H1H2 Hm)C (H1H2 HmC)上式左边是永真式，当且仅当H1H2 HmC是永假式。第20页/共24页第二十一页，共24页。例例1-5-7 1-5-7 证明证明 (PQ)(PQ)是是PPQ Q 的有效结论。的有效结论。即证：即证：PPQ Q (PQ)(PQ)分析：用反证法，将分析：用反证法，将(PQ)(PQ)作为假设前提去证作为假设前提去证:PPQQ(PQ)(PQ)F F证明：证

27、明：(1)(1)(PQ)(PQ)规则规则P P（假设前提）（假设前提）(2)PQ (1)(2)PQ (1)双重双重(shungchng)(shungchng)否定律，否定律，规则规则T T (3)P (2)(3)P (2)简化式简化式,，规则，规则T T (4)(4)PPQ Q 规则规则P P (5)(5)P (4)P (4)简化式，规则简化式，规则T T (6)P (6)PP P（矛盾）（矛盾）(3)(5)(3)(5)合取式合取式,，规则，规则T T由反证法得：由反证法得：PPQ Q (PQ)(PQ)第21页/共24页第二十二页，共24页。设设P1,P2,PnP1,P2,Pn为命题公式为命题

28、公式(gngsh)H1,H2,Hm(gngsh)H1,H2,Hm中的命题中的命题变元。变元。相容：如果对于相容：如果对于P1,P2,PnP1,P2,Pn的某一真值指派，的某一真值指派，H1H2Hm H1H2Hm 的真值为，的真值为，则称命题公式则称命题公式(gngsh)H1,H2,Hm(gngsh)H1,H2,Hm是相容的。是相容的。不相容：如果对不相容：如果对P1,P2,PnP1,P2,Pn的所有真值指派，的所有真值指派，H1H2Hm H1H2Hm 的真值皆为，的真值皆为，则称命题公式则称命题公式(gngsh)H1,H2,Hm(gngsh)H1,H2,Hm是不相容的。是不相容的。命题命题(m

29、ng t)公式相容性公式相容性思考：若H1,H2,Hm 是不相容的，则H1H2Hm M (M为任意(rny)命题)第22页/共24页第二十三页，共24页。课内练习课内练习1-5-2 1-5-2 证明证明 ABAB，CCB B A AC C 证明证明1 1：反证法：反证法 (A(AC)PC)P（假设前提（假设前提(qint)(qint)）AC ,T AC ,T A ,T A ,T C ,T C ,T AB PAB P B ,T B ,T C CB PB P B ,TB ,T B BB(B(矛盾矛盾)证明(zhngmng)2：附加前提证明(zhngmng)法(略)第23页/共24页第二十四页，共24页。