简单析取式和简单合取式

1、简单析取式和简单合取式第1页，共12页，2022年，5月20日，5点56分，星期二如：p(qr)与p(qr) （Pq)0与（Pq) 1互为对偶式定义：在仅含有联结词，的命题公式A中，将换成， 换成，若A中含0或1，就将0换成1,1换成0，所得命题公式称为A的对偶式，记作A*。范 式 - 对 偶 式第2页，共12页，2022年，5月20日，5点56分，星期二范 式 - 对 偶 式定理1.2设A与A*互为对偶式，p,q,r是出现在A和A*中的全部的命题变项，若将A和A*写成函数形式:A(p,q,r)p(qr)A*(p,q,r)A*(p,q,r)p(qr)A*(p,q,r)上页对偶原理 设A,B为命

2、题公式，若AB,则A*B*， 其中A*，B*分别为A,B的对偶式。第3页，共12页，2022年，5月20日，5点56分，星期二范 式 - 析取式和合取式定义：仅由有限个命题变项或其否定构成的析取式称为简单析取式。例如 ：给定命题变项p,q,则p, q, p, q, pq, pq, pq, pq 都是简单析取式一个简单析取式是重言式，当且仅当它同时含一个命题变项及其否定。 ppq是重言式第4页，共12页，2022年，5月20日，5点56分，星期二范 式 - 析取式和合取式定义：仅由有限个命题变项或其否定构成的合取式称为简单合取式。一个简单合取式是矛盾式，当且仅当它同时含一个命题变项及其否定。 p

3、pq是矛盾式例如 ：给定命题变项p,q,则p, q, p, q, pq, pq, pq,pq 都是简单析取式上页第5页，共12页，2022年，5月20日，5点56分，星期二范 式 - 析取范式和合取范式析取范式：仅由有限个简单合取式构成的析取式A=(pqr)(pq)(qq)析取范式的对偶 式为合取范式合取范式的 对偶式为析 取范式析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式合取范式是重言式，当且仅当它的每个简单析取式都是重言式合取范式：仅由有限个简单析取式构成的合取式A*=(pqr)(pq)(qq)第6页，共12页，2022年，5月20日，5点56分，星期二范 式 - 析取范式和合取

4、范式范式存在定理 任一命题公式都存在着与之等值的析取范式和合取范式例 求命题公式(pq)r)q的范式解：化简原式(pq)r)q) (消去第一个) (pq)r)p (消去第一个) (pq)r)p (pq)r)p (pq)r)p求析取范式(pq)r)p(pr)(qr)p(对分配律) p(qr) (交换律和吸收律)上页求合取范式 (pq)r)p(pqp)(rp) (pq)(rp) (交换律和等幂律) 第7页，共12页，2022年，5月20日，5点56分，星期二范 式 - 主范式主析取范式概念求主析取范式主合取范式概念求主合取范式第8页，共12页，2022年，5月20日，5点56分，星期二范 式 -

5、主析取范式定义形如AA1A2An基中Ai(I=1,2,3n) 为极小项记为：（m1m2m2n-1)极小项在n个变元的简单合取式中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，这种合取式叫做极小项pqr记作000m0001m1010m2011m3100m4101m5110m6111m7N个变元可构成2n 个极小项pqr第9页，共12页，2022年，5月20日，5点56分，星期二范 式 - 求主析取范式任何命题公式的主析取范式都是存在的，并且是唯一的。 (4)将极小项按由小到大的顺序排列,并用表示(2,4,5,6,7)求命题公式A的主析取范式的步骤：求命题公式( pq)r)p的主析

6、取范式。（1）求A的析取范式A(2)若A的某简单合取式B中不含命题变项pi 或其否定 pi ，则将B变成极小项如下：BB1B(pipi)(Bpi)(Bpi)解：(pq)r)pp(qr) （3）将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”，如ppp, pp0 P(qq)(rr) (pp)(qr)(pqr)(pqr)(pqr)(pqr) (pqr)(pqr)111110101100110010m2m4m5m6m7m7m6m5 m4m6m2pqrp(qr)0000000100010110110010010101101101111110上页第10页，共12页，2022年，5月20日，5点5

7、6分，星期二范 式 - 主合取范式定义形如AA1 A2 An基中Ai(I=1,2,3n) 为极大项记为：（m1m2m2n-1)极大项在n个变元的简单析取式中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，这种析取式就叫做极大项pqr记作000M0 001M1 010M2 011M3 100M4 101M5 110 M6 111M7 pqr第11页，共12页，2022年，5月20日，5点56分，星期二范 式 - 求主析取范式求pq r的主合取范式解（pq）r （Pr)(qr) （P(qq)r)(pp)qr) （Pqr)(Pqr)(pqr)(pqr) 000 010 000 011 M0 M2 M3 (0,2,3)求出