离散数学 命题逻辑.ppt

主要内容: 主要内容: ? 1 蕴含关系? 2 等价关系? 3 置换定理与对偶定理一、命题公式的蕴含关系定义设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) E 14 ? 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) 基本的蕴含式编号蕴含式 I 1P?Q?PI 2P?Q?Q I 3 P ?P?Q I 4Q?P?Q I 5? P ?P?Q I 6Q?P?Q I 7?(P? Q) ?PI 8?(P? Q) ??Q 设P、Q、R 是命题变元,下表中列出了 16 个最基本的蕴含式。编号蕴含式 I 9P?Q?P?Q或表示为:P、Q?P?Q I 10?P?(P? Q) ?Q?P、(P? Q) ?Q I 11P?(P? Q) ?Q P 、P?Q?Q I 1 2?Q?(P? Q) ?? P?Q、P?Q ?? P I 13 (P? Q) ?(Q ? R) ?P?R P ?Q、Q?R?P?R I 14 (P? Q) ?(P? R) ? (Q ? R) ?R P ?Q、P?R、Q?R?R I 15P?Q?(P? R) ?(Q ? R) I 16P?Q?(P? R) ?(Q ? R) 二、蕴含式的判别判定“ A ? B”是否成立的问题可转化为判定 A ? B 是否为重言式,有下述判定方法: (1)真值表; (2)等值演算; (3)假定前件 A为真; (4)假定后件 B为假。 1. 真值表方法例4 证明 I 14 :( (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 →RP→RP∨QP Q R 00111111 11110101 11011101 00010101 11111111 证明 I 11:P∧(P?Q)?Q 证明(P∧(P?Q))?Q ??(P∧(?P∨Q))∨Q E 11 ?(?P∨?(?P∨Q))∨Q E 10 ノ?(?P∨Q)∨?(?P∨Q)E 2?1 代入规则,E 5 因此 P∧(P?Q)?Q