(6)--1.12 主合取范式离散数学离散数学.ppt

主合取范式 上一讲介绍了命题公式的主析取范式，这一讲介绍命题公式的“主合取范式”的概念，两者之间实际上是存在关系的。n设命题公式A(p1,p2,pn)，又设Pkpk,pk,k=1.n,则称P1 P2 Pn为公式A的一个极大项。每个命题变量及其否定不能同时存在，但二者必居其一。命题变量pi按照其下标从小到大排列n关于命题公式A(p1,p2,pn)的极大项有2n个。以3命题变量p,q,r为例，可以构造23=8个极大项。1、极大项3个命题变项p、q、r的极大项的表示：p q r000-0，记作M0p q r001-1，记作M1p q r010-2，记作M2p q r011-3，记作M3 p q r100-4，记作M4 p q r101-5，记作M5 p q r110-6，记作M6 p q r111-7，记作M7成假赋值1、极大项2个命题变项p、q的极大项的表示：p q000-0，记作M0p q001-1，记作M1 p q010-2，记作M2 p q011-3，记作M3成假赋值1、极大项n命题公式A称为命题公式B(p1,p2,pn)的主合取范式当且仅当其具有形式A1 A2 Am(1m2n)，其中Ai(1im)为公式B的一个极大项，且AiAj(对ij)。n特别地约定，重言式的主合取范式为1。n任何命题公式的主合取范式一定存在且唯一。2、主合取范式3、主合取范式的求解（1）真值表在真值表中，一个命题公式的真值为0的指派（成假赋值）所对应的极大项的合取式，即为公式的主合取范式。例1：利用真值表求命题公式(p q)(p q)的主合取范式。解：(1)先构造(p q)(p q)的真值表pq(p q)(p q)p q(p q)(p q)000100100110011010111001(2)根据成假赋值写出对应极大项，并排序；成假赋值00，11对应的极大项M0=p qM3=p q(3)主合取范式：M0 M33、主合取范式的求解（2）等值演算n求A的合取范式An若A的某简单析取式B中不含某个命题变量pi，则按如下方法将其补上：BB 0B(pi pi)(B pi)(B pi)n消去重复出现的个体变项、极大项和重言式。n极大项从小到大排序，用表示。如M1 M4 M5(1,4,5)3、主合取范式的求解例2：利用等值演算求公式(pr)q)(qp)的主合取范式。解：(pr)q)(qp)(p r)q)(q p)(p q r)(p q)（合取范式）(p q r)(p q)(r r)(p q r)(p q r)(p q r)M4 M2 M3(2,3,4)主合取范式3、主合取范式的求解n求命题公式的成真、成假赋值。n判断两命题公式是否等值。n判断命题公式的类型。A为重言式，当且仅当A的主合取范式不含任何极大项，即A的主合取范式为1A为矛盾式，当且仅当A的主合取范式包含所有极大项A为可满足式，当A的主合取范式中极大项个数小于2n4、主合取范式的用途5、主合取范式与主析取范式的关系例3：利用真值表求命题公式(p q)(p q)的主析取范式和主合取范式。由真值表可知，一个命题公式的极小项编码和极大项编码是“互补”的。pq(p q)(p q)p q(p q)(p q)000100100110011011111001根据成真赋值写出对应极小项，并排序；m1=p q,m2=p q,m3=p q主析取范式是(1,2,3)根据成假赋值写出对应极大项，并排序；M0=p q主合取范式是(0)例4：求公式(pr)q)(qp)的主析取范式和主合取范式。解：(pr)q)(qp)(p r)q)(q p)(p r q)(q p)(p q r)(p q)(r r)(p q r)(p q r)(p q r)M2 M3 M4(2,3,4)主合取范式（0，1，5，6，7）主析取范式5、主合取范式与主析取范式的关系THANK YOU