离散数学析取范式与合取范式.ppt

《离散数学析取范式与合取范式.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、11.4析取范式与合取范式简单析取式与简单合取式析取范式与合取范式主析取范式与主合取范式2定义文字:命题变项及其否定的总称.简单析取式:有限个文字构成的析取式.如p,q,pq,pqr,…简单合取式:有限个文字构成的合取式.如p,q,pq,pqr,…1）一个简单析取式为重言式当且仅当它同时含有一个命题变项及它的否定；2）一个简单和取式为矛盾式当且仅当它同时含有一个命题变项及它的否定.由定义易知：3由有限个简单合取式组成的析取式.A1A2Ar,其中A1,A2,,Ar是简单合取式合取

2、范式:由有限个简单析取式组成的合取式.A1A2Ar,其中A1,A2,,Ar是简单析取式由定义易知：析取范式:1）在析取范式（合取范式）中没有联结词2）联结词只出现在原子命题前面.3）析取范式（合取范式）是合取式（析取式）的析取式（合取式）.4范式:析取范式与合取范式的总称.公式A的析取范式:与A等值的析取范式公式A的合取范式:与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式形如pqr,pqr的公式既是析取范式，又是合取范式(为什么?)5任何命题公式都存在着与之等值的析取

3、范式与合取范式.求公式A的范式的步骤：(1)消去A中的,（若存在）(2)内移或消去否定联结词(3)利用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一，这是它的局限性.定理（范式存在定理）6求公式的范式举例例1.15求下列公式的析取范式与合取范式:(1)A=(pq)r解(pq)r(pq)r（消去）pqr（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）7(2)B=(pq)

4、r解:(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）8例1.16(1)求(pq)(pr)的析取范式;解:(pq)(pr)(pq)(pr)（消去）(pq)(pr)（双重否定律）(pp)(qp)(pr)(qr)（对分配）

5、(qp)(pr)(qr)（零律,同一律）9(2)求(pq)(pr)的合取范式。解:(pq)(pr)(pq)(pr)（消去）(pqp)(pqr)（对分配）pqr（排中律,同一律）10极小项定义在含有n个命题变项的简单合取式中，若每个命题变项均以文字的形式在其中出现且只出现一次，而且第i（1in）个文字出现在左起第i位上，这样的简单合取式称为极小项.如：pq，pqr11说明：n个命题变项产生2n个极小项，2n个极小项均互不等值.用m

6、i表示第i个极小项，其中i是该极小项成真赋值的十进制表示,mi称为极小项的名称.12公式成真赋值极小项pqpqpqpq00011011由p,q两个命题变项形成的极小项:13由p,q,r三个命题变项形成的极小项:公式成真赋值极小项pqrpqrpqrpqrpqrpqrpqrpqr000001010011100101110111m0m1m2m3m4m5m6m714主析取范式主析取范式:由极小项构成的析取范式.例如，n=3,命题变项为p,q,r

7、时，(pqr)(pqr)m1m3是主析取范式A的主析取范式:与A等值的主析取范式.15定理任何命题公式都存在着与之等值的主析取范式,并且是惟一的.用等值演算法求公式的主析取范式的步骤：(1)先求析取范式;(2)将不是极小项的简单合取式化成与之等值的若干个极小项的析取，需要利用同一律、排中律、分配律、等幂律……(3)极小项用名称mi表示，按角标从小到大顺序排序.16求公式的主析取范式例1.17求公式(pq)r的主析取范式.(pq)r(pq)r,（析取范式）①其中(pq)

8、(pq)(rr)(pqr)(pqr)m6m7,②17r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7③②,③代入①并排序，得(pq)rm1m3m5m6m7（主析取范式）18例1.18求下列公式的主析取范式.(pq)(pr)((pq)r)p答案:(1)(pq)(pr)