离散数学---范式.ppt

《离散数学---范式.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、§1.5范式从前面的讨论可知,存在大量互不相同的命题公式，实际上互为等价,因此,有必要引入命题公式的标准形式,使得相互等价的命题公式具有相同的标准形式。这无疑对判别两个命题公式是否等价以及判定命题公式的类型是一种好方法,同时对命题公式的简化和推证也是十分有益的.命题公式的标准形式：（主）析取范式（主）合取范式对偶式和对偶原理对偶式：将只含∨∧（如有→，则应该化去）联结词公式A中的联结词∨------->∧,∧------->∨,0------->1,1------->0得到的新公式A*称为A的对偶式。例如：A=(p∧(p∧q)∨T)A*=((p∨(p∨q))∧

2、F)显然：一般情况A≠A*(A*)*=A1.对偶式2.引理:A(p1,p2,…,pn)A*(p1,p2,…,pn)A*(p1,p2,…,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）3.对偶原理若AB，则A*B*证：设P1,P2,…,Pn是出现于A和B中的所有原子变元.因为A(P1,P2,…,Pn)B(P1,P2,…,Pn)则A(P1,P2,…,Pn)B(P1,P2,

3、…,Pn)永真.故A(┐P1,┐P2,…,┐Pn)B(┐P1,┐P2,…,┐Pn)永真.由定理1.7.1得┐A*(P1,P2,…,Pn)┐B*(P1,P2,…,Pn)因此A*B*.显然：如果A是永真式，则A*是永假式。1.简单合取式（基本积）:∧∧…∧,（为Pi或Pi）简单析取式（基本和）：∨∨…∨2.析取范式：基本积的析取式合取范式：基本和的合取式3.任何公式A都存在与之等价的析(合)取范式证(构造法)：1）将A中的→、化掉，使其只含∨∧；2）将否定深入到变元前面；3）使用分配律将公式化为析（合）取范式例如：求A=p∧(q→r)→s的析(合)取范式解:Ap∧(

4、q∨r)→s化掉→(p∧(q∨r))∨s化掉→p∨(q∨r)∨s否定深入p∨(q∧r)∨s否定深入析取范式p∨s∨(q∧r)(p∨s∨q)∧(p∨s∨r)分配律合取范式课堂作业：求(p→q)→(q∨p)的析（合）取范式。q∨p1.极小项：∧∧…∧,（为Pi或Pi）中，1)n个变元全部出现；2)n个变元的位置有序；2)Pi、Pi不同时出现；极大项：∨∨…∨2.主析取范式：极小项的析取式主合取范式：极大项的合取式3.任何公式A都存在与之等价的主析(合)取范式方法1)：真值表法2)：先求析(合)取范式，再求主析、合取范式极小项、极大

5、项的足标与形式的对应例如,三个命题变元P,Q,R,极小项共有8个:小项编码真值指派小项的真值┐P┐Q┐Rm000/m00001┐P┐QRm001/m10011┐PQ┐Rm010/m20101┐PQRm011/m30111P┐Q┐Rm100/m41001P┐QRm101/m51011PQ┐Rm110/m61101PQRm111/m71111n个命题变元最多可产生多少个极小（大）项？三个命题变元P,Q,R,极大项共有8个:大项编码真值指派大项的真值PQRM000/M00000PQ┐RM001/M10010P┐QRM010/M20100P

6、┐Q┐RM011/M30110┐PQRM100/M41000┐PQ┐RM101/M51010┐P┐QRM110/M61100┐P┐Q┐RM111/M71110求主析取和主合取范式的方法（一）——等价演算法1.在公式中消去→及；2.利用∧对∨的分配律或∨对∧的分配律得到析取或合取范式。3.进一步由各个基本积推出所有极小项得到主析取范式或由各个基本和推出所有极大项得到主合取范式。4.由主范式可直接利用上述两个性质2判定该命题公式是否是可满足的。例如：求A=p∧(q→r)的主析、合取范式法一：Ap∧(q∨r)合取范式……(p∨q∨r)∧(p∨q∨r)

7、∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)001000010011010110M0∧M1∧M2∧M3∧M6（主合取范式）m4∨m5∨m7（主析取范式）从主析(合)取范式求真值表：A=p∧(q→r)(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)=M0∧M1∧M2∧M3∧M6pqrp∧(q→r)00000010010001101001011100111001000010110011已知公式A＝p∧(q→r)的真值表，求A的主