离散数学课件第一章(第5讲).ppt

《离散数学课件第一章(第5讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第一章(第5讲).ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6 推理理论推理理论 按公认的推论规则，从前提集合中推导出一个结论，按公认的推论规则，从前提集合中推导出一个结论，这样的推导过程称为这样的推导过程称为演绎演绎，或者叫，或者叫形式证明形式证明。根据逻辑规则推导出来的任何结论称为根据逻辑规则推导出来的任何结论称为有效结论有效结论。定定义义：给给定定二二个个命命题题公公式式和和，当当且且仅仅当当是是一一个个永永真真式式，则则AB，可可以以称称是是从从推推导导出来的，或称是前提的有效结论。出来的，或称是前提的有效结论。定定义义：设设H1，H2,Hm,都都是是命命题题公公式式，当当且且仅仅当当H1 H2 Hm，则则可可以以称称是是前前提提集集合合 H1

2、，H2,Hm 的有效结论。的有效结论。我我们们只只讨讨论论命命题题论论证证的的有有效效性性，而而不不去去讨讨论论命命题题的的真真假假值值；所所以以在在推推论论规规则则中中不不需需要要有有真真值值表表，也不需要对命题进行真值指派。也不需要对命题进行真值指派。1直接证明法：直接证明法：直直接接证证明明法法的的思思想想是是根根据据给给定定的的前前提提，依依据据常常用用的的永永真真蕴蕴含含式式和和等等价价公公式式，并并利利用用P规规则则和和T规规则则推导出结论。推导出结论。逻辑推理证明方法逻辑推理需要应用的二个规则：逻辑推理需要应用的二个规则：P规则规则：在推导的过程中引入前提（条件）：在推导的过程中

3、引入前提（条件）T规规则则：在在推推导导过过程程中中，如如果果前前面面有有一一个个或或多多个个公公式式永永真真蕴蕴含含S，则则可可以以把把S引引入入推推导导过过程程。或或两两个个公公式等价，将等价的公式引入推导过程。式等价，将等价的公式引入推导过程。(1)PQ P (2)P P (3)Q T(1)(2)I (4)Q R P (5)R T(3)(4)I 也可以这样推理：也可以这样推理：(1)PQ P (2)Q R P (3)PR T(1)(2)I (4)P P (5)R T(3)(4)I 例例1 证明：证明：PQ,Q R,P R证：证：例例2 证明：证明：P Q,P R,Q S S R 证证:(

4、1)P Q P (2)P Q T(1)E (3)Q S P (4)P S T(2)(3)I (5)S P T(4)E (6)P R P (7)S R T(5)(6)I (8)S R T(7)E 例例3 构造下面推理的证明。构造下面推理的证明。2是素数或合数。若是素数或合数。若2是素数，则是素数，则 是无理数。则是无理数。则 是无理数，则是无理数，则4不是素数。所以，如果不是素数。所以，如果4是素数，则是素数，则2是合数。是合数。翻译：翻译：P：2是素数是素数 Q:2是合数是合数 R:是无理数是无理数 S:4是素数是素数 前提：前提：P Q,P R,R S 结论：结论：S Q例例3 证明：证明：

5、前提：前提：P Q,P R,R S 结论：结论：S Q证证:(1)P Q P (2)P Q T(1)E (3)P R P (4)R S P (5)P S T(3)(4)I (6)S P T(5)E (7)S Q T(2)(6)I 例例4 构造下面推理的证明。构造下面推理的证明。如果今天是周六，我们就去颐和园或圆明园玩。如果如果今天是周六，我们就去颐和园或圆明园玩。如果颐和园游人太多，就不去颐和园。今天是周六，并且颐和园游人太多，就不去颐和园。今天是周六，并且颐和园游人太多。所以我们去圆明园或动物园玩。颐和园游人太多。所以我们去圆明园或动物园玩。翻译：翻译：P：今天是周六：今天是周六 Q:我们到

6、颐和园玩我们到颐和园玩 R:我们到圆明园玩我们到圆明园玩 S:颐和园游人太多颐和园游人太多 T:我们到动物园玩我们到动物园玩 前提：前提：P (Q R),S Q,P，S 结论：结论：R T例例4 证明：证明：前提：前提：P (Q R),S Q,P,S 结论：结论：R T证证:(1)S P (2)S Q P (3)Q T(1)(2)I (4)P (Q R)P (5)P P (6)Q R T(4)(5)I (7)Q R T(6)E (8)R T(3)(7)I (9)R T T(8)I 2.CP规则证明规则证明设设H1，H2,Hm是命题公式，是命题公式，要证明要证明H1 H2 Hm AB，是否可以转

7、变为证明是否可以转变为证明H1 H2 Hm A B？CP规则证明思想是规则证明思想是:如果能从如果能从A和给定的前提集合和给定的前提集合H1,H2,Hm 中推导出中推导出B，则就能从前提集合，则就能从前提集合H1,H2,Hm 中推导出中推导出A B。即即：要要证证明明 H1 H2 Hm AB,可可以以转转变变为为证明证明H1 H2 Hm A B。CP规则证明方法是一种间接证明法。规则证明方法是一种间接证明法。CP规则证明方法为什么成立？规则证明方法为什么成立？要证明要证明 H1 H2 Hm AB,可以转变为证明可以转变为证明H1 H2 Hm A B。解解释释：若若H1 H2 Hm A B 成成

8、立立，则则根根据据永永真真蕴蕴含含定义，定义，H1 H2 Hm A B 为永真式。为永真式。而而H1 H2 Hm A B (H1 H2 Hm A)B (H1 H2 Hm)A B (H1 H2 Hm)(A B)(H1 H2 Hm)(A B)(H1 H2 Hm)(A B)为永真式，则根据永真蕴含为永真式，则根据永真蕴含定义知：定义知：H1 H2 Hm AB成立。成立。例例1 P(Q S),R P,Q RS证证:(1)R 附加前提附加前提(2)R P P (3)RP T(2)E (4)P T(1)(3)I (5)P(Q S)P (6)Q S T(4)(5)I (7)Q P (8)S T(6)(7)I

9、 (9)RS CP 例例2 PQ P(P Q)证证:(1)P 附加前提附加前提 (2)PQ P (3)Q T(1)(2)I (4)P Q T(1)(3)I (5)P(P Q)CP3反证法反证法（归谬法）（归谬法）反证法的证明思想是：将结论取反，作为附加前反证法的证明思想是：将结论取反，作为附加前提，和原有的前提集合一起推导出矛盾的结论，提，和原有的前提集合一起推导出矛盾的结论，则原前提集合推导出结论是成立的。则原前提集合推导出结论是成立的。反证法也是一种间接证明法。反证法也是一种间接证明法。定义定义给出命题公式给出命题公式H1,H2Hm，H1 H2 Hm 具有具有真值为真值为“T”，则命题公式

10、集合，则命题公式集合 H1,H2Hm 称为是一称为是一致的。否则称致的。否则称 H1,H2Hm 是非一致的。是非一致的。定理定理设设 H1,H2Hm 是一致的，同时设是一致的，同时设C是一是一个命题公式，如果前提集合个命题公式，如果前提集合H1,H2Hm,C是非是非一致一致的，则一定有的，则一定有H1,H2HmC成立。成立。证明：由条件证明：由条件H1 H2 Hm C F H1 H2 Hm C必定为永假式。必定为永假式。而而H1 H2 Hm是一致的，即为永真式，从而是一致的，即为永真式，从而只有只有C为永假式，则为永假式，则C 一定为永真式，则一定为永真式，则H1 H2 Hm C为永真式为永真

11、式 故故H1 H2 HmC成立。成立。例例1 证明证明 P Q (P Q)证证:(1)(P Q)假设前提假设前提 (2)P Q T(1)E (3)P T(2)I (4)P Q P (5)P T(4)I (6)P P T(3)(5)I例例2 证明证明:RQ,R S,SQ,PQ P证证:(1)(P)假设前提假设前提 (2)P T(1)E (3)PQ P (4)Q T(2)(3)I (5)SQ P (6)QS T(5)E (7)S T(4)(6)I (8)R S P (9)R T(7)(8)I (10)RQ P (11)Q T(9)(10)I (12)Q Q T(4)(11)I7其他命题联结词其他命

12、题联结词其他命题联结词其他命题联结词：(1)不可兼或（异或）不可兼或（异或）(a)符号：符号：“”（），），读作，读作“异或异或”(b)定义：（见真值表）定义：（见真值表）(c)异或的性质：异或的性质：（）（）（）（）（可交换的）（可交换的）（）（）（可结合的）（可结合的）P Q P QF F FF T TT F TT T F()()()（对对 可分配的）可分配的）(2)“与非与非”联结词：联结词：(a)符号符号“”，（，（）读作：）读作：“与的否定与的否定”或或“与非与非”（）（）(b)定义：（见真值表）定义：（见真值表）PQP QFFTFTTTFTTTF(c)性质：性质：（）（）（）（）（）（）（）（）（）（）（）不可结合的）不可结合的（）（）不可结合的不可结合的 ，(3)“或非或非”联结词：联结词：(a)符号：符号：“”（）读作：）读作：“或的否定或的否定”或或“或非或非”（）（）(b)定义（由真值表给出）：定义（由真值表给出）：PQFFTFTFTFFTTF(c)性质：性质：（可交换的）（可交换的）（）（）（）（）（）（）不可结合的）不可结合的（）（）不可结合的不可结合的 ；(4)“蕴含否定蕴含否定”联结词：联结词：(a)符号：符号：(b)定义（见真值表）：定义（见真值表）：P Q(PQ)“”cPQP QTTFTFTFTFFFFcc