离散数学(第三讲教材课件

离散数学（第三讲）1.5 公式的蕴涵1.5.1公式蕴涵的基本概念1.5.2基本蕴涵式1.5.3蕴涵式A B的证明的证明1.5.1 公式蕴涵的基本概念定义1.5.1 设A,B是两个公式,如果AB是永真式,则称A蕴涵B,记作A B.例1.5.11.5.1 公式蕴涵的基本概念设A,B是两个公式，称A B是一个蕴涵式，而称A B是一个等价式，二者有如下的关系：定理1.5.1 设A,B是公式,则A B等价于A B且 B A.由该定理可知，A B是“双向蕴涵”，即A蕴涵B，且B蕴涵A1.5.1 公式蕴涵的基本概念蕴涵式具有如下的性质：定理1.5.2 设A,B,C是公式,那么:(1)A A;(2)若A B,B C,则A C;(3)若A B,A C,则A BC;(4)若A C,B C,则AB C.1.5.2 基本蕴涵式由等价和蕴涵的关系可知，所有的基本等价式都是蕴涵式在数理逻辑中还经常使用下面7个基本蕴涵式:(1)化简式:PQ P,PQ Q (2)附加式:P PQ (3)假言推论:P(PQ)Q (4)拒取式:(PQ)Q P (5)析取三段式:(PQ)P Q (6)假言三段式:(PQ)(QP)PR (7)逆反式:PQ QP1.5.3 蕴涵式A B的证明A B的方法:(1)真值表法:用真值表证明AB 1.该方法的优点是直观明了,缺点是当命题变元较多时,真值表较大.(2)等价演算法:用等价演算证明AB 1.例1.5.31.5.3 蕴涵式A B的证明A B的方法:(3)条件式特点演算法:要证明A B,无非是说明AB是永真式,而由AB的真值特点,AB的真值为0等价于A的真值为1而B的真值为0,除此情况外,AB的真值永远是1.因此,只要排除A为1而B为0的可能性,即可以说明AB是永真式,即A B.为此,有两种两种方式可以进行.假定A为1,推演得到B一定为1;假定B为0,推演得到A一定为0.例1.5.4用条件式特点证明A B是一种行之有效的方法。在有些情况下，其复杂程度远小于用真值表法或等价演算法。1.6 联结词完备集1.6.1其他联结词1.6.2联结词的数目1.6.3联结词完备集6个联结词是否够用？够用，但并不是说用它们就可以简洁而有效地表达所有命题之间、公式之间的联系。尤其是在计算机逻辑电路设计及工程中，需要用到其他的联结词1.6.1 其他联结词定义1.6.1 设P和Q是命题,复合命题 PQ (PQ)称为”P和Q与非”.真值表如表1.6.11.6.1 其他联结词定理1.6.1 设P是Q公式,那么:(1)PP P(2)PQ QP(3)(PQ)(PQ)PQ(4)(PP)(QQ)PQ(5)(PP)P 1定义1.6.2 设P和Q是命题,复合命题 PQ (PQ)称为”P与Q的或非”.联结词具有下面的性质定理1.6.2 设P,Q是公式,那么:(1)PP P(2)PQ QP(3)(PQ)(PQ)PQ(4)(PP)(QQ)PQ(5)(PP)P 0定义1.6.3 设P和Q是命题,复合命题 P Q (PQ)称为”P和Q的条件否定”.真值表如表1.6.31.6.3 联结词完备集定义1.6.4 设S是一个联结词的集合.如果任何公式都可以用只包含S中的联结词的等价公式表达,则称S是一个联结词完备集.例1.6.1例1.6.2例1.6.31.6.3 联结词完备集定义1.6.5 设S是一个联结词完备集,如果从S中去掉任何一个联结词以后就不再是联结词完备集,则称S是一个极小联结词完备集.例1.6.4例1.6.5例1.6.1,是一个联结词完备集.例1.6.2,是联结词完备集.例1.6.3,是联结词完备集.例1.6.4,和,都是极小联结词完备集.1.7 公式的对偶1.7.1公式对偶的基本概念1.7.2对偶原理1.7.1 公式对偶的基本概念定义1.7.1 设公式A中只含联结词,将A中的,分别换成,若有0和1则分别换成1和0,所得新的公式称为A的对偶式,记为A*.例1.7.1 写出下列公式的对偶式.(1)P (Q R);(2)(P Q)(P(Q S);(3)P 0如果公式A中除了,以外还有其他的联结词，那么在写A的对偶式之前首先必须先将其他联结词消去，而不能直接将,分别换为 和,将0和1分别换成1和0例1.7.21.7.2 对偶原理定理1.7.1 设P1,Pn是出现在A中的所有命题变元,将A和A*分别记为A(P1,Pn)和A*(P1,Pn),则 A(P1,Pn)A*(P1,Pn)A(P1,Pn)A*(P1,Pn)其中,A*(P1,Pn)表示将 A*中的 P1,Pn分别替换成 P1,Pn而得到的公式.定理1.7.2(对偶原理)设A和B是公式,若 A B,则A*B*1.7.2 对偶原理定理1.7.2(对偶原理)设A和B是公式,若 A B,则A*B*有些情况下，可以利用对偶原理证明一些等价式借助对偶原理可以简化和推演一些命题公式，还可以通借助对偶原理可以简化和推演一些命题公式，还可以通过已知的等价式来证明其他的等价式，简化证明过程。过已知的等价式来证明其他的等价式，简化证明过程。例：若已知例：若已知 (PQ)(PQ)(PQ)PQ)PQPQ 请证明：请证明：(PQ)(PQ)(PQ)PQ)PQPQ设设A*A*、B*B*分别为公式分别为公式A A、B B的对偶式，若的对偶式，若A AB B，则，则A*A*B*B*。定理定理定理定理1.8 公式的范化1.8.1简单合取式与简单析取式1.8.2公式的范式1.8.1 简单合取式与简单析取式定义1.8.1 设P1,Pn是命题变元,公式 A ,其中要么是i要么是i（i,k),则称是简单合取式，称为的合取项定义1.8.设P1,Pn是命题变元,公式 A ,其中 要么是i要么是i（i,k）,则称是简单析取式，称为的析取项定理1.8.1 设A是一个公式,那么:(1)若A简单合取式,则A是永假式等价于A的合取项中同时有某个命题变元及其否定;(2)若A简单析取式,则A是永真式等价于A的析取项中同时有某个命题变元及其否定;请读者思考：该结论可否推广到一般情形？也即下面的结论是否成立？设A1，Ak都是公式，那么：（1）若A A1A2Ak，则A是永真式等价于A1，Ak中有2个互为否定；（2）若A A1A2Ak，则A是永假式等价于A1，Ak中有2个互为否定；1.8.2 公式的范式定义1.8.3 如果公式A是一些简单合取式的析取,则称A是一个析取范式.定理1.8.2 任何公式都存在与之等价的析取范式及合取范式.对于一个给定的公式A,总是可以通过如下步骤求出它的析取范式和合取范式:1,消去公式A中除,以外的联结词,这是因为析取范式及合取范式中只包含3中联结词:,.2,利用得.摩根律,将否定词都换到命题变元之前,换言之,将括号外的都深入到括号内.3,利用分配律等基本等价式将A化成析取范式及合取范式.例1.8.4 求(p(QR)S的析取范式及合取范式.解:(p(QR)S (p(QR)S (pQR)S (pQR)S (pS)(QS)(RS)例1.8.5 求P(pQ)R)的析取范式及合取范式.定理1.8.3 设A是一个公式,那么:(1)A为 ,等价于A的析取范式中每个简单合取式都是永假式.(2)A为 ,等价于A的合取范式中每个简单析取式都是永真式.例 判定下列公式的类型1,(P(PQ)Q2,P(PQ)永真式定义定义1.4.3 1.4.3 设设A A是一个公式是一个公式,如果如果在任何一种解释之下在任何一种解释之下A A的真值的真值都为都为1,1,则称则称A A是永真式是永真式,或称为或称为重言式重言式永假式定义定义1.4.4 1.4.4 设设A A是一个公式是一个公式,如果在任如果在任何一种解释之下何一种解释之下A A的真值都为的真值都为0,0,则则称称A A是永假式是永假式,或称为矛盾式或称为矛盾式.