离散数学1-8

离散数学DiscreteMathematics陈明Email:mingchen_gang@163.com信息科学与工程学院二零一零年九月§1—8推理理论在数学和其它自然科学中，经常要考虑从某些前提A1，A2，…，An能够推导出什么结论。例如：从分子学说，原子学说，能够得到什么结论；从光的波动学说，能得到什么结论。我们一般地要对“假设”的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 作深入 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，并推究其间的关系，从而得到结论。但也有一些推理，只需分析假设中的真值和联结词，便可获得结论。第一章命题逻辑在实际应用的推理中，我们常常把本门学科的一些定律、定理和条件，作为假设前提，尽管这些前提在数理逻辑中实非永真，但在推理过程中，却总是假设这些命题为T，并使用一些公认的规则，得到另外的命题，形成结论，这种过程就是论证。如果6是偶数，则7被2除不尽。或5不是素数，或7被2除尽。但5是素数。所以6是奇数。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题，结论则是从前提出发通过推理而得到的新命题。要研究推理，首先应该明确什么样的推理是有效的。符号化下列格式并且验证论证的有效性：如果6是偶数，则7被2除不尽。或5不是素数，或7被2除尽。但5是素数。所以6是奇数。解：设P：6是偶数，Q：7被2除尽；R：5是素数则符号化为：(P->┐Q)∧(┐R∨Q)∧(R)┐P验证：设(P->┐Q)∧(┐R∨Q)∧(R)为T，那么R为T，并且┐R∨Q为T，故Q为T，再因为P->┐Q为T，得到┐P为T。1.定义定义1-8.1设A和C是两个命题公式，当且仅当A→C为一重言式，即AC，称C是A的有效结论。或C可由A逻辑地推出。3.论证过程判别有效结论的过程就是论证过程。2.推广有效结论定义可以推广到有n个前提的情况。设H1，H2，……，Hn，C是命题公式，当且仅当H1∧H2∧…∧HnC(A)称C是一组前提H1，H2，……，Hn的有效结论。一、有效结论注意：必须把推理的有效性和结论的真实性区别开。二、证明方法1.真值表法2.直接证法3.间接证法1.真值表法设P1，P2，…，Pn是出现于前提H1，H2，…，Hn和结论C中的全部命题变元，假定对P1，P2，…，Pn作了全部的真值指派，这样就能对应地确定H1，H2，…，Hn和C的所有真值，列出这个真值表，即可看出(A)式是否成立。H1，H2，…，Hn真值均为T的行，对于每一个这样的行，若C也有真值T，则(A)式成立；或者看C的真值为F的行，在每一个这样的行中，H1，H2，…，Hn的真值至少有一个为F，则(A)式也成立。例题1一份统计表格的错误或者是由于 材料 关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料 不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。解设各命题变元为P：统计表格的错误是由于材料不可靠。Q：统计表格的错误是由于计算有错误。本例可译为：Q是前提P∨Q，┐P的有效结论，即┐P∧(P∨Q)Q我们列出真值表1-8.1如下从表上看到只有在第三行P∨Q和┐P的真值都为T，这时Q的真值亦为T。故(P∨Q)∧(┐P)Q成立。或者考察Q的真值为F的情况，在第二行和第四行，其相应的P∨Q或┐P中至少有一真值为F，故亦说明(P∨Q)∧(┐P)Q成立。例题2如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可得到解答。解若设P：张老师来了。Q：李老师来了。R：这个问题可以得到解答。上述语句可翻译成下述命题关系式(P→R)∧(Q→R)∧(P∨Q)R列出真值表1-8.2从真值表看到，P→R，Q→R，P∨Q的真值都为T的情况为第一行、第三行和第五行，而在这三行中R的真值均为T。故(P→R)∧(Q→R)∧(P∨Q)R。真值表法证明前真：看后真；后假：前至少有一个假。我们知道判断推理是否正确的方法，已经有真值表法、等价演算法，主范式法。当推理中包含的命题变元较多时，这些方法的演算量太大，给推理带来了困难。为此引入命题逻辑的推理理论。命题逻辑的推理是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知前提，或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。它有两种方法：直接推理和间接推理。二、证明方法1.真值表法2.直接证法3.间接证法直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。真值表法是把所给前提一起使用，而直接证法则是不断使用前提和前面推出的结论，构成推导序列，是把前提一步一步拿来使用。P规则前提在推导过程中的任何时候都可以使用。T规则在推导中，如果有一个或多个公式，重言蕴含着公式S，则公式S可作为条件引入推导之中。2.直接证法常用的蕴含式（43页表1-8.3）常用的等价式(43页表1-8.4)合取引入规则：任意两个命题公式A，B可以推出A∧B用直接推理法证明(p→q)∧(q→r)∧pr）证明：⑴p→qP⑵pP⑶qT⑴,⑵I（假言推理）⑷q→rP⑸rT⑶,⑷I（假言推理）例题1证明(P∨Q)∧(P→R)∧(Q→S)S∨R(8)S∨RT(7)E（E16）(7)┐S→RT(5),(6)I（I13）(6)P→RP(5)┐S→PT(4)E（E18）(4)┐P→ST(2),(3)I（I13）(3)Q→SP(2)┐P→QT(1)E（E16）证法1(1)P∨QP例题1证明(P∨Q)∧(P→R)∧(Q→S)S∨R证法2(1)P→RP(2)P∨Q→R∨QT(1)I（I15）(3)Q→SP(4)Q∨R→S∨RT(3)I（I15）(5)P∨Q→S∨RT(2),(4)I(I13)(6)P∨QP(7)S∨RT(5),(6)I（I11）例题2证明(W∨R)→V,V→C∨S,S→U,┐C∧┐U┐W(13)┐WT(12)I(12)┐W∧┐RT(11)E(11)┐(W∨R)T(7),(10)I(10)(W∨R)→C∨ST(8),(9)I(9)V→C∨SP(8)(W∨R)→VP(7)┐(C∨S)T(6)E(6)┐C∧┐ST(4),(5)I(5)┐CT(1)I(4)┐ST(2),(3)I(3)S→UP(2)┐UT(1)I证明(1)┐C∧┐UP真值表法前真：看后真；后假：前至少有一个假。直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。P规则前提在推导过程中的任何时候都可以使用。T规则在推导中，如果有一个或多个公式，重言蕴含着公式S，则公式S可作为条件引入推导之中。直接证法区别：真值表法是把所给前提一起使用；而直接证法则是不断使用前提和前面推出的结论，构成推导序列，是把前提一步一步拿来使用。证明：(W∨R)→V,V→C∨S,S→U,┐C∧┐U┐W二、证明方法1.真值表法2.直接证法3.间接证法(1)定义定义1-8.2假设公式H1，H2，…，Hn中的命题变元为P1，P2，…，Pn，对于P1，P2，…，Pn的一些真值指派，如果能使H1∧H2∧…∧Hn的真值为T，则称公式H1，H2，…，Hn是相容的。如果对于P1，P2，…，Pn的每一组真值指派使得H1∧H2∧…∧Hn的真值均为F，则称公式H1，H2，…，Hn是不相容的。3.间接证法(2)证法可以把不相容的概念应用于命题公式的证明。设有一组前提H1，H2，…，Hn，要推出结论C，即证H1∧H2∧…∧HnC，记作SC，即┐C→┐S为永真，或C∨┐S为永真，故┐C∧S为永假。因此要证明H1∧H2∧…∧HnC，只要证明H1，H2，…，Hn与┐C是不相容的。类似于假定┐C为真，推出矛盾。　　　也就是反证法。例题3证明A→B，┐(B∨C)可逻辑推出┐A(7)B∧┐B(矛盾)T(5),(6)I(6)┐BT(4)I(5)BT(1),(2)I(4)┐B∧┐CT(3)E(3)┐(B∨C)P(2)AP(附加前提)(1)A→BP证明例题4（eg1）证明(P∨Q)∧(P→R)∧(Q→S)S∨R(13)(P∧┐R)∧┐(P∧┐R)(矛盾)T(9),(12)I(12)┐(P∧┐R)T(11)E(11)┐P∨RT(10)E(10)P→RP(9)P∧┐RT(2),(8)I(8)(┐S∧┐R)→(P∧┐R)T(7)I(7)┐S→PT(6)E(6)┐P→ST(4),(5)I(5)Q→SP(4)┐P→QT(3)E(3)P∨QP(2)┐S∧┐RT(1)E(1)┐(S∨R)P(附加前提)证明(3)CP规则（结论为R→C时使用）间接证法的另一种情况是：若要证H1∧H2∧…∧Hn(R→C)。设H1∧H2∧…∧Hn为S，即证S(R→C)或S(┐R∨C)，故S→(┐R∨C)为永真式。因为S→(┐R∨C)┐S∨(┐R∨C)(┐S∨┐R)∨C┐(S∧R)∨C(S∧R)→C，所以若将R作附加前提，如有(S∧R)C，即证得S(R→C)。由(S∧R)C，证得S(R→C)称为CP规则。例题5证明A→(B→C)，┐D∨A，B重言蕴含D→C(8)D→CCP(7)CT(5),(6)I(6)BP(5)B→CT(3),(4)I(4)A→(B→C)P(3)AT(1),(2)I(I10)(2)┐D∨AP(1)DP(附加前提)证明例题6设有下列情况，问结论是否有效？(a)或者是天晴，或者是下雨。(b)如果是天晴，我去看电影。.(c)如果我去看电影，我就不看书。结论：如果我在看书则天在下雨。解若设M：天晴。Q：下雨。S：我看电影。R：我看书。故本题即证：M∨Q，M→S，S→┐R，推出R→Q(1)RP(附加前提)(2)S→┐RP(3)R→┐ST(2)E(4)┐ST(1),(3)I(5)M→SP(6)┐MT(4),(5)I(10)(┐M→Q)∧(┐Q→M)T(9)E(11)┐Q→MT(10)I(12)┐M→QT(11)E(13)QT(6),(12)I(14)R→QCP(8)┐(MQ)T(7)E(9)M┐QT(8)EM∨Q，M→S，S→┐R，推出R→Q真值表法：前真：看后真；后假：前至少有一个假。直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。间接证法要证明H1∧H2∧…∧HnC，只要证明H1，H2，…，Hn与是┐C是不相容的。要证明H1∧H2∧…∧Hn(R→C)。如能证明H1∧H2∧…∧Hn∧RC，即证得H1∧H2∧…∧Hn(R→C)，这个证明称为CP规则。命题推理方法作业P46-P47(1)a（真值表法）、c，d(2)a、d。（要求用两种方法）(3)c(4)b(5)c第一章内容回顾 一、知识点1．命题的概念、表示方法。2．命题公式的递归定义，自然语言翻译成命题公式3．真值表的构造、命题公式等价的概念。4．重言式与蕴涵式的定义，逻辑等价与逻辑蕴涵的意义和证明方法。常用的逻辑等价公式和逻辑蕴涵公式。5．命题公式的对偶式、合取范式、析取范式、主合取范式、主析取范式。逻辑小项、逻辑大项。任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。6．命题逻辑的推理理论，主要的推理方法：真值表法、直接证明法、间接证明法。常用推理规则：P规则、T规则、CP规则。二、要求1．识记命题表示方法、真值判断、命题公式的递归定义。2．领会联结词真值确定、翻译、命题公式的等价性和蕴涵性证明、任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。3．简单应用命题逻辑推理规则。个人观点供参考，欢迎讨论