3-命题逻辑-2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,上海第二工业大学 计算机学院软件系 王帅,重言式、等价式和蕴含式,公式的分类,一个命题公式，如果对于所有指派,命题公式的值都是,T,，则称该公式为,重言式,(,永真式,),命题公式的值都是,F,，则称该公式为,矛盾式,(,永假式,),至少存在一种真指派，则称该公式为,可满足的,至少存在一种假指派，则称该公式为,非永真的,例：重言式,P,P,矛盾式,P,P,、,(P,Q),P,P,Q,P,Q,P,Q,T,T,T,T,T,F,F,F,F,T,T,T,F,F,T,T,P,Q,P,Q,P,(,P,Q,),P,T,T,T,F,F,T,F,F,F,F,F,T,F,T,F,F,F,F,T,F,P,Q,P,Q,(P,Q),P,Q,P,Q,(P,Q),(P,Q),T,T,T,F,F,F,F,T,T,F,F,T,F,T,T,T,F,T,F,T,T,F,T,T,F,F,F,T,T,T,T,T,PQ,是可满足式、是非永真的,(PQ)P,是永假式,(PQ)(PQ),是永真式,公式的分类,定理,任何两个重言式的合取或析取，仍然是重言式,任何两个矛盾式的合取或析取，仍然是矛盾式,对一个重言式的同一分量都用某个公式置换，得到的仍然是重言式,对一个矛盾式的同一分量都用某个公式置换，得到的仍然是矛盾式,公式的分类,例：,P,P,、,Q,Q,是重言式,所以,(,P,P),(,Q,Q),、,(,P,P),(,Q,Q),都是重言式,P,P,是重言式,用公式,P,Q,置换,P,，得到的,P,Q,(P,Q),也是重言式,等价公式,定义,给定两个命题公式,A,和,B,，设,P,1,P,2,P,n,是所有出现在,A,和,B,中的原子变元，若给,P,1,P,2,P,n,任一组真值指派，,A,和,B,的值都相同，则称,A,和,B,是等价的，或逻辑相等的，记作,A,B,由上节真值表中的例子，可知,P,Q,P,Q,等价公式,命题公式之间的等价关系具有自反性、对称性、传递性。即：,对任意公式,A,、,B,、,C,，有：,A,A,若,A,B,，则,B,A,若,A,B,，,B,C,，则,A,C,判断两个命题公式是否等价,真值表法,适用于公式中的变元较少的情况,利用等价的传递性来推导公式（等值演算）,常用的公式 见教材,9,页基本等式（,1,）,-,（,24,）,特别重要的等价公式,等价公式,-,例题,求证,Q,(P(PQ),QP,证明,1,Q,(P(PQ),Q,(P(PQ),(,Q,PP)(,Q,PQ),(,Q,P)T,Q,P,QP,证明,2,根据吸收律,P(PQ)P,所以,Q,(P(PQ),QP,命题逻辑的等式推理,推理理论,推理是利用一些推理规则由前提推出结论的思维过程。,在命题逻辑中，前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。,在传统数学中定理的证明均是由前提（已知条件，全是真命题）推出结论（亦全是真命题），这样的结论称为,合法结论,。,数理逻辑有所不同，它着重研究的是推理的过程，这种过程称为演绎或形式证明。在过程中使用的推理规则必须是公认的且要明确列出，而对于作为前提和结论的命题并不一定要求它们全是真命题，这样的结论称为,有效结论,。,命题逻辑的等式推理,等式推理由三部分组成,基本等式,(,是推理的基础,),推理规则,代入规则,替换规则,推理过程,代入规则,把等价公式中某个变元的所有出现用另一命题公式代入后，等价关系不变。这个规则称为代入规则,例：因为,A,B,A,B,用,PQ,代入,A,用,R,S,代入,B,得,到新的等价公,式,(PQ)(,R,S,),(PQ)(,R,S,),置换规则,设,A,是一个命题公式，,C,是,A,的子公式，且,C,D,，若将,A,中出现子公式,C,的某处（未必是全部）替换为,D,后得到公式,B,，则,AB,例如,对公式,(,P,Q,),R,因为,PQ,P,Q,由置换规则即得重言式,(,P,Q,),R,(,P,Q,),R,推理过程,等式推理过程是一个有命题公式,P,经等式推理，最终得到另一个等价的命题公式,Q,的过程,等价公式,-,例题,求证,(P,(QS)(,P,(QS),QS,证明,(P,(QS)(,P,(QS),(,(QS)P)(QS),P),(QS)(P,P),(QS)T,QS,等价公式,-,例题,求证,Q,(P,Q)P),T,证明,Q,(P,Q)P),Q,(,(P,Q),P),Q,(,P,Q),P),Q,(,P,P)(,Q,P),Q,(T(,Q,P),Q,(,Q,P),(Q,Q),P,T,P,T,等价公式,-,例题,求证,(A,B)C)(B(DC),(B,(DA)C,证明,：,左边,(,(A,B)C)(,B,(DC),(,A,BC)(,B,CD),(,BC,A,)(,B,CD),(,BC)(,A,D),右边,(B,(DA)C,B,(,DA)C,B,(D,A)C,(,BC)(,A,D),左边,重言式,-,定理,A,、,B,是两个命题公式，,A,B,当且仅当,A,B,是重言式,证明,：（,根据等价和双条件的定义证明）,（,1,）若,A,B,，则,A,B,有相同的真值，即,A,B,永真,（,2,）若,A,B,是重言式，即,A,B,永真，所以,A,B,的真值相同，即,A,B,利用该定理，可以证明两个命题公式等价,例题,证明,(P,Q)(P,Q),P,证：,(,(P,Q)(P,Q),P,(,(,P,Q)(,P,Q),P,(,P,(Q,Q),P,(,P,F,),P,P,P,T,注意,和,是两个完全不同的符号,区别：,不是命题联结词。,是命题联结词,联系：,A,B,当且仅当,A,B,是重言式,蕴含式,定义,当且仅当,P,Q,是一个重言式时，我们称“,P,蕴含,Q”,，记为,P,Q,注意,也不是命题联结词,判定蕴含的方法,分析,要判断,P,Q,是否成立，也就是判断,P,Q,是否为永真,根据,P,Q,的真值表,P,Q,P,Q,T,T,T,T,F,F,F,T,T,F,F,T,要想使,PQ,取真，,需要排除第二种情况,方法一：,假定前件,P,为真，检查此情况下的,Q,是否也为真，如果,Q,也是真，则说明,PQ,取真，,PQ,是重言式，从而有,P,Q,方法二：,假定后件,Q,为假，检查此情况下的,P,是否有可能为真，如果,P,不可能是真，则说明,PQ,取真，,PQ,是重言式，从而有,P,Q,判定蕴含的方法,方法一,设前件,P,为,T,如果证出后件,Q,为,T,，则,P,Q,永真,方法二,设后件,Q,为,F,如果证出前件,P,为,F,，则,P,Q,永真,方法三,真值表法,方法四,公式推导,判定蕴含,-,例题,证明,P,(PQ),Q,方法一,：（前真推后真,）,设,P,(PQ),为,T,，,则,P,为,T,，且,PQ,为,T,P,为,F,，,Q,为,T,P,(PQ),Q,永真,P,(PQ),Q,判定蕴含,-,例题,证明,P,(PQ),Q,方法二：（后假推前假）,设,Q,的真值为,F,，,若,P,为,T,，则,P,为,F,P,(PQ),为,F,若,P,为,F,，则,PQ,为,F,P,(PQ),为,F,当,Q,为,F,时，无论,P,为,T,或,F,，都有,P,(PQ),为,F,P,(PQ),Q,永真,P,(PQ),Q,判定蕴含,-,例题,证明,P,(PQ),Q,方法三：（真值表法）,P,Q,P,PQ,P,(PQ),P,(PQ),Q,T,T,F,T,F,T,T,F,F,T,F,T,F,T,T,T,T,T,F,F,T,F,F,T,判定蕴含,-,例题,证明,P,(PQ),Q,方法四：（公式推导）,P,(PQ),Q,(P,(PQ),Q,(P,(PQ),Q,P,(,P,Q),Q,(,P,P)(,P,Q),Q,(T,(,P,Q),Q,(,P,Q),Q,P,(,Q,Q),P,T,T,P,(PQ),Q,判定蕴含,-,练习,用各种方法证明,(P,Q)Q,PQ,蕴含与等价,P,Q,(PQ)(QP),从这个式子中可以看出,与,有紧密地联系,若,PQ,，则,PQ,永真，即,(PQ)(QP),永真,PQ,永真，,且,QP,永真,PQ,且,QP,反之，若,PQ,且,QP,，则,PQ,永真且,QP,永真,(PQ)(QP),永真，即,PQ,永真,PQ,蕴含与等价,-,定理,设,P,、,Q,为任意两个命题公式，,P,Q,的充要条件是,P,Q,且,Q,P,蕴含的性质,设,A,、,B,、,C,为任意公式,若,A,B,，且,A,是重言式，则,B,必是重言式,若,A,B,，,AC,，则,A,(B,C),若,A,B,，,CB,，则,(,A,C),B,对任意公式,A,，有,AA,（蕴含的自反性）,若,A,B,，,BC,，则,A,C,（蕴含的传递性）,蕴含的性质,证明蕴含的传递性,若,A,B,，,BC,，则,A,C,证明,A,B,，,BC,AB,永真，,BC,永真,AC,AC(,AC)(,BB),(,AC,B)(,ACB),(,A(,BC)(,AB)C),(,A(B,C)(A,B)C),(,AT)(TC),TTT,即,AC,永真，,A,C,常用的蕴含公式,23,页公式（,1,）,-,（,8,）,特别重要的蕴含公式,命题逻辑中的蕴含推理,蕴含式,A,B,表示“如果,A,为真则,B,必为真”,如果把,A,看作前提，,B,作为结论，则,A,B,可,表示“若前提,A,为真必可推得结论,B,为真”,我们用符号“,”表示推理、推出的意思，则,P1,P2,Pn,Q,表示 以,P1,P2,Pn,为前提可以推出结论,Q,A,B,也就可以表示为,A,B,蕴含推理规则,在蕴含推理中之允许使用三种规则：,P,规则：前提引入规则,在推理过程中可以随时使用已知前提,T,规则：推理引入规则,在推理过程中可使用基本蕴含式和等价式等推理规则,CP,规则：附加前提引入规则,如果待证结论形如,AB,，则可以把结论中的前件,A,作为附加前提引入，即把,A,作为已知，把,B,作为结论,蕴含推理,-,例,例：试证,P,Q,Q,R,P,R,。,证明,(1),P,Q,（,P,规则）,(2),P,（,P,规则）,(3),Q,（,(1),(2),规则）,(4),Q,R,（,P,规则）,(5),R,（,(3),(4),规则）,蕴含推理,-,例,例,:,证明,P,Q,Q,R,P,M,M,R,(,P,Q,),本例要复杂得多。分析如下,:,1),要证明的结论是,R,(,P,Q,),因为,P,Q,是前提,所以只要能推出,R,就可以由,67,推得,R,(,P,Q,);,2),因为,R,仅含在前提,Q,R,中,且是该蕴含式的后件,如果能先推出前件,Q,则可由,69,得出,R,;,3),除前提,Q,R,外,Q,仅含在前提,P,Q,中,若能推得,P,则由,I,52,和前提,P,Q,可得出,Q,;,4),由前提,P,M,和,M,根据,55,即可推得,P,。由此问题得到解决,将以上分析的步反过来按证明的格式书写,就可以得到证明的过程,证明,(1),M,（,P,）,(2),P,M,（,P,）,(3),P,（,T(1),(2),）,(4),P,Q,（,P,）,(5),Q,（,T(3),(4),）,(6),Q,R,（,P,）,(7),R,（,T(5),(6),）,(8),R,(,P,Q,)(T(7),(4),）,试证,P,(,Q,S),R,P,Q,R,S,证明,(1),P,(,Q,S),（,P,）,(2),P,Q,S,（,T(1),）,(3),Q,P,S,（,T(2),）,(4),Q,(,P,S),（,T(3),）,(5),Q,（,P,）,(6),P,S,（,T(4),(5),）,(7),R,P,（,P,）,(8),R,P,（,T(7),）,(9),R,S,（,T(6),(8),）,该题也可用,CP,规则证明,蕴含推理,-,例,蕴含推理,-,例,试证,P,(,Q,S),R,P,Q,R,S,证明,(1),R,P,（,P,）,(2),R,P,（,T(1),）,(3),R,（,P