1-78 对偶与范式.ppt

《1-78 对偶与范式.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1-7对偶与范式1-7.1对偶式定义1-7.1在给定的命题公式A中，将联结词换成，将换成，若有特殊变元F和T亦相互取代，所得公式A*称为A的对偶式。显然，A也是A*的对偶式。1-7.1对偶式例:求对偶式(PQ)R(PQ)TPQPQ(PQ)(P(QS))(PQ)R(PQ)FPQPQ(PQ)(P(QS))1-7.1对偶式定理1-7.1设A和A*是对偶式，P1，P2，Pn是出现在A和A*中的原子变元，则A(P1,P2,…,Pn)A*(P1,P2,…,Pn)A(P1,P2,…,

2、Pn)A*(P1,P2,…,Pn)证明：由德.摩根定律(PQ)PQ(PQ)PQ故A(P1,P2,…,Pn)A*(P1,P2,…,Pn)同理A(P1,P2,…,Pn)A*(P1,P2,…,Pn)1-7.1对偶式例题：设A(S,W,R)=S(WR)，求它的等价式解：由定理知：A*(S,W,R)=S(WR)A*(S,W,R)=S(WR)A*(S,W,R)=(S(WR))即为A的等价式1-7.1对偶式定理1-7.2设P1，P2，Pn是出现在公式A和B中的所有原

3、子变元，如果AB，则A*B*。证明：见P301-7.2范式(normalform)定义1-7.2合取范式(conjunctivenormalform)：一个命题公式称为合取范式，当且仅当它具有形式：A1A2…An，（n≥1）其中A1，A2，…，An都是由命题变元或其否定所组成的析取式。例(PQR)(PQ)Q是一个合取范式。(PQ)是否是合取范式？(PQ)是否是合取范式？是不是1-7.2范式定义1-7.3析取范式(disjunctivenormalform)：一个命题公式称为析取范式，当且仅当它具有形式：A1

4、A2…An，（n≥1）其中A1，A2，…，An都是由命题变元或其否定所组成的合取式。例P(PQR)(PQ)是一个析取范式。(PQ)是否是析取范式？(PQ)是否是析取范式？是不是1-7.2范式求命题公式的合取范式或析取范式的三个步骤见P311-7.2范式例：求P((QR)S)的析取范式。解：原式P((QR)S)P((QR)S)P(QR)S例：求(PQ)R的合取范式。解：原式(PQ)R(PQ)R(PR)(QR)1-7.2范式请做P39(1)求

5、公式P(PQ)的析取范式和合取范式。解：原式P(PQ)为合取范式(PP)(PQ)为析取范式F(PQ)PQ1-7.3主析取范式定义1-7.4[小项]n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。例如：两个命题变元P、Q，其小项为PQ，PQ，PQ，PQ1-7.3主析取范式三个命题变元P、Q、R，其小项为PQR，PQR，PQR，PQR，PQR，PQR，PQR，PQR一般说来，n个命题变元

6、共有2n个小项。1-7.3主析取范式可以得出结论：（1）没有两个小项是等价的（2）每个小项只对应P和Q的一组真值指派，使得该小项的真值为T。记作：m11=PQ，m10=PQ，m01=PQ，m00=PQ总结出规律：在小项中，看P34小项的性质小项的性质（1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1种指派情况下均为F。（2）任意两个不同小项的合取式永假。（3）全体小项的析取式永为真，记为：1-7.3主析取范式定义1-7.5对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析

7、取范式。定理1-7.3在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。证明见P34。1-7.3主析取范式例：求(PQ)R的主析取范式。解：用真值表法：PQRPQ(PQ)RTTTTTTTFTFTFTFTTFFFTFTTTTFTFTFFFTTTFFFTF1-7.3主析取范式上式的主析取范式为：(PQR)(PQR)(PQR)(PQR)(PQR)m111m101m100m011m001=1,3,4,5,7PQRPQ(PQ)RTTTTTTFTFTTFFF

8、TFTTTTFFTTT1-7.3主析取范式求主析取范式的方法分为：（1）真值表法（2）等价公式法看P36推演步骤看P35例题8，例题91-7.3主析取范式例：求(P