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

1、第1-3讲 蕴含式1. 蕴含式2.证明蕴含式的方法3.证明蕴含式的例子4.基本蕴含式5.蕴含式的性质6.等价式和蕴含式的联系7.其它联结词8.最小联结词集9. 作业1第1-3讲 蕴含式1. 蕴含式11、蕴含式定义设、为命题公式，当且仅当是一个重言式，称“蕴含”，记作。 对而言，称为逆换式，为反换式，为逆反式。由上表中可以看出：PQQP；QPPQ。 如同等价一样，也不是逻辑联结词。仅仅表示是永真式。21、蕴含式定义设、为命题公式，当且仅当是一个重言2、证明蕴含式的方法分析：要证，即要证为重言式。对来说，除为真、为假时，的真值为假外，其余情况的真值皆为真。故要证，只须对条件命题的前提指定其真值为真

2、，若由此推出后件亦为真，则 为重言式。即成立。另一方面，由，要证为重言式，只需证为重言式。即证为真时，为真。亦即证为假时，为假。 证明给定的蕴含式的正确性的方法： .假定前件是真,若能推出后件是真,则此蕴含式为真。 .假设后件是假,若能推出前件亦假,则此蕴含式为真。32、证明蕴含式的方法分析：要证，即要证为重言式。例 证明() 证：设()为真，则和皆为真，那麽为假。再由为真,得知应为真。 或证为：设为假（那麽等值于），那麽，()(F),即前件为假。例 2 证明(PQ)(QR) PR证：设PR为假，则为真，R为假。如Q为真，则QR为假；若Q为假，则PQ为假。 故(PQ)(QR)为假。3、证明蕴含

3、式的例子4例 证明() 例 2 证明(PQ)4、基本蕴含式(1) PQP ( PQQ) (2) PPQ ( QPQ) (3) PPQ (因为PPQPQ )(4) QPQ (因为QPQPQ )(5) (PQ)P (因为(PQ)PQP)(6) (PQ) Q(7) P(PQ) Q(8) Q(PQ) P(9) P(PQ) Q (10) (PQ)(QR) PR (11) (PQ)(PR)(QR) R(设前件为真去证) (12) (PQ)(QR) PR (设前件为真，分P为真和为假两种情况讨论 ) 54、基本蕴含式(1) PQP ( PQQ) 5、蕴含式的性质若且是重言式，则必为重言式。证明：因为为永真式

4、，当为永真时，如果对某一指派，的真值为假，则与为永真相矛盾，故永真。若，则。证明：因，所以，为永真式，那麽（）（）亦为永真式。另外，由I10，可知(AB)(BC) (AC)那麽由性质是永真式，亦即。65、蕴含式的性质若且是重言式，则必为重言式。若5、蕴含式的性质（续） 若且，则。证明：设的真值为真，由于，则，的真值亦为真，从而的真值为真，故为永真，从而。 若且，则。证明：因和为永真，那麽永真。而(AB)(CB)(AB)(CB) (AC)B (AC)B (AC)B。 故为永真，从而。75、蕴含式的性质（续） 若且，则。6、等价式和蕴含式的联系联结词“”和“”有如下关系： AB(A B)(BA)，

5、 等价式和蕴含式之间也有着紧密的联系，如下所述。定理 设、为任意两个命题公式，的充分必要条件是且。证明：若，则为重言式，因为（）（），故和皆为真，即和成立。 反之，若且，则和皆为真，从而为真，即为重言式，亦即。86、等价式和蕴含式的联系联结词“”和“”有如下关系：定理7、其它联结词给定个命题变元，按命题公式的形成规则可以得到无数多个命题公式。但在这些无穷尽的命题公式之中，是否其真值都不同（指真值表最后一列不同）呢?或者说它们都是彼此不等价的呢?回答是否定的!这是因为对个变元只能有2N个不同的真值指派，在每一种真值指派下该命题公式只有真假两个可能，对于2N个不同的真值指派就只有2的2N个不同的真

6、假二值的排列。一个排列相当于某一个由个变元生成的命题公式的真值表中的最后一列。 例如包含两个命题变元、的不同命题公式只有2的22个，即个。其它命题公式必定与这个之中的某一个有相同的真值。或者说与这十六个命题之一等价。97、其它联结词给定个命题变元，按命题公式的形成规则可以得到包含两个命题变元P和Q的不同命题公式10包含两个命题变元P和Q的不同命题公式107、其它联结词（续1）从包含两个命题变元、的不同命题公式表不难看出，表示这个真值不同的公式，如果每个公式只准用一个联结词，则定义九个联结词已足够使用。或者说对一个或两个命题进行运算（连接），有九个运算符就足够了。当然，这并不是必须的。定义 设、

7、是两个命题公式，复合命题称为与的不可兼析取。为真，当且仅当、真值不同。117、其它联结词（续1）从包含两个命题变元、的不同命题公式7、其它联结词（续2）联结词有以下性质：(1) PQ(PQ) （双条件否定）(2) PQ (PQ)(PQ)(3) PQ QP (4) (PQ)RP(QR)(5) P(QR) (PQ)(PR)(6) PPF (7) FPP (8) TPP 关于联结词的定理定理 设、是命题公式，如果，则 ，且。证明： 如果，则 = 127、其它联结词（续2）联结词有以下性质： 关于联结词的定7、其它联结词（续3）定义 设、是两个命题公式，复合命题称为与的条件否定，为真，当且仅当的真值为

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

9、质：(1) PP (PP) P(2) (PQ)(PQ) (PQ) PQ(3) (PP)(QQ) PQ (PQ)PQ 包含、的复合命题，其合式公式的定义与以前的定义类似。147、其它联结词（续4）定义4 设、是两个命题公式，复合命8、最小联结词集从基本恒等式可以发现，九个联结词并不都是必需的。 由PQ(PQ)，PQ(PQ)可知， 和可以互相替代。 由PQPQ可知，可用和替代； 由PQ(PQ)(QP)可知，可用和替代； 所以、可用，或，代替。由于PQ(PQ)，PQ(PQ)， PQ(PQ)，PQ(PQ)， 所以、可用、替代。结论：任意命题公式都可由仅包含、或、的命题公式等价地表示出来。 158、最小联结词集从基本恒等式可以发现，九个联结词并不都是必需8、最小联结词集(续)联结词组，或，能否再归结为、呢？设 P(.(PR).) 对右边所出现的变元都指派真值，则右边命题公式的真值必为，但此时左边命题公式的真值为。这一矛盾说明不能由、的复合所代替。，和，称为最小联结词组,任何命题公式都能由仅含这些