第一章 命题逻辑(1.7).pptVIP

§1.7.1 对偶 定义1-7.1 在给定的命题公式中，将联结词∨换成∧，将∧换成∨，若有特殊变元F和T亦相互取代，所得公式A* 称为A的对偶式。 §1.7.1 对偶 讨论定义： （１）若命题公式中有联结词?，?，则必须把化成由联结词∧， ∨，?组成的等价的命题公式，然后求它的对偶式； 例：求(P?Q) ∧(P?R)的对偶式 §1.7.1 对偶 （２）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。 例：（Ｐ∧Ｑ）∨Ｒ对偶式写成 （Ｐ∨Ｑ）∧Ｒ，而不能写成Ｐ∨Ｑ∧Ｒ §1.7.1 对偶 定理1-7.1（摩根推广定理） 设Ａ和A*为对偶式，P1,P2．．．Pn 是出现在Ａ和A*中的所有原子命题变元，则： ?Ａ（P1，P2．．．Pn） ? A* （?P1，?P2．．．?Pn）——（1） Ａ（?P1，?P2．．．?Pn） ? ?A*（P1，P2．．．Pn）——（２） §1.7.1 对偶 证明：由摩根定理 　?（Ｐ∨Ｑ）??Ｐ∧?Ｑ—（１） ?（Ｐ∧Ｑ）??Ｐ∨?Ｑ—（２） ∴不难看出：一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。 §1.7.1对偶 例：设Ａ（Ｐ，Ｑ，Ｒ）??Ｐ∧ ? （Ｑ∨Ｒ），验证上述定理： 证明： (１)Ａ（Ｐ，Ｑ，Ｒ）??Ｐ∧ ?Ｑ∧ ?Ｒ 　∴ ?Ａ（Ｐ，Ｑ，Ｒ） ?Ｐ∨Ｑ∨Ｒ A*（Ｐ，Ｑ，Ｒ） ??Ｐ∨ ?Ｑ∨ ?Ｒ A*（?Ｐ，?Ｑ，?Ｒ）?Ｐ∨Ｑ∨Ｒ （２）Ａ（ ?Ｐ，?Ｑ，?Ｒ）?Ｐ∧Ｑ∧Ｒ ? A*（Ｐ，Ｑ，Ｒ）??（ ?Ｐ∨ ?Ｑ∨?Ｒ） ?Ｐ∧Ｑ∧Ｒ 有Ａ（ ?Ｐ， ?Ｑ， ?Ｒ） ? ?A*（Ｐ，Ｑ，Ｒ） §1.7.1 对偶 定理1-7.2 若两个命题公式互为等价，则它们的对偶式也互为等价，亦即若Ａ?Ｂ，则A*?B*成立。 证明：已知：Ａ、Ｂ为任一命题公式，且Ａ?Ｂ，要证明A*?B* 设：P1、P2．．．Pn 是出现在Ａ和Ｂ中的原子命题变元， §1.7.1 对偶 由Ａ?Ｂ， 即Ａ（P1，P2．．．Pn） ?Ｂ（P1，P2．．．Pn） ∴ ?Ａ（P1，P2．．．Pn）? ?Ｂ（P1，P2．．．Pn） 由摩根推广定理 ∴Ａ*（?P1，?P2．．．?Pn）? Ｂ*（?P1，?P2．．．?Pn） §1.7.1 对偶 ∴Ａ*（?P1，?P2．．．?Pn）? Ｂ*（?P1，?P2．．．?Pn）为永真式 ＊前面讲过永真式的代换实例仍为永真式，所以用 ?Pi代换A*和B*中的Pi （1≤i≤n) 则得： Ａ*（ ? ?P1， ? ?P2．．． ? ?Pn）? Ｂ*（ ? ?P1， ? ?P2．．． ? ?Pn） 即为：Ａ*（P1，P2．．．Pn）? Ｂ*（P1，P2．．．Pn） §1.7.1 对偶 例：证明： （１）?（Ｐ∧Ｑ）→（?Ｐ∨（?Ｐ∨ Ｑ）） ?（?Ｐ∨Ｑ） （２）（Ｐ∨Ｑ） ∧ （?Ｐ∧（?Ｐ∧Ｑ）） ?（?Ｐ∧Ｑ） 证明： （１）左边???(Ｐ∧Ｑ）∨（?Ｐ∨（?Ｐ∨ Ｑ）） ? （Ｐ∧Ｑ） ∨ （?Ｐ∨ Ｑ） ? （Ｐ∨?Ｐ∨Ｑ）∧（Ｑ∨ ?Ｐ∨ Ｑ） ? （?Ｐ∨ Ｑ） §1.7.1 对偶 （２）（Ｐ∨Ｑ） ∧ （?Ｐ∧（?Ｐ∧Ｑ）） ?（?Ｐ∧Ｑ） （２）左边 ? （Ｐ∨Ｑ） ∧ （?Ｐ∧Ｑ） ? （Ｐ∧?Ｐ∧Ｑ） ∨ （Ｑ∧?Ｐ∧Ｑ） ? （?Ｐ∧Ｑ） 结论：（１）和（２）是互为对偶的。 §1.7.2范式 如何判定命题公式为永真式、永假式和可满足式或二个命题公式等价，归纳有三种方法： （1）真值表法：对于变元的所有真值指派，看对应命题公式的真值。 （2）命题演算方法：化简命题公式至最简式，看是否存在和 （Ｐ∨?Ｐ）、（Ｐ∧?Ｐ）等价，若不则为可满足的。 （3）范式方法：本节就介绍此法。 §1.7.2范式 什么叫范式 把命题公式化归为一种标准的形式，称此标准形式为范式。 什么叫判定 以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。 讨论范式和主范式的目的就是为了进