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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 張家鋒;徐揚(yáng);;格值命題邏輯LP(X)中的語(yǔ)義歸結(jié)方法[A];中國(guó)運(yùn)籌學(xué)會(huì)模糊信息與模糊工程分會(huì)第五屆學(xué)術(shù)年會(huì)論文集[C];2010年

6 戴細(xì)華;;邏輯系統(tǒng)中的語(yǔ)義博弈[A];2007年現(xiàn)代邏輯與邏輯史研討會(huì)論文集[C];2007年

7 許滌非;;二重命題邏輯系統(tǒng)■_(T4)[A];2001年邏輯研究專輯[C];2001年

8 張清宇;;極小的弗協(xié)調(diào)U、S時(shí)態(tài)命題邏輯[A];邏輯、語(yǔ)言與思維——周禮全先生八十壽辰紀(jì)念文集[C];2001年

9 莫紹揆;;傳統(tǒng)邏輯與數(shù)理邏輯[A];邏輯學(xué)文集[C];1978年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

1 佟芳;首屆生命基因高峰論壇舉行[N];科技日?qǐng)?bào);2009年

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

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

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

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

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

3 高菲菲;多值命題邏輯中若干邏輯理論的拓?fù)淇坍媅D];陜西師范大學(xué);2008年

4 劉小山;基本命題邏輯的模態(tài)擴(kuò)張[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問(wèn)題的合理解及新型反向三I算法[D];蘭州理工大學(xué);2011年

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

，

本文編號(hào)：1149744