1-5重言式与蕴含式.ppt

1、1-5重言式与蕴含式,1-5.1重言式（tautology）,定义1-5.1 重言式: 给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。,1-5重言式与蕴含式,1-5.1重言式（tautology）,定义1-5.2 矛盾式: 给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。,1-5.1重言式（tautology）,性质1-5.1 若A和B均为重言式，则AB及AB也为重言式。 性质1-5.2 若A是一个重言式，则对A的同一个分量都用另外一个合式公式置换，所得公式仍为重言式。 例：(PQ) (PQ)

2、 是重言式(P14) P用RT 替换，还是重言式。,1-5.1重言式（tautology）,定理1-5.3 设A、B为两个命题，AB当且仅当A B 为一个重言式。,证明：若AB，则A、B有相同的真值， 由双条件定义 A B 永为T。,上例是重言式，则(PQ) (PQ) 德.摩根律得证,若A B为重言式，则A B永为T， 故A、B有相同的真值，即AB。,1-5.2蕴含式(implication),定义1-5.3 蕴含式当且仅当是一个重言式时，我们称“蕴含”，并记作。 对于来说，逆换式为： 反换式为： 逆反式为： 有与不等价， ， （命题与逆否命题等价）,1-5.2蕴含式(implication)

3、,证明AB的方法： 要证AB，即证AB是重言式，或证其逆反式B A是重言式即可。 要证AB是重言式： （推理法） （1）假设A为T时，说明B也为T。 因为当A为T，B为F时，AB为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蕴含式(impl

4、ication),例：见P21 例1 课上做表1-5.2的11式 看表1-5.2，记住常用的蕴含式。,1-5.2蕴含式(implication),定理1-5.4：设P、Q为任意两个命题公式，PQ的充分必要条件是PQ且QP 。 证明：由定理 1-5.3 ，P Q，则P Q为重言式，因为由表1-4.7 P Q (PQ)(QP)，故(PQ)为T且 (Q P)为T，即PQ且QP 成立。 反之，若PQ且QP 成立，则(PQ)为T且 (QP)为T，因此P Q为T， P Q为重言式，即PQ。 这个定理也可作为两个公式等价的定义。,1-5.3蕴含的性质,*（1）设A、B、C是合式公式，若A B且A是重言式，则

5、B必是重言式。 *（2）若A B，B C，则A C（传递性） *（3）若A B，A C ，则A BC （4）若A B，C B ，则AC B 以上性质在推理中常用。 特别说明：如果推导蕴含，则可以用等价的式子替换，因为“等价”比“蕴含”强，好比“大于等于”与“等于”的关系。,作业（1-5）,P23. (1) b) c) (2) b) 说明： （6）（8）先不做，因为有效性第八节讲。,1-6其它联结词,定义1-6.1不可兼析取(Exclusive OR)： 设P和Q是两个命题公式，复合命题PQ称作P和Q的不可兼析取。 PQ的真值为T，当且仅当P与Q的真值不相同时为T，否则， PQ的真值为F。真值表

6、如下：,1-6.1 不可兼析取的性质,设P、Q、R为命题公式，则有 （1）P Q Q P 交换性 （2）（PQ）R P（QR） 结合性 （3）P(QR)(PQ)(PR) 分配性 （4） PQ （PQ ）（PQ） （5） PQ （P Q）由定义得到 （6） PP F，FP P，TP P,1-6.2 条件否定,定义1-6.2 条件否定 设P和Q是两个命题公式，复合命题PQ称作P和Q的条件否定。 PQ的真值为T，当且仅当P的真值为T，Q的真值为F，否则， PQ的真值为F。真值表如下：,C,C,C,C,1-6.2 条件否定的性质,由定义可知： P Q （P Q）,C,1-6.3 与非,定义1-6.3

7、与非 设P和Q是两个命题公式，复合命题P Q称作P和Q的“与非”。当且仅当P和Q的真值都为T时， P Q的真值为 F ，否则P Q的真值都为T 。真值表如下：,1-6.3 与非的性质,（1）P Q （PQ） （2）P P （P P）P （3）（P Q）（P Q）（P Q） P Q （4）（P P）（ Q Q）P Q （PQ）PQ,1-6.4 或非,定义1-6.4 或非 设P和Q是两个命题公式，复合命题P Q称作P和Q的“或非”。当且仅当P和Q的真值都为F 时，PQ的真值为T ，否则， PQ的真值都为F。真值表如下：,1-6.4 或非的性质,（1）P Q （PQ） （2）P P （PP）P （3）（PQ）（PQ）（PQ） PQ （4）（PP）（ Q Q）P Q （P Q） P Q,1-6.5 联结词是否够用,每种联结词对应一种四个T或F的组合，总共可以有24=16种组合，似乎需要16种联结词才够用。 事实上，我们定义的这九种就够用了。 请看P27 表1-6.5,1-6.6 最小联结词组,最小联结词组应为，或，亦可以为或。 证明：1）用这些联结词组可以表示其它的联结词。 2）用，以及，不能表示其它的联结词。 不能表示 ， ， 因为含有二元联结词的命题公式不能用仅含一元联结词的命题公式等价代换。