第四讲对偶及范式对偶的定义：将命题公式中的A换成V,▽换成A,T和F互相替代，所得公式即为公式A的对偶式，记作A*例如：((pVq)AF)人(TAq(rVqp))的对偶式为：((pAq)VT)V(FVq(rAqp))下面给出两个对偶定理1、命题公式的否定定价于其各个命题变项否定之后所组成的对偶式。举例来说：命题公式pAq,其否定：q(pAq),等于其各个命题变项否定之后qP,qq所组成的对偶式qpVqq。即q(pAq)。qpVqq这就是德•摩根律2、设A*,B*分别是A,B的对偶式，如果AoB，那么A*oB*。也就是说,一对等价公式的对偶式也等价。范式在提出范式之前,要先提出两个概念：简单合取式和简单析取式。简单合取式：用A连接各个命题变项或其否定所形成的命题公式就是简单合取式。比如pAq,pAqAqr,pAqpAqr都是简单合取式。简单析取式：用V连接各个命题变项或其否定所形成的命题公式就是简单析取式。比如pVq,pVqVqr,pVqpVqr都是简单析取式。需要注意的是：p,qp即是简单合取式,又是简单析取式。给出两个显而易见的定理：一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及其否定,如pAqpAqr一个简单析取式是重言式当且仅当它同时含有某个命题变项及其否定,如pVqpVqr范式的定义：由有限个简单合取式构成的析取式称为析取范式。如(pAq)V(pAqpAqr)由有限个简单析取式构成的合取式称为合取范式。如rA(pVq)A(pVqVqr)析取范式和合取范式统称为范式。需要指出的是：pAqAnr即是一个简单合取式所构成的析取范式，又是一个由三个简单析取式构成的合取范式。同样的pVqVqr即是一个简单析取式所构成的合取范式，又是一个由三个简单合取式构成的析取范式析取范式和合取范式具有如下性质：一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。下面给出一个重要定理：任一命题公式都存在着与之等价的析取范式和合取范式。主范式主范式是一种范式的标准，它是存在且唯一。主范式的提出是对范式的一种规范化。在提出主范式的定义之前。需要先提出两个概念：极小项和极大项。极小项：在一个简单合取式中，如果每个命题变项和它的否定仅出现一个，并且必须出现一个，并且命题变项或其否定是按固定的顺序排列的（一般为字典顺序，即a,b,c），那么称这样的简单合取式为极小项。比如pAqAqr,pAq。极大项：在一个简单析取式中，如果每个命题变项和它的否定仅出现一个，并且必须出现一个，并且命题变项或其否定是按固定的顺序排列的，那么称这样的简单析取式为极大项。比如pVqVqr,pVq。在提出了极小项和极大项之后，我们可以在命题公式，命题变项的真值和二进制
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示之间建立一个对应关系。如下表所示。其中，公式为真时，p,q,r的赋值称为成真赋值。公式为假时，p,q,r的赋值称为成假赋值。Mi,m：的脚标i表示赋值列中的三个数值所组成的二进制所对应的十进制数。由表所知：「m：oMj极小项极大项公式成真赋值名称公式成假赋值名称npAnqAnr000m1pVqVr000叫npAnqAr001叫pVqVqr001M2npAqAnr010叫pVqqVr010M3qpAqAr011m丄丄丄4pVqqVnr011M4pAqqAqr100mrnpVqVr100叫pAqqAr101mrnpVqVqr101M6pAqAqr110m7npVqqVr110m7pAqAr111m丄丄丄8HpVqqV1r111M8主范式的定义：由n个命题变项构成的析取范式中所有的简单合取式都是极小项，称为主析取范式。由n个命题变项构成的合取范式中所有的简单析取式都是极大项，称为主合取范式。任何命题公式都存在着与之等价的主析取范式和主合取范式。通过一道例题来介绍主析取范式和主合取范式的求法：例：求((pVq)fr)fp的主析取范式和主合取范式((pVq)fr)fpo(n(pVq)Vr)^pon(n(pVq)Vr)Vpo(pVq)AqrVpo(pVq)A(qrVp)下一步非常关键：前一个括号内缺少r,所以析取一个(rAr),后一个括号也是同样，如果是(pAq)，就合取一个(rVqr)；o((pVq)V(rAqr))A((qrVp)V(qAnq))o(pVqVr)A(pVqVqr)A(pVqrVq)A(pVqrVqq)o(pVqVr)A(pVqVqr)A(pVqrVqq)oMoooAMooiAMoiiomoioVmiooVmioiVmiioVmiii主析取范式和主合取范式的简记式中的角标是互补的，知其一即可求另一个。另一种求法是画真值表。主范式的作用如下：1.求公式的成真赋值与成假赋值2.判断公式的类型。A为重言式当且仅当它的主析取范式含全部2n个极小项。A为矛盾式当且仅当它的主析取范式不含极小项。A为可满足式当且仅当它的主析取范式至少含有一个极小项。3判断两公式是否等价。求出两公式的主析取范式，若相同，则等价；否则，不等价。
浙公网安备 33021202002483