基于有向超圖的命題邏輯合取范式的約簡
本文關鍵詞:基于有向超圖的命題邏輯合取范式的約簡
更多相關文章: 命題邏輯 合取范式 有向超圖 霍恩公式 冗余對象 約簡運算
【摘要】:在知識表示和自動推理領域,命題邏輯是一種極其重要的形式化語言,其中命題邏輯可滿足性問題是研究最廣泛的核心問題之一,約簡命題邏輯公式是由SAT問題衍生的一個子問題。有向超圖作為普通有向圖的推廣,能夠恰當?shù)乇硎敬笮统W(wǎng)絡、數(shù)據(jù)庫系統(tǒng)、命題邏輯等研究課題和研究領域中各元素之間的關系。以有向超圖作為工具是眾多的命題邏輯公式約簡方法中的一種。本文基于命題邏輯和有向超圖的相關知識、特別是近期的相關研究工作,主要取得了如下研究結(jié)果:1、針對命題邏輯中一般的合取范式給出了與之一一對應的關聯(lián)有向超圖的定義,給出一種新的超路徑表示方式,得到了刻畫兩個子句和兩條超邊之間的一些基本關系的等價命題和性質(zhì),為進一步利用有向超圖尋找并約簡具有特定的冗余結(jié)構(gòu)的公式奠定了理論基礎。2、通過定義擴展B-圖來表示霍恩公式,得到了其可滿足性的若干結(jié)論及其約簡性質(zhì),為進一步約簡特定結(jié)構(gòu)的一般公式奠定了基礎。3、將命題邏輯中的冗余對象分為絕對冗余變元、自歸入子句、強歸結(jié)子句這三類。根據(jù)兩個子句歸結(jié)的特點又將強歸結(jié)子句分為具有R1,R2,R3結(jié)構(gòu)的子句。通過研究上述冗余對象和冗余結(jié)構(gòu),得到了其約簡性質(zhì),進一步在理論上證明了約簡的合理性。4、針對命題邏輯中五種冗余結(jié)構(gòu):絕對冗余變元、自歸入子句、具有R1,R2,R3結(jié)構(gòu)的強歸結(jié)子句,提出了相應的約簡運算,即弱尾約簡、擴展的平行約簡、強超邊約簡、強超路徑約簡、強連續(xù)約簡,并輔以實例說明五種約簡運算的正確性和有效性。
【學位授予單位】:西南交通大學
【學位級別】:碩士
【學位授予年份】:2016
【分類號】:O141;O157.5
【相似文獻】
中國期刊全文數(shù)據(jù)庫 前10條
1 齊冬冬;;淺談命題邏輯[J];學理論;2010年31期
2 唐金文;解析命題符號化[J];曲靖師范學院學報;2002年06期
3 李建湘,鄧康,湯四平;命題邏輯中的蘊涵置換法[J];數(shù)學理論與應用;2003年04期
4 徐鳳生;命題邏輯中的集合表示[J];計算機與現(xiàn)代化;2005年05期
5 李剛;李春;;命題邏輯簡化功能的應用[J];科技信息(學術研究);2007年04期
6 李立峰;張東曉;;概念格在二值命題邏輯命題集約簡中的應用[J];電子學報;2007年08期
7 任燕;王洪濤;;二值命題邏輯中的極大命題集與完備命題集[J];模糊系統(tǒng)與數(shù)學;2009年03期
8 金樊;;推理有效性的判定方法及其特點比較——以命題邏輯為例[J];長春工程學院學報(社會科學版);2010年02期
9 張勝禮;;中介命題邏輯一種改進的無窮值語義模型[J];興義民族師范學院學報;2011年01期
10 陳敬華;胡松林;;關于命題邏輯中兩個問題的思考[J];湖北師范學院學報(自然科學版);2011年04期
中國重要會議論文全文數(shù)據(jù)庫 前9條
1 陳國勛;陳斌;;F-時態(tài)命題邏輯中的歸結(jié)原理[A];模糊數(shù)學和系統(tǒng)成果會論文集[C];1991年
2 任燕;王洪濤;;二值命題邏輯中的極大命題集與完備命題集[A];第六屆中國不確定系統(tǒng)年會論文集[C];2008年
3 賴家俊;潘小東;徐開俊;徐揚;;基于十八元非鏈格值命題邏輯L_(18)P(X)中的歸結(jié)方法的研究[A];第六屆中國不確定系統(tǒng)年會論文集[C];2008年
4 吳堅;;關于假言命題的真假問題的思考[A];1998年邏輯研究專輯[C];1998年
5 張家鋒;徐揚;;格值命題邏輯LP(X)中的語義歸結(jié)方法[A];中國運籌學會模糊信息與模糊工程分會第五屆學術年會論文集[C];2010年
6 戴細華;;邏輯系統(tǒng)中的語義博弈[A];2007年現(xiàn)代邏輯與邏輯史研討會論文集[C];2007年
7 許滌非;;二重命題邏輯系統(tǒng)■_(T4)[A];2001年邏輯研究專輯[C];2001年
8 張清宇;;極小的弗協(xié)調(diào)U、S時態(tài)命題邏輯[A];邏輯、語言與思維——周禮全先生八十壽辰紀念文集[C];2001年
9 莫紹揆;;傳統(tǒng)邏輯與數(shù)理邏輯[A];邏輯學文集[C];1978年
中國重要報紙全文數(shù)據(jù)庫 前1條
1 佟芳;首屆生命基因高峰論壇舉行[N];科技日報;2009年
中國博士學位論文全文數(shù)據(jù)庫 前1條
1 王偉;格值命題邏輯系統(tǒng)LP(X)中基于α-歸結(jié)原理的自動推理方法的研究[D];西南交通大學;2002年
中國碩士學位論文全文數(shù)據(jù)庫 前10條
1 鄧鵬;命題邏輯中子句集的分類研究[D];西南交通大學;2015年
2 張志佳;基于有向超圖的命題邏輯合取范式的約簡[D];西南交通大學;2016年
3 高菲菲;多值命題邏輯中若干邏輯理論的拓撲刻畫[D];陜西師范大學;2008年
4 劉小山;基本命題邏輯的模態(tài)擴張[D];西南大學;2014年
5 侯麗平;基本命題邏輯模型類的可定義性研究[D];西南大學;2015年
6 黃沖;組合優(yōu)化中的命題邏輯[D];華中科技大學;2011年
7 宋慶燕;命題邏輯公式集上的正則相似關系和一種新型的三I算法[D];陜西師范大學;2003年
8 鄧富喜;n值S-MTL命題邏輯系統(tǒng)中的近似推理理論及三I算法的還原性[D];蘭州理工大學;2011年
9 李彩紅;命題邏輯中廣義MP問題的合理解及新型反向三I算法[D];蘭州理工大學;2011年
10 任燕;命題集的相容性、根及發(fā)散性[D];陜西師范大學;2004年
,本文編號:1149744
本文鏈接:http://sikaile.net/kejilunwen/yysx/1149744.html