简单析取式和简单合取式.pptVIP

第1页，共12页，星期日，2025年，2月5日如：┐p∨(q∧r)与┐p∧(q∨r)（P∨q)∨0与（P∧q)∧1互为对偶式定义：在仅含有联结词┐，∨，∧的命题公式A中，将∨换成∧，∧换成∨，若A中含0或1，就将0换成1,1换成0，所得命题公式称为A的对偶式，记作A*。范式----对偶式第2页，共12页，星期日，2025年，2月5日范式----对偶式

定理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)?┐A*(p,q,r)上页对偶原理设A,B为命题公式，若A?B,则A*?B*，

其中A*，B*分别为A,B的对偶式。第3页，共12页，星期日，2025年，2月5日范式----析取式和合取式定义：仅由有限个命题变项或其否定构成的析取式称为简单析取式。

例如：给定命题变项p,q,则

p,q,┐p,┐q,p∨q,p∨┐q,┐p∨q,┐p∨┐q都是简单析取式一个简单析取式是重言式，当且仅当它同时含一个命题变项及其否定。p∨┐p∨q是重言式第4页，共12页，星期日，2025年，2月5日范式----析取式和合取式定义：仅由有限个命题变项或其否定构成的合取式称为简单合取式。

一个简单合取式是矛盾式，当且仅当它同时含一个命题变项及其否定。p∧┐p∧q是矛盾式例如：给定命题变项p,q,则

p,q,┐p,┐q,p∧q,p∧┐q,┐p∧q,

┐p∧┐q都是简单析取式上页第5页，共12页，星期日，2025年，2月5日范式----析取范式和合取范式析取范式：

仅由有限个简单合取式构成的析取式A=(p∧┐q∧r)∨(┐p∧q)∨(q∧┐q)析取范式的对偶

式为合取范式合取范式的

对偶式为析

取范式析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式合取范式是重言式，当且仅当它的每个简单析取式都是重言式合取范式：

仅由有限个简单析取式构成的合取式A*=(p∨┐q∨r)∧(┐p∨q)∧(q∨┐q)第6页，共12页，星期日，2025年，2月5日范式----析取范式和合取范式范式存在定理任一命题公式都存在着与之等值的析取范式和合取范式例求命题公式((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)

(交换律和等幂律)

第7页，共12页，星期日，2025年，2月5日范式----主范式主析取范式概念求主析取范式主合取范式概念求主合取范式第8页，共12页，星期日，2025年，2月5日范式----主析取范式定义形如A＝A1∨A2∨……∨An 基中Ai(I=1,2,3……n)为极小项

记为：∑（m1m2……m2n-1)极小项在n个变元的简单合取式中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，这种合取式叫做极小项pqr记作000m0001m1010m2011m3100m4101m5110m6111m7N个变元可构成2n个极小项p∧┐q∧r第9页，共12页，星期日，2025年，2月5日