基于有向超图的命题逻辑合取范式的约简

发布时间：2017-11-06 23:01

  本文关键词：基于有向超图的命题逻辑合取范式的约简

  更多相关文章： 命题逻辑 合取范式 有向超图 霍恩公式 冗余对象 约简运算

【摘要】：在知识表示和自动推理领域,命题逻辑是一种极其重要的形式化语言,其中命题逻辑可满足性问题是研究最广泛的核心问题之一,约简命题逻辑公式是由SAT问题衍生的一个子问题。有向超图作为普通有向图的推广,能够恰当地表示大型超网络、数据库系统、命题逻辑等研究课题和研究领域中各元素之间的关系。以有向超图作为工具是众多的命题逻辑公式约简方法中的一种。本文基于命题逻辑和有向超图的相关知识、特别是近期的相关研究工作,主要取得了如下研究结果：1、针对命题逻辑中一般的合取范式给出了与之一一对应的关联有向超图的定义,给出一种新的超路径表示方式,得到了刻画两个子句和两条超边之间的一些基本关系的等价命题和性质,为进一步利用有向超图寻找并约简具有特定的冗余结构的公式奠定了理论基础。2、通过定义扩展B-图来表示霍恩公式,得到了其可满足性的若干结论及其约简性质,为进一步约简特定结构的一般公式奠定了基础。3、将命题逻辑中的冗余对象分为绝对冗余变元、自归入子句、强归结子句这三类。根据两个子句归结的特点又将强归结子句分为具有R1,R2,R3结构的子句。通过研究上述冗余对象和冗余结构,得到了其约简性质,进一步在理论上证明了约简的合理性。4、针对命题逻辑中五种冗余结构：绝对冗余变元、自归入子句、具有R1,R2,R3结构的强归结子句,提出了相应的约简运算,即弱尾约简、扩展的平行约简、强超边约简、强超路径约简、强连续约简,并辅以实例说明五种约简运算的正确性和有效性。
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O141;O157.5

【相似文献】

中国期刊全文数据库 前10条

1 齐冬冬;;浅谈命题逻辑[J];学理论;2010年31期

2 唐金文;解析命题符号化[J];曲靖师范学院学报;2002年06期

3 李建湘,邓康,汤四平;命题逻辑中的蕴涵置换法[J];数学理论与应用;2003年04期

4 徐凤生;命题逻辑中的集合表示[J];计算机与现代化;2005年05期

5 李刚;李春;;命题逻辑简化功能的应用[J];科技信息(学术研究);2007年04期

6 李立峰;张东晓;;概念格在二值命题逻辑命题集约简中的应用[J];电子学报;2007年08期

7 任燕;王洪涛;;二值命题逻辑中的极大命题集与完备命题集[J];模糊系统与数学;2009年03期

8 金樊;;推理有效性的判定方法及其特点比较——以命题逻辑为例[J];长春工程学院学报(社会科学版);2010年02期

9 张胜礼;;中介命题逻辑一种改进的无穷值语义模型[J];兴义民族师范学院学报;2011年01期

10 陈敬华;胡松林;;关于命题逻辑中两个问题的思考[J];湖北师范学院学报(自然科学版);2011年04期

中国重要会议论文全文数据库 前9条

1 陈国勋;陈斌;;F-时态命题逻辑中的归结原理[A];模糊数学和系统成果会论文集[C];1991年

2 任燕;王洪涛;;二值命题逻辑中的极大命题集与完备命题集[A];第六届中国不确定系统年会论文集[C];2008年

3 赖家俊;潘小东;徐开俊;徐扬;;基于十八元非链格值命题逻辑L_(18)P(X)中的归结方法的研究[A];第六届中国不确定系统年会论文集[C];2008年

4 吴坚;;关于假言命题的真假问题的思考[A];1998年逻辑研究专辑[C];1998年

5 张家锋;徐扬;;格值命题逻辑LP(X)中的语义归结方法[A];中国运筹学会模糊信息与模糊工程分会第五届学术年会论文集[C];2010年

6 戴细华;;逻辑系统中的语义博弈[A];2007年现代逻辑与逻辑史研讨会论文集[C];2007年

7 许涤非;;二重命题逻辑系统■_(T4)[A];2001年逻辑研究专辑[C];2001年

8 张清宇;;极小的弗协调U、S时态命题逻辑[A];逻辑、语言与思维——周礼全先生八十寿辰纪念文集[C];2001年

9 莫绍揆;;传统逻辑与数理逻辑[A];逻辑学文集[C];1978年

中国重要报纸全文数据库 前1条

1 佟芳;首届生命基因高峰论坛举行[N];科技日报;2009年

中国博士学位论文全文数据库 前1条

1 王伟;格值命题逻辑系统LP（X）中基于α-归结原理的自动推理方法的研究[D];西南交通大学;2002年

中国硕士学位论文全文数据库 前10条

1 邓鹏;命题逻辑中子句集的分类研究[D];西南交通大学;2015年

2 张志佳;基于有向超图的命题逻辑合取范式的约简[D];西南交通大学;2016年

3 高菲菲;多值命题逻辑中若干逻辑理论的拓扑刻画[D];陕西师范大学;2008年

4 刘小山;基本命题逻辑的模态扩张[D];西南大学;2014年

5 侯丽平;基本命题逻辑模型类的可定义性研究[D];西南大学;2015年

6 黄冲;组合优化中的命题逻辑[D];华中科技大学;2011年

7 宋庆燕;命题逻辑公式集上的正则相似关系和一种新型的三I算法[D];陕西师范大学;2003年

8 邓富喜;n值S-MTL命题逻辑系统中的近似推理理论及三I算法的还原性[D];兰州理工大学;2011年

9 李彩红;命题逻辑中广义MP问题的合理解及新型反向三I算法[D];兰州理工大学;2011年

10 任燕;命题集的相容性、根及发散性[D];陕西师范大学;2004年

，

本文编号：1149744