第二单元 命题逻辑的等值推演.pptVIP

第二章 命题逻辑的等值推演 杨圣洪 yangshenghong8@ 6:8080/ysh007 2.1 等值式 一、复习 p?q仅在p与q均为0时结果才为0，其他为1。 p?q仅在p与q均为1时结果才有1，其他为0。 p?q仅在p为1、q为0才为0，其他为1。 p?q仅在p与q等值时才1，其他为1。 用真值表证明了 p?q与?p?q的真值表完全一样，即这两者等值，根据双条件的定义， (p?q)? (?p?q)为永真或重言式。 p?q? (p?q)?(q?p) ?(p?q)?(?p??q) 二、等值式定义 公式A、B，如果其真值表完全一样，或者A?B为永真式，则称A与B等值，记为A?B 如： p?q ? ?p?q p?q? (p?q)?(q?p) ?(p?q)?(?p??q) 三、判断方法 判断真值表是否一样 判断A?B是否为永真。 例如： ? ?p与p ?(p?q)与?p??p，这是德摩律 ?(p?q)与?p??p ?与?互反 p?q ? ?p?q p?q? (p?q)?(q?p) ?(p?q)?(?p??q) ? ?p?p ?(p?q) ??p??p 德摩律 ?(p?q) ??p??p ?与?对偶 p?p?p ? p?p p?(q?r) ?(p?q)?(p?r) 分配律 p?(q?r)?(p?q)?(p?r) 对偶式 p?(p?q) ?p 吸收律(多吃少) p?(p?q) ?p p??p ?1，p??p ?0 (p?q) ? (?p??q) 双条件相同为真 (p?q)?(p??q) ??p 归谬律 如： p?q ? ?p?q p?q? (p?q)?(q?p) ?(p?q)?(?p??q) ? ?p?p ?(p?q) ??p??p 德摩律 ?(p?q) ??p??p ?与?对偶 p?p?p ? p?p p?(q?r) ?(p?q)?(p?r) 分配律 p?(q?r)?(p?q)?(p?r) 对偶式 p?(p?q) ?p 吸收律(多吃少) p?(p?q) ?p p??p ?1，p??p ?0 (p?q) ? (?q??p) (p?q)?(p??q) ??p 归谬律 将以上公式中命题变元p/q，换成公式A/B，一样成立！ A?B ? ?A?B p?q ? ?p?q 可推出 A?B ? ?A?B 尽管A/B可能很复杂，但是公式值也只有0、1二种可能，公式A/B的组合只有0/0,0/1,1/0,1/1四种，即只要证明： 0?0 与 ?0?0 相等 0?1 与 ?0?1 相等 1?0 与 ?1?0 相等 1?1 与 ?1?1 相等 这与证明p?q ??p?q的过程完全一样， 即变元 p/q的值只有0、1,变元p/q的组合只有0/0,0/1,1/0与1/1四种组合，即证明各组合下各值相等。 p?q ? ?p?q 可推出 A?B ? ?A?B 这种将变元换成公式的方法，称为“置换规则”，推而广知： 已知A ? B ，?(A)是含公式A的命题公式，将?(A)中A全部换成公式B，则?(A) ? ?(B) 如： p?q ? ?p?q ，?(p?q)=(p?q)?p， 这里A= p?q ，B= ?p?q ， ?(A)=?(p?q)= (p?q)?p， ?(B)=?(?p?q)= (?p?q)?p，故 (p?q)?p ? (?p?q)?p 部分等值置换后公式仍等值！可用于等值演算 因为p?q ? ?p?q 故 (p?q)?p ? (?p?q)?p 部分等值置换后公式仍等值！可用于等值演算 (p?q)?r ?(?p?q)?r (因(p?q) ? (?p?q)) ??(?p?q)?r (因(?p?q) ?r ??(?p?q)?r ) ?(??p??q)?r (德摩律) ?(p??q)?r (双重否定律) ?(p?r) ?(?q?r) (双重否定律) 证： (p?q) ?r ? (p?r) ? (q?r) 尽量转换??? 证：(p?q)?p?q 先演算后判断公式类型 ?(p?(p?q)) ?r 应用题： 甲：王不是苏州人，是上海人 乙：王不是上海人