离散数学第四讲-推理规则与证明方法.ppt

《离散数学第四讲-推理规则与证明方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四讲推理规则和证明方法讲授内容：1.推理和推理规则推理推理规则两规则替换规则2.证明方法直接证明方法CP规则反证法讲授重点：推理规则，直接证明方法与CP规则讲授难点：直接证明方法，CP规则与反证法1什么是推理？1.推理和推理规则推理:从前提推出结论的思维过程。前提:指已知的命题公式。结论:从前提出发，应用推理规则推出的命题公式。本节内容：从逻辑推理的角度来理解命题演算前提结论推理规则推理2推理的例子：设x属于实数,P:x是偶数,Q:x2是偶数。例1.如果x是偶数,则x2是偶数。x是偶数。x2是偶数。例3.如果x是偶数,则x2是偶数。x不是偶数。x2不是

2、偶数。例2.如果x是偶数,则x2是偶数。x2是偶数。x是偶数。例4.如果x是偶数,则x2是偶数。x2不是偶数。x不是偶数。√√××前提-------------结论四个例子的推理是否正确？所用依据是什么？31、推理和推理规则刚才的例子表明了研究推理规则的重要性。推理规则：正确推理的依据。任何一条永真蕴含式都可以作为一条推理规则。例：析取三段论：如果，P：他在钓鱼，Q：他在下棋前提：他在钓鱼或下棋；他不在钓鱼结论：所以他在下棋4定义1：若H1∧H2∧…∧HnC,则称C是H1,H2,…,Hn的有效结论。特别若AB,则称B是A的有效结论，或从A推出B。1、

3、推理和推理规则注意：不考虑前提的真假，推理正确≠结论为真。结论的真假取决于前提H1∧H2∧…∧Hn的真假。前提为真，则结论为真；前提为假，则结论可真可假。因此，定义中只说C是H1,H2,…,Hn的有效结论而不说是正确结论。“有效”是指结论的推出合乎推理规则。5常用的推理规则1)恒等式(E1~E24)2)永真蕴含式(I1~I8,表1.5-1)3)替换规则，代入规则4)P规则和T规则P规则：(前提引入)在推导的任何步骤上，都可以引入前提。T规则：(结论引用)在推导任何步骤上所得结论都可以作为后继证明的前提。1、推理和推理规则6表1.5-1常用推理规则7永真蕴

4、含式8例1：考虑下述论证:1.如果这里有球赛,则通行是困难的。2.如果他们按时到达,则通行是不困难的。3.他们按时到达了。4.所以这里没有球赛。前3个断言是前提,最后1个断言是结论,要求我们从前提推出结论。证：步骤断言(真)根据（1）RP（2）R→¬QP（3）¬QT,(1),(2),I3（4）P→QP（5）¬PT,(3),(4),I4设P:这里有球赛,Q:通行是困难的,R:他们按时到达。即证P→Q，R→¬Q，R¬P运用推理规则形式化证明91).无义证明法证明PQ为真，只需证明P为假。2).平凡证明法证明PQ为真，只需证明Q为真。无义证明法和平凡证明

5、法应用的次数较少,但对有限的或特殊的情况,它们常常是重要的。3.证明方法10证：(1)CDP(2)¬(¬C)DT,(1),E1(3)¬C→DT,(2),E14(4)D→SP(5)¬C→ST,(3),(4),I6(6)C→RP(7)¬R→¬CT,(6),E24(8)¬R→ST,(5),(7),I6(9)¬(¬R)ST,(8),E14(10)RST,(9),E13.证明方法3).直接证明法H1∧H2∧…∧HnC，由前提利用推理规则直接推出C。例2：证明CD,C→R,D→SRS114).间接证明法-（对原命题的逆否命题进行证明）证PQ只需证¬

6、Q¬P因为PQiffP→Q永真iff¬Q→¬P永真iff¬Q¬P5).(H1∧H2∧…∧Hn)Q形式命题的证明H1∧H2∧…∧HnQiffH1∧H2∧…∧Hn→Q是重言式iff¬(H1∧H2∧…∧Hn)Q是重言式iff¬H1¬H2…¬HnQ是重言式iff(Q¬H1)(Q¬H2)…(Q¬Hn)是重言式iff(¬Q→¬H1)(¬Q→¬H2)…(¬Q→¬Hn)是重言式若至少有一个i，使得使¬Q¬Hi,则原恒等式成立。3.证明方法126.CP规则（演绎定理）P1∧P2∧…∧Pn→(P→Q)形式命题的证明证：P1∧P2∧…∧

7、PnP→Q即证P1∧P2∧…∧Pn∧PQ因为P1∧P2∧…∧PnP→QiffP1∧P2∧…∧Pn→(P→Q)永真iff¬(P1∧P2∧…∧Pn)(¬PQ)永真iff¬P1¬P2…¬Pn¬PQ永真iff(¬P1¬P2…¬Pn¬P)Q永真iff¬(P1∧P2∧…∧Pn∧P)Q永真iffP1∧P2∧…∧Pn∧P→Q永真iffP1∧P2∧…∧Pn→(P→Q)6.证明方法13利用CP规则证明以下例题例3：证A→(B→C)，¬DA，BD→C证：(1)DP（附加前提）(2)¬DAP(3)AT,(1),(2),I5(4)A→(B→C

8、)P(5)B→CT,(3),(4),I3(6)BP(7)CT,(5),(6),I