《命题公式主范式的求法及应用》由会员分享，可在线阅读，更多相关《命题公式主范式的求法及应用（21页珍藏版）》请在金锄头文库上搜索。
1、 PINGDINGSHAN UNIVERSITY毕业论文毕业论文( (设计设计) )题题 目目: 命题公式主范式的求法及应用命题公式主范式的求法及应用 院院 ( 系系 ): 数学与信息科学学院 专业专业年年级级: 数学与应用数学 05 级 姓姓 名名: 马蓓蓓 学学 号号: 051030233 指指导导教教师师: 屈聪 硕士 2009 月月 3 日日PINGDINGSHAN UNIVERSITYThesis (design)Subject: The Solution and Application of Principal Norm Formcollege: Mathematics and I
2、nformation Science Major and Grade: Mathematics and Applied Mathematics, Grade 2005 Name: Ma Bei-bei No.: 051030233 Advisor: Master Qu-Cong March3, 2009中文摘要中文摘要本文介绍了命题公式主范式的基本定义及相关定理，并对其作出相应解释；在此基础上，探讨了命题公式主范式的两种求法-真值表和等值演算并举出相应的例子.最后，具体给出了主范式的七个方面的应用，并联系实际对这些应用加以阐述.关键词关键词：主范式，真值表，主析取范式，主合取范式Abstrac
3、tAbstractThis paper introduces the basic definitions and related 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 t
4、o illustrate it; finally, the application of the principal norm 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基础知
5、识1 1.1 相关基本概念1 1.2 命题公式主范式重要的相关定理4 2.命题公式主范式的求法5 21 用真值表求出主析(合)取范式5 22 利用等值演算法求命题公式主析(合)取范式7 3.命题公式主范式在数理逻辑中的重要作用8 3.1 利用主范式可以判断两个命题公式是否等8 3.2 主范式提供了最理想的判别命题公式的类型的判别方法8 3.3 利用主范式可以将一命题公式进行化简9 3.4 利用主范式可求公式的成真赋值与成假赋值9 3.5 利用主范式可以写出一个命题公式的真值10 36 利用主范式可以判断推理过程的准确性10 3.7 可以应用主范式分析和解决实际问题11 4.附 录14 5.参考
6、文献15 6.致 谢16 平顶山学院本科毕业论文（设计）- - 1 1 - -逻辑学是研究思维和论证的科学，也就是研究关于人类推理的学问.在 20 世纪的下半个世纪，伴随着计算机科学技术的迅猛发展，新的逻辑学分支数理逻辑也发展起来.数理逻辑也称为符号逻辑，是一门运用数学的方法来研究推理的形式结构和推理规律的边缘性学科.其内容相当广泛，包括逻辑演算(命题演算与谓词演算)、公理集合论、证明论、递归函数论等，其中逻辑演算是其它各部分的基础.它在逻辑电路、自动控制、人工智能、程序设计、数据库理论以及计算机科学的其它领域有着广泛的应用.本文主要介绍了命题公式主范式的求法及其应用.首先，给出了主范式的基础
7、定义及相关定理，并对其中定义给出解释，定理做出解释；接着，有前面的基础，探讨出主范式的两种求法真值表和等值演算，举出例子来加强对这两种方法的理解；最后，总结主范式的应用，系统地给出它的应用的七个方面，列出实例来充分说明，这是本文的主要特色.1.1.预备知识预备知识1.11.1 相关基本概念相关基本概念定义定义 1.1.11.1.1 (1)单个命题变项和命题常项是合式公式，并称为原子命题公式.(2)若是合式公式，则也是合式公式.A()A(3)若，是合式公式，则,也是合式公式.AB()AB()AB()AB()AB(4)有限次地应用(1)(3)形成的符号串是合式公式.合式公式也称为命题公式或命题形式
8、，简称公式.设为合式公式，为中的一部分，若为合式公式，则称为的子公式.ABABBA为了便于理解，我们对定义 1.1.1 作以下说明：(1)定义引进、等符号，用它们表示任意的合式，作为元语言符号，而具体的公式，AB如的作为对象语言符号.,()p pqpqr(2)为方便，等公式单独出现时，外层符号可以省去，写成，等.()A()ABAAB另外，公式中不影响运算次序的括号也可以省去，如，可以写成()()pqr . pqr 定义定义 1.1.21.1.2 设是出现在公式中的全部命题变项，给各指定12,p pnpA12,np pp一个真值，称为对的赋值或解释.若指定的一组值使为 ，则称这组值为的成真赋AA
9、1A值，若指定的一组值使为，则称这组值为的成假赋值.将命题公式在所有赋值下取A0A值情况列成表，称为的真值表.A在本文中，对含命题变项的公式的赋值采用下述方式：nA(1)若中出现的命题变项为，的赋值是指 .A12,np ppA12 n1122,nnpa papa(2)若中出现的命题变项(按字母顺序)为，的赋值是指A, , ,p q rA12na 命题公式主范式的求法及应用- - 2 2 - -，最后的字母赋值.其中为或 ,.不难看出，含1,npa qani011,2in个命题变项的公式共有个不同的赋值.例如，在中，n(1)n 2n()pqr为成真赋值，为成假赋值.011(0,1,1)pqr10
10、0(1,0,0)pqr根据公式在各种赋值下的取值情况，可按下述定义将命题公式进行分类.定义定义 1.1.31.1.3 设为任一命题公式，A(1)若在它的各种赋值下取值均为真，则称是重言式或永真式.AA(2)若在它的各种赋值下取值均为假，则称是矛盾式或永假式.AA(3)若不是矛盾式，则称为可满足式.AA从上面的定义我们可以看出：(1)为可满足式，则它的等价定义为：至少存在一个成真赋值. AA(2)重言式一定是可满足式，但反之不真.若为可满足式，且它至少存在一个成假赋值，A则称 A 是非重言式的可满足式.定义定义 1.1.41.1.4 设、是两个命题公式，若、构成的等价式为重言式，则ABABAB称
11、与是等值的，记作.ABAB注注: : 定义中的符号不是连接符，它用来说明与是等值的一种记法.因而是元语AB言符号，与不能混为一谈，同时还要注意它与一般的=的区别.定义定义 1.1.51.1.5 有已知的等值式推演出另外一些等值式的过程称为等值演算.(适用于命题逻辑部分的等值式见附录)它是布尔代数和逻辑代数的重要主成部分.在本文中的命题公式等值演算中使用了置换规则，即：设是含公式的命题公式，是用公式( )AA( )B置换中的所有出现后得到的命题公式.若,则.这是显然的，B( )AABA( )( )BA 因为如果，那么在任意的真值赋值下和的真值相同，把它们带入得到的BABA( ) 结果也相同，从而.( )( )AB 定义定义 1.1.61.1.6 命题变项及其否定统称作文字，仅有有限个文字构成的析取式称作简单析取式；仅有有限个文字构成的合取式称作简单合取式.例如，给定命题变项，p，及是简单析取式， 及是简qpqpqpqpqpqpqpq单合取式.定义定义 1.1.71.1.7
