第四讲第四讲 推理规则和证明方法推理规则和证明方法讲授内容：讲授内容： 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 1∧H∧H2 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 1∧H∧H2 2∧ …∧∧ …∧H Hn n的真假l前提为真，则结论为真；前提为真，则结论为真；l前提为假，则结论可真可假前提为假，则结论可真可假 3.3.因此，定义中只说因此，定义中只说C C 是是H H1 1, H, H2 2, …, , …, H Hn n 的的有效结论有效结论而不说而不说而不说而不说是是正确结正确结论论有效有效””是指结论的推出合乎推理规则是指结论的推出合乎推理规则 5 常用的推理规则常用的推理规则1) 1) 恒等式恒等式( (E E1 1~E~E2424) )2) 2) 永真蕴含式永真蕴含式(I(I1 1~ ~I I8 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） P→Q P （5） ¬ P T,(3),(4),I4设设P P: : 这里有球赛这里有球赛, , Q Q: : 通行是困难的通行是困难的, , R R: : 他们按时到达。
他们按时到达 即证即证 P P→→Q 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) ¬ R→¬C 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 1∧H∧H2 2∧ …∧∧ …∧H Hn n C C，，由前提利用推理规则直接推出由前提利用推理规则直接推出C C。
例例2 2：证明：证明 C C D, CD, C→R→R, D, D→→S S R R S S11 4). 4). 间接证明法间接证明法- -（（对原命题的逆否命题进行证明）对原命题的逆否命题进行证明） 证证P Q只需证只需证¬ Q ¬P 因为因为P Q iff P→Q永真永真 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 →( P→Q)形式命题的证明形式命题的证明证：证： P1∧∧P2∧∧ …∧∧Pn P→Q 即证即证 P1∧∧P2∧∧ …∧∧Pn ∧∧ P Q 因为因为 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 ∧∧ P) Q 永真永真 iff P1∧∧P2∧∧ …∧∧Pn ∧∧ P → Q 永真永真 iff P1∧∧P2∧∧ …∧∧Pn →( P→Q)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 。