离散数学概论 第2版 第二章 一阶逻辑.ppt

*****直接证明法(续)证明①r?s前提引入②?s前提引入③?r①②拒取式④(púq)?r前提引入⑤?(púq)③④拒取式⑥?pù?q⑤置换*构造证明之二——附加前提证明法欲证明前提：A1,A2,…,Ak结论：C?B等价地证明前提：A1,A2,…,Ak,C结论：B?理由：(A1ùA2ù…ùAk)?(C?B)??(A1ùA2ù…ùAk)ú(?CúB)??(A1ùA2ù…ùAkùC)úB?(A1ùA2ù…ùAkùC)?B例构造下面推理的证明:2是素数或合数.若2是素数，则是无理数.若是无理数，则4不是素数.所以，如果4是素数，则2是合数.用附加前提证明法构造证明*附加前提证明法(续)推理的形式结构前提：púq,p?r,r??s结论：s?q解设p：2是素数，q：2是合数，r：是无理数，s：4是素数*附加前提证明法(续)证明①s附加前提引入②p?r前提引入③r??s前提引入④p??s②③假言三段论⑤?p①④拒取式⑥púq前提引入⑦q⑤⑥析取三段论请用直接证明法证明之*构造证明之三——归谬法(反证法)欲证明前提：A1,A2,…,Ak结论：B将?B加入前提，若推出矛盾，则得证推理正确.理由:A1ùA2ù…ùAk?B??(A1ùA2ù…ùAk)úB??(A1ùA2ù…ùAkù?B)括号内部为矛盾式当且仅当(A1ùA2ù…ùAk?B)为重言式。*归谬法(续)例构造下面推理的证明前提：?(pùq)úr,r?s,?s,p结论：?q证明（用归缪法）①q结论否定引入②r?s前提引入③?s前提引入④?r②③拒取式*归谬法(续)⑤?(pùq)úr前提引入⑥?(pùq)④⑤析取三段论⑦?pú?q⑥置换⑧?p①⑦析取三段论⑨p前提引入⑩?pùp⑧⑨合取请用直接证明法证明之(2)请根据下面事实，找出凶手：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⑵?D??E前提⑶??D拒取式⑷D