2023/10/23人工智能講義1第三章一般搜索原理盲目搜索啟發式搜索歸結原理2023/10/23人工智能講義2盲目搜索圖搜索策略深度優先搜索寬度優先搜索等代價搜索2023/10/23人工智能講義3一些基本概念節點深度：

根節點深度=0

其它節點深度=父節點深度+101232023/10/23人工智能講義4一些基本概念（續1）路徑 設一節點序列為(n0,n1,…,nk)，對于i=1,…,k，若節點ni-1具有一個后繼節點ni，則該序列稱為從n0到nk的路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節點間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。2023/10/23人工智能講義5一些基本概念（續1）擴展一個節點

生成出該節點的所有后繼節點，并給出它們之間的耗散值。這一過程稱為“擴展一個節點”。2023/10/23人工智能講義6一般的圖搜索算法（GRAPHSEARCH）1,G=G0(G0=s),OPEN=(s);2,CLOSED=();3,LOOP:IFOPEN=()EXIT(FAIL);4,n=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)EXIT(SUCCESS);6,EXPAND(n)→{mi},G=ADD(mi,G);2023/10/23人工智能講義7一般的圖搜索算法（續）7,標記和修改指針： ADD(mj,OPEN),并標記mj到n的指針； 計算是否要修改mk、ml到n的指針； 計算是否要修改ml到其后繼節點的指針；8,對OPEN中的節點按某種原則重新排序；9,GOLOOP；2023/10/23人工智能講義8深度優先搜索在深度優先搜索中，首先擴展最新產生的(最深的)節點，深度相等的節點可以任意排列?！白钔懋a生的節點最先擴展”2023/10/23人工智能講義9深度優先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G=ADD(mi,G);8,IF目標在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標記mj到n的指針;10,GOLOOP;2023/10/23人工智能講義10231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標2023/10/23人工智能講義11深度優先搜索的性質一般不能保證找到最優解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關的方法2023/10/23人工智能講義12寬度優先搜索如果搜索是以接近起始節點的程度依次擴展節點的，那么這種搜索就叫做寬度優先搜索。這種搜索使逐層進行的，在對下一層的任意節點進行搜索之前，必須搜索完本層的所有節點。“先產生的節點先擴展”2023/10/23人工智能講義13寬度優先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G=ADD(mi,G);7,IF目標在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并標記mj到n的指針;9,GOLOOP;2023/10/23人工智能講義1423184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標82341876542023/10/23人工智能講義15寬度優先搜索的性質當問題有解時，一定能找到解當問題為單位耗散值，且問題有解時，一定能找到最優解方法與問題無關，具有通用性效率較低屬于圖搜索方法2023/10/23人工智能講義16等代價搜索寬度優先搜索可被推廣用來解決尋找從起始節點到目標節點具有最小代價路徑問題，這種推廣了的寬度優先搜索算法叫做等代價搜索算法。2023/10/23人工智能講義17等代價搜索算法算法1,G=G0(G0=s),OPEN=(s),CLOSED=(),g(s)=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,從OPEN表中選擇一個節點i,使其g(i)為最小。如果有幾個節點都合格，那么就要選擇一個目標節點作為i(要是有目標節點的話)；否則，就從中選一個作為節點I;REMOVE(i,OPEN),ADD(i,CLOSED);4,IFGOAL(i)EXIT(SUCCESS);5,EXPAND(i)→{j},G=ADD(j,G);6,對每個后繼節點j,計算g(j)=g(i)+c(i,j)且ADD(OPEN,j),并標記j到i的指針;7,GOLOOP;2023/10/23人工智能講義18啟發式圖搜索利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。啟發信息的強度強：降低搜索工作量，但可能導致找不到最 優解弱：一般導致工作量加大，極限情況下變為 盲目搜索，但可能可以找到最優解2023/10/23人工智能講義19希望：引入啟發知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。2023/10/23人工智能講義20基本思想定義一個評價函數f，對當前的搜索狀態進行評估，找出一個最有希望的節點來擴展。2023/10/23人工智能講義211，啟發式搜索算法A（A算法）評價函數的格式：

f(n)=g(n)+h(n) f(n)：評價函數 h(n)：啟發函數2023/10/23人工智能講義22符號的意義g*(n)：從s到n的最短路徑的耗散值h*(n)：從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n)：從s經過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計值2023/10/23人工智能講義23A算法1,OPEN=(s),f(s)=g(s)+h(s);2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{Mi}, 計算f(n,mi)=g(n,mi)+h(mi);

2023/10/23人工智能講義24A算法（續）

ADD(mj,OPEN),標記mj到n的指針； IFf(n,mk)<f(mk)f(mk)=f(n,mk), 標記mk到n的指針； IFf(n,ml)<f(ml,)f(ml)=f(n,ml), 標記ml到n的指針, ADD(ml,OPEN);7,OPEN中的節點按f值從小到大排序；8,GOLOOP；2023/10/23人工智能講義25一個A算法的例子定義評價函數： f(n)=g(n)+h(n) g(n)為從初始節點到當前節點的耗散值 h(n)為當前節點“不在位”的將牌數

28316475123847652023/10/23人工智能講義26h計算舉例 h(n)=42

831

6475123457682023/10/23人工智能講義272831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標123456定義評價函數： f(n)=g(n)+h(n) g(n)為從初始節點到當前節點的耗散值 h(n)為當前節點“不在位”的將牌數2023/10/23人工智能講義28最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件： h(n)≤h*(n) 則A算法稱為A*算法。2023/10/23人工智能講義29A*條件舉例8數碼問題h(n)=“不在位”的將牌數h(n)=將牌“不在位”的距離和2

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：22023/10/23人工智能講義30A*算法的性質定理1：

對有限圖，如果從初始節點s到目標節點t有路徑存在，則算法A一定成功結束。2023/10/23人工智能講義31A*算法的性質（續1）引理2.1：

對無限圖，若有從初始節點s到目標節點t的路徑，則A*不結束時，在OPEN表中即使最小的一個f值也將增到任意大，或有f(n)>f*(s)。2023/10/23人工智能講義32A*算法的性質（續2）引理2.2： A*結束前，OPEN表中必存在f(n)≤f*(s)。2023/10/23人工智能講義33A*算法的性質（續3）定理2：

對無限圖，若從初始節點s到目標節點t有路徑存在，則A*一定成功結束。2023/10/23人工智能講義34A*算法的性質（續4）推論2.1： OPEN表上任一具有f(n)<f*(s)的節點n，最終都將被A*選作擴展的節點。2023/10/23人工智能講義35A*算法的性質（續5）定理3(可采納性定理)：

若存在從初始節點s到目標節點t有路徑，則A*必能找到最佳解結束。2023/10/23人工智能講義36A*算法的性質（續6）推論3.1： A*選作擴展的任一節點n，有f(n)≤f*(s)。2023/10/23人工智能講義37A*算法的性質（續7）定理4：設對同一個問題定義了兩個A*算法A1和A2，若A2比A1有較多的啟發信息，即對所有非目標節點有h2(n)>h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結束時，由A2所擴展的每一個節點，也必定由A1所擴展，即A1擴展的節點數至少和A2一樣多。簡寫：如果h2(n)>h1(n),則A1擴展的節點數≥A2擴展的節點數2023/10/23人工智能講義38A*算法的改進問題的提出：

因A算法第6步對ml類節點可能要重新放回到OPEN表中，因此可能會導致多次重復擴展同一個節點，導致搜索效率下降。2023/10/23人工智能講義39s(10)A(1)B(5)C(8)G目標631118一個例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)A(7)B(8)s(10)A(5)B(8)s(10)C(9)A(5)B(8)s(10)A(5)B(7)C(9)s(10)A(4)B(7)C(9)s(10)2023/10/23人工智能講義40出現多次擴展節點的原因在前面的擴展中，并沒有找到從初始節點到當前節點的最短路徑，如節點A。2023/10/23人工智能講義41解決的途徑對h加以限制能否對h增加適當的限制，使得第一次擴展一個節點時，就找到了從s到該節點的最短路徑。對算法加以改進能否對算法加以改進，避免或減少節點的多次擴展。2023/10/23人工智能講義42改進的條件可采納性不變不多擴展節點不增加算法的復雜性2023/10/23人工智能講義43對h加以限制定義：一個啟發函數h，如果對所有節點ni和nj，其中nj是ni的子節點，滿足

h(ni)-h(nj)≤c(ni,nj) h(t)=0 則稱h是單調的。h(ni)ninjh(nj)c(ni,nj)2023/10/23人工智能講義44h單調的性質定理5：

若h(n)是單調的，則A*擴展了節點n之后，就已經找到了到達節點n的最佳路徑。

即：當A*選n擴展時，有g(n)=g*(n)。2023/10/23人工智能講義45h單調的性質（續）定理6：

若h(n)是單調的，則由A*所擴展的節點序列其f值是非遞減的。2023/10/23人工智能講義46h單調的例子8數碼問題：h為“不在位”的將牌數1 h(ni)-h(nj)=0 (nj為ni的后繼節點)-1 h(t)=0 c(ni,nj)=1滿足單調的條件。 2023/10/23人工智能講義47對算法加以改進一些結論：OPEN表上任一具有f(n)<f*(s)的節點定會被擴展。A*選作擴展的任一節點，定有f(n)≤f*(s)。2023/10/23人工智能講義48改進的出發點OPEN=(…………)f*(s)f值小于f*(s)的節點f值大于等于f*(s)的節點fm：到目前為止已擴展節點的最大f值，用fm代替f*(s)2023/10/23人工智能講義49修正過程A1,OPEN=(s),f(s)=g(s)+h(s),fm=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,NEST={ni|f(ni)<fm} IFNEST≠()n=NEST中g最小的節點 ELSEn=FIRST(OPEN), fm=f(n);4,…,8:同過程A。2023/10/23人工智能講義50s(10)A(1)B(5)C(8)G目標631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)2023/10/23人工智能講義51例子：傳教士與野人問題

設有3個傳教士和3個野人來到河邊，打算乘一只船從右岸渡到左岸去。該船的負載能力為兩人。在任何時候，如果野人人數超過傳教士人數，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡河過去？

2023/10/23人工智能講義52問題表示：需要考慮兩岸的修道士人數和野人人數，船的位置。用三元式表示狀態：

S=(m,c,b)

其中，m表示左岸修道士人數，c表示左岸野人人數，b表示左岸船的數目。解：確定估價函數。

f(n)=g(n)＋h(n)=d(n)＋m＋c－2b

其中，d(n)為節點深度。h(n)＜h*(n)，滿足A*算法的限制條件。2023/10/23人工智能講義53(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問題的A*搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)2023/10/23人工智能講義544.5AO*算法搜索與或圖的A*算法節點評價方法

A*算法中，對節點n的評價，實際上是對“初始節點--節點n--目標節點”這一條路徑的評價

AO*算法中，由于與節點的存在，解對應的不是一條路徑，而是一個子圖，因此對節點的評價，實際是對局部解圖的評價2023/10/23人工智能講義55

A(6)

B

C

D(3)(4)(5)f(A)=min{(B)+(C)+2,(D)+1}

G

H

E

F(4)(4)(5)(7)(10)(9)(6)(11)與或圖節點擴展與評價2023/10/23人工智能講義56算法的兩個階段第一階段：自上而下的圖生成過程

對于每一個已經擴展過的節點，都對應一個指針，指向該節點后繼節點中，代價值小的那條邊。圖生成過程，就是從初始節點出發，按照該指針向下搜索，一直到找到一個未擴展的節點為止。然后擴展該節點。第二階段：自下而上的代價值計算過程

設n為最新被擴展的節點，計算節點n對應的最小代價值，并標記一個指針指向對應最小代價的邊。對于n的父節點，進行同樣的計算。重復這一過程，直到初始節點s為止。這時，從s出發，選擇那些指針所指向的邊得到的局部圖，為當前代價值最小的局部圖。2023/10/23人工智能講義57具體步驟Step1建立一個僅由初始節點s構成的搜索圖G，計算h(s)Step2在以下兩過程間循環，直到s標記為可解或不可解，或其代價值大于閾值：

2.1選擇節點進行擴展

2.2根據擴展情況修改節點的可解性與代價值

2023/10/23人工智能講義58Step2.1選擇節點進行擴展：1根據指針找出待擴展的局部解圖G′。

2選擇G′中的一個非終節點n作為當前節點。

3擴展節點n，如不能擴展，則標記為不可解，否則生成子節點集，如子節點為非終節點，計算其代價值，若為終節點，標注其可解。將所有子節點添加到G中。4建立含n的單一節點集合S，S:＝{n}2023/10/23人工智能講義59Step2.2修改節點的可解性與代價值

重復以下步驟，直到S為空：

1從S中挑選一個子孫節點都不在S中的節點m2計算始于m的每條連接線的代價，取其中最小值為m對應的代價，并在對應于最小代價的連接線上加指針。3如果連接于最小代價連接線上的所有節點都可解，則標注m可解。4如果m的可解性或代價值發生改變，則把m的所有祖先節點添加到S中。2023/10/23人工智能講義60AO*算法舉例目標目標初始節點n0n1n2n3n4n5n6n7n8h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2

h(n7)=0h(n8)=0連接線的代價=后繼節點個數2023/10/23人工智能講義61n0n1n2n3n4n5n6n7n8n0(3)n1(2)n4(1)n5(1)紅色代價：4藍色代價：32023/10/23人工智能講義62n0n1n2n3n4n5n6n7n8n4(1)n5(1)紅色代價：4藍色代價：6n1(2->5)n2(4)n3(4)n0(3)n0(3->4)2023/10/23人工智能講義63n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1->2)2023/10/23人工智能講義64n0n1n2n3n4n5n6n7n8紅色代價：5藍色代價：6n0(4)n4(1)n5(1->2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4->5)2023/10/23人工智能講義65n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2023/10/23人工智能講義66目標目標初始節點n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2023/10/23人工智能講義67目標目標初始節點n0n1n2n3n4n5n6n7n8初始節點可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2023/10/23人工智能講義68歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義69歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義70概述歸結原理由J.A.Robinson由1965年提出。與演繹法完全不同，新的邏輯演算算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結原理，總可以在有限步內給以判定。語義網絡、框架表示、產生式規則等等都是以推理方法為前提的。即，有了規則已知條件，順藤摸瓜找到結果。而歸結方法是自動推理、自動推導證明用的。（“數學定理機器證明”）本課程只討論一階謂詞邏輯描述下的歸結推理方法，不涉及高階謂詞邏輯問題。

2023/10/23人工智能講義71歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義72歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義73命題邏輯的歸結法基本單元：簡單命題（陳述句）例：

命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B反證法：證明A1ΛA2ΛA3Λ～B是矛盾式

（永假式）

2023/10/23人工智能講義74命題邏輯的歸結法建立子句集合取范式：命題、命題和的與，如： PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）

子句集S：S={P,P∨Q,～P∨Q}

2023/10/23人工智能講義75命題邏輯的歸結法歸結式消除互補對，求新子句→得到歸結式。如子句：C1=C1′∨L,C2=C2′∨

歸結式：R(C1,C2)=C1′∨

C2′

注意：C1ΛC2→R(C1,C2)

，反之不一定成立。假言推理:由合適公式W1和W1

→W2產生合適公式W2,如何用歸結法證明?2023/10/23人工智能講義76命題邏輯的歸結法歸結過程

對結論作否定,并加入前提中將命題寫成合取范式求出子句集對子句集使用歸結推理規則歸結式作為新子句參加歸結歸結式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結：除了有量詞和函數以外，其余和命題歸結過程一樣。2023/10/23人工智能講義77命題邏輯的歸結法例證明先將化為合取范式建立子句集S=對S做歸結PNIL2023/10/23人工智能講義78歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義79歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義80子句形

引用Herbrand定理，以說明歸結原理的意義及一個原理形成的根基與背景SKOLEM標準形前束范式：把所有的量詞都提到前面去，然后消掉所有量詞。

定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。即(Q1x1)…(Qnxn)M(x1,…,xn),其中Qixi為存在量詞或全稱量詞,M(x1,…,xn)

為合取范式(由一些子句的合取組成)。2023/10/23人工智能講義81子句形(Skolem標準形)

量詞消去原則：

消去存在量詞“

”，略去全程量詞“

”。

注意：左邊有全稱量詞的存在量詞，消去時該變量改寫成為全稱量詞的函數(Skloem函數)；如沒有，改寫成為常量。

例子：見《人工智能及其應用》P752023/10/23人工智能講義82子句形(Skolem標準形)

定理： 謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。SKOLEM標準形定義：

消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標準形同G并不等值。2023/10/23人工智能講義83子句形(Skolem標準形)

例:G=(x)(y)(z)(u)P(x,y,z,u)Skolem標準形為：

(y)(z)P(a,y,z,f(y,z))其中，x=a(常量)，u=f(y.z)

2023/10/23人工智能講義84子句形子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析取（謂詞的和）。子句集S的求?。篏→SKOLEM標準形 →消去存在變量 →以“，”取代“Λ”，并表示為集合形式。2023/10/23人工智能講義85子句形

G是不可滿足的<=>S是不可滿足的G與S不等價，但在不可滿足的意義下是一致的。

定理： 若G是給定的公式，而S是相應的子句集，則G是不可滿足的<=>S是不可滿足的。

注意：G真不一定S真，而S真必有G真。

即：S=>G2023/10/23人工智能講義86子句形G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的子句集可以分解成幾個單獨處理。

有SG=S1US2US3U…USn

則SG

與S1US2US3U…USn在不可滿足的意義上是一致的。

即SG

不可滿足<=>S1US2US3U…USn不可滿足

2023/10/23人工智能講義87歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義88歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義89Herbrand定理問題：

一階邏輯公式的永真性（永假性）的判定是否能在有限步內完成？2023/10/23人工智能講義90Herbrand定理1936年圖靈(Turing)和邱吉(Church)互相獨立地證明了：

“沒有一般的方法使得在有限步內判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內判定它是永真（或永假）。對于非永真（或永假）的公式就不一定能在有限步內得到結論。判定的過程將可能是不停止的?！?/p>

2023/10/23人工智能講義91Herbrand定理Herbrand的思想定義：

公式G永真：對于G的所有解釋，G都為真。思想：

尋找一個已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內停止。2023/10/23人工智能講義92Herbrand定理H域H解釋語義樹結論：Herbrand定理2023/10/23人工智能講義93Herbrand定理H域H解釋語義樹結論：Herbrand定理2023/10/23人工智能講義94Herbrand定理（H域）基本方法：因為量詞是任意的，所討論的個體變量域D是任意的，所以解釋的個數是無限、不可數的。簡化討論域。建立一個比較簡單、特殊的域，使得只要在這個論域上，該公式是不可滿足的。此域稱為H域：H0為G中所出現的常量的集合，若G中沒有常量，就任取常量，H0={a}。

規定為H域

※

例題請參考教科書P272023/10/23人工智能講義95H域舉例例1S={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))，…}2023/10/23人工智能講義96Herbrand定理（H域）幾個基本概念f（t1,t2,…tn）：f為子句集S中的所有函數變量。t1,t2,…tn為S的H域的元素。通過它們來討論永真性。原子集A：謂詞套上H域的元素組成的集合。如

A={所有形如P(t1,t2,…tn)的元素}

即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數的，因此，A也是可數的。一旦原子集內真值確定好（規定好），則S在H上的真值可確定。成為可數問題。2023/10/23人工智能講義97原子集舉例例1S={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))),…}2023/10/23人工智能講義98Herbrand定理（H域）沒有變量出現的原子、文字、子句和子句集，分別稱作基原子、基文字、基子句和基子句集。它們在討論子句集S的不可滿足性時占有重要置。2023/10/23人工智能講義99Herbrand定理H域H解釋語義樹結論：Herbrand定理2023/10/23人工智能講義100Herbrand定理H域H解釋語義樹結論：Herbrand定理2023/10/23人工智能講義101Herbrand定理（H解釋）解釋I*：取一個值得到一個結論I映射S中到所有常量符號到它們本身。(即原子集)令f是n元函數，I是f下的一個指派，即H中的元素到f的一個映射（函數值）。簡單地說(P29)，A中的各元素真假組合都是H的解釋。（或真或假只取一個）問題：對于所有的解釋，全是假才可判定。因為所有解釋代表了所有的情況，如可窮舉，問題便可解決。

2023/10/23人工智能講義102H解釋-舉例例1S={P(a),～

P(x)∨P(f(x))}

S的H域H∞={a,f(a),f(f(a))，…}S的原子集為

A={P(a),P(f(a)),P(f(f(a))),…}S的H解釋：

I1*={P(a),P(f(a)),P(f(f(a))),…} S|I1*=T

I2*={～

P(a),P(f(a)),P(f(f(a))),…} S|I2*=F

I3*={P(a),～

P(f(a)),P(f(f(a))),…} S|I3*=F我們關心的是：對論域上的任一解釋I，若有S|I=T,如何求得一個相應的H解釋I*,使得S|I*=T成立。2023/10/23人工智能講義103Herbrand定理（H解釋）如下三個定理保證了歸結法的正確性：定理1：

設I是S的論域D上的解釋，存在對應于I的H解釋I*，使得若有S|I=T，必有S|I*=T。定理2：

子句集S是不可滿足的，當且僅當所有的S的H解釋下為假。定理3：

子句集S是不可滿足的，當且僅當對每一個解釋I下，至少有S的某個子句的某個基例為假。2023/10/23人工智能講義104Herbrand定理（H解釋）基例S中某子句中所有變元符號均以S的H域中的元素代入時，所得的基子句C’稱為C的一個基例。若一個子句為假，則此解釋為假。一般來說，D是無窮不可列的，因此，子句集S也是無窮不可列的。但S確定后H是無窮可列的。不過在H上證明S的不可滿足性仍然是不可能的。解決問題的方法：語義樹2023/10/23人工智能講義105Herbrand定理H域H解釋語義樹結論：Herbrand定理2023/10/23人工智能講義106Herbrand定理H域H解釋語義樹結論：Herbrand定理2023/10/23人工智能講義107Herbrand定理（語義樹）構成方法原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標記在兩側的分枝上（可不完全畫完）。(P34)特點一般情況H是可數集，S的語義樹是無限樹。2023/10/23人工智能講義108Herbrand定理（語義樹）意義SHA語義樹可以理解語義樹為H域的圖形解釋。

目的：把每個解釋都攤開。語義樹中包含原子集的全部元素，因此，語義樹是完全的。每一個直到葉子節點的分支對應S的一個解釋?？梢酝ㄟ^對語義樹每一個分支來計算S的真值。如果每個基例都為假，則可認為是不可滿足的。2023/10/23人工智能講義109語義樹-舉例例1設子句集S的原子集A={P,Q,R}

語義樹：

N0

N11N12N21N22N23N24N31N32N33N34N35N36N37N38P～

QQR～

R～

PI(N)表示從根節點到節點N分枝上所標記的所有文字的并集。如I(N34)={P,～

Q,～

R}2023/10/23人工智能講義110Herbrand定理（語義樹）幾個概念失敗結點： 當（由上）延伸到點N時，I(N)已表明了S的某子句的某基例假。但N以前尚不能判斷這事實。就稱N為失敗結點。完全語義樹：如果對語義樹的所有葉結點N來說，I(N)包含了S的原子集A={A1,A2,…}中的所有元素Ai或～

Ai，I=1…n。封閉語義樹： 如果S的完全語義樹的每個分枝上都有一個失敗結點，就稱它是一棵封閉語義樹。2023/10/23人工智能講義111封閉語義樹-舉例例子句集S={～P(x)∨Q(x),P(f(y)),～Q(f(y))}H={a,f(a),f(f(a)),…}A={P(a),Q(a),P(f(a)),Q(f(a)),…}

語義樹：

N0

N11N12N21N22N23N24N31N32N33N34N35N36N37N38P(a)Q(a)P(f(a))N41N42N43N44N45N46N47N48N49N410N411N413N415N412N414N416這是一個無限樹，然而它是否是一個封閉樹？Q(f(a))ΧΧΧΧΧΧΧΧΧΧI(N41)={P(a),Q(a),P(f(a)),Q(f(a))},它使S的子句～Q(f(y))的基例～Q(f(a))為假，而N41的父輩不能使子句的基例為假2023/10/23人工智能講義112封閉語義樹-舉例例子句集S={～P(x)∨Q(x),P(f(y)),～Q(f(y))}H={a,f(a),f(f(a)),…}A={P(a),Q(a),P(f(a)),Q(f(a)),…}

封閉語義樹：

N0

N11N12N21N22N23N24N31N32N36N37N38P(a)Q(a)P(f(a))N41N42N49N410N413N414Q(f(a))ΧΧΧΧΧΧΧΧΧΧ2023/10/23人工智能講義113Herbrand定理H域H解釋語義樹結論：Herbrand定理2023/10/23人工智能講義114Herbrand定理H域H解釋語義樹結論：Herbrand定理2023/10/23人工智能講義115Herbrand定理（結論）Herbrand定理：子句集S是不可滿足的，當且僅當對應于S的完全語義數是棵有限封閉樹。

子句集S是不可滿足的，當且僅當存在不可滿足的S的有限基例集。

2023/10/23人工智能講義116Herbrand定理（結論）定理的意義Herbrand定理已將證明問題轉化成了命題邏輯問題。由此定理保證，可以放心的用機器來實現自動推理了。（歸結原理）注意Herbrand定理給出了一階邏輯的半可判定算法，即僅當被證明定理是成立時，使用該算法可以在有限步得證。而當被證定理并不成立時，使用該算法得不出任何結論。但是

2023/10/23人工智能講義117例S={P(x,g(x),y,h(x,y),z,k(x,y,z)),～P(u,v,e(v),w,f(v,w)),x)}有H0={a},S0′={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個元素S1′：

63+64=1512個元素

H2：元素個數有63數量級（由于變量最多的函數是k(x,y,z),三個變量都可能取值于H1的六個元素）S2′：元素個數有(63)

4數量級建立S3′，S4′，直到S5′才是不可滿足。然而

S5′元素個數已達（1064）4=10256Herbrand定理（結論）仍存在的問題：基例集序列元素的數目隨子句基的元素數目成指數地增加。因此，Herbrand定理是30年代提出的，始終沒有顯著的成績。

直至1965年Robinson提出了歸結原理。2023/10/23人工智能講義118歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義119歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義120歸結原理歸結原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數，所以要考慮合一和置換。

(定義與例題參考教科書P41)2023/10/23人工智能講義121歸結原理置換和合一的注意事項：謂詞的一致性，P()與Q()，不可以常量的一致性，P(a,…)與P(b,….)，不可以

常量與變量，P(a,….)與P(x,…)，可以變量與函數，P(a,x,….)與P(x,f(x),…)，不可以；但P(a,x,…)與P(x,f(y),…)，可以是不能同時消去兩個互補對，P∨Q與～P∨～Q的空，不可以先進行內部簡化（置換、合并）2023/10/23人工智能講義122歸結原理歸結的過程(P48)寫出謂詞關系公式→用反演法寫出謂詞表達試→SKOLEM標準形→

子句集S→對S中可歸結的子句做歸結→歸結式仍放入S中，反復歸結過程→得到空子句

?得證2023/10/23人工智能講義123歸結原理歸結法的實質：歸結法是僅有一條推理規則的推理方法。歸結的過程是一個語義樹倒塌的過程。(P51)歸結法的問題子句中有等號或不等號時，完備性不成立。※Herbrand定理的不實用性引出了可實用的歸結法。2023/10/23人工智能講義124歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義125歸結原理概述命題邏輯的歸結法子句形Herbrand定理歸結原理歸結過程的策略控制2023/10/23人工智能講義126歸結過程的控制策略要解決的問題：歸結方法的知識爆炸?？刂撇呗缘哪康臍w結點盡量少控制策略的原則給出控制策略，以使僅對選擇合適的子句間方可做歸結。避免多余的、不必要的歸結式出現。或者說，少做些歸結仍能導出空子句。2023/10/23人工智能講義127歸結過程的控制策略盲目歸結

例S={P∨Q,

～

P∨Q,P∨～Q,～

P∨～Q}是不可滿足。

證明從S0=S開始，依次構造Si={C1,C2的歸結式|C1∈S0∪S1∪…∪Si-1,C2∈Si-1},i=1,2,…,直至得到空子句。具體過程如下：S0(1)

P∨Q(2)～

P∨Q(3)P∨～Q(4)～

P∨～QS1(5)Q(1)(2)(6)P(1)(3)(7)Q∨～Q(1)(4)(8)P∨～P(1)(4)(9)Q∨～Q(2)(3)(10)P∨～P(2)(3)(11)～P(2)(4)(12)～Q(3)(4)2023/10/23人工智能講義128歸結過程的控制策略(盲目歸結)S2(13)P(1)(7)(14)P∨Q(1)(8)(15)P∨Q(1)(9)(16)P∨Q(1)(10)(17)Q(1)(11)(18)P(1)(12)(19)Q

(2)(6)(20)～P∨Q(3)(4)(21)～P∨Q(2)(8)(22)～P∨Q(2)(9)(23)～P∨Q(2)(10)(24)～P(2)(12)(25)P(3)(5)(26)P∨～Q(3)(7)(27)P∨～Q(3)(8)(28)P∨～Q(3)(9)(29)P∨～Q(3)(10)(30)～Q(3)(11)(31)～P(4)(5)(32)～Q(4)(6)(33)～P∨～Q(4)(7)(34)～P∨～Q(4)(8)(35)～P∨～Q(4)(9)(36)～P∨～Q(4)(10)(37)Q

(5)(7)(38)Q(5)(9)(39)?(5)(12)產生過多不必要的歸結式。一類是重言式（7）-（10）由它們又產生了（13）-（16），（20）-（23），(26)-(29),(33)-(39)。另一類是重復的，如P,Q,～P,～Q.2023/10/23人工智能講義129歸結過程的控制策略刪除策略

設有兩個子句C和D，若有置換ó使得Có?D成立，便說子句C把子句D歸類。例C=P(X)D=P(a)∨Q(a)

取ó={a/x},便有Có=P(a)?{P(a),Q(a)}。刪除策略：若對s使用歸結推理過程中，當歸結式Cj是重言式或Cj被S中子句或歸結式Ci(i<j)歸類時，便將Cj刪除。2023/10/23人工智能講義130歸結過程的控制策略支持集策略

支持集：設S的子集T，說T是支持集，如果S-T是可滿足。（目標公式的否定或由它們的后裔產生的子句）策略：每次歸結時，至少有一個子句來自于T或由T導出的歸結式。例S={P∨Q,～P∨R,～Q∨R,～R}取T={～R}2023/10/23人工智能講義131歸結過程的控制策略語義歸結策略

將子句集S分成兩部分，約定每部分內的子句間不允許做歸結。還引入文字次序，約定歸結時其中的一個子句被歸結文字只能是該子句中“最大”的文字。例S={～P∨～Q∨R,P∨R,Q∨R,～R}

文字次序：P>Q>R

解釋I={～P,～Q,～R}2023/10/23人工智能講義132歸結過程的控制策略線性歸結策略

首先從子句集S中選取一個稱為頂子句的子句C0開始做歸結，其次是歸結過程中所得到的歸結式Ci立即同另一個子句Bi進行歸結得歸結式Ci+1。而Bi屬于S或是已出現的歸結式Cj(j<i)。2023/10/23人工智能講義133歸結過程的控制策略單元歸結：

在歸結過程中，每次歸結都有一個子句是單元（只含一個文字）子句或單元因子時的歸結過程。2023/10/23人工智能講義134歸結過程的控制策略輸入歸結：

在歸結過程中，對兩個子句所做的每一次歸結，其中必須有一個是S的子句時，便稱作輸入歸結。2023/10/23人工智能講義135歸結過程的控制策略控制策略的方法刪除 => 完備采用支撐集 <=>完備語義歸結 <=> 完備線性歸結 <=>完備單元歸結 => 完備輸入歸結 => 完備2023/10/23人工智能講義136謂詞邏輯的歸結方法對于子句C1L1和C2L2，如果L1與~L2可合一，且s是其合一者，則(C1C2)s是其歸結式。例：P(x)Q(y),~P(f(z))R(z) =>Q(y)R(z)2023/10/23人工智能講義137歸結舉例設公理集： (x)(R(x)L(x)) (x)(D(x)~L(x)) (x)(D(x)I(x))求證：(x)(I(x)~R(x))化子句集：

(x)(R(x)L(x))=>(x)(~R(x)L(x))=>~R(x)L(x)(1)2023/10/23人工智能講義138 (x)(D(x)~L(x))=>(x)(~D(x)~L(x))=>~D(x)~L(x)(2) (x)(D(x)I(x))=>D(A)I(A)=>D(A)(3) I(A)(4)2023/10/23人工智能講義139目標求反：

~(x)(I(x)~R(x))=>(x)~(I(x)~R(x))=>(x)(~I(x)R(x))=>~I(x)R(x)