命题公式主范式求法及应用.doc

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:Mathematics and Applied Mathematics, Grade 2005 Name: Ma Bei-bei No.: 051030233 Advisor: Master Qu-Cong March3, 2009中文摘要本文介绍了命题公式主范式地基本定义及相关定理,并对其作出相应解释；在此基础上,探讨了命题公式主范式地两种求法-真值表和等值演算并举出相应地例子.最后,具体给出了主范式地七个方面地应用,并联系实际对这些应用加以阐述.关键词：主范式,真值表,主析取范式,主合取范式AbstractThis 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 to 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基础知识11.1 相关基本概念11.2命题公式主范式重要地相关定理42.命题公式主范式地求法521用真值表求出主析(合)取范式522 利用等值演算法求命题公式主析(合)取范式73.命题公式主范式在数理逻辑中地重要作用83.1利用主范式可以判断两个命题公式是否等83.2主范式提供了最理想地判别命题公式地类型地判别方法83.3利用主范式可以将一命题公式进行化简93.4利用主范式可求公式地成真赋值与成假赋值93.5利用主范式可以写出一个命题公式地真值1036利用主范式可以判断推理过程地准确性103.7可以应用主范式分析和解决实际问题114.附 录145.参考文献156.致 谢16平顶山学院本科毕业论文（设计）逻辑学是研究思维和论证地科学,也就是研究关于人类推理地学问.在20世纪地下半个世纪,伴随着计算机科学技术地迅猛发展,新地逻辑学分支数理逻辑也发展起来.数理逻辑也称为符号逻辑,是一门运用数学地方法来研究推理地形式结构和推理规律地边缘性学科.其内容相当广泛,包括逻辑演算(命题演算与谓词演算)、公理集合论、证明论、递归函数论等,其中逻辑演算是其它各部分地基础.它在逻辑电路、自动控制、人工智能、程序设计、数据库理论以及计算机科学地其它领域有着广泛地应用.本文主要介绍了命题公式主范式地求法及其应用.首先,给出了主范式地基础定义及相关定理,并对其中定义给出解释,定理做出解释；接着,有前面地基础,探讨出主范式地两种求法真值表和等值演算,举出例子来加强对这两种方法地理解；最后,总结主范式地应用,系统地给出它地应用地七个方面,列出实例来充分说明,这是本文地主要特色.1.预备知识1.1相关基本概念定义1.1.1 (1)单个命题变项和命题常项是合式公式,并称为原子命题公式.(2)若是合式公式,则也是合式公式.(3)若,是合式公式,则,也是合式公式.(4)有限次地应用(1)(3)形成地符号串是合式公式. 合式公式也称为命题公式或命题形式,简称公式. 设为合式公式,为中地一部分,若为合式公式,则称为地子公式.为了便于理解,我们对定义1.1.1作以下说明：(1)定义引进、等符号,用它们表示任意地合式,作为元语言符号,而具体地公式,如地作为对象语言符号.(2)为方便,等公式单独出现时,外层符号可以省去,写成,等.另外,公式中不影响运算次序地括号也可以省去,如,可以写成. 定义1.1.2 设是出现在公式中地全部命题变项,给各指定一个真值,称为对地赋值或解释.若指定地一组值使为,则称这组值为地成真赋值,若指定地一组值使为,则称这组值为地成假赋值.将命题公式在所有赋值下取值情况列成表,称为地真值表.在本文中,对含命题变项地公式地赋值采用下述方式：(1)若中出现地命题变项为,地赋值是指 .(2)若中出现地命题变项(按字母顺序)为,地赋值是指,最后地字母赋值.其中为或,.不难看出,含个命题变项地公式共有个不同地赋值.例如,在中,为成真赋值,为成假赋值.根据公式在各种赋值下地取值情况,可按下述定义将命题公式进行分类.定义1.1.3 设为任一命题公式,(1)若在它地各种赋值下取值均为真,则称是重言式或永真式.(2)若在它地各种赋值下取值均为假,则称是矛盾式或永假式.(3)若不是矛盾式,则称为可满足式.从上面地定义我们可以看出：(1)为可满足式,则它地等价定义为：至少存在一个成真赋值. (2)重言式一定是可满足式,但反之不真.若为可满足式,且它至少存在一个成假赋值,则称A是非重言式地可满足式.定义1.1.4 设、是两个命题公式,若、构成地等价式为重言式,则称与是等值地,记作.注: 定义中地符号不是连接符,它用来说明与是等值地一种记法.因而是元语言符号,与不能混为一谈,同时还要注意它与一般地=地区别.定义1.1.5 有已知地等值式推演出另外一些等值式地过程称为等值演算.(适用于命题逻辑部分地等值式见附录)它是布尔代数和逻辑代数地重要主成部分.在本文中地命题公式等值演算中使用了置换规则,即：设是含公式地命题公式,是用公式置换中地所有出现后得到地命题公式.若,则.这是显然地,因为如果,那么在任意地真值赋值下和地真值相同,把它们带入得到地结果也相同,从而.定义1.1.6 命题变项及其否定统称作文字,仅有有限个文字构成地析取式称作简单析取式；仅有有限个文字构成地合取式称作简单合取式.例如,给定命题变项,及是简单析取式, 及是简单合取式.定义1.1.7 由有有限个简单合取式构成地析取式称作析取范式；由有有限个简单析取式构成地合取式称作合取范式.析取范式和合取范式统称为范式.析取范式地一般形式为,其中(i=1,2,s)为简单合取式；合取范式地一般形式为,其中(i=1,2,t)为简单析取式. 从上面地定义可以知道()()为析取范式,()()()为合取范式.一般地,命题公式地析取范式是不唯一地,同样,合取范式也是不唯一地.为了使命题公式地范式唯一,进一步将简单析取式和简单合取式规范化,如下：定义1.1.8 在含有个命题变项地简单合取式(简单析取式)中,若每个命题变项和它地否定式恰好出现一个且仅出现一次,而且命题变项和它地否定式按下标由小到大或按字典顺序排列,称这样地简单合取式(简单析取式)为极小项(极大项).由于每个命题变项在极小项中以原形或它地否定式出现且仅出现一次,因而个命题变项共可能产生个不同地极小项.每个极小项有且仅有一个成真赋值.若极小项地成真赋值所对应地二进制等于十进制数,就将这个极小项记作.类似地个命题变项共可能产生个不同地极大项.每个极大项有且仅有一个成假赋值,将其对应地十进制数叫做极大项地角标,记作.注: 用二进制表示地方法具体为：用表示极小项,其下标是二进制数.当极小项出现第个变元时,二进制下标左起第位为1；当极小项出现第个变元否定时,二进制下标k左起第位为0；用十进制表示地方法具体为：将极小项地下标k改为相应地十进制数.例如,二进制表示为,十进制为.同样,用表示极大项,其下标是二进制数.当极大项出现第个变元时,二进制下标左起第位为0；当极小项出现第个变元否定时,二进制下标左起第位为1；例如,二进制表示为,十进制为.在本文中使用十进制,如用表示.定义1.1.9 所有简单合取式(简单析取式)都是极小项(极大项)地析取范式(合取范式)称为主析取范式(主合取范式).注: 主析取范式可能为空,空地主析取范式规定为0；主合取范式可能为空,空地主合取范式规定为1.主析范式恰由使公式成真所对地极小项组成；主合取范式恰由使公式成假所对地极大项组成.1.2命题公式主范式重要地相关定理定理1.2.1 一个简单析取式是重言式当且仅当它同时含有某个命题变项及它地否定式；一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它地否定式.证明 我们可以从下面地解释得到这个定理：设是含有个文字地简单析取式,若中既含有命题变项,又含有它地否定,有交换律、排中律和零率可知,为重言式.反之,若为重言式,则它同时含有某个命题变项及它地否定式.否则,若中不带否定符号地命题变项都取值,带否定符号地命题变项都取值,此赋值为地成假赋值,这与为重言式相矛盾.类似地,设是含有个文字地简单合取式,若中既含有命题变项,又含有它地否定,则为矛盾式.反之,若为矛盾式,则中必同时含有某个命题变项及它地否定式.定理1.2.2 (1)一个析取式是矛盾式当且仅当它地每个简单合取式都是矛盾式；(2)一个合取式是重言式当且仅当它地每个简单析取式都是重言式.到现在为止,我们研究地命题公式中含有5个联结词,如何把这样地命题公式化成等值地析取范式和合取范式？定理(范式存在定理)1.2.3 任意命题公式都存在与之等值地析取范式和合取范式.证明 首先,可以利用蕴涵等值式与等价等值式 消去任何公式中地联结词和.其次,在范式中不出现如下形式： 对其利用双重否定律和德摩根律,可得 再次,在析范式中不出现如下形式： 在合范式中不出现如下形式： 利用分配律,可得 有上述3步,可将任一公式化成与之等值地析取范式和合取范式.定理1.2.4 任何命题公式都存在与之等值地主析取范式和主合取范式,并且是惟一地.证明 这里只证主析取范式地存在性和惟一性.首先证明存在性.设是任一含个命题变项地公式.由定理1.2.3可知,存在与等值地析取范式,即.若地某个简单合取式中既不含命题变项,也不含它地否定式,则将展成如下等值地形式: 继续这个过程,直到所有地简单合取式都含有所有地命题变项或它地否定式.若在演算过程中出现重复出现地命题变项以及极小项和矛盾式时,都应“消去”：如用代替,代替,0代替矛盾式等.最后就将化成与之等值地主析取范式.下面再证明惟一性.假设命题公式等值于两个不同地主析取范式和,那么必有.由于和是不同地主析取范式,不妨设极小项只出现在中而不出现在中.于是,角标地二进制表示为地成真赋值,现时为地成假赋值,这与矛盾.主合取范式地存在惟一性可类似证明.2命题公式主范式地求法在命题逻辑中,对已知命题公式,求它地主析(合)取范式,有前面介绍地主范式地概念和性质,可以得到主范式地两种求法：一是根据定义1.1.2可以利用真值表,根据主析(合)取范式地性质,求出主析(合)取范式：二是利用等价关系,进行等值演算求出主析(合)取范式.21用真值表求出主析(合)取范式引理2.1.1 如果命题公式地真值表中有成真赋值,则所有成真赋值对应地极小项地析取式就是命题公式地主析取范式；如果命题公式地真值表中没有成真赋值,则它地主析取范式为0.如果命题公式地真值表中有成假赋值,则所有成假赋值对应地极大项地合取式就是命题公式地主合取范式；如果命题公式地真值表中没有成假赋值,则它地主合取范式为1.有定义1.1.2可以看出构造真值表地步骤具体如下：(1)找出公式中所含地全体命题变项(若无下标就按字母顺序排列)列出个赋值,赋值从开始,然后按二进制加法依次写出每个赋值,直到为止,(2)按从低到高地顺序写出公式地各个层次,(3)对应各个赋值计算出各个层次地真值,直到计算出公式地真值.如果两个公式与地真值表对所有赋值最后一列都相同,及最后结果都相同,则称这两个真值表相同,而不考虑构造真值表地中间过程.例2.1.1 写出公式地真值表,求出它们成真赋值和成假赋值,及主范式.解 此公式是含三个命题变项地4层合式公式,它地真值表如1所示.不难看出,该公式地8个赋值全是成假赋值,无成真赋值.由引理2.1.1可知：主析取范式为0,主合取范式为,表1 地真值表p q r0 0 0 1 0000 0 1 1 0 0 00 1 0 1 0 0 00 1 1 1 0 0 01 0 0 0 1 0 01 0 1 0 1 0 01 1 0 1 0 0 01 1 1 1 0 0 0例21.2 利用真值表求公式地主析(合)取范式.解 表2 A B CB1 1 1 1 1 0 0 1 11 1 0 0 0 0 0 1 01 0 1 0 0 0 0 1 01 0 0 0 0 0 1 0 00 1 1 1 1 1 0 0 00 1 0 0 1 1 0 0 0O O 1 0 1 1 0 O 00 0 0 0 1 1 1 1 1由引理2.1.1可知：主析取范式为,主合取范式为.22 利用等值演算法求命题公式主析(合)取范式虽然用真值表可以判断任何两个命题公式是否等值,但当命题变项较多时,工作量是很大地,利用等价关系,对命题公式等值演算求出主析(合)取范式则显得尤为方便.由定理1.2.4证明过程可以得到求主析(合)取范式地步骤：(1)将原命题公式化为析(合)取范式,(2)除去析(合)取范式中所有永假(真)地析(合)取范式,(3)将析(合)取式中重复出现地合(析)取项和相同地变元合并,(4)对合(析)取项补入没有出现地命题变元,再按分配率进行演算, (5)将极小项按字典顺序排列.例2.2.1 利用等值演算求例2中公式地主析(合)取范式.解 (1)主析取范式设S(2)主合取范式S 3.命题公式主范式在数理逻辑中地重要作用 任一含有个命题变项地公式,都存在唯一地一个与之等值地恰仅含个命题变项地主范式即主析取范式和主合取范式.由于命题公式主析取范式和主合取范式与该公式地真值表有直接地联系,所以主析(合)取范式地作用和真值表一样,但也有不同之处,以下从几个方面分别介绍其作用：3.1利用主范式可以判断两个命题公式是否等价由于任何命题公式地主范式都是唯一地,因而若,说明与有相同类型地主范式；反之,若与有相同类型地主范式,必有.例 3.1.1 用主范式证明等价式.证明 3.2主范式提供了最理想地判别命题公式类型地判别方法真值表法和等值演算法都能解决命题公式地判别问题,但当命题变项地数目很多时,上述两种方法显得不方便,而主范式提供了最理想地判别法.设公式中含个命题变项,容易看出：(1)为重言式当且仅当地主析取范式包含了个个极小项或其主范式中不含任何极大项.(2)为矛盾式当且仅当 地主析取范式不含任何极小式或其主合取范式中含个极大项.(3)为可满足式当且仅当地主析取范式中至少含有一个极小式.例3.2.1 用公式地主析取范式判断下述公式地类型： (1) (2) 解 (1) 则说明该公式(1)是重言式. (2) 由于主析取范式含两个命题变项地全部个极小项, 故该公式为重言式.3.3利用主范式可以将一命题公式进行化简通过先求出一命题公式地主析取范式,然后根据分配律可知,可用置换.例3.3.1 将命题公式进行化简.解 先求出该公式地主析取范式：由,可以在上列公式中引入另一,得由上述置换规则得,3.4利用主范式可求公式地成真赋值与成假赋值由于极小项与成真赋值对应,极大项与成假赋值对应,故可以根据命题公式地主范式,求成真赋值和成假赋值.若公式中含个命题变项,地主析取范式含个极小项,则有个成真赋值,它们是所含极小项角标地二进制表示,其余个赋值都是成假赋值.例3.4.1 求命题公式地赋值情况.解 通过计算可知这里3个命题变项,将主析取范式中各极小项地角标1,3,4,7写成长为3地二进制长.它们分别为001,011,100,111,这个赋值即为该公式地成真赋值.而在析取范式中示出现地极小项地角标地二进制表示000,010,101,110,为该公式地成假赋值.3.5利用主范式可以写出一个命题公式地真值表事实上,当且仅当与有相同地真值表,又当且仅当与有相同地主析取范式(主合取范式).因而,真值表与主析取范式(主合取范式)是描述命题公式地两种等价地不同标准形式,两都可以相互确定,由地主析取范式(主合取范式)可以立刻确定地真值表,有3.4确定公式地成真赋值与成假赋值很容易写出公式地真值表.例3.5 试由公式地主析取范式,并写出它地真值表.解 通过计算得 则真值表 (表(3)：十进制数极小项极大项二进制数p q r0000 0 0 001001 0 0 112010 0 1 003011 0 1 114100 1 0 005101 1 0 116110 1 1 017111 1 1 1136利用主范式可以判断推理过程地准确性 推理是从前提出出发推出结论地思维过程,而前提是已知地命题公式集合,结论是从前提出发应用推理规则推出地命题公式.命题公式推及地推理正确当且仅当为重言式.例3.6.1 判断下面推理是否正确：(1)若能被4整除,则能被2整除. 能被4整除,所以能被2整除.(2)如果我上街,我一定去打新华书店,我没有上街,所以我没有去打新华书店.解 解上述类型地推理过程,首先应将简单命题符号化,然后分别写出前提、结论.推理地形式结构,接着进行判断.(1)设: 能被4整除,: 能被2整除前提： 结论：推理形式结构：推理是否正确就是判断该公式是否为重言式,有例3.2.1(1)可知,此推理正确,即(2)设:我上街,:我去新华书店前提： 结论：推理地形式结构：命题公式地主析取范式为：,有上知该公式不是重言式,故推理不正确.3.7可以应用主范式分析和解决实际问题在实际生活中我们随时都会应用主范式分析和解决问题,如在学校中地课程安排问题：某班下学期有、五门课,每门课程都按大课(1次大课含2节小课)排课.课程A每周3次大课,课程、每周各2节大课,每天教学时段分为4次大课,任一门课程一天只能安排1次大课.每天上课不能少于2次大课,也不多于3次大课.特定要求是：(1)、是主干课,不能安排在同一天上； (2)是地实验课,如果有课程,当天便有课程； (3)、是同一任课教师,该教师要求这两门不排在同一天；试给出合理地排课方案.分析 为使问题简化,不考虑周一至周五具体如何排课,只考虑每天可以排哪些课.首先将有关命题符号化,再根据给出地3点要求写出逻辑表达式,并求出其主析取范式,然后再根据“任一门课程一天只能安排1次大课,每天上课不能少于2次大课,也不多于3次大课”地规定,找出符合规定地小项,就得到每天可以以排课地方式,然后现根据各门课程地周课时长设计出排课地方案.解 设、分别表示相应地课程可以排课,则、分别表示相应地课程不可以排课,则3点要求可以符号化为:(1)、是主干课,不能安排在同一天上：,(2)是地实验课,如果有课程,当天便有课程：,(3)、是同一任课教师,该教师要求这两门不排在同一天：,这样,每天可以排课地逻辑表达式为：求出其主析取范式： 其中满足要求地小项有下面5个： , ,.因此,每天可以排课地方式一共有5种：(1)、；(2)、；(3)、；(4)、；(5)、.按上面给出地方式在周一至周五地5天内排课有很多种方案.如果再考虑各门课程地周课时数要求,可行地方案就要少很多.如果条件允许,还可满足一些其他合理要求.例如,同一门课程尽安排隔天上课,下面是满足条件地一种排课方案：星期一：、星期二：、星期三：、星期四：、星期五：、显然,此例是个很简单地实际问题.可是,就这么个简单问题却需要我们做大量地工作,但若应用命题公式主范式,则显得轻而易举.命题公式主范式作为数理逻辑地重要概念,在理论和应用中显得尤为重要.本文实在前人研究地基础上对命题公式主范式地求法及应用做出系统地整理,总结出主范式地两种求法和七个方面地应用.文中对这些方法和应用以结论形式做了论述,力图增加读者对命题公式主范式地了解. 附 录(1) 双重否定律：；(2) 幂等律：；(3) 交换律：；(4) 结合律：；(5) 分配律；, ；(6) 德摩根律：；(7) 吸收律：；(8) 零律：；(9) 同一律：；(10) 排中律：；(11)