第1章 命题逻辑_20

第,1,章 命题逻辑,1.5,范式,1.5.1,析取范式,与,合取范式,定义,1.5.1,由一些命题变元或其否定构成的析取式称为,基本和,，也叫,简单析取式,。约定,单个变元或其否定是基本和,。,例如，,p,q,、,p,q,、,p,q,、,q,、,p,、,q,都是基本和。,定义,1.5.2,由一些命题变元或其否定构成的合取式称为,基本积,，也叫,简单合取式,。约定,单个变元或其否定是基本积,。,例如，,p,q,、,p,q,、,p,q,、,p,、,q,、,p,都是基本积。,定义,1.5.3,由基本和的合取构成的公式叫做,合取范式,。约定,单个基本和是合取范式,。,定义,1.5.4,由基本积的析取构成的公式叫做,析取范式,。约定,单个基本积是析取范式,。,1),基本和和基本积,既是析取范式，又是合取范式,。,2),析取范式和合取范式都仅含联结词,。,利用双重否定律消去否定联结词,“,”,或利用德摩根律将否定联结词,“,”,移到各命题变元前,(,内,移,),。,利用分配律，结合律将公式归约为合取范式和析取范式。,任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下：,消去联结词“”和“”,【,例,1.21】,求命题公式,(p,q)p,的合取范式和析取范式。,解：求合取范式,(,p,q,),p,(,p,q,),p,)(,p,(,p,q,)(,消去,),(,p,q,),p,)(,p,(,p,q,)(,消去,),(,p,q,),p,)(,p,(,p,q,)(,内移,),(,p,p,)(,q,p,)(,p,p,q,)(,分配律,),1(,q,p,)(1,q,)(,排中律,),1(,q,p,)1 (,零律,),(,q,p,)(,同一律，合取范式,),合取范式,求析取范式,(,p,q,),p,(,p,q,),p,)(,p,q,),p,)(,消去,),(,p,q,),p,)(,p,q,),p,)(,内移,),p,(,p,q,p,)(,吸收律,),p,(,p,p,q,)(,交换律,),p,(,p,q,)(,幂等律，析取范式,),由此例可以看出，命题公式的析取范式也不惟一。,析取范式,析取范式,A,B,(,A,B,),(,A,B,),1.5.2,主析取范式,由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是,惟一,的。,析取范式和合取范式的基本成分是基本积和基本和，而主析取范式和主合取范式的基本成分是,极小项,和,极大项,，它们分别是,特殊的基本积和基本和,。,p,，,q,的极小项为：,p,q,，,p,q,，,p,q,，,p,q,定义,1.5.5,在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做,布尔合取,也叫,小项,或,极小项,。,表,1.12,是两个变元,p,和,q,的极小项的真值表。极小项有下列的性质：,两个命题变元的极小项共,4(=2,2,),个,三个命题变元的极小项共,8(=2,3,),个,。一般地说，,n,个命题变元共有,2,n,个极小项。,表,1.12,p,q,p,q,p,q,p,q,p,q,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,1,1,1,0,0,0,表,1.13,极小项,成真赋值,名称,p,q,00,m,0,p,q,01,m,1,p,q,10,m,2,p,q,11,m,3,每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。,极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为,m,的下标来表示该极小项，叫做该,极小项的名称,。,两个命题变元的极小项、成真赋值和名,称如表,1.13,所示。,三个命题变元的极小项，成真赋值和名称如,表,1.14,所示。,表,1.14,极小项,成真赋值,名称,p,q,r,000,m,0,p,q,r,001,m,1,p,q,r,010,m,2,p,q,r,011,m,3,p,q,r,100,m,4,p,q,r,101,m,5,p,q,r,110,m,6,p,q,r,111,m,7,从表,1.13,和表,1.14,中可以看出，极小项与其成真赋值的对应关系为：变元对应,1,，而变元的否定对应,0,。,任意两个不同的极小项的合取式为永假式。,例如：,m,001,m,100,(,p,q,r,)(,p,q,r,),p,q,r,p,q,r,0,定义,1.5.6,对于给定的命题公式，如果有一个它的等价公式，仅由极小项的析取组成，称该公式为原公式的,主析取范式,。,m,0,m,1,1,任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：,等价演算法：即用基本等价公式推出。,全体极小项的析取式为永真式。记为：,用等价演算法求主析取范式的步骤如下：,例,1.22,用等价演算法求,(,p,q,)(,p,r,)(,q,r,),的主析取范式。,解：,(,p,q,)(,p,r,)(,q,r,),(,p,q,(,r,r,)(,p,r,(,q,q,)(,q,r,(,p,p,),(,p,q,r,)(,p,q,r,)(,p,q,r,)(,p,q,r,),(,p,q,r,)(,p,q,r,),(,p,q,r,)(,p,q,r,)(,p,q,r,)(,p,q,r,),m,111,m,110,m,011,m,001,m,7,m,6,m,3,m,1,1,，,3,，,6,，,7,在基本积中补入没有出现的命题变元，即添加,(,x,x,),，再用分配律展开，最后合并相同的极小项。,化归为析取范式。,除去析取范式中所有永假的基本积。,在基本积中，将重复出现的合取项和相同变元合并。,真值表法：即用真值表求主析取范式。,用真值表求主析取范式的步骤如下：,构造命题公式的真值表。,找出,公式的成真赋值对应的极小项。,这些极小项的析取就是此公式的主析取范式。,表,1.15,p,q,r,p,q,(,p,q,),r,0,0,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,【,例,1.24】,用真值表法，求,(,p,q,),r,的主析取范式。,解：表,1.15,是,(,p,q,),r,的真值表，公式的成真赋值对应的极小项为：,p,q,r,(,成真赋值为,001),p,q,r,(,成真赋值为,011),p,q,r,(,成真赋值为,100),p,q,r,(,成真赋值为,101),p,q,r,(,成真赋值为,111),(,p,q,),r,的主析取范式为：,(,p,q,r,)(,p,q,r,)(,p,q,r,)(,p,q,r,)(,p,q,r,),m,001,m,011,m,100,m,101,m,111,m,1,m,3,m,4,m,5,m,7,1,，,3,，,4,，,5,，,7,因而主析取范式含,2,n,(,n,为公式中命题变元的个数,),个极小项。,矛盾式无成真赋值，,可满足式的主析取范式中极小项的个数一定小于等于,2,n,。,因而其主析取范式不含任何极小项，将矛盾式的主析取范式记为,0,。,重言式无成假赋值，,矛盾式、重言式、可满足式主析取范式的性质,1.5.3,主合取范式,定义,1.5.7,在基本和中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本和叫作布尔析取，也叫,大项,或,极大项,。,两个变元,p,，,q,构成的极大项为：,p,q,，,p,q,，,p,q,，,p,q,三个命题变元,p,，,q,，,r,构成的极大项为：,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,，,p,q,r,两个命题变元的极大项共,4(=2,2,),个,三个命题变元的极大项共,8(=2,3,),个,。一般地说，,n,个变元共有,2,n,个极大项。,例如，两个变元,p,，,q,的极大项,p,q,，它的成假赋值是,11,，表示为,M,11,，把,11,理解为,2,进制数，它的,10,进制表示为,3,，所以,M,11,又表示为,M,3,。,表,1.16,极大项,成假赋值,名称,p,q,00,M,0,p,q,01,M,1,p,q,10,M,2,p,q,11,M,3,两个命题变元的极大项，成假赋值及名称见表,1.16,，三个命题变元的极大项，成假赋值及名称见表,1.17,。,极大项有下列三个性质：,每个极大项只有一个成假赋值，极大项不同，成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码，并把编码作为,M,的下标来表示该极大项，叫做,极大项的名称,。,从表,1.16,和表,1.17,中可以看出，极大项与成假赋值的对应关系为：变元对应,0,，而变元的否定对应,1,。,表,1.17,极大项,成假赋值,名称,p,q,r,000,M,0,p,q,r,001,M,1,p,q,r,010,M,2,p,q,r,011,M,3,p,q,r,100,M,4,p,q,r,101,M,5,p,q,r,110,M,6,p,q,r,111,M,7,M,0,M,1,0,全体极大项的合取式为永假式。记为：,永真式,任意两个不同的极,大项的析取式为,定义,1.5.8,对于给定的命题公式，如果有一个它的等价公式，仅由极大项的合取组成，则该等价式称为原公式的,主合取范式,。,等价演算法,：即用基本等价公式推出。,其演算步骤如下：,化归为合取范式。,除去所有永真的基本和。,在基本和中合并重复出现的析取项和相同的变元。,在基本和中补入没有出现的命题变元。即增加,(,x,x,),，然后，应用分配律展开公式，最后合并相同的极大项。,任何命题公式都存在着与之等价的主合取范式。主合取范式也可以由以下两种方法求得。,【,例,1.25】,用等价演算法求,(,p,q,),r,的主合取范式。,解：,(,p,q,),r,(,p,q,),r,(,p,q,),r,(,p,r,),(,q,r,),(,p,r,(,q,q,)(,q,r,(,p,p,),(,p,r,q,)(,p,r,q,)(,p,q,r,)(,p,q,r,),(,p,q,r,)(,p,q,r,)(,p,q,r,),M,000,M,010,M,110,M,0,M,2,M,6,0,，,2,，,6,真值表法,：用真值表求主合取范式。,用真值表求主合取范式的步骤如下：,构造命题公式的真值表。,找出公式的成假赋值对应的极大项。,这些极大项的合取就是此公式的主合取范式。,【,例,1.26】,用真值表法求,(,p,q,),r,的主合取范式。,解：,(,p,q,),r,的真值表是表,1.15,。公式的成假赋值对应的大项为：,p,q,r,(,成假赋值为,000),p,q,r,(,成假赋值为,010),p,q,r,(,成假赋值为,110),主合取范式为：,(,p,q,r,),(,p,q,r,),(,p,q,r,),M,000,M,010,M,110,M,0,M,2,M,6,0,，,2,，,6,矛盾式无成真赋值，因而矛盾式的主合取范式含,2,n,(,n,为公式中命题变元的个数,),个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重言式的主合取范式记为,1,。至于可满足式，它的主合取范式中极大项的个数一定小于,2,n,。,在例,1.23,和例,1.24,中求出,(,p,q,),r,的主析取范式为：,m,7,m,5,m,4,m,3,m,1,1,，,3,，,4,，,5,，,7,在例,1.25,和例,1.26,中求出该公式的主合取范式为：,M,0,M,2,M,6,0,，,2,，,6,比较这两个结果，得出以下的结论,:,同一公式的主析取范式中,m,的下标和主合取范式中,M,的下标是互补的。因此，知道了主析,(,合,),取范式就可以写出主合,(,析,),取范式。,