等价式和蕴涵式.pptVIP

§8．2 重言式 等价式和蕴涵式 8．2．1 重言式 矛盾式 从上节例8.5中我们看到，虽然公式一般随所含命题变元的真值变化而变化，但也有公式无论变元真值指派是什么它的真值都是真，也有公式无论变元真值指派是什么它的真值都是假，它们是两类特殊的命题公式即重言式（也叫永真式）和矛盾式（也叫永假式），当然更多的是命题公式的真值随变元真值的不同有真有假，我们称它们为可满足式。 定义8.3 对于命题公式A，如果对A中命题变元的一切指派A的真值都为真，则称命题公式A为重言式（tautology），又称永真式；记作T。 如果对A中命题变元的一切指派A的真值都为假，则称命题公式A为矛盾式（contradication），又称永假式。记作F。 如果对A中命题变元的一切指派A的真值有真有假则称A为可满足式（satisfactable formula）。 那么任何一个公式肯定是永真式、永假式和可满足式三种公式中的一个，判定一个公式是这三类公式中的哪一个往往称为公式的判定问题，目前我们可以借助真值表有效判定。 很显然，而当A是永真式（永假式）时， ?A必为永假式（永真式）。 例8.9 用真值表证明(P∨Q)∧?P→Q为重言式。 证 待证公式的真值表为： 表8.9 由表的最后一列可以看出，原式为重言式。 如果能给一组命题公式中的每一变元一个真值，使各表达式均为真，则这一组命题公式是一致的。在给出系统规范时，必须使这些规范一致。例如：“当且仅当系统正常操作时，系统处于多用户状态。如果系统正常操作，则它的核心程序正在运行。核心程序不能正常运行，或者系统处于中断模式。如果系统不处于多用户状态，它就处于中断模式。系统不处在中断模式”这个系统规范就不一致。 8．2．2 等价式 我们再来观察一下例 8.4公式?P∨Q的真值表,它与公式P→Q的真值表相同，也就是说，公式P→Q与?P∨Q对于P，Q的所有真值指派它们的真值都相同。这时我们称这两个公式等价，即有等价式P→Q??P∨Q。 定义3.3 对于命题公式A，B中所有变元的任何指派，A和B的真值都相同，则称A等价于B，或逻辑相等。记为A ? B，又称它为逻辑等价式(logically equivalent)。 注意： （1）符号“?”与“?”的区别：“?”表示两个公式等价，是关系符，而“?”是逻辑联接词，任何两个公式都可以用它联接成一个新的公式。 （2）“?”与“?”还有密切的联系：易证A?B当且仅当A?B是重言式。 （3）“?”是公式间的一个等价关系，满足自反性、对称性和传递性。 　　首先我们有以下的基本等价式，它们都是以命题定律的形式出现的，故也叫命题定律。其中A，B，C表示任意命题变元： 表8 .10 除以上基本等价式外，还有一些不是运算律的重要等价式，也是在今后常用的。 E20 A→B?┐A∨B E21 A→B?┐B→┐A E22 A? B? (A→B)∧(B→A) E23 A? B? (A∧B)∨(┐A∧┐B) E24 A∧B→C?A→(B→C) 说明： 这些等价式是今后作运算和推理的重要依据，它们就象代数中(a+b)2=a2+2ab+b2, (a+b)3=a3+3a2b+3ab2+b3那么重要。如E21就是我们熟悉的原命题与其逆否命题等价。基本等价式的运算律与集合运算满足的运算律相似，它们的对应是：∧对应∩，∨对应∪，? 对应ˉ（补），T对应E（全集）， F对应?（空集），读者可以对应记忆。 当然它们都可以用真值表来验证。 上面所有等价式中的A，B，C是任意的公式也可以，因为对任意的命题变元成立的等价式与变元取值无关，因此把变元换成任意公式也成立。 如：（?P∨Q）∨?（?P∨Q）?T；　　　 　　（A→B）∧┐（A→B）?F 　　（┐A┐B）→C ??（┐A∧┐B）∨C 因此我们今后要灵活运用这些等价式。 前面已述，我们可以用真值表来判定一个公式是永真式、永假式还是可满足式，也可以用真值表来判断两个公式是否等价。但真值表对公式含有少量变元是可行的，当变元数目增长时，就不可行了。 例如，对于含20个变元的公式，它的真值指派组合有220=1048576组，显然此时需要用一台计算机帮你做这个工作。可当变元有1000个时，一台计算机要检查21000种真值组合的真值在几亿年内都不能完成，而迄今为止尚没有其他已知的计算过程能使计算机在合理可接受的时间内完成，这涉及到算法复杂性问题，也是计算机解决问题最重要最根本的问题。 那么我们还可以用什么方法判定一个公式是哪一种公式，还能用什么方法讨论两个公式等价呢？那就是现在的等价公式。依据等价公式作运算，还有一个重要的置换规则。 定理8.1 置换原理（rule of replacement）设A为一命题