离散数学课件重言式及蕴含式.pptVIP

1-5重言式与蕴含式 1-5.1重言式（tautology） 1-5重言式与蕴含式 1-5.1重言式（tautology） 1-5.1重言式（tautology） 性质1-5.1 若A和B均为重言式，则A?B及A?B也为重言式。 性质1-5.2 若A是一个重言式，则对A的同一个分量都用另外一个合式公式置换，所得公式仍为重言式。 例：?(P?Q) (?P??Q) 是重言式(P14) P用R?T 替换，还是重言式。 1-5.1重言式（tautology） 定理1-5.3 设A、B为两个命题，A?B当且仅当A B 为一个重言式。 1-5.2蕴含式(implication) 定义1-5.3 [蕴含式］当且仅当Ｐ?Ｑ是一个重言式时，我们称“Ｐ蕴含Ｑ”，并记作Ｐ?Ｑ。 对于Ｐ?Ｑ来说，逆换式为：Ｑ?Ｐ 反换式为：?Ｐ? ?Ｑ 逆反式为：?Ｑ? ?Ｐ 有Ｐ?Ｑ与Ｑ?Ｐ不等价， Ｐ?Ｑ??Ｑ? ?Ｐ，Ｑ?Ｐ? ?Ｐ? ?Ｑ 　　（命题与逆否命题等价） 1-5.2蕴含式(implication) 证明A?B的方法： 要证A?B，即证A?B是重言式，或证其逆反式?B? ?A是重言式即可。 要证A?B是重言式： （推理法） （1）假设A为T时，说明B也为T。 [因为当A为T，B为F时，A?B为F] 或（2）假设B为F时，说明A也为F。 [因为可得?B为T时，?A也为T，即 ?B? ?A是重言式] （此方法是命题逻辑中的一个基本证明方法） 可使用表1-5.2的蕴含式 1-5.2蕴含式(implication) 例：n是整数，证明若n2是奇数，n也是奇数。 证明：（反证法）若n是偶数，n2也是偶数。 设n=2k，k是一个整数， 则n2=(2k)2=2(2k2), 所以n2是偶数。 所以原命题得证。 1-5.2蕴含式(implication) 例：见P21 例1 课上做表1-5.2的11式 看表1-5.2，记住常用的蕴含式。 1-5.2蕴含式(implication) 定理1-5.4：设P、Q为任意两个命题公式，P?Q的充分必要条件是P?Q且Q?P 。 证明：由定理 1-5.3 ，P ?Q，则P Q为重言式，因为由表1-4.7 P Q ?(P?Q)?(Q?P)，故(P?Q)为T且 (Q ?P)为T，即P?Q且Q?P 成立。 反之，若P?Q且Q?P 成立，则(P?Q)为T且 (Q?P)为T，因此P Q为T， P Q为重言式，即P?Q。 这个定理也可作为两个公式等价的定义。 1-5.3蕴含的性质 *（1）设A、B、C是合式公式，若A ? B且A是重言式，则B必是重言式。 *（2）若A ? B，B ? C，则A ? C（传递性） *（3）若A ? B，A ? C ，则A ? B?C （4）若A ? B，C ? B ，则A?C ? B 以上性质在推理中常用。 特别说明：如果推导蕴含，则可以用等价的式子替换，因为“等价”比“蕴含”强，好比“大于等于”与“等于”的关系。 作业（1-5） P23. (1) b) c) (2) b) 说明： （6）~（8）先不做，因为有效性第八节讲。 1-6其它联结词 定义1-6.1不可兼析取(Exclusive OR)： 设P和Q是两个命题公式，复合命题P?Q称作P和Q的不可兼析取。 P?Q的真值为T，当且仅当P与Q的真值不相同时为T，否则， P?Q的真值为F。真值表如下： 1-6.1 不可兼析取的性质 设P、Q、R为命题公式，则有 （1）P ? Q ? Q ? P 交换性 （2）（P?Q）?R ? P?（Q?R） 结合性 （3）P?(Q?R)?(P?Q)?(P?R) 分配性 （4） P?Q ?（P??Q ）?（?P?Q） （5） P?Q ? ?（P Q）由定义得到 （6） P?P ? F，F?P ?P，T?P ??P 1-6.2 条件否定 定义1-6.2 条件否定 设P和Q是两个命题公式，复合命题P?Q称作P和Q的条件否定。 P?Q的真值为T，当且仅当P的真值为T，Q的真值为F，否则， P?Q的真值为F。真值表如下： 1-6.2 条件否定的性质 由定义可知： P? Q ? ?（P ?Q） 1-6.3 与非? 定义1-6.3 与非 设P和Q是两个命题公式，复合命题P ? Q称作P和Q的“与非”。当且仅当P和Q的真值都为T时， P