謂詞邏輯基礎(chǔ)-免費(fèi)閱讀
【正文】 謂詞邏輯歸結(jié)原理 如同單元?dú)w結(jié)策略，不是所有的可歸結(jié)謂詞公式的最后結(jié)論都是可以從原始子句集中的得到的。否則也可能事與愿違。 語義歸結(jié)策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以用采用語義歸結(jié)策略達(dá)到加快歸結(jié)速度的目的。 就是說 ， 至少有一個(gè)子句來自于支撐集 T或由 T導(dǎo)出的歸結(jié)式 。 這樣的推理過程便稱做使用了刪除策略的歸結(jié)過程 。 ※ Herbrand定理的不實(shí)用性引出了可實(shí)用的歸結(jié)法。 同時(shí)稱 F1，F(xiàn)2， ... ， Fn是可合一的 。?/xn, u1/y1, u2/y2, … , un/yn } 中刪去以下兩種元素： ? i. 當(dāng) ti?=xi時(shí) ， 刪去 ti?/xi (i = 1, 2, … , n)。 其中 ， x1, x2, … , xn是互不相同的變量 ， t1, t2, … , tn是不同于 xi的項(xiàng) （ 常量 、 變量 、 函數(shù) ） ； ti/xi表示用 ti置換 xi， 并且要求 ti與 xi不能相同 ， 而且 xi不能循環(huán)地出現(xiàn)在另一個(gè) ti中 。 ? 有 SG = S1 U S2 U S3 U … U Sn 則 SG 與 S1 U S2 U S3 U … U Sn在不可滿足得意義上是一致的 。 注意 ：謂詞公式 G的 SKOLEM標(biāo)準(zhǔn)形同 G并不等值 。 （ 2） ?x Q(x), 其中 Q(x)表示 x活到一百歲以上 。 ? 8是個(gè)自然數(shù) 。 謂詞邏輯基礎(chǔ) 謂詞邏輯基礎(chǔ) ? 例如： （ 1） 所有的人都是要死的 。 注意： 左邊有全程量詞的存在量詞，消去時(shí)該變量改寫成為全程量詞的函數(shù)；如沒有，改寫成為常量。 ? 定理： 若 G是給定的公式，而 S是相應(yīng)的子句集，則 G是不可滿足的 = S是不可滿足的。 ? 但由于有函數(shù)，所以要考慮 合一 和 置換 。 它是從集合 {t1最后得 ? ? 解：先將問題用謂詞表示如下： ? R1:“任何通過計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂的 ” (?x)((Pass(x, puter)∧ Win(x, prize))→Happy(x)) ? R2:“任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有考試 ” (?x)(?y)(Study(x)∨ Lucky(x)→Pass(x, y)) ? R3:“張不肯學(xué)習(xí)但他是幸運(yùn)的 ” ～ Study(zhang)∧ Lucky(zhang) ? R4:“任何幸運(yùn)的人都能獲獎(jiǎng) ” (?x)(Luck(x)→Win(x,prize)) ? 結(jié)論： “ 張是快樂的 ” 的否定 ～ Happy(zhang) 例題 “快樂學(xué)生”問題 ? 由 R1及邏輯轉(zhuǎn)換公式 :P∧ W→H = ～ （ P∧ W） ∨ H ， 可得 ? (1)～ Pass(x, puter)∨ ～ Win(x, prize)∨ Happy(x) ? 由 R2： (2)～ Study(y)∨ Pass(y,z) ? (3)～ Lucky(u)∨ Pass(u,v) ? 由 R3： (4)～ Study(zhang) ? (5)Lucky(zhang) ? 由 R4： (6)～ Lucky(w)∨ Win(w， prize) ? 由結(jié)論： (7)～ Happy(zhang) （ 結(jié)論的否定 ） ? (8)～ Pass(w, puter)∨ Happy(w)∨ ～ Luck(w) (1)(6)， {w/x} ? (9)～ Pass(zhang, puter)∨ ～ Lucky(zhang) (8)(7)， {zhang/w} ? (10) ～ Pass(zhang, puter) (9)(5) ? (11) ～ Lucky(zhang) (10)(3)， {zhang/u, puter/v} ? (12) ? ? (11)(5) ? 歸結(jié)法的實(shí)質(zhì)： ? 歸結(jié)法是僅有一條
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1