《命题公式主范式的求法及应用.doc》由会员分享，可在线阅读，更多相关《命题公式主范式的求法及应用.doc（21页珍藏版）》请在金锄头文库上搜索。
1、 PINGDINGSHAN UNIVERSITY 毕业论文(设计)题 目: 命题公式主范式的求法及应用 院(系): 数学与信息科学学院 专业年级: 数学与应用数学05级 姓 名: 马蓓蓓 学 号: 051030233 指导教师: 屈聪 硕士 2009月3日 PINGDINGSHAN UNIVERSITY Thesis (design)Subject: The Solution and Application of Principal Norm Form college: Mathematics and Information Science Major and Grade:Mathematic
2、s and Applied Mathematics, Grade 2005 Name: Ma Bei-bei No.: 051030233 Advisor: Master Qu-Cong March3, 2009中文摘要本文介绍了命题公式主范式的基本定义及相关定理，并对其作出相应解释；在此基础上，探讨了命题公式主范式的两种求法-真值表和等值演算并举出相应的例子.最后，具体给出了主范式的七个方面的应用，并联系实际对这些应用加以阐述.关键词：主范式，真值表，主析取范式，主合取范式AbstractThis paper introduces the basic definitions and rela
3、ted theorems of the principal norm form ,which are explained in some aspect. On the base of these ,in order to solove the principal norm form ,we discuss two methods which is truth table and equivalent calculus ,and company with examples to illustrate it; finally, the application of the principal no
4、rm form is given in seven aspects，which is combined with real life,and point out the application by union actual examples.Key words: Principal norm form, Truth table, Principal disjunctive norm form,Principal conjunctive norm form目 录1基础知识11.1 相关基本概念11.2命题公式主范式重要的相关定理42.命题公式主范式的求法521用真值表求出主析(合)取范式522
5、 利用等值演算法求命题公式主析(合)取范式73.命题公式主范式在数理逻辑中的重要作用83.1利用主范式可以判断两个命题公式是否等83.2主范式提供了最理想的判别命题公式的类型的判别方法83.3利用主范式可以将一命题公式进行化简93.4利用主范式可求公式的成真赋值与成假赋值93.5利用主范式可以写出一个命题公式的真值1036利用主范式可以判断推理过程的准确性103.7可以应用主范式分析和解决实际问题114.附 录145.参考文献156.致 谢16平顶山学院本科毕业论文（设计）逻辑学是研究思维和论证的科学，也就是研究关于人类推理的学问.在20世纪的下半个世纪，伴随着计算机科学技术的迅猛发展，新的逻
6、辑学分支数理逻辑也发展起来.数理逻辑也称为符号逻辑，是一门运用数学的方法来研究推理的形式结构和推理规律的边缘性学科.其内容相当广泛，包括逻辑演算(命题演算与谓词演算)、公理集合论、证明论、递归函数论等，其中逻辑演算是其它各部分的基础.它在逻辑电路、自动控制、人工智能、程序设计、数据库理论以及计算机科学的其它领域有着广泛的应用.本文主要介绍了命题公式主范式的求法及其应用.首先，给出了主范式的基础定义及相关定理，并对其中定义给出解释，定理做出解释；接着，有前面的基础，探讨出主范式的两种求法真值表和等值演算，举出例子来加强对这两种方法的理解；最后，总结主范式的应用，系统地给出它的应用的七个方面，列出
7、实例来充分说明，这是本文的主要特色.1.预备知识1.1相关基本概念定义1.1.1 (1)单个命题变项和命题常项是合式公式，并称为原子命题公式.(2)若是合式公式，则也是合式公式.(3)若，是合式公式，则,也是合式公式.(4)有限次地应用(1)(3)形成的符号串是合式公式. 合式公式也称为命题公式或命题形式，简称公式. 设为合式公式，为中的一部分，若为合式公式，则称为的子公式.为了便于理解，我们对定义1.1.1作以下说明：(1)定义引进、等符号，用它们表示任意的合式，作为元语言符号，而具体的公式，如的作为对象语言符号.(2)为方便，等公式单独出现时，外层符号可以省去，写成，等.另外，公式中不影响
8、运算次序的括号也可以省去，如，可以写成. 定义1.1.2 设是出现在公式中的全部命题变项，给各指定一个真值，称为对的赋值或解释.若指定的一组值使为，则称这组值为的成真赋值，若指定的一组值使为，则称这组值为的成假赋值.将命题公式在所有赋值下取值情况列成表，称为的真值表.在本文中，对含命题变项的公式的赋值采用下述方式：(1)若中出现的命题变项为，的赋值是指 .(2)若中出现的命题变项(按字母顺序)为，的赋值是指，最后的字母赋值.其中为或,.不难看出，含个命题变项的公式共有个不同的赋值.例如，在中，为成真赋值，为成假赋值.根据公式在各种赋值下的取值情况，可按下述定义将命题公式进行分类.定义1.1.3
9、 设为任一命题公式，(1)若在它的各种赋值下取值均为真，则称是重言式或永真式.(2)若在它的各种赋值下取值均为假，则称是矛盾式或永假式.(3)若不是矛盾式，则称为可满足式.从上面的定义我们可以看出：(1)为可满足式，则它的等价定义为：至少存在一个成真赋值. (2)重言式一定是可满足式，但反之不真.若为可满足式，且它至少存在一个成假赋值，则称A是非重言式的可满足式.定义1.1.4 设、是两个命题公式，若、构成的等价式为重言式，则称与是等值的，记作.注: 定义中的符号不是连接符，它用来说明与是等值的一种记法.因而是元语言符号，与不能混为一谈，同时还要注意它与一般的=的区别.定义1.1.5 有已知的
10、等值式推演出另外一些等值式的过程称为等值演算.(适用于命题逻辑部分的等值式见附录)它是布尔代数和逻辑代数的重要主成部分.在本文中的命题公式等值演算中使用了置换规则，即：设是含公式的命题公式，是用公式置换中的所有出现后得到的命题公式.若,则.这是显然的，因为如果，那么在任意的真值赋值下和的真值相同，把它们带入得到的结果也相同，从而.定义1.1.6 命题变项及其否定统称作文字，仅有有限个文字构成的析取式称作简单析取式；仅有有限个文字构成的合取式称作简单合取式.例如，给定命题变项，及是简单析取式， 及是简单合取式.定义1.1.7 由有有限个简单合取式构成的析取式称作析取范式；由有有限个简单析取式构成
11、的合取式称作合取范式.析取范式和合取范式统称为范式.析取范式的一般形式为，其中(i=1，2，s)为简单合取式；合取范式的一般形式为，其中(i=1，2，t)为简单析取式. 从上面的定义可以知道()()为析取范式，()()()为合取范式.一般的，命题公式的析取范式是不唯一的，同样，合取范式也是不唯一的.为了使命题公式的范式唯一，进一步将简单析取式和简单合取式规范化，如下：定义1.1.8 在含有个命题变项的简单合取式(简单析取式)中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项和它的否定式按下标由小到大或按字典顺序排列，称这样的简单合取式(简单析取式)为极小项(极大项).由于每个
12、命题变项在极小项中以原形或它的否定式出现且仅出现一次，因而个命题变项共可能产生个不同的极小项.每个极小项有且仅有一个成真赋值.若极小项的成真赋值所对应的二进制等于十进制数，就将这个极小项记作.类似的个命题变项共可能产生个不同的极大项.每个极大项有且仅有一个成假赋值，将其对应的十进制数叫做极大项的角标，记作.注: 用二进制表示的方法具体为：用表示极小项，其下标是二进制数.当极小项出现第个变元时，二进制下标左起第位为1；当极小项出现第个变元否定时，二进制下标k左起第位为0；用十进制表示的方法具体为：将极小项的下标k改为相应的十进制数.例如,二进制表示为，十进制为.同样，用表示极大项，其下标是二进制
13、数.当极大项出现第个变元时，二进制下标左起第位为0；当极小项出现第个变元否定时，二进制下标左起第位为1；例如,二进制表示为，十进制为.在本文中使用十进制，如用表示.定义1.1.9 所有简单合取式(简单析取式)都是极小项(极大项)的析取范式(合取范式)称为主析取范式(主合取范式).注: 主析取范式可能为空，空的主析取范式规定为0；主合取范式可能为空，空的主合取范式规定为1.主析范式恰由使公式成真所对的极小项组成；主合取范式恰由使公式成假所对的极大项组成.1.2命题公式主范式重要的相关定理定理1.2.1 一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式；一个简单合取式是矛盾式当且仅
14、当它同时含有某个命题变项及它的否定式.证明 我们可以从下面的解释得到这个定理：设是含有个文字的简单析取式，若中既含有命题变项，又含有它的否定，有交换律、排中律和零率可知，为重言式.反之，若为重言式，则它同时含有某个命题变项及它的否定式.否则，若中不带否定符号的命题变项都取值，带否定符号的命题变项都取值，此赋值为的成假赋值，这与为重言式相矛盾.类似的，设是含有个文字的简单合取式，若中既含有命题变项，又含有它的否定，则为矛盾式.反之，若为矛盾式，则中必同时含有某个命题变项及它的否定式.定理1.2.2 (1)一个析取式是矛盾式当且仅当它的每个简单合取式都是矛盾式；(2)一个合取式是重言式当且仅当它的每个简单析取式都是重言式.到现在为止，我们研究的命题公式中含有5个联结词，如何把这样的命题公式化成等值的析取范式和合取范式？定理(范式存在定理)1.2.3 任意命题公式都存在与之等值的析取范式和合取范式.证明 首先，可以利用蕴涵等值式与等价等值式 消去任何公式中的联结词和.其次，在范式中不出现如下形式： 对其
