最新离散数学析取范式与合取范式课件PPT.ppt

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

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

2、范式）中没有联结词2）联结词只出现在原子命题前面.3）析取范式（合取范式）是合取式（析取式）的析取式（合取式）.3(2)B=(pq)r解:(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）7例1.16(1)求(pq)(pr)的析取范式;解:(pq)(pr)(pq)(pr)（消去）(pq)(pr)（双重否定律）(

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

4、小项，其中i是该极小项成真赋值的十进制表示,mi称为极小项的名称.11公式成真赋值极小项pqpqpqpq00011011由p,q两个命题变项形成的极小项:12由p,q,r三个命题变项形成的极小项:公式成真赋值极小项pqrpqrpqrpqrpqrpqrpqrpqr000001010011100101110111m0m1m2m3m4m5m6m713主析取范式主析取范式:由极小项构成的析取范式.例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3是主析取范式A的主析取范式:与A等值

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

6、qr)(pqr)m1m3m5m7③②,③代入①并排序，得(pq)rm1m3m5m6m7（主析取范式）17例1.18求下列公式的主析取范式.(pq)(pr)((pq)r)p答案:(1)(pq)(pr)m2m3m5m7(2)((pq)r)pm2m4m5m6m718例1.19由(pq)r的真值表求其主析取范式.pqrpq(pq)r0000010101110111001011101110011111100000主析取范式为：m3m5m719作业:P3617(1)(3)，18(1)，19201.

7、证明：⑴p(qr)(pq)r⑵(pq)(pq)p2.求主析取范式：⑴(pq)r⑵(pq)(qr)(3)(pq)qr(4)(pq)r课堂练习：∑(0,1,3,7)∑(1,3,5,7)∑(5)∑(1,3,4,5,7)21主范式的用途——与真值表相同(1)求公式的成真赋值和成假赋值例如(pq)rm1m3m5m6m7，其成真赋值为001,011,101,110,111，其余的赋值000,010,100为成假赋值.22设A含n个命