謂詞邏輯基礎(chǔ)-全文預(yù)覽
【正文】 的人都是快樂的 ” (?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é)法是僅有一條推理規(guī)則的推理方法。 ? 例： 設(shè)有公式集 F＝ {P(x, y, f(y)), P(a,g(x),z)}， 則 ?＝ {a/x, g(a)/y, f(g(a))/z}是它的一個(gè)合一 。最后得 ? ? Ii. 當(dāng) yi?{x1,x2, … , xn}時(shí) ， 刪去 uj/yj (j = 1, 2, … , m) 最后剩下的元素所構(gòu)成的集合。 它是從集合 {t1 例如 {a/x， c/y， f(b)/z}是一個(gè)置換 。 ? 但由于有函數(shù)，所以要考慮 合一 和 置換 。 即 SG 不可滿足 = S1 U S2 U S3 U … U Sn不可滿足 謂詞邏輯歸結(jié)原理 例：對所有的 x,y,z來說 ， 如果 y是 x的父親 ， z又是 y的父親 ， 則 z是 x的祖父 。 ? 定理： 若 G是給定的公式，而 S是相應(yīng)的子句集，則 G是不可滿足的 = S是不可滿足的。 謂詞邏輯歸結(jié)原理 例： 將下式化為 Skolem標(biāo)準(zhǔn)形： ～ (?x)(?y)P(a, x, y) → (?x)(～ (?y)Q(y, b)→ R(x)) ? 解：第一步 ， 消去 → 號(hào) ， 得： ～ (～ (?x)(?y)P(a, x, y)) ∨ (?x) (～～ (?y)Q(y, b)∨ R(x)) ? 第二步 ， ～深入到量詞內(nèi)部 ， 得： (?x)(?y)P(a, x, y) ∨( ?x) ((?y)Q(y, b)∨ R(x)) ? 第三步 ， 變元易名 ， 得 (?x)(?y)P(a, x, y) ∨ (?u) (? v)(Q(v, b) ∨ R(u)) ? 第四步 ， 存在量詞左移 ， 直至所有的量詞移到前面 ， (?x) (?y) (?u) (? v) (P(a, x, y) ∨ (Q(v, b) ∨ R(u)) 由此得到前述范式 ? 第五步 ， 消去 “ ?” （ 存在量詞 ） ， 略去 “ ?” 全稱量詞 ? 消去 (?y)， 因?yàn)樗筮呏挥?(?x)， 所以使用 x的函數(shù)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1