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