离散数学第一章第三节分解课件.ppt

1、第1-3讲 蕴含式1.蕴含式2.证明蕴含式的方法3.证明蕴含式的例子4.基本蕴含式5.蕴含式的性质6.等价式和蕴含式的联系7.其它联结词8.最小联结词集9.作业11、蕴含式定义设、为命题公式，当且仅当是一个重言式，称“蕴含”，记作。n 对而言，称为逆换式，为反换式，为逆反式。P Q0 0 1 1 1 1 1 10 1 1 0 1 0 0 11 0 0 1 0 1 1 01 1 0 0 1 1 1 1由上表中可以看出：由上表中可以看出：PQQP；QPPQ。n 如同等价如同等价一样，一样，也不是逻辑联结词。也不是逻辑联结词。仅仅表仅仅表示示是永真式。是永真式。22、证明蕴含式的方法n分析：要证分析

2、：要证，即要证，即要证为重言式。对为重言式。对来说，除为真、为假时，来说，除为真、为假时，的真值为假外，其的真值为假外，其余情况余情况的真值皆为真。故要证的真值皆为真。故要证，只须对条，只须对条件命题件命题的前提指定其真值为真，若由此推出后的前提指定其真值为真，若由此推出后件亦为真，则件亦为真，则 为重言式。即为重言式。即成立。另一成立。另一方面，由方面，由，要证，要证为重言式，只为重言式，只需证需证 为重言式。即证为重言式。即证 为真时，为真时，为真。为真。亦即证为假时，为假。亦即证为假时，为假。n 证明给定的蕴含式的正确性的方法：.假定前件是真,若能推出后件是真,则此蕴含式为真。.假设后件

3、是假,若能推出前件亦假,则此蕴含式为真。3例例 证明证明()证：设证：设()为真，则为真，则 和和皆为真，那皆为真，那麽为假。再由麽为假。再由为真为真,得知应为真。得知应为真。或证为：设为假（那麽或证为：设为假（那麽等值于），那麽，等值于），那麽，()(F)F),即前件即前件为假。为假。例例 2 证明证明(PQ)(QR)PQ)(QR)PRPR证：证：设设PR为假，则为真，为假，则为真，R为假。如为假。如Q为真，则为真，则QR为假；若为假；若Q为假，则为假，则PQ为假。为假。故故(PQ)(QR)为假。为假。3、证明蕴含式的例子44、基本蕴含式(1)(1)PQPQP (PQP (PQQ)Q)(2)

4、(2)P PPQ (QPQ (QPQ)PQ)(3)(3)P PPQ PQ (因为因为 P PPQPQPQ)PQ)(4)(4)Q QPQ PQ (因为因为Q QPQPQPQ)PQ)(5)(5)(PQ)PQ)P P(因为因为(PQ)PQ)PP Q QP)P)(6)(6)(PQ)PQ)Q Q(7)(7)P(PQ)P(PQ)Q Q(8)(8)Q(PQ)Q(PQ)P P(9)(9)P(PQ)P(PQ)Q Q(10)(10)(PQ)(QR)PQ)(QR)PR PR(11)(11)(PQ)(PR)(QR)PQ)(PR)(QR)R R(设前件为真去证设前件为真去证)(12)(12)(P PQ)(QQ)(QR)

5、R)P PR R (设前件为真，分设前件为真，分P为真和为假两种情况讨论为真和为假两种情况讨论)55、蕴含式的性质若且是重言式，则必为重言式。证明：因为证明：因为为永真式，当为永真时，如果对为永真式，当为永真时，如果对某一指派，的真值为假，则与某一指派，的真值为假，则与为永真相矛为永真相矛盾，故永真。盾，故永真。若，则。证明：因证明：因，所以，所以，为永真为永真式，那麽（式，那麽（）（）亦为永真式。另外，）亦为永真式。另外，由由I I1010，可知可知(AB)(BC)AB)(BC)(AC)(AC)那麽由性质那麽由性质是永真式，亦即是永真式，亦即。65、蕴含式的性质（续）若且，则。证明：设的真值

6、为真，由于证明：设的真值为真，由于，则，则，的真值亦为真，从而的真值亦为真，从而的真值为真，故的真值为真，故为永真，从而为永真，从而。若且，则。证明：因证明：因和和为永真，那麽为永真，那麽永真。而永真。而(AB)(CB)AB)(CB)(AB)(AB)(CB)CB)(AA C)B C)B (AC)B(AC)B(AC)B(AC)B。故故为永真，从而为永真，从而。76、等价式和蕴含式的联系n联结词联结词“”和和“”有如下关系：有如下关系：A AB B(A(A B)(B B)(BA)A)，等价式和蕴含式之间也有着紧密的联系，如下所述。等价式和蕴含式之间也有着紧密的联系，如下所述。定理 设、为任意两个命

7、题公式，的充分必要条件是且。证明：若证明：若，则，则为重言式，因为为重言式，因为（）（），故），故和和皆为真，皆为真，即即和和成立。成立。反之，若反之，若且且，则，则和和皆为皆为真，从而真，从而为真，即为真，即为重言式，亦即为重言式，亦即。87、其它联结词n给定个命题变元，按命题公式的形成规则可以得到给定个命题变元，按命题公式的形成规则可以得到无数多个命题公式。但在这些无穷尽的命题公式之中，无数多个命题公式。但在这些无穷尽的命题公式之中，是否其真值都不同（指真值表最后一列不同）呢是否其真值都不同（指真值表最后一列不同）呢?或者或者说它们都是彼此不等价的呢说它们都是彼此不等价的呢?n回答是否定的

8、回答是否定的!这是因为对个变元只能有这是因为对个变元只能有2 2N N个不同的个不同的真值指派，在每一种真值指派下该命题公式只有真假真值指派，在每一种真值指派下该命题公式只有真假两个可能，对于两个可能，对于2 2N N个不同的真值指派就只有个不同的真值指派就只有2 2的的2 2N N个不个不同的真假二值的排列。一个排列相当于某一个由个同的真假二值的排列。一个排列相当于某一个由个变元生成的命题公式的真值表中的最后一列。变元生成的命题公式的真值表中的最后一列。n 例如包含两个命题变元、的不同命题公式只有例如包含两个命题变元、的不同命题公式只有2 2的的2 22 2个，即个。其它命题公式必定与这个之

9、个，即个。其它命题公式必定与这个之中的某一个有相同的真值。或者说与这十六个命题之中的某一个有相同的真值。或者说与这十六个命题之一等价。一等价。9 P Q 0 0 1 1 0 1 0 1 代表性的命题公式 1 0 0 0 0 F(永假式)2 0 0 0 1 PQ 3 0 0 1 0(PQ),或 PQ 或 PQ 4 0 0 1 1 P 5 0 1 0 0(QP)或 PQ 或 QP 6 0 1 0 1 Q 7 0 1 1 0(PQ),或 PQ 8 0 1 1 1 PQ 9 1 0 0 0(PQ),或 PQ 或 PQ 10 1 0 0 1 PQ 或 PQ 11 1 0 1 0 Q 12 1 0 1 1

10、 QP 或 PQ 13 1 1 0 0 P 14 1 1 0 1 PQ 或 PQ 15 1 1 1 0(PQ),或 PQ 或 PQ 16 1 1 1 1 T(永真式)包含两个命题变元P和Q的不同命题公式107、其它联结词（续1）n从包含两个命题变元、的不同命题公式表不难看从包含两个命题变元、的不同命题公式表不难看出，表示这个真值不同的公式，如果每个公式只出，表示这个真值不同的公式，如果每个公式只准用一个联结词，则定义九个联结词已足够使用。或准用一个联结词，则定义九个联结词已足够使用。或者说对一个或两个命题进行运算（连接），有九个运者说对一个或两个命题进行运算（连接），有九个运算符就足够了。当然

11、，这并不是必须的。算符就足够了。当然，这并不是必须的。定义 设、是两个命题公式，复合命题 称为与的不可兼析取。为真，当且仅当、真值不同。117、其它联结词（续2）n联结词有以下性质：(1)(1)P P Q Q(P(PQ)Q)（双条件否定）双条件否定）(2)(2)P P Q Q(P(P Q)(Q)(PQ)PQ)(3)P(3)P Q Q Q Q P (4)(PP (4)(P Q)Q)R RP P(Q(Q R)R)(5)P(Q(5)P(Q R)R)(PQ)(PQ)(PR)(PR)(6)P(6)P P PF F (7)F (7)F P PP (8)TP (8)T P PP Pn 关于联结词的定理定理定

12、理 设、是命题公式，如果设、是命题公式，如果，则，则 ，且，且 。证明：证明：如果如果，则，则 =127、其它联结词（续3）定义 设、是两个命题公式，复合命题设、是两个命题公式，复合命题 称为称为与的条件否定，与的条件否定，为真，当且仅当的真值为真，为真，当且仅当的真值为真，的真值为假。的真值为假。从上述定义可知，从上述定义可知，P Q(PQ)，故联结词故联结词 称为称为“条件否条件否定定”。定义 设、是两个命题公式，复合命题设、是两个命题公式，复合命题称为称为与的与的“与非与非”。当且仅当和真值皆为真时，。当且仅当和真值皆为真时，为假，否则为假，否则为真。为真。从上述定义可知，从上述定义可知

13、，PQ(PQ)，故联结词故联结词称为称为“与非与非”n 联结词联结词有以下性质有以下性质：(1)PP (PP)P(2)(PQ)(PQ)(PQ)PQ(3)(PP)(QQ)P Q (P Q)PQ137、其它联结词（续4）定义4 设、是两个命题公式，复合命题设、是两个命题公式，复合命题称为称为与的与的“或非或非”。当且仅当和真值皆为假时，。当且仅当和真值皆为假时，为真，否则为真，否则为假。为假。从上述定义可知，从上述定义可知，PQ (PQ)，故联结词故联结词称为称为“或非或非”。n 联结词联结词有以下性质有以下性质：(1)(1)PP PP (PP)(PP)P P(2)(PQ)(PQ)(2)(PQ)(

14、PQ)(PQ)(PQ)PQPQ(3)(3)(PP)(QQ)(PP)(QQ)PP Q Q(PP Q)Q)PQPQn 包含包含、的复合命题，其合式公式的定义与的复合命题，其合式公式的定义与以前的定义类似。以前的定义类似。148、最小联结词集n从基本恒等式可以发现，九个联结词并不都是必需的。从基本恒等式可以发现，九个联结词并不都是必需的。n 由由PQPQ(PP Q)Q)，PQPQ(PP Q)Q)可知，可知，和和可以互相替代可以互相替代。由由P PQ QPQPQ可知，可知，可用可用 和和替代替代；由由PQ(PQ)(QP)可知，可知，可用可用和和替代替代；所以所以、可用可用，或或，代替代替。n由于由于P

15、 P Q Q(P(PQ)Q)，P P Q Q(P(PQ)Q)，PQPQ(PQ)(PQ)，PQPQ(PQ)(PQ)，所以所以、可可用用、替代。替代。结论：结论：任意命题公式任意命题公式都可由仅都可由仅包含包含、或或、的的命题公式等价命题公式等价地地表示出来表示出来。158、最小联结词集(续)n联结词组联结词组，或或，能否能否再再归结归结为为、呢？呢？设设 P(.(PR).)对对右边右边所所出现出现的变元都指派真值，的变元都指派真值，则则右边命题公式右边命题公式的的真值必为，但此时真值必为，但此时左边命题公式左边命题公式的真值为。这一矛的真值为。这一矛盾盾说明说明 不能不能由由、的的复合复合所所代替代替。n，和和，称为最小联结词组称为最小联结词组,任何命题任何命题公式公式都能由仅含都能由仅含这些联结这些联结词的词的命题公式等价代命题公式等价代换换,并且最小联结词组并且最小联结词组中没有中没有多余多余的的联结联结词。词。n因因联结联结词词、可可分别分别用用或或来来代替代替，所以，所以，和和也是最小联结词组也是最小联结词组。16第1-3讲 作业nP23 1bc，2 bc，7，8ce，9bnP29 1c，3，917