2.2 析取范式与合取范式ppt课件

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