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