人工智能第二章知識表示方法

第二章知識表達辦法教材：蔡自興等《人工智能及其應用》（第4版）清華大學出版社，2023.5華科大自動化學院第1頁第二章知識表達辦法人類智能活動主要是取得并利用知識。知識是智能基礎。為了使計算機具有智能，能模擬人類智能行為，就必須使它具有知識。但知識需要用合適模式表達出來才能存放到計算機中去，因此，知識表達成為人工智能中一種十分主要研究課題。本章將首先介紹知識與知識表達概念，然后介紹狀態(tài)空間法、問題歸約法、謂詞邏輯法、語義網(wǎng)絡法、框架表達、本體技術、過程表達等目前人工智能中應用比較廣泛知識表達辦法，為背面介紹推理辦法、專家系統(tǒng)等奠定基礎。2第2頁第二章知識表達辦法2.1知識與知識表達概念

2.2狀態(tài)空間法2.3問題歸約法2.4謂詞邏輯法2.5語義網(wǎng)絡法2.6框架表達2.7本體技術2.8過程表達2.9小結3第3頁2.1.1知識概念知識：在長期生活及社會實踐中、在科學研究及試驗中積累起來對客觀世界結識與經(jīng)驗。知識：把有關信息關聯(lián)*在一起所形成信息構造。知識反應了客觀世界中事物之間關系，不一樣事物或者相同事物間不一樣關系形成了不一樣知識*。

信息關聯(lián)形式：“假如……，則……”

假如大雁向南飛，則冬天就要來臨了。

——規(guī)則——事實例如：

“雪是白色”。

“假如頭痛且流涕，則有也許患了感冒”。2.1知識與知識表達概念

4第4頁2.1.1知識概念Feigenbaum以為知識是通過加工信息，它包括事實、信念和啟發(fā)式規(guī)則。Bernstein說知識是由特定領域描述、關系和過程組成。Hayes-Roth以為知識是事實、信念和啟發(fā)式規(guī)則。知識庫觀點看，知識是某論域中所包括各有關方面、狀態(tài)一種符號表達。5第5頁2.1.1知識概念人工智能系統(tǒng)所關懷知識事實：是有關對象和物體知識。規(guī)則：是有關問題中與事物行動、動作相聯(lián)系因果關系知識。元知識：是有關知識知識，是知識庫中高層知識。包括如何使用規(guī)則、解釋規(guī)則、校驗規(guī)則、解釋程序構造等。常識性知識：泛指普遍存在并且被普遍結識了客觀事實一類知識。

2.1知識與知識表達概念

6第6頁2.1.2知識特性1.相對正確性任何知識都是在一定條件及環(huán)境下產(chǎn)生*，在這種條件及環(huán)境下才是正確。1+1=2

（十進制）1+1=10(二進制）2.1知識與知識表達概念

7第7頁2.1.2知識特性不確定性*隨機性引發(fā)不確定性*

含糊性引發(fā)不確定性*經(jīng)驗引發(fā)不確定性不完全性引發(fā)不確定性(常識性？？）知識狀態(tài)：“真”

“假”

“真”與“假”之間中間狀態(tài)

“假如頭痛且流涕，則有也許患了感冒”

小李很高2.1知識與知識表達概念

8第8頁2.1.2知識特性

可表達性與可利用性知識可表達性:知識能夠用合適形式表達出來，如用語言、文字、圖形、神經(jīng)網(wǎng)絡等。知識可利用性:知識能夠被利用。2.1知識與知識表達概念

9第9頁2.1.3知識表達知識表達就是研究用機器表達上述這些知識可行性、有效性一般辦法，能夠看作是將知識符號化并輸入到計算機過程和辦法。知識表達=數(shù)據(jù)構造+處理機制知識表達觀點：陳說性過程性10第10頁2.1.3知識表達陳說性知識表達和過程性知識表達各有優(yōu)缺陷由于高級智能行為似乎強烈地依賴于陳說性知識，因此AI研究應重視陳說性開發(fā)。過程性知識陳說化表達。以合適方式將過程性知識和陳說性知識綜合，能夠提升智能系統(tǒng)性能。11第11頁2.1.3知識表達策略知識有關如何處理問題政策策略，包括在什么時間、什么地點、由什么主體采取什么行動、達成什么目標、注意什么事項等等一整套完整而詳細行動計劃規(guī)劃、行動步驟、工作方式和工作辦法。12第12頁2.1.3知識表達“智能”在給定問題——問題環(huán)境——主體目標條件下，有針對性地獲取問題——環(huán)境信息，恰本地對這些信息進行處理以提煉知識達成認知，在此基礎上，把已有知識與主體目標信息相結合，合理地產(chǎn)生處理問題策略信息，并利用所得到策略信息在給定環(huán)境下成功地處理問題達成主體目標。13第13頁2.1.4智能中“信息-知識-策略”關系4個要素包括信息知識策略行為4個能力包括獲取有用信息能力由信息生成知識(認知)能力由知識和目標生成策略(決策)能力實行策略取得效果(施效)能力14第14頁2.1.4智能中“信息-知識-策略”關系信息、知識、智能之間關系：信息是基本資源；知識是對信息進行加工所得到抽象化產(chǎn)物；策略是由客體信息和主體目標演繹出來智慧化身，智能是把信息資源加工成知識、進而把知識激活成處理問題策略并在策略信息引導下詳細處理問題所有能力。

信息、知識、智能關系，正好符合人類本身結識世界和優(yōu)化世界活動過程中由信息生成知識、由知識激活智能過程總結：信息經(jīng)加工提煉而成知識，知識被目標激活而成智能。15第15頁2.1.4智能中“信息-知識-策略”關系獲取信息功能由感覺器官完成，傳遞信息功能由神經(jīng)系統(tǒng)完成，處理信息和再生信息功能由思維器官完成，施用信息功能由效應器官完成。16第16頁2.1.5AI對知識表達辦法要求表達能力，要求能夠正確、有效地將問題求解所需要各類知識都表達出來?？衫斫庑?，所示知識應易懂、易讀。便于知識獲取，使得智能系統(tǒng)能夠漸進地增加知識，逐漸進化。便于搜索，表達知識符號構造和推理機制應支持對知識庫高效搜索，使得智能系統(tǒng)能夠迅速地感知事物之間關系和變化；同步很快地從知識庫中找到有關知識。便于推理，要能夠從己有知識中推出需要答案和結論。17第17頁2.1.6知識分類形態(tài)性知識、內容性知識、效用性知識三者綜合，組成了知識完整概念18第18頁第二章知識表達辦法2.1知識與知識表達概念

2.2狀態(tài)空間法2.3問題歸約法2.4謂詞邏輯法2.5語義網(wǎng)絡法2.6框架表達2.7本體技術2.8過程表達2.9小結19第19頁2.2狀態(tài)空間法

（StateSpaceRepresentation）問題求解技術主要是兩個方面：問題表達：同一問題有多種不一樣表達求解辦法1：許多問題求解辦法采取試探搜索辦法狀態(tài)空間法：基于解答空間問題表達和求解辦法狀態(tài)（state）算符（operator）狀態(tài)空間辦法2.2狀態(tài)空間法

20第20頁2.2.1

問題狀態(tài)描述狀態(tài)定義：描述某類不一樣事物間差異而引入一組最少變量q0，q1，…，qn有序集合。其矢量形式如下：Q=［q0,q1,…,qn］T式中每個元素qi(i=0,1，…，n)為集合分量，稱為狀態(tài)變量。給定每個分量一組值就得到一種詳細狀態(tài)，如：

qk=［q０k,q1k,…,qnk］T

2.1狀態(tài)空間法21第21頁2.2.1問題狀態(tài)描述初始狀態(tài)：由問題已知條件原始描述所組成狀態(tài)目標狀態(tài)：問題處理時應當達到狀態(tài)算符：使問題從一種狀態(tài)變化為另一種狀態(tài)伎倆，操作符可為走步、過程、規(guī)則、數(shù)學算子、運算符號或邏輯符號等。狀態(tài)空間：一種表達該問題所有也許狀態(tài)及其關系圖，包括三種說明集合，即所有也許問題初始狀態(tài)集合S、

操作符集合F以及目標狀態(tài)集合G?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。2.2狀態(tài)空間法22第22頁狀態(tài)空間表達概念詳釋OriginalStateMiddleStateGoalState2.2狀態(tài)空間法對一種問題狀態(tài)描述，必須確定3件事：該狀態(tài)描述方式，尤其是初始狀態(tài)描述；操作符集合及其對狀態(tài)描述作用；目標狀態(tài)描述。例如：數(shù)碼難題。23第23頁例1:三數(shù)碼難題

（3puzzleproblem）123123123312312312初始棋局目標棋局2.2狀態(tài)空間法24第24頁圖論基本概念有向圖途徑代價圖顯示說明圖隱示說明2.2.2狀態(tài)圖示法AB2.2狀態(tài)空間法25第25頁圖論基本概念有向圖(directedgraph)：節(jié)點(node)：圖形上匯合點，用來表達狀態(tài)、事件和時間關系匯合，也可用來批示通路匯合；后繼節(jié)點(descendantnode)與父輩節(jié)點(parentnode)：假如某條弧線從節(jié)點ni指向節(jié)點nj，那么節(jié)點nj就叫做節(jié)點ni后繼節(jié)點或后裔，而節(jié)點ni叫做節(jié)點nj父輩節(jié)點或祖先?；【€(arc)：節(jié)點間連接線；有向圖(directedgraph)：圖由節(jié)點（不一定是有限節(jié)點）集合構。一對節(jié)點用弧線連接起來，從一種節(jié)點指向另一種節(jié)點。

2.2狀態(tài)空間法

26第26頁圖論基本概念途徑：某個節(jié)點序列(n1,n2,…,nk)，當j=2，3，…，k時，假如對于每一種nj-1都有一種后繼節(jié)點nj存在，那么就把這個節(jié)點序列叫做從節(jié)點n1至節(jié)點nk長度為k途徑。假如從節(jié)點ni到節(jié)點nj存在有一條路經(jīng)，則稱nj是從ni可達成節(jié)點。尋找從一種狀態(tài)變換成另一種狀態(tài)某個算符序列問題等價于謀求圖某一途徑問題。

2.2狀態(tài)空間法

27第27頁圖論基本概念代價：衡量狀態(tài)之間轉變所需時間、精力等量化值。用c(ni,nj)來表達從節(jié)點ni指向節(jié)點nj弧線代價。兩節(jié)點間途徑代價等于連接該途徑上各節(jié)點所有弧線代價之和。對于最優(yōu)化問題，就要找兩節(jié)點間具有最小代價途徑。顯式表達：各節(jié)點及其具有代價弧線由一張表白確給出。此表也許列出該圖中每一節(jié)點、它后繼節(jié)點以及連接弧線代價。問題：對于大型圖和具有沒有限節(jié)點集合圖不適用。

2.2狀態(tài)空間法

28第28頁圖論基本概念

隱式表示：起始節(jié)點無限集合{si}和后繼節(jié)點算符Γ是已知。算符Γ能作用于任一節(jié)點以產(chǎn)生該節(jié)點所有后繼節(jié)點和各連接弧線代價。1節(jié)點擴展：將后繼算符Γ應用于節(jié)點過程，就是擴展一個節(jié)點過程。問題求解：搜索某個狀態(tài)空間以求得算符序列一個解答過程，就對應于使隱式圖足夠大一部分變?yōu)轱@示方便包括目標節(jié)點過程。優(yōu)化：問題表示對求解工作量有很大影響。優(yōu)化問題表示使狀態(tài)空間小而簡單，從而便于求解。許多似乎很難問題，當表示適當初就也許具有小而簡單狀態(tài)空間。2.2狀態(tài)空間法

29第29頁嘗試多種不一樣走步，直到偶爾得到目標棋局為止。

1

2

3

8

4

7

6

5目標狀態(tài)例2：九宮排序（八數(shù)碼問題）2.2狀態(tài)空間法

12

38

47

652

31

8

47

6

5初始狀態(tài)2

31

8

47

6

52

31

8

47

6

52

31

8

47

6

52

8

31

47

6

52

31

8

47652

341876530第30頁規(guī)則：假如針對每個數(shù)碼來要求規(guī)則(上下左右移動)，則需要8*4=32條規(guī)則，假如針對空格來要求規(guī)則，則只需要4條規(guī)則。R1：IF

空格上方有棋THEN

空格上移R2：IF

空格右方有棋THEN

空格右移R3：IF

空格下方有棋THEN

空格下移R4：IF

空格左方有棋THEN

空格左移求解辦法：首先把適用算符用于初始狀態(tài)，以產(chǎn)生新狀態(tài)；然后，再把另某些適用算符用于這些新狀態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標狀態(tài)為止。2.2狀態(tài)空間法

31第31頁九宮排序（寬度優(yōu)先搜索）23184765

231847652831476523184765283147652831647528314765283164752831647528371465

8321476528143765283145761237846512384765125673123847658432第32頁九宮排序（深度優(yōu)先搜索）23184765

231847652831476523184765283147652831647528314765283164752831647528371465

83214765281437652831457612378465123847652836417528316754832147652837146528143765283145761238476523456789abcd133第33頁2.2.3狀態(tài)空間表達舉例產(chǎn)生式系統(tǒng)（productionsystem）一種總數(shù)據(jù)庫：它具有與詳細任務有關信息伴隨應用情況不一樣，這些數(shù)據(jù)庫也許簡單，或許復雜。一套規(guī)則：它對數(shù)據(jù)庫進行操作運算。每條規(guī)則由左部鑒別規(guī)則適用性或先決條件以及右部描述規(guī)則應用時所完成動作。一種控制策略：它確定應當采取哪一條適用規(guī)則，并且當數(shù)據(jù)庫終止條件滿足時，就停頓計算。2.1狀態(tài)空間法34第34頁用顯式說明（列表）表達狀態(tài)圖，表中放有旅行商通過都市，表中最后一種元素就是旅行商目前所在都市。初始數(shù)據(jù)庫：（A）目標數(shù)據(jù)庫：（A,…….,A)規(guī)則：R1：IF

沒有去過B

THEN

下一步去BR2：IF

沒有去過C

THEN

下一步去CR3：IF

沒有去過D

THEN

下一步去DR4：IF

沒有去過E

THEN

下一步去ER5：IF

都去過了THEN

下一步去AA5722341

431BEDC例3：旅行商問題2.2狀態(tài)空間法

35第35頁2.2.3狀態(tài)空間表達舉例產(chǎn)生式系統(tǒng)（productionsystem）數(shù)據(jù)庫（事實庫）：具有與詳細任務有關信息,伴隨應用情況不一樣，這些數(shù)據(jù)庫也許簡單，或許復雜。規(guī)則（知識庫）：它對數(shù)據(jù)庫進行操作運算。每條規(guī)則由左部鑒別規(guī)則適用性或前提條件以及右部描述規(guī)則應用時所完成操作?？刂撇呗?：它確定應當采取哪一條適用規(guī)則，并且當數(shù)據(jù)庫終止條件滿足時，就停頓計算。2.2狀態(tài)空間法36第36頁例4：猴子和香蕉問題在一種房間內有一只猴子（可把這只猴子看做一種機器人）、一種箱子和一束香蕉。香蕉掛在天花板下方，但猴子高度不足以遇到它。那么猴子如何才能摘到香蕉呢？2.2狀態(tài)空間法1.綜合數(shù)據(jù)庫：用一種四元表列(W,x,Y,z)來表達這個問題狀態(tài)：W：猴子水平位置；X：當猴子在箱子頂上時x=1；不然x=0；Y：箱子水平位置，Z：當猴子摘到香蕉時z=1；不然z=037第37頁2.2狀態(tài)空間法pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）（2）climbbox猴子爬上箱頂，即有（W，0，W，z）climbbox（W，1，W，z）（3）grasp猴子摘到香蕉，即有（c，1，c，0）grasp（c，1，c，1）

（4）goto（U）表達猴子走到水平位置（W，0，Y，z）goto（U）（U，0，Y，z）（1）2.規(guī)則庫這個問題操作（算符）以及產(chǎn)生式規(guī)則表達如下：38第38頁2.2狀態(tài)空間法3.控制策略試探性方式4.初始條件初始狀態(tài)為(a,0,b,0)5.結束條件達成狀態(tài)(c,1,c,1)abc(a,0,b,0)初始狀態(tài)

猴子香蕉箱子goto(b)

猴子香蕉箱子

(b,0,b,0)climbbox

pushbox(c)

(c,0,c,0)goto(U)goto(U)pushbox(V)

climbbox

(c,1,c,0)

grasp(c,1,c,1)目標狀態(tài)

Ha!Ha!求解成果：該初始狀態(tài)變換為目標狀態(tài)操作序列{goto(b),pushbox(c),climbbox,grasp}狀態(tài)空間圖(求解過程1):39第39頁例5：設字符轉換規(guī)則A∧B→C，A∧C→D，B∧C→G，B∧E→F，D→E。目前已知：A和B，求：F。1.綜合數(shù)據(jù)庫3.控制策略{x}，其中x為字符次序排隊2.規(guī)則集(用產(chǎn)生式系統(tǒng)來描述）4.初始條件IFA∧BTHENC

{A，B}

IFA∧CTHEND

5.結束條件IFB∧CTHENG

F∈{x}IFB∧ETHENFIFDTHENE40第40頁1、IF

A∧B

THEN

C2、IF

A∧C

THEN

D3、IF

B∧C

THEN

G4、IF

B∧E

THEN

F5、IF

D

THEN

E

初始條件{A，B}

結束條件F∈{x}

A,B,C,D（3）（5）（2）（3）

A,B

A,B,C（1）

A,B,C,D,G,E,F

A,B,C,D,G,E（4）

A,B,C,D,G（5）初始狀態(tài)例3問題狀態(tài)空間圖41第41頁N個傳教士，N個野人，一條船，可同步乘坐k個人乘渡。傳教士為安全起見，應如何要求擺渡方案，使得任何時刻，當傳教士與野人在同一地點(河兩岸以及船上)時，野人數(shù)目總是不超出傳教士數(shù)目。傳教士與野人均可擺渡。左岸右岸M30C30B10左岸右岸M03C03B01初始狀態(tài)目標狀態(tài)例6：傳教士與野人問題（M-C問題）：以N=3(傳教士或野人數(shù))，k=2(每條船載人數(shù))為例求解。42第42頁求解過程如下：1.綜合數(shù)據(jù)庫用(m,c,b)表達左岸傳教士人數(shù)、野人人數(shù)和船狀態(tài)（b=0無船，b=1有船）：0≤m,c≤3,b∈{0,1}。2.規(guī)則集IF(m,c,1)THEN(m-1,c,0)

IF

(m,

c,

0)

THEN

(m+1,

c,

1)IF

(m,c,

1)

THEN

(m,

c-1,

0)

IF

(m,

c,

0)

THEN

(m,

c+1,

1)IF(m,c,1)THEN(m-1,c-1,0)

IF

(m,

c,

0)

THEN

(m+1,

c+1,

1)

IF

(m,c,

1)

THEN

(m-2,

c,

0)

IF(m,c,0)THEN(m+2,c,1)IF(m,c,1)THEN(m,c-2,0)

IF

(m,

c,

0)

THEN

(m,

c+2,

1)

太繁瑣！43第43頁也能夠定義為：IF(m,c,1)∧(1≤i+j≤2)∧{(c-j≤m-i∨

m-i=0)∧(3-c+j≤3-m+i

∨3-m+i=0)}THEN(m-i,c-j,0)IF(m,c,0)∧(1≤i+j≤2)∧{(c+j≤m+i∨m+i=0)∧(3-c-j≤3-m-i

∨3-m-i=0)}THEN(m+i,c+j,0)3.控制策略

試探性方式4.初始條件

(3,3,1)5.結束條件

（0,0,0）44第44頁6.繪制狀態(tài)空間圖(3,3,1)(2,2,0)(3,1,0)(0,2,1)(1,1,1)(0,3,1)(2,2,1)(3,1,1)(3,2,1)(3,0,0)(3,2,0)(0,0,0)(0,1,0)(0,2,0)(1,1,0)(1)IF(m,c,1)THEN(m-1,c,0)

(2)IF

(m,

c,

0)

THEN

(m+1,

c,

1)(3)IF

(m,

c,

1)

THEN

(m,

c-1,

0)

(4)IF

(m,

c,

0)

THEN

(m,

c+1,

1)(5)IF(m,c,1)THEN(m-1,c-1,0)

(6)IF

(m,

c,

0)

THEN

(m+1,c+1,1)

(7)IF

(m,

c,

1)

THEN

(m-2,

c,

0)

(8)IF(m,

c,0)THEN(m+2,c,1)(9)IF(m,c,1)THEN(m,c-2,0)(10)IF

(m,

c,

0)

THEN

(m,

c+2,

1)(3)(9)(9)(5)(7)(9)(7)(5)(9)(4)(2)(4)(6)(4)(6)(4)45第45頁2.3問題歸約法

（ProblemReductionRepresentation）子問題1子問題n原始問題子問題集本原問題問題歸約是另一種基于狀態(tài)空間問題描述與求解辦法。已知問題描述，通過一系列變換把此問題最后變?yōu)橐环N子問題集合；這些子問題解能夠直接得到，從而處理了初始問題。46第46頁例1：假定會求矩形面積，目前要求如圖所示五邊形面積。II①②2III

③

3

I1求五邊形面積?

1面積?

2面積?

3面積①面積②面積③面積I面積II面積III面積47第47頁問題歸約表達組成部分：一種初始問題描述；一套把問題變換為子問題操作符；一套本原問題描述。問題歸約實質：從目標(要處理問題)出發(fā)逆向推理，建立子問題以及子問題子問題，直至最后把初始問題歸約為一種平凡本原問題集合。2.3

問題規(guī)約法48第48頁2.3.1問題歸約描述

（ProblemReductionDescription）1.梵塔難題12.3

問題規(guī)約法最初，所有3個圓從大B到小堆放在第1個柱子上，要求把所有圓盤從大到小堆放在第3個柱子上。每次只許移動一種，并且只能先搬動柱子頂上圓盤，還不能把大圓盤堆放在較小圓盤上。CC

AB初始狀態(tài)

AB目標狀態(tài)1

2

349第49頁梵塔難題求解12.3

問題規(guī)約法把原始問題規(guī)約為一種較簡單問題集合：要把所有圓盤移到柱子3，首先把圓盤C移至柱子3；并且在其之前，要求柱子3是空。只有移開A、B之后，才能移動C；且A、B最佳不要移至柱子3，不然C不能移至柱子3。因此首先把A、B移至柱子2上。然后，把C從柱子1移至柱子3，并繼續(xù)處理難題其他部分。CC

AB初始配備

AB目標配備1

2

350第50頁C

ABC

AB（3,3,3）目標配備C

ABC

AB子問題(1,1,1)初始配備C

AB(1,2,2)(3,2,2)

(3,3,3)上述分析允許把原始難題歸約（簡化）為3個子難題：移動圓盤A、B至柱子2雙圓盤難題。移動圓盤C至柱子3單元盤難題。移到圓盤A、B至柱子3雙圓盤難題。①②③51第51頁梵塔問題歸約圖1（113）（123）

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

2.3

問題規(guī)約法將所有子問題歸約為本原問題，最后畫出與或圖(AND/ORgraph)，來說明如何由問題歸約法求得問題解答。52第52頁2.問題歸約描述問題歸約辦法應用算符來將問題描述變換為子為題描述。問題描述能夠有多種數(shù)據(jù)構造形式：表列、樹、字符串、矢量、數(shù)組等。對于梵塔難題，其子問題能夠用一種包括兩個數(shù)列表列來描述：[(113),(333)]表達把初始配備(1,1,3)變換為目標配備(3,3,3)1。能夠用狀態(tài)空間表達三元組(S,F,G)來要求與描述問題。可將有關子問題當作狀態(tài)空間中兩個一定“腳踏石”之間尋找途徑問題來處理。對于梵塔難題，子問題[(111)→(122)]，[(122)→(322)],[(322)→(333)]要求了最后解答途徑要通過腳踏石狀態(tài)(122)和(322)。53第53頁問題歸約法與狀態(tài)空間法之間不一樣點與關系：問題歸約能夠應用狀態(tài)、算符和目標這些表達法來描述問題，這并不意味問題歸約和狀態(tài)空間法是同樣。事實上，遞增狀態(tài)空間搜索應用某個問題歸約一般形式，而問題歸約法是比狀態(tài)空間法更一般一種問題求解辦法。把問題描述變換為一種歸約或后續(xù)問題描述集合，這是由問題歸約算符進行。變換得到所有后續(xù)問題解就是父輩問題一種解所用問題歸約目標是最后產(chǎn)生具有顯著解答本原問題。這些問題也許是能夠由狀態(tài)空間搜索中走動一步來處理問題，或者也許是其他具有已知解答更復雜問題。本源問題除了對終止搜索過程起到顯著作用外，有時還被用來限制歸約過程中產(chǎn)生后續(xù)問題替代集合。154第54頁2.2.2與或圖表達1.與圖、或圖、與或圖與或圖能夠方便用一種類似于圖構造來表達把問題歸約為后繼問題替代集合，畫出歸約問題圖（與或圖）1。2.3

問題規(guī)約法ABCD與圖ABC或圖55第55頁2.3

問題規(guī)約法BCDEFGAHMBCDEFGAN圖2.6子問題替代集合構造圖圖2.7一種與或圖56第56頁2.與或圖術語2.3

問題規(guī)約法與或圖：1由與節(jié)點及或節(jié)點組成構造圖模擬問題歸約辦法有關構造是一種與或圖在狀態(tài)空間搜索中，主線不出現(xiàn)任何與節(jié)點。是否存在與節(jié)點也就成為區(qū)分問題歸約和狀態(tài)空間兩種問題求解辦法主要根據(jù)。在描述與或圖時，仍然采取如父輩節(jié)點、后繼結點和連接兩節(jié)點弧線等術語。57第57頁2.3

問題規(guī)約法HMBCDEFGAN父節(jié)點與節(jié)點:只有處理所有子問題，才能處理其父輩問題節(jié)點集合，各個結點之間用一段小圓弧連接標識，如(B,C)和(D,E,F)?；【€或節(jié)點:只要處理某個問題就可處理其父輩問題節(jié)點集合，如(M,N,H)。子節(jié)點終葉節(jié)點:對應于本原問題節(jié)點，它沒有后裔1。58第58頁2.3

問題規(guī)約法與或圖中一種可解節(jié)點一般定義可歸納如下：終葉節(jié)點必然是可解節(jié)點(由于它們是本原問題)。若某個非終葉節(jié)點具有或后繼節(jié)點，則只要當其后繼節(jié)點有一種是可解時，此非終葉節(jié)點就是可解。若某個非終葉節(jié)點具有與后繼節(jié)點，則只有當其后繼節(jié)點所有為可解時，此非終葉節(jié)點才是可解。與或圖中不可解節(jié)點一般定義可歸納如下：沒有后裔非終葉節(jié)點為不可解節(jié)點。若某個非終葉節(jié)點具有或后繼節(jié)點，則只有當其所有后裔為不可解時，此非終葉節(jié)點才是不可解。若某個非終葉節(jié)點具有與后繼節(jié)點，則只要當其后裔最少有一種為不可解時，此非終葉節(jié)點就是不可解。59第59頁與或圖例子2.3

問題規(guī)約法圖2.8與或圖例子（顯式圖）ttttttttt（a）（b）有解節(jié)點(用小圓點表達）無解節(jié)點(用小圓點表達)終葉節(jié)點(用字母t表達)60第60頁與或圖組成規(guī)則2.3

問題規(guī)約法與或圖中每個節(jié)點代表一種要處理單一問題或問題集合。與或圖中起始節(jié)點對應于原始問題。對應于本源問題節(jié)點，叫做終葉節(jié)點，它沒有后裔。對于把算符應用于問題A每種也許情況，都把問題變換為一種子問題集合；有向弧線自A指向后繼結點，表達所求得子問題集合。對于與節(jié)點，需要用圓弧將有向弧線連接起來。而或節(jié)點不需要。代表子問題集合中間或節(jié)點能夠省略。備注：與狀態(tài)空間問題求解同樣，很少使用顯式圖來搜索，而是用由初始問題描述和消解算符所定義隱式圖來搜索。這樣，一種問題求解時只要生成與或圖足夠部分就能夠了。61第61頁(S,F,Gf)(S,F,G)({g},F,G)問題歸約機理關鍵算符：當應用某個算符是問題求解決定性步驟時，就稱該算符為關鍵算符。當確定下來某個關鍵算符時，可用它來確定問題歸約過程。例2：假設一種狀態(tài)空間搜索問題有三元狀態(tài)(S,F,G)所要求。S為初始狀態(tài)，F(xiàn)為規(guī)則集，G為目標狀態(tài)。設f是該問題關鍵算符，則(S,F,G)第一種后裔問題是去尋找一條通向適用狀態(tài)途徑問題。設Gf表達f適用所有狀態(tài)集合，則得到原問題子問題(S,F,Gf)

。設狀態(tài)g∈Gf，則得到另一種子問題({g},F,{f(g)})。其中，f(g)表達把f應用于g而得到狀態(tài)，且f(g)∈G。由于這個問題僅僅由應用關鍵算符f來解決，因此它是本原。62第62頁例3.猴子和香蕉問題在一種房間內有一只猴子（可把這只猴子看做一種機器人）、一種箱子和一束香蕉。香蕉掛在天花板下方，但猴子高度不足以遇到它。那么猴子如何才能摘到香蕉呢？2.2狀態(tài)空間法1.綜合數(shù)據(jù)庫：用一種四元表列(W,x,Y,z)來表達這個問題狀態(tài)：W：猴子水平位置；X：當猴子在箱子頂上時x=1；不然x=0；Y：箱子水平位置，Z：當猴子摘到香蕉時z=1；不然z=063第63頁2.2狀態(tài)空間法pushbox（V）猴子把箱子推到水平位置V，即有f2：（W，0，W，z）pushbox(V)（V，0，V，z）（2）climbbox猴子爬上箱頂，即有f3：（W，0，W，z）climbbox（W，1，W，z）（3）grasp猴子摘到香蕉，即有

f4：（c，1，c，0）grasp（c，1，c，1）

（4）goto（U）表達猴子走到水平位置f1：W，0，Y，z）goto（U）（U，0，Y，z）（1）這個問題操作（算符）以及產(chǎn)生式規(guī)則表達如下：令F={f1,f2,f3,f4}是4個算符集合，G是滿足目標條件狀態(tài)集合。則初始問題為：({(a,0,b,0)},F,G)。64第64頁

關鍵算符是f4。假設Gf4是適用于算符f4狀態(tài)集合，則初始問題變?yōu)椋?{(a,0,b,0)},Gf4)和(S1,

G)。這里S1=

(c,1,c,0),

S1必須是求解前一問題得到狀態(tài)?！镜谝徊健空谊P鍵算符【第二步】求解問題({(a,0,b,0)},Gf4)由(a,0,b,0)所描述狀態(tài)不在Gf4中，由于：①箱子不在c處；②猴子不在c處；③猴子不在箱子上。則下列算符為該問題關鍵算符：f2:pushbox(c)，f1:goto(c)，f3:climbbox應用關鍵算符產(chǎn)生各歸約問題子問題集合?！镜谌健肯忍幚韱栴}①，應用f2使問題({(a,0,b,0)},

Gf4)變?yōu)閱栴}({(a,0,b,0)},

Gf2)和(S11,Gf4)，其中S11是應用f2得到狀態(tài)(c,0,c,0)。65第65頁計算({(a,0,b,0)},Gf2)問題差異，此差異為猴子不在b處。則得到關鍵算符f1：goto(b)，應用f1得到問題({(a,0,b,0)},Gf2)變?yōu)閱栴}({(a,0,b,0)},Gf1)和(S111,Gf2)。S111是應用f1得到狀態(tài)(b,0,b,0)。由于狀態(tài)(a,0,b,0)在規(guī)則f1域內，因此問題({(a,0,b,0)},Gf1)已是本原問題。由于狀態(tài)S111=(b,0,b,0)在規(guī)則f2域內，則問題({(b,0,b,0)},Gf2)也是本原問題，且問題①

目標狀態(tài)S11為(c,0,c,0)。至此，所有問題得到處理。最后畫出與或圖。66第66頁

(c,1,c,0)

?

(c,1,c,1)(a,0,b,0)

?

(c,0,c,0)(c,0,c,0)

?

(c,1,c,0)(a,0,b,0)

?

(c,1,c,1)

f4(a,0,b,0)

?

(c,1,c,0)

f2f3f1(a,0,b,0)

?

(b,0,b,0)(b,0,b,0)

?

(c,0,c,0)用問題歸約法求解猴子和香蕉問題與或圖67第67頁用要證問題與已知規(guī)則結論相匹配匹配操作：將其條件與要證問題條件相比較若條件已存在，則為本原問題，該問題可解；若缺乏條件，則將該條件作為要證子問題，原問題條件仍為新子問題條件，繼續(xù)歸約。如對一種問題同步有幾條本原問題描述能夠匹配,則能夠對該問題節(jié)點進行或擴展。歸約操作辦法:68第68頁例4：求證一種角平分線上點與該角兩邊距離相等.已知：∠DBA=∠DBC，BA⊥AD,BC⊥CD，DB為一線段，?BAD和?BCD為三角形，試用問題歸約法證明：AD=CD。假設：已有知識是:若兩個三角形有一個等長邊，且相鄰兩個角相等,則兩個三角形全等。即：設?X1X2X3，?Y1Y2Y3，若：X3X1=Y3Y1,∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3,則：?X1X2X3??Y1Y2Y3另外，已有知識尚有：全等三角形邊都等長；兩線垂直，夾角為90度；三角形內角和為180度，即：∠X1X2X3+∠X2X3X1+∠X3X1X2=180。或：∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3?∠X2X3X1=∠Y2Y3Y1ABCD69第69頁

練習-答案問題表達：∠DBA=∠DBC,BA⊥AD,BC⊥CD,?BAD,?BCD?AD=CDP1：∠X1=90o,∠X2=90o?∠X1=∠X2P2：?X1X2X3，?Y1Y2Y3，X3X1=Y3Y1，∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3??X1X2X3??Y1Y2Y3P3：X1X2⊥X2X3?∠X1X2X3=90oP4：?X1X2X3??Y1Y2Y3?X2X3=Y2Y3P5：?X1X2X3?∠X1X2X3+∠X2X3X1+∠X3X1X2=180oP6：?X1X2X3,?Y1Y2Y3,∠X3X1X2=∠Y3Y1Y2,∠X1X2X3=∠Y1Y2Y3?∠X2X3X1=∠Y2Y3Y1ABCD70第70頁

BA⊥AD

?∠BAD=

90oBC⊥CD

?∠BCD=

90o

{S}?

AD=CD

P4{S}

?

?

BAD?

?

BCDP2∠BAD,∠BCD=

90o?∠BAD=

∠BCDDB=DB,

∠BDA=∠BDC,

∠DBA=

∠DBC?

?

BAD

?

?

BCD

{S}

?

∠BAD=

∠BCD

P1,

P3{S}

?∠DBA=∠DBC

設{S}={∠DBA=

∠DBC,

BA⊥AD,BC⊥CD,

?BAD,

?

BCD

}。

?

BAD

?

?

BCD

?

AD=CD{S}

?

∠BDA=

∠BDC

P6

ADC71第71頁問題歸約法小結狀態(tài)空間法與問題歸約法比較狀態(tài)空間——問題空間狀態(tài)空間圖——與或圖操作——歸約求解途徑——本原問題歸約就是化簡，即把復雜問題分解為若干子問題，且使得：每個子問題比原問題好解；這些子問題處理了，原問題就處理了問題歸約法描述：用與或圖72第72頁2.4謂詞邏輯表達2.4謂詞邏輯法

人工智能中用到邏輯可劃分為兩大類（如下列圖所示）：典型命題邏輯和一階謂詞邏輯（又稱為二值邏輯）1：任何一種命題真值為“真”或“假”，二者必居其一。非典型邏輯：三值邏輯、多值邏輯、含糊邏輯等。

謂詞邏輯是在命題邏輯基礎上發(fā)展起來，命題邏輯可看作是謂詞邏輯一種特殊形式。含糊邏輯邏輯典型邏輯（二值邏輯）非典型邏輯三值邏輯一階謂詞邏輯典型命題邏輯多值邏輯73第73頁2.4.1命題命題（proposition）：一種非真即假陳說句。若命題意義為真*，稱它真值為真，記為T。

若命題意義為假*，稱它真值為假，記為F。一種命題可在一種條件下為真，在另一種條件下為假*。命題邏輯*：研究命題及命題之間關系符號邏輯系統(tǒng)*。命題邏輯表達法：無法把它所描述事物構造及邏輯特性反應出來*，也不能把不一樣事物間共同特性表述出來*。例如：3<5

例如：太陽從西邊升起

例:1＋1＝10P：北京是中華人民共和國首都P：老李是小李爸爸P：李白是詩人Q：杜甫也是詩人74第74頁2.4.2謂詞命題邏輯（propositionallogic）能夠把客觀世界多種事實表達為命題邏輯。不過，它具有較大不足，不適合于表達比較復雜問題。謂詞邏輯（predicatelogic）允許體現(xiàn)那些無法用命題邏輯體現(xiàn)事情。更詳細地說，一階謂詞演算（firstorderpredicatecalculus）是一種形式語言，其主線目標在于把數(shù)學中邏輯論證符號化。假如能夠采取數(shù)學演繹方式證明一種新語句是從那些已知正確語句導出，那么也就能斷定這個新語句也是正確。

75第75頁2.4.2謂詞謂詞邏輯基本組成部分是謂詞符號、變量符號、函數(shù)符號和常量符號，并用園括弧、方括弧、花括弧和逗號隔開，以表達論域內關系。一般，原子公式由若干謂詞符號和個體組成。謂詞一般形式：P(x1,x2,…,xn)個體x1,x2,…,xn

：某個獨立存在事物或者某個抽象概念；謂詞名P：刻畫個體性質、狀態(tài)或個體間關系。（1）個體是常量：一種或者一組指定個體。

“老張是一種教師”：一元謂詞Teacher(Zhang)“5>3”：二元謂詞

Greater(5,3)“Smith作為一種工程師為IBM工作”：三元謂詞

Works(Smith,IBM,engineer)76第76頁（2）個體是變元（變量）：沒有指定一種或者一組個體。*“小李爸爸是教師”：Teacher(father(Li))（3）個體是函數(shù)：一種個體到另一種個體映射*?！皒<5”

：Less(x,5)

（4）個體是謂詞*Smith作為一種工程師為IBM工作”：二階謂詞Works(engineer(Smith),IBM)77第77頁2.4.3謂詞公式PLF

1.連接詞（連詞）（1）﹁：“否認”（negation）或“非”*。（2）∨：“析取”（disjunction）——或*。（3）∧：“合取”（conjunction）——與*?！皺C器人不在2號房間”：﹁Inroom(robot,r2)“李明打籃球或踢足球”：Plays(Liming,basketball)∨

Plays(Liming,football)“我喜歡音樂和繪畫”：

Like(I,music)∧

Like(I,painting)78第78頁（4）→：“蘊含”(implication)或“條件”(condition)*

表達“假如-那么”語句。IF前項（左式）→THEN后項（右式）若后項取值為T，則不論前項值是否為T，蘊涵均為T。若前項取值為F，則不論后項取值如何，蘊涵均為T。不然，蘊涵為F。一般地：P→Q:“P→Q為假，當且僅當P為真，Q為假”“假如劉華跑得最快，那么他取得冠軍?！保?/p>

RUNS(Liuhua，faster)→WINS(Liuhua，champion)“假如該書是何平，那么它是藍色（封面）?！保?/p>

OWNS(HEPING，BOOK-1)

→COLOR(BOOK-1,BLUE)79第79頁連接詞謂詞邏輯真值表80第80頁2.4.3謂詞公式2.量詞（quantifier）（1）全稱量詞（universalquantifier）（?x）：“對個體域中所有（或任一種）個體x

”?！八袡C器人都是灰色”：

(?x)[ROBOT(x)→

COLOR(x，GRAY)]（2）存在量詞（existentialquantifier）（彐

x）：“在個體域中存在個體

x

”?！?號房間有個物體”：（彐x）INROOM（x，r1）81第81頁全稱量詞和存在量詞舉例：

(?x)(彐y)Friend(x,y)表達對于個體域中任何個體x都存在個體y，x與y是朋友。

(彐x)(?y)Friend(x,y)表達在個體域中存在個體x，與個體域中任何個體y都是朋友。

(彐x)(彐y)F(x,y)表達在個體域中存在個體x與個體y，x與y是朋友。

(?x)(?y)Friend(x,y)表達對于個體域中任何兩個個體x和y，x與y都是朋友。

82第82頁全稱量詞和存在量詞出現(xiàn)次序將影響命題意思。例如：

(?x)(彐y)(Employee(x)→

Manager(y,x)):

“每個雇員都有一種經(jīng)理。”

(彐y)(?x)(Employee(x)→

Manager(y,x)):

“有一種人是所有雇員經(jīng)理?！?3第83頁3.謂詞公式定義2.2可按下述規(guī)則得到謂詞演算謂詞公式（合式公式）：單個謂詞是謂詞公式，稱為原子謂詞公式。若A是謂詞公式，則﹁A也是謂詞公式。若A，B都是謂詞公式，則A∧B，A∨B，A→B，A

B也都是謂詞公式。若A是謂詞公式，則(?x)A，(彐(

x)A也是謂詞公式。有限步應用（1）－（4）生成公式也是謂詞公式。*1連接詞優(yōu)先級別從高到低排列：

﹁，∧，∨，→，

必須指出是，本課程所用到謂詞演算為一階謂詞演算，不允許對謂詞符號或函數(shù)進行量化。例如在一階謂詞演算中，(?P)P(A)這樣某些公式就不是合式公式。84第84頁4．量詞轄域

量詞轄域：位于量詞背面單個謂詞或者用括弧括起來謂詞公式。約束變元與自由變元：轄域內與量詞中同名變元稱為約束變元，不一樣名變元稱為自由變元。例如：

(彐x)(P(x,y)→Q(x,y))∨R(x,y)(P(x,y)→

Q(x,y))：(彐x)轄域，轄域內變元x是受（彐x）約束變元，R(x,y)中x是自由變元。公式中所有y都是自由變元。

85第85頁例：對于所有x，假如x是整數(shù)，則x或為正或者為負。解：用I(x)表達“x是整數(shù)”，P(x)表達“x是正數(shù)”，N(x)表達“x是負數(shù)”。則得到：(?x)I(x)→P(x)∨N(x)例：通過兩個不一樣點a和b直線L1和L2是同始終線。解：用T(x)表達x是點，L(x)表達x是線；P(x,y,z)表達直線x通過點y和z。E(x,y)表達x和y是同始終線。則得到：T(a)∧T(b)∧L(L1)∧L(L2)∧P(L1,a,b)∧P(L2,a,b)→E(L1,L2)例：有些小孩長高了。解：C(x)表達x是小孩，BH(x)表達x長高了。則得到：(?x)(C(x)∧BH(x))

等價于：~[(?x)(C(x)∧~BH(x))]86第86頁例：“最少有一偶數(shù)是素數(shù)”。解：用A(x)表達x是偶數(shù)，B(x)表達x是素數(shù)。則：

(?x)(A(x)∧B(x))例：“最少有一偶數(shù)并且最少有一素數(shù)”。

(?x)A(x)∧(?x)B(x)例：用謂詞演算來表達下面英文句子：*1

Foreverysetx,thereisasety,suchthatthecardinalityofythe

is

greaterthanthecardinalityofx.CARD(y,v)CARD(x,u)G(v,u)?x{SET(x)→(?y)(?u)(?v)[SET(y)∧CARD(x,u)∧CARD(y,v)∧G(v,u)]}?xSET(x)?ySET(y)87第87頁例：凡是人都要學習。(?x)(HUMAN(x)→NEED-STUDY(x))例：有一種人弟兄是老師。

(?x)TEACHER(brother(x))例：“小孩都要長高”與“有個小孩長高了”不同樣：一種表達一種結論或觀點，包括著條件和結論；一種表達事實。

(?x)(CHILD(x)→GROW-UP(x))(?x)(CHILD(x)∧GROW-UP(x))注意：①事實不能表達成推理。

②變量和函數(shù)一般用小寫字母表達。88第88頁2.4.4謂詞公式性質1.謂詞公式解釋謂詞公式在個體域上解釋：個體域中實體對謂詞演算體現(xiàn)式中每個常量、變量、謂詞和函數(shù)符號指派*。Friends(george,x)Friends(george,susie)TFriends(george,kate)F對于每一種解釋，謂詞公式都可求出一種真值（T或F）。89第89頁2.謂詞公式永真性、可滿足性、不可滿足性

2.謂詞公式永真性、可滿足性、不可滿足性

定義2.5對于謂詞公式P，假如最少存在一種解釋使得P在此解釋下真值為T，則稱P是可滿足，不然，則稱P是不可滿足。

定義2.4假如謂詞公式P對個體域D上任何一種解釋都取得真值F，則稱P在D上是永假；假如P在每個非空個體域上均永假，則稱P永假。

定義2.3假如謂詞公式P對個體域D上任何一種解釋都取得真值T，則稱P在D上是永真；假如P在每個非空個體域上均永真，則稱P永真。90第90頁3.謂詞公式等價性定義2.6設P與Q是兩個謂詞公式，D是共同個體域，若對D上任一解釋，P與Q都有相同真值，則稱公式P和Q在D上是等價。假如D是任意個體域，則稱P和Q是等價，記為P?Q

。

（3）德.摩根律(De.Morgen)又叫反演律

﹁

(P∧Q)?﹁

P∨﹁Q;﹁

(P∨Q)?﹁

P∧﹁Q（2）連接詞化歸律和(7)逆否律P→Q?﹁

P∨Q；P→Q?﹁

P→﹁Q（8）量詞轉換律

?(?x)P(x)?(?x)(?P(x))；?(?x)(P(x)?(?x)(?P(x))注：P38、P39其他等價式。3.謂詞公式等價性91第91頁

4.謂詞公式永真蘊含定義2.7對于謂詞公式P與Q，假如P→Q永真，則稱公式P永真蘊含Q，且稱Q為P邏輯結論，稱P為Q前提，記為P?Q。（1）假言（或假元）推理：P,P→Q?Q（2）拒取式推理：﹁Q,P→Q?﹁P*1

（3）假言三段論:P→Q,Q→R?P→R（4）全稱固化（或全稱化推理）:(?x)P(x)?P(y)

（5）存在固化:(?x)P(x)?P(y)92第92頁(1)假言推理假言推理是根據(jù)假言命題邏輯性質進行推理。分為充足條件假言推理，必要條件假言推理和充足必要條件假言推理三種。充足條件假言推理是根據(jù)充足條件假言命題邏輯性質進行推理。充足條件假言推理有兩條規(guī)則：規(guī)則1：肯定前件，就要肯定后件；否認前件，不能否認后件。規(guī)則2：否認后件，就要否認前件；肯定后件，不能肯定前件。93第93頁根據(jù)規(guī)則，充足條件假言推理有兩個正確形式：

（1）肯定前件式

假如P，那么QP___________

因此，Q（2）否認后件式假如P，那么Q非Q___________因此，非P例子：94第94頁充足條件假言推理假如誰驕傲自滿，那么他就要落后；小張驕傲自滿，因此，小張肯定要落后。假如誰得了肺炎，他就一定要發(fā)熱；小李沒發(fā)熱，因此，小李沒患肺炎。例1和例2都是充足條件假言推理，前者是肯定前件式；后者是否認后件式。兩個推理都符合推理規(guī)則，因此，都是正確。

根據(jù)規(guī)則，充足條件假言推理否認前件式和肯定后件式都是無效。

例子：95第95頁假如降落物體不受外力影響，那么，它不會變化降落方向；這個物體受到了外力影響，因此，它會變化降落方向。假如趙某是走私犯，那么，他應受法律制裁；經(jīng)查明，趙某確實受到了法律制裁，因此，趙某是走私犯。

上例都是不正確充足條件假言推理，由于：例1：違反了“否認前件，不能否認后件”規(guī)則；例2：違反了“肯定后件，不能肯定前件”規(guī)則。96第96頁(2)假言三段論在邏輯中，假言三段論是服從下列形式有效論證:

P→Q.Q→R.因此,P→R.換句話說，這種論證陳說假如第一種蘊涵第二個，并且第二個蘊涵第三個，則第一種蘊涵第三個。例子：假如我不能起床，則我不能上班。假如我不能上班，則我不能得到報酬。因此，假如我不能起床，則我不能得到報酬。

97第97頁(3)全稱固化（或全稱化推理）(?x)P(x)?P(y)其中，y是個體域中任一種體，利用此永真蘊涵式可消去公式中全稱量詞。(4)存在固化

(?x)P(x)?P(y)

其中，y是個體域中某一種可使P(y)為真?zhèn)€體，利用此永真蘊涵式可消去公式中存在量詞。98第98頁2.4.4謂詞公式性質5.謂詞邏輯其他推理規(guī)則P規(guī)則：在推理任何步驟上都可引入前提。T規(guī)則：在推理過程中，假如前面步驟中有一種或多種公式永真蘊含公式S，則可把S引入推理過程中。CP規(guī)則：假如能從任意引入命題R和前提集合中推出S來，則可從前提集合推出R→S來。反證法：

定理：Q為P1,P2,…,Pn邏輯結論，當且僅當(P1

∧

P2∧,…,∧Pn)∧﹁Q是不可滿足。99第99頁例：所有人都是會死，?x(Human(x)→Die(x))

由于諸葛亮是人，

Human（Zhugeliang）因此諸葛亮是會死。

Die（Zhugeliang）

{1}?x(Human(x)→Die(x))

P規(guī)則

{2}Human（Zhugeliang）

P規(guī)則{1,2}Die（Zhugeliang）

T規(guī)則

100第100頁2.4.4置換與合一在謂詞邏輯中，有些推理規(guī)則可應用于一定合式公式和合式公式集，以產(chǎn)生新合式公式。一種主要推理規(guī)則是假元推理：W1,W1

→W2

?W2；全稱化推理：(?x)W(x)?W(A)

；同步應用假言推理和全稱化推理。1.置換運算：有體現(xiàn)式E和置換S={t1/x1,t2/x2,……,tn/xn}，用ES表達以項ti

(i=1,…,n)置換體現(xiàn)式E中出現(xiàn)變量xi。其中：每個xi都是變量，且xi≠xj(i≠j)。每個ti都是項,且ti中不能出現(xiàn)xi。置換運算規(guī)則：E中變量xi(i=1,…,n)均用ti置換。對所有變量只能一次同步置換完成。101第101頁例：體現(xiàn)式P[x,f(y),B]2個置換為：s1={z/x,w/y}，s2={A/y},則

P[x,f(y),B]s1=P[z,f(w),B]P[x,f(y),B]s2=P[x,f(A),B]例：P[x,f(y),B]2個置換為：s3={q(z)/x,A/y},s4={c/x,A/y}，則P[x,f(y),B]s3=P[q(z),f(A),B]P[x,f(y),B]s4=P[c,f(A),B]性質：①置換是可結合。用s1?s2表達兩個置換s1和s2合成，L表達某一體現(xiàn)式，則：(Ls1)s2=L(s1?s2)。并且(s1?s2)?s3=