[哲学]离散数学03.ppt

回顾：本节主要内容 蕴含式 扩充的联结词 全功能联结词集 作业 P41 第7，8，10，11题 离散数学 （第三讲） 课程代码：MAT2131T 授课教师：师雪霖 公共邮箱：discretemath2011@ 公共邮箱密码：buct2011 教师Email：shixl@ 复习：上节主要内容 真值表 永真式和永假式 等价式 基本等价式（命题定律） 代入规则和置换规则 公式推演法 复习：基本等价式（命题定律） 编号 中文名称 等价式 1 双重否定律 ~ ~P ? P 2 等幂律 P∨P ? P P∧P ? P 3 结合律 (P∨Q)∨R ? P∨(Q∨R) (P∧Q)∧R ? P∧(Q∧R) 4 交换律 P∨Q ? Q∨P P∧Q ? Q∧P 5 分配律 P∨(Q∧R) ? (P∨Q)∧(P∨R) P∧(Q∨R) ? (P∧Q)∨(P∧R) 编号 中文名称 等价式 6 吸收律 P∨(P∧Q) ? P P∧(P∨Q) ? P 7 德.摩根律 ~ (P∧Q) ? ~P∨~Q ~ (P∨Q) ? ~P∧~Q 8 同一律 P∨F ? P P∧T ? P 9 零律 P∨T ? T P∧F ? F 10 补余律 P∨~P ? T（排中律） P∧~P ? F（矛盾律） 编号 中文名称 等价式 11 条件转化律 P→Q ? ~P∨Q P→Q ? ~Q→~P ~ (P→Q) ? P∧~Q 12 双条件转化律 P?Q ? (P→Q)∧(Q→P) P?Q ? (P∧Q)∨(~P∧~Q) 13 归缪律 (P→Q)∧(P→~Q) ? ~P 14 输出律 (P∧Q)→R ? P→(Q→R) 复习：公式推演法 定义 有了代入规则和置换规则，就可以利用已知的等价式来推演出一些更为复杂的等价式。这种利用已知的等价式、代入规则和置换规则来推演复杂等价式的方法称为公式推演法。 公式推演法的用途： （1）验证两个命题公式等价 （2）判别命题公式的类型 （3）解决实际问题 本节主要内容 蕴含式 扩充的联结词 全功能联结词集 蕴含式 定义 给定命题公式P→Q，称命题公式Q→P为它的逆换式，命题公式~P→~Q为它的反换式，命题公式~Q→~P为它的逆反式 。 性质 P→Q?~Q→~P Q→P?~P→~Q 蕴含式 定理 设A, B为两个命题公式，若A→B是永真式，即A→B ? T，则称命题公式A蕴含命题公式B，记作A ? B。 注意 ① 正如?和?区别一样， ?和→也是完全不同的符号. ② 条件联结词→是逻辑联结词. ?不是逻辑联结词，不能作为命题公式的一部分，而仅表示两个命题公式之间的关系. ③ A ? B充要条件是A→B为永真式，可以通过判断是否A→B为永真式来判定A是否蕴含B 蕴含式 真值表法 使用真值表证明A→B 为永真式。 前件真推证后件真方法 设A为T，若能推证B为T，则A→B 为永真式，即A ? B 。 后件假推证前件假方法 设B为F，若能推证A为F，则A→B 为永真式，即A ? B 。 证明A ? B可采用三种方法： 蕴含式 例：证明~Q∧(P → Q) ? ~P 证明：（1）真值表法。 欲证明~Q∧(P → Q) ? ~P，即只要证明~Q∧(P → Q)→~P 为永真式。写出它的真值表即可证明。 （2）前件真推证后件真方法。 假定~Q∧(P → Q) 为T，则有~Q和P→Q均为T, 从而Q为F， 由P→Q为T则有P为F，则~P为T。所以蕴含式得证。 （3）后件假推证前件假方法。 假定~P为F，则有P为T。若Q为T，则~Q∧(P → Q) 为F；若Q为F， ~Q∧(P → Q) 仍为F。得证。 基本蕴含式 编号 中文名称 蕴含式 1 化简式 P∧Q ? P P∧Q ? Q 2 附加式 P ? P∨Q Q ? P∨Q 3 ~P ? P→Q 4 Q ? P→Q 5 ~(P→Q) ? P 6 ~(P→Q) ? ~Q 编号 中文名称 蕴含式 7 假言推理 P∧(P→Q) ? Q 8 拒取式 ~Q∧(P→Q) ? ~P 9 析取三段论 ~P∧(P∨Q) ? Q 10 假言三段论 (P→Q)∧(Q→R) ? (P→R) 11 双条件三段论 (P?Q)∧(Q?R) ? (P?R) 12 构造性二难 (P→Q)∧(R→S)∧(P∧R) ? Q∧S (P→Q)∧(R→S)∧(P∨R) ? Q∨S 13 二难推论 (P→Q)∧(R→Q)∧(P∧R) ? Q (P→Q)∧(R→Q)∧(P∨R) ? Q 蕴含与等价的关系 定理 设A和B为命题公式，A ? B的充分必要条件是A ?B且B?A 。 证明： 必要性。设A ? B，则A?B为永真式，由于A?B