【正文】 t) = 0則稱 h是單調(diào)的。2/27/2023 45人工智能講義h單調(diào)的例子? 8數(shù)碼問題：–h為 “不在位 ”的將牌數(shù) 1h(ni) h(nj) = 0 (nj為 ni的后繼節(jié)點 ) 1 h(t) = 0c(ni, nj) = 1 滿足單調(diào)的條件。2, LOOP: IF OPEN=( ) EXIT(FAIL)。該船的負載能力為兩人。解 ：確定估價函數(shù)。圖生成過程，就是從初始節(jié)點出發(fā)，按照該指針向下搜索，一直到找到一個未擴展的節(jié)點為止。重復這一過程，直到初始節(jié)點 s為止。 3 擴展節(jié)點 n，如不能擴展，則標記為不可解，否則生成子節(jié)點集，如子節(jié)點為非終節(jié)點，計算其代價值，若為終節(jié)點，標注其可解。 4 如果 m的可解性或代價值發(fā)生改變，則把 m的所有祖先節(jié)點添加到 S中。即，一階邏輯中任意恒真公式，使用歸結原理，總可以在有限步內(nèi)給以判定。（ “數(shù)學定理機器證明 ”）? 本課程只討論一階謂詞邏輯描述下的歸結推理方法，不涉及高階謂詞邏輯問題 。 假言推理 : 由合適公式 W1和 W1 → W2產(chǎn)生合適公式 W2 ,如何用歸結法證明 ?2/27/2023 75人工智能講義命題邏輯的歸結法? 歸結過程 – 對結論作否定 ,并加入前提中– 將命題寫成合取范式– 求出子句集– 對子句集使用歸結推理規(guī)則– 歸結式作為新子句參加歸結– 歸結式為空子句 □ ， S是不可滿足的（矛盾），原命題成立。 即 (Q1x1)…(Q nxn)M(x1, …, x n),其中Qixi為存在量詞或全稱量詞 , M(x1, …, x n) 為合取范式 (由一些子句的合取組成 )。 –SKOLEM標準形定義：消去量詞后的謂詞公式。–子句集 S的求?。? G → SKOLEM 標準形 → 消去存在變量 → 以 “ ， ” 取代 “ Λ ” ，并表示為集合形式 。即： S = G2/27/2023 85人工智能講義子句形? G = G1Λ G 2Λ G 3Λ …Λ G n 的子句形– G的子句集可以分解成幾個單獨處理。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。–思想：尋找一個已給的公式是真的解釋。建立一個比較簡單、特殊的域，使得只要在這個論域上，該公式是不可滿足的。通過它們來討論永真性。–一旦原子集內(nèi)真值確定好（規(guī)定好），則 S在 H上的真值可確定。2/27/2023 98人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結論： Herbrand定理2/27/2023 99人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結論： Herbrand定理2/27/2023 100人工智能講義Herbrand定理 （ H解釋）? 解 釋 I*：取一個值得到一個結論– I映射 S中到所有常量符號到它們本身。因為所有解釋代表了所有的情況，如可窮舉，問題便可解決 。 –定理 3：子句集 S是不可滿足的，當且僅當對每一個解釋 I下，至少有 S的某個子句的某個 基例 為假。但 S確定后 H是無窮可列的。 (P34)? 特點–一般情況 H是可數(shù)集， S的語義樹是無限樹。 每一個直到葉子節(jié)點的分支對應 S的一個解釋。如 I(N34)={P, ～ Q, ～ R}2/27/2023 109人工智能講義Herbrand定理 （語義樹）? 幾個概念– 失敗結點 ： 當（由上）延伸到點 N時， I(N)已表明了 S的某子句的某基例假。– 封閉語義樹 ：如果 S的完全語義樹的每個分枝上都有一個失敗結點，就稱它是一棵封閉語義樹。–由此定理保證，可以放心的用機器來實現(xiàn)自動推理了。={P(a,g(a),a,h(a,a),a,k(a,a,a)), ～ P(a,a,e(a),a,f(a,a)),a)} H1={a,g(a),h(a,a),k(a,a,a),e(a),f(a,a)} 共 6個元素 S1180。 ， 直到 S5180。因此， Herbrand定理是 30年代提出的，始終沒有顯著的成績。–但由于有函數(shù)，所以要考慮 合一 和 置換 。 ※ Herbrand定理的不實用性引出了可實用的歸結法。或者說，少做些歸結仍能導出空子句。一類是重言式（ 7） （ 10）由它們又產(chǎn)生了（ 13） （ 16），（ 20） （ 23）， (26)(29),(33)(39)。例 C=P(X) D=P(a)∨Q(a) 取 243。2/27/2023 129人工智能講義歸結過程的控制策略?支持集策略 支持集：設 S的子集 T，說 T是支持集，如果 ST是可滿足。例 S={～P∨～ Q∨ R, P∨ R, Q∨ R ,～R } 文字次序： PQR 解釋 I={～P, ～Q, ～R} 2/27/2023 131人工智能講義歸結過程的控制策略? 線性歸結策略 首先從子句集 S中選取一個稱為頂子句的子句 C0開始做歸結，其次是歸結過程中所得到的歸結式 Ci立即同另一個子句 Bi進行歸結得歸結式 Ci+1。2/27/2023 134人工智能講義歸結過程的控制策略? 控制策略的方法–刪除 = 完備–采用支撐集 =完備–語義歸結 =完備–線性歸結 =完備–單元歸結 = 完備–輸入歸結 = 完備2/27/2023 135人工智能講義謂詞邏輯的歸結方法? 對于子句 C1?L1和 C2?L2，如果 L1與 ~L2可合一，且 s是其合一者，則 (C1?C2)s是其歸結式。研究案情時，偵察員 A說： “趙與錢中至少有一人作案 ”；偵察員 B說： “錢與孫中至少有一人作案 ”；偵察員 C說： “孫與李中至少有一人作案 ”；偵察員 D說： “趙與孫中至少有一人與此案無關 ”；偵察員 E說： “錢與李中至少有一人與此案無關 ”。? 修改后的證明樹稱為 修改證明樹2/27/2023 141人工智能講義歸結反演求解 舉例“如果無論 John到哪里去， Fido也就去那里，那么如果 John在學校， Fido在哪里？ ”已知： (?x)[AT(John, x) ? AT(Fido, x)] AT(John, School)求證： (?x)AT(Fido, x)如果我們首先證明公式 (?x)AT(Fido, x) 在邏輯上遵循前提公式集，然后尋求一個存在 x的例，那么就能解決 “Fido在哪里 ”的問題。2/27/2023 132人工智能講義歸結過程的控制策略? 單元歸結： 在歸結過程中，每次歸結都有一個子句是單元（只含一個文字）子句或單元因子時的歸結過程。例 S={P∨ Q,～P∨ R, ～Q ∨ R, ～R }取 T={～R }2/27/2023 130人工智能講義歸結過程的控制策略? 語義歸結策略 將子句集 S分成兩部分，約定每部分內(nèi)的子句間不允許做歸結。=P(a) ? {P(a),Q(a)}。 使得 C 243。 證明從 S0=S開始，依次構造 Si={C1,C2的歸結式 |C1∈ S0∪ S1 ∪ … ∪ Si1,C2 ∈ Si1} ,i=1,2, …, 直至得到空子句。? 控制策略的目的–歸結點盡量少? 控制策略的原則– 給出控制策略，以使僅對選擇合適的子句間方可做歸結。 –歸結的過程是一個語義樹倒塌的過程。2/27/2023 117人工智能講義歸結原理? 概述? 命題邏輯的歸結法? 子句形? Herbrand定理? 歸結原理? 歸結過程的策略控制2/27/2023 118人工智能講義歸結原理? 概述? 命題邏輯的歸結法? 子句形? Herbrand定理? 歸結原理? 歸結過程的策略控制2/27/2023 119人工智能講義歸結原理? 歸結原理正確性的根本在于，找到矛盾可以肯定不真。然而 S5180。 ： 元素個數(shù)有 (63) 4 數(shù)量級建立 S3180。而當被證定理并不成立時，使用該算法得不出任何結論。 2. 子句集 S是不可滿足的，當且僅當存在不可滿足的 S的有限基例集。就稱 N為失敗結點。如果每個基例都為假，則可認為是不可滿足的。 目的：把每個解釋都攤開。? 解決問題的方法： 語義樹2/27/2023 104人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結論： Herbrand定理2/27/2023 105人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結論： Herbrand定理2/27/2023 106人工智能講義Herbrand定理 （語義樹）? 構成方法–原子集中所有元素逐層添加的一棵二叉樹。? 若一個子句為假，則此解釋為假。2/27/2023 102人工智能講義Herbrand定理 （ H解釋）? 如下三個定理保證了歸結法的正確性：–定理 1：設 I是 S的論域 D上的解釋，存在對應于 I的 H解釋 I*，使得若有 S|I = T，必有 S|I* = T。簡單地說 (P29)， A中的各元素真假組合都是 H的解釋。 2/27/2023 96人工智能講義原子集舉例? 例 1 S={P(a), ～ P(x)∨P(f(x)) } H∞ = {a,f(a),f(f(a))， …} S的原子集為 A={P(a),P(f(a)),P(f(f(a))), … }2/27/2023 97人工智能講義Herbrand定理 （ H域）? 沒有變量出現(xiàn)的原子、文字、子句和子句集，分別稱作基原子、基文字、基子句和基子句集。如A = {所有形如 P(t1, t2, …t n)的元素 }即把 H中的東西填到 S的謂詞里去。 規(guī)定 為 H域 ※ 例題請參考教科書 P272/27/2023 94人工智能講義H域舉例? 例 1 S={P(a), ～ P(x)∨P(f(x)) }依定義有H0={a}H1={a} U{f(a)}={a,f(a)}H2={a,f(a)}U{f(a),f(f(a))}={a,f(a),f(f(a))}…H∞ = {a,f(a),f(f(a))， …}2/27/2023 95人工智能講義Herbrand定理 （ H域）? 幾個基本概念– f（ t1, t2, …t n） ： f為子句集 S中的所有函數(shù)變量。 2/27/2023 91人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結論： Herbrand定理2/27/2023 92人工智能講義Herbrand定理? H域? H解釋? 語義樹? 結論： Herbrand定理2/27/2023 93人工智能講義Herbrand定理 （ H域）? 基本方法：– 因為 量詞是任意的，所討論的個體變量域 D是任意的，所以解釋的個數(shù)是無限、不可數(shù)的 。判定的過程將可能是不停止的。即 SG 不可滿足 = S1 U S2 U S3 U …U Sn不可滿足 –定理：若 G是給定的公式，而 S是相應的子句集，則 G是不可滿足的 = S是不可滿足的。 2/27/2023 82人工智能講義子句形 ( Skolem 標準形 )? ? ? ? ? ? ? ? ? ? ? ? ?–例 :G=(?x)(?y)(?z)(?u)P(x,y,z,u)Skolem 標準形為：