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

第三讲 范式与主范式 第三讲 范式与主范式 讲授重点：范式与主范式的求法 讲授难点：主范式的求法 1、范式---析取范式与合取范式 1.文字：命题变元或命题变元否定，P, ? Q； 2.质合取式：若干个文字的合取, P∧ ? Q ∧ R; 3.质析取式：若干个文字的析取, P ∨ Q ∨ ? R; 4.析取范式: 若干质合取式的析取,若与公式A等价， 则称它为A 的析取范式。 5.合取范式: 若干质析取式的合取，若与公式A等价， 则称它为A 的合取范式。 1、范式---析取范式与合取范式 1、范式---析取范式与合取范式 范式存在定理 1、范式---析取范式与合取范式 2、主范式-主析取范式与主合取范式 2、主范式 2.主析取范式: 若干个极小项的析取,若与公式A等价，则称它为A 的主析取范式。 例2. 求命题公式(P∧Q)∨R的主析取范式。 2、主范式 极小项的性质： 1).极小项之间彼此不等价； 2).极小项与使其为真的指派之间建立了一一对应关系 3).主析取范式中，极小项与真值表中相应指派处公式真值为1的相对应。 2、主范式 4. 主合取范式 若干个大项的合取,若与公式A等价，则称它为A 的主合取范式。 2、主范式 例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的主合取范式. 一个命题公式的真值表是唯一的, 因此一个命题公式的主析取范式(主合取范式)也是唯一的。 2、主范式 主范式的应用 利用主范式可以求解判问题或者证明等价式成立。 2、主范式 （2）证明命题公式是否等价 由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。 作业：P21 习题1.3 2 ( 2)、 3 (2)、 * * 1.为什么引入范式？ 命题公式千变万化，不易于研究其性质和应用。 2.解决办法：将命题公式转化为逻辑等价的标准形。 范式----逻辑等价的标准形式 讲授内容： 1. 范式 析取范式 合取范式 2. 主范式 主析取范式 主合取范式 3. 主析取范式的个数 合取式---称为积 析取式---称为和 析取范式: 合取范式: 定理1：任意一个命题公式A都存在与之等价的 析取范式和合取范式。 1)、化成限定性公式；A中→，?化成 ? ，∧，∨； 析取范式 合取范式 ∨对∧的分配律 （合取范式） E11: ?(P∧Q) ? ?P∨ ?Q; E10: ?(P∨Q) ? ?P∧ ?Q ? ? P?P 1、范式---析取范式与合取范式 2)、将否定联结词?移到命题变量的前面, 摩根律E10,E11； 3)、消除多余的否定联结词，双否定律 4)、用∧对∨的分配律化成，析取范式。 常用公式 任给一个命题公式A,经过以上四步演算,即得到一个与A等值的析取范式或合取范式. 任何命题公式的析取范式和合取范式都不是唯