《离散数学第三讲-范式与主范式[一类教资].ppt》由会员分享，可在线阅读，更多相关《离散数学第三讲-范式与主范式[一类教资].ppt（26页珍藏版）》请在三一文库上搜索。
1、第三讲 范式与主范式,1.为什么引入范式？ 命题公式千变万化，不易于研究其性质和应用。 2.解决办法：将命题公式转化为逻辑等价的标准形。 范式-逻辑等价的标准形式,1,苍松课资,讲授重点：范式与主范式的求法 讲授难点：主范式的求法,讲授内容： 1. 范式 析取范式 合取范式 2. 主范式 主析取范式 主合取范式 3. 主析取范式的个数,第三讲 范式与主范式,2,苍松课资,1.文字：命题变元或命题变元否定，P, Q； 2.质合取式：若干个文字的合取, P Q R; 3.质析取式：若干个文字的析取, P Q R; 4.析取范式: 若干质合取式的析取,若与公式A等价， 则称它为A 的析取范式。 5.
2、合取范式: 若干质析取式的合取，若与公式A等价， 则称它为A 的合取范式。,1、范式-析取范式与合取范式,合取式-称为积 析取式-称为和,3,苍松课资,析取范式:,合取范式:,1、范式-析取范式与合取范式,4,苍松课资,范式存在定理,定理1：任意一个命题公式A都存在与之等价的 析取范式和合取范式。,1、范式-析取范式与合取范式,5,苍松课资,1)、化成限定性公式；A中，化成 ，；,析取范式,合取范式,对的分配律 （合取范式）,E11: (PQ) P Q; E10: (PQ) P Q, PP,1、范式-析取范式与合取范式,2)、将否定联结词移到命题变量的前面, 摩根律E10,E11；,3)、消除
3、多余的否定联结词，双否定律,4)、用对的分配律化成，析取范式。,常用公式,6,苍松课资,任给一个命题公式A,经过以上四步演算,即得到一个与A等值的析取范式或合取范式. 任何命题公式的析取范式和合取范式都不是唯一的,1、范式-析取范式与合取范式,7,苍松课资,2、主范式-主析取范式与主合取范式,特殊的质合取式,1. 小项,极小项定义：,8,苍松课资,例如：2 个变元P , Q 可构造 4 个极小项,2、主范式,极小项的个数：n个命题变元可以构成 个极小项。,我们把对应的十进制数当作足标, 用mi表示这一项, 即,9,苍松课资,2、主范式,一般，n个变元的极小项是:,10,苍松课资,2、主范式,2
4、.主析取范式: 若干个极小项的析取,若与公式A等价，则称它为A 的主析取范式。,求命题公式A的主析取范式的步骤： 1) 求公式A 的析取范式A 2) 展开：若A的某简单质合取式B中不含命题变项pi或其否定 pi,则将B展成如下形式： B BT B(PiPi) (BPi)(BPi) 3) 消去：将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”,如PP用P代,PP用F代,mimi用mi代。 4) 排序：小项的序号从小到大。,例2. 求命题公式(PQ)R的主析取范式。,11,苍松课资,例2. 求命题公式(PQ)R的主析取范式。,2、主范式,12,苍松课资,2、主范式,极小项的性质： 1).极
5、小项之间彼此不等价； 2).极小项与使其为真的指派之间建立了一一对应关系 3).主析取范式中，极小项与真值表中相应指派处公式真值为1的相对应。,主析取范式与真值表的关系,例如： 极小项 足标 指 派 m5 - 101 1，0，1,13,苍松课资,2、主范式,3.大项,极大项：,14,苍松课资,4. 主合取范式 若干个大项的合取,若与公式A等价，则称它为A 的主合取范式。,2、主范式,例4 求(PQ)R的主合取范式.,求命题公式A的主合取范式的步骤： （1）先求出合取范式A. （2）若A的某简单析取式B中不含命题变项Pi ,或其否定Pi, 则将B展成如下形式： B BF B(Pi Pi) (BP
6、i)(B Pi).,15,苍松课资,例4 求(PQ)R的主合取范式.,2、主范式,解： (PQ)R (PR)(QR) (合取范式) (P(Q Q)R)(P P)QR) (PQR)(P QR) (PQR) (PQR) (PQR)(P QR)(PQR) M0M2M4 (0,2,4) 其中表示合取.,16,苍松课资,极小项与极大项的关系 一个命题公式的主析取范式和主合取范式紧密相关, 在它们的简记式中, 代表极小项和极大项的足标是互补的, mi Mi, Mi mi. 原命题A与其否命题A的关系 设命题公式A中含n个命题变元，且设A的主析取范式中含k个极小项mil,mi2,mik则 A的主析取范式中必
7、含2n-k个极小项,设为mjl,mj2, , , 即 A mjl mj2 A A (mjl mj2 ) mjl mj2 Mjl Mj2 ,极小项与极大项之间的关系,17,苍松课资,(1)求出A的主析取范式中没包含的极小项mj1,mj2, . (2)求出与(1)中极小项下标相同的极大项Mj1,Mj2, . (3)由以上极大项构成的合取式为A的主合取范式.,主析取范式与主合取范式的关系,极小项与极大项之间的关系,18,苍松课资,一个命题公式的真值表是唯一的, 因此一个命题公式的主析取范式(主合取范式)也是唯一的。,2、主范式,两个命题公式如果有相同的主析取范式(主合取范式), 那么两个命题公式是逻
8、辑等价的。,定理2：在真值表中使一个命题公式A的真值为真(假)的指派所对应的小项(大项)的析取(合取)，即为A的主析取范式(主合取范式) 。,19,苍松课资,A：(PQ)R B：m001 m011 m101 m110 m111 (1)对使A的真值为真的指派，由于它所对应的小项在B中，所以此类指派也使B的真值为真。 (2)对使A的真值为假的指派，由于它所对应的小项不在B中，所以此类指派也使B的真值为假。 故A与B同真假，从而逻辑等价,例：,2、主范式,(PQ)R的主析取范式 (PQ)R m001m011m101m110m111 (1,3,5,6,7),20,苍松课资,主范式的应用 利用主范式可以
9、求解判问题或者证明等价式成立。,2、主范式,(1) 判定命题公式的类型 根据主范式的定义和定理，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式；其次按下列条件判定之： (a)若A，或A可化为与其等价的、含2n个小项的主析取范式，则A为永真式。 (b)若A，或A可化为与其等价的、含2n个大项的主合取范式，则A为永假式。 (c)若A不与或者等价，且又不含2n个小项或者大项，则A为可满足的。,21,苍松课资,（2）证明命题公式是否等价 由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。,2、主范式,22,苍松课资,当n=1时,极小项有21=2个，即P, P。主析取范式有 :,3、主析取范式的个数,23,苍松课资,当n=2 时，极小项有 22=4 个，即PQ ，PQ ， PQ ，PQ。主析取范式有,3、主析取范式的个数,24,苍松课资,共222=16 个。以此类推, n个命题变元, 可构造22n个不同的主析取范式(包括F)。这个数字增长非常快, 如n=3时223=256, n=4 时224=65 536。 主合取范式和主析取范式是一一对应的, 因此, n个命题变元, 也可构造22n个不同的主合取范式(包括T)。,3、主析取范式的个数,25,苍松课资,作业：P21 习题1.3 2 ( 2)、 3 (2)、,26,苍松课资,