离散数学-命题逻辑-4-左孝凌.pdf

析取范式与合取范式 定义1 7 2定义1 7 2 由一些命题变元或其否定构成的析取式 称为基本和 也叫简单析取式 约定单个变元或 其否定是基本和 例 p q p q p q q p q都是基本和 定义1 7 3定义1 7 3 由一些命题变元或其否定构成的合取式 称为基本积 也叫简单合取式 约定单个变元或 其否定是基本积 例 p q p q p q p q p都是基本积 析取范式与合取范式 定义1 7 4定义1 7 4 由基本和的合取构成的公式叫做合取范 式 约定单个基本和是合取范式 例如 P P R P Q P Q R P Q Q R 是合取范式 定义1 7 5定义1 7 5 由基本积的析取构成的公式叫做析取范 式 约定单个基本积是析取范式 例如 P P R P Q P Q R P Q Q R 是析取范式 求析取范式和合取范式的步骤 任何命题公式都可以化成与其等价的析取范式 或合取范式 求析取范式和合取范式的步骤如 下 消去联结词 和 利用双重否定律消去否定联结词 或利用德 摩根律将否定联结词 移到各命题变元前 内移 利用分配律 结合律将公式归约为合取范式和 析取范式 求合取范式 例求命题公式 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 p p q p p q p 消去 p q p p q p 内移 p p q p 吸收律 析取范式 p p p q 交换律 p p q 幂等律 析取范式 由此例可以看出 命题公式的析取范式也不惟一 主范式 由于析取范式和合取范式不惟一 所以使用起 来很不方便 为此 引入主析取范式和主合取 范式的概念 当命题变元的顺序约定以后 主 析取范式和主合取范式是惟一的 析取范式和合取范式的基本成分是基本积和基 本和 而主析取范式和主合取范式的基本成分 是极小项和极大项 它们分别是特殊的基本积 和基本和 极小项 定义1 7 6 在基本积中 每个变元及其否定不同时存在 但两 者之一必须出现且仅出现一次 这样的基本积叫做布尔合取 也叫小项或极小项 p q的极小项为 p q p q p q p q 两个命题变元的极小项共4 22 个 三个命题变元的极小项 共8 23 个 一般地说 n个命题变元共有2n个极小项 表1 7 1是两个变元p和q的极小项的真值表 表1 7 1 pqp qp q p q p q 000001 010010 100100 111000 极小项的性质 极小项有下列的性质 每个极小项只有一个成真赋值 且各极小项的成真赋值互 不相同 极小项和它的成真赋值构成了一一对应的关系 可用成真赋值为极小项进行编码 并把编码作为m的下标来 表示该极小项 叫做该极小项的名称 两个命题变元的极小项 成真赋值和名称如表1 7 2所示 三个命题变元的极小项 成真赋值和名称如表1 7 3所示 从表1 7 2和表1 7 3中可以看出 极小项与其成真赋值的 对应关系为 变元对应1 而变元的否定对应0 极小项的性质 表1 7 2 极小项 表1 7 2 极小项成真赋值成真赋值名称名称 p q p q0000m m0 0 p q p q0101m m1 1 p qp q1010m m2 2 p qp q1111m m3 3 表1 7 3 极小项 表1 7 3 极小项成真赋值成真赋值名称名称 p q r p q r000000m m0 0 p q r p q r001001m m1 1 p q r p q r010010m m2 2 p q r p q r011011m m3 3 p q rp q r100100m m4 4 p q rp q r101101m m5 5 p q rp q r110110m m6 6 p q rp q r111111m m7 7 极小项的性质 任意两个不同的极小项的合取式为永假式 例如 m001 m100 p q r p q r p q r p q r F 全体极小项的析取式为永真式 记为 12 0 n i i m m0 m1 T 12 n m 主析取范式 定义1 7 7 对于给定的命题公式 如果有一个它的 等价公式 仅由极小项的析取组成 称该公式 为原公式的主析取范式 任何命题公式都存在着与之等价的主析取范 式 主析取范式 一个命题公式的主析取范式可以由以下两种方法求得 等价演算法 即用基本等价公式推出 用等价演算法求主析取范式的步骤如下 化归为析取范式 除去析取范式中所有永假的基本积 在基本积中 将重复出现的合取项和相同变元合并 在基本积中补入没有出现的命题变元 即添加 p p 再用分配律展开 最后合并相同的极小 项 主析取范式 例用等价演算法求 p q p r q r 的主析取范式 解 p q p r q r p q r r p r q q q r p p p q r p q r p q r p q r p q r p q r p q r p q r p q r p q r m111 m110 m011 m001 m7 m6 m3 m1 1 3 6 7 主析取范式 真值表法 即用真值表求主析取范式 用真值表求主析取范式的步骤如下 构造命题公式的真值表 找出公式的成真赋值对应的极小项 这些极小项的析取就是此公式的主析取 范式 主析取范式 例用真值表法 求 p q r的主析取范式 解 表1 7 4是 p q r的真值表 公式的成真赋值对应的极小项为 p q r 成真赋值为001 p q r 成真赋值为011 p q r 成真赋值为100 p q r 成真赋值为101 p q r 成真赋值为111 p q r的主析取范式为 p q r p q r p q r p q r p q r m111 m101 m100 m011 m001 m7 m5 m4 m3 m1 1 3 4 5 7 表1 7 4 p 表1 7 4 pq qr rp qp q p q r p q r 0 00 00 01 10 0 0 00 01 11 11 1 0 01 10 01 10 0 0 01 11 11 11 1 1 10 00 00 01 1 1 10 01 10 01 1 1 11 10 01 10 0 1 11 11 11 11 1 主析取范式 矛盾式无成真赋值 因而主析取范式不含 任何极小项 将矛盾式的主析取范式记为0 而 重言式无成假赋值 因而主析取范式含2n n为 公式中命题变元的个数 个极小项 至于可满足 式 它的主析取范式中极小项的个数一定小于 等于2n 极大项 定义1 7 8 在基本和中 每个变元及其否定不同时存在 但两 者之一必须出现且仅出现一次 这样的基本和叫作布尔析 取 也叫大项或极大项 两个变元p q构成的极大项为 p q p q p q p q 三个命题变元p q r构成的极大项为 p q r p q r p q r p q r p q r p q r p q r p q r 两个命题变元的极大项共4 22 个 三个命题变元的极大项 共8 23 个 一般地说 n个变元共有2n个极大项 极大项的性质 每个极大项只有一个成假赋值 极大项不同 成假赋值也不 同 极大项和它的成假赋值构成了一一对应的关系 故可用 成假赋值为该极大项进行编码 并把编码作为M的下标来表 示该极大项 叫做极大项的名称 例两个变元p q的极大项 p q 它的成假赋值是11 表示 为M11 把11理解为2进制数 它的10进制表示为3 所以M11 又表示为M3 两个命题变元的极大项 成假赋值及名称见表1 7 5 三个 命题变元的极大项 成假赋值及名称见表1 7 6 从表1 7 5和表1 7 6中可以看出 极大项与成假赋值的对应 关系为 变元对应0 而变元的否定对应1 极大项的性质 表表1 7 5 极大项极大项成假赋值成假赋值名称名称 p qp q0000M M0 0 p qp q0101M M1 1 p q p q1010M M2 2 p q p q1111M M3 3 表表1 7 6 极大项极大项成假赋值成假赋值名称名称 p q rp q r000000M M0 0 p q rp q r001001M M1 1 p q rp q r010010M M2 2 p q rp q r011011M M3 3 p q r p q r100100M M4 4 p q rp q r101101M M5 5 p q r p q r110110M M6 6 p q r p q r111111M M7 7 极大项的性质 任意两个不同的极大项的析取式为永真式 例如 M001 M100 T 全体极大项的合取式为永假式 记为 12 0 n i i M M0 M1 12 nM F 主合取范式 定义1 5 8 对于给定的命题公式 如果有一个它的等价公式 仅由极 大项的合取组成 则该等价式称为原公式的主合取范式 任何命题公式都存在着与之等价的主合取范式 主合取范式也可 以由以下两种方法求得 等价演算法 即用基本等价公式推出 其演算步骤如下 化归为合取范式 除去所有永真的基本和 在基本和中合并重复出现的析取项和相同的变元 在基本和中补入没有出现的命题变元 即增加 p p 然后 应用分配律展开公式 最后合并相同的极大项 主合取范式 例用等价演算法求 p q r的主合取范式 解 p q r p q r p q r p r q r p r q q q r p p p r q p r q p q r p q r p q r p q r p q r M000 M010 M110 M0 M2 M6 0 2 6 主合取范式 真值表法 用真值表求主合取范式 用真值表求主合取范式的步骤如下 构造命题公式的真值表 找出公式的成假赋值对应的极大项 这些极大项的析取就是此公式的主合取范式 主合取范式 例用真值表法求 p q r的主合取范式 解 p q r的真值表是表1 7 7 公式的成假赋值对应 的大项为 p q r 成假赋值为000 p q r 成假赋值为010 p q r 成假赋值为110 主合取范式为 p q r p q r p q r M000 M010 M110 M0 M2 M6 0 2 6 表1 7 7 p 表1 7 7 pq qr rp qp q p q r p q r 0 00 00 01 10 0 0 00 01 11 11 1 0 01 10 01 10 0 0 01 11 11 11 1 1 10 00 00 01 1 1 10 01 10 01 1 1 11 10 01 10 0 1 11 11 11 11 1 主合取范式 矛盾式无成真赋值 因而矛盾式的主合取范 式含2n n为公式中命题变元的个数 个极大项 而 重言式无成假赋值 因而主合取范式不含任何极 大项 将重言式的主合取范式记为1 至于可满足 式 它的主合取范式中极大项的个数一定小于2n 主析取和主合取范式的关系 在前面例中 求出 p q r的主析取范式为 m7 m5 m4 m3 m1 1 3 4 5 7 求出该公式的主合取范式为 M0 M2 M6 0 2 6 比较这两个结果 得出以下的结论 同一公式的主析取 范式中m的下标和主合取范式中M的下标是互补的 因 此 知道了主析 合 取范式就可以写出主合 析 取范 式 数理逻辑的主要任务是用逻辑的方法研究数 学中的推理 所谓推理是指从前提出发 应用推 理规则推出结论的思维过程 任何一个推理都由 前提和结论两部分组成 前提就是推理所根据的 已知命题 结论则是从前提出发通过推理而得到 的新命题 要研究推理 首先应该明确什么样的 推理是有效的或正确的 1 8 命题逻辑的推论理论 1 8 命题逻辑的推论理论 定义1 8 1 设H1 H2 Hn和C是n 1个命题公式 若 H1 H2 Hn C 则称C为H1 H2 Hn的有效结论 也 称C可由H1 H2 Hn逻辑的推出 H1 H2 Hn叫做C的一 组前提 可记为 H1 H2 Hn C 亦可记为 H1 H2 Hn C 由定义1 8 1可以看出 要证明C是一组前提H1 H2 Hn的 有效结论 只需证明H1 H2 Hn C为重言式 证明一 个公式为重言式 可以用真值表 等价演算 主析 合 取范 式或已知的蕴含式等方法进行 用等价演算和主析 合 取范 式证明重言式的方法前面已经讨论过了 要证明C为前提H1 H2 Hn的有效结论 只需构造命题公式H1 Hn C 的真值表 证明它是重言式 因为条件命题H1 Hn C为假当且仅当它的前件H1 Hn为真 后件 C为假 只要能排除前件为真 后件为假的情况 H1 Hn C就是重言 式 从而C为一组前提H1 H2 Hn的有效结论 于是就有了下面方法 构造H1 H2 Hn与C的真值表 且做在一个表上 找出H1 H2 Hn都为真的行 若C也为真 则H1 H2 Hn C 即C 为前提H1 H2 Hn的有效结论 找出C为假的行 若在每个这样的行中 H1 H2 Hn的真值至少有一 个为假 则H1 H2 Hn C 即C为一组前提H1 H2 Hn 的有效 结论 用真值表证明有效结论 例1 分析事实 如果我有时间 那么我就去上街 如果我 上街 那么我就去书店买书 但我没有去书店买书 所以 我没有时间 试指出这个推理前提和结论 并证明结论 是前提的有效结论 解 令p 我有时间 q 我去上街 r 我去书店买书 根据题意 前提为 p q q r r 结论为 p 以下证明 p是一组前提p q q r r的有效结论 即证明 p q q r r p 用真值表证明有效结论 作公式p q q r r p 的真值表 如表1 8 1所示 从表中可以看出 p q q r r都为1的行 赋值000的行 p也为1 p为0的行 赋值100 101 110 111的行 p q q r r至少有一个为0 表1 8 1 pqrp qq r r p 0001111 0011101 0101011 0111101 1000110 1010100 1101010 1111100 所以 p q q r r p 用真值表证明有效结论 推理方法 我们已经有了判断推理是否正确的4种方法 即真值表 法 等值演算法 主析取范式法和蕴含演算法 当推理中 包含的命题变元较多时 以上4种方法的演算量太大 给推 理带来了困难 为此引入命题逻辑的推理理论 命题逻辑 的推理是一个描述推理过程的命题公式序列 其中的每个 命题公式或者是已知前提 或者是由某些前提应用推理规 则得到的结论 中间结论或推理中的结论 它有两种方 法 直接推理和间接推理 直接推理的基本思想是 由一组前提出发 利用一些公认的规则 根 据已知的等价式或蕴含式 推演得到有效结论 公认的推理规则有4条 P规则 前提在推导过程中的任何时候都可以引入使用 T规则 推理中 如果一个或多个公式 蕴含了公式S 则公式S可 以引入到以后的推理之中 置换规则 在推导过程的任何步骤上 命题公式中的子公式都可 以用与之等价的公式置换 合取引入规则 任意两个命题公式A B可以推出A B 常用的等价式和蕴合式包括1 4节中的15个命题定律 1 5节中的13个 重要的蕴含式及过去学过的所有等价式和蕴含式 直接推理 例用直接推理法证明 p q q r p r 证明 p qP pP qT 假言推理 q rP rT 假言推理 直接推理 间接推理 间接推理常有下列两种方法 CP规则 有时要证明的有效结论是一个条件命题 即要证明 H1 H2 Hn A B 其中