1.5推理规则和证明方法

《1.5推理规则和证明方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学DiscreteMathematics数理逻辑1.5推理规则与证明方法张晓西北工业大学计算机学院zhangxiao@nwpu.edu.cn2011-1-10引言§什么时候数学论证是正确的？§用什么方法来构造数学论证？§数理逻辑的主要任务是用数学的方法来研究推理过程。§所谓推理是指从前提出发推出结论的思维过程§前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。§要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的。2011-1-10离散数学21.5.1推理规则§前几节所讲的命题演算,本质

2、上和简单的开关代数一样,简单的开关代数是命题演算的一种应用。§现在,我们从另一角度研究命题演算,即从逻辑推理角度来理解命题演算。2011-1-10离散数学34个推理的例子§设x属于实数,P:x是偶数,Q:x2是偶数。例1如果x是偶数,则x2是偶数。P→Q前提x是偶数。Px2是偶数。结论∴Q在每一例子中,横线上的是前提,例2横线下的是结论。右侧是例子的逻辑符表示。如果x是偶数,则x2是偶数。P→Qx2是偶数。Q2011-1-10x是偶数。离散数学∴P4例3如果x是偶数,则x2是偶数。P→Qx不是偶数。Px2不是偶数。∴Q例4如果x是偶数,则x

3、2是偶数。P→Qx2不是偶数。Qx不是偶数。∴P2011-1-10离散数学5例1中,若不管命题的具体涵义,那么它所应用的推理规则就是左侧规则的另一所对应的永真蕴P→Q种写法含式。P,→PPQ推得Q∴P∧(P→Q)⇒QQ从这个永真蕴含式可看出,它正是代表“如果P并且P→Q是真,则Q是真”的意义,这里P和Q表示任意命题。它恰好代表左侧的推理规则。这条推理规则叫假言推理,从形式上看结论Q是从P→Q中分离出来的,所以又叫分离规则。它是推理规则中最重要的一条。2011-1-10离散数学6对任一永真蕴含式AB⇒来说,如果前提A为真,则可保证B为真,因此

4、不难看出,任一个永真蕴含式都可作为一条推理规则。例如,┓P∧(P∨Q)⇒Q代表以下规则,叫做析取三段论。所对应的永真蕴P∨Q含式。或P，P∨Q推得Q。┓P∧(P∨Q)⇒QP∴Q2011-1-10离散数学7下边举一个例子,说明这条推理规则是正确的。设P:他在钓鱼,Q:他在下棋。他在钓鱼或下棋P∨Q他不在钓鱼P∴Q∴他在下棋这样,就可给出以下定义:2011-1-10离散数学8有效结论定义1.4-1若H∧H∧…∧H⇒C,则称C是H,H,…,12n12H的有效结论。n特别若AB⇒,则称B是A的有效结论。定义说明:若H∧H∧…∧H⇒C,则从H∧H∧

5、…∧H推出12n12nC,这样的推理是正确的。2011-1-10离散数学9注意§前提为真时,才保证结论C为真;前提为假时,C可能真也可能假§AC⇒，则C是正确的×AC⇒，并且A为真，则C为真√§推理正确不等于结论为真§只要不出现真值表中1→0的情况，推理就是正确的。§有效是指结论的推出是合乎推理规则的，判别有效结论的过程就是论证过程。2011-1-10离散数学10由有效结论定义可知：例2所以错误,是Q∧(P→Q)→P不是永真蕴含式,不能用作推理规则,换言之,P不是Q和(P→Q)的有效结论。这种错误叫肯定后件的错误。例3所以错误,其理由类似于

6、例2,这种错误叫做否定前件的错误。2011-1-10离散数学11肯定/否定前件与肯定/否定后件§肯定前件必定肯定后件（假言推理）P∧(P→Q)⇒Q§否定后件必定否定前件（拒取式）┓Q∧(P→Q)⇒┓P2011-1-10离散数学12判别有效结论的方法（证明的方法）§真值表法、等值演算法、主析取范式法（比较繁琐）§直接证明法§间接证明法（1.5.2介绍）2011-1-10离散数学13真值表法§设P,P,…,P是出现于前提H1,H2,…,Hm和结12n论C中的全部命题变元，假定对P,P,…,P作了全12n部的真值指派，这样就能对应地确定H1,H2

7、,…,Hm和C的所有真值，列出这个真值表，即可看出⇒H1∧H2∧…∧HnC式是否成立。2011-1-10离散数学14H1∧H2∧…∧HnC的真值表⇒PQRH1H2…HnCH1∧H2∧…∧Hn→C0001111100101101112011-1-10离散数学15直接证明法(演绎法)§直接证法就是由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。§P规则:前提在推导过程中的任何时候都可以引入使用。§T规则:在推导中，如果有一个或多个公式、重言蕴含着公式S，则公式S可以引入推导中。2011-1-10离散数学16推理

8、流程结束Y引入事实事实库规则匹配新事实事实=结论？触发规则N公理库将事实加入到事实库中2011-1-10离散数学17表1.5-1最常用的推理规则2011-1-10离散数学18可使