命题逻辑第四节课件.ppt

《命题逻辑第四节课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Lecture04主讲：陈义明信息科学技术学院2.3范式学习内容2信息科学技术学院理解简单合(析)取式以及合(析)取范式的概念,能熟练求一个公式的合(析)取范式。学习目标理解极小项和极大项以及主合(析)取范式的定义，掌握主合(析)取范式的求法。理解主合(析)取范式的用途。3信息科学技术学院简单析取式与简单合取式文字:命题变项及其否定的统称。简单析取式:有限个文字构成的析取式。如pq,pqr,p,q,…。简单合取式:有限个文字构成的合取式如pq,pqr,p,q,…注意：一个文字既是简单析取式又是简单合取式。4信息科学技术学院简单析取式与

2、简单合取式定理2.3(1)一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定。(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定。5信息科学技术学院析取范式与合取范式析取范式:由有限个简单合取式组成的析取式。设A1、A2Ar为简单合取式，则A1A2Ar为析取范式,如:(pq)(qr)p合取范式:由有限个简单析取式组成的合取式。设A1、A2Ar为简单析取式,则A1A2Ar是合取范式。如:(pqr)(pq)r范式:析取范式与合取范式的统称。注意：形如pqr的公式既是析取范式，又是

3、合取范式。类似地，形如pqr的公式有同样的结论。6信息科学技术学院析取范式与合取范式定理2.4(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式。(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式。7信息科学技术学院如何求合(析)取范式？(1)消去A中的,ABABAB(AB)(AB)(2)否定联结词的内移或消去AA(AB)AB(AB)AB(3)使用分配律A(BC)(AB)(AC)求合取范式A(BC)(AB)(AC)求析取范式8信息科学技术学

4、院范式存在定理定理2.5任何命题公式都存在着与之等值的析取范式与合取范式.公式A的范式的步骤：消去A中的,否定联结词的内移或消去使用分配律9信息科学技术学院例1求(pq)r的析取范式与合取范式注意:公式的析取范式与合取范式不惟一.求p(qr)的析取范式与合取范式10信息科学技术学院极小项与极大项定义2.17在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项均以文字的形式出现且仅出现一次，而且第i(1in)个文字(按下标或字母顺序排列)出现在左起第i位上,称这样的简单合取式(简单析取式)为极小项(极大项)。11信息科学技术

5、学院极小项与极大项说明：(2)每个极小项(极大项)都有且仅有一个成真(成假)赋值。(1)n个命题变项产生2n个极小项和2n个极大项(3)用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.12信息科学技术学院极小项与极大项(续)极小项极大项公式成真赋值名称公式成假赋值名称pq00m0pq00M0pq01m1pq01M1pq10m2pq10M2pq11m3pq11M3p,q形成的极小项与极大项定理2.6设mi与Mi

6、是由同一组命题变项形成的极小项和极大项,则miMi,Mimi13信息科学技术学院简单合(析)取式与极小(大)项如何把简单合取式pq用含命题变项p,q,r的极小项表示?pq(pq)(rr)(pqr)(pqr)如何把简单析取式pq用含命题变项p,q,r的极大项表示?pq(pq)(rr)(pqr)(pqr)14信息科学技术学院主析取范式与主合取范式主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m

7、3是主析取范式(pqr)(pqr)M1M5是主合取范式15信息科学技术学院求主析取范式的步骤(1)求A的析取范式A=B1B2…Bs,其中Bj是简单合取式j=1,2,…,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mimi(4)将极小项按下标从小到大排列16信息科学技术学院求主合取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的合取范式A=B1

8、B2…Bs,其中Bj是简单析取式j=1,2,…,s(2)若某个Bj既不含p