謂詞邏輯基礎(chǔ)-展示頁
2024-08-16 14:24本頁面
【正文】 y)∨ ANS(x) 則得到的相應(yīng)的子句集為： { S A1， S A2， S～ B } 謂詞邏輯歸結(jié)原理 ? 歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。 即 SG 不可滿足 = S1 U S2 U S3 U … U Sn不可滿足 謂詞邏輯歸結(jié)原理 例：對所有的 x,y,z來說 ， 如果 y是 x的父親 ， z又是 y的父親 ， 則 z是 x的祖父 。 即： S = G 謂詞邏輯歸結(jié)原理 ? G = G1Λ G 2Λ G 3Λ … Λ G n 的子句形 ? G的字句集可以分解成幾個單獨處理。 ? 定理： 若 G是給定的公式，而 S是相應(yīng)的子句集，則 G是不可滿足的 = S是不可滿足的。 ? 子句集 S的求?。? G → SKOLEM 標(biāo)準(zhǔn)形 → 消去存在變量 → 以 “ ， ” 取代 “ ∧ ” ，并表示為集合形式 。 謂詞邏輯歸結(jié)原理 例： 將下式化為 Skolem標(biāo)準(zhǔn)形： ～ (?x)(?y)P(a, x, y) → (?x)(～ (?y)Q(y, b)→ R(x)) ? 解：第一步 ， 消去 → 號 ， 得： ～ (～ (?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)， 因為它左邊只有 (?x)， 所以使用 x的函數(shù)f(x)代替之 ， 這樣得到： (?x)(?u)(?v) (P(a, x, f(x)) ∨ Q(v, b)∨ R(u)) ? 消去 (?u)，同理使用 g(x)代替之，這樣得到： (?x) (?v) ( P(a, x, f(x)) ∨ Q(v, b) ∨ R(g(x))) ? 則 ， 略去全稱變量 ， 原式的 Skolem標(biāo)準(zhǔn)形為： P(a, x, f(x)) ∨ Q(v, b) ∨ R(g(x)) ? 子句與子句集 ? 文字：不含任何連接詞的謂詞公式 。 ? SKOLEM標(biāo)準(zhǔn)形定義： 消去量詞后的謂詞公式。 注意： 左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)；如沒有，改寫成為常量。 一階邏輯 ? 公式及其解釋 ? 個體常量： a,b,c ? 個體變量： x,y,z ? 謂詞符號： P,Q,R ? 量詞符號： ? ,? 謂詞邏輯基礎(chǔ) 量詞否定等值式： ? ～ (? x ） P（ x） = （ ? y ） ～ P（ y） ? ～ (? x ） P（ x） = （ ? y ） ～ P（ y） 量詞分配等值式： ? (? x ） ( P（ x） ∧ Q（ x） ) = (? x ） P（ x） ∧ (? x ） Q（ x） ? (? x ） ( P（ x） ∨ Q（ x） ) = (? x ） P（ x） ∨ (? x ） Q（ x） 消去量詞等值式： 設(shè)個體域為有窮集合（ a1, a2, … an） ? (? x ） P（ x） = P（ a1 ） ∧ P（ a2 ） ∧ … ∧ P（ an ） ? (? x ） P（ x） = P（ a1 ） ∨ P（ a2 ） ∨ … ∨ P（ an ） 謂詞邏輯基礎(chǔ) 量詞轄域收縮與擴(kuò)張等值式： ? (? x ） ( P（ x） ∨ Q) = (? x ） P（ x） ∨ Q ? (? x ） ( P（ x） ∧ Q
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1