离散数学 第三讲.pdf

2006 3 1电子工程学院 离散数学1 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 1 4 1 其它联结词其它联结词 定义定义1 11 设设p q为两个 命题 复合命题 为两个 命题 复合命题 p与与q之 中恰有一个成立 之 中恰有一个成立 称为称为p 与与q的的排斥或排斥或 异或 记为 异或 记为p q 称为排斥 或 称为排斥 或 P q为真当且仅当为真当且仅当 p与与q中恰有一个为真 中恰有一个为真 011 101 110 000 p qqp 2006 3 1电子工程学院 离散数学2 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 联结词联结词 有以下性质 设 有以下性质 设p q r为命题 则 为命题 则 p q q p p q r p q r p q r p q p r 请大家自证 请大家自证 p q p q p q p q p q p p 0 0 p p 1 p p 2006 3 1电子工程学院 离散数学3 定理定理 设设p q r为命题 若为命题 若p q r 则 则 p r q q r p p q r 为永假式 矛盾式 证明 为永假式 矛盾式 证明 p r p p q 0 q q q r q p q 0 q q p q r r r 0 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 2006 3 1电子工程学院 离散数学4 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 定义定义1 12 设设p q为两个 命题 复合命题 为两个 命题 复合命题 p不蕴 涵 不蕴 涵q 称为称为p与与q的的条件否 定 条件否 定 记为 记为p q p q为 真当且仅当 为 真当且仅当p为真为真q为 假 为 假 p q p q 011 101 010 000 p qqp 2006 3 1电子工程学院 离散数学5 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 定义定义1 13设设p q为两个命 题 复合命题 为两个命 题 复合命题 p与与q的否 定 的否 定 称为称为p与与q的的与非式与非式 记为 记为p q p q为真当 且仅当 为真当 且仅当p与与q不同时为真 不同时为真 p q p q 011 101 110 100 p qqp 2006 3 1电子工程学院 离散数学6 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 联结词联结词 有以下性质 设 有以下性质 设p q为命题 则 为命题 则 p p p p p p q p q p q p q p p q q p q p q p q 2006 3 1电子工程学院 离散数学7 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 定义定义1 14 设设p q为两个命 题 复合命题 为两个命 题 复合命题 p或或q的否 定 的否 定 称为称为p与与q的的或非式或非式 记为 记为p q p q为真当 且仅当 为真当 且仅当p与与q不同时为真 不同时为真 p q p q 011 001 010 100 p qqp 2006 3 1电子工程学院 离散数学8 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 联结词联结词 有以下性质 设 有以下性质 设p q为命题 则 为命题 则 p p p p p p q p q p q p q p p q q p q p q p q 2006 3 1电子工程学院 离散数学9 1010101011 1100110001 1111000010 1111111100 1p qp q p q p q p qp qqp 1010101011 1100110001 1111000010 0000000000 p qp qqq ppp qp q0qp 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 2006 3 1电子工程学院 离散数学10 1 4 2 全功能集全功能集 定义定义1 15 一个一个n维卡氏积维卡氏积 0 1 n到到 0 1 的函数称为的函数称为n元 真值函数 定义 元 真值函数 定义1 16 在一个联结词的集合中 如果一个联结词可 以用集合中的其余联结词表示 则称该联结词为 在一个联结词的集合中 如果一个联结词可 以用集合中的其余联结词表示 则称该联结词为冗余 的 冗余 的联结词 否则称为联结词 否则称为独立的独立的联结词 联结词 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 2006 3 1电子工程学院 离散数学11 前面定义的前面定义的5个联结词可组成集合 个联结词可组成集合 而 而 p q p q p q p q q p p q q p 显然 联结词 显然 联结词 是冗余的 再考虑集合 是冗余的 再考虑集合 而 而 p q p q p q 所以 联结词 也是冗余的 所以 联结词 也是冗余的 请大家讨论 请大家讨论 无冗余 且无冗余 且 也是无冗 余的 也是无冗 余的 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 2006 3 1电子工程学院 离散数学12 定义定义1 17 若任一真值函数 命题公式 都可以用仅 含某一联结词集合的联结词的命题公式表示 则称 该联结词集为 若任一真值函数 命题公式 都可以用仅 含某一联结词集合的联结词的命题公式表示 则称 该联结词集为全功能集全功能集 功能完备集 若一个联 结词的全功能集不含冗余的联结词 则称它为 功能完备集 若一个联 结词的全功能集不含冗余的联结词 则称它为极小 的全功能集 极小 的全功能集 极小的功能完备集 因此 极小的功能完备集 因此 是极小的全功能集 可以证明 是极小的全功能集 可以证明 也是极小的全功能集 也是极小的全功能集 例例1 12和例和例1 13请大家自学 请大家自学 1 4 1 4 1 4 1 4 联结词全功能集联结词全功能集联结词全功能集联结词全功能集 2006 3 1电子工程学院 离散数学13 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 1 5 1 对偶式 定义 对偶式 定义1 18 在仅含在仅含 的命题公式的命题公式A中 将 与 对 换 若 中 将 与 对 换 若A中含中含0或或1 则将 则将0和和1对换 所得到的命题公 式称为 对换 所得到的命题公 式称为A的对偶式 记为的对偶式 记为A 显然 显然 A与与A 互为对偶式 且互为对偶式 且 A A 例例 求求p q p q的对偶式 解 因 的对偶式 解 因p q p q 则 则 p q的对偶式为 的对偶式为 p q 即 即p q 同理 同理 p q的对偶式为的对偶式为p q 2006 3 1电子工程学院 离散数学14 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 定理定理1 2 设设A和和A 互为对偶式 互为对偶式 p1 p2 pn是出现 在 是出现 在A和和A 中的全部命题变项 则 中的全部命题变项 则 1 A p1 p2 pn A p1 p2 pn 2 A p1 p2 pn A p1 p2 pn 证明 由证明 由p q p q p q p q 则 则 A p1 p2 pn A p1 p2 pn 同理 同理 A p1 p2 pn A p1 p2 pn 2006 3 1电子工程学院 离散数学15 例例 设设A p q r 是 是 p q r 证明 证明 A p q r A p q r 证明 因证明 因 A p q r 是 是 p q r 则 则 A p q r 是是p q r 但 但 A p q r 是 是 p q r 故 故 A p q r 是是 p q r 所以 所以 A p q r A p q r 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学16 定理定理1 3 设设p1 p2 pn是出现在是出现在A和和B中的命题 变项 若 中的命题 变项 若A B 则 则A B 对偶原理对偶原理 证明 由 证明 由 A B 则 则 A p1 pn B p1 pn 是永真式 故 是永真式 故 A p1 pn B p1 pn 也是永真式 即 也是永真式 即 A p1 pn B p1 pn 由定理由定理1 2 A p1 p2 pn B p1 p2 pn 即 即 A B 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学17 1 5 2 范式范式 给定一个命题公式 判断它是永真式 永假式 还是可满足式 这类问题称为 给定一个命题公式 判断它是永真式 永假式 还是可满足式 这类问题称为判定问题判定问题 前面学过的判定方法 前面学过的判定方法 真值表法真值表法 等值演算法等值演算法 但 以上方法不适合命题变项的数目较多的情形 必须将 命题公式化为规范的形式 但 以上方法不适合命题变项的数目较多的情形 必须将 命题公式化为规范的形式 主析取范式主析取范式和和主合取范 式 主合取范 式 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学18 定义定义1 19 1 一个命题公式称为 一个命题公式称为析取范式析取范式 当且仅当 它具有形式 当且仅当 它具有形式 A1 A2 An 其中 其中Ai i 1 2 n 由命题变元或其否定所组成的合取式 如 由命题变元或其否定所组成的合取式 如 p p q p q r 为为析取范式析取范式 2 1 一个命题公式称为 一个命题公式称为合取范式合取范式 当且仅当它 具有形式 当且仅当它 具有形式 A1 A2 An 其中 其中Ai i 1 2 n 由命题变元或其否定所组成的析取式 如 由命题变元或其否定所组成的析取式 如 p p q p q r 为为合取范式合取范式 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学19 定理定理1 4 范式存在定理 任一命题公式都存在与它等 值的析取范式或合取范式 范式存在定理 任一命题公式都存在与它等 值的析取范式或合取范式 消去除消去除 外冗余的联结词 因 外冗余的联结词 因 是全功能集 若命题公式中含其它联结 词 可用如下基本等值式及置换规则将它们消去 是全功能集 若命题公式中含其它联结 词 可用如下基本等值式及置换规则将它们消去 p q p qp q p q p q p q q p p q p q p q p q p q p q p q p q 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学20 否定号的消去或内移 用 否定号的消去或内移 用 p p p q p q p q p q 利用分配率 利用分配率 求求析取范式析取范式 使用 使用 对对 的分配律 的分配律 求求合取范式合取范式 使用 使用 对对 的分配律 的分配律 注意 析取范式和合取范式存在 但不是唯一的 注意 析取范式和合取范式存在 但不是唯一的 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学21 例例1 14 求命题公式 求命题公式 p q r p的合取范式和析 取范式 解 的合取范式和析 取范式 解 1 求 求合取范式合取范式 p q r p p q r p 消去第一个 消去第一个 p q r p 消去第二个 消去第二个 p q r p 消去 消去 p q p r p 对 的分配律 对 的分配律 p q r p 显然 合取范式不唯一 以上两式都是显然 合取范式不唯一 以上两式都是合取范式合取范式 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学22 2 求 求析取范式析取范式 p q r p p q r p 前面的结论 前面的结论 p r q r p 对 的分配律 对 的分配律 p q r 利用交换律和吸收律 显然 以上两式均为 利用交换律和吸收律 显然 以上两式均为析取范式析取范式 由于命题公式的合取范式和析取范式不唯一 因此 不能作为命题公式的标准形式 因此必须引入 由于命题公式的合取范式和析取范式不唯一 因此 不能作为命题公式的标准形式 因此必须引入主合取范 式 主合取范 式和和主析取范式主析取范式的概念 讨论标准型 的概念 讨论标准型 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学23 定义定义1 5 4 在含在含n个命题变项的简单合取式中 若每 个命题变项与其否定不同时存在 但 个命题变项的简单合取式中 若每 个命题变项与其否定不同时存在 但Pi与 与 Pi必须出 现且仅出现一次 且 必须出 现且仅出现一次 且Pi与 与 Pi出现在从左起的第出现在从左起的第i 位 上 若命题变项无角标 则按字典顺序 这样的 简单合取式称为极小项 位 上 若命题变项无角标 则按字典顺序 这样的 简单合取式称为极小项 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学24 P q r p q r p q r p q r p q r p q r p q r p q r 极小项极小项 m77111 m66011 m55101 m44001 m33110 m22010 m11100 m00000 记号十进制数记号十进制数rqp 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 3个命题变项例个命题变项例 2006 3 1电子工程学院 离散数学25 一般地 一般地 n个命题变项共产生个命题变项共产生2n个极小项 个极小项 m0 m1 m2n 1 1 5 3 主析取范式 定义 主析取范式 定义1 21 在含在含n个命题变项的命题公式个命题变项的命题公式A中 若中 若A的析 取范式中的简单合取式全部是极小项 则称该析取范 式为主析取范式 的析 取范式中的简单合取式全部是极小项 则称该析取范 式为主析取范式 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学26 例例1 15 前面例前面例1 14的析取范式的析取范式 p q r p 1 1 1 q r p q q r r 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 p q r p q r m2 m4 m5 m6 m7 2 4 5 6 7 显然 上式是标准的显然 上式是标准的主析取范式主析取范式 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学27 定理定理1 5 任何命题公式的为主析取范式都是存在的 并 且唯一 求给定命题公式 任何命题公式的为主析取范式都是存在的 并 且唯一 求给定命题公式A的主析取范式的步骤如下 的主析取范式的步骤如下 求求A的析取范式的析取范式A 若若A 的某简单合取式的某简单合取式B中不含命题变项中不含命题变项pi或 或 pi 则将 则将 B展成 展成 B B 1 B pi pi B pi B pi 将重复出现的命题变项 永假式及重复出现的极小项将重复出现的命题变项 永假式及重复出现的极小项 消去消去 将极小项按由小到大的顺序排列 并用将极小项按由小到大的顺序排列 并用 表示 表示 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学28 例例1 16 求求p q r的主析取范式 解法 的主析取范式 解法1 p q r p q r p q 1 1 1 r p q r r p p q q r p q r p q r p q r p q r p q r p q r m1 m3 m5 m6 m7 1 3 5 6 7 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学29 也可利用真值表 法求命题公式的主 析取范式 也可利用真值表 法求命题公式的主 析取范式 例例1 16 求上例求上例p q r的主析取范式 解法 的主析取范式 解法2 真值表见右 图 显然 真值表见右 图 显然 主析取范式 为 主析取范式 为 1 3 5 6 7 与解法与解法1的结果完全 一致 的结果完全 一致 1 1 0 0 0 0 0 0 p q 1111 1011 1101 0001 1110 0010 1100 0000 p q rrqp 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学30 总结 主析取范式有以下用途 总结 主析取范式有以下用途 判断两个命题公式是否等值 判断两个命题公式是否等值 判断命题公式的类型 判断命题公式的类型 1 5 1 5 1 5 1 5 对偶与范式对偶与范式对偶与范式对偶与范式 2006 3 1电子工程学院 离散数学31 解 原式 解 原式 p q r p p q r p p q r p p r q r p p 1 r 1 q r p 1 1 p q q r p p q r p q q r r p q r p q r p q r p q r p q r p q r p q r