离散数学-1-8推理理论.ppt

1,第一章命题逻辑,1-8推理理论授课人：李朔Email:chn.nj.lS,2,在数学和其它自然科学中，经常要考虑从某些前提A1、A2、An出发，能推导出什么结论。数理逻辑的主要任务是用逻辑的方法研究数学中的推理。所谓推理是指从前提出发，应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。要研究推理，首先应该明确什么样的推理是有效的或正确的,3,一、有效推理,假设一些命题为，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。定义1-8.1设A和C是2个命题公式，当且仅当AC为一重言式，即AC，则称C为A的有效结论。或C可由A逻辑的推出。A叫做C的前提。上述定义可以推广到n个前提的情况：设H1，H2，Hn,C是n+1个命题公式,当且仅当H1H2HnC，称C是一组前提H1，H2，Hn的有效结论。*判断有效结论的过程就是论证过程，基本方法是真值表法、直接证法、间接证法。,4,二、真值表法,由定义1-8.1可以看出，要证明C是一组前提H1，H2，Hn的有效结论，只需证明H1H2HnC为重言式。而证明一个公式为重言式，可以用真值表、等值演算、主析(合)取范式或已知的蕴含式等方法进行。用等价演算和主析(合)取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。（1）真值表法设P1，P2，Pn出现于前提H1，H2，Hm和结论C的全部命题变元，假定对P1，P2，Pn作了全部的真值指派，这样就能对应地确定H1，H2，Hn和C的所有真值，列出这个真值表，即可看出H1H2HmC是否成立即找出H1，H2，Hm均为的行，对于每一个这样的行，若C也为,则上式成立。或C为，H1，H2，Hm中起码有一个为,5,二、真值表法,例：分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”。试指出这个推理前提和结论，并证明结论是前提的有效结论。解：令：我有时间。：我去上街。：我去书店买书。根据题意，前提为：，结论为：以下证明是一组前提,的有效结论。即证明：(PQ)(QR)RP,6,二、真值表法,作公式PQ，QR，R，P的真值表从表中可以看出:PQ，QR，R都为1的行(赋值000的行)，P也为1。(或P为0的行(赋值100，101，110，111的行)PQ，QR，R至少有一个为0）所以(PQ)(QR)RP,7,三、命题逻辑的推理理论,当推理中包含的命题变元较多时，真值表法或等值演算法，主析取范式法等方法的演算量太大。给推理带来了困难。为此引入命题逻辑的推理理论。命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。它有两种方法：直接证法（直接推理）和间接证法（间接推理）。,8,直接证法（直接推理）,直接证法（直接推理）基本思想是：由一组前提出发，利用一些公认的规则，根据已知的等价式或蕴含式，推演得到有效结论。公认的推理规则有4条：P规则：前提在推导过程中的任何时候都可以引入使用。T规则：推导中，如果一个或多个公式蕴含着公式S，则公式S可以引入到以后的推理之中。置换规则：在推导过程的任何步骤上，命题公式中的子公式都可以用与之等价的公式置换。(等价式表）合取引入规则：任意两个命题公式A,B可以推出AB常用的蕴含式和等价式见P43表1-8.3表1-8.4,9,直接证法（直接推理）,例题：用直接推理法证明()()()证法1:(1)P-(P规则，引入前提)(2)QT(1)E-(对(1)式T规则,根据E16蕴含等值式)(3)P-(P规则，引入前提)(4)T(2),(3)I-(对(2),(3)式规则，根据I13假言三段论)(5)SPT(4)E-(对()式T规则,根据E16蕴含等值式)(6)P-(P规则，引入前提)(7)SRT(5),(6)I(对(5),(6)式规则，根据I13假言三段论)(8)T(7)E-(对(7)式T规则,根据E16蕴含等值式),10,直接证法（直接推理）,证法2:(1)P(2)RT(1)I(3)P(4)RSRT(3)I(5)SRT(2)(4)I(6)P(7)T(5),(6)I,11,直接证法（直接推理）,用直接推理法证明(PQ)(QR)PR证明：PQPPPQTI假言推理(I11)QRPRTI假言推理(I11),12,间接证法（间接推理）,定义1-8.2假设公式H1，H2，Hm中的命题变元P1，P2，Pn，对于P1，P2，Pn的一些真值指派，如果能使H1H2Hm的真值为，则称公式H1，H2，Hm是相容的。如果对于P1，P2，Pn的每一组真值指派，使H1H2Hm的真值均为，则称公式H1，H2，Hm是不相容的。,13,间接证法（间接推理）,将不相容的概念应用于命题公式的证明(归谬法)设有一组前提H1，H2，Hn，要推出结论C，即要证H1H2HnC，令SH1H2Hn则上式可以简记为SC由永真蕴含的定义有1SCSC两边否定0SCH1H2HnC即要证明C是前提H1，H2，Hn的有效结论，只须证明H1H2HnC0(即H1，H2，Hn与C不相容）这种间接推理方法称为归谬法,14,间接证法（间接推理）,例题证明，(C)可逻辑推出。证明：(1)P(2)P(附加前提）(3)(C)P(4)CT(3)E(E9德摩根律)(5)BT(1),(2)I(I11假言推理)(6)T(4)I(I1简化式)(7)(矛盾）T(5),(6)I(I1合取引入规则),15,间接证法（间接推理）,CP规则间接证法的另一种情况：要证H1H2Hn()。设SH1H2Hn，则上式可以简记为S(AB)由永真蕴含的定义有1S()S()(SR)C(SR)C(SR)CH1H2HnRC即H1H2HnRC所以，要证明H1H2Hn(RC)，只需证明H1H2HnRC，其中R叫做附加前提。*这种间接推理方法称为CP规则。,16,间接证法（间接推理）,例题证明()，,B重言蕴含证明：(1)DP(附加前提）(2)P(3)T(1)(2)I析取三断论(4)()P(5)T(3),(4)I(I11假言推理)(6)P(7)T(5),(6)I(I11假言推理)(8)DCP,17,间接证法（间接推理）,例用CP规则证明：P(QR)，TP，QTR证明：TP(附加前提)TPPPT析取三段论P(QR)PQRT假言推理QPRT假言推理TRCP规则,18,间接证法（间接推理）,例试构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。解：（.将简单命题符号化)设P:小张去看电影。Q:小王去看电影。R:小李去看电影。S:小赵去看电影。(2.找出前题与结论。)前提：(PQ)R,SP,Q，结论：SR）,19,间接证法（间接推理）,故本题即要证明：(PQ)R,SP,Q推出SR证明：(.用CP规则证明)(1)SP(附加前提引入)(2)SPP(3)PT(1)(2)I(析取三段论)(4)(PQ)RP(5)QP(6)PQT(3)(5)I(合取引入规则）(7)RT(4)(6)I(假言推理)(8)SRCP,20,间接证法（间接推理）,例构造下面推理的证明。如果小张守第一垒并且小李向B队投球，则A队将取胜；或者A队未取胜，或者A队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒。因此，小李没有向B队投球。解:设P:小张守第一垒。Q:小李向B队投球。R:A队取胜。S:A队获得联赛第一名。,21,间接证法（间接推理）,前提：(PQ)R,RS,S,P结论：Q证明：(用归谬法)(1)QP(附加前提）(2)RS(3)S(4)RT(2)(3)I(析取三段论)(5)(PQ)RP(6)(PQ)T(4)(5)I(拒取式)(7)PQT(6)E(德摩根律，置换）(8)PP(9)QT(7)(8)I(析取三段论(10)QQ（矛盾）(1)(9)I(合取引入规则）,22,本课小结,有效推理真值表法论证命题逻辑的推理理论直接证法，间接证法（归缪法、规则