离散数学L2命题演算.pptVIP

Lu Chaojun, SJTU * 对偶定理 定义 ?和? 同永真:? 永真 iff ? 永真 ?和? 同可满足:? 可满足 iff ? 可满足 定理:以下两对公式都是同永真且同可满足的:? 与?－, ?? 与?*. 对偶定理:以下两对公式都是同永真且同可满足的:??? 与?*??*, ??? 与?*??*. 推论: ? = ? iff ?* = ?*. Lu Chaojun, SJTU * 公式有没有标准形式? 公式的数量是无穷多的. 即便只有一个变元P,也可以写出 P , P ? P , P ? P ? P , P ? P ? P ? P, …… 但若按等值关系对全体公式进行划分, n个命题变项所能形成的不同公式仅有22n个. 问题:与命题公式? 等值的公式能否都化为某种标准形式? 借助于标准形容易判断两个公式是否等值. 借助于标准形容易判断公式是否重言式或矛盾式. Lu Chaojun, SJTU * 范式(normal form) 由命题变元或命题变元的否定利用?(?)联结而成的公式称为合(析)取式. 合取式例:P, ?P, P?Q, P??Q??P 析取式例:P, ?P, P?Q, P??Q??P 由合(析)取式利用?(?)联结而成的公式称为析(合)取范式. 析取范式形如: ?1 ? ?2 ? … ??n (诸?i是合取式) 合取范式形如: ?1 ? ?2 ? … ??n (诸?i是合取式) Lu Chaojun, SJTU * 公式转化为范式 范式定理: 任一公式都有与之等值的合取范式和析取范式. 根据真值表列写公式就是求范式一法. 等值变换法求范式 1.消去?,? 2.否定词深入到变元前 3.合(析)取词深入 这时已经是范式. 4.(可选)化简 * Lu Chaojun, SJTU * 1.消去?,? 方法:利用下列等值式 ??? = ?? ?? ??? = (??? )?(????? ) [适合求析取范式] ??? = (???? )?(???? ) [适合求合取范式] 例:求?(P?Q)?(P?Q)的析取范式 ?(P?Q)?(P?Q) = (?(P?Q) ? (P?Q)) ? (??(P?Q) ? ?(P?Q)) * Lu Chaojun, SJTU * 2.否定词深入 方法:利用下列等值式 ?(? ?? ) = ?? ? ?? ?(? ?? ) = ?? ? ?? ??? = ? 例 ?(P?Q)?(P?Q) = (?(P?Q) ? (P?Q)) ? (??(P?Q) ? ?(P?Q)) = (?P??Q ? P?Q) ? ((P?Q) ? (?P??Q)) * Lu Chaojun, SJTU * 3.合(析)取词深入 方法:利用分配律 ? ? (? ?? ) = (? ?? ) ? (? ?? ) [用于析取范式] ? ? (? ?? ) = (? ?? ) ? (? ?? ) [用于合取范式] 例 ?(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??P) ? (P??Q) ? (Q??P) ? (Q??Q) * Lu Chaojun, SJTU * 4.(可选)化简 方法:利用下列等值式消去矛盾式 P ? F = F ? ? F = ? 例 ?(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??P) ? (P??Q) ? (Q??P) ? (Q??Q) = (P??Q) ? (?P?Q) * Lu Chaojun, SJTU * 范式的用途 判断?是否重言式 求?的合取范式,若每个析取式都含有某个变元及其否定(如P和?P),则?是重言式. 判断?是否矛盾式 求?的析取范式,若每个合取式都含有某个变元及其否定(如P和?P),则?是矛盾式. 判断? =? ? 求? 和? 的同一种范式,看是否相同. 问题是: 范式唯一吗? * Lu Chaojun, SJTU * 主范式 假设以下讨论的公式都只涉及n个命题变元P1, … , Pn. 极小项: n个命题变元都在其中出现一次的合取式. 极小项有2n个. 主析取范式:仅由极小项构成的析取式. 定理:任一公式都有唯一与之等值的主析取范式. 假设以下讨论的公式都只涉及n个命题变元P1, … , Pn. 极大项: n个命题变元都在其中出现一次的析取式. 极大