命题逻辑等值演算.ppt

1 1 3命题逻辑等值演算 p q是命题变项 p q与 p q在4个赋值00 01 10 11下均有相同的真值 即 p q p q 的取值都为1 重言式 永真式 给定n个命题变项 按合式公式的规则可以形成无数个命题公式 n个命题变项共2n个赋值 每个赋值时命题公式的值为0或1 因此n个命题变项共生成22n个真值不同的命题公式 如n 2 共16个真值不同的命题公式 如何判断那些命题公式具有相同的真值 2 等值式 定义若等价式A B是重言式 则称A与B等值 记作A B 并称A B是等值式说明 定义中 A B 均为元语言符号 A或B中可能有哑元出现 例如 在 p q p q r r 中 r为左边公式的哑元 用真值表可验证两个公式是否等值请验证 p q r p q rp q r p q r 3 基本等值式 双重否定律 A A等幂律 A A A A A A交换律 A B B A A B B A结合律 A B C A B C A B C A B C 分配律 A B C A B A C A B C A B A C 注意 A B C代表任意的命题公式 4 基本等值式 续 德 摩根律 A B A B A B A B吸收律 A A B A A A B A零律 A 1 1 A 0 0同一律 A 0 A A 1 A排中律 A A 1矛盾律 A A 0 注意 A B C代表任意的命题公式 5 基本等值式 续 蕴涵等值式 A B A B等价等值式 A B A B B A 假言易位 A B B A等价否定等值式 A B A B归谬论 A B A B A注意 A B C代表任意的命题公式牢记这些等值式是继续学习的基础 6 等值演算与置换规则 等值演算 由已知的等值式推演出新的等值式的过程置换规则 若A B 则 B A 等值演算的基础 1 等值关系的性质 自反 对称 传递 2 基本的等值式 3 置换规则 7 应用举例 证明两个公式等值 例1证明p q r p q r证p q r p q r 蕴涵等值式 置换规则 p q r 结合律 置换规则 p q r 德摩根律 置换规则 p q r 蕴涵等值式 置换规则 说明 也可以从右边开始演算 请做一遍 因为每一步都用置换规则 故可不写出熟练后 基本等值式也可以不写出 8 应用举例 证明两个公式不等值 例2证明 p q r p q r用等值演算不能直接证明两个公式不等值 证明两个公式不等值的基本思想是找到一个赋值使一个成真 另一个成假 方法一真值表法 自己证 方法二观察赋值法 容易看出000 010等是左边的成真赋值 是右边的成假赋值 方法三用等值演算先化简两个公式 再观察 9 应用举例 判断公式类型 例3用等值演算法判断下列公式的类型 1 q p q 解q p q q p q 蕴涵等值式 q p q 德摩根律 p q q 交换律 结合律 p 0 矛盾律 0 零律 由最后一步可知 该式为矛盾式 10 例3 续 2 p q q p 解 p q q p p q q p 蕴涵等值式 p q p q 交换律 1由最后一步可知 该式为重言式 问 最后一步为什么等值于1 11 例3 续 3 p q p q r 解 p q p q r p q q r 分配律 p 1 r 排中律 p r 同一律 这不是矛盾式 也不是重言式 而是非重言式的可满足式 如101是它的成真赋值 000是它的成假赋值 总结 A为矛盾式当且仅当A 0A为重言式当且仅当A 1说明 演算步骤不惟一 应尽量使演算短些 12 1 4联结词全功能集 复合联结词排斥或与非式或非式真值函数联结词全功能集 13 复合联结词 排斥或 异或 p q之中恰好有一个成立 p q p q p q 与非式 p与q的否定 p q p q 或非式 p或q的否定 p q p q 问题 多少个联结词最合适 14 真值函数 问题 含n个命题变项的所有公式共产生多少个互不相同的真值表 答案为个 为什么 定义称定义域为 00 0 00 1 11 1 值域为 0 1 的函数是n元真值函数 定义域中的元素是长为n的0 1串 常用F 0 1 n 0 1 表示F是n元真值函数 共有个n元真值函数 例如F 0 1 2 0 1 且F 00 F 01 F 11 0 F 10 1 则F为一个确定的2元真值函数 15 命题公式与真值函数 对于任何一个含n个命题变项的命题公式A 都存在惟一的一个n元真值函数F为A的真值表 等值的公式对应的真值函数相同 下表给出所有2元真值函数对应的真值表 每一个含2个命题变项的公式的真值表都可以在下表中找到 例如 p q p q p q p q q 等都对应表中的 16 2元真值函数对应的真值表 17 联结词的全功能集 定义在一个联结词的集合中 如果一个联结词可由集合中的其他联结词定义 则称此联结词为冗余的联结词 否则称为独立的联结词 例如 在联结词集 中 由于p q p q 所以 为冗余的联结词 类似地 也是冗余的联结词 又在 中 由于p q p q 所以 是冗余的联结词 但 无冗余的联结词 类似地 也是冗余的联结词 但 无冗余的联结词 18 联结词的全功能集 续 定义设S是一个联结词集合 如果任何n n 1 元真值函数都可以由仅含S中的联结词构成的公式表示 则称S是联结词全功能集 如果联结词全功能集不含冗余的联结词 则称为极小功能集 说明 若S是联结词全功能集 则任何命题公式都可用S中的联结词表示 若S1 S2是两个联结词集合 且S1 S2 若S1是全功能集 则S2也是全功能集 19 联结词的全功能集实例 1 S1 2 S2 3 S3 4 S4 5 S5 6 S6 7 S7 而 等则不是联结词全功能集 20 例如已知 是全功能集 证明 也是全功能集证 因为 是全功能集 任意一个真值函数可以用 联结词的命题公式表示 对于任意的命题公式 A B A B 因此任意一个真值函数可以用 联结词的命题公式表示 例 p p p p p p p p p pp p p p p p p p p p p p p p p p