离散数学第三讲-范式与主范式.ppt

第三讲范式与主范式讲授重点：范式与主范式的求法
讲授难点：主范式的求法1.文字：命题变元或命题变元否定，P,¬Q；
2.质合取式：若干个文字的合取,P∧¬Q∧R;
3.质析取式：若干个文字的析取,P∨Q∨¬R;
4.析取范式:若干质合取式的析取,若与公式A等价，
则称它为A的析取范式。
5.合取范式:若干质析取式的合取，若与公式A等价，
则称它为A的合取范式。
析取范式:
范式存在定理

任给一个命题公式A,经过以上四步演算,即得到一个与A等值的析取范式或合取范式.
任何命题公式的析取范式和合取范式都不是唯一的
2、主范式-主析取范式与主合取范式2、主范式2、主范式例2.求命题公式(P∧Q)∨R的主析取范式。2、主范式2、主范式4.主合取范式
若干个大项的合取,若与公式A等价，则称它为A的主合取范式。
例4求(P∧Q)∨R的主合取范式.极小项与极大项的关系
一个命题公式的主析取范式和主合取范式紧密相关,在它们的简记式中,代表极小项和极大项的足标是互补的,
miMi,Mimi.
原命题A与其否命题A的关系
设命题公式A中含n个命题变元，且设A的主析取范式中含k个极小项mil,mi2,…,mik则A的主析取范式中必含2n-k个极小项,设为mjl,mj2,…,,
即Amjl∨mj2∨…
AA(mjl∨mj2∨…)
mjl∧mj2∧…∧
Mjl∧Mj2∧…∧(1)求出A的主析取范式中没包含的极小项mj1,mj2,···,.
(2)求出与(1)中极小项下标相同的极大项Mj1,Mj2,···,.
(3)由以上极大项构成的合取式为A的主合取范式.一个命题公式的真值表是唯一的,因此一个命题公式的主析取范式(主合取范式)也是唯一的。A：(P∧Q)∨R
B：m001∨m011∨m101∨m110∨m111
(1)对使A的真值为真的指派，由于它所对应的小项在B中，所以此类指派也使B的真值为真。
(2)对使A的真值为假的指派，由于它所对应的小项不在B中，所以此类指派也使B的真值为假。
故A与B同真假，从而逻辑等价主范式的应用
利用主范式可以求解判问题或者证明等价式成立。
（2）证明命题公式是否等价
由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。
当n=1时,极小项有21=2个，即P,P。主析取范式有:当n=2时，极小项有22=4个，即┏P∧┏Q，┏P∧Q，P∧┏Q，P∧Q。主析取范式有共222=16个。以此类推,n个命题变元,可构造22n个不同的主析取范式(包括F)。这个数字增长非常快,如n=3时223=256,n=4时224=65536。
主合取范式和主析取范式是一一对应的,因此,n个命题变元,也可构造22n个不同的主合取范式(包括T)。作业：P21习题1.3
2(2)、3(2)、