一种求解前束析(合)取范式的简单方法

《一种求解前束析(合)取范式的简单方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、CN43—1258／TP计算机工程与科学2008年第3O卷第1O期ISSN1007—130XCOMPUTERENGINEERING&SCIENCEVo1．30，No．10，2008文章编号：1007—130X(2008)10—0082-03一种求解前束析(合)取范式的简单方法ASimpleMethodforSolvingPrenexDisjuncti0n(Conjunction)NormalForms潘美芹。丁志军PANMei-qin，DINGZhHnil(山东科技大学信息科学与工程学院。山东青岛266510)(SchoolofInforma

2、tionScienceandEngineering，ShandongUniversityofScienceandTechnology，Qingdao266510，China)摘要：本文提出了一种由前柬析(合)取范式求前束合(析)取范式的简单方法。该方法根据谓词逻辑自身的特点，结合命题逻辑中命题公式的主析取范式和主合取范式的互补关系，将前束析(合)取范式转化为主析(合)取范式，再得出相应的主合(析)取范式，最后准确地得出前柬合(析)取范式。Abstract：Thispaperproposesasimplemethodforsolvingpren

3、exdisjunction(conjunction)normalforms，whichisbasedonthepredicatelogic’Scharacteristicsandthemutual-complementaryrelationsofthemajordisjunctionnormalformandthemajorconjunctionnormalform．Itchangestheprenexdisjunction(conjunction)norrrlalformintothemajordisjunc-tion(conjunctio

4、n)normalform，andthengetsthemajorconjunction(disjunction)normalform，andfinallygetstheprenexconjunction(disjunction)normalforr~关键词：数理逻辑；谓词逻辑；范式；前束范式Keywords：propositionallogic；predicatelogic；normalform；prenexnormalform中图分类号：O158文献标识码：A1引言2主析取范式和主合取范式离散数学是随着计算机的发展而逐渐完善起来的一门在命题

5、逻辑中，同一命题公式有各种相互等价的表达新兴学科，它是计算机专业的一门重要基础课。学生对这门形式。为了规范命题公式，故有范式的概念，而范式又分为课程对掌握的好坏，直接影响到后继专业课程的学习以及将析取范式和合取范式。对于任何一命题公式，都存在与其来在专业上的发展。由于离散数学和传统数学在基本思想等价的析取范式和合取范式。然而，命题公式的合取范式和方法上有很大差别，学生在学习这门课程时普遍存在很多和析取范式是不唯一的。为进一步规范化命题公式，引进困难。在我们所选的教材中(绝大部分教材都如此)，数理逻了主析取范式和主合取范式。主析取范式是由小项的

6、析取辑安排在第_篇，它的概念很抽象，逻辑性强，而其中的谓词构成，主合取范式是由大项的合取构成，从小项和大项的定逻辑更是难点。由于谓词逻辑中的前束范式中通常有多个义可知，主析取范式和主合取范式有着“互补”关系。见例量词，而且量词的作用域中又涉及多个命题函数，学生做前1，公式(P^Q)V(一P^R)的真值表如表1所示，公式束析取范式和前束合取范式的练习时往往无从下手，并且稍含三个命题变元，故真值表中有八种指派，表中画线对应的有不慎就会得出错误的结果。事实上，根据谓词逻辑自身的是主合取范式的四个大项，其余部分对应的是主析取范式特点，结合命题逻辑中命

7、题公式的主析取范式和主合取范式的四个小项。根据这个特点，当用公式化归法求解出某一的互补关系，在求出前束析取范式时，遵循我们的简单方法，公式的主析取范式时，利用互补性，马上可得到其主合取范会准确地得出前束合取范式，反之亦然。式，反之亦然。·收稿日期：2008-03-1I；修订日期：2008-04—29基金项目：国家自然科学基金资助项目(10571109)作者简介：潘美芹(1972～)，女，浙江仙居人，博士生，副教授，研究方向为离散数学的教学及非线性优化方法、遗传算法和数据挖掘等通讯地址：266510山东省青岛市山东科技大学信息科学与工程学院Ad

8、dress：SchoolofInformationScienceandEngineering，ShandongUniversityofScienceandTechn