对偶与范式4

福建师范大学数学与计算机科学学院对偶与范式对偶式的定义在仅含有联结词,∧,∨的命题公式A中,将∨换成∧,∧换成∨,若A中含0或1,就将0换成1,1换成0,所得命题公式称为A的对偶式,记作A*.从定义不难看出,A是A*的对偶式,即对偶式是相互的.又(A*)*＝A.求(P→Q)→R的对偶式(P→Q)→R的对偶式是(P→Q)→R()()PQRPQR()PQR定理1.2设A和A*互为对偶式，P1，P2，…，Pn是出现A和A*中的命题变元，则①A(P1，P2，…，Pn)A*(P1，P2，…，Pn)②A(P1，P2，…，Pn)A*(P1，P2，…，Pn)①表明，公式A的否定等价于其命题变元否定的对偶式②表明，命题变元否定的公式等价于对偶式之否定例A(p,q,r)p∧(q∨r)A*(p,q,r)p∨(q∧r)（1）A(p,q,r)（p∧(q∨r)）p∨(q∧r)A*(p,q,r)p∨(q∧r)（2）A(p,q,r)p∧(q∨r)A*(p,q,r)（p∨(q∧r)）p∧(q∨r)定理1.3（对偶原理）设A，B为两个命题公式，若AB，则A*B*.例1.A1（重言式），则A*0（矛盾式）2.A0（矛盾式），则A*1（重言式）3.p∨(p∨(q∧q)）1则p∧(p∧(q∨q)）0析取范式和合取范式定义1.18仅由有限个命题变项及其否定构成的析取式称作简单析取式。仅由有限个命题变项及其否定构成的合取式称作简单合取式。简单析取式举例：p,┐q，p∨┐p，┐p∨q，┐p∨┐q∨r,p∨┐q∨r简单合取式举例：┐p,q，┐p∧p，p∧┐q，p∧q∧┐r,┐p∧p∧q说明一个文字（p，┐p）既是简单析取式，又是简单合取式。析取范式和合取范式为讨论方便，有时用A1,A2,…,As表示s个简单析取式或s个简单合取式。设Ai是含n个文字的简单析取式，若Ai中既含某个命题变项pj，又含它的否定式┐pj，即pj∨┐pj，则Ai为重言式。反之，若Ai为重言式，则它必同时含某个命题变项和它的否定式，否则，若将Ai中的不带否定符号的命题变项都取0值，带否定号的命题变项都取1值，此赋值为Ai的成假赋值，这与Ai是重言式相矛盾。类似的讨论可知，若Ai是含n个命题变项的简单合取式，且Ai为矛盾式，则Ai中必同时含某个命题变项及它的否定式，反之亦然。定理(P.15)(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式。(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。定义1.19(1)由有限个简单合取式构成的析取式称为析取范式。(2)由有限个简单析取式构成的合取式称为合取范式。(3)析取范式与合取范式统称为范式。设Ai(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨As为析取范式。例如，A1=p∧┐q，A2=┐q∧┐r，A3=p，则由A1,A2,A3构造的析取范式为A=A1∨A2∨A3=(p∧┐q)∨(┐q∧┐r)∨p设Ai(i=1,2,…,s)为简单析取式，则A=A1∧A2∧…∧As为合取范式。例如，取A1=p∨q∨r，A2=┐p∨┐q，A3=r，则由A1,A2,A3组成的合取范式为A=A1∧A2∧A3=(p∨q∨r)∧(┐p∨┐q)∧r说明形如┐p∧q∧r的公式既是一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。形如p∨┐q∨r的公式既是含三个简单合取式的析取范式，又是含一个简单析取式的合取范式。定理(P.16)(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。说明研究范式的目的在于，将给定公式化成与之等值的析取范式或合取范式，进而将公式化成与之等值的主析取范式或主合取范式。范式存在的讨论在范式中不会出现联结词→与，否则可使用等值式消除A→B┐A∨BAB(┐A∨B)∧(A∨┐B)在范式中不会出现形如┐┐A,┐(A∧B),┐(A∨B)的公式：┐┐AA┐(A∧B)┐A∨┐B┐(A∨B)┐A∧┐B在析取范式中不会出现形如A∧(B∨C)的公式：A∧(B∨C)(A∧B)∨(A∧C)在合取范式中不出现形A∨(B∧C)的公式：A∨(B∧C)(A∨B)∧(A∨C)定理1.4任一命题公式都存在着与之等值的析取范式与合取范式。求给定公式范式的步骤(1)用基本等值式消去联结词→、等(若存在)。A→B┐A∨BAB(┐A∨B)∧(A∨┐B)(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。┐┐AA┐(A∧B)┐A∨┐B┐(A∨B)┐A∧┐B(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。A∧(B∨C)(A∧B)∨(A∧C)A∨(B∧C)(A∨B)∧(A∨C)例题例求下面公式的析取范式与合取范式：(p→q)r(1)求合取范式(p→q)r(┐p∨q)r（消去→）((┐p∨q)→r)∧(r→(┐p∨q))（消去）(┐(┐p∨q)∨r)∧(┐r∨┐p∨q)（消去→）((p∧┐q)∨r)∧(┐p∨q∨┐r)（否定号内移）(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)（∨对∧分配律）解答(2)求析取范式(p→q)r((p∧┐q)∨r)∧(┐p∨q∨┐r)[((p∧┐q)∧(┐p∨q∨┐r)]∨[r∧(┐p∨q∨┐r)](p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)说明命题公式的析取范式不唯一。同样，合取范式也是不唯一的。范式的规范化形式定义1.20(1.22)在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为极小项（极大项）。n个命题变项共可产生2n个不同的极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数i，就将所对应极小项记作mi。类似地，n个命题变项共可产生2n个极大项，每个极大项只有一个成假赋值，将其对应的十进制数i做极大项的角标，记作Mi。表1p,q形成的极小项与极大项表2p,q,r形成的极小项与极大项范式的规范化形式定理(p.21)设mi与Mi是命题变项p1,p2,…,pn形成的极小项和极大项，则┐miMi，┐Mimi定义1.21(1.23)设由n个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）为主析取范式（主合取范式）。定理1.5任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。(只证主析取范式的存在和唯一性)(1)证明存在性。设A是任一含n个命题变项的公式。由定理1.4可知，存在与A等值的析取范式A′，即AA′，若A′的某个简单合取式Ai中既不含命题变项pj，也不含它的否定式┐pj，则将Ai展成如下形式：AiAi∧1Ai∧(pj∨┐pj)(Ai∧pj)∨(Aj∧┐pj)继续这个过程，直到所有的简单合取式都含任意命题变项或它的否定式。若在演算过程中出现重复的命题变项和矛盾式时，都应“消去”：如用p代替p∧p，mi代替mi∨mi，0代替矛盾式等。最后就将A化成与之等值的主析取范式A。定理1.5的证明(2)证明唯一性。假设某一命题公式A存在两个与之等值的主析取范式B和C，即AB且AC，则BC。由于B和C是不同的主析取范式，不妨设极小项mi只出现在B中而不出现在C中。于是，角标i的二进制表示为B的成真赋值，而为C的成假赋值。这与BC矛盾，因而B与C必相同。求公式A的主析取范式的方法与步骤方法一、等值演算法(1)化归为析取范式。(2)除去析取范式中所有永假的析取项。(3)将析取式中重复出现的合取项和相同的变元合并。(4)对合取项补入没有出现的命题变元，即添加如(p∨┐p)式，然后应用分配律展开公式。方法二、真值表法(1)写出A的真值表。(2)找出A的成真赋值。(3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。求公式A的主合取范式的方法与步骤方法一、等值演算法(1)化归为合取范式。(2)除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。(4)对析取项补入没有出现的命题变元，即添加如(p∧┐p)式，然后应用分配律展开公式。方法二、真值表法(1)写出A的真值表。(2)找出A的成假赋值。(3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序析取。例求命题公式p→q的主析取范式和主合取范式。(1)求主合取范式p→q┐p∨qM2(2)求主析取范式p→q┐p∨q（┐p∧（┐q∨q））∨（(┐p∨p)∧q）(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)(┐p∧┐q)∨(┐p∧q)∨(p∧q)m0∨m1∨m3解答pqp→q001011100111例求(p→q)r的主析取范式和主合取范式.(1)求主析取范式(p→q)r(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)p∧┐q∧┐rm4┐p∧r┐p∧（┐q∨q）∧r(┐p∧┐q∧r)∨(┐p∧q∧r)m1∨m3q∧r(┐p∨p)∧q∧r(┐p∧q∧r)∨(p∧q∧r)m3∨m7(p→q)rm1∨m3∨m4∨m7(2)求主合取范式(p→q)r(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)┐p∨q∨┐rM5p∨rp∨(q∧┐q)∨r(p∨q∨r)∧(p∨┐q∨r)M0∧M2┐q∨r(p∧┐p)∨┐q∨r(p∨┐q∨r)∧(┐p∨┐q∨r)M2∧M6(p→q)rM0∧M2∧M5∧M6由公式的主析取范式求主合取范式设公式A含n个命题变项。A的主析取范式含s(0s2n)个极小项，即12,021,1,2,,sniiijAmmmijs没有出现的极小项设为snjjjmmm221,,,它们的角标的二进制表示为┐A的成真赋值，因而┐A的主析取范式为snjjjmmmA221)(221snjjjmmmAA)221snjjjmmmsnjjjMMM221例题例13由公式的主析取范式，求主合取范式：(1)Am1∨m2(A中含两个命题变项p,q)(2)Bm1∨m2∨m3(B中含三个命题变项p,q,r)解答(1)AM0∧M3(2)BM0∧M4∧M5∧M6∧M7真值表与范式的关系AB当且仅当A与B有相同的真值表，又当且仅当A与B有相同的主析取范式（主合取范式）。真值表与主析取范式（主合取范式）是描述命题公式标准形式的两种不同的等价形式。n个命题变项共可产生2n个极小项（极大项）可以产生的主析取范式（主合取范式）数目为：nnnnnCCC22212022主析取范式的用途求公式的成真赋值与成假赋值判断公式的类型判断两个命题公式是否等值应用主析取范式分析和解决实际问题求公式的成真赋值与成假赋值若公式A中含n个命题变项，A的主析取范式含s(0≤s≤2n)个极小项，则A有s个成真赋值，它们是所含极小项角标的二进制表示，其余2n-s个赋值都是成假赋值。在例7中，(p→q)rm1∨m3∨m4∨m7,各极小项均含三个文字，因而各极小项的角标均为长为3的二进制数，它们分别是001，011，100，111，这四个赋值为该公式的成真赋值,其余的为成假赋值。在例8中，p→qm0∨m1∨m3，这三个极小项均含两个文字，它们的角标的二进制表示00，01，11为该公式的成真赋值，10是它的成假赋值。判断公式的类型设公式A中含n个命