第一部分 第二章 命题逻辑等值演算.ppt

第二章命题逻辑等值演算 2 1等值式2 2析取范式与合取范式2 3联结词的完备集2 4可满足性问题与消解法 重点 难点 2 1等值式 定义2 1设A B是任意两个命题公式 若等价式A B为重言式 则称A与B是等值的 记作 A B 自反性 即对任意命题公式A A A 对称性 即对任意命题公式A和B 若A B 则B A 传递性 即对任意命题公式A B和C 若A B B C 则A C 两点注意 与 A B 表示两公式一样 A B 表示两公式真值一样 与 是两类完全不同的符号 是联结词 运算符 A B是一个公式 不是联结词 而是两个公式之间的关系符 真值表判断等值 十六组重要的等值式 模式 1 双重否定律A A2 幂等律A A A A A A3 交换律A B B A A B B A4 结合律 A B C A B C A B C A B C 十六组重要的等值式 5 分配律 提取公因式 A B C A B A C A B C A B A C 6 德摩根律 A B A B A B A B 德摩根律的例子 地大物博 的否定 地不大或物不博 A B A B 用人民币或港币支付 的否定 既不能用人民币支付 也不能用港币支付 A B A B 十六组重要的等值式 7 吸收律A A B A A A B A8 零律A 1 1 A 0 09 同一律A 0 A A 1 A10 排中律A A 111 矛盾律A A 0 十六组重要的等值式 12 蕴涵等值式A B A B13 等价等值式A B A B B A 14 假言易位A B B A15 等价否定等值式A B A B16 归谬论 A B A B A 蕴涵等值式的例子 蕴涵等值式 A B A B否定形式 并非 p q p q p q例 并非招手即停 招手且不停车 归谬论的应用 归谬论 A B A B A反证法如果非p 则q如果非p 则非q所以 p 归谬论的例子 亚理士多德 物体的下落速度与物体的重量成正比 伽利略的思想实验 A快B慢 A B比A快 A快B慢 A B比A慢 归谬论的例子 一个岛上有一个风俗 凡是外乡人都要作为祭品被杀掉 但允许被杀的人在临死前说一句话 如果这句话是真的 则死在真理之神面前 如果这句话是假的 则死在错误之神面前 一个哲学家说了一句话 而免于一死 等值演算与置换规则 由已知的等值式推演出另外的等值式的过程称为等值演算 置换规则设 A 是一个含有公式A的命题公式 B 是用公式B置换了 A 中的公式A后得到的公式 如果A B 那么 A B 等值演算的例子 例2 1 用等值演算验证等值式p q r p q r 等值演算的例子 例2 2 用等值演算法判断下列公式的类型 q p q p p p q q r p q p 等值演算的例子 解 q p q p q p p q p 分配律 q 0 q p 矛盾律 q q p 同一律 q q p 德摩根律 q q p 结合律 1 p 排中律 1 零律 由此可知 为重言式 等值演算的例子 解 p p q q r 1 q q r 排中律 1 0 r 矛盾律 1 0 零律 0 条件联结词的定义 由此可知 为矛盾式 p q p p q p 蕴涵等值式 p 吸收律 由此可知 是可满足式 练习 1 用等值演算验证等值式 1 p q r p r q r 2 p q p q p q 2 判断公式的类型 1 p q p q 2 p q q r 判断问题 例2 6 判断王教授是哪里人 甲说王教授不是苏州人 是上海人乙说王教授不是上海人 是苏州人丙说不是上海人 也不是杭州人王教授说三个人中一个说的全对 一个说对了一半 另一个全不对 解 p 王教授是苏州人q 王教授是上海人r 王教授是杭州人 解题思路 pqr001010100王教授的话是对的 写出公式A p q r 找出它的成真赋值 根据实际情况 只有3个赋值 而不是8个 作业 习题二38 39页题目 3 417 1819 20 2 2析取范式与合取范式 定义2 2将命题变元及其否定统称为文字 literal 简单析取式 基本和 仅由有限个文字构成的析取式 也称为子句 clause 简单合取式 基本积 仅由有限个文字构成的合取式 例如 p q既是一个文字的简单析取式 又是一个文字的简单合取式 p q p r均是有两个文字的简单析取式 即子句 p q r p q q均是有三个文字的简单合取式 定理2 1 1 一个简单析取式是重言式 当且仅当它同时含有一个命题变元及其否定 2 一个简单合取式是矛盾式 当且仅当它同时含有一个命题变元及其否定 例如 p q p是重言式p q q是矛盾式 范式 normalform 的定义 定义2 3析取范式由有限个简单合取式构成的析取式 简称DNF disjunctivenormalform 合取范式由有限个简单析取式构成的合取式 简称CNF conjunctivenormalform 析取范式的例子 A A1 A2 An p q r p q q p 合取范式的例子 A B1 B2 Bm p q r p q q p 子句 范式存在定理 定理2 3任一命题公式都存在着与之等值的析取范式任一命题公式都存在着与之等值的合取范式 求范式的步骤如下 消去联结词 和 利用双重否定律消去否定联结词 或利用德摩根律将否定联结词 移到各命题变元前 内移 利用分配律 结合律将公式归约为合取范式和析取范式 例题 例2 7 求 p q p的合取范式和析取范式 p q p p q p p p q p q p p p q p q p p p q p p q p p p q 1 q p 1 q 1 q p 1 q p 合取范式 合取范式 析取范式 练习 求析取范式与合取范式 p q r 合取范式 p r q r p q r 析取范式 p q r p r q r 极小项与极大项 定义2 4极小项 在含有n个命题变元的简单合取式中 1 若每个命题变元和它的否定式不同时出现 而二者之一必出现且仅出现一次 2 且第i个命题变元 或它的否定式 出现在从左算起的第i位上 极大项 简单析取式中满足如上条件 极小 大 项的核心性质 定理 n个命题变元共有2n个极小项 极大项 每个极小 大 项只有一个成真 假 赋值 且各极小项的成真赋值互不相同 极小项和它的成真赋值构成了一一对应的关系 极小项的记号与编码 可用成真赋值为极小项进行编码 并把编码作为m的下标来表示该极小项 叫做该极小项的名称 极小项与其成真赋值的对应关系为 变元对应1 而变元的否定对应0 极小项的记号 n 3 极大项的记号 n 2 3 练习 写出极小项的公式 m4m6m7 当变元的个数分别为3 4时 写出极大项的公式 M4M6M7 当变元的个数分别为3 4时 定理 极小项与极大项 定理2 4 mi Mimi Mi 主范式的定义 定义2 5主析取范式 析取范式中所有的简单合取式都是极小项 主合取范式 合取范式中所有的简单析取式都是极大项 例 m0 m1 m7 n 3 M0 M2 M6 n 3 问题 对于n个命题变元 有多少个主析 合 取范式 主范式的存在性与唯一性 定理2 5任何命题公式都存在与之等值的主析取范式和主合取范式 并且是唯一的 证明 1 存在性 等值演算 2 唯一性 反证法 例题与练习 例2 8 求主析取范式与主合取范式 p q r 合取范式 p r q r p q r 析取范式 p q r p r q r 练习 求p q的主范式 主范式与真值表 定理若公式A中含n个命题变元 A的主析取范式含s 0 s 2n 个极小项 则A有s个成真赋值 它们是所含极小项编号的二进制表示其余2n s个赋值都是成假赋值 反之也成立 对主合取范式有相同的结果 对应成假赋值 从真值表求主范式 例 用真值表法 求 p q r的主范式 m001 m011 m100 m101 m111 m1 m3 m4 m5 m7 排斥或 的公式 排斥或 p q p q m1 m2 通过主范式判别公式类型 定理A为重言式当且仅当A的主析取范式含全部2n个极小项 主合取范式0个极大项 A为矛盾式当且仅当A的主析取范式不含任何极小项 主合取范式含所有的极大项 A为可满足式当且仅当A的主析取范式至少含一个极小项 主析取范式与主合取范式的关系 定理同一公式的主析取范式中极小项m的下标和主合取范式中极大项M的下标是互补的 换言之 对于任一公式 在它的2n个赋值中 非0即1 因此其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为2n 且其下标不会相同 练习 由主析取范式 求主合取范式 1 A m1 m2 两个变元 2 B m1 m2 m3 三个变元 作业 习题二38 40页题目 5 6 910 1213 1425 26 练习 12 已知公式A含3个命题变项p q r 且它的成真赋值为000 011 110 求A的主范式 13 已知公式A含3个命题变项p q r 且它的成假赋值为010 011 110 111求A的主范式 14 已知公式A含n个命题变项 且无成假赋值 求A的主合取范式 2 3联结词的完备集 定义2 6n元真值函数F 0 1 n 0 1 定理每个真值函数 都一一对应一个真值表 每个真值函数 都存在许多与之等值的命题公式 反之 每个命题公式对应唯一的与之等值的真值函数 定义2 7设S是联结词集合 如果任何n元真值函数都可以由仅含S中的联结词构成的公式表示 则称S是联结词完备集 联结词的完备集 定理2 6S 联结词完备集 推论以下集合都是完备集 联结词的完备集 定义2 8与非联结词 p q p q 或非联结词 p q p q 定理2 7 是联结词完备集 2 4可满足性问题与消解法 命题公式的 可满足性问题 SAT问题 SATisfiabilityProblem 是 算法理论 的核心问题之一 真值表 主范式的计算量大 从 算法复杂度 上讲 SAT是第一个被证明为 NP难 的问题 八皇后问题 SAT问题 很多问题可以转化为SAT问题如 著名的八皇后问题鸽笼问题图着色问题等 本节内容将一般的SAT问题转化为 合取范式的SAT问题 理论准备 从 消解规则 到 可满足的否证 可编程实现的 消解算法 在掌握理论与算法的同时 理解其背后的 思想 更重要 合取范式的可满足性 SAT 问题 合取范式 S C1 C2 C3 CnS表示合取范式 C表示简单析取式 子句 L表示文字 S是可满足的当且仅当每个Ci都是可满足的或者 只要一个子句不可满足 则S不可满足进一步 只要一部分不满足 则整体不可满足 对整个合取范式的不可满足问题 采用 分而治之 的思想多个子句合取转化为 比较少 的子句合取的相应问题以致于最终转化为 一个子句 或 两个子句合取 的 不 可满足问题 一个子句 简单析取式 Ci L1 L2 L3 Lk一个简单析取式中同时出现 文字L 如p 及它的补Lc 如 p 则它为永真式 永真式可以从合取范式中除去 是多余的 因此 假设简单析取式中不同时出现某个命题变项和它的否定 与 极大项 类似 简单的消解规则 简单的消解规则 合取范式 S C1 1 C3 Cn消解后的范式S C1 C3 Cn根源 一个子句中同时出现文字L及它的补Lc 那么在不同的子句中 同时出现文字L及它的补Lc 是不是也能对合取范式进行化简呢 少了一个子句 子句间的 冲突 造成合取范式 不可满足 合取范式 S C1 C2 C3 Cn S C1 C2 p p 子句间的 冲突 的根源在于 不同的子句中 同时出现文字L及它的补Lc S p q p q q S p q q r p q r 引入消解法 将 p p 削去 归结为 空子句 并规定 空子句 不可满足 空子句 不可满足 Ci L1 L2 L3 Lk文字越多 越容易满足文字越少 越难满足 越易冲突 如子句p 在p 1时被满足而子句p q 在p 0时也能满足 q 0 定理 空子句 记为 不可满足 定理 含有空子句的合取范式是不可满足的 S C1 C2 C3 不可满足 通过 消解规则 寻找 冲突 S C1 C2 p p S C1 C2 不可满足 一般情况 如 S p q q r p q r 少了一个子句 消解规则 一般的 消解规则 定义2 9C1与C2是两个子句 简单析取式 C1 C1 L 如 p q r C2 C2 Lc 如 p r s t 消解式 消解规则 Res C1 C2 C1 C2 消解式 Res C1 C2 q r r s t p q p s tRes p p 消解规则的理论基础 定理2 8C1 C2 Res C1 C2 即 C1 C2可满足当且仅当消解式Res C1 C2 可满足 例 若C1 p q rC2 p r则C1 C2 p q r p r Res C1 C2 p q 例题 求消解结果 1 C1 p q rC2 p r s2C1 p q rC2 p q r Res C1 C2 q r sRes C1 C2 p p r q q r 例题 通过消解规则 寻找子句间的 冲突 S p q q r p q r q q p与 p为消解文字 不可满足 不可满足 消解序列与否证 定义2 10设S是一个合取范式 C1 C2 Cn是一个如下生成的子句序列 对每一个i 1 i n Ci是S中的一个子句 简单析取式 或者Ci是它之前的某两个子句 简单析取式 Cj Ck 1 j k i 的消解结果 则称此序列是由S导出的消解序列 当Cn 空子句 时 称此序列是S的一个否证 例题 构造公式的否证 从而证明它是矛盾式 S p q q r p q r q q 否证 p q q r p q r q q 练习 构造公式的否证 从而证明它是矛盾式 q 否证 p q p q q q S p q p q q 练习 构造公式的否证 从而证明它是矛盾式 q r q p q p r q r p r r q 否证 p q q r p r r q r q q 理论基础 消解的完全性 推论如果合取范式S有否证 则S是不可满足的 定理2 10 消解的完全性 如果合取范式S是不可满足的 则S有否证 推论合取范式S是不可满足的当且仅当S有否证 如何判别可满足的公式 p p q p q q r q r p p r p r q p p p q p q 当遍历所有的消解结果后 都不出现 则公式可满足 面向实用 消解算法 输入 合式公式A输出 当A是可满足的 回答 yes 否则回答 no 步骤如下 求A的合取范式SS1为S的所有子句的集合 S0与S2为空集 典型的判定问题 当前的子句集合 历史子句集合 消解出的子句集合 算法的核心步骤 对S0与S1运用消解规则 3 对S0中的每一个子句C1与S1中的每一个子句C2如果C1 C2可以消解 则计算C Res C1 C2 如果C 则输出 no 计算结束否则 如果S0与S1都不包含C则将C加入S2 算法的核心步骤 对S1运用消解规则 4 对S1中的每一对子句C1与C2如果C1 C2可以消解 则计算C Res C1 C2 如果C 则输出 no 计算结束否则 如果S0与S1都不包含C则将C加入S2 算法循环或结束 5 如果S2中没有任何元素则输出 yes 计算结束否则把S1加入S0 令S1等于S2 清空S2 返回3 例题 例2 14 通过消解法判断公式是否是可满足的 1 p q p q q 2 p p q p q q r q r 1 p q p q q 第一次循环2 已相互消