已经交稿----命题逻辑中范式的求解及应用

1、命题逻辑中范式的求解及应用陶琦春2009051328黔南民族师范学院数学系 贵州 都匀 邮编 558000【摘 要】 本文主要介绍范式及主范式的求解方法，以及范式的应用 。【关键词】范式；极大（小）项； 真值表；推演法；有效性 Propositional formula's Normal Form and Its ApplicationQiChun Tao2009051328Math Department of Qiannan Normal College for Nationalities, Duyun, Guizhou, 558000【Abstract】 This paper ma

2、inly introduces the method on solving propositional formula's normal form and its application.【Key words】normal form; biggest or smallest item; true value form; deduction method; validity命题逻辑中的范式在离散数学的教学过程中是一个重点内容，同时也是一个难点内容，学好范式的求解方法，了解一些范式的应用人们学习数理逻辑，特别是初学者有很大的帮助。本文主要归纳范式求解的常见方法和范式的一些应用。一 范式的相

3、关概念1.命题逻辑的基本概念定义1.11 设为命题，复合命题“非”(或的否定)称为的否定式，记作称作否定联结词。规定为真当且仅当为假。定义1.2 设、为两个命题，复合命题“或”称为与的析取式，记为 . 称作析取联结词。设、为两个命题，复合命题“并且”称为与的合取式，记为.称作合取联结词。 定义1.3 设是出现在公式中的全部命题变项，给各指定一个真值，称为对的一个赋值或解释。若指定的一组使为1，则称这组值为的成真赋值；若指定的一组使为0，则称这组值为的成假赋值。定义1.4 仅由有限个文字构成的析取式称作简单析取式。仅由有限个文字构成的合取式称作简单合取式。定义1.5 仅由有限个简单合取式的析取构

4、成的命题公式称为析取范式。仅由有限个简单析取式的合取构成的命题公式称为合取范式。定理1（范式存在定理）：任一命题公式都存在与之等值的析取范式与合取范式。一般地，命题公式的析（合）取范式是不惟一的。为了使命题公式的范式惟一，进一步将简单合取式和简单析取式规范化，定义如下。定义1.6 在含有个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定式按下标从小到大或按字典顺序排列，称这样的简单合取式（简单析取式）为极小项（极大项）。定义1.7 所有简单合取式（简单析取式）都是极小项（极大项）的析取范式（合取范式）称为主析取范式（主合取范式）。

5、 二. 范式的求法解析 1.范式的求解方法求给定公式范式的步骤为1：1.消去联结2.用双重否定律消去双重否定符，用德摩根律内移否定符。3.使用分配律：求析取范式时使用对的分配律，求合取范式时使用对的分配律。例1：求下面公式的析取范式与合取范式： 解：为了清晰与无误，利用交换律使每个简单析取式和简单合取式中命题变项都按字典顺序出现。 （1）先求合取范式 含有3个简单析取式的合取范式。（2）求析取范式 求析取范式和合取范式的前两步是相同的，只有利用分配律时有所不同，因而前4步与（1）相同，接着使用对的分配律。最后两步的结果都是析取范式。 2. 主范式的求法解析求一个公式的主合取（析取）范式可分为直

6、接求法和间接求法，下面就以主合取范式为例各给出它们中的各两种求法, 并进行理论解析。 直接求法类1.1真值表法定理22：对于任意公式，可按下述方法求出其主合取范式：（1）列出公式的真值表。（2）将真值表最后一列的真值0 的左侧的二进制数对应的极大项写出。（3）将这些极大项合取起来。证明：按上述定理的出的极大项的合取式为，往下证.设含有个命题变项且由上面方法共得出个极大项.依 的顺序取公式的任一解释I，并将其对应的二进制数转化为十进制数后记为则 .若，则其对应的极大项必为中之一。此时由极大项的性质，的.若，则其对应的极大项不在中，由极大项性质得. 于是且必为的唯一的主合取范式。特点：利用定理2求

7、出公式的主合取范式简单、容易理解和掌握，且可以一次既可求出其主合取范式，又可求出其主析取范式。但若已知公式层次较多时，会给列真值表带来麻烦，增大计算量。 1.2推演法定理3：对于任意公，其主合取范式可由下面的推演法求出。设为公式的个命题变项。（1） 将公式化为任一个合取范式。（2） 检查中每个简单析取式是否为极大项。如果是，则留下；如果某个简单析取式 Go 不是关于的极大项，则中肯定缺少某些命题变项 . 则 在上述推演中，反复使用分配律、交换律、结合律、幂等律、互补律、零律、同一律等算律，如 ，最终将简单析取式 化成了若干个极大项之合取。对于（1）中其它极大项的简单析取式，重复（2）的方法，将

8、其化成为若干个极大项的合取式。最后将公式运用某些运算律，整理为标准的主合取范式。特点：当将公式初步为合取范式后，各简单析取式所缺命题变项较少，已比较接近主合取范式时，用此方法很简单。若公式中命题变项较多，各命题变项复杂且包含不易化为合取范式；或者化为合取范式后，所缺命题变项较多，使用推演法很麻烦，并容易产生运算错误。间接求法类1.3用真值表法求的主合取范式定理42：已知公式含有个命题变项.公式是按定理2 的方法，将G 化为个极大项之析取得到的的主合取范式；则将公式中未出现的关于的极大项全合取来为公式，那么即为的主合取范式。证明：即证 ，已知 .不妨设为公式的个极大项 ，而是关于命题变项的另外个

9、极大项。又设I 为公式G 的任一解释（因中同样包含这n个原子）。则解释I 必使某极大项真值为0；同时有.由极大项的性质（2）知：此解释I 必弄真其它有极大项，故 .所以 .若T1 (G )=1 则解释I 不满足 中任一者；于是有由极大项的性质I必满足中某个极大项， 故 ，所以 . 因此特点：若公式 比公式的形式更为简捷，则先求出 ，然后列出 的真值表，将最后列公式真值中1 对应的极大项析取出来，即可得到的主合取范式。（同时也可得到 的主合取范式）如若已知 的主合取范式，则可由这个定理直接写出的主合取范式。1.4用推演法求的主合取范式G*定理：对于任意公式，可由下述方法求得其主合取范式：（1）用

10、推演法求出公式的主析取范式G*。（2）由G*，用德摩根律求出的主合取范式（3）求的主合取范（使用德摩根律） .特点：（1）如若公式的主析取范式，运用推演法，易于求得，则使用定理5，可非常方便的求出公式的主合取范式，而且二者可兼得。（2）由该定理易见，对于任何一公式的主合取范式和主析取范式可互相转换。我们可根据实际问题灵活选择方法。例 ：已知公式 ，求其主合取范式解：公式 层次较少，可使用真值表法，由定理2直接求。P q r p q 成假赋值 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 0

11、 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 将公式 的真值中对应的极大项合取出来，则 使用真值表法解决问题的步骤：（1） 先判断是否可用真值表法（即所求公式层次较少时可以用；（2） 列出公式的真值表；（3） 将真值表最后一列的真值0 的左侧的二进制数对应的极大项写出；（4） 将这些极大项合取起来。使用真值表法解决问题时应该注意：一般应用在所求公式层次较少的计算，必须体现出成假赋值。例：求其主析取范式和主合取范式：解: 求主合取范式在求范式的例子中已经给出公式的析取范式，即已是一个合取范式的形式，其中短句与中仅缺一个原子，所以，可直接用推

12、演法，与定理3求知。其中已经是极大项。利用矛盾律和同一律将另两个简单析取式化成极大项。 于是 同样可以求主析取范式：在求范式的例子中已经给出公式的析取范式，即在此析取范式中，第一项是最小项，另外两个简单范式，都不是极小项。下面先分别求出它们的派生极小项。注意，因为公式含有3个命题变项，所以极小项均由3的文字组成。 于是 使用推演法解决问题的步骤：（1） 将所求公式化为任一个合取范式；（2） 检查中每个简单析取式是否为极大项。如果是，则留下；如果某个简单析取式 Go 不是关于的极大项，则中肯定缺少某些命题变项 .则 使用推演法解决问题时应该注意：将所求公式化为任一个合取范式时，这个短句所缺失的原

13、子是否较少（所缺失的原子较少时可以用此方法）。例： 已知公式求主合取范式和主析取范式。解：公式包含有6 个逻辑运算层次，3 个原子以及2 个“”符，因此，若直接使用真值表法，运算将十分烦琐。所以，可先对公式进行初步简化。 这已经是的主合取范式，且形式简单明了。为要求的主析取范式，下一步求的主合取范式，再由定理5 用间接方法得之。 使用推演法求的主合取范式方法解决问题的步骤：（1）用推演法求出公式的主析取范式.（2）由，用德摩根律求出 的主析取范式. （3）求的主合取范（使用德摩根律）.使用推演法求的主合取范式方法解决问题时应该注意：针对逻辑运算层次较多的，在不易直接应用真值表法与推演法的情况下

14、。三、范式的应用 1在电路的逻辑设计方面有广泛的应用例： 加法器的设计，有两个位二进制数相加和为，分别写成： 其中 是第 位、 及 (是第 位向第位的进位)的和，显然 是、 及的函数，写成 (、)，它与、的关系如下表： (、)0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1在电路逻辑设计中,我们如下对应逻辑部件:“否定”对应着“非门”,“合取”可以对应“与门”,“析取”可以对应“或门”。2. 在生活中的应用 例 ：安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将

15、课程安排在第一或第二节。如何安排课表，使得三位教师都满意。令、 分别表示语言课排在第一、第二、第三节。、 分别表示数学课排在第一、第二、第三节。、 分别表示原理课排在第一、第二、第三节。三位教师都满意的条件是:为真。将上式写成析取范式( 用分配律) 得:可以取(、为T ,得到两种排法。3.在排队论中的应用 例： 甲、乙、丙、丁四个人出去参加比赛回来后，向外部透漏比赛结果。甲说：丙第一，乙第二；乙说：丙第二，丁第三；丙说：甲第二，丁第四。已知这三个人说的都是一句真，一句假，并且无并列情况。则四个人的实际名次如何？ 解： 用表示丙第一；用表示乙第二；用表示丙第二；用表示丁第三；用表示甲第二；用表示

16、丁第四；则因为每个人的话中至少有一个真命题，所以它们的析取为真命题，进而，这三个真命题的合取也是真命题。即是一个真命题，同时这又是一个合取范式，现将其转化为析取范式。 因为无并列情况, 所以、均为假命题，又因为分身乏术， 所以 、 、也是假命题，而该公式又是一个真命题，所以就一定是一个真命题、即丙第一、丁第三、甲第二。这样乙就只能是第四了。于是得出实际上的比赛名次如下： 丙第一、 甲第二、丁第三、乙第四。4. 主范式在推理有效性判断中的应用 1 7要掌握主范式在推理有效性判断中的应用需要预备以下知识点：定义 ：设和是两个命题公式，当且仅当是个永真式，即 ，才说是的有效结论，或可由逻辑推出.定理

17、6 设表示第个极小项,则 设表示第个极大项,则 定理7 设 表示第个极大项,则 .定理8 设和是两个命题公式，是永真式的充分必要条件是假定为真则能推出为真，或假定为假则能推出为假。1.利用主析取范式判断推理是否有效命题1： 设和是两个含有个命题变元的命题公式，是的有效结论的充分必要条件是 的主析取范式中含全部个极小项.例8: 判断下面推理是否有效：若是奇数，则不能被2整除.若是偶数，则能被2整除.因此如果是偶数，则不是奇数.解： 设：是奇数，：能被2整除，：是偶数。推理的形式结构为 由于是含有3个命题变元的命题公式，其主析取范式中含有全部8个极小项，为重言式.故推理有效.命题2 设和是两个含有

18、个命题变元的命题公式，若的主析取范式中含全部2个极小项,则是的有效结论.2.利用主合取范式判断推理是否有效命题3 设和是两命题公式，它们共有个不同的命题变元，若与 的主合取范式中的每个极大项都含有这个命题变元，则是的有效结论的充分必要条件是的主合取范式中含有的主合取范式中的所有极大项.例9 判断下面推理是否有效： 如果小王是理科生，则他的数学成绩一定很好。如果小王不是文科生，他一定是理科生。小王的数学成绩不好.所以小王是文科生。解： (1) 设：小王是理科生， ：小王数学成绩好， ：小王是文科生.推理的前提为，结论为. 在( 的主合取范式中含有主合取范式中所有的极大项 . 为 的有效结论，故推理有效.上述给出了利用主析取范式、主合取范式判别推理有效性的两种方法的应用。四、总结本文通过归纳范式的求解方法及范式的应用。我们对范式有了深刻的理解，我们将求主合取范式的方法分为直接方法和间接方法两类，并独立给出它们分别用真值表求解是两个定理的证明。并且利用通俗的道理,使这些形式化的数理逻辑中的范式不再枯燥,与实际生活生动的联系在一起 。参考文献： 1 耿素云. 屈婉玲、