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

1、6 推理理论 按公认的推论规则，从前提集合中推导出一个结论，这样的推导过程称为演绎，或者叫形式证明。 根据逻辑规则推导出来的任何结论称为有效结论。 定义：给定二个命题公式和，当且仅当是一个永真式，则AB，可以称是从推导出来的，或称是前提的有效结论。定义：设H1，H2,Hm,都是命题公式，当且仅当H1 H2 Hm ，则可以称是前提集合 H1，H2,Hm 的有效结论。我们只讨论命题论证的有效性，而不去讨论命题的真假值；所以在推论规则中不需要有真值表，也不需要对命题进行真值指派。1直接证明法：直接证明法的思想是根据给定的前提，依据常用的永真蕴含式和等价公式，并利用P规则和T规则推导出结论。逻辑推理证

2、明方法逻辑推理需要应用的二个规则：P规则：在推导的过程中引入前提（条件）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 证明：PQ , P R , Q S SR 证: (1) PQ P (2) P Q T(1) E (

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

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

5、4) (5) I (7) Q R T(6) E (8) R T(3) (7) I (9) RT T(8) I 2. CP规则证明设H1，H2,Hm是命题公式，要证明H1 H2 Hm AB，是否可以转变为证明H1 H2 HmA B？CP规则证明思想是:如果能从A和给定的前提集合H1 , H2 , , Hm 中推导出B，则就能从前提集合H1 , H2 , , Hm 中推导出A B。即：要证明 H1 H2 Hm AB,可以转变为证明H1 H2 HmA B 。CP规则证明方法是一种间接证明法。 CP规则证明方法为什么成立？要证明 H1 H2 Hm AB,可以转变为证明H1 H2 HmA B 。解释：

6、若H1 H2 HmA B 成立，则根据永真蕴含定义，H1 H2 HmA B 为永真式。 而H1 H2 HmA B (H1 H2 HmA) B (H1 H2 Hm) AB (H1 H2 Hm) (AB) (H1 H2 Hm) (A B )(H1 H2 Hm) (A B )为永真式，则根据永真蕴含定义知：H1 H2 Hm AB成立。例1 P(Q S), RP, Q RS证: (1) R 附加前提 (2) RP 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) RS C

7、P 例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， H1H2 Hm 具有真值为“T”，则命题公式集合 H1,H2Hm 称为是一致的。否则称 H1,H2Hm 是非一致的。定理设 H1,H2Hm 是一致的，同时设C是一个命题公式，如果前提集合H1,H2Hm,C是非一致的，则一定有H1,H2Hm

8、C成立。证明：由条件H1H2 Hm C F H1H2 Hm C必定为永假式。而H1H2 Hm是一致的，即为永真式，从而只有C为永假式，则C 一定为永真式，则H1H2 Hm C为永真式 故H1H2 HmC成立。例1 证明 P Q (PQ) 证: (1) ( (PQ) 假设前提 (2) PQ 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, RS , 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

9、(5) E (7) S T(4)(6) I (8) RS P (9) R T(7)(8) I (10) RQ P (11) Q T(9)(10) I (12)Q Q T(4)(11) I7其他命题联结词其他命题联结词： (1)不可兼或（异或）(a)符号：“”（），读作“异或” (b)定义：（见真值表）(c)异或的性质： （）（ ） （）（ ） （可交换的）（） （ ）（可结合的） PQP QFFFFTTTFTTTF()() ()（对 可分配的） (2)“与非”联结词：(a)符号“”，（）读作：“与的否定”或“与非”（）（）(b)定义：（见真值表）PQP QFFTFTTTFTTTF(c)性质：（）（）（） （）（）（）（）（）（） （）（）不可结合的（）（） 不可结合的 ，(3)“或非”联结词：(a)符号：“” （）读作：“或的否定”或