真值函数 1元真值函数 2元真值函数.ppt

《真值函数 1元真值函数 2元真值函数.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、真值函数定义2.12称F:{0,1}n{0,1}为n元真值函数n元真值函数共有个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式1元真值函数p00011101012.2命题逻辑等值演算（续）12元真值函数pq0000000000010000111110001100111101010101pq00111111110100001111100011001111010101012联结词完备集定义2.13设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词完备集定理2.1下述联结词集合都是完备集:(1)S1={,

2、,,,}(2)S2={,,,}(3)S3={,,}(4)S4={,}(5)S5={,}(6)S6={,}AB(AB)(BA)ABABAB(AB)(AB)AB(AB)AB(A)BAB3复合联结词与非式:pq(pq),称作与非联结词或非式:pq(pq),称作或非联结词pq为真当且仅当p,q不同时为真pq为真当且仅当p,q不同时为假定理2.2{},{}是联结词完备集证p(pp)pppq(pq)(pq)(pq)(pq)得证{}

3、是联结词完备集.对于{}可类似证明.42.3范式2.3.1析取范式与合取范式简单析取式与简单合取式析取范式与合取范式2.3.2主析取范式与主合取范式极小项与极大项5简单析取式与简单合取式文字:命题变项及其否定的统称简单析取式:有限个文字构成的析取式如p,q,pq,pqr,…简单合取式:有限个文字构成的合取式如p,q,pq,pqr,…定理2.3(1)一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定6析取范式与合取范式析取范式:由有限个简单合取式组成的析取式A1A2Ar,其中A

4、1,A2,,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式A1A2Ar,其中A1,A2,,Ar是简单析取式范式:析取范式与合取范式的统称定理2.4(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式7范式存在定理定理2.5任何命题公式都存在着与之等值的析取范式与合取范式.证求公式A的范式的步骤：(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)

5、(AB)(AC)求合取范式A(BC)(AB)(AC)求析取范式8范式存在定理(续)例1求(pq)r的析取范式与合取范式解(pq)r(pq)r(pq)r析取范式(pr)(qr)合取范式注意:公式的析取范式与合取范式不惟一.9极小项与极大项定义2.17在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项均以文字的形式出现且仅出现一次，而且第i(1in)个文字(按下标或字母顺序排列)出现在左起第i位上,称这样的简单合取式(简单析取式)为极小项(极大项)Note:(1)n个命题变项产生2n个极小项和2n个

6、极大项(2)2n个极小项(极大项)均互不等值(3)用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.10极小项与极大项(续)定理2.6设mi与Mi是由同一组命题变项形成的极小项和极大项,则miMi,Mimi极小项极大项公式成真赋值名称公式成假赋值名称pq00m0pq00M0pq01m1pq01M1pq10m2pq10M2pq11m3pq11M3p,q形成的极小项与极大项11主析取范式与主合取范式主析取范式:由极小项构成的析取范式

7、主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3是主析取范式(pqr)(pqr)M1M5是主合取范式定理2.7任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.12求主析取范式的步骤设公式A含命题变项p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是简单合取式j=1,2,…,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj