本文關(guān)鍵詞：基于有向超圖的命題邏輯合取范式的約簡

  更多相關(guān)文章： 命題邏輯 合取范式 有向超圖 霍恩公式 冗余對象 約簡運算

【摘要】：在知識表示和自動推理領(lǐng)域,命題邏輯是一種極其重要的形式化語言,其中命題邏輯可滿足性問題是研究最廣泛的核心問題之一,約簡命題邏輯公式是由SAT問題衍生的一個子問題。有向超圖作為普通有向圖的推廣,能夠恰當?shù)乇硎敬笮统W(wǎng)絡(luò)、數(shù)據(jù)庫系統(tǒng)、命題邏輯等研究課題和研究領(lǐng)域中各元素之間的關(guān)系。以有向超圖作為工具是眾多的命題邏輯公式約簡方法中的一種。本文基于命題邏輯和有向超圖的相關(guān)知識、特別是近期的相關(guān)研究工作,主要取得了如下研究結(jié)果：1、針對命題邏輯中一般的合取范式給出了與之一一對應(yīng)的關(guān)聯(lián)有向超圖的定義,給出一種新的超路徑表示方式,得到了刻畫兩個子句和兩條超邊之間的一些基本關(guān)系的等價命題和性質(zhì),為進一步利用有向超圖尋找并約簡具有特定的冗余結(jié)構(gòu)的公式奠定了理論基礎(chǔ)。2、通過定義擴展B-圖來表示霍恩公式,得到了其可滿足性的若干結(jié)論及其約簡性質(zhì),為進一步約簡特定結(jié)構(gòu)的一般公式奠定了基礎(chǔ)。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é)子句,提出了相應(yīng)的約簡運算,即弱尾約簡、擴展的平行約簡、強超邊約簡、強超路徑約簡、強連續(xù)約簡,并輔以實例說明五種約簡運算的正確性和有效性。
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O141;O157.5

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 齊冬冬;;淺談命題邏輯[J];學(xué)理論;2010年31期

2 唐金文;解析命題符號化[J];曲靖師范學(xué)院學(xué)報;2002年06期

3 李建湘,鄧康,湯四平;命題邏輯中的蘊涵置換法[J];數(shù)學(xué)理論與應(yīng)用;2003年04期

4 徐鳳生;命題邏輯中的集合表示[J];計算機與現(xiàn)代化;2005年05期

5 李剛;李春;;命題邏輯簡化功能的應(yīng)用[J];科技信息(學(xué)術(shù)研究);2007年04期

6 李立峰;張東曉;;概念格在二值命題邏輯命題集約簡中的應(yīng)用[J];電子學(xué)報;2007年08期

7 任燕;王洪濤;;二值命題邏輯中的極大命題集與完備命題集[J];模糊系統(tǒng)與數(shù)學(xué);2009年03期

8 金樊;;推理有效性的判定方法及其特點比較——以命題邏輯為例[J];長春工程學(xué)院學(xué)報(社會科學(xué)版);2010年02期

9 張勝禮;;中介命題邏輯一種改進的無窮值語義模型[J];興義民族師范學(xué)院學(xué)報;2011年01期

10 陳敬華;胡松林;;關(guān)于命題邏輯中兩個問題的思考[J];湖北師范學(xué)院學(xué)報(自然科學(xué)版);2011年04期

中國重要會議論文全文數(shù)據(jù)庫 前9條

1 陳國勛;陳斌;;F-時態(tài)命題邏輯中的歸結(jié)原理[A];模糊數(shù)學(xué)和系統(tǒng)成果會論文集[C];1991年

2 任燕;王洪濤;;二值命題邏輯中的極大命題集與完備命題集[A];第六屆中國不確定系統(tǒng)年會論文集[C];2008年

3 賴家俊;潘小東;徐開俊;徐揚;;基于十八元非鏈格值命題邏輯L_(18)P(X)中的歸結(jié)方法的研究[A];第六屆中國不確定系統(tǒng)年會論文集[C];2008年

4 吳堅;;關(guān)于假言命題的真假問題的思考[A];1998年邏輯研究專輯[C];1998年

5 張家鋒;徐揚;;格值命題邏輯LP(X)中的語義歸結(jié)方法[A];中國運籌學(xué)會模糊信息與模糊工程分會第五屆學(xué)術(shù)年會論文集[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];邏輯學(xué)文集[C];1978年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 佟芳;首屆生命基因高峰論壇舉行[N];科技日報;2009年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 王偉;格值命題邏輯系統(tǒng)LP（X）中基于α-歸結(jié)原理的自動推理方法的研究[D];西南交通大學(xué);2002年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 鄧鵬;命題邏輯中子句集的分類研究[D];西南交通大學(xué);2015年

2 張志佳;基于有向超圖的命題邏輯合取范式的約簡[D];西南交通大學(xué);2016年

3 高菲菲;多值命題邏輯中若干邏輯理論的拓撲刻畫[D];陜西師范大學(xué);2008年

4 劉小山;基本命題邏輯的模態(tài)擴張[D];西南大學(xué);2014年

5 侯麗平;基本命題邏輯模型類的可定義性研究[D];西南大學(xué);2015年

6 黃沖;組合優(yōu)化中的命題邏輯[D];華中科技大學(xué);2011年

7 宋慶燕;命題邏輯公式集上的正則相似關(guān)系和一種新型的三I算法[D];陜西師范大學(xué);2003年

8 鄧富喜;n值S-MTL命題邏輯系統(tǒng)中的近似推理理論及三I算法的還原性[D];蘭州理工大學(xué);2011年

9 李彩紅;命題邏輯中廣義MP問題的合理解及新型反向三I算法[D];蘭州理工大學(xué);2011年

10 任燕;命題集的相容性、根及發(fā)散性[D];陜西師范大學(xué);2004年

，

本文編號：1149744