(3)--1.10 范式离散数学离散数学.ppt

《(3)--1.10 范式离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(3)--1.10 范式离散数学离散数学.ppt（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、范 式n定义假设命题公式A中只有联结词、和，将A中的,1,0分别以,0,1全部替换，得到新的公式A*,A*称为A的对偶，或称A和A*互为对偶。例1：A=(p q)r，其对偶A*=(p q)r例2：A=(pq)r 0，其对偶A*=(pq)r 11、对偶n对偶式的两个定理定理1设公式A中出现的所有个体变项为p1,p2,pn，将A记为A(p1,p2,pn)。若公式A(p1,p2,pn)与公式A*(p1,p2,pn)互为对偶，则有A(p1,p2,pn)A*(p1,p2,pn)A(p1,p2,pn)A*(p1,p2,pn)实际上就是摩根律的推广。1、对偶n对偶式的两个定理定理2设有公式A和B，其对偶分别

2、为A*和B*。若AB，则A*B*。反之亦然。由此可知：“两公式等值”“两公式的对偶式等值”A*为重言式A为矛盾式A*为矛盾式A为重言式A*为可满足式A为可满足式 1、对偶2、范式n简单析取式：仅由有限个个体变项或其否定构成的析取式。例：对p,q,r，p,p,p q,p q r都是简单析取式。n简单合取式：仅由有限个个体变项或其否定构成的合取式。例：对p,q,r，p,p,p q,p q r都是简单合取式。显然：简单析取式是重言式当且仅当同时含有一个个体变项及其否定；简单合取式是矛盾式当且仅当同时含有一个个体变项及其否定。n析取范式：仅由有限个简单合取式构成的析取式。如A=A1 A2 An,Ai(

3、i=1,2,n)为简单合取式。如：(p q)(p q)，(p r)(q r)p，(p q)(p r)(p q)(p r)2、范式n合取范式：仅由有限个简单析取式构成的合取式。如A=A1 A2 Ai An,Ai(i=1,2,n)为简单析取式。如：p q r(p q)(p r)(p q r)(p r)q实际上，析取范式与合取范式是相互对偶的。2、范式任一命题公式都存在着与之等值的析取范式和合取范式。求范式的步骤：(2)的消去或内移。利用德摩根律或双重否定律;范式存在定理(1)消去除,外的其它联结词。(3)利用分配律。求析取范式，利用 对 的分配律；求合取范式，利用 对 的分配律。求命题公式(p q

4、)r)p的析取范式和合取范式。解：(1)求析取范式(p q)r)p(p q)r)p德 摩根律(p r)(q r)p分配律(析取范式)p(q r)吸收律(析取范式)(p q)r)p蕴含等值式(p q)r)p蕴含等值式2、范式例1解：(2)求合取范式(p q)r)pp(q r)(p q)(p r)分配律(合取范式)2、范式求命题公式(p q)r)p的析取范式和合取范式。例1解：(1)求析取范式(pq)(rp)(r q)p)(p q)(r p)(r q)p)(p q)(p r)(p q)(p r)(p q)(r p)(r q)p)(p q)(p r)(p r)(p q)(r p)(r q)p)求命题公式(pq)(rp)(r q)p)的合取范式和析取范式。例2解：(2)求合取范式(pq)(rp)(r q)p)(p q)(p r)(p r)(p(q r)(p r)(p p)(q r)p)(p r)(q r)r)(p q r)(p r)求命题公式(pq)(rp)(r q)p)的合取范式和析取范式。例2n范式的唯一性一个命题公式的合取范式或析取范式不是唯一的。2、范式能否找到“最为规范”的具备唯一性的范式是下一讲的主要内容。THANK YOU