离散数学：r01命题逻辑c

1、1回顾回顾n命题公式及其翻译命题公式及其翻译n重言式重言式n命题公式的等价关系命题公式的等价关系2永真蕴含永真蕴含n当且仅当当且仅当AB是一个重言式时，称为是一个重言式时，称为A永真蕴含永真蕴含(implicate) B，记做，记做AB。n注意注意 和和 的区别和联系。的区别和联系。n证明证明A B的的方法：方法：通过真值表或等价替换证明通过真值表或等价替换证明A B是一个重言式，则是一个重言式，则AB。肯定前件法：假设肯定前件法：假设A为为T，推出，推出B也为也为T，则，则AB；否定后件法：假设否定后件法：假设B为为F，推出，推出A也为也为F，则，则AB。3对于第二、第三种方法，分析过程如下

2、：而要证明对于第二、第三种方法，分析过程如下：而要证明AB，即，即证证AB是一个重言式。对于是一个重言式。对于AB来说，除了来说，除了A的真值为的真值为T，B的真值为的真值为F这样一种指派使得其真值结果为这样一种指派使得其真值结果为F外，其余情况外，其余情况下，下，A B的真值都是的真值都是T。所以要证明。所以要证明AB，只需对，只需对A B的前件的前件A指派为指派为T，如果可以推出，如果可以推出B为为T，则，则AB为重言式，为重言式，即即AB成立，这种方法称为成立，这种方法称为肯定前件法肯定前件法；或者对；或者对AB的后的后件件B指派为指派为F，如果可以推出，如果可以推出A为为F，则，则AB

3、为重言式，即为重言式，即AB成立，这种方法称为成立，这种方法称为否定后件法否定后件法。4例例1 证明证明 Q(PQ)P。证明证明:( 1 )肯定前件法：肯定前件法： 设设Q(PQ )为为T，则，则Q为为T, (PQ )为为T， 所以所以Q为为F，P为为F，于是，于是P为为T，故，故Q(PQ ) P成立。成立。( 2 )否定后件法：否定后件法： 设设P为为F，则，则P为为T，( i ) 当当Q为为F，则，则PQ为为F，所以，所以Q(PQ )为为F；( ii ) 当当Q为为T，则，则Q为为F，所以，所以Q(PQ )为为F。 故故Q(PQ ) P成立。成立。5PQPI1PQQI2PPQI3QPQI4

4、PPQI5QPQI6(PQ)PI7 (PQ)QI8P（PQ）QI9Q（PQ）PI10n常见的永真蕴含式：常见的永真蕴含式：6P（PQ）QI11（PQ）（QR）PRI12（PQ）（PR）（QR）RI13（PQ）（QR）（PR）I14（PQ）（RS）（PR）（QS）I15（PQ）（QR）PRI16PQ（PR）（QR）I17PQ（PR）（QR）I187如同联结词如同联结词和和的关系一样，等价关系和永真蕴含关系之的关系一样，等价关系和永真蕴含关系之间也有紧密的联系。间也有紧密的联系。定理：定理： 设设A和和B是任意两个命题公式，是任意两个命题公式，AB当且仅当当且仅当AB并且并且 BA。证明：证明：

5、如果如果AB，则，则AB为重言式，为重言式， 而而AB（AB）（BA），）， 所以，所以，AB 和和 BA 均为均为T，即，即AB并且并且BA。 如果如果AB并且并且BA，则，则AB为为T，且，且BA为为T， 所以所以A B为为T，即为重言式，故，即为重言式，故AB。该定理可以作为两个命题公式等价的定义该定理可以作为两个命题公式等价的定义。8等价关系和永真蕴含关系的几个等价关系和永真蕴含关系的几个常用性质常用性质： 设设A、B和和C是命题公式，是命题公式，性质性质(a) 如果如果AB并且并且A是重言式，则是重言式，则B也是重言式。也是重言式。证明证明: 因为因为AB永为永为T，所以当，所以当A

6、为为T时，时，B一定永为一定永为T。 性质性质(b) 如果如果AB并且并且BC，则，则AC。即。即等价关系是传递的等价关系是传递的。证明证明: 因为因为AB，所以，所以AB永真，永真， 又因为又因为BC，所以，所以BC永真，永真， 所以（所以（AB）（BC）永真，）永真， 由由I16有（有（AB）（BC）AC， 由性质由性质(a)可得可得AC为永真，所以为永真，所以AC。9性质性质(c) 如果如果AB 并且并且 BC，则，则AC。即。即蕴含关系是传递的蕴含关系是传递的。证明证明: 如果如果AB，BC，则，则AB和和BC是重言式。是重言式。 利用否定后件法，设利用否定后件法，设C为为F，则，则B

7、为为F，进而，进而A为为F，所以，所以AC。性质性质(d) 如果如果 AB 并且并且 AC，则，则ABC。证明证明: 如果如果AB，AC，则，则AB和和AC是重言式。是重言式。 利用肯定前件法，设利用肯定前件法，设A为为T，则，则B、C为为T，所以，所以BC为为T，即即ABC。性质性质(e) 如果如果 AC 并且并且 BC，则，则ABC。证明证明: 如果如果 AC 并且并且 BC，则，则AC并且并且BC为为T。 利用否定后件法，设利用否定后件法，设C为为F，则，则A、B为为F，所以，所以AB为为F，即即ABC。10联结词的扩充联结词的扩充 1. 1. 一元运算一元运算 Pf1 f2 f3 f

8、4010 0 1 10 1 0 1 永假永假 恒等恒等 否定否定 永真永真 1.4 联结词的完备集联结词的完备集112. 2. 二元运算二元运算 条条件件条条件件条条件件条条件件12 除除f5 , f6 , f 7 , f8 , f 13 , f 14 , f 15已定义已定义, f 1 , f10 , f 11 , f 16作为运作为运算意义不大算意义不大, 只需再定义以下只需再定义以下 4 个个: f 12与非：与非： PQ (PQ) f2 或非：或非： PQ (PQ) f9排斥或排斥或(异或异或): P Q (P Q) PQPQ f 3 , f 4条件否定条件否定: P Q (PQ) 1

9、3联结词的归约联结词的归约 9 个联结词是否都必要个联结词是否都必要? 显然不是的显然不是的, 只用只用 , , 三个三个联结词构造的式子联结词构造的式子, 就足以把一切命题公式等价地表示出来。就足以把一切命题公式等价地表示出来。定义：定义：对于一个联结词集合，如果所有的命题公式都能用其中对于一个联结词集合，如果所有的命题公式都能用其中 的联结词等价表示出来，则称其为的联结词等价表示出来，则称其为全功能联结词集合全功能联结词集合， 或称该联结词集合是功能完备的。如或称该联结词集合是功能完备的。如 , , 。根据德根据德摩根定律摩根定律: (PQ) PQ, (PQ) PQ, 所所以以, 和和中去

10、掉一个也足以把一切命题公式等价地表示出来。中去掉一个也足以把一切命题公式等价地表示出来。 14同一命题公式可以有各种各样的相互等价的表达形式，同一命题公式可以有各种各样的相互等价的表达形式，为了将命题公式转化为等价的标准形式，以简化研究工为了将命题公式转化为等价的标准形式，以简化研究工作并方便应用，需要进行命题公式的规范化。下面讨论作并方便应用，需要进行命题公式的规范化。下面讨论与之相关的命题公式的范式问题。与之相关的命题公式的范式问题。 1.5 范式15定义：定义：设有命题公式设有命题公式A, 其中仅有联结词其中仅有联结词, , 。在。在A中将中将 , 分别换以分别换以, ,如果有常元如果有

11、常元 F 和和 T，也互相替，也互相替 换换, 所得公式记为所得公式记为A*，则，则A*称为称为A的的对偶公式对偶公式。显然，显然，(A*)* A，即对偶是相互的。，即对偶是相互的。例例1 (a) PF 的对偶的对偶公式？公式？ (b) PQR的对偶公式？的对偶公式？ 对偶式对偶式注意：不可改变原来运算的顺序。注意：不可改变原来运算的顺序。P(QR) PT16 定理：定理： 设设A和和A*是对偶式。是对偶式。P 1, P2, Pn是出现于是出现于A和和A* 中的所有命题变元中的所有命题变元, 于是于是A(P1, P2, , Pn)A *(P1, P2, Pn)A(P1, P2, Pn) A*(

12、P1, P2, , Pn)如在前例如在前例(b)中中, A(P, Q, R) PQR A(P, Q, R) (PQR) (P)(QR) (P)(QR)A*(P, Q, R) P(QR)A*(P, Q, R)(P)(QR) 所以，所以，A(P, Q, R)A*(P, Q, R)17定理定理：（对偶原理）对偶原理）若若AB, 且且 A , B为命题变元为命题变元P1, P2,., Pn及联结词及联结词 , , 构成的公式构成的公式, 则则A* B*。 定理：定理：若若AB, 且且 A , B为命题变元为命题变元P1, P2, , Pn及联结词及联结词 , , 构成的公式构成的公式, 则则B*A*。

13、18) 1(.21nAAAnRRQRQP)()(定义：定义：一个命题公式称为一个命题公式称为析取范式析取范式（disjunctive normal form），）， 当且仅当它具有如下形式：当且仅当它具有如下形式：其中，其中，A1，A2，An是由是由命题变元命题变元或或其否定其否定所组成的所组成的合取式合取式。例如例如析取范式和合取范式析取范式和合取范式19)1(.21nAAAnRRQRQP)()(定义：定义：一个命题公式称为一个命题公式称为合取范式合取范式（conjunctive normal form），）， 当且仅当它具有如下形式：当且仅当它具有如下形式：其中，其中，A1，A2，An是由是由命题变元命题变元或或其否定其否定所组成的所组成的析取式析取式。例如例如20n任何一个命题公式，都可以求得它的合取范式或者析取范式，任何一个命题公式，都可以求得它的合取范式或者析取范式，步骤如下：步骤如下：将公式中的联结词都归约成将公式中的联结词都归约成、和和。利用德利用德摩根定律将否定符号摩根定律将否定符号直接移到各命题变元之前。直接移到各命题变元之前。利用分配律、结合律将公式归约成合取范式或者析取范式。利用分配律、结合律将公式归约成合取范式或者析取范式。)()()()()()(:1514QPQPQ