离散数学讲义命题逻辑.ppt
文本预览下载声明
# 例5 求公式 F1= (P?Q)?(P??Q)和 公式F2=P?(P?(Q?P))的主合取范式 F1? (?P?Q)?(P??Q) E11 ? (?P?Q)?(P?(Q??Q))?(?Q?(P??P)) E?5, E4 ? (?P?Q)?(P?Q)?(P??Q)?(P??Q)?(?P??Q) E?3 ? (P?Q)?(P??Q)?(?P?Q)?(?P??Q) E?7 解 F2 ??P∨(P∧(?Q∨P)) E11 ? (?P∨P)∧(?P∨?Q∨P) E3ノ ?1∧1 E5,E1 ? 1 六、利用主范式判定公式类型 1. 利用主析取范式判定 (1) 若公式 F(P1, P2,…,Pn)的主析取范式包含所有2n个最小项,则 F是永真公式。 (2) 若 F的主析取范式是一空公式且为0,则 F是永假公式。 (3) 否则,F为可满足的公式。 2 利用主合取范式判定 (1) 若公式F(P1, P2, …, Pn)的主合取范式包含所有2n个最大项,则F是永假公式。 (2) 若F的主合取范式是一空公式且为1,则F是永真公式。 (3) 否则,F为可满足公式 三、命题公式的蕴含关系 定义2.4.2 设A,B是两个公式,若公式A?B是重言式,即A?B?1,则称公式A蕴含公式B,记作A?B。称“A?B”为蕴含式。 注意: (1) 符号“?”和 “?”的区别和联系 (2) A?B是偏序关系 即 自反性:A?A 反对称:若A?B,B?A,则A?B 传递性:若A?B,B?C,则 A?C (3) 若A 、B和C是三个命题公式,且A?B, A ?C,则A?B∧C (4) 若A 、B和C是三个命题公式,且A? C , B ?C,则A ∧ B ?C 定理2.4.2 A ? B当且仅当A ? 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
显示全部