计算机数学基础3

1、三、主析取范式：1极小项定义4：如公式中共有N个命题变项P，Pn这N个变项的合取式中，每个变项Pi或其否定 Pi，均出现且两者仅出现一个，并且按命题变项的下标排列（字母按字典序列）这样的简单合取式称为极小项，又称布尔合取。例如：公式中出现P，Q，R三个命题变项PQR，PQR是极小项PQ不是极小项，其中没出现RPQ P不是极小项，P，P同时出现2极小项和赋值的一一对应每一个极小项只有一个赋值使其为真，其余2n-1个赋值使其为假。例如：公式中出现P，Q，R三个不同的赋值。极小项PQR，赋值010使其为真，其余23-1=7个赋值使其为假。这样极小项与赋值建立了一一对应关系。而PQ不是极小项，有两个赋

2、值010，011使其为真，其余6个赋值使其为假。3极小项的记法公式共有2n个赋值，每个赋值对应一个极小项。如极大项对应赋值a1a2a3，把其看作二进数，化为十进数为k0k 2n-1,则该极小项记作ma1a2a3,也记作mk极小项对应的赋值十进制数记法PQR0000M000或M0PQR0011M001或M1PQR0102M010或M2PQR0113M011或M3PQR1004M100或M4PQR1015M101或M5PQR1106M110或M6PQR1117M111或M74.主析取范式：定义4：若干个不同的极小项的析取式，称为主析取范式定理5：任何一个命题公式均存在一个与之等值的主析取范式，而且

3、是唯一的。例如：P（PQ），（PQ）（PR）是析取范式,但不是主析取范式。（PQR）（PQR）是主析取范式，当然也是析取范式。5求主析取范式方法之一：真值表法一个公式的主析取范式与该公式的真值是一一对应的例如：由三个极小项组成的主析取范式（PQR）（PQR）（PQR）这三个极小项对应的赋值分别是111，011，010，则该三个赋值使公式为真，而其它五个赋值使公式为假。而反过来如果这三个赋值公式为真，而其它赋值使公式为假，则该公式的主析取范式就是有这三个赋值对应的极小值的析取而成。因此我们可以用真值表的方法来求出公式的主析取范式。例4：用真值表的方法求（PQ）的主析取范式解：（PQ）的真值表P

4、QPQ（PQ）0 0010 1011 0011 110找使公式为真的赋值。00对应的极小项是PQ （m0）01对应的极小项是PQ （m1）10对应的极小项是PQ （m2）则原公式的主析取范式是（PQ）（PQ） （PQ）（PQ）m0m1 m2例5：用真值表的方法求（PQ）（QR）的主析取范式。解：（PQ）（QR）的真值表P Q RPQQR（PQ）（QR）对应极小项0 0 0011PQR0 0 1001PQR0 1 01000 1 1111PQR1 0 0111PQR1 0 11001 1 01001 1 1111PQR找使公式真值为1的赋值。由此主析取范式为：（PQ）（QR）（PQR）（PQR）

5、（PQR）（PQR）（PQR）m0 m1 m3 m4 m7 6.求主析取范式的方法之二：等值演算法利用十六个命题公式、命题定理用等值演算的方法一步步将它化为主析取范式。第一步：将公式化为析取范式，“消去”含有矛盾式的简单合取式，这是因为（PPQ）GG0，而PP用P代替。第二步：若析取范式中的简单合取式项不是极小项，即该项中缺命题变项，则添加（PiPi）再用分配律展开。例如：公式中含P、Q、R，某合取项为PR，缺Q。则PR PR（QQ）（P QR）（P QR）第三步：用幂等律将重复的极小项删去，即mimimI然后将各极小项按顺序排列。例6：求（PQ）R）P的主析取范式。解：原公式（PQ）R）P（PQ）R）P（PR）（QR）P（析取范式）P（QR）（析取范式）（P（QQ）（RR）（QR）（ PP）（PQR）（PQR）（PQ R）（P