第23讲 命题公式的范式.ppt

离散数学,第23讲 命题公式的范式,第3章 命题逻辑,3.5 命题公式的范式,本讲内容,,3.5 命题公式的范式,命题公式的范式就是其标准形式或规范形式.有了命题公式的范式, 就可以不用写出真值表就能确定在何真值指派下取真以及在何真值指派下取假.,1. 命题公式的析取范式及合取范式(1) 析取范式及合取范式的定义 Def 3-5 设A是命题公式, 若A = A1 A2  …  An (n 1), 其中Ai(1 i  n)是由命题变元或其否定组成的合取式, 则称A1 A2  …  An为A的析取范式(disjunctive normal form). Remarks Ai= p  q  r, p  q, q  r, q, r? n = 1? 如A = p  q  r = (p  q  r ).,Def 3-6 设A是命题公式, 若A = A1 A2  …  An (n 1), 其中Ai(1 i  n)是由命题变元或其否定组成的析取式, 则称A1 A2  …  An为A的合取范式(conjunctive normal form). Remarks Ai= p  q  r, p  q, q  r, q, r? n = 1? 如A = p  q  r = (p  q  r ).若A = p  q  r , 则p  q  r也是A的析取范式.,(2) 析取范式及合取范式的计算Step1 使用等值式, 将命题公式中的联结词归约为, , ；Step2 利用De Morgan律将移到命题变元的前面；Step3 根据分配律得到命题公式的析取范式及合取范式：A(BC) = (AB)(AC)(求析取范式用).A(BC) = (AB)(AC)(求合取范式用).,例3-17 设p, q和r是命题变元,求命题公式A = (p  q)  r的析取范式及合取范式.Solution 求命题公式的析取范式及合取范式的Step1和Step2是相同的.,析取范式:合取范式:,(3)析取范式及合取范式的应用根据命题公式的析取范式及合取范式可分别得出该命题公式取真、假的指派.,例3-18 从p, q, r, s四人中选派2人出差,求满足下列3个条件的选派方法有哪几种.(1)若p去,则r和s中只去1人；(2)q和r不能都去；(3)若r去, 则s不能去.Solution p: p去出差, q: q去出差, r: r去出差, s: s去出差,则(1)(2)(3),(a)p, s去;(b)q, s去;(c)p, r去.,2. 命题公式的主析取范式及主合取范式一般来说, 命题公式的析取范式及合取范式不是唯一的, 如A = (p  q)  (p  q) = p都是A的析取范式. 下面讨论, 给定命题公式的唯一的标准形式：主析取范式以及主合取范式.给定命题公式, 从A中命题变元产生的最小项和最大项的角度来讨论A的主析取范式及主合取范式, 在逻辑电路中也会讨论其相应的标准形式.,(1)主析取范式Def 对于给定的命题变元,若由命题变元或其否定组成的合取式满足(1) 每个命题变元或其否定二者之一只出现一次; (2)按字典顺序或按下标从小到大顺序出现, 称这样的合取式为由所给命题变元产生的最小项.,,对于每一个最小项只有一种指派使其取1.可以根据这个结论对最小项编码. 最小项用表示mi,其下标是由成真指派得到的二进制数或对应的十进制数, 对于最小项p q  r, 成真指派得到的二进制数为110, 因为(110)2 = 6, 所以p q  r = m110= m6 . 表3-15?,Def 对于命题公式A, 若A等值于由A中所有命题变元产生的若干个最小项的析取, 则把后者称为A的主析取范式(major disjunctive form).含n个命题变元的命题公式,“若干个”最大为2n, 最小为0. 所有最小项的析取为永真式1, 而0个最小项的析取意味着A为永假式0, 这时的主析取范式不存在. 除这两种极端情形外, A均为中性式.,显然, 主析取范式是析取范式, 但反过来不成立.,根据这个分析, 我们得到求A的主析取范式的第一种方法：等值演算法.利用等值演算法求A的主析取范式的步骤为Step1 求出A的析取范式；Step2 利用分配律补充所缺少的命题变元.由上面的主析取范式可知,使A取1的真值指派为(p, q, r) = (1, 0, 0), (0, 1, 1), (0, 0, 1), (1, 1, 1). 实际上,我们可以利用A的真值表求A的主析取范式.,利用真值表求主析取范式的3个步骤为Step1 写出命题公式A的真值表；Step2 对于使A取1的指派,写出对应的最小项,使该最小项在该指派下也为1；Step3 (可以证明)A等值于所有这样写出的最小项的析取.,例3-20 设p, q和r是命题变元,求命题公式 (p  q)  r 的主析取范式.,,(2) 主合取范式主合取范式的讨论与主析取范式是类似的,为了方便自学, 我们还是进行完整的讨论.Def 3-9 对于给定的命题变元, 若由命题变元或其否定组成的析取式满足(1) 每个命题变元或其否定二者之一只出现一次; (2)按字典顺序或按下标从小到大顺序出现,称这样的析取式为由所给命题变元产生的最大项(maximal term).,对于每一个最大项只有一种指派使其取0.可以根据这个结论对最大项编码. 最大项用表示Mi,其下标是由成假指派得到的二进制数或对应的十进制数, 对于最大项p  q  r, 成真指派得到的二进制数为001, 因为(001)2 = 1, 所以p  q  r = M001= M1 .,Def 3-10 对于命题公式A, 若A等值于由A中所有命题变元产生的若干个最大项的合取, 则把后者称为A的主合取范式.含n个命题变元的命题公式,“若干个”最大为2n, 最小为0. 所有最大项的合取为永假式0, 而0个最大项的合取意味着A为永真式1 , 这时的主合取范式不存在. 除这两种极端情形外, A均为中性式.,主合取范式是合取范式, 但反过来不成立.,根据这个分析,我们得到求A的主合取范式的第一种方法：等值演算法. 利用等值演算法求A的主合取范式的步骤为Step1 求出A的合取范式；Step2 利用分配律补充所缺少的命题变元.由上面的主合取范式可知,使A取0的真值指派为(p, q, r) = (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 0, 1). 实际上,我们可以利用A的真值表求A的主合取范式.,下面介绍求的主合取范式的第二种方法：真值表法.Step1 写出命题公式A的真值表；Step2 对于使A取0的指派,写出对应的最大项,使该最大项在该指派下也为0；Step3 (可以证明)A等值于所有这样写出的最大项的合取.,例3-22 设p, q和r是命题变元,求命题公式 (p  q)  r 的主合取范式.,,Theorem 3-9 任意非永假命题公式都存在唯一的主析取范式; 任意非永真命题公式都存在唯一的主合取范式. (1) 命题公式的主析取范式和主合取范式是等值的. (2) 主析取范式中所含的最小项个数加上主合取范式中所含的最大项个数等于该命题公式的真值指派数目. (3) 可以从主析取范式求出主合取范式,反过来亦然(?).,A. 利用命题公式的主析取范式及主合取范式判定其类型. 例3-23 设p和q是命题变元,利用主范式判断命题公式p  (p q)的类型. Solution,B. 利用命题公式的主析取范式及主合取范式可以判断两个命题公式是否等值.例3-24(1)(2),C. 在数字逻辑等后继课程中的应用.例3-25 设公式A的真值表如下, 求A.,将A化简.门电路实现.,解法1比解法2好, 因为最小项的个数为3而最大项的个数为5, 所以在电路实现时对A进行的化简要容易些. 一般原则是,若取1的个数小于取0的个数,求出主析取范式; 若取0的个数小于取1的个数,求出主合取范式. 同一个命题公式的主析取范式与其主合取范式是等值的.只要给出了一个命题公式的真值表,就可以将该命题公式(的表达式)求出来. 这一点在3.6节中也会用到.,另外, 根据真值表法可知,若得出了命题公式的主析取范式, 则可以得出使为真的所有指派, 进而得出使为假的所有指派, 因此可以得出命题公式的主合取范式; 反过来亦然.,,小结与作业,,,Any Questions,,?,Thank You !,。