离散数学方世昌第5节

1、11.5 1.5 推理规则和证明方法推理规则和证明方法讲授重点：推理规则，直接证明方法与讲授重点：推理规则，直接证明方法与CPCP规则规则讲授难点：直接证明方法，讲授难点：直接证明方法，CPCP规则与反证法规则与反证法2什么是推理？什么是推理？1.推理和推理规则推理和推理规则推理推理: :从前提推出结论的思维过程。从前提推出结论的思维过程。前提前提: :指已知的命题公式。指已知的命题公式。结论结论: :从前提出发，应用从前提出发，应用推理规则推理规则推出的命题公推出的命题公式。式。前提前提 结论结论推理规则推理规则推理推理3推理的例子：设推理的例子：设x属于实数属于实数, P: x是偶数是偶数

2、, Q: x2是偶数。是偶数。例例1. 1. 如果如果x x是偶数是偶数, , 则则x x2 2是偶数。是偶数。 x x是偶数。是偶数。x x2 2是偶数。是偶数。QPQP 例例3.3.如果如果x x是偶数是偶数, , 则则x x2 2是偶数。是偶数。 x x不是偶数。不是偶数。x x2 2不是偶数。不是偶数。QPQP 例例2.2.如果如果x x是偶数是偶数, , 则则x x2 2是偶数。是偶数。 x x2 2是偶数。是偶数。x x是偶数。是偶数。PQQP 例例4.4.如果如果x x是偶数是偶数, , 则则x x2 2是偶数。是偶数。 x x2 2不是偶数。不是偶数。x x不是偶数。不是偶数。

3、PQQP 前提前提- - 结论结论四个例子的推理是否正确？四个例子的推理是否正确？所用依据是什么？所用依据是什么？2x 2x 41、推理和推理和推理规则推理规则推理规则：正确推理的依据。推理规则：正确推理的依据。任何一条永真蕴含式都可以作为一条推理规则。任何一条永真蕴含式都可以作为一条推理规则。例：析取三段论：例：析取三段论： 如果，如果，P P：他在钓鱼，：他在钓鱼，Q Q：他在下棋：他在下棋 前提：他在钓鱼或下棋；前提：他在钓鱼或下棋； 他不在钓鱼他不在钓鱼 结论：所以他在下棋结论：所以他在下棋 QQPP )(QP QP 所以所以 5定义定义1 1：若若H H1 1HH2 2 H Hn n

4、 C, C, 则称则称C C是是H H1 1, , H H2 2, , H, , Hn n的的有效结论有效结论。 特别若特别若A A B, B, 则称则称，或，或。1 1、推理和推理和推理规则推理规则注意注意： 不考虑前提的真假，推理正确不考虑前提的真假，推理正确结论为真。结论为真。 结论的真假结论的真假 取决于取决于 前提前提H H1 1HH2 2 H Hn n的真假。的真假。l前提为真，则结论为真；前提为真，则结论为真；l前提为假，则结论可真可假前提为假，则结论可真可假。 因此，定义中只说因此，定义中只说C C 是是H H1 1, H, H2 2, , H, , Hn n 的的有效有效结论

5、结论是是正确结论正确结论。“有效有效”是指结论的推是指结论的推出合乎推理规则。出合乎推理规则。 6有效结论有效结论如如Q是是PQ，P 的一个有效结论。的一个有效结论。即即 证证P (PQ) 永真蕴含永真蕴含Q也就是要证：也就是要证： P (PQ) Q 是重言是重言式式.设设 P (PQ) 取值为真，则取值为真，则 P为真，为真，且且 PQ为真，为真，故故 Q为真为真故故P (PQ) Q 是重言式是重言式. 假言推理假言推理 PQ P Q7如： Q是P，(P Q) 的有效结论。即 P(P Q) Q 是一个永真式。析取三段论规则析取三段论规则 P Q P 8推理的形式结构推理的形式结构形式(1)

6、H1H2HnC形式(2) 前提: H1, H2, , Hn 结论: C 推理正确记作 H1H2HnC注注1. 与与的区别的区别9推理的形式结构推理的形式结构形式(1) H1H2HnC形式(2) 前提: H1, H2, , Hn 结论: C 推理正确记作 H1H2HnC对于实际中给出的推理对于实际中给出的推理:将推理中的（简单）命题符号化将推理中的（简单）命题符号化写出前提和结论写出前提和结论判断该推理是否正确判断该推理是否正确正确：给出一个证明序列正确：给出一个证明序列不正确：给出反例不正确：给出反例10常用的推理规则常用的推理规则1) 1) 恒等式恒等式(E(E1 1EE2424) )2)

7、2) 永真蕴含式永真蕴含式(I(I1 1II8 8, ,表表1.5-1)1.5-1)3) 3) 替换规则，代入规则替换规则，代入规则4) P4) P规则和规则和T T规则规则P P规则规则：( (前提引入前提引入) ) 在推导的任何步骤上，都可以引入前提。在推导的任何步骤上，都可以引入前提。 T T规则规则：( (结论引用结论引用) ) 在推导任何步骤上所得结论都可以作为后继在推导任何步骤上所得结论都可以作为后继证明的前提。证明的前提。 1 1、推理和推理和推理规则推理规则11永真蕴含式永真蕴含式12(4) 拒取式规则拒取式规则 PQ Q P(3) 假言推理规则假言推理规则 PQ P Q(1)

8、 加法规则加法规则 P P Q(2) 简化规则简化规则 P Q P(5) 析取三段论规则析取三段论规则 P Q Q P13推理规则推理规则(9) 破坏性二难推理规则破坏性二难推理规则 PQ RS QS PR(8)构造性二难推理规则构造性二难推理规则 PQ RS P R Q S(7) 合取引入规则合取引入规则 P Q P Q (6) 前提三段论规则前提三段论规则 PQ QR PR14例例1：考虑下述论证考虑下述论证: 1. 如果这里有球赛如果这里有球赛, 则通行是困难的。则通行是困难的。 2. 如果他们按时到达如果他们按时到达, 则通行是不困难的。则通行是不困难的。 3. 他们按时到达了。他们按

9、时到达了。 4. 所以这里没有球赛。所以这里没有球赛。 前前 3 个断言是前提个断言是前提, 最后最后1个断言是结论个断言是结论, 要求要求我们从前提推出结论。我们从前提推出结论。设设P P: : 这里有球赛这里有球赛, , Q Q: : 通行是困难的通行是困难的, , R R: : 他们按他们按时到达。时到达。 即证即证 P PQ Q，R R Q Q，R R P P运用推理规则形式化证明运用推理规则形式化证明15证证： 步骤步骤 断言断言( (真真) ) 根根 据据 （1） R P （2） R Q P （3） Q T,(1),(2),I3 （4） PQ P （5） P T,(3),(4),I

10、4即证即证 P PQ Q，R R Q Q，R R P P161.5.2 1.5.2 证明方法证明方法定理常见的形式是定理常见的形式是“P当且仅当当且仅当Q”，“如果如果P，那么，那么Q”。 而前者又相当于而前者又相当于PQ并且并且QP， 所以归根结所以归根结底，定理的主要形式是底，定理的主要形式是PQ。至于其它形式，诸如：。至于其它形式，诸如： P形式，只需证明形式，只需证明P是假是假; PQ形式，只需证明形式，只需证明P、Q俱真俱真; PQ形式，可转化为形式，可转化为 PQ形式。形式。我们主要从策略意义上说明如何证明我们主要从策略意义上说明如何证明PQ形式形式的命题，具体的技巧，仍需通过例题

11、来学习。的命题，具体的技巧，仍需通过例题来学习。171). 无义证明法无义证明法 证明证明 P Q为真，只需证明为真，只需证明P为假。为假。2). 平凡证明法平凡证明法 证明证明 P Q为真，只需证明为真，只需证明Q为真。为真。 无义证明法和平凡证明法应用的次数较少无义证明法和平凡证明法应用的次数较少, 但但 对有限的或特殊的情况对有限的或特殊的情况, 它们常常是重要的。它们常常是重要的。 3. 证明方法证明方法（PQ）183. 证明方法证明方法3).3).直接证明法直接证明法假设假设P是真，如果能推得是真，如果能推得Q是真，则是真，则PQ是真是真 H H1 1HH2 2 H Hn n C C

12、，由前提利用推理规则直接推由前提利用推理规则直接推出出C C。例例2 2：证明：证明 C C D, CD, CR, DS R, DS R R S S19 证证： (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), E1 例例2 2：证明：证明 C C D, CD, CR, DS R, DS R R S S20实例实例例 构造

13、推理的证明: 若明天是星期一或星期三, 我就有课. 若有课, 今天必须备课. 我今天下午没备课. 所以, 明天不是星期一和星期三. 解 设 P:明天是星期一, Q:明天是星期三， R:我有课， S:我备课前提: (PQ)R, RS, S结论: PQ 21实例实例(续续)前提: (PQ)R, RS, S结论: PQ 证明 RS 前提引入 S 前提引入 R 拒取式 (PQ)R 前提引入 (PQ) 拒取式 PQ 置换结论有效, 即明天不是星期一和星期三224). 4). 间接证明法间接证明法- -（对原命题的逆否命题进行证明）对原命题的逆否命题进行证明） 证证P Q只需证只需证 Q P 因为因为P

14、Q 也即也即 PQ永真永真 ， Q P永永真真 所以所以 Q P3. 证明方法证明方法23(2) 一个完全数是一个整数，它等于它的所有因子一个完全数是一个整数，它等于它的所有因子(除除本身外本身外)的和。的和。 如如 6 是一个完全数，因为是一个完全数，因为 6=1+2+3，同样同样 28 也是。也是。定理定理: 一个完全数不是一个质数。一个完全数不是一个质数。证证 其逆反如下其逆反如下: 一个质数不是一个完全数。一个质数不是一个完全数。 假假设设P是一质数，那么是一质数，那么P2 并且并且P恰有两个因子恰有两个因子 1 和和P，所以小于所以小于P的所有因子的总和是的所有因子的总和是 1。 这

15、得出这得出P不是一不是一个完全数。个完全数。这是间接证明法。这是间接证明法。245). (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, 则原恒等式成立。则原恒等式成立。256. CP6. CP规则（演绎定理）规则（演绎定理）P1P2

16、Pn ( PQ)形式命题的证明形式命题的证明证：证： P1P2 Pn PQ因为因为 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 永真永真 6. 证明方法证明方法26CP规则（演绎定理）前提: P1, P2, , Pn 结论: PQ欲证明欲证明等价地证明等价地证明前提: P1, P2, , Pn, P(附加前提)结论: Q27例 1.5-7 如果A参

17、加球赛，则B或C也将参加球赛。 如果B参加球赛，则A不参加球赛。 如果D参加球赛，则C不参加球赛。 所以，A若参加球赛，则D不参加球赛。解 设A: A参加球赛，B: B参加球赛，C: C参加球赛，D: D参加球赛。要证明的是A D可从ABC，B A，D C 推出。2829利用利用CP规则证明以下例题规则证明以下例题练习：证练习：证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

18、(8) D C CP规则规则 307.分情况证明分情况证明 证明证明 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 ) 永真永真31例例 1.5-81.5-8 试证记作试证记作“”的二元运算的二元运算“max”是可结合的，即对是可结合的，即对

19、任何整数任何整数a、b和和c，(ab)c=a(bc)。证证 对任意对任意 3 整数整数a、b、c，下列，下列 6 种情况之一必须成立种情况之一必须成立: abc，acb，bac，bca，cab或或cba。情况情况 1: abc，那么，那么 (ab)c=ac=a a(bc)=ab=a所以所以 (ab)c=a(bc)其它情况类似可证。其它情况类似可证。328. 反证法（又称归谬法、矛盾法）反证法（又称归谬法、矛盾法） 定义定义：设公式：设公式H1, H2, , Hm中的原子命题变元是中的原子命题变元是P1, P2, , Pn, 如果给如果给P1, P2, , Pn以某一以某一 指派指派, 能使能使H1H2 Hm的真值为真的真值为真, 则称命题公式集则称命题公式集合合H1, H2, , Hm是是一致一致的的, 否则称为否则称为非一致非一致的。的。 这个定义也可这样叙述这个定义也可这样叙述: : 若若H1H2Hm RR, 则则H1, H2, , Hm是非一致的是非一致的, 否则是一致的。否则是一致的。 3. 证明方法证明方法33证明证明：H1H2Hn C RR iff H1H2Hn C 永假永假 (1) 而而H1, H2, , Hn是一致的，是一致的， 所以所以存在一种指派使得存在