第一章 命题逻辑(17).ppt

1.7.1对偶,定义1-7.1在给定的命题公式中，将联结词换成，将换成，若有特殊变元F和T亦相互取代，所得公式A*称为A的对偶式。,例：写出下列命题公式的对偶式：（）（）对偶式A*,1.7.1对偶,讨论定义：（）若命题公式中有联结词，则必须把化成由联结词，组成的等价的命题公式，然后求它的对偶式；例：求(PQ)(PR)的对偶式,1.7.1对偶,（）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。例：（）对偶式写成（），而不能写成,1.7.1对偶,定理1-7.1（摩根推广定理）设和A*为对偶式，P1,P2Pn是出现在和A*中的所有原子命题变元，则：（P1，P2Pn）A*（P1，P2Pn）（1）（P1，P2Pn）A*（P1，P2Pn）（）,1.7.1对偶,证明：由摩根定理（）（）（）（）不难看出：一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。,1.7.1对偶,例：设（，）（），验证上述定理：证明：()（，）（，）A*（，）A*（，）（）（，）A*（，）（）有（，）A*（，）,1.7.1对偶,定理1-7.2若两个命题公式互为等价，则它们的对偶式也互为等价，亦即若，则A*B*成立。证明：已知：、为任一命题公式，且，要证明A*B*设：P1、P2Pn是出现在和中的原子命题变元，,1.7.1对偶,由，即（P1，P2Pn）（P1，P2Pn）（P1，P2Pn）（P1，P2Pn）由摩根推广定理*（P1，P2Pn）*（P1，P2Pn）,1.7.1对偶,*（P1，P2Pn）*（P1，P2Pn）为永真式前面讲过永真式的代换实例仍为永真式，所以用Pi代换A*和B*中的Pi（1in)则得：*（P1，P2Pn）*（P1，P2Pn）即为：*（P1，P2Pn）*（P1，P2Pn）,1.7.1对偶,例：证明：（）（）（）（）（）（）（）（）证明：（）左边(）（）（）（）（）（）（）,1.7.1对偶,（）左边（）（）（）（）（）结论：（）和（）是互为对偶的。,1.7.2范式,如何判定命题公式为永真式、永假式和可满足式或二个命题公式等价，归纳有三种方法：（1）真值表法：对于变元的所有真值指派，看对应命题公式的真值。（2）命题演算方法：化简命题公式至最简式，看是否存在和（）、（）等价，若不则为可满足的。（3）范式方法：本节就介绍此法。,1.7.2范式,什么叫范式把命题公式化归为一种标准的形式，称此标准形式为范式。什么叫判定以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。讨论范式和主范式的目的就是为了进行判定。,1.7.2范式,1、析取范式与合取范式定义1-7.2一个命题公式称为合取范式。当且仅当它具有形式A1A2An，其中Ai(i=1,2,n)为由命题变元或其否定所组成的析取式。定义1-7.3一个命题公式称为析取范式。当且仅当它具有形式A1A2An，其中Ai(i=1,2,n)为为由命题变元或其否定所组成的合取式。,1.7.2范式,例如：(PR)(PQR)(PR)是合取范式。(PQ)(PQ)是析取范式,1.7.2范式,范式存在定理任一命题公式都存在着与之等值的析取范式和合取范式。下面给出求任一公式的析取范式和合取范式的步骤:（1）利用蕴含等值式和等价等值式消去公式中的联结词“”和“”；（2）利用德摩根律和双重否定律将联结词“”向内深入，使之只作用于命题变元；（3）利用分配律将公式化为所需要的范式。,1.7.2范式,例求(PQ)R)P的析取范式和合取范式。解（1）求合取范式(PQ)R)P(PQ)R)P（消去）(PQ)R)P(PQ)R)P（深入）(PQ)R)P(PQ)R)P(PQP)(RP)（对的分配律）再利用交换律和幂等律得(PQP)(RP)(PQ)(RP)可见，(PQ)(RP)也是原公式的合取范式，这说明与某个命题公式等值的合取范式不是惟一的。,1.7.2范式,例求(PQ)R)P的析取范式和合取范式。（2）析取范式用对的分配律就可得到析取范式，即(PQ)R)P(PQ)R)P(PR)(QR)P(对分配律)最后结果为原公式的析取范式。利用交换律和吸收律得P(QR)，此公式也是原公式的析取范式，由此可见，与命题公式等值的析取范式也不是惟一的。,1.7.2范式,布尔合取或极小项定义1-7.4n个命题变元，每个变元与它的否定不能同时出现，但是两者必须出现且仅出现一次的合取式。,两个命题变元的极小项：PQ000记作m00或m0PQ011记作m01或m1PQ102记作m10或m2PQ113记作m11或m3,n个命题变元可形成2n个极小项,n个命题变元的极小项的性质：,（1）每个极小项当其真值指派与编码相同时，其真值为T，在其余2n-1种指派情况下均为F。,（2）任意两个不同极小项的合取式为永假。,（3）全体极小项的析取式为永真。,主析取范式,定义1-7.5对于给定的命题公式，如果有一个等价公式，它仅由极小项的析取所组成，则该等价公式称作原式的主析取范式。,主析取范式,定理1-7.3在真值表中，一个公式的真值为T的指派所对应的极小项的析取，即为此公式的主析取范式。,求主析取范式的方法：,1、真值表法2、等值演算法,例利用真值表求、（）、的主析取范式,例利用真值表求、（）、的主析取范式则可直接写出各命题公式的主析取范式：（）（）（）（）（）（）（）（）（）（）（）,等值演算求主析取范式的步骤：,1、求A的析取范式2、消去析取范式中所有为永假的析取项3、合并相同的合取项和相同的变元4、对合取项补入没有出现的命题变元，即添加（PP）式，然后，应用分配律展开公式。5、将极小项按由小到大的顺序排列。,例：求（）的主析取范式解：原式（）（）-（1）化为析取范式（）-（2）消去永假项，变为最简析取范式（）（）（）（）（）-（3）添项（）（）-（4）合并相同最小项,主析取范式的用途：（1）判断两个命题公式是否等值（2）判断一个命题公式的类型（3）求命题公式的成真指派和成假指派,例：证明（）证明方法是写出二命题公式的主析范式，看其是否相同：（）（）（）（）（）而（）（）（）（）（）（）（）（）（）主析范式相同，有（）,1.7.2范式,布尔析取或极大项定义1-7.6n个命题变元，每个变元与它的否定不能同时出现，但是两者必须出现且仅出现一次的析取式。,两个命题变元的极大项：PQ000记作M00或M0PQ011记作M01或M1PQ102记作M10或M2PQ113记作M11或M3,n个命题变元可形成2n个极大项,n个命题变元的极大项的性质：,（1）每个极大项当其真值指派与编码相同时，其真值为F，在其余2n-1种指派情况下均为T。,（2）任意两个不同极大项的析取式为永真。,（3）全体极大项的合取式为永假。,主合取范式：,定义1-7.7对于给定的命题公式，如果有一个等价公式，它仅由极大项的合取所组成，则该等价公式称作原式的主合取范式。,主合取范式：,定理1-7.4在真值表中，一个公式的真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。,求主合取范式的方法：,1、真值表法2、等值演算法,例利用真值表求（PQ）（PR）的主合取范式,（PQ）（PR）（PQR）（PQR）（PQR）（PQR）,等值演算求主合取范式的步骤：,1、求（A）的合取范式2、消去合取范式中所有为永真的合取项3、合并相同的析取项和相同的变元4、对析取项补入没有出现的命题变元，即添加（PP）式，然后，应用分配率展开公式。5、将极大项按由小到大的顺序排列。,例化（PQ）（PR）为主合取范式例化（PQ）R）P为主合取范式,为了使主析取范式和主合取范式表达简洁，用表示小项的析取，i,j,k，即表示mimjmk，用表示大项的合取，i,j,k，即表示MiMjMk。m00m