第03章 命题逻辑.ppt

4, 5, 7(2,4,6,8), 9(2,4), 10(2,4,6), 11(2,4,6) 4, 7, 9(略) 5. P: 天正在下雪; Q: 我将进城; R: 我有空. (1) Q?(R??P) ; (2) P?Q; (3) (Q?R)?(R?Q); (4) ?(R?Q). 10. (2) (?P?Q)?R; (4) P?((Q?R)?S); (6) ?(P?Q)?(P?Q); 11. (2) (?P??Q)?(P??Q); (4) P?(P?(Q?P)); (6) (P??R)?(S?P). * 范式的求解方法 定理3.5.1 对于任意命题公式，都存在与其等价的析取范式和合取范式。 公式转换方法： （1）将公式中的 →、? 用联结词 ? 、∧、∨ 来取代，例如： (Ｇ→Ｈ) = (?Ｇ∨Ｈ)； (Ｇ?Ｈ) = (Ｇ→Ｈ)∧(Ｈ→Ｇ) = (?Ｇ∨Ｈ)∧(?Ｈ∨Ｇ)。 * 范式的求解方法(续) （2）重复使用德?摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号, 例如： ?(Ｇ∨Ｈ) = ?Ｇ∧ ?Ｈ； ?(Ｇ∧Ｈ) = ?Ｇ∨ ?Ｈ； ?(?Ｇ) =Ｇ （3）重复利用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取，例如： Ｇ∨(Ｈ∧Ｓ) = (Ｇ∨Ｈ)∧(Ｇ∨Ｓ)； Ｇ∧(Ｈ∨Ｓ) = (Ｇ∧Ｈ)∨(Ｇ∧Ｓ)。 * 例3.5.1 求公式：(Ｐ→?Ｑ)∨(Ｐ?R)的析取范式和合取范式. 解 (Ｐ→?Ｑ)∨(Ｐ?R) = (?Ｐ∨?Ｑ) ∨ ((?Ｐ∨R)∧(?R∨P)) = (?Ｐ∨?Ｑ∨?Ｐ∨R)∧(?Ｐ∨?Ｑ∨? R∨P） = ((?Ｐ∨?Ｑ)∨(?Ｐ∨R)) ∧ ((?Ｐ∨?Ｑ)∨(? R∨P)) = (?Ｐ∨?Ｑ∨R) ——合取范式 = ?Ｐ∨?Ｑ∨R ——析取范式 * 练习: P91 10(1)(3) 10. 求下列命题公式所对应的合取范式和析取范式 (1) P?(P→Q); (3) ?(P??Q)?(S→R); 答: (1) 析取范式 (P?Q) 合取范式 P?Q 或 P?(?P??Q) (3) 析取范式 (?P?Q??S)?(?P?Q?R) 合取范式 ?P?Q?(R??S) * 3.5.2 主析取范式和主合取范式 1 极小项和极大项 定义 3.5.3 在含有 n个命题变元P1、P2、P3、…、Pn的短语 (或子句) 中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，则称此短语 (或子句) 为关于P1、P2、P3、…、Pn的一个极小项 (或极大项)。 对于n个命题变元，可构成2n个极小项和2n个极大项. * 例子 （1）一个命题变元P， 对应的极小项有两项：P、? P； 对应的极大项有两项：P、? P。 （2）两个命题变元P、Q， 对应的极小项有四项： P∧Q、 ? P∧Q、 P∧? Q、 ? P∧? Q； 对应的极大项有四项： P∨Q、 ? P∨Q、 P∨? Q、 ? P∨? Q。 * 两个命题变元的所对应极小项真值表 P Q ┐P∧┐Q ┐P∧Q P∧┐Q P∧Q 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 注意：（1）没有等价的两个极小项； （2）使该极小项的真值为真的指派是唯一的； （3）使极小项为真的那组指派为对应极小项的编码； ?Ｐ∧?Ｑ →{0、0}为真 →{0 0} → m00(m0) ?Ｐ∧Ｑ →{0 1}为真 →{0 1} → m01(m1) Ｐ∧?Ｑ →{1 0}为真 →{1 0} → m10(m2) Ｐ∧Ｑ →{1 1}为真 →{1 1} → m11(m3) * 两个命题变元的所对应极大项真值表 P Q ┐P∨┐Q ┐P∨Q P∨┐Q P∨Q 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1