第九章 离散数学.ppt

三、命题公式的蕴含关系 定义9-11 设A，B是两个公式，若公式A?B是重言式，即A?B?1，则称公式A蕴含公式B，记作A?B。称“A?B”为蕴含式。 注意：符号“?”和 “?”的区别和联系与符号“?”与“?”的区别和联系类似。 “?”不是联结词， “A?B”不是公式，它表示公式A与B之间存在蕴含关系。 “?”是联系词，A?B是一个公式。 A?B当且仅当A?B是永真公式 。 A?B是偏序关系 即 自反性：A?A。 反对称：若A?B，B?A，则A?B。 传递性：若A?B，B?C，则 A?C。 反对称性的证明： 设A?B且B?A， 由定义7-11 A?B?1且B?A?1 于是A?B?(A?B)?(B?A) E14 ? 1?1 ? 1 因此 A?B 传递性的证明： 设A?B，B?C， 则A?B?1，B?C?1 ? (?A?B?C)?(?A??B?C) ? ((A?B) ?C)?(?A?(B?C)) ? (1?C)?(?A?1) ? 1?1 ? 1 因此 A?C. 于是 A?C ?? A?C ? (?A?C)?(B??B) 四、基本的蕴含式 编号 蕴 含 式 I1 P?Q?P I2 P?Q?Q I3 P ?P?Q I4 Q?P?Q I5 ?P ?P?Q I6 Q?P?Q I7 ?(P?Q)?P I8 ?(P?Q)? ?Q 设P、Q、R是命题变元，下表中列出了16个最基本的蕴含式。 编号 蕴 含 式 I9 P?Q?P?Q 或表示为：P、Q?P?Q I10 ?P?(P?Q) ?Q ?P、(P?Q)?Q I11 P?(P?Q)?Q P、P?Q?Q I12 ?Q?(P?Q)??P ?Q、P?Q??P I13 (P?Q)?(Q?R)?P?R P?Q、Q?R?P?R I14 (P?Q)?(P?R) ? (Q?R) ?R P?Q、P?R、Q?R?R I15 P?Q?(P?R)?(Q?R) I16 P?Q?(P?R)?(Q?R) 五、蕴含式的判别 判定“A ? B”是否成立的问题可转化为判定A ? B是否为重言式，有下述判定方法： ?（1）真值表； （2）等值演算； （3）假定前件A为真； （4）假定后件B为假。 ?????1. 真值表方法 例4 证明I14 ：(（P∨Q）∧（P ? R）∧（Q ? R）) ? R 证明 令公式 F =（（P∨Q）∧（P?R）∧（Q?R））?R， 其真值表如下： 公式F对任意的一组真值指派取值均为1，故F是重言式。 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 F (P∨Q)∧ (P→R）∧（ Q →R） Q →R P→R P∨Q P Q R 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 ??????????2.?? 等值演算方法 例5 证明 I11：P∧（P?Q）? Q 证明 （P∧（P?Q））? Q ? ?（P∧（?P∨Q））∨ Q E11 ? （?P∨?（?P∨Q））∨ E10ノ ?（?P∨Q）∨?（?P∨Q） E2 ? 1 代入规则,E5 因此 P∧（P?Q）? Q ???????????3.? 假定前件A真 假定前件A为真，检查在此情况下，其后件B是否也为真。 A B A?B 0 0 1 0 1 1 1 0 0 1 1 1