简单析取式和简单合取式

《简单析取式和简单合取式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、范　式对偶式简单析取式和简单合取式析取范式和合取范式主范式01计机08号陈燕丽如：┐p∨(q∧r)与┐p∧(q∨r)（P∨q)∨0与（P∧q)∧1互为对偶式定义：在仅含有联结词┐，∨，∧的命题公式A中，将∨换成∧，∧换成∨，若A中含0或1，就将0换成1,1换成0，所得命题公式称为A的对偶式，记作A*。范式----对偶式范式----对偶式定理1.2设A与A*互为对偶式，p,q,r是出现在A和A*中的全部的命题变项，若将A和A*写成函数形式:┐A(p,q,r)┐p∨(q∧┐r)A*(┐p,┐q,┐r)A*(┐p,┐q,┐r)┐p∧(q∨┐r)

2、┐A*(p,q,r)上页对偶原理设A,B为命题公式，若AB,则A*B*，其中A*，B*分别为A,B的对偶式。范式----析取式和合取式定义：仅由有限个命题变项或其否定构成的析取式称为简单析取式。例如：给定命题变项p,q,则p,q,┐p,┐q,p∨q,p∨┐q,┐p∨q,┐p∨┐q都是简单析取式一个简单析取式是重言式，当且仅当它同时含一个命题变项及其否定。p∨┐p∨q是重言式范式----析取式和合取式定义：仅由有限个命题变项或其否定构成的合取式称为简单合取式。一个简单合取式是矛盾式，当且仅当它同时含一个命题变项及其否定。p∧┐p∧q是矛盾式例如

3、：给定命题变项p,q,则p,q,┐p,┐q,p∧q,p∧┐q,┐p∧q,┐p∧┐q都是简单析取式上页范式----析取范式和合取范式析取范式：仅由有限个简单合取式构成的析取式A=(p∧┐q∧r)∨(┐p∧q)∨(q∧┐q)析取范式的对偶式为合取范式合取范式的对偶式为析取范式析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式合取范式是重言式，当且仅当它的每个简单析取式都是重言式合取范式：仅由有限个简单析取式构成的合取式A*=(p∨┐q∨r)∧(┐p∨q)∧(q∨┐q)范式----析取范式和合取范式范式存在定理任一命题公式都存在着与之等

4、值的析取范式和合取范式例求命题公式((p∨q)→r)→q的范式解：化简原式(┐(p∨q)∨r)→q)(消去第一个→)┐(┐(p∨q)∨r)∨p(消去第一个→)┐((┐p∧┐q)∨r)∨p((┐┐p∨┐┐q)∧┐r)∨p((p∨q)∧┐r)∨p求析取范式((p∨q)∧┐r)∨p(p∧┐r)∨(q∧┐r)∨p(∧对∨分配律)p∨(q∧┐r)(交换律和吸收律)上页求合取范式((p∨q)∧┐r)∨p(p∨q∨p)∧(┐r∨p)(p∨q)∧(┐r∨p)(交换律和等幂律)范式----主范式主析取范式概念求主析取范式主合取范式概念求主合取范

5、式范式----主析取范式定义　形如A＝A1∨A2∨……∨An基中Ai(I=1,2,3……n)为极小项记为：∑（m1m2……m2n-1)极小项在n个变元的简单合取式中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，这种合取式叫做极小项pqr记作000m0001m1010m2011m3100m4101m5110m6111m7N个变元可构成2n个极小项p∧┐q∧r范式----求主析取范式任何命题公式的主析取范式都是存在的，并且是唯一的。(4)将极小项按由小到大的顺序排列,并用∑表示∑(2,4,5,6,7)求命题公式A的主析取范式的步骤：

6、求命题公式((p∨q)→r)→p的主析取范式。（1）求A的析取范式A’(2)若A’的某简单合取式B中不含命题变项pi或其否定┐pi，则将B变成极小项如下：BB∧1B∧(pi∨┐pi)(B∧pi)∨(B∧┐pi)解：((p∨q)→r)→pp∨(q∧┐r)（3）将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”，如p∧pp,p∨┐p0P∧(q∨┐q)∧(r∨┐r)∨(p∨┐p)∧(q∧┐r)(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(p∧┐q∧┐r)∨(p∧q∧┐r)∨(┐p∧q∧┐r)111∨110∨101∨10

7、0∨110∨010m2∨m4∨m5∨m6∨m7m7∨m6∨m5∨m4∨m6∨m2pqrp∨(q∧┐r)0000000100010110110010010101101101111110上页范式----主合取范式定义　形如A＝A1∧A2∧……∧An基中Ai(I=1,2,3……n)为极大项记为：∏（m1m2……m2n-1)极大项在n个变元的简单析取式中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，这种析取式就叫做极大项pqr记作000M0001M1010M2011M3100M4101M5110M6111M7┐p∨q∨┐r范式----

8、求主析取范式求p∧q∨r的主合取范式解（p∧q）∨r（P∨r)∧(q∨r)（P∨(q∧┐q)∨r)∧((p∧┐p)∨q∨r)（P