离散数学--命题逻辑1.5.ppt

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

1、1.5对偶与范式对偶式与对偶原理析取范式与合取范式主析取范式与主合取范式1对偶式和对偶原理定义在仅含有联结词,∧,∨的命题公式A中，将∨换成∧,∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)*还原成A定理设A和A*互为对偶式，p1,p2,…,pn是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则(1)A(p1,p2,…,pn)A*(p1,p2,…,pn)(2)A(p1,p2,…,pn)A*(p1,p2,…,pn)定理（对偶原理）设A，B为两个命题公式，若AB，则A*B*.2析取范式

2、与合取范式文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p,q,pq,pqr,…简单合取式:有限个文字构成的合取式如p,q,pq,pqr,…析取范式:由有限个简单合取式组成的析取式A1A2Ar,其中A1,A2,,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式A1A2Ar,其中A1,A2,,Ar是简单析取式3析取范式与合取范式(续)范式:析取范式与合取范式的总称公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式pqr,pqr既是析取范式，又是合

3、取范式(为什么?)4命题公式的范式定理任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1)消去A中的,（若存在）(2)否定联结词的内移或消去(3)使用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一5求公式的范式举例例求下列公式的析取范式与合取范式(1)A=(pq)r解(pq)r(pq)r（消去）pqr（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）6求公式的范式举例(续)(2)B=(pq)r解(pq)r(p

4、q)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）7极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用mi表示第i个极小项，其中i是该极小项成真赋

5、值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.mi与Mi的关系:miMi,Mimi8极小项与极大项(续)由p,q两个命题变项形成的极小项与极大项公式成真赋值名称公式成假赋值名称pqpqpqpq00011011m0m1m2m3pqpqpqpq00011011M0M1M2M3极小项极大项9由p,q,r三个命题变项形成的极小项与极大项极小项极大项公式成真赋值名称公式成假赋值名称pqrpqrpqrpqrpqrpqrpqrpqr00

6、0001010011100101110111m0m1m2m3m4m5m6m7pqrpqrpqrpqrpqrpqrpqrpqr000001010011100101110111M0M1M2M3M4M5M6M710主析取范式与主合取范式主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3是主析取范式(pqr)(pqr)M1M5是主合取范式A的主析取范式:与A等值的主析取范式A的主合取范式:与A等值的主合取范式.11主析

7、取范式与主合取范式(续)定理任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）(2)将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.12求公式的主范式例求公式A=(pq