离散-1-2-命题逻辑(1).ppt

.,1,1.3永真式1.公式的解释,定义1.3.1:设A(P1,Pn)是合式公式，对P1,Pn的一组真值赋值，称为对A的一个解释。,例:设A(P1,P2),其解释有:若B(Q1,Q2,Q3),则其解释有解释的个数与变元的关系：含n个变元的公式有2n种不同的解释。公式的真值表：例:构造(PQ)R的真值表。,.,2,例:构造(PQ)R的真值表,PQR,000001010011100101110111,PQ,00000011,(PQ)R,11111101,公式真值表公式分类,.,3,1.3永真式2.公式的分类,定义:设A是合式公式,则（1）如果A在任何解释下均为真，则称A为永真式或重言式；（2）如果A在任何解释下均为假，则称A为永假式或矛盾式；（3）如果至少有一个解释使A为真，则称A为可满足式；代入规则（定理1.3.1):永真式的代入实例是永真式。,.,4,定理1.3.1：永真式的代入实例是永真式。,证明：设A(P1,Pn)是永真式，A是用Bi取代Pi(1in)所得到的代入实例，对A的任一解释I,A是永真式，A在解释I下的真值为真，由I的任意性得：A也是永真式。,此定理得逆是否成立？,.,5,证明:C与D的不同仅在于C中A的一处或几处出现换成B,并且AB对C,D中变元的任一组真值赋值，C与D的真值相同，CD为永真式，即CD例：证明P(PQ)(PQ)证明:P,基本恒等式,定理:设A是C的子公式且AB，若用B替换C中A的一处或几处出现得到公式D,则CD.,同一律,PT,补余律,P(QQ),分配律(PQ)(PQ)P(PQ)(PQ),.,6,基本恒等式,用替换规则证明的例子,证明:(Q(P(PQ)(QP).解:我们有(QP)(QP)和(P(PQ)P(吸收律)用(P(PQ)替换第一处出现的P，于是由替换规则可得(Q(P(PQ)(QP).基本逻辑恒等式中字符P,Q,R可以是命题变元也可以是命题公式；T,F可以是真、假命题也可以是重言式、永假式.,.,7,1.3永真式3.公式间的等价关系(2),例：证明（AB)(BA)是永真式。证明:(AB)(BA)蕴涵等值式(AB)(BA),基本恒等式,德摩根律、双重否定律(AB)(BA),分配律(ABA)(BBA),交换律、结合律、补余律T（AB)(BA)是永真式,.,8,1.3永真式4.对偶原理（1）,对偶式：设A是仅含、的合式公式，在A中将和互换、T和F互换,所得到的公式A*称为A的对偶式。例：求A(P,Q,R)=(PQ)R的对偶式解:A(P,Q,R)(PQ)RPQRPQR对偶式为（PQ)R对偶式的性质：(A*)*=A,.,9,定理:设A(P1,Pn)是仅含,的公式，则A(P1,Pn)A*(P1,Pn),证明:若A为P、T或F,则A*为P,F或T,此时有:PP,TF和FT,结论成立.设对A1,A2结论成立,当A为A1,时，A*为A*1A(A1)(A*1(P1,Pn)A*(P1,Pn)若A为A1A2，则A*为A*1A*2A(A1A2)A1A2A*1(P1,Pn)A*2(P1,Pn)（A*1A*2)(P1,Pn)A*(P1,Pn)同理可证当A为A1A2时，结论也成立,.,10,定理1.3.4(对偶定理)：设A为是仅含,的合式公式,若AB，则A*B*(说明基本逻辑恒等式会成对出现)证明：设AB,则AB,1.3永真式4.对偶原理（2）,AB是永真式。,ABA*(P1,Pn)B*(P1,Pn)(定理1.3.3)A*(P1,Pn)B*(P1,Pn)-也是永真式。用Pi取代Pi(1in),得到的一个代入实例：A*(P1,Pn)B*(P1,Pn)由代入规则（定理1.3.1)知：A*B*是永真式。A*B*,.,11,1.3永真式5.永真蕴涵关系(1),定义：若AB是永真式，则称A永真蕴涵B，记作AB证明方法:真值表、等价推导、前真导后真、后假导前假例1：证明P(PQ)Q证明：若P(PQ)为T,则P为T且(PQ)为T。,Q也为T。,因此，P(PQ)Q是永真式，,故P(PQ)Q。,例2：证明(PQ)(QR)PR证明：若PR为F,则P为T，R为F,若Q为T，则QR为F,(PQ)(QR)为F,若Q为F，则PQ为F,(PQ)(QR)为F,(PQ)(QR)PR永真，因此，(PQ)(QR)PR,.,12,永真蕴涵关系的性质：自反性：对任意公式A,有AA传递性：若AB,BC,则AC反对称性：AB当且仅当AB且BA如何证明反对称性?若AB,则BA证明：若B为T,1.3永真式5.永真蕴涵关系(2),则B为F,AB,A为F,A为T，,因此，BA,定理1.3.5:设A,B为仅含,的公式，若AB，则B*A*,.,13,基本永真蕴涵式：,附加式：PPQ化简式：PQP假言推论：P(PQ)Q假言三段论:(PQ)(QR)PR析取三段论:P(PQ)Q拒取式：Q(PQ)P,蕴涵关系,.,14,定理:设A,B为仅含,的公式，若AB，则B*A*,证明：设P1,Pn为出现在A和B的所有变元，AB，则有BA,BA是永真式,BAB*(P1,Pn)A*(P1,Pn)B*(P1,Pn)A*(P1,Pn)永真。现用Pi取代Pi(1in),得到上式的一个代入实例:B*(P1,Pn)A*(P1,Pn)即B*A*仍为永真式B*A*,.,15,基本逻辑恒等式(P9),双重否定律：PP补余律：PPTPPF等幂律：PPPPPP交换律：PQQPPQQP结合律:(PQ)RP(QR)(P