《已经交稿----命题逻辑中范式的求解及应用(共13页)》由会员分享，可在线阅读，更多相关《已经交稿----命题逻辑中范式的求解及应用(共13页)（13页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上命题逻辑中范式的求解及应用陶琦春黔南民族师范学院数学系 贵州 都匀 邮编 【摘 要】 本文主要介绍范式及主范式的求解方法，以及范式的应用 。【关键词】范式；极大（小）项； 真值表；推演法；有效性 Propositional formulas Normal Form and Its ApplicationQiChun TaoMath Department of Qiannan Normal College for Nationalities, Duyun, Guizhou, 【Abstract】 This paper mainly introduces the meth
2、od on solving propositional formulas normal form and its application.【Key words】normal form; biggest or smallest item; true value form; deduction method; validity命题逻辑中的范式在离散数学的教学过程中是一个重点内容，同时也是一个难点内容，学好范式的求解方法，了解一些范式的应用人们学习数理逻辑，特别是初学者有很大的帮助。本文主要归纳范式求解的常见方法和范式的一些应用。一 范式的相关概念1.命题逻辑的基本概念定义1.11 设为命题，复合命
3、题“非”(或的否定)称为的否定式，记作称作否定联结词。规定为真当且仅当为假。定义1.2 设、为两个命题，复合命题“或”称为与的析取式，记为 . 称作析取联结词。设、为两个命题，复合命题“并且”称为与的合取式，记为.称作合取联结词。 定义1.3 设是出现在公式中的全部命题变项，给各指定一个真值，称为对的一个赋值或解释。若指定的一组使为1，则称这组值为的成真赋值；若指定的一组使为0，则称这组值为的成假赋值。定义1.4 仅由有限个文字构成的析取式称作简单析取式。仅由有限个文字构成的合取式称作简单合取式。定义1.5 仅由有限个简单合取式的析取构成的命题公式称为析取范式。仅由有限个简单析取式的合取构成的
4、命题公式称为合取范式。定理1（范式存在定理）：任一命题公式都存在与之等值的析取范式与合取范式。一般地，命题公式的析（合）取范式是不惟一的。为了使命题公式的范式惟一，进一步将简单合取式和简单析取式规范化，定义如下。定义1.6 在含有个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定式按下标从小到大或按字典顺序排列，称这样的简单合取式（简单析取式）为极小项（极大项）。定义1.7 所有简单合取式（简单析取式）都是极小项（极大项）的析取范式（合取范式）称为主析取范式（主合取范式）。 二. 范式的求法解析 1.范式的求解方法求给定公式范式的
5、步骤为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 化为个极大项之析取得到的的主合取范式；则将公式中未出现的关于的极大项全合取来为公式，那么即为的主合取范式。证明：即证 ，已知 .不妨设为公式的个极大项 ，而是关于命题变项的另外个极大项。又设I 为公式G 的任一解释（因中同样包含这n个原
9、子）。则解释I 必使某极大项真值为0；同时有.由极大项的性质（2）知：此解释I 必弄真其它有极大项，故 .所以 .若T1 (G )=1 则解释I 不满足 中任一者；于是有由极大项的性质I必满足中某个极大项， 故 ，所以 . 因此特点：若公式 比公式的形式更为简捷，则先求出 ，然后列出 的真值表，将最后列公式真值中1 对应的极大项析取出来，即可得到的主合取范式。（同时也可得到 的主合取范式）如若已知 的主合取范式，则可由这个定理直接写出的主合取范式。1.4用推演法求的主合取范式G*定理：对于任意公式，可由下述方法求得其主合取范式：（1）用推演法求出公式的主析取范式G*。（2）由G*，用德摩根律求
10、出的主合取范式（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 0 1 0 1 0 1 1 0 1 1 1 0 1 1
11、1 1 0 1 1 1 1 1 1 1 1 将公式 的真值中对应的极大项合取出来，则 使用真值表法解决问题的步骤：（1） 先判断是否可用真值表法（即所求公式层次较少时可以用；（2） 列出公式的真值表；（3） 将真值表最后一列的真值0 的左侧的二进制数对应的极大项写出；（4） 将这些极大项合取起来。使用真值表法解决问题时应该注意：一般应用在所求公式层次较少的计算，必须体现出成假赋值。例：求其主析取范式和主合取范式：解: 求主合取范式在求范式的例子中已经给出公式的析取范式，即已是一个合取范式的形式，其中短句与中仅缺一个原子，所以，可直接用推演法，与定理3求知。其中已经是极大项。利用矛盾律和同一律将
12、另两个简单析取式化成极大项。 于是 同样可以求主析取范式：在求范式的例子中已经给出公式的析取范式，即在此析取范式中，第一项是最小项，另外两个简单范式，都不是极小项。下面先分别求出它们的派生极小项。注意，因为公式含有3个命题变项，所以极小项均由3的文字组成。 于是 使用推演法解决问题的步骤：（1） 将所求公式化为任一个合取范式；（2） 检查中每个简单析取式是否为极大项。如果是，则留下；如果某个简单析取式 Go 不是关于的极大项，则中肯定缺少某些命题变项 .则 使用推演法解决问题时应该注意：将所求公式化为任一个合取范式时，这个短句所缺失的原子是否较少（所缺失的原子较少时可以用此方法）。例： 已知公
13、式求主合取范式和主析取范式。解：公式包含有6 个逻辑运算层次，3 个原子以及2 个“”符，因此，若直接使用真值表法，运算将十分烦琐。所以，可先对公式进行初步简化。 这已经是的主合取范式，且形式简单明了。为要求的主析取范式，下一步求的主合取范式，再由定理5 用间接方法得之。 使用推演法求的主合取范式方法解决问题的步骤：（1）用推演法求出公式的主析取范式.（2）由，用德摩根律求出 的主析取范式. （3）求的主合取范（使用德摩根律）.使用推演法求的主合取范式方法解决问题时应该注意：针对逻辑运算层次较多的，在不易直接应用真值表法与推演法的情况下。三、范式的应用 1在电路的逻辑设计方面有广泛的应用例： 加法器的设计，有两个位二进制数相加和为，分别写成： 其中 是第 位、 及 (是第 位向第位的进位)的和，显然 是、 及的函数，写成 (、)，它与、的关系如下表： (、)0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11
