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