2.2析取范式与合取范式

本节给出命题公式的两种规范表示方法,这种规范的表达式能表达真值表所能提供的一切信息

定义2.2命题变项及其否定统称作文宇.仅由有限个文字构成的析取式称作简单析取式仅由有限个文字构成的合取式称作简单合取式

P,┓g;pV┓p,┓pVq和┓pV┓qVr,pV┓pVr都是简单析取式,分别由1个文字,2个文字和3个文字构成

┓p,q;p^p,P^┓q和p∧q^┓r, ┓P^P^q都是简单合取式,分别由1个文字,2个文字和3个文字构成.注意,一个文字既是简单析取式、又是简单合取式

设A是含n个文字的简单析取式,若Ai中既含某个命题变项Pj又含它的否定式┓Pj,由交换律、排中律和零律可知,Ai为重言式.反之,若Ai为重言式,则它必同时含某个命题变项及它的否定式.否则若将A,中的不带否定符的命题变项都取0值,带否定符的命题变项都取1值,此赋值为Ai的成假赋值,这与Ai是重言式相矛盾.类似地,设Ai是含n个命题变项的简单合取式若Ai中既含某个命题变项Pj又含它的否定式┓Pj则Ai,为矛盾式.反之,若Ai为矛盾式,则Ai中必同时含某个命题变项pj及它的否定式.于是,得到下面的定理

定理2.1 (1)简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式

定义2.3由有限个简单合取式的析取构成的命题公式称为析取范式,由有限个简单析取式的合取构成的命题公式称为合取范式,

析取范式与合取范式统称为范式析取范式的一般形式为A1VA2V…VAi,其中A,(i=1,2,…,s)为简单合取式;合取范式的般形式为B1^B2^...^Bj,其中B(j=1,2,…,t)为简单析取式例如,(P^┓q)V(┓q^┓r)Vp为析取范式(pVqVr)^(┓pV┓q)^(┓pV┓rVs)为合取范式.┓P^q^r既是由一个简单合取式构成的析取范式,又是由3个简单析取式构成的合取范式;类似地, pv┓qvr既是由3个简单合取式构成的析取范式,又是由一个简单析取式构成的合取范式。(看定义)

析取范式和合取范式具有下述性质

定理2.2 (1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式

(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式

到现在为止,我们研究的命题公式中含有5个联结词{∧,V,┓,→,},如何把这样的命题公式化成等值的析取范式和合取范式？

首先,可以利用蕴涵等值式与等价等值式

A→B┓AVB |

AB(┓AVB)∧(AV┓B) |(2.17)

消去任何公式中的联结词→和

其次,在范式中不出现如下形式

┓┓A, (┓A^B), ┓(AVB)

对其利用双重否定律和德摩根律,可得

┓┓AA |

┓(A^B)┓AV┓B |

┓(AVB)┓A^┓B |(2.18)

再次,在析取范式中不出现如下形式:

A^(BVC)

在合取范式中不出现如下形式

AV(B^C)

利用分配律,可得

A^(BVC)(A^B)V(A^C)

AV(B^C)(AVB)^(AVC)

上述3步,可将任一公式化成与之等值的析取范式和合取范式.于是,得到下述定理

定理2.3(范式存在定理) 任一命题公式都存在与之等值的析取范式与合取范式

求给定公式范式的步骤

例2.7求下面公式的析取范式与合取范式:

(p->q)r

解为了清晰和无误,利用交换律使每个简单析取式和简单合取式中命题变项都按字典顺出现。

(p->q)r

(┓pVq)r (消去→)

((┓pVq)→r)∧(r→(┓pVq)) (消去)

(┓(┓pVq)Vr)∧(┓rV┓pVq) (消去→)

((P∧┓q)Vr)∧(┓pVqV┓r) (否定符内移)台

(PVr)∧(qVr)∧(┓pVq┓r) (v对∧的分配律)

含3个简单析取式的合取范式

(p-q)r

((p^┓q)Vr)^( ┓pVqV┓r)

(p^┓q^┓p)V(P^┓q^q)V(p^┓q^┓r)

V(r^q)V(r^┓q) (^对V的分配律)

(p^┓q^┓r)V(┓p^r)V(q^r) (矛盾律和同一律)

最后两步的结果都是析取范式,一般地,命题公式的析取范式是不惟一的同样,合取范式也是不惟一的为了使命题公式的范式惟一,进一步将简单合取式和简单析取式规范化,定义如下

定义2.4在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项和它的否定式恰好出现一个且仅出现一次,而且命题变项或它的否定式按下标从小到大或按字典顺序排列,称这样的简单合取式(简单析取式)为极小项(极大项)

由于每个命题变项在极小项中以原形或否定形式出现且仅出现一次,因而n个命题变项共可产生2"个不同的极小项.每个极小项都有且仅有一个成真赋值.若极小项的成真赋值所对应内二进制数等于十进制数i,就将这个极小项记作mi类似地,n个命题变项共可产生2"个不同的极大项,每个极大项只有一个成假赋值,将其对应的十进制数i做极大项的角标,记作Mi 表2.3和表2.4分别列出含p,q与p,q,r的全部极小项和极大项

根据表2.3和表2.4可以直接验证极小项与极大项之间有下述关系

定理2.4设mi与Mi是命题变项含P1,P2,...,P3的极小项和极大项,则

┓mi