L2命题逻辑2 离散数学ppt课件.ppt

命题逻辑 二 1 LuChaojun SJTU 2 2 主要内容 命题与命题联结词命题公式等值演算命题公式的范式联结词的功能完全集永真蕴涵式命题逻辑推理 LuChaojun SJTU 3 等值关系 一种重要的数学论证方法是 将一个命题用另一个等值命题替换 两个命题公式A和B若在任一赋值下的真值都相同 则称A和B等值 equivalence 记作A B 例如 a b a b这两个公式语法上是不同的 但语义上相同 LuChaojun SJTU 4 与 的关系 等值定理 对公式A和B A BiffA B是永真式证明 若A B永真 则在任一赋值下其真值都为1 依 的定义知A和B真值相同 若A B 则在任一赋值下A和B都有相同的真值 依 的定义即A B真值为1 注 教材中干脆用此关系作为等值的定义 LuChaojun SJTU 5 与 的不同 从形式系统角度看 是系统内的符号 A B是系统内的命题公式 语法 是系统外的符号 A B不是命题公式 在系统外观察系统内两个公式是否等值 语义 从真假性来看A B是表示A和B是否等值的一个命题 只有A B为真 才肯定A和B等值 但A B可为假 A B则肯定地表示A和B等值 LuChaojun SJTU 6 补充 等值关系 的性质 和数学里的等号一样 具有下面三个性质 1 自反性 A A2 对称性 若A B 则B A3 传递性 若A B且B C 则A C这三条性质刻画了两事物 等同 同一性 概念 满足这三条性质的关系称为等价关系 在等值概念下 命题常量可看成只有两个 1 0 6 LuChaojun SJTU 7 如何证明两公式等值 真值表技术利用等值定理利用基本等值式进行等值演算 7 LuChaojun SJTU 8 例 利用真值表证明等值 证明 a a b b 证 列出真值表即可看出等式成立 LuChaojun SJTU 9 例 利用等值定理证明等值 证明 a b a b 根据等值定理 可转化为证明 a b a b 是永真式 比如列出此公式的真值表 这样本质上还是真值表技术 还可利用重言式推理系统 9 LuChaojun SJTU 10 基本等值式 1 结合律 A B C A B C A B C A B C A B C A B C 2 交换律A B B AA B B AA B B A注意 没有 的结合律和交换律 LuChaojun SJTU 11 基本等值式 续 3 分配律A B C A B A C A B C A B A C A B C A B A C 4 吸收律A A B AA A B A LuChaojun SJTU 12 基本等值式 续 5 关于否定词的等值式 A A 对合律 A B A B DeMorgan律 A B A B DeMorgan律 A B A B A B A B A B A B A B 基本等值式 续 6 相同命题变量的等值式A A A 等幂律 A A A 等幂律 A A 1A A 1A A 1 排中律 A A 0 矛盾律 A A A A A AA A 0此处的1 0代表任意真值恒为1 0的命题公式 LuChaojun SJTU 13 LuChaojun SJTU 14 基本等值式 续 7 部分赋值的等值式A 0 AA 1 A1 A AA 0 A1 A A0 A A A 1 1A 0 0A 1 10 A 1 14 LuChaojun SJTU 15 基本等值式 续 8 关于 的等值式A B A B A B A B B A 假言易位 A B C A B C 合取前提 A B C B A C 交换前提 A C B C A B C 析取前提 A B A B A 归谬论 A B C A B A C A B C A B A C 基本等值式 续 9 关于 的等值式A B A BA B A B A B 同真或同假 A B A B A B 一真一假 A B A B B A 充分必要 由于 更易理解和处理 常利用8和9类的等值式将含 和 的公式改写成仅含有 的公式 LuChaojun SJTU 16 置换规则 定理 设A A B B 则有 1 A A 2 A B A B 3 A B A B 4 A B A B 5 A B A B 置换 将公式的一部分用等值公式替换 定理 置换规则 设B C 若将A中出现的一个或几个B换成C后得到公式A 则有A A LuChaojun SJTU 17 LuChaojun SJTU 18 等值演算 等值演算 利用等值定律 基本等值式以及替换规则进行公式推演 一般是将 两边的公式推演成相同形状的公式 从而证明等值式成立 例 等值演算 证明 a b c b c a c c 证明 左端 a b c b a c 分配律 a b c b a c 结合律 a b c b a c 德摩根律 a b b a c 分配律 a b a b c 交换律 1 c 置换 c LuChaojun SJTU 19 LuChaojun SJTU 20 对偶式和内否式 观察下面两个等值式 分配律 A B C A B A C A B C A B A C 可见 命题逻辑公式存在 对偶 规律 限制性公式 公式中只用到联结词 将限制性公式A中的 1 0分别以 0 1替换 所得公式称为A的对偶式A 将限制性公式A中所有肯定形式出现的变元x换成 x 所有否定形式出现的变元 x换成x 所得公式称为A的内否式A 其实 求A 时A不必是限制性公式 即可包含 和 LuChaojun SJTU 21 A 和A 的性质 定理 1 A A A A 2 A B A B A B A B 3 A B A B A B A B 定理 1 A A A A 2 A A DeMorgan律的一般形式 3 A A LuChaojun SJTU 22 命题公式的对偶性质 推论 若A B 则 A B 推论 若A B 则A B 一旦证明了两公式等值 则同时证明了它们的对偶式也等值 LuChaojun SJTU 23 23 主要内容 命题与命题联结词命题公式等值演算命题公式的范式联结词的功能完全集永真蕴涵式命题逻辑推理 LuChaojun SJTU 24 公式有没有标准形式 命题公式的数量是无穷多的 即便只有一个命题变量x 也可以写出x x x x x x x x x x 但若按等值关系对全体公式进行划分 n个命题变量所能形成的不同公式仅有22n个 Why 问题 与命题公式A等值的公式能否都化为某种标准形式 借助于标准形容易判断两个公式是否等值 借助于标准形容易判断公式是否永真式或永假式 LuChaojun SJTU 25 简单析 合 取式 一个命题符号a及其否定 a统称为文字 由文字利用 联结而成的公式称为简单析 合 取式 简单析取式例 x x x y x y x简单合取式例 x x x y x y x定理 1 一个简单析取式是永真式iff它同时包含一个命题符号及其否定 2 一个简单合取式是矛盾式iff它同时包含一个命题符号及其否定 析 合 取范式 由若干个简单合取式利用 联结而成的公式称为析取范式 形如 A1 A2 An 诸Ai是简单合取式 由若干个简单析取式利用 联结而成的公式称为合取范式 形如 A1 A2 An 诸Ai是简单析取式 定理 1 一个析取范式是矛盾式iff它的每个简单合取式都是矛盾式 2 一个合取范式是永真式iff它的每个简单析取式都是永真式 LuChaojun SJTU 26 LuChaojun SJTU 27 范式存在定理及求法 范式定理 对任一命题公式都存在与之等值的析取范式和合取范式 等值变换法求范式 1 消去 2 深入到命题符号之前 3 深入至此已是范式 4 可选 化简 27 LuChaojun SJTU 28 求范式 1 消去 方法 利用下列等值式A B A BA B A B A B 用于求析取范式 A B A B A B 用于求合取范式 例 求 x y x y 的析取范式 x y x y x y x y x y x y 28 LuChaojun SJTU 29 求范式 2 否定词深入 方法 利用下列等值式 A B A B A B A B A A例 x y x y x y x y x y x y x y x y x y x y 29 LuChaojun SJTU 30 求范式 3 合 析 取词深入 方法 利用分配律A B C A B A C 用于求析取范式 A B C A B A C 用于求合取范式 例 x y x y x y x y x y x y x y x y x y x y x y x y x x x y y x y y 30 LuChaojun SJTU 31 求范式 4 可选 化简 方法 利用下列等值式消去矛盾式A 0 0A 0 A例 x y x y x y x y x y x y x y x y x y x y x y x y x x x y y x y y x y x y 31 LuChaojun SJTU 32 范式的用途 判断A是否永真式求A的合取范式 若每个简单析取式都含有某个变元及其否定 如x和 x 则A是永真式 判断A是否矛盾式求A的析取范式 若每个简单合取式都含有某个变元及其否定 如x和 x 则A是矛盾式 判断A B 求A和B的同一种范式 看是否相同 这里有问题 范式唯一吗 32 LuChaojun SJTU 33 极小项与极大项 设公式只涉及n个命题变量x1 xn 极小项 n个文字的简单合取式 诸xi以xi或 xi形式出现且只出现一次 且xi出现在左起第i个位置 极小项有2n个 根据对应的成真赋值 可记为m0 00 x1 xn 1 xnm0 01 x1 xn 1 xnm0 10 x1 xn 1 xn m1 11 x1 xn 1 xn 设公式只涉及n个命题变量x1 xn 极大项 n个文字的简单析取式 诸xi以xi或 xi形式出现且只出现一次 且xi出现在左起第i个位置 极大项有2n个 根据对应的成假赋值 可记为M0 00 x1 xn 1 xnM0 01 x1 xn 1 xnM0 10 x1 xn 1 xn M1 11 x1 xn 1 xn LuChaojun SJTU 34 极小 大项的性质 每个极小项只在一个赋值下为真 一个赋值不能使两个极小项都为真 两个极小项的合取为0极小项两两不等值 若A由k个极小项的析取组成 则其余2n k个极小项的析取就是 A 若k 2n 则A是重言式 每个极大项只在一个赋值下为假 一个赋值不能使两个极小项都为假 两个极大项的析取为1极大项两两不等值 若A由k个极大项的合取组成 则其余2n k个极大项的合取就是 A 若k 2n 则A是矛盾式 34 LuChaojun SJTU 35 主范式 主析取范式 仅由极小项构成的析取范式 定理 任何非永假的命题公式都存在唯一与之等值的主析取范式 主合取范式 仅由极大项构成的合取范式 定理 任何非永真的命题公式都存在唯一与之等值的主合取范式 LuChaojun SJTU 36 主范式的求法 1 利用基本等值式 1 先求一个析取范式 2 若简单合取式A中未出现命题变量x 则通过A A x x A x A x 来补足x 3 消去重复出现的变量 矛盾式及重复出现的极小项 利用基本等值式 1 先求一个合取范式 2 若简单析取式A中未出现命题变量x 则通过A A x x A x A x 来补足x 3 消去重复出现的变量 永真式及重复出现的极大项 36 LuChaojun SJTU 37 例 基本等值式方法 例 求x y的主析取范式 1 x y x y 2 x x y y x y x y y y x x x y x y 3 消去一个 x y 于是 x y m00 m01 m11 例 求 x y 的主合取范式 1 x y x y 2 x x y y x y x y y y x x x y x y 3 消去一个 x y 于是 x y M00 M01 M11 37 LuChaojun SJTU 38 主范式的求法 2 利用真值表 1 根据每个使A为真的赋值写一个包含各命题变量的合取式 即极小项 2 写出各极小项的析取式 即主析取范式 利用真值表 1 根据每个使A为假的赋值写一个包含各命题变量的析取式 即极大项 2 写出各极大项的合取式 即主合取范式 38 LuChaojun SJTU 39 例 真值表方法求主析取范式 例 A有三个成真赋值 由 x y 0 0 可写出合取式 x y由 x y 0 1 可写出合取式