第二章 命题逻辑的等值推演.ppt

第二章命题逻辑的等值推演 杨圣洪yangshenghong8 222 240 135 76 8080 ysh00713007432216 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 qp q p q q p p q p q 三 判断方法判断真值表是否一样判断A B是否为永真 例如 p与p p q 与 p p 这是德摩律 p q 与 p p 与 互反 p q p qp q p q q p p q p q p p p q p p德摩律 p q p p 与 对偶p p p p pp q r p q p r 分配律p q r p q p r 对偶式p p q p吸收律 多吃少 p p q pp p 1 p p 0 p q p q 双条件相同为真 p q p q p归谬律 如 p q p qp q p q q p p q p q p p p q p p德摩律 p q p p 与 对偶p p p p pp q r p q p r 分配律p q r p q p r 对偶式p p q p吸收律 多吃少 p p q pp 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应用题 甲 王不是苏州人 是上海人乙 王不是上海人 是苏州人丙 王不是上海人 也不是杭州人王说 一人全对 一人对一半 一人全不对 解 p 王是苏州人 q是上海人 r王是杭州人 甲 p q乙 p q丙 q r王说的话译成公式为 据此判断p q r的值 一 复习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 2 2析取范式与合取范式文字 命题变项 变元 及其否定称为文字 如 p q r p q r简单析取式 仅由有限个文字构成的析取式 如 p q p q p q p q p q r简单合取式 仅由有限个文字构成的合取式 如 p q p q p q p q p q r定理2 1 简单析取式与简单合取式 1 一个简单析取式Ai是重言式当且仅当同时含有某个命题变元及其否定式 如Ai p p 2 一个简单合取式Ai是矛盾式当且仅当同时含有某个命题变元及其否定式 如Ai p p 2 2析取范式与合取范式定义2 3 由有限个简单合取式的析取构成的命题公式称为析取范式 总体是析取式 每对括号内是合取式A p q p r 定义2 3 由有限个简单析取式的合取构成的命题公式称为合取范式 总体是合取式 每对括号内是析取式A p q p r 2 2析取范式与合取范式总体是析取式 每对括号内是合取式A p q p r 析取范式总体是合取式 每对括号内是析取式A p q p r 合取范式定理2 2 析取范式与合取范式 1 一个析取范式A是矛盾式当且仅当每个简单合取式是矛盾式 A p q p r 2 一个合取范式A是重言式当且仅当每个简单析取式是重言式 A p q p r 2 2析取范式与合取范式A p q p r 析取范式A p q p r 合取范式建立范式的基本步骤 1 转换条件式A B A B 2 转换双条式A B A B A B A B A B 3 否定到底 A A B A B 4 取消公因式A B C A B C 2 2析取范式与合取范式 1 转换条件式A B A B 2 转换双条式A B A B A B A B A B 3 否定到底 A A B A B 4 取消公因式A B C A B C 如合取式范式 p q r p q r p q r p q r p q r p q r p r q r p q r 2 2析取范式与合取范式 1 转换条件式A B A B 2 转换双条式A B A B A B A B A B 3 否定到底 A A B A B 4 取消公因式A B C A B C 如析取式范式 p q r p q r p q r p q r p r q r p q r 2 2析取范式与合取范式定义2 4 在含有n个变元的简单合取式中 每个命题变元或其否定仅出现一次 且各变元按其字母顺序出现 则该简单合取式为 极 小项 如 p q r p q r p q r p q r p q r p r q r p q r 非小项定义2 4 在含有n个变元的简单析取式中 每个命题变元或其否定仅出现一次 且各变元按其字母顺序出现 则该简单析取式为 极 大项 如 p q r p q r p q r p q r p q r p r q r p q r 非大项 2 2析取范式与合取范式小项的取值情况 对小项仅有一个成真的赋值如 p q r为111 记为m111或m7 p q r为101 记为m101或m5 p q r为110 记为m110或m6 p q r为011 记为m011或m3 大项的取值情况 对小项仅有一个成假的赋值 如 p q r为000 记为M000或M0 p q r为010 记为M010或M2 p q r为001 记为M001或M1 p q r为011 记为M011或M3 2 2析取范式与合取范式定义2 5 一个析取范式中 如果所有简单合取式均为 极 小项 则称为主析取范式 p q r p r q r p q r p 1 r 1 q r p q r p q q r p p q r p q r p q r p q r p q r p q r p q r m011 m001 m111 m011 m100 2 2析取范式与合取范式定义2 5 一个析取范式中 如果所有简单合取式均为 极 小项 则称为主析取范式 p q r p r q r p q r p 1 r 1 q r p q r p q q r p p q r p q r p q r p q r p q r p q r p q r m011 m001 m111 m011 m100 m011 m001 m111 m100 2 2析取范式与合取范式定义2 5 一个合取范式中 如果所有简单析取式均为 极 大项 则称为主合取范式 p q r p r q r p q r p 0 r 0 q r p q r p q q r p p q r p q r p q r p q r p q r p q r p q r M000 M010 M110 M101 成假赋值来编号 m011 m001 m111 m100 编号互补 2 2析取范式与合取范式主范式的获取方法 先转换析取式或合取式 再对于主析取 小项的析取 式 如果其中的简单合取式没有出现某个变元 则合取1 如 p q r p r q r p q r p 1 r 1 q r p q r 对于主合取范式 大项的合取 如果所有简单析取式没有出现某个变元 则析取0 如 p q r p r q r p q r p 0 r 0 q r p q r 2 2析取范式与合取范式主范式的获取方法 1 先转换析取式或合取式 再合取1或析取0 2 先建立真值表 取出所有成真赋值对应的小项 析取所有小项得主析取范式 取出所有成假赋值对应的大项 合取所有大项得主合取范式 如 p q r 2 2析取范式与合取范式主范式的获取方法 1 先转换析取式或合取式 再合取1或析取0 2 先建立真值表 成真赋值之小项析取 成假赋值的大项合取 如 p q r主范式的应用 1 若A去则B去 2 若B去则C不能去 3 若C不去则A或B可去 解 p q q r r p q 用方法1或方法2建立主析取范式 再进一步处理 2 3联结词的完备集第一章介绍了生成公式的4条规则 对于n个变元的所有可能公式中 只要使用我们所学的5个联结词 及园括号 足以表示所有这些公式 这称为联结词的完备性 其实只要 与园括号 足够了 2 4可满足性问题与消解法公式的可满足性是指 是否存在一种赋值情况 使得该公式的值为真 可以先得到一个公式的主析取或主合取范式 然后判断公式的类型 当一个公式比较复杂时 该问题的求解比较麻烦 因此Ribson找到了一种好方法 2 3联结词的完备集第一章介绍了生成公式的4条规则 对于n个变元的所有可能公式中 只要使用我们所学的5个联结词 及园括号 足