2.2 析取范式与合取范式

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 命题逻辑等值运算,第,1,节 等值式,第,2,节 析取范式与合取范式,第,3,节 联结词的完备集,一、简单合取式和简单析取式,二、范式,第,2,节,析取范式与合取范式,三、范式的唯一性,主范式,四、几点注意,每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况。,逻辑公式在等值演算下也有标准形,范式，范式有两种：析取范式和合取范式。,定义,2.2,命题变项,及其否定统称作,文字,.,仅由有限个文字构成的析取式称作,简单析取式,.,仅由有限个文字构成的合取式称作,简单合取式,.,一、简单合取式和简单析取式,如，,p, q,等为一个文字构成简单析取式，,pp,，,pq,等为,2,个文字构成的简单析取式，,pqr, pqr,等为,3,个文字构成的简单析取式,.,一个文字既是简单析取式，又是简单合取式,.,为方便起见，有时用表示,s,个简单,析取式或,s,个简单合取式,.,注意,定理,2.1,（,1,）一个简单析取式是,重言式,当且仅当它同时含,有某个命题变项及它的否定式,;,（,2,）一个简单合取式是,矛盾式,当且仅当它同时含,有某个命题变项及它的否定式。,证明：,设,是含,n,个文字的简单析取式,.,若,中既含有某个命题变项,，又含有它的否定式,，由交换律、排中律和零律可知，,为重言式。,反之，若,为重言式，则它必同时含某个命题变项及它的否定式，否则，若将 中的不带否定号的命题变项都取,0,，带否定号的命题变项都取,1,，此赋值为 的成假赋值，这与 是重言式相矛盾。,类似的讨论可知，若,是含,n,个命题变项的简单合取式，且,为矛盾式，则,中必同时含有某个命题变项及它的否定式，反之亦然,.,如：,pp,，,ppr,都是重言式,.,pq,，,pqr,都不是重言式,.,二、范式,1,、范式的定义,定义,2.3,（,1,）由有限个简单合取式构成的析取式称为,析取范式,.,（,2,）由有限个简单析取式构成的合取式称为,合取范式,.,（,3,）析取范式与合取范式统称为,范式,.,设 为简单的析取式，则,为合取范式,.,设 为简单的合取式，则,为析取范式。,2,、范式的性质,定理,2.2,（,1,）一个析取范式是,矛盾式,当且仅当它的每个简单,合取式都是矛盾式,.,（,2,）一个合取范式是,重言式,当且仅当它的每个简单,析取式都是重言式,.,定理,2.3,（范式存在定理）,任一命题公式都存在着与之等值的析取范式与合取范式。,证明,:,(1),由蕴涵等值式与等价等值式可知,AB,AB,A B (AB)(AB) （2.17）,因而在等值的条件下，可消去任何公式中的联结词,和,(2),用双重否定律和德摩根律，可得,A A,(AB) AB,(AB) AB （2.18）,(3),利用分配律，可得,A(BC) (AB)(AC),A(BC) (AB)(AC) (2.19),由（,2.17,）,（,2.18,）,（,2.19,）,3,步，可将任一公式化成与之等值的析取范式或合取范式,.,3,、求范式的步骤：,(1),消去联结词,、,(2),否定号的消去（利用双重否定律）或内移（利,用德摩根律）。,(3),利用分配律：利用,对,的分配律求析取范式，,利用, 对,的分配律求合取范式。,为了清晰和无误，演算中利用交换律，使得每个简单析取式或合取式中命题变项的出现都是按字典顺序，这对下文中求主范式更为重要,.,注意,例,2.7,求公式,(,pq,) r,的,析取范式,与,合取范式,：,解：,（,1,）先求合取范式,(pq),r,(pr)(qr)(pqr),（对,分配律）,(pq)r)(pqr),（,否定号内移）,(pq)r)(rpq),（,消去,）,(pq)r)(r(pq),（,消去 ）,(pq) r,（,消去,）,（,2,）求析取范式,求析取范式与求合取范式的前两步是相同的，只是在利用分配律时有所不同。因而可以用（,1,）中前四步的结果，接着进行,对,分配律演算。,(pq),r,(pq)r)(pqr),(pqp)(pqq)(pqr),(rp)(rq)(rr),(pqr)(pr)(qr),在以上演算中，从第二步到第三步是利用矛盾律和同一律。另外，第二步和第三步结果都是析取范式，这正说明命题公式的析取范式是不唯一的。同样，合取范式也是不唯一的。,上述范式不唯一，下面追求一种更严格的范式,主范式，它是存在且唯一的。,1,、极小项（极大项）,(1),定义,2.4,在含有,n,个,命题变项,的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第,i,个命题变项或它的否定式出现在从左算起的第,i,位上（若命题变项无角标，就按字典顺序排列），称这样的,简单合取式,（,简单析取式,）为,极小项,（,极大项,）,.,三、范式的唯一性,主范式,(2),由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而,n,个命题变项共可产生,2,n,个不同的极小项,.,(3),每个极小项都有且仅有一个成真赋值,.,若成真赋值所对应的二进制数转换为十进制数,i,，就将所对应极小项记作,.,类似地，,n,个命题变项共可产生,2,n,个极大项，每个极大项只有一个成假赋值，将其对应的十进制数,i,做极大项的角标，记作,.,表,2.3 p, q,形成的极小项与极大项,(4),表,2.4 p, q, r,形成的极小项与极大项,(5),极小项与极大项的关系。,定理,2.4,设 与 是命题变项,形成的极小项和极大项，则,2,、,主范式,(1),定义,2.5,设由,n,个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）为,主析取范式,（,主合取范式,）,.,(2),主范式的存在性和唯一性,定理,2.5,任何命题公式都存在着与之等值的,主析取范式,和,主合取范式,，并且是唯一的,.,证明：,这里只证主析取范式的存在和唯一性,.,首先证明存在性,.,设,A,是任一含,n,个,命题变项,的,公式,.,由定理,2.3,可知，存在与,A,等值的析取范式,A,，即,A,A,，若,A,的某个简单合取式,中既不含命题变项,，也不含,，则将,展成如下形式：,继续下去，直到所有的,简单合取式,都含任意命题变项或它的否定式,.,若在演算过程中重复出现的命题变项以及,极小项,和矛盾式时，都应“消去”：最后就将,A,化成与之等值的主析取范式,A,。,下面再证明唯一性。,假设某一命题公式,A,存在两,个与之等值的主析取范式,B,和,C,，即,A,B,且,A,C,，,则,B,C,。由于,B,和,C,是不同的主析取范式，不妨设极小项,m,i,只出现在,B,中而不出现在,C,中。于是，角标,i,的二进制表示为,B,的,成真赋值,，而为,C,的,成假赋值,.,这与,B,C,矛盾，因而,B,与,C,必相同。,主合取范式的存在唯一性可类似证明,.,在证明定理,2.5,的过程中，已经给出了求主析取范式的步骤,.,为了醒目和便于记忆，求出某公式的主析取范式（主合取范式）后，将极小项（极大项）都用名称写出，并且按极小项（极大项）名称的角标由小到大顺序排列,.,例,2.8,求公式,(,pq,) r,主析取范式和主合取范式,.,解,:,（,1,）求主析取范式,在例,2.7,中已给出的公式的析取范式，即,（pq） r,(pqr)(pr)(qr),例,2.7,在此析取范式中，简单合取式,pr,，,qr,都不是极小项。下面分别求出它们派生的极小项。,注意，因为公式含三个命题变项，所以极小项均由三个文字组成。,（pr）,p（qq）r,(pqr)(pqr),qr,(pqr）(pqr),(,pp)qr,而简单合取式,pqr,已是极小项,.,于是,(,pq),r,由例,2.7,已求出公式的合取范式，即,(2),再求主合取范式,.,(pq）,r,(pr)(qr)(pqr),其中简单析取式（,pqr,）,已是极大项,M,5,.,利用矛盾律和同一律将不是极大项的简单析取式,化成极大项,.,(pr),(qr),(p(qq)r),(pqr)(pqr),(pqr)(pqr),(pp)qr),于是,(pq） r,记住主要步骤和规则以后，可以很快的求出公式的主析取范式和主合取范式,.,例,2.9,求命题公式,pq,的,主析取范式,和,主合取范式,.,解,:,本公式中含两个命题变项，所以极小项和极大,项均只含两个文字,.,（,1,）,pq,pq,(,主合取范式,),（,2,）,pq,(pq)(pq)(pq),(pq)(pq)(pq)(pq),p（qq）(pp)q,pq,(,主析取范式,),由例,2.8,与,2.9,可知，在求给定公式的主析取范式（主合取范式）时，一定根据公式中命题变项的个数决定极小项（极大项）中文字的个数,.,注意,3,、主范式的应用,(1),求公式的成真和成假赋值,成真赋值：,主析取范式的极小项的下标对应的二进制表示的值；,成假赋值：,主合取范式的极大项的下标对应的二进制表示的值。,（,2,）判断公式的类型,重言式：,主析取范式有,2,n,个极小项；,矛盾式：,主合取范式有,2,n,个极大项；,可满足式：,主析取范式中到少有一个极小项。,（,3,）判断两个命题公式是否等值,两公式等价当且仅当它们有相同主范式。,(4),解决实际问题,(1),若,A,去,则,C,同去,.,(2),若,B,去,则,C,不能去,.,(3),若,C,不去,则,A,或,B,可以去,.,例,2.12,某科研所要从,3,名科研骨干,A,，,B,，,C,中选出,12,名出国进修,.,由于工作的需要,选派是要满足以下条件,:,问所里应如何选派他们,?,四、几点注意,1.,由公式的主析取范式求主合取范式,设公式,A,含,n,个,命题变项, A,的,主析取范式,含,s(0s2n),个,极小项,，即,没出现的极小项为,它们的角标的,二进制表示为,A,的成真赋值，因而,A,的主析取,范式为,A =,由,定理,2.4,可知,A,A,于是，由公式的主析取范式，即可求出它的主合取,范式。,解,（,1,） 由题可知，没出现在主析取范式中的极小项为,和,，所以,A,的主合取范式中含两个极大项,和,，故,例,2.13,由公式的主析取范式，求主合取范式：,（,1,）,A,m,1,m,2,( A,中含两个命题变项,p, q ),（,2,）,B m,1,m,2,m,3,( B,中含两个命题变项,p, q, r ),(2) B,的主析取范式中没出现的极小项为,因而,反之，由公式的主合取范式，也可以确定主析取范式,.,2,重言式与矛盾式的主合取范式,矛盾式,无成真赋值，因而矛盾式的,主合取范式,含,个,极大项,.,（,n,为公式中命题变项个数）,重言式无成假赋值，因而主合取范式不含任何极大项,.,将重言式的主合取范式记为,1.,3,主析取范式有多少种不同的情况,含,n,个命题变项的所有无穷多合式公式中，它们等值的主析取范式（主合取范式）共有多少种不同的情况,?,n,个命题变项可产生 个极小项（极大项），因而共可产生,种不同的主析取范式（主合取范式），由定理,2.5,可知，含,n,个命题变项的所有公式的主析取范式（主合取范式）最多有 种不同情况,.,因而可以这样说，真值表与主析取范式（主合取范式）是描述命题公式标准形式的两种不同的等价形式。,当且仅当,A,与,B,有相同的真值表，,当且仅当,A,与,B,有相同的主析取范式（主合取范式）,可以看出：,作业：,P39,42,5.(3),6.(3),7.(2),13,