离散数学3(精品·公开课件).ppt

1-7. 命题逻辑推理 推理就是根据一个或几个已知的判断得出一个新的判断的思维过程。称这些已知的判断为前提。得到的新的判断为前提的有效结论。 实际上，推理的过程就是证明永真蕴含式的过程，即令H1，H2，…，Hn是已知的命题公式(前提)，若有 H1∧H2∧....∧Hn ? C 则称C是H1，H2，…Hn的有效结论，简称结论。 如何根据前提得到结论，需要有推理的规则。下面先介绍两个推理规则。 规则P(引入前提规则)：在推理过程中，可以随时引入前提。 规则T(引入结论规则)：在推理过程中，如果前边有一个或几个公式永真蕴涵公式S，则可将S纳入推理过程中。 在推理过程中，还要应用教材中列出的永真蕴涵式和等价公式 (常用的公式要熟记)。 下面主要介绍四种推理方法： 直接推理、条件论证法、反证法及归结法。 一.直接推理 直接推理，就是从前提直接推出结论。 上面讲到推理的过程实际上是证明永真蕴含式的过程。只不过证明的过程采用另外一种书写格式。 格式中包含：步骤号，给定前提或得出的结论，推理时所用规则，此结论是从哪几步得到的以及所用公式。下面请看一些例子。 例题４求证P→(Q→S),?R∨P,Q ?R→S 证明(1) P→(Q→S) P (2) ?P∨(?Q∨S) T (1) E (3) ?P∨(S∨?Q) T (2) E (4) (?P∨S)∨?Q T (3) E (5) Q P (6) ?P∨S T (4)(5) I (7) P→S T (6) E (8) ?R∨P P (9) R→P T (8) E (10) R→S T (7)(9) I 补充题：请根据下面事实，找出凶手： 1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 3.如果秘书的证词是正确的，则谋害发生在午夜前。 4.如果秘书的证词不正确，则午夜时屋里灯光未灭。 5. 如果清洁工富裕，则他不会谋害经理。 6.经理有钱且清洁工不富裕。 7.午夜时屋里灯灭了。 令A:清洁工谋害了经理。 B:秘书谋害了经理。 C:谋害发生在午夜前。 D:秘书的证词是正确的. E:午夜时屋里灯光灭了。H:清洁工富裕. G:经理有钱. 命题符号为： A∨B,A??C,D?C,?D??E,H??A,G∧?H,E ?? A∨B,A??C,B?C, D?C ?D??E,H??A,G∧?H,E ?? ⑴ E P ⑵ ?D??E P ⑶ ??D T ⑴⑵ I ⑷ D T ⑶ E ⑸ D?C P ⑹ C T ⑷⑸ I ⑺ A??C P ⑻ ?A T ⑹⑺ I ⑼ A∨B P ⑽ B T⑻⑼ I 结果是秘书谋害了经理。 二.条件论证 定理1-7.1 如果H1∧H2∧...∧Hn∧R?Ｓ，则 H1∧H2∧...∧Hn ? R→S 证明 因为H1∧H2∧...∧Hn∧Ｒ?Ｓ 则 (H1∧H2∧...∧Hn∧R)?S 是永真式， 即 ?(H1∧H2∧...∧Hn∧R)∨S 是永真式， 即?H1∨?H2∨...∨?Hn∨?R∨S 是永真式， 得(?H1∨?H2∨...∨?Hn)∨(R→S)是永真式， 即?(H1∧H2∧...∧Hn)∨(R→S) 是永真式， 所以 (H1∧H2∧...∧Hn)?(R→S)是永真式。 即 H1∧H2∧...∧Hn ? R→S。 此定理告诉我们，如果要证明的结论是蕴涵式(R→S)形式，则可以把结论中蕴涵式的前件R作为附加前提，与给定的前提一起推出后件S即可。 我们把上述定理写成如下规则： 规则CP( Conditional Ｐroof)： 如果H1∧H2∧...∧Hn∧R ? S，则 H1∧H2∧...∧Hn ? R→S 下面我们用条件论证方法求证例题４ P→(Q→S),?R∨P,Q ? R→S 例题５ 用条件论证，证明例题４ P→(Q→S),?R∨P,Q ? R→S 证明 (1) R P(附加前提) (2) ?R∨P P (3) P T (1)(2) I (4) P→(Q→S) P (5) Q→S T (3