謂詞邏輯基礎(chǔ)-文庫吧
2025-07-17 14:24 本頁面
【正文】 謂詞邏輯歸結(jié)原理 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 量詞消去原則： 消去存在量詞 “ ?” ，略去全程量詞“ ?” 。 注意： 左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)；如沒有，改寫成為常量。 謂詞邏輯歸結(jié)原理 ? ? ? ? ? ? ? ? ? ? ? ? ? ? Skolem定理 ： 謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。 ? SKOLEM標(biāo)準(zhǔn)形定義： 消去量詞后的謂詞公式。 注意 ：謂詞公式 G的 SKOLEM標(biāo)準(zhǔn)形同 G并不等值 。 謂詞邏輯歸結(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)) ? 子句與子句集 ? 文字：不含任何連接詞的謂詞公式 。 ? 子句：一些文字的析取 （ 謂詞的和 ） 。 ? 子句集 S的求?。? G → SKOLEM 標(biāo)準(zhǔn)形 → 消去存在變量 → 以 “ ， ” 取代 “ ∧ ” ，并表示為集合形式 。 謂詞邏輯歸結(jié)原理 ? G是不可滿足的 = S是不可滿足的 ? G與 S不等價，但在不可滿足得意義下是一致的。 ? 定理： 若 G是給定的公式，而 S是相應(yīng)的子句集，則 G是不可滿足的 = S是不可滿足的。 注意 ： G真不一定 S真，而 S真必有 G真。 即： S = G 謂詞邏輯歸結(jié)原理 ? G = G1Λ G 2Λ G 3Λ … Λ G n 的子句形 ? G的字句集可以分解成幾個單獨處理。 ? 有 SG = S1 U S2 U S3 U … U Sn 則 SG 與 S1 U S2 U S3 U … U Sn在不可滿足得意義上是一致的 。 即 SG 不可滿足 = S1 U S2 U S3 U … U Sn不可滿足 謂詞邏輯歸結(jié)原理 例：對所有的 x,y,z來說 ， 如果 y是 x的父親 ， z又是 y的父親 ， 則 z是 x的祖父 。 又知每個人都有父親 ， 試問對某個人來說誰是它的祖父 ？ 求：用一階邏輯表示這個問題 ， 并建立子句集 。 解：這里我們首先引入謂詞： ? P(x, y) 表示 x是 y的父親 ? Q(x, y) 表示 x是 y的祖父 ? ANS(x) 表示問題的解答 謂詞邏輯歸結(jié)原理 對于第一個條件 ， “
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1