离散数学对偶和范式.ppt

《离散数学对偶和范式.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、,pn)(2)A(p1,p2,…,pn)A*(p1,p2,…,pn)(1)表明，公式A的否定等价于其命题变元否定的对偶式；(2)表明，命题变元否定的公式等价于对偶式之否定。4对偶式和对偶原理定理（对偶原理）设A，B为两个命题公式，若AB，则A*B*.有了等值式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等值式，使化简命题公式更为方便。5判定问题真值表等值演算范式6析取范式与合取范式文字:命题变项及其否定的总称如p,q简单析取式:有限个文字构成的析取式如p,q,p

3、q,pqr,…简单合取式:有限个文字构成的合取式如p,q,pq,pqr,…注意：一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如p，q等。7析取范式与合取范式定理：简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。定理：简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。8析取范式与合取范式简单析取式:有限个文字构成的析取式如p,q,pq,pqr,…简单合取式:有限个文字构成的合取式如p,q,pq,pqr,…析取范式:由有限个简单

4、合取式组成的析取式A1A2Ar,其中A1,A2,,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式A1A2Ar,其中A1,A2,,Ar是简单析取式9析取范式与合取范式(续)范式:析取范式与合取范式的总称公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式形如pqr,pqr的公式既是析取范式，又是合取范式(为什么?)10命题公式的范式定理任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的

5、步骤：(1)消去A中的,（若存在）（消去公式中除、和以外公式中出现的所有联结词）(2)否定联结词的内移或消去（使用(P)P和德·摩根律）(3)使用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一，这是它的局限性11求公式的范式举例例求下列公式的析取范式与合取范式(1)A=(pq)r解(pq)r(pq)r（消去）pqr（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取

6、式）12求公式的范式举例(续)(2)B=(pq)r解(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）13极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的

7、简单合取式（简单析取式）为极小项（极大项）.例如，两个命题变元p和q，其构成的小项有pq，pq，pq和pq；而三个命题变元p、q和r，其构成的小项有pqr，pqr，pqr，pqr，pqr，pqr，pqr，pqr。14极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.例如

8、，由两个命题变元p和q，构成大项有pq，pq，pq，pq；三个命题变元p，q和r，构成pqr，pqr，pqr，pqr，pqr，pqr，pqr，pqr。15极小项与极大项说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.（将命题变元按字典序排列，并且把命题变元与1对应