离散数学-命题逻辑.pptVIP

*实例将公式的真值进行分解，分解成一些子公式，该子公式仅有一组解释使其真值为真，此时的每一个子公式都对应了一个极小项。p?q?r(p→q)?r┐p∧┐q∧r┐p∧q∧rp∧┐q∧┐rp∧q∧r0?0?0000000?0?1110000?1?0000000?1?1101001?0?0100101?0?1000001?1?0000001?1?110001将极小项全部进行析取后，可得到相应的主析取范式：?(p→q)?r=(┐p∧┐q∧r)∨(┐p∧q∧r)∨(p∧┐q∧┐r)∨(p∧q∧r)写出A的真值表。找出A的成假赋值。求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序合取。方法二、真值表法方法一、等值演算法化归为合取范式。除去合取范式中所有永真的合取项。将合取式中重复出现的析取项和相同的变元合并。对析取项补入没有出现的命题变元，即添加如(p∧┐p)式，然后应用分配律展开公式。求公式A的主合取范式的方法与步骤实例(1)等值推演法求主合取范式(p→q)?r?(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)┐p∨q∨┐r?M5p∨r ?p∨(q∧┐q)∨r ?(p∨q∨r)∧(p∨┐q∨r) ?M0∧M2┐q∨r?(p∧┐p)∨┐q∨r ?(p∨┐q∨r)∧(┐p∨┐q∨r) ?M2∧M6(p→q)?r?M0∧M2∧M5∧M6实例*p?q?rp→q(p→q)?r0?0?0100?0?1110?1?0100?1?1111?0?0011?0?1001?1?0101?1?111(2)真值表法求(p→q)?r的主合取范式。解?首先列出其真值表实例将公式的真值进行分解，分解成一些子公式，该子公式仅有一组解释使其真值为假，此时的每一个子公式都对应了一个极大项将极大项全部进行析取后，可得到相应的主合取范式：(P→Q)?R=(P∨Q∨R)∧(P∨┐Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)p?q?r(p→q)?rp∨q∨rp∨┐q∨r┐p∨q∨┐r┐p∨┐q∨r0?0?0001110?0?1111110?1?0010110?1?1111111?0?0111111?0?1011011?1?0011101?1?111111真值表技术*利用真值表技术求主析取范式和主合取范式的简要方法：①从真值表知，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个成真解释所对应的极小项，将这些极小项的析取即可得到相应的主析取范式。②从真值表知，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个成假解释所对应的极大项，将这些极大项的合取即可得到相应的主合取范式。从真值表按所给的算法求出主范式的方法，称为真值表技术（TechniqueofTruthTable）。Try1Try*设G=┐(p→q)∨r，求出它的主析取范式和主合取范式。（分别用等值推演和真值表法）主范式的应用*设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值求公式的成真成假赋值成真赋值为001,011,101,110,111，成假赋值为000,010,100.类似地，由主合取范式也立即求出成假赋值和成真赋值.例如(p??q)?r?m1?m3?m5?m6?m7判断公式的类型主范式的应用*2.判断公式的类型设A含n个命题变项.A为重言式?A的主析取范式含全部2n个极小项?A的主合取范式不含任何极大项,记为1.A为矛盾式?A的主合析取范式含全部2n个极大项?A的主析取范式不含任何极小项,记为0.A为非重言式的可满足式?A的主析取范式中至少含一个、但不是全部极小项