人工智能lesson3-(已修改)
2025-08-05 21:56 本頁面
【正文】 第三章 基于謂詞邏輯的機器推理 歸結(jié)演繹推理 定義 1 原子謂詞公式及其否定稱為文字；文字的析取式稱為子句； r個文字組成的子句稱為 r文字子句。 1文字子句也稱為單元子句。不含任何文字的子句稱為空子句，記為 或 NIL。由子句構(gòu)成的集合稱為子句集。 任何一個謂詞公式都可以化為子句集，步驟如下： （ 1）、利用等價式 A ? B ? ?A ?B 和 A ? B ? (A ? B) ?(B ? A)消去聯(lián)結(jié)詞“ ? ” 和 “ ? ”。 （ 2）、縮小否定聯(lián)結(jié)詞的作用范圍，使其僅作用于原子公式?？衫孟铝械葍r式： ? ? A ?A； ?(A?B) ? ? A ? ? B； ?(A ? B) ? ?A ??B； ??xA(x) ? ?x? A(x)； ??xA(x) ? ? x? A(x) （ 3）、重新命名變元名，使不同量詞約束的變元有不同的名字。 （ 4）、消去存在量詞。若存在量詞不在全稱量詞的轄域內(nèi)，則用一個常量符號替換該存在量詞轄域中的相應(yīng)約束變元。這樣的常量稱為Skolem常量；若該存在量詞在一個或多個全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變元的一個函數(shù)替換該存在量詞約束的變元。這樣的函數(shù)稱為 Skolem函數(shù)。 例如 ?x1 ?x2 ? ? ???xn?yP(x1,x2,…, x n,y)中 y可用Skolem函數(shù) f(x1,x2,…, x n)替換為 ?x1 ?x2 ? ? ?? ?xnP(x1,x2,…, x n,f(x1,x2,…, x n))。 （ 5）、把全稱量詞全部移到公式的左邊。 （ 6）、把全稱量詞后面的公式利用等價關(guān)系A(chǔ)?(B ?C) ? (A?B) ?(A ?C)化為子句的合取式，得到的公式稱為 Skolem標(biāo)準(zhǔn)形。 Skolem標(biāo)準(zhǔn)形的一般形式為 ?x1 ?x2 ? ? ???xnM，其中M是子句的合取式。 （ 7）、消去全稱量詞。 （ 8）、對變元更名，使子句間無同名變元。 （ 9）、消去合取詞 ? ，以子句為元素組成的集合稱為謂詞公式的子句集。 例、把謂詞公式 ?x{?yP(x,y) ? ??y[Q(x,y)?R(x,y)]}化為子句集。 定理 1 謂詞公式 G 不可滿足當(dāng)且僅當(dāng)其子句集 S不可滿足。子句集 S是不可滿足的是指其全部子句的合取式是不可滿足的。 命題邏輯中的歸結(jié)原理 要證明在前提 P下結(jié)論 Q成立，即是證明 P ? Q永真，這只須證明 P ? ?Q不可滿足。根據(jù)定理 1，只須證明 P ? ?Q的子句集不可滿足。由于子句之間是合取關(guān)系，只要有一個子句不可滿足，則整個子句集不可滿足。由于空子句是不可滿足的，所以如果子句集中包含空子句，則該子句集是不可滿足的。若子句集中不包含空子句，則可通過 Robinson提出的歸結(jié)原理對子句集進行歸結(jié)，歸結(jié)過程保證子句集的不可滿足性不變。一旦歸結(jié)出空子句，則證明結(jié)束。因此，歸結(jié)原理把定理的證明化為子句集中歸結(jié)出空子句的過程。 定義４、設(shè) L是一個文字，則稱 L與 ?L為互補文字。 定義５、設(shè) C C2是命題邏輯中的兩個子句， C1 中有文字 L1 ， C２ 中有文字 L２ ，且 L1與 L２互補， 從 C1， C２ 中分別刪除 L1 ， L２ ，再將剩余部分析取起來，構(gòu)成的新子句 C1２ 稱為 C1與C2的歸結(jié)式（消解式）， C1， C2稱為 C1２ 的親本子句。 定理２、歸結(jié)式 C1２ 是其親本子句 C1與 C2的邏輯結(jié)論。 推論、設(shè) C1， C2是子句集 S的兩個子句， C1２ 是它們的歸結(jié)式，則 （１）若用 C1２ 代替 C1和 C2后得到新子句集 S1，則由 S1的不可滿足性可推出原子句集 S的不可滿足性。即 S1不可滿足 ?S不可滿足 （２）若把 C1２ 加入到 S中，得到新子句集S２ ，則 S２ 與 S在不可滿足意義上是等價的。即 S2不可滿足 ? S不可滿足 例、用歸結(jié)原理證明 R是 P， （ P ? Q） ? R， （ S?U） ? R， U的邏輯結(jié)果。 替換與合一 定義６、一個替換 (Substitution)是形如 {t1 / x1, t2 / x2 ,…,t n / xn }的有限集合，其中 t1 , t2 ,…,t n 是項， x1, x2 ,…,x n是互不相同的個體變元。 ti / xi表示用 ti代換 xi 。 ti與 xi不同， xi也不能出現(xiàn)在 tj中 (j=1,2,…,n) 。 例、｛ a/x, g(y)/y, f(g(b))/z}是一個替換，{g(y)/x, f(x)/y}不是一個替換。 定義７、設(shè) ?＝ {t1 / x1, t2 / x2 ,…,t n / xn }是一個替換， E是一個表達(dá)式（項、原子公式、文字、子句），把 E中出現(xiàn)的所有個體變元 xi都用 ti 替換，得到的結(jié)果記為 E? ，稱為 E在 ?下的替換實例。 例、若 E=P(x,y,g(z)), ?＝ {a / x, f(b) /y ,c /z }，則E?= P(a,f(b),g(c))。 定義８、設(shè) ?＝ {t1 / x1, t2 / x2 ,…,tn
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1