离散数学课件：1-7 推理理论.ppt

在逻辑学中把从所谓在逻辑学中把从所谓前提前提的一些命题出发，依的一些命题出发，依据公认的推理规则，推导出所谓据公认的推理规则，推导出所谓结论结论的一个命的一个命题的过程称为题的过程称为有效推理有效推理或或形式证明形式证明，所得结论，所得结论叫做叫做有效结论有效结论.&设设A和和C是两个命题公式，当且仅当是两个命题公式，当且仅当AC为一重言式，即为一重言式，即A C,称称C是是A的的有效结论有效结论，或，或C可由可由A逻辑推出逻辑推出.&注意：不是注意：不是正确结论正确结论.比如比如如果猪会飞，那么太阳从西边出来如果猪会飞，那么太阳从西边出来.是重言式，而命题是重言式，而命题“太阳从西边出来太阳从西边出来”的真值为的真值为F.七、七、 推推 理理 理理 论论一、推理的概念一、推理的概念推广到有推广到有n个前提的情形个前提的情形 设设H1, H2, …, Hn和和C是命题公式，当且仅当是命题公式，当且仅当H1 H2  … Hn  C ，，称称C是一组前提是一组前提H1, H2, …, Hn的的有效结论有效结论，有时可记，有时可记为为H1, H2, …, Hn  C .注注&在形式证明中重要的是在形式证明中重要的是推理的有效性推理的有效性，而不在于结论，而不在于结论是否真实；是否真实；&所谓所谓“推理有效推理有效”是指，结论是前提的合乎逻辑的结是指，结论是前提的合乎逻辑的结果果.七、推理理论七、推理理论 判别有效结论的过程就是论证过程判别有效结论的过程就是论证过程.论证方法有：论证方法有：&真值表法；真值表法；&直接证法；直接证法；&间接证法：间接证法：&反证法；反证法；&CP规则规则.二、论证方法二、论证方法七、推理理论七、推理理论真值表法真值表法 要证明要证明H1 H2  … Hn  C是否成立，使是否成立，使用真值表有两个方法：用真值表有两个方法：&对于每一个对于每一个H1, H2, …, Hn真值均为真值均为T的行，的行，C也有真也有真值T（（前件前件为真，后件也真，后件也为真真））.&对于每一个对于每一个C 的的真值均为真值均为F的行，的行，H1, H2, …, Hn的真的真值中中至少有一个至少有一个为F（（后件后件为假，前件假，前件也也为假假））.七、推理理论七、推理理论例例例例1.7.11.7.1一份统计表格的错误或者是由于材料不可靠，或者一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误材料不可靠，所以这份统计表格是由于计算有错误.解：解： 设设P:统计表格的错误是由于材料不可靠统计表格的错误是由于材料不可靠. Q:统计表格的错误是由于计算有错误统计表格的错误是由于计算有错误.则有则有  P  (P   Q) Q.P QT TT FF TF F PF F TTP   QTT TF从真值表看到：当从真值表看到：当  P和和P   Q 的真值都为的真值都为T时（在第三行），时（在第三行），Q也为也为T，所以，所以  P  (P   Q) Q.或者由：当或者由：当Q的真值为的真值为F 时，时，  P和和P   Q至少有一个为至少有一个为F.本题证明本题证明的是一个的是一个常用蕴含常用蕴含式，本质式，本质上就是我上就是我们常用的们常用的排除法排除法.七、推理理论七、推理理论例例例例1.7.21.7.2如果张老师来了，这个问题可以得到解答；如果李如果张老师来了，这个问题可以得到解答；如果李老师来了，这个问题也可以得到解答老师来了，这个问题也可以得到解答.总之，张老总之，张老师或李老师来了，这个问题就可以得到解答师或李老师来了，这个问题就可以得到解答.解：解： 设设P:张老师来了张老师来了. Q:李老师来了李老师来了. R:这个问题可以得到这个问题可以得到解答解答.则有则有(P R) (Q R) (P  Q) R.从真值表看到：当从真值表看到：当P R, Q R和和P   Q 的真值都为的真值都为T时时（在第一、三、五列），（在第一、三、五列），R也为也为T，所以，所以(P R) (Q R) (P  Q) R.构造性二构造性二难的应用难的应用PT TTT FFFFQT TFFT T FFRT FTFT FTFQ RT F TT T FTTP  QT TTT T T FFP RT FTFT T TT七、推理理论七、推理理论直接证明法直接证明法 直接证明法直接证明法就是由一组前提，利用一些公就是由一组前提，利用一些公认的推理规则，根据已知的认的推理规则，根据已知的等价公式等价公式或或蕴含公蕴含公式式，推演得到有效的结论，推演得到有效的结论.&P规则规则（前提引入）：前提在推导过程中的任（前提引入）：前提在推导过程中的任何时候都可以引入；何时候都可以引入；&T规则规则（结论引用）：在推导中，如果有一个（结论引用）：在推导中，如果有一个或多个公式重言蕴含着公式或多个公式重言蕴含着公式S（结论），则公（结论），则公式式S可以引入推导之中可以引入推导之中.常用的蕴含公常用的蕴含公式和等价公式式和等价公式是推理证明的是推理证明的基础基础.七、推理理论七、推理理论1. P   Q 2. P   Q 化化简简 P  Q3. P 附附加加 P   Q4. Q  P   Q5.   P  P  Q6. Q  P  Q附附加加的的应应用用7.  (P  Q)  P8.  (P  Q)    Q化化简简的的应应用用常用的逻辑蕴含式常用的逻辑蕴含式七、推理理论七、推理理论9. P   (P  Q) 10.   Q   (P  Q) 假假 言言 推推 理理 Q    P11.   P   (P   Q) 析析取取三三段段论论 Q12. (P  Q)  (Q  R)  P→R拒拒取取式式假假言言三三段段论论常用的逻辑蕴含式常用的逻辑蕴含式13. (P  Q)  (Q  R) (P  R)等等价价三三段段论论即即“反证反证法法”又称又称“选言推理选言推理”或或“排除法排除法”七、推理理论七、推理理论16. P , Q 17. P  Q合合 取取 引引 入入 P   Q ( P   R)  (Q   R)常用的逻辑蕴含式常用的逻辑蕴含式18. P  Q ( P   R)  (Q   R)14. (P   Q)  (P  R)  (Q  S) R   S构构造造性性二二难难15. (P  R)  (Q  S) (P   Q) (R   S)七、推理理论七、推理理论1.  P对对合合律律2. P P3. P P 幂幂等等律律4. P Q5. P Q交交换换律律 P  P  PQ PQ P常用的等价公式常用的等价公式七、推理理论七、推理理论6. (P Q)  R7. (P Q) R结结合合律律8. P (Q   R )9. P (Q   R )分分配配律律10.   (P Q)11.   (P Q)德德 ·摩摩 根根律律 P (Q R) P (Q R)(P  Q)  ( P R)(P Q)   (P R)   P   Q   P  Q常用的等价公式常用的等价公式七、推理理论七、推理理论12. P (P Q)13. P (P Q)吸吸收收律律 14. P T15. P F零零律律16. P F17. P T同同一一律律 P  P19. P   P18. P P否否定定律律 P  P T F F  T常用的等价公式常用的等价公式七、推理理论七、推理理论20. PQ21.   (PQ)22. PQ23. P  (Q R) 24. P Q 25. P Q    P   Q  P     Q 26.  (P  Q) (PQ)   (Q  P)  (P   Q)  (  P     Q) P    Q (P   Q) R   QP常用的等价公式常用的等价公式七、推理理论七、推理理论 形式推理的具体操作可在包含形式推理的具体操作可在包含3列列的一张表上的一张表上进行：进行：&第一列是序号，将各次操作按先后排序；第一列是序号，将各次操作按先后排序；&第二列是断言或命题公式，内容可以是前提，第二列是断言或命题公式，内容可以是前提，中间结论或最终结论；中间结论或最终结论；&第三列是注释或根据，表明所引用的推理规则第三列是注释或根据，表明所引用的推理规则及与之有关的行的编号及与之有关的行的编号.七、推理理论七、推理理论形式推理的表上作业形式推理的表上作业形式推理的表上作业形式推理的表上作业证明：证明：证明：证明：  (P     Q),   Q   R,   R    P .(1)   R(2)   Q   R(3)   Q(4)   (P     Q) (5)   P   Q(6)   PPPT(1)(2), IPT(4), ET(3)(5), I为什么可以这样表示？为什么可以这样表示？&蕴含式蕴含式P Q的证明方法之一就是：的证明方法之一就是：假设前件假设前件P为为T，能，能够推得后件够推得后件Q也为也为T.&第二列所列命题公式均是真值为第二列所列命题公式均是真值为T的的.七、推理理论七、推理理论证：证：证：证：(1) P   Q(2)   P  Q(3) Q  S(4)   P  S(5)   S  P(6) P RPT(1), EPT(7), ET(4), EP例例例例1.7.31.7.3证明：证明： (P   Q)  (P  R)  (Q  S)  R   S. (7)   S  R(8) S   RT(5)(6), IT(2)(3), I七、推理理论七、推理理论证法一：证法一：证法一：证法一：(1)   C     U(2)   U (3) S  U(4)   S (5)   C (6)   C     S PT(1), IPPT(1), IT(4)(5), I例例例例1.7.41.7.4证明：证明： W   R  V, V  C   S, S  U,   C     U   W . (7)   (C   S) (8) W   R  VT(6), ET(2)(3), I(9) V  C   S(10)W   R  C   S(11)   (W   R) (12)   W     R (13)   W PT(11), ET(12), IT(7)(10), IT(8)(9), I七、推理理论七、推理理论证法二：证法二：证法二：证法二：(1)   C     U(2)   U (3) S  U(4)   S (5)   C (6)   C     S PT(1), IPPT(1), IT(4)(5), I例例例例1.7.41.7.4证明：证明： W   R  V, V  C   S, S  U,   C     U   W . (7)   (C   S) (8) V  C   ST(6), ET(2)(3), I(9)   V(10)W   R  V(11)   (W   R) (12)   W     R (13)   W T(7)(8), IT(11), ET(12), IT(9)(10), IP七、推理理论七、推理理论相容相容&不相容不相容 设设P1, P2, …, Pm是出现于前提是出现于前提H1, H2, …, Hn中的全体命题变元，中的全体命题变元，&对于对于P1, P2, …, Pm的的一些一些真值指派，如果能真值指派，如果能使使H1 H2  … Hn的真值为的真值为T，， 则称公式称公式H1, H2, …, Hn是是相容相容的的. &如果对于如果对于P1, P2, …, Pm的的每一组每一组真值指派，真值指派，使得使得H1 H2  … Hn的真值均为的真值均为F，， 则称公式称公式H1, H2, …, Hn是是不相容不相容的的. 七、推理理论七、推理理论间接证明法之一：反证法间接证明法之一：反证法要证要证H1 H2  … Hn C ,记作记作S  C ,即即S  C 或或 S  C为为T，，故故S    C为为 F，，即即S与与 C不相容不相容. 因此要证因此要证H1 H2  … Hn C ,只要证只要证H1, H2, …, Hn与与 C是不相容的是不相容的.F这其实就是我们经常使用的这其实就是我们经常使用的反证法反证法.七、推理理论七、推理理论证：（证：（证：（证：（反证法反证法））））(1) A(2) A  B(3) B(4)   (B   C) (5)   B     C (6)   BP(附加前提附加前提)PT(1)(2), IT(4), ET(5), I例例例例1.7.5 1.7.5 证明：证明： A  B,   (B   C)    A . (7) B     B（矛盾）（矛盾） T(3)(6), IP下证下证A  B,   (B   C) 与与 (  A) 不相容不相容.七、推理理论七、推理理论证法三（证法三（证法三（证法三（反证法反证法反证法反证法）：）：）：）：(1) W(2) W   R (3) W   R  V(4) V  C   S(5) W   R  C   S (6) C   S P（附加前提）（附加前提）T(1), IPT(7), IT(3)(4), IT(2)(5), I例例例例1.7.41.7.4证明：证明： W   R  V, V  C   S, S  U,   C     U   W . (7)   C     U(8)   CPP(9) S(10) S  U(11) U (12)   U (13) U     U (矛盾矛盾)T(6)(8), IT(7), IT(11)(12), IT(10), IP七、推理理论七、推理理论间接证明法的另一种情形：间接证明法的另一种情形：CP规则规则要证要证H1 H2  … Hn (R  C) ,将将H1 H2  … Hn记作记作S，即要证，即要证S  (R  C) ,即即S  (R  C)为为T.由由E23 :P  (Q R) 从而，要证明从而，要证明S  (R  C) ，转化为，转化为证明证明(S   R)  C 这就是这就是CP规则规则(Conditional Proof),这这里将里将R称为称为附加前提附加前提. (P   Q) R，知，知S  (R C)  (S   R) C.七、推理理论七、推理理论证：证：证：证：(1) D(2)   D   A(3) A(4) A  (B C)(5) B C(6) BP(附加前提附加前提)PT(1)(2), IT(3)(4), IP例例例例1.7.6 1.7.6 证明：证明： A  (B C),   D   A, B  D C.(7) C T(5)(6), IP(8) D C CP七、推理理论七、推理理论证：证：证：证：(1) P(2) P Q(3) Q(4) Q  (  R S)(5)   R S(6)   R P(附加前提附加前提)PT(1)(2), IT(3)(4), IPQ  (  R S), P Q,   R  P S.(7) S T(5)(6), IP(8) P S CP例例例例1.7.7 1.7.7 对下面的论述构造一个证明：对下面的论述构造一个证明： 如果李明来苏州大学，若王军不生病，则王军如果李明来苏州大学，若王军不生病，则王军一定去看望李明一定去看望李明.如果李明出差到苏州，那么李明一如果李明出差到苏州，那么李明一定来苏州大学定来苏州大学. 王军没有生病王军没有生病.所以，如果李明出差所以，如果李明出差到苏州，王军一定去看望李明到苏州，王军一定去看望李明. 设设P:李李明出差到苏州明出差到苏州. Q:李明来苏州大学李明来苏州大学.R:王军生病王军生病.S:王军去看望李明王军去看望李明.则问题归结为证：则问题归结为证：列表证明如下：列表证明如下：七、推理理论七、推理理论1. 学习要求：学习要求：a. 掌握命题，命题公式，重言式，等价式，掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念蕴涵式等基本概念.b. 能利用逻辑联结词或真值表，等价式与能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理。

蕴涵式进行命题演算和推理c. 会求较复杂命题公式的主析取范式或主会求较复杂命题公式的主析取范式或主合取范式合取范式d. 会判断公式类型会判断公式类型. 小小 结结HW: 1-8习题习题(2)a,e;(3)a;(4)。