《主范式的求法及应用》由会员分享，可在线阅读，更多相关《主范式的求法及应用（23页珍藏版）》请在金锄头文库上搜索。
1、- O158 单位代码 11395 密 级 学 号 1204210135 学生毕业论文题 目主式的求法及应用作 者王定超院 (系)数学与统计学院专 业数学与应用数学指导教师祁兰辩论日期2016年5月21日. z.-榆 林 学 院毕业论文诚信责任书本人重声明：所呈交的毕业论文，是本人在导师的指导下独立进展研究所取得的成果。毕业论文中凡引用他人已经发表或未发表的成果、数据、观点等,均已明确注明出处。尽我所知，除文中已经注明引用的容外，本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成果.对本文的研究做出重要奉献的个人和集体，均已在文中以明确方式标明.本人毕业论文与资料假设有不实，愿意承当一
2、切相关的法律责任。论文作者签名:年 月 日. z.-摘 要主式即主合取式与主析取式，它是数理逻辑中重要的基石也是推动计算机科学开展的动力，其方法与应用颇有价值.本文通过介绍主式的相关定理、定义并作出相应解释，以及由式的不唯一性引出主式的唯一性，得到求主式的三种方法：真值表法、真值指派法、等值演算法，并给出主式的四种应用：判断几个命题公式是否等价、命题公式的类型、求公式的成真成假赋、解决实际问题.关键词：主式；真值表；真值指派法；等值演算法. z.-The method and application of principal normal form ABSTRACTPrincipal norm
3、al form are the host conjunctive normal form and the host disjunctive normal form. It is an important cornerstone in the mathematical logic and the power of impelling the puter science development. The method and the application is of great value.In this paper,we make corresponding e*planation and t
4、he non-uniqueness of the paradigm leads to the uniqueness of principal normal formby the introduction of related theorem of principal normal form anddefinition. We get the methodsofprincipal normal form: truth table method, true value assignment method, and equivalent calculating method, and then gi
5、ve the applicationsofprincipal normal form: judging several propositional formulas whether equivalent or not, the type of propositional formula, seeking the formula of being true or false, and solve practical problems.Keywords:principal normal form; truth table; true value assignment method; equival
6、ent calculating method. z.-目 录摘 要IABSTRACTII目 录III1 引言12 预备知识23 主式的求法43.1真值表法43.2真值指派法63.3 等值演算法84 主式的应用124.1求公式的成真成假赋124.2 判断公式是否等值124.3 判断公式的类型134.4 解决实际问题154 小结17参考文献18致 19. z.-1 引言主式即主析取式与主合取式，它是离散数学数理逻辑的一个重要分支并是计算机科学根底的必备知识,它与计算机有着不可分割的关系.在计算机科学的操作系统、数据构造、算法分析、编译系统、系统构造、逻辑构造等都含有主式的知识.随着计算机科学对人们
7、的生活越来越重要，数理逻辑支撑学科的迅速开展，而主式理论及应用是数理逻辑重要的概念之一，其方法和应用也颇具价值.式分为合取式与析取式，而合取式与析取式在命题公式中不唯一，为使命题公式的式唯一即析取式与合取式进展规化，化成命题公式的主合取式与主析取式.本文主要介绍主式的三种方法等值演算法、真值指派法、真值表法.利用真值表法可以快速，有效的得到主式；真值指派法适合一些特殊的式得到主式，这两种方法都可以防止传统算法中较复杂的等值演算法.利用主式可以求公式的成真成假赋值、判断公式的类型、几个公式的等值、在实际问题上也有一些具体应用，并给出相应例子加深理解主式的方法和应用. z.-2 预备知识定义2.1
8、1在一公式中，仅由命题变元及否认构成的析取式(合取式，称该公式为简单析取式(简单合取式，其中每个命题变元或其否认，称为析取项(合取项).定义2.21一个命题公式称为合取式(析取式)，当且仅当可表示为简单析取式的合取(简单合取式的析取)，即；其中为简单析取式(简单合取式).定义2.32 在含有个命题变项的简单析取式(简单合取式)中,假设每个命题变项和它的否认式不同时出现,而二者之一必出现且反出现一次,且第个命题变项或它的否认式出现从左算起的第位上(假设命题变项无角标，就按字典顺序排列).称这样的简单析取式(简单合取式)为极大项(极小项).用表示极小项, 表示表示极大项，以,三个命题变元为列，见下
9、表2-1,2-2. 表2-1 使相应公式为真的极小项极小项二进制十进制00000101001110010111011101234567. z.- 表2-2 使相应公式为假的极大项极大项二进制十进制00000101001110010111011101234567性质 2.13 个命题变元可构成个极大(小)项.性质 2.23 全体极大(小)项的合(析)取式永为0(1).性质2.33 任意两个极大(小)项的析(合)取式永为1(0),即时，.性质2.43每个极大(小)项当其真值指派与编码一样时，其真值为0(1)，其余种指派情况下均为1(0).定义2.42 由不同极大(小)项组出的合取(析取)式称为主合
10、(析)取式.3 主式的求法由于主式是由极大项或极小项构成，从极大项和极小项的定义，可知： 因此，主合取式和主析取式有着“互补关系4.设命题公式中含有个命题变元，且的主析取式中含有个小项，则的主析取式中必含有其余的个小项，不妨含为，即于是. 故由给定公式的主析取式可以求出主合取式.本文主要给出求主析取式的三种方法：等值演算法、真值指派法、真值表法.3.1真值表法公式在全部可能的真值指派所取的真值表，称为真值表3.真值表由表的 左局部列出公式的每一种解释，右局部给出相应每种解释公式得到的真值. 假设真值用0和1表示真和假，则对公式中个不同命题变元的个解释，可按为二进数从小到大或从大到小次序表示出来
11、，假设公式有2个命题变元，它便有个解释，写成相应的二进制数为00、01、10、11. 命题公式真值表的构造步骤如下： (1) 命题变元按字典序列排列； (2) 对公式的每个解释，以二进制数从小到大或从从大到小顺序列出；(3) 假设公式复杂，可先列出各子公式的真值(假设有括号，则应从里层向外层展开)，最后列出所得公式的真值.真值表法求主式的步骤如下：(1)写出相应的真值表； (2)列出真值为1的极小项进展析取得到主析取式；(3)列出真值为0的极小项，通过“互补得到相应的极大项进展合取为主合取式.例3.1求命题公式的主式.解由题意,使用真值表可得,表3-1 使相应公式为真的极小项 01234567
12、0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 00 1 00 0 00 1 10 0 00 0 01 0 01 0 101010011其真值为1的极小项为故主析取式： 由真值为0的极小项通过主式的“互补得到相应的极大项为故主合取式：例3.2求命题公式的主式.解由题意,使用真值表可得,表3-2 使相应公式为真的极小项012345670 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111100110 11 10 11 11 11 00 11 101011001其真值为1的极小项为则主析取式: 其真值为0的极小项通过主式的“互补所得极大项为则主合取式: 3.2真值指派法 设为含有命题变元的命题公式，给一组确定的取值，称做公式关于的一组真值指派3.其真值用1和0表示真和假. 真值指派法求主析取式构造步骤如下： (1)把命题公式化为析取式； (2)析取式中每一项假设是极小项，则分别取二进制数；假设含有不是极小项，进展补项，再分别取二进制数.如三个元，析取式补项取真值指派为(1,1,1),(1,1,0)；(3)假设有一样的指派进展合并，写出每个指派的极小项进展析取，则得到主析取式.例3.32 求命题公式的主式.解 由
