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

第四讲第四讲 推理规则和证明方法推理规则和证明方法讲授内容：讲授内容：1.推理和推理规则推理和推理规则 推理推理 推理规则推理规则 两规则两规则 替换规则替换规则 2.证明方法证明方法 直接证明方法直接证明方法 CP规则规则 反证法反证法 讲授重点：推理规则，直接证明方法与讲授重点：推理规则，直接证明方法与CPCP规则规则讲授难点：直接证明方法，讲授难点：直接证明方法，CPCP规则与反证法规则与反证法1.什么是推理？什么是推理？1.推理和推理规则推理和推理规则推理推理:从前提推出结论的思维过程。从前提推出结论的思维过程。前提前提:指已知的命题公式。指已知的命题公式。结论结论:从前提出发，应用从前提出发，应用推理规则推理规则推出的命题公式。推出的命题公式。本节内容：从逻辑推理的角度来理解命题演算本节内容：从逻辑推理的角度来理解命题演算本节内容：从逻辑推理的角度来理解命题演算本节内容：从逻辑推理的角度来理解命题演算前提前提 结论结论推理规则推理规则推理推理2.推理的例子：设推理的例子：设x属于实数属于实数,P:x是偶数是偶数,Q:x2是偶数。是偶数。例例1.1.如果如果x x是偶数是偶数,则则x x2 2是偶数。是偶数。x x是偶数。是偶数。x x2 2是偶数。是偶数。例例3.3.如果如果x x是偶数是偶数,则则x x2 2是偶数。是偶数。x x不是偶数。不是偶数。x x2 2不是偶数。不是偶数。例例2.2.如果如果x x是偶数是偶数,则则x x2 2是偶数。是偶数。x x2 2是偶数。是偶数。x x是偶数。是偶数。例例4.4.如果如果x x是偶数是偶数,则则x x2 2是偶数。是偶数。x x2 2不是偶数。不是偶数。x x不是偶数。不是偶数。前提前提-结论结论四个例子的推理是否正确？四个例子的推理是否正确？所用依据是什么？所用依据是什么？3.1、推理和推理和推理规则推理规则刚才的例子表明了研究推理规则的重要性。刚才的例子表明了研究推理规则的重要性。推理规则：正确推理的依据。推理规则：正确推理的依据。任何一条永真蕴含式都可以作为一条推理规则。任何一条永真蕴含式都可以作为一条推理规则。例：析取三段论：例：析取三段论：如果，如果，P P：他在钓鱼，：他在钓鱼，Q Q：他在下棋：他在下棋 前提：他在钓鱼或下棋；前提：他在钓鱼或下棋；他不在钓鱼他不在钓鱼 结论：所以他在下棋结论：所以他在下棋 4.定义定义1 1：若若H H1 1HH2 2 H Hn n C,C,则称则称C C是是H H1 1,H,H2 2,H,Hn n的的有效结论有效结论。特别若特别若A A B,B,则称则称B B B B是是是是A A A A的有效结论的有效结论的有效结论的有效结论，或，或从从从从A A A A推出推出推出推出B B B B。1 1、推理和推理和推理规则推理规则注意注意：1.1.不考虑前提的真假，推理正确不考虑前提的真假，推理正确结论为真。结论为真。2.2.结论的真假结论的真假 取决于取决于 前提前提H H1 1HH2 2 H Hn n的真假。的真假。l前提为真，则结论为真；前提为真，则结论为真；l前提为假，则结论可真可假前提为假，则结论可真可假。3.3.因此，定义中只说因此，定义中只说C C 是是H H1 1,H,H2 2,H Hn n 的的有效结论有效结论而不说而不说而不说而不说是是正确结正确结论论。“有效有效”是指结论的推出合乎推理规则。是指结论的推出合乎推理规则。5.常用的推理规则常用的推理规则1)1)恒等式恒等式(E(E1 1EE2424)2)2)永真蕴含式永真蕴含式(I(I1 1II8 8,表表1.5-1)1.5-1)3)3)替换规则，代入规则替换规则，代入规则4)P4)P规则和规则和T T规则规则P P规则规则：(前提引入前提引入)在推导的任何步骤上，都可以引入前提。在推导的任何步骤上，都可以引入前提。T T规则规则：(结论引用结论引用)在推导任何步骤上所得结论都可以作为后继证明的前提。在推导任何步骤上所得结论都可以作为后继证明的前提。1 1、推理和推理和推理规则推理规则6.表表1 1.5 5-1 1 常常用用推推理理规规则则7.永真蕴含式永真蕴含式8.例例1：考虑下述论证考虑下述论证:1.如果这里有球赛如果这里有球赛,则通行是困难的。则通行是困难的。2.如果他们按时到达如果他们按时到达,则通行是不困难的。则通行是不困难的。3.他们按时到达了。他们按时到达了。4.所以这里没有球赛。所以这里没有球赛。前前 3 个断言是前提个断言是前提,最后最后1个断言是结论个断言是结论,要求我们从前提推出结论。要求我们从前提推出结论。证证：步骤步骤 断言断言(真真)根根 据据 （1）R P （2）R Q P （3）Q T,(1),(2),I3 （4）PQ P （5）P T,(3),(4),I4设设P P:这里有球赛这里有球赛,Q Q:通行是困难的通行是困难的,R R:他们按时到达。他们按时到达。即证即证 P PQ Q，R R Q Q，R R P P运用推理规则形式化证明运用推理规则形式化证明9.1).无义证明法无义证明法 证明证明 P Q为真，只需证明为真，只需证明P为假。为假。2).平凡证明法平凡证明法 证明证明 P Q为真，只需证明为真，只需证明Q为真。为真。无义证明法和平凡证明法应用的次数较少无义证明法和平凡证明法应用的次数较少,但但 对有限的或特殊的情况对有限的或特殊的情况,它们常常是重要的。它们常常是重要的。3.证明方法证明方法10.证证：(1)CD P (2)(C)D T,(1),E1 (3)C D T,(2),E14 (4)D S P (5)C S T,(3),(4),I6 (6)C R P (7)RC T,(6),E24 (8)R S T,(5),(7),I6(9)(R)S T,(8),E14(10)R S T,(9),E13.证明方法证明方法3).3).直接证明法直接证明法 H H1 1HH2 2 H Hn n C C，由前提利用推理规则直接推出由前提利用推理规则直接推出C C。例例2 2：证明：证明 C C D,CD,CRR,D,DS S R R S S11.4).4).间接证明法间接证明法-（对原命题的逆否命题进行证明）对原命题的逆否命题进行证明）证证P Q只需证只需证 Q P 因为因为P Q iff PQ永真永真 iff Q P永真永真 iff Q P5).(H1 H2 Hn)Q形式命题的证明形式命题的证明 H1 H2 Hn Q iff H1 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.证明方法证明方法12.6.CP6.CP规则（演绎定理）规则（演绎定理）P1 P2 Pn(PQ)形式命题的证明形式命题的证明证：证：P1 P2 Pn PQ 即证即证 P1 P2 Pn P Q 因为因为 P1 P2 Pn PQ iff P1 P2 Pn(PQ)永真永真 iff (P1 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 永真永真 iff P1 P2 Pn(PQ)6.证明方法证明方法13.利用利用CP规则证明以下例题规则证明以下例题例例3：证：证A(B C)，D A，B D C证：证：(1)D P（附加前提）（附加前提）(2)D A P (3)A T,(1),(2),I5 (4)A(B C)P (5)B C T,(3),(4),I3 (6)B P (7)C T,(5),(6),I3 (8)D C CP规则规则 3.证明方法证明方法14.7.分情况证明分情况证明 证明证明 P P1 1 P P2 2 P Pn n Q Q，只需证明对只需证明对每一i，P Pi i Q Q成立。成立。3.证明方法证明方法因为因为 P1 P2 Pn Q iff P1 P2 Pn Q 永真永真iff (P1 P2 Pn)Q 永真永真iff (P1 P2 Pn)Q 永真永真iff (P1 Q)(P2 Q)(Pn Q)永真永真iff (P1 Q)(P2 Q)(Pn Q)永真永真15.8.反证法（又称归谬法、矛盾法）反证法（又称归谬法、矛盾法）定义定义：设公式设公式H1,H2,Hm中的原子命题变元是中的原子命题变元是P1,P2,Pn,如果如果给给P1,P2,Pn以某一以某一 指派指派,能使能使H1 H2 Hm的真值为真的真值为真,则称命则称命题公式集合题公式集合H1,H2,Hm是是一致一致的的,否则称为否则称为非一致非一致的。的。这个定义也可这样叙述这个定义也可这样叙述:若若H1 H2 Hm R R,则则H1,H2,Hm是非一致的是非一致的,否则否则是一致的。是一致的。3.证明方法证明方法16.8.反证法（又称归谬法、矛盾法）反证法（又称归谬法、矛盾法）定理定理：设设H1,H2,Hn是一致的是一致的,C是一命题公式是一命题公式,如果如果H1,H2,Hn,C非一致非一致,则能从则能从H1,H2,Hn推出推出C，即即H1 H2 Hn C。3.证明方法证明方法证明证明：H1 H2 Hn C R R iff H1 H2 Hn C 永假永假 (1)而而H1,H2,Hn是一致的，是一致的，所以所以存在一种指派使得存在一种指派使得H1 H2 Hn 为真为真(2)由由(1),(2)知知存在一种指派使得存在一种指派使得 C 为假，即为假，即C为真为真。由肯定前件法可得由肯定前件法可得H1 H2 Hn C。17.例例4:P Q R,R S,S P Q 证：证：(1)(P Q)P,假设前提假设前提 (2)P Q T,(1),E10 (3)P Q T,(1),E1 (4)P Q R P (5)R T,(3),(4),I3 (6)R S P (7)S T,(5),(6),I5 (8)S P (9)S S T,(7),(8),合取式合取式3.证明方法证明方法18.作业：作业：P32 1.5习题习题 5(5)、8(3)(4)、9(1)、11(1)、12(4)、15(3)19.例例5：(P Q)(P R)(Q S)S R证证:(1)(S R)P,假设前提假设前提 (2)S R T,(1),E10 (3)S T,(2),I2 (4)(P Q)(P R)(Q S)P (5)Q S T,(4),I2 (6)Q T,(3),(5),I4 (7)P Q T,(4),I2 (8)P T,(6),(7),I5 (9)P R T,(4),I2 (10)R T,(8),(9),I3 (11)R T,(2),I2 (12)R R T,(10),(11),合取式合取式3.证明方法证明方法20.