1、离散数学之数理逻辑（ 2）上海交通大学软件学院吴刚2009年 6月内容n 命题逻辑n 等式的对偶定理n 蕴含重言式与命题逻辑推理n 范式n 命题联结词的归约回顾命题的公式化n 如果我下班早 , 就去商店看看 , 除非我很累n P Q R，其中 P代表 “我很累 ”， Q代表 “我下班早”， R代表 “我去商店看看 ”n 还可表示为： P (Q R)n 李四是计算机系的学生 , 他住在 312室或 313室n P (Q R) (Q R)，其中： P代表 “李四是计算机系学生 ”， Q代表 “李四住 312室 ”， R代表 “李四住313室 ”n 还可表示为： P (Q R) (Q R)等式的证明
2、n 例 1： P Q R = P (Q R)n 例 2： P (Q R) (Q R)=P (Q R) (Q R)n 注意： 等式 A=B代表的含义是 A B永真，不是 A永真或 B永真等式的对偶定理n 定义：设有公式 A，其中仅使用了联结词 ，则将其中的联结词 及命题常量 T、 F分别换成 和 F、 T后得到的公式 A*称为 A的对偶公式n 对偶定理：设有等式 A=B，且 A,B中 均只使用了联结词 ，则有 A*=B*n 即若有一个等式成立，其两边公式的对偶公式的等式也成立等式的对偶定理n 例子：n 由 P (P Q)=P可得 P (P Q)=Pn 由 P Q= (P Q) 可得P Q= (P
3、 Q)n 由 F P =F 可得T P =T蕴含重言式n 基本蕴含重言式n 第 182页 (43)-(61)，可用真值表证明n P Q P意味着 P Q P永真P Q P Q P Q PT T T TT F F TF T F TF F F T蕴含重言式n 基本蕴含重言式n P P Qn Q P Qn P (P Q) Qn (P Q) (Q R) P Rn 此外等价重言式可生成两个蕴含重言式n 因为 P Q = (P Q) (Q P) n 所以若 P Q (即 P=Q)，则有 PQ且 QP命题逻辑推理n 一般推理模式n 一组前提，推出一个结论n 前提 1,前提 2,前提 n 结论n 所有的前提是合取关系，与顺序无关n 只有在 “当所有前提都为真时，结论为真 ”成立的情况下，这一推理才是有效的。n 定理：n “前提 1,前提 2,前提 n 结论 ”有效的充要条件是命题公式 “(前提 1 前提 2 前提n) 结论 ”是重言式命题逻辑推理n 若有 PQ，则有 P Qn 若有 P1 P2 P3Q，则有P1,P2,P3 Q
