FDM-W.01-L.07 命题逻辑等值式.pdf

计计计计算算算算机机机机科科科科学学学学MMO OO OC C课课课课程程程程群群群群 离离散散数数学学基基础础 定义 命题逻辑等值式 给定两个命题公式 A B 设 p1 p2 pn 为所有出现于 A B 中的命题变量 若对 p1 p2 pn 中的任何一组逻辑解释 A 和 B 的真值都相同 则称 A B 是等值的或逻辑相等的 记为 A B p1 p2 pn 的所有逻辑解释总数为 2n 个 定义 命题逻辑等值式 若两个命题公式 A B 在任意的真值赋值函数 t Var 0 1 下取得相同的真 值 则称 A B 是等值的 或逻辑相等的 记为 A B 上述定义是前一个定义的等价定义 利用了之前定义复合语句的真值时引用的真值 赋值函数 t 我们马上意识到 使用真值表可以判断两个逻辑公式的等值性 定义 命题逻辑等值式 例 证明 p q p q pq p p q p q 0011 1 0111 1 1000 0 1101 1 在每个解释下 p q 和 p q 取相同的真值 所以是一对等值式 等值的基本性质 对公式 A B C 按照等值的定义显然有 A A 自反性 若 A B 则 B A 对称性 若 A B 且 B C 则 A C 传递性 具有自反性 对称性和传递性的关系称为等价关系 所以命题逻辑公式的等值 性通常也称为等价性 定理 等值定理 设命题公式 A B 则 A B iff A B 是重言式 证 若 A B 则 A 与 B 在任意解释下都有相同的真值 由 的定义 A B 只能取值1 即 A B 是重言式 若 A B 只取值1 由 的真值表 A 与 B 在任意解释下都有相同的真值 由 的 定义 有 A B 定理给出验证两个命题公式相等的一种基本方法 命题逻辑的等值演算 当命题公式所含的命题变量个数较多时 使用真值表方法判断公式的等价性有 困难 等值演算以一些基本的等值式 也称为命题定律 为基础 利用等值演算规则 对公式进行变形 从而保持变形前后公式的等价性 等值演算给出了验证两个 命题公式相等的另外一种基本方法 定理 基本的等价公式 命题定律16条 设有命题公式 A B C 则下述等值性成立 1 双重否定律 A A 2 幂等律 A A A A A A 3 交换律 A B B A A B B A 4 结合律 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 A B A A A B A 7 德 摩根律 A B A B A B A B 8 零律 A 1 1 A 0 0 9 同一律 A 0 A A 1 A 10 矛盾律 A A 0 11 排中律 A A 1 12 蕴涵等值式 A B A B 联结词化归 13 等价等值式 A B A B B A 14 假言易位 A B B A 15 等价否定 A B A B 16 归谬 A B A B A 证明 利用等值定理和真值表容易得到证明 语义支持 上述定律大部分可以直接获得自然语言的语义支持 其他常用的等值公式 A B C B A C A B C A B C A A 1 A A A 1 A A 0 A 1 A 1 1 A 0 A A A 1 A A 0 1 A A 0 A A 定义 联接词 功能 完备集 设有联结词集合 C 若只使用 C 中的联接词 就可以等价表出 wff 的所有公 式 则称 C 是一个联接词 功能 完备集 一个具有最少元素个数的联结词 完备集称为是一个最小完备集 例1 是联接词完备集 证 合式公式本来就是由这五个联结词定义的 例2 都是联接词完备集 和 是两个最小 完备集 证 1 由基本等值式 13 等价等值式 A B A B B A 知道 联结词 可以由联 结词集合 表出 所以 是一个联接词完备集 2 由基本等值式 12 蕴涵等值式 A B A B 知道 联结词 可以由联结词集合 表出 所以 是一个联接词完备集 3 由基本等值式 7 德 摩根律 A B A B 结合双重否定律得到 A B A B 联结词 可以由联结词集合 表出 所以 是一个联接词完备集 4 由基本等值式 7 德 摩根律 A B A B 结合双重否定律得到 A B A B 联结词 可以由联结词集合 表出 所以 是一个联接词完备集 其它联接词 异或 定义 设 p q 为命题 则 p q 也是一个命题 称为 p 和 q 的异或 其逻 辑意义为 p qp q FF F FT T TF T TT F 从真值表看出 当且仅当P Q只有一个为T时 P Q 为T 与之前讨论的 排斥性选择 语义对应 其它联接词 异或 例 计算下列真值表 可知 p q p q p q p q p q p q p q p q p q p q 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 其它联接词 与非 定义 设 p q 为命题 则 p q 也是一个命题 称为p 和 q 的与非 其逻 辑意义与 p q 等价 p qp q FF T FTT TF T TTF 其它联接词 或非 定义 设 p q 为命题 则 p q 也是一个命题 称为p 和 q 的或非 其逻 辑意义与 p q 等价 p qp q FF T FTF TF F TTF 现在我们的联结词集合里面有了8个联结词 最小联 结词完备集是 和 例 证明 是一个联结词完备集