《第三讲 等价公式.doc》由会员分享，可在线阅读，更多相关《第三讲 等价公式.doc（3页珍藏版）》请在金锄头文库上搜索。
1、第三讲 等价公式等价公式定义： 对于两个给定的命题公式A和B，其中共有n个命题变项（命题变项的概念在上一讲提及），如果对于所有2n个赋值（每个命题变项的取值有T或F两种选择，由乘法定理易得2n），A、B两公式的真值都相同，那么两公式等价。 比如公式 r (q p) 和公式 ( r q) p 的真值表如下（1表示T，0表示F）Pqr r (q p)( r q) p1111111000101111001101111010110011100011由上表可以看到两公式对于三个命题变项的8中赋值都有相同的真值，所以两公式等价。两公式等价记作 AB （ 表示是等价符号）根据真值表，可以形象地给出重言式，矛
2、盾式，可满足式的定义：如果真值表最后一列全是T, 则公式为重言式。也叫永真式。如果真值表最后一列全是F，则公式为矛盾式。也叫永假式。如果真值表最后一列至少有一个T，则公式为可满足式。由定义知，重言式必是可满足式。下面给出几组等价公式：双重否定律p p幂等律ppp, ppp结合律(pq)rp(qp)(pq)rp(qp) 交换律pqqppqqp分配律p(qr) (pq)(pr)p(qr) (pq)(pr)吸收律p(pq) pp(pq) p德摩根律(pq) pq(pq) pq同一律pFp, pTp零律pTT, pFF排中律ppT矛盾律ppF蕴涵律p qp q等价律(pq)(pq) (qp)假言易位律
3、pqqp等价否定律pq pq归谬律(pq)(pq) p以上几组等价公式都可以同过真值表来证明。以上公式可以用于化简一个复杂公式来判断该公式是重言式还是矛盾式亦或是可满足式，也可以用来比较两个化简后的公式是否是等价公式等，这些公式非常重要。下面举例来说明这些公式的运用：1、判断公式 （p(pq)）r 是是重言式、矛盾式还是可满足式？（p(pq)）r（p(pq)）r 蕴涵律（p(pq)）r 德摩根律（p(pq)）r 双重否定律（ppq)）r 德摩根律（Fq)）r 矛盾律 Fr 零律 F 零律所以是矛盾式2、判断 (p (p q) 和 p q 是否等价 (p (p q) p (p q) 德摩根律p （p q) 德摩根律p （p q) 双重否定律（p p）（p q）分配律F（p q） 矛盾律 p q 同一律所以，两公式等价
