命题公式的范式.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 命题与逻辑,1.5,命题公式的范式,在命题逻辑中，判断两个命题公式是否等价是非常重要的事。以前我们多次提到，每一个命题公式都有无穷多个命题公式与之等价，它们的形式也可能是大相径庭的。本节我们引进命题公式的标准化，即使之等价于标准形式的命题公式，以致两个命题公式等价当且仅当它们的标准形式一样。这样根据命题公式的形式，就可以判断两个命题公式是否等价。这和线性代数中二次型的合同标准形是类似的。,一、合取范式和析取范式,定义,1.5.1,命题变元及其否定称为文字。,定义,1.5.2,有限个文字的合取式称为简单合取式，其中每个文字称为合取项。有限个文字的析取式称为简单析取式，其中每个文字称为析取项。,由定义，文字既是简单合取式，又是简单析取式。,例,1.5.1,都是简单合取式,都是简单析取式。,定理,1.5.1,(1),简单合取式是矛盾式的充要条件是它包含两个分别为某个命题变元及其否定的合取项。,(2),简单析取式是重言式的充要条件是它包含两个分别为某个命题变元及其否定的析取项。,证明,我们只证,(2),(1),的证明是类似的。,充分性 对命题变元,P,P,P,为重言式。所以如果简单析取式中含有,P,P,那么此简单析取式必是重言式。,必要性 假设某简单析取式是重言式，并设其所含的命题变元为,P,1,P,2,P,n,。,如果此简单析取式中不存在两个析取项分别为某个命题变元及其否定，那么它等价于,P,1,*,P,2,*,P,n,*,其中每个,P,i,*,都为文字,P,i,或,P,i,。,显然,有个真值指派使每个,P,i,*,取值都为,0,那么在此真值指派下,此简单析取式取值为,0,矛盾于它是重言式。,定义,1.5.3,有限个简单合取式的析取式称为析取范式。由定义，命题公式,A,为析取范式当且仅当,A,=,A,1,A,2,A,n,(,n,1)，,其中每个,A,i,都为简单合取式。,定义,1.5.4,有限个简单析取式的合取式称为合取范式。由定义，命题公式,A,为合取范式当且仅当,A,=,A,1,A,2,A,n,(,n,1),其中每个,A,i,都为简单析取式。,由定义，下面的结论是显然的,:,(1),简单析取式和简单合取式都既是析取范式，又是合取范式。,(2),析取范式与合取范式都仅含联结词,和。析取范式的对偶式是合取范式，合取范式的对偶式是析取范式。,例1.5.2,为析取范式,为合取范式。,定理,1.5.2,(,范式存在定理,),对任一命题公式，都存在与之等价的析取范式和合取范式。,证明,(,构造性证明,),下面给出求解等价于给定命题公式的范式的步骤：,(1),消除给定命题公式中的联结词和,使之等价于仅含联结词,和的命题公式。利用等价关系和置换规则：,将子公式,A,B,置换成,A,B,。,将子公式,A,B,置换成,(,A,B,),(,A,B,),或,(,A,B,)(,A,B,)。,(2),将联结词,向内深入到命题变元前面。利用等价关系和置换规则：,将子公式,(,A,B,),和(,A,B,),分别置换成,A,B,和,A,B,。,将子公式,A,置换成,A,。,(3）,利用结合律和分配律将命题公式变成所要的范式。,习惯上，我们称与命题公式,A,等价的析取范式,(,或合取范式,)为,A,的析取范式,(,或合取范式,),。显然，,A,的析取范式,(,或合取范式,),不是唯一的。例如,P,P,(,P,P,),和,P,(,Q,Q,),都是,A,的析取范式。,例1.5.3,求命题公式 的析取范式和合取范式。,解,（合取范式）,（析取范式）,（析取范式）,定理,1.5.3,(1),命题公式,A,为矛盾式的充要条件是,A,的析取范式中每个简单合取式包含两个分别为某个命题变元及其否定的合取项。,(2),命题公式,A,为重言式的充要条件是,A,的合取范式中每个简单析取式包含两个分别为某个命题变元及其否定的析取项。,证明,我们只证,(1)，(2),的证明是类似的。,设,A,的任一析取范式为,A,1,A,2,A,n,其中每个,A,i,为简单合取式。,充分性 因为每个,A,i,都包含两个分别为某个命题变元及其否定的合取项，所以由定理,1.5.1,每个,A,i,都为矛盾式，因而,A,为矛盾式。,必要性假设,A,为矛盾式，因为每个,A,i,蕴涵,A,，,所以由定理,1.3.9,每个,A,i,都为矛盾式。再由定理,1.5.1,得证。,例1.5.3,判断下面两个命题公式的类型。,(1),(2),解,(1),上面的合取范式中第一个简单析取式含,P,与,P,，,第二个简单析取式含,R,与,R,。,所以,(1),为重言式。,(2),（析取范式）,（合取范式）,上面的析取范式和合取范式都不满足定理,1.5.3,的条件，因而既不是重言式，又不是矛盾式，它是可满足式。,二、主范式,虽然命题公式的范式为判别其类型带来了一定的方便，但因为其形式的不唯一性，所以我们往往还不能仅从比较两个命题公式,A,和,B,的范式的形式,(,而不是看或的范式的形式,),来判别,A,和,B,的等价或蕴涵关系。为此我们需要引进主范式的概念。,定义,1.5.5,设,P,1,P,2,P,n,为,n,个命题变元,称简单合取式,P,1,*,P,2,*,P,n,*,为由命题变元,P,1,P,2,P,n,所产生的小项,称简单析取式。,P,1,*,P,2,*,P,n,*,为由命题变元,P,1,P,2,P,n,所产生的大项,其中每个,P,i,*,为文字,P,i,或,P,i,。,记小项,P,1,*,P,2,*,P,n,*,为,其中,如果,P,i,*,为文字,P,i,那么,;,如果,P,i,*,为文字,P,i,那么 。记大项,P,1,*,P,2,*,P,n,*,为,其中,如果,P,i,*,为文字,P,i,那么,;,如果,P,i,*,为文字,P,i,那么 。,有时为了方便起见，我们也记 和 分别为,m,k,和,M,k,其中,k,为由二进制数 转化的十进制数。表,1.5.1,和表,1.5.2,列出了,n,=2,时所有小项和大项的真值表。,表1.5.1,表,1.5.2,由表,1.5.1,可以得到小项有如下的性质：,（,1）,n,个命题变元可构成,2,n,个小项。,（,2,）任意两个小项的合取式为矛盾式，所有小项的析取式为重言式。,（,3,）小项 在给每个,P,i,以真值 的这一组真值指派下取值为,1,，在其余,2,n,-,1,组真值指派下取值为,0,。,由表,1.5.2,可以得到大项有如下的性质：,（,1）,n,个命题变元可构成,2,n,个大项。,（,2,）任意两个大项的合取式为矛盾式，所有大项的析取式为重言式。,（,3,）大项 在给每个,P,i,以真值 的这一组真值指派下取值为,0,，在其余,2,n,-,1,组真值指派下取值为,1,。,定义,1.5.6,设,P,1,P,2,P,n,为,n,个命题变元，由此,n,个命题变元所产生的互不相同的小项所构成的析取范式称为由,P,1,P,2,P,n,所产生的主析取范式。由此,n,个命题变元所产生的互不相同的大项所构成的合取范式称为由,P,1,P,2,P,n,所产生的主合取范式。,显然主析取范式不为矛盾式，主合取范式不为重言式。,定理,1.5.4,(,主范式存在定理,),设,A,为命题变元都在集合,P,1,P,2,P,n,中的命题公式。,(1),如果,A,不为矛盾式,那么,A,等价于一个由,P,1,P,2,P,n,所产生的主析取范式,称之为,A,关于,P,1,P,2,P,n,的主析取范式,进一步如果,A,=,A,(,P,1,P,2,P,n,),简称为,A,的主析取范式。,(2),如果,A,不为重言式,那么,A,等价于一个由,P,1,P,2,P,n,所产生的主合取范式,称之为,A,关于,P,1,P,2,P,n,的主合取范式，进一步如果,A,=,A,(,P,1,P,2,P,n,),简称为,A,的主合取范式。,证明,(,构造性证明,),首先由定理,1.5.2,，可以得到,A,的析取范式和合取范式。继续进行构造，便可得到,A,关于,P,1,P,2,P,n,的主析取范式和主合取范式。我们在此仅就,(1),进行构造证明，,(2),的证明是类似的。设,A,*,是,A,的析取范式。,(1),扩展,:,如果,A,*,的某个简单合取式,B,不含命题变元 及其否定,P,i,那么利用置换规则,用,B,P,i,(,B,P,i,),置换,B,。,(2),削去,:,将重复出现的命题变元，矛盾式和重复出现的小项都削去。,(3),排序,:,将小项按下标从小到大的顺序排列。,由小项和大项的性质，容易得到下面用,A,=,A,(,P,1,P,2,P,n,),的真值表来求,A,的主范式的方法,:,(1),A,的主析取范式为所有与,A,在同一组关于,P,1,P,2,P,n,的真值指派下都取值为,1,的由,P,1,P,2,P,n,所产生的小项所构成的析取范式。,(2),A,的主合取范式为所有与,A,在同一组关于,P,1,P,2,P,n,的真值指派下都取值为,0,的由,P,1,P,2,P,n,所产生的大项所构成的合取范式。,例,1.5.3,求命题公式,(,P,Q,),P,的主析取范式和主合取范式,解一,（主析取范式）（主合取范式）,表,1.5.3,解二,因为与,(,P,Q,),P,在同一组真值指派下都取值为,1,的小项只有,m,11,与(,P,Q,),P,在同一组真值指派下都取值为,0,的所有大项是,M,00,M,01,M,10,所以,小项和大项之间有如下的关系，有兴趣的读者可以自己给出其证明：,(1),设,A,=,A,(,P,1,P,2,P,n,),为命题公式，和 为集合,0,1,2,.,2,n,-,1,的两个子集。如果,那么 ,0,1,2,.,2,n,-,1。,定理,1.5.4,(,范式唯一性定理,),设,A,为命题变元都在集合,P,1,P,2,P,n,中的命题公式，如果不计其中小项（或大项）的排列次序，那么,A,关于,P,1,P,2,P,n,的主析取范式（或主合取范式）是唯一的。,证明,(,反证法,),我们只证主析取范式情形。假设,A,有两个不同的关于,P,1,P,2,P,n,的主析取范式,A,1,和,A,2,那么至少有一个小项,如,m,i,只出现在,A,1,和,A,2,之一中,不妨设在,A,1,中。那么在使,m,i,成真的真值指派下,A,1,为真，而,A,2,为假。矛盾于,A,1,等价于,A,2,。,下面两个定理是主范式在证明等价关系与蕴涵关系和判别命题公式类型上的应用，,留给读者给出其证明。,定理,1.5.5,设,A,和,B,为两个命题变元都在集合,P,1,P,2,P,n,中的命题公式，那么,A,B,的充要条件是,A,和,B,有相同的关于,P,1,P,2,P,n,的主析取范式或主合取范式。特别地，,A,为重言式的充要条件是,A,关于,P,1,P,2,P,n,的主析取范式含有所有的,2,n,个小项；,A,为矛盾式的充要条件是,A,关于,P,1,P,2,P,n,的主合取范式含有所有的,2,n,个大项。,定理,1.5.6,设,A,和,B,为两个命题变元都在集合,P,1,P,2,P,n,中的命题公式，,A,和,B,都既不是重言式，也不是矛盾式，那么以下三者等价：,(1),A,B,。,(2),A,关于,P,1,P,2,P,n,的主析取范式中的所有小项都在,B,关于,P,1,P,2,P,n,的主析取范式中。,(3),B,关于,P,1,P,2,P,n,的主合取范式中的所有大项都在,A,关于,P,1,P,2,P,n,的主合取范式中。,