命题逻辑公式的范式和主范式.pdf

计计计计算算算算机机机机科科科科学学学学MMO OO OC C课课课课程程程程群群群群 离离散散数数学学基基础础 本本单单元元内内容容比比较较多多 视视频频分分割割成成三三个个部部分分 范范式式的的概概念念 主主范范式式及及其其应应 用用和和主主范范式式的的编编码码 PART 1 范式的概念 范式的概念 范式的一些基本定义 文字 原子命题及其否定式统称为文字 形 例 对变量表 p q p p q q 都是文字 例 把 F 称为空文字 记作 NIL 基本积 由有限个文字的合取构成 简单合取式 例 对变量表 p q r 基本积有 p p q p q p r 等等 基本和 由有限个文字的析取构成 简单析取式 例 对变量表 p q r 基本和有 p p q p q p r 等等 定理6 一个基本和是永真的当且仅当其中含有某个原子的互补对 由排中律和零律 p p 1 1 一个基本积是矛盾的当且仅当其中含有某个原子的互补对 由矛盾律和零律 p p 0 0 定义 析取范式 一个命题公式称为是一个析取范式当且仅当其具有形式 A1 A2 An 1 n 其中 Ai 是基本积 1 i n 例1 p q r s n 3 例2 p n 1 例3 p q r n 1 例4 p q r n 3 定义 合取范式 一个命题公式称为是一个合取范式当且仅当其具有形式 A1 A2 An 1 n 其中 Ai 是基本和 1 i n 例1 p q s p r s n 2 例2 p n 1 例3 p q r n 3 例4 p q r n 1 定理7 1 一个合取范式是永真的当且仅当其中含有的基本和都是永真的 2 一个析取范式是矛盾的当且仅当其中含有的基本积都是矛盾的 证明 留作思考 定理8 范式存在基本定理 任一命题公式都有与之等值的析取范式和合取范式 构造性证明 以求合取范式为例 重复施行如下的等值变形 联结词化归 应用联结词消去等值式 消去 和 否定词深入 应用德 摩根律 使否定词直接作用于原子命题变量 重复利用 和 之间的分配律求得析取范式或合取范式 例 p q r s p q r s 联结词化归 p q r s 德 摩根律 p q r s 德 摩根律 p q s p r s 分配律 p q s p r s p r s 幂等律 讨论 一个命题公式的合取 析取 范式不是唯一的 PART 2 主范式及其应用 主范式及其应用 定义 极小项 设命题公式 A p1 p2 pn 又设 Ak pk pk k 1 n 则称 A1 A2 An 为公 式 A 的一个极小项 极小项也称布尔积 1 关于 A p1 p2 pn 或原子变量集合 p1 p2 pn 的极小项有 2n 个 例 对 p q 可以构造 22 4 个极小项 p q p q p q p q 2 对变量表的任一解释有且仅有一个极小项的值为1 其余的值为0 称该极 小项为该解释所对应的极小项 例 对 p q 的一个解释 t p 1 t q 0 有且仅有 p q 1 对其他的三个 极小项 每个极小项中至少有一个文字的值是0 所以这三个极小项的值都 是0 3 任何一对不同极小项的合取为0 所有极小项的析取为1 由 2 对变量表的任一解释 任何一对极小项中最多有一个极小项取值为 1 另外的取值为0 所以合取为0 所有极小项中恰有一个极小项取值为1 所以析取为1 定义 极大项 设命题公式 A p1 p2 pn 又设 Ak pk pk k 1 n 则称 A1 A2 An 为公 式 A 的一个极大项 极大项也称布尔和 1 关于 A p1 p2 pn 或原子变量集合 p1 p2 pn 的极大项有 2n 个 例 对 p q 可以构造极大项 p q p q p q p q 2 对任一解释有且仅有一个极大项的值为0 其余的值为1 称该极大项为该解 释所对应的极大项 3 任何一对不同极大项的析取为1 所有极大项的合取为0 定义 主析取范式 一个命题公式 B p1 p2 pn 称为是一个主析取范式 形的 当且仅当其具有 形式 B1 B2 Bm 1 m 2n 其中 Bi 1 i m 为公式 B 的一个极小项 且 Bi Bj 对i j 定义 主合取范式 一个命题公式 B p1 p2 pn 称为是一个主合取范式 形的 当且仅当其具有 形式 B1 B2 Bm 1 m 2n 其中 Bi 1 i m 为公式 B 的一个极大项 且 Bi Bj 对i j 定理9 主范式存在和唯一性定理 任一命题公式都有与之等值的主析取范式和主合取范式 考虑到在交换律下等 值的公式形态的同一性 主范式的形态是唯一的 证明 留作思考 例 利用真值表求 p q 的主析取范式 p qp q 0 00 0 11 1 01 1 11 在命题公式 A 的真值表中 令 A 的取值为1的所有解释所对应的极小项的析 取 构成其主析取范式 因此 p q p q p q p q 上述过程的正确性证明 设该析取式为 B 显然 B 为主析取范式的形态 当 A 1 时 其解释对应于一个取值为1的极小项 且该极小项为构成 B 的 极小项之一 故此时B 1 当 A 0 时 其解释所对应的极小项不在构成 B 的极小项中 故此时B中所 有极小项取值0 即B 0 综上可得 B A 即 B 是 A 的主析取范式 范式的应用 例1 一个双稳态 高 低电平 控制线路 有 A B C 三路输入和分别对 应的 FA FB FC 三路输出 要求 输入均为低电平时 没有高电平输出 至 多有一路高电平输出 有高电平输入时 只有按 A B C 的次序检测到的第 一个高电平输入才有效 其对应的输出获得高电平 此时其他输出被抑制 要 求 1 写出分别描述上述三路输出的逻辑表达式 2 用与非门搭建实现上 述控制要求的逻辑电路 ABC FAFBFC 000000 001001 010010 011010 100100 101100 110100 111100 由真值表容易写出 FA FB 和 FC 的主析取范式 FA A B C A B C A B C A B C FB A B C A B C FC A B C 经过化简后的表达式为 FA A A A A A FB A B A A B A A B A A B FC A B C A A B B C 范式的应用 例2 一个会议室有4个门 1盏灯 每个门旁边各有一个双稳态开关 要求 任何一个开关状态的改变都能导致灯的亮 灭状态的改变 写出实现上述控制 要求的逻辑表达式 解 设初始灯是开路的 而且所有开关处于0状态 则只要令灯在有奇数个开 关处于1状态时接通 即满足题目的要求 真值表如下页 A B C D 分别 表示4个开关的状态 一共有 24 16 个逻辑解释 由真值表可以写出 L 的主 析取范式 请你自行完成 A BC DL 00000 00011 00101 00110 01001 01010 01100 01111 A BC DL 10001 10010 10100 10111 11000 11011 11101 11110 等值演算构造主析取范式 1 构造析取范式并化简合并 2 在每一个基本积中利用同一律填满所有的原子命题文字形式 利用分配律 构造布尔积 称为基本积的扩展 3 重复第2步直到所有基本积都扩展成布尔积 4 合并同类布尔积 经适当排列得到最后结果 例 第2步对于 A p q r 扩展基本积 p q p q r r p q r p q r p p q q r r p q p q r r p q r r p q r 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 PART 3 主范式的编码 主范式的编码 定义 极小项的成真编码 对关于 n 个原子的极小项 Bi A1 A2 An 1 i 2n Ak pk pk k 1 n 令 Bi 为真的原子的真值序列 v1v2 vn 是唯一的 称之为 Bi 的成真编码 以 二进制数1表示真值T 0表示真值F 则可构造 Bi 的成真 n 位二进制编码 C 记为 mC 例 命题公式 A p q 有4个极小项 p q 对应 m00 或 m0 当 t p 0 t q 0 时 p q 1 p q 对应 m01 或 m1 当 t p 0 t q 1 时 p q 1 p q 对应 m10 或 m2 当 t p 1 t q 0 时 p q 1 p q 对应 m11 或 m3 当 t p 1 t q 1 时 p q 1 定义 极大项的成假编码 对关于 n 个原子的极大项 Bi A1 A2 An 1 i 2n Ak pk pk k 1 n 令 Bi 为假的原子的真值序列 v1v2 vn 是唯一的 称之为 Bi 的成假编码 以 二进制数1表示真值T 0表示真值F 则可构造 Bi 的成假 n 位二进制编码 C 记为 MC 例 命题公式 A p q 有4个极大项 p q 对应 M11 或 M3 当 t p 1 t q 1 时 p q 0 p q 对应 M10 或 M2 当 t p 1 t q 0 时 p q 0 p q 对应 M01 或 M1 当 t p 0 t q 1 时 p q 0 p q 对应 M00 或 M0 当 t p 0 t q 0 时 p q 0 定理10 mi 和 Mi 如上所述 则 mi Mi Mi mi 证明 设 mi A1 A2 An Ak pk pk k 1 n 则有令 mi 1 的真值序列 i v1v2 vn 在 t pk vk 1 k n 的赋值下 A1 A2 An 1 故 Ak 1 或 Ak 0 1 k n 构造公式 mi A1 A2 An A1 A2 An 0 上述公式化去可能出现的双重否定后 是一个极大项 且在真值序列 i v1v2 vn t pk vk 1 k n 的赋值下成假 依定义记为 Mi 即 mi Mi 易 证 Mi mi 定理11 命题公式 A p1 p2 pn 若有主析取范式 A mi1 mi2 mik 1 k 2n is it 当 1 s t k is it 1 2 2n 则有主合取范式 A Mj1 Mj2 MjL L 2n k js jt 当 1 s t L js jt 1 2 2n i1 i2 ik 证明 公式 A 的主析取范式 A mi1 mi2 mik 可由A 的真值表写出 则由 A 的真值表可写出 A 的主析取范式 A mj1 mj2 mjL L 2n k js jt 当 1 s t L js jt 1 2 2n i1 i2 ik 故 A mj1 mj2 mjL 由定理10有 mjs Mjs 故 A Mj1 Mj2 MjL 例 A P Q R 的真值表 P Q R Q P Q P Q R 0 0 011 0