謂詞邏輯基礎(chǔ)-資料下載頁(yè)
2025-08-01 14:24本頁(yè)面
【正文】 便將 Cj刪除 。 這樣的推理過(guò)程便稱(chēng)做使用了刪除策略的歸結(jié)過(guò)程 。 謂詞邏輯歸結(jié)原理 ? 主要思想：歸結(jié)過(guò)程在尋找可歸結(jié)子句時(shí) ， 子句集中的子句越多 ， 需要付出的代價(jià)就會(huì)越大 。如果在歸結(jié)時(shí)能把子句集中無(wú)用的子句刪除掉 ，就會(huì)縮小搜索范圍 ， 減少比較次數(shù) ， 從而提高歸結(jié)效率 。 刪除策略對(duì)阻止不必要的歸結(jié)式的產(chǎn)生來(lái)縮短歸結(jié)過(guò)程是有效的 。 然而要在歸結(jié)式 Cj產(chǎn)生后方能判別它是否可被刪除 ， 這部分計(jì)算量是要花費(fèi)的 ， 只是節(jié)省了被刪除的子句又生成的歸結(jié)式 。 盡管使用刪除策略的歸結(jié) ，少做了歸結(jié)但不影響產(chǎn)生空子句 ， 就是說(shuō)刪除策略的歸結(jié)推理是完備的 。 謂詞邏輯歸結(jié)原理 采用支撐集 =完備 支撐集：設(shè)有不可滿(mǎn)足子句集 S的子集 T， 如果 ST是可滿(mǎn)足的 ， 則 T是支持集 。 采用支撐集策略時(shí) ， 從開(kāi)始到得到 ?的整個(gè)歸結(jié)過(guò)程中 ， 只選取不同時(shí)屬于 ST的子句 ，在其間進(jìn)行歸結(jié) 。 就是說(shuō) ， 至少有一個(gè)子句來(lái)自于支撐集 T或由 T導(dǎo)出的歸結(jié)式 。 謂詞邏輯歸結(jié)原理 例如： A1ΛA 2ΛA 3Λ ～ B中的～ B可以作為支撐集使用 。要求每一次參加歸結(jié)的親本子句中 ， 只要應(yīng)該有一個(gè)是有目標(biāo)公式的否定 （ ～ B） 所得到的子句或者它們的后裔 。 ? 支撐集策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以用采用支撐集策略達(dá)到加快歸結(jié)速度的目的。問(wèn)題是如何尋找合適的支撐集。一個(gè)最容易找到的支撐集是目標(biāo)子句的非，即 S～ B。 謂詞邏輯歸結(jié)原理 S T 可滿(mǎn)足 支撐集示意圖 謂詞邏輯歸結(jié)原理 語(yǔ)義歸結(jié) = 完備 語(yǔ)義歸結(jié)策略是將子句 S按照一定的語(yǔ)義分成兩部分 ， 約定每部分內(nèi)的子句間不允許作歸結(jié) 。 同時(shí)還引入了文字次序 ， 約定歸結(jié)時(shí)其中的一個(gè)子句的被歸結(jié)文字只能是該子句中 “ 最大 ” 的文字 。 語(yǔ)義歸結(jié)策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以用采用語(yǔ)義歸結(jié)策略達(dá)到加快歸結(jié)速度的目的。問(wèn)題是如何尋找合適的語(yǔ)義分類(lèi)方法，并根據(jù)其含義將子句集兩個(gè)部分中的子句進(jìn)行排序。 謂詞邏輯歸結(jié)原理 線性歸結(jié) =完備 線性歸結(jié)策略首先從子句集中選取一個(gè)稱(chēng)作頂子句的子句 C0開(kāi)始作歸結(jié)。歸結(jié)過(guò)程中所得到的歸結(jié)式 Ci立即同另一子句 Bi進(jìn)行歸結(jié)得歸結(jié)式 Ci+1。而B(niǎo)i屬于 S或是已出現(xiàn)的歸結(jié)式 Cj(ji)。即，如下圖所示歸結(jié)得到的新子句立即參加歸結(jié)。 線性歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以采用線性歸結(jié)策略達(dá)到加快歸結(jié)速度的目的。如果能搞找到一個(gè)較好的頂子句，可以式歸結(jié)順利進(jìn)行。否則也可能事與愿違。 謂詞邏輯歸結(jié)原理 C0 C1 C2 C3 C4 C5 空 線性歸結(jié)策略示意圖 謂詞邏輯歸結(jié)原理 單元?dú)w結(jié) = 完備 單元?dú)w結(jié)策略要求在歸結(jié)過(guò)程中 ， 每次歸結(jié)都有一個(gè)子句是單元子句 （ 只含一個(gè)文字的子句 ）或單元因子 。 顯而易見(jiàn) ， 詞中方法可以簡(jiǎn)單地削去另一個(gè)非單子句中的一個(gè)因子 ， 使其長(zhǎng)度減少 ，構(gòu)成簡(jiǎn)單化 ， 歸結(jié)效率較高 。 初始子句集中沒(méi)有單元子句時(shí)，單元?dú)w結(jié)策略無(wú)效。所以說(shuō) “ 反之不成立 ” ，即此問(wèn)題不能采用單元?dú)w結(jié)策略 。 謂詞邏輯歸結(jié)原理 輸入歸結(jié) = 完備 與單元?dú)w結(jié)策略相似 ， 輸入歸結(jié)策略要求在歸結(jié)過(guò)程中 ， 每一次歸結(jié)的兩個(gè)子句中必須有一個(gè)是 S的原始子句 。 這樣可以避免歸結(jié)出的不必要的新子句加入歸結(jié) ， 造成惡性循環(huán) 。 可以減少不必要的歸結(jié)次數(shù) 。 謂詞邏輯歸結(jié)原理 如同單元?dú)w結(jié)策略，不是所有的可歸結(jié)謂詞公式的最后結(jié)論都是可以從原始子句集中的得到的。簡(jiǎn)單的例子，歸結(jié)結(jié)束時(shí)，即最后一個(gè)歸結(jié)式為空子句的條件是，參加歸結(jié)的雙方必須是兩個(gè)單元子句。原始子句集中沒(méi)有單元子句的謂詞公式一定不能采用輸入歸結(jié)策略。 謂詞邏輯歸結(jié)原理
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1