人工智能的基本推理技術(shù).ppt

1、2020/9/1,1,基本的推理技術(shù),課程的基本內(nèi)容及要求： 基本內(nèi)容 推理的概念和類(lèi)型，推理的控制策略； 歸結(jié)反演系統(tǒng)歸結(jié)原理、歸結(jié)反演及其控制策略、應(yīng)用歸結(jié)反演求取問(wèn)題的答案等； 基于規(guī)則的演繹推理（包括正向、反向和雙向的演繹推理）。 要求 熟練掌握與運(yùn)用歸結(jié)原理； 理解各種歸結(jié)反演的控制策略； 學(xué)會(huì)如何從一歸結(jié)反演系統(tǒng)中提取回答； 掌握基于規(guī)則的演繹推理的工作過(guò)程。,2020/9/1,2,課程的安排： 1，2（2小節(jié)）節(jié)（學(xué)時(shí)） 重點(diǎn)：1節(jié)2小節(jié)；2節(jié)1小節(jié) 2（2，3小節(jié)）（學(xué)時(shí)） 重點(diǎn)：2節(jié)2，3小節(jié) 2（4小節(jié)），3（學(xué)時(shí)） 重點(diǎn)：2節(jié)（4小節(jié)）3節(jié)（1，2小節(jié)）,2020/9/1

2、,3,1 推理技術(shù)概述,確定知識(shí)表達(dá)方法將知識(shí)表示出來(lái)并存儲(chǔ)到計(jì)算機(jī)中去 表達(dá)知識(shí)并存儲(chǔ)知識(shí)目的為了更好地利用知識(shí)來(lái)解決實(shí)際問(wèn)題 利用知識(shí)進(jìn)行推理是知識(shí)利用的基礎(chǔ)；是問(wèn)題求解的主要手段 如專(zhuān)家系統(tǒng)、智能機(jī)器人、模式識(shí)別、自然語(yǔ)言理解等 本章介紹的推理歸結(jié)反演、基于規(guī)則的演繹系統(tǒng)等是基于邏輯的推理，屬于確定性推理,2020/9/1,4,1 推理技術(shù)概述,推理的概念和類(lèi)型 推理人類(lèi)求解問(wèn)題主要思維方法，其任務(wù)是利用知識(shí) 與知識(shí)表達(dá)方法的關(guān)系 推理按照某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過(guò)程。推理是由程序?qū)崿F(xiàn)的，稱(chēng)為推理機(jī) 在人工智能系統(tǒng)中，推理機(jī)利用知識(shí)庫(kù)中的知識(shí)，按一定的控制策略去求解問(wèn)題 醫(yī)療診

3、斷專(zhuān)家系統(tǒng)：知識(shí)庫(kù)中存儲(chǔ)經(jīng)驗(yàn)及醫(yī)學(xué)常識(shí)，數(shù)據(jù)庫(kù)中存放病人的癥狀、化驗(yàn)結(jié)果等初始事實(shí)，為病人診治疾病實(shí)際上就是一次推理過(guò)程即從病人的癥狀及化驗(yàn)結(jié)果等初始事實(shí)出發(fā)，利用知識(shí)庫(kù)中的知識(shí)及一定的控制策略，對(duì)病情作出診斷，并開(kāi)出醫(yī)療處方 從初始事實(shí)出發(fā)，不斷運(yùn)用知識(shí)庫(kù)中的已知知識(shí)，逐步推出結(jié)論的過(guò)程就是推理,2020/9/1,5,1 推理技術(shù)概述,推理的概念和類(lèi)型 人類(lèi)的智能活動(dòng)有多種思維方式，人工智能作為對(duì)人類(lèi)智能的模擬，相應(yīng)地也有多種推理方式推理的基本任務(wù)是從一種判斷推出另一種判斷分類(lèi) 1演繹推理、歸納推理、默認(rèn)推理 2.確定性推理、不精確推理 3單調(diào)推理、非單調(diào)推理 4啟發(fā)式推理、非啟發(fā)式推理,2

4、020/9/1,6,1 推理技術(shù)概述,推理的概念和類(lèi)型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認(rèn)推理 1）演繹推理 從全稱(chēng)判斷推出特稱(chēng)判斷或單稱(chēng)判斷的過(guò)程，即從一般到個(gè)別的推理 演繹推理中最常用的形式是三段論法（大前提和小前提，及結(jié)論） 例如： （1）所有的推理系統(tǒng)都是智能系統(tǒng)一般的知識(shí) （2）專(zhuān)家系統(tǒng)是推理系統(tǒng)個(gè)體的判斷 （3）所以，專(zhuān)家系統(tǒng)是智能系統(tǒng)新判斷 沒(méi)有增加新的知識(shí),2020/9/1,7,1 推理技術(shù)概述,推理的概念和類(lèi)型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認(rèn)推理 2）歸納推理 人們對(duì)客觀事物的認(rèn)識(shí)總是由認(rèn)識(shí)個(gè)別事物開(kāi)始，進(jìn)而認(rèn)識(shí)事物的普遍規(guī)律，其中歸納推理起了

5、重要的作用 歸納推理是從足夠多的事例中歸納出一般性結(jié)論的推理過(guò)程，是一種從個(gè)別到一般的推理過(guò)程 常用的歸納推理有簡(jiǎn)單枚舉法和類(lèi)比法,2020/9/1,8,1 推理技術(shù)概述,推理的概念和類(lèi)型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認(rèn)推理 2）歸納推理 枚舉法歸納推理是由已觀察到的事物都有某屬性，而沒(méi)有觀察到相反的事例，從而推出某類(lèi)事物都有某屬性 推理過(guò)程可以形式地表示為： S1 是 P S2 是 P Sn 是 P (S1,S2, Sn 是S 類(lèi)中的個(gè)別事物，在枚舉中兼容) S 都是 P,2020/9/1,9,1 推理技術(shù)概述,推理的概念和類(lèi)型 1從推出新判斷的途徑分：演繹推理、歸納推理、

6、默認(rèn)推理 2）歸納推理 枚舉法歸納推理分完全歸納推理與不完全歸納推理 完全歸納推理在進(jìn)行歸納時(shí)考察了相應(yīng)事物的全部對(duì)象，并根據(jù)這些對(duì)象是否都具有某種屬性，從而推出這個(gè)事物是否具有這個(gè)屬性 完全歸納推理是必然性推理 不完全歸納推理只考察了相應(yīng)事物的部分對(duì)象，就得出了結(jié)論 不完全推理得出的結(jié)論不具有必然性，屬于非必然性推理,2020/9/1,10,1 推理技術(shù)概述,推理的概念和類(lèi)型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認(rèn)推理 2）歸納推理 在兩個(gè)或兩類(lèi)事物在許多屬性上都相同的基礎(chǔ)上，推出它們?cè)谄渌鼘傩陨弦蚕嗤?，這就是類(lèi)比法歸納推理 類(lèi)比法歸納可形式化地表示為： A 具有屬性a,b,c,d

7、,e B 具有屬性a,b,c,d, B 也具有屬性e,2020/9/1,11,1 推理技術(shù)概述,推理的概念和類(lèi)型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認(rèn)推理 2）歸納推理 類(lèi)比法的可靠程度決定于兩個(gè)或兩類(lèi)事物的相同屬性與推出的那個(gè)屬性之間的相關(guān)程度，相關(guān)程度越高，則類(lèi)比法的可靠性就越高 歸納推理是人類(lèi)思維活動(dòng)中最基本、最常用的一種推理形式 歸納推理增加了知識(shí)（在機(jī)器學(xué)習(xí)部分稱(chēng)為歸納學(xué)習(xí)）,2020/9/1,12,1 推理技術(shù)概述,推理的概念和類(lèi)型 1從推出新判斷的途徑分：演繹推理、歸納推理、默認(rèn)推理 3）歸納推理 默認(rèn)推理又稱(chēng)為缺省推理，是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)

8、行的推理 如：在條件A已成立的情況下，如果沒(méi)有足夠的證據(jù)能證明條件B不成立，則就默認(rèn)B是成立的，并在此默認(rèn)的前提下進(jìn)行推理，推導(dǎo)出某個(gè)結(jié)論 由于這種推理允許默認(rèn)某些條件是成立的，這就擺脫了需要知道全部有關(guān)事實(shí)才能進(jìn)行推理的要求，能在知識(shí)不完全的情況下也能進(jìn)行推理 在默認(rèn)推理過(guò)程中，如果到某一時(shí)刻發(fā)現(xiàn)原先所作的默認(rèn)不正確，則就要撤消所作的默認(rèn)以及由此默認(rèn)推出的所有結(jié)論，重新按新情況進(jìn)行推理,2020/9/1,13,1 推理技術(shù)概述,推理的概念和類(lèi)型 2按推理時(shí)所用的知識(shí)的確定性來(lái)分： 確定性推理、不精確推理 1）確定性推理（精確推理） 如在推理中所用的知識(shí)都是精確的，即可以把知識(shí)表示成必然的因果

9、關(guān)系，然后進(jìn)行邏輯推理，推理的結(jié)論或者為真，或者為假，這種推理就稱(chēng)為確定性推理 歸結(jié)反演、基于規(guī)則的演繹系統(tǒng)等都是確定性推理,2020/9/1,14,1 推理技術(shù)概述,推理的概念和類(lèi)型 2按推理時(shí)所用的知識(shí)的確定性來(lái)分： 確定性推理、不精確推理 1）不精確推理 （不確定推理） 在人類(lèi)知識(shí)中，有相當(dāng)一部分屬于人們的主觀判斷，是不精確的和含糊的。由這些知識(shí)歸納出來(lái)的推理規(guī)則往往是不確定的 基于不確定的推理規(guī)則進(jìn)行推理，形成的結(jié)論也是不確定的，這種推理稱(chēng)為不精確推理 專(zhuān)家系統(tǒng)中主要使用的是不精確推理,2020/9/1,15,1 推理技術(shù)概述,推理的概念和類(lèi)型 3按推理過(guò)程中推出的結(jié)論是否單調(diào)增加，或

10、者說(shuō)推出的結(jié)論是否越來(lái)越接近最終目標(biāo)來(lái)劃分： 單調(diào)推理、非單調(diào)推理 1）單調(diào)推理 在推理過(guò)程中隨著推理的向前推進(jìn)及新知識(shí)的加入，推出的結(jié)論呈單調(diào)增加的趨勢(shì)，并且越來(lái)越接近最終目標(biāo)單調(diào)推理 一個(gè)演繹推理的邏輯系統(tǒng)有一個(gè)無(wú)矛盾的公理系統(tǒng)，新加入的結(jié)論必須與公理系統(tǒng)兼容，因此新的結(jié)論與已有的知識(shí)不發(fā)生矛盾，結(jié)論總是越來(lái)越多，所以演繹推理是單調(diào)推理,2020/9/1,16,1 推理技術(shù)概述,推理的概念和類(lèi)型 3按推理過(guò)程中推出的結(jié)論是否單調(diào)增加，或者說(shuō)推出的結(jié)論是否越來(lái)越接近最終目標(biāo)來(lái)劃分： 單調(diào)推理、非單調(diào)推理 2）非單調(diào)推理 在推理過(guò)程中隨著推理的向前推進(jìn)及新知識(shí)的加入，不僅沒(méi)有加強(qiáng)已推出的結(jié)論，

11、反而要否定它，使得推理退回到前面的某一步，重新開(kāi)始非單調(diào)推理 一般非單調(diào)推理是在知識(shí)不完全的情況下進(jìn)行的，由于知識(shí)不完全，為使推理進(jìn)行下去，就要先做某些假設(shè)，并在此假設(shè)的基礎(chǔ)上進(jìn)行推理，當(dāng)以后由于新知識(shí)的加入發(fā)現(xiàn)原先的假設(shè)不正確時(shí)，就需要推翻該假設(shè)以及由此假設(shè)為基礎(chǔ)的一切結(jié)論，再用新知識(shí)重新進(jìn)行推理,2020/9/1,17,1 推理技術(shù)概述,推理的概念和類(lèi)型 4按推理中是否運(yùn)用與問(wèn)題有關(guān)的啟發(fā)性知識(shí)可分： 啟發(fā)式推理、非啟發(fā)式推理 1）啟發(fā)式推理 如果在推理過(guò)程中，運(yùn)用與問(wèn)題有關(guān)的啟發(fā)性知識(shí)，即解決問(wèn)題的策略、技巧及經(jīng)驗(yàn)，以加快推理過(guò)程，提高搜索效率，這種推理過(guò)程稱(chēng)為啟發(fā)式推理 A*、AO*等

12、算法就屬于此類(lèi)推理,2020/9/1,18,1 推理技術(shù)概述,推理的概念和類(lèi)型 4按推理中是否運(yùn)用與問(wèn)題有關(guān)的啟發(fā)性知識(shí)可分： 啟發(fā)式推理、非啟發(fā)式推理 2）非啟發(fā)式推理 如果在推理過(guò)程中，不運(yùn)用啟發(fā)性知識(shí)，只按照一般的控制邏輯進(jìn)行推理，這種推理稱(chēng)為非啟發(fā)式推理 這種方法缺乏對(duì)求解問(wèn)題的針對(duì)性，所以推理效率較低，容易出現(xiàn)“組合爆炸”問(wèn)題 圖搜索策略中的寬度優(yōu)先搜索法，雖然是完備的算法，但是對(duì)于復(fù)雜問(wèn)題的求解，將出現(xiàn)“組合爆炸”現(xiàn)象，其搜索效率低,2020/9/1,19,1 推理技術(shù)概述,推理的控制策略 推理的控制策略主要是指推理方向的選擇、推理時(shí)所用的搜索策略及沖突解決策略等 一般推理的控制策

13、略與知識(shí)表達(dá)方法有關(guān) 1推理方向 推理方向用于確定推理的驅(qū)動(dòng)方式 根據(jù)推理方向的不同，可將推理分為正向推理、反向推理和正反向混合推理 無(wú)論按哪種方式進(jìn)行推理，一般都要求系統(tǒng)具有一個(gè)存放知識(shí)的知識(shí)庫(kù)（KB）、一個(gè)存放初始事實(shí)和中間結(jié)果的數(shù)據(jù)庫(kù)（DB）和一個(gè)用于推理的推理機(jī),2020/9/1,20,1 推理技術(shù)概述,推理的控制策略 1推理方向 (1) 正向推理 正向推理（事實(shí)驅(qū)動(dòng)推理）是由已知事實(shí)出發(fā)向結(jié)論方向的推理 基本思想是：系統(tǒng)根據(jù)用戶(hù)提供的初始事實(shí)，在知識(shí)庫(kù)中搜索能與之匹配的規(guī)則即當(dāng)前可用的規(guī)則，構(gòu)成可適用的規(guī)則集RS，然后按某種沖突解決策略從RS中選擇一條知識(shí)進(jìn)行推理，并將推出的結(jié)論作為

14、中間結(jié)果加入到數(shù)據(jù)庫(kù)DB中作為下一步推理的事實(shí)，在此之后，再在知識(shí)庫(kù)中選擇可適用的知識(shí)進(jìn)行推理，如此重復(fù)進(jìn)行這一過(guò)程，直到得出最終結(jié)論或者知識(shí)庫(kù)中沒(méi)有可適用的知識(shí)為止,2020/9/1,21,1 推理技術(shù)概述,推理的控制策略 1推理方向 （1）正向推理,是,2020/9/1,22,1 推理技術(shù)概述,推理的控制策略 1推理方向 （1）正向推理 正向推理簡(jiǎn)單、易實(shí)現(xiàn)，但目的性不強(qiáng)，效率低 需要用啟發(fā)性知識(shí)解除沖突并控制中間結(jié)果的選取，其中包括必要的回溯 由于不能反推，系統(tǒng)的解釋功能受到影響,2020/9/1,23,1 推理技術(shù)概述,推理的控制策略 1推理方向 （2）反向推理,2020/9/1,24

15、,1 推理技術(shù)概述,推理的控制策略 1推理方向 （2）反向推理 反向推理以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的一種推理，又稱(chēng)為目標(biāo)驅(qū)動(dòng)推理或逆向推理 反向推理的基本思想是：首先提出一個(gè)假設(shè)目標(biāo)，然后由此出發(fā)，進(jìn)一步尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則該假設(shè)成立，推理成功；若無(wú)法找到支持該假設(shè)的所有證據(jù)，則說(shuō)明此假設(shè)不成立，需要另作新的假設(shè),2020/9/1,25,1 推理技術(shù)概述,推理的控制策略 1推理方向 （2）反向推理 與正向推理相比，反向推理的主要優(yōu)點(diǎn)是不必使用與目標(biāo)無(wú)關(guān)的知識(shí)，目的性強(qiáng)，同時(shí)它還有利于向用戶(hù)提供解釋 反向推理的缺點(diǎn)是在選擇初始目標(biāo)時(shí)具有很大的盲目性，若假設(shè)不正確，就有可能

16、要多次提出假設(shè)，影響了系統(tǒng)的效率 反向推理比較適合結(jié)論單一或直接提出結(jié)論要求證實(shí)的系統(tǒng),2020/9/1,26,1 推理技術(shù)概述,推理的控制策略 1推理方向 （3）正反向混合推理,2020/9/1,27,1 推理技術(shù)概述,推理的控制策略 1推理方向 （3）正反向混合推理,正向推理 效率低，推出大量無(wú)關(guān)子目標(biāo),反向推理 假設(shè)的盲目性降低效率,正反向混合推理,2020/9/1,28,1 推理技術(shù)概述,推理的控制策略 1推理方向 （3）正反向混合推理 正反向混合推理的一般過(guò)程是：先根據(jù)初始事實(shí)進(jìn)行正向推理以幫助提出假設(shè)，再用反向推理進(jìn)一步尋找支持假設(shè)的證據(jù)，反復(fù)這個(gè)過(guò)程，直到得出結(jié)論為止 正反向混合

17、推理集中了正向推理和反向推理的優(yōu)點(diǎn)，但其控制策略相對(duì)復(fù)雜,2020/9/1,29,1 推理技術(shù)概述,推理的控制策略 2搜索策略 推理時(shí)，要反復(fù)用到知識(shí)庫(kù)中的規(guī)則，而知識(shí)庫(kù)中的規(guī)則又很多，這樣就存在著如何在知識(shí)庫(kù)中尋找可用規(guī)則的問(wèn)題，即如何確定推理路線，使其付出的代價(jià)盡可能的少，而問(wèn)題又能得到較好的解決 為了有效地控制規(guī)則的選取，可以采用各種搜索策略 常用搜索策略： 狀態(tài)空間搜索（寬度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索等） 啟發(fā)式搜索等（第三章）,2020/9/1,30,1 推理技術(shù)概述,推理的控制策略 3沖突解決策略 在推理過(guò)程中，系統(tǒng)要不斷地用數(shù)據(jù)庫(kù)中的事實(shí)與知識(shí)庫(kù)中的規(guī)則進(jìn)行匹配，當(dāng)

18、有一個(gè)以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫(kù)相匹配時(shí)，就需要有一種策略來(lái)決定首先使用哪一條規(guī)則，這就是沖突解決策略 沖突解決策略實(shí)際上就是確定規(guī)則的啟用順序,2020/9/1,31,1 推理技術(shù)概述,推理的控制策略 3沖突解決策略 (1) 專(zhuān)一性排序 如果某一規(guī)則的條件部分規(guī)定的情況比另一規(guī)則的條件部分所規(guī)定的情況更專(zhuān)門(mén)，則這條規(guī)則具有較高的優(yōu)先級(jí) 例，有如下規(guī)則： 規(guī)則1：IF A AND B AND C THEN E； 規(guī)則2：IF A AND B AND C AND D THEN F； 數(shù)據(jù)庫(kù)中A、B、C、D均為真，這時(shí)規(guī)則1和規(guī)則2都與數(shù)據(jù)庫(kù)相匹配，但因?yàn)橐?guī)則2的條件部分包括了更多的限制，所以

19、具有較高的優(yōu)先級(jí) 本策略是優(yōu)先使用針對(duì)性較強(qiáng)的產(chǎn)生式規(guī)則,2020/9/1,32,1 推理技術(shù)概述,推理的控制策略 3沖突解決策略 (2) 規(guī)則排序 如果規(guī)則編排的順序就表示了啟用的優(yōu)先級(jí)，則稱(chēng)之為規(guī)則排序 (3) 數(shù)據(jù)排序 數(shù)據(jù)排序就是把規(guī)則條件部分的所有條件排序，即按優(yōu)先級(jí)次序編排起來(lái)，當(dāng)發(fā)生沖突時(shí)，首先使用在條件部分包含較高優(yōu)先級(jí)數(shù)據(jù)的規(guī)則 (4) 就近排序 就近排序就是把最近使用的規(guī)則放在最優(yōu)先的位置。如果某一規(guī)則經(jīng)常使用，則傾向于更多地使用這條規(guī)則,2020/9/1,33,1 推理技術(shù)概述,推理的控制策略 3沖突解決策略 (5) 上下文限制 上下文限制就是把產(chǎn)生式規(guī)則按它們所描述的上

20、下文分組，在某種上下文條件下，只能從與其相對(duì)應(yīng)的那組規(guī)則中選擇可應(yīng)用的規(guī)則 不僅可以減少?zèng)_突，而且由于搜索范圍小，也提高了推理的效率,2020/9/1,34,1 推理技術(shù)概述,推理的控制策略 3沖突解決策略 (6) 按匹配度排序 在不精確匹配中，為了確定兩個(gè)知識(shí)模式是否可以進(jìn)行匹配，需要計(jì)算這兩個(gè)模式的相似程度，當(dāng)其相似度達(dá)到某個(gè)預(yù)先規(guī)定的值時(shí)，就認(rèn)為它們是可匹配的 相似度又稱(chēng)為匹配度，它除了可用來(lái)確定兩個(gè)知識(shí)模式是否可匹配外，還可用于沖突解除。若有幾條規(guī)則均可匹配成功，則可根據(jù)它們的匹配度來(lái)決定哪一個(gè)產(chǎn)生式規(guī)則可優(yōu)先被應(yīng)用,2020/9/1,35,1 推理技術(shù)概述,推理的控制策略 3沖突解決

21、策略 (6) 按條件個(gè)數(shù)排序 如果有多條產(chǎn)生式規(guī)則生成的結(jié)論相同，則要求條件少的產(chǎn)生式規(guī)則被優(yōu)先應(yīng)用，因?yàn)橐髼l件少的規(guī)則匹配時(shí)花費(fèi)的時(shí)間較少 不同的系統(tǒng)，可使用上述這些策略的不同組合，目的是盡量減少?zèng)_突的發(fā)生，使推理有較快的速度和較高的效率 如何選擇沖突解決策略完全是由啟發(fā)性知識(shí)決定的,2020/9/1,36,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 在謂詞演算（第二章）中，利用前面列出的等價(jià)式和永真蘊(yùn)含式可以從已知的一些公式推導(dǎo)出新的公式，這個(gè)導(dǎo)出的公式叫做定理，在推導(dǎo)過(guò)程中使用的推理規(guī)則序列就成了該定理的一個(gè)證明 將要介紹的歸結(jié)原理是定理證明的基礎(chǔ)，它應(yīng)用于稱(chēng)為子句的一種公式類(lèi)的推理,2020/9/1

22、,37,2 歸結(jié)反演系統(tǒng),歸結(jié)原理,難；繁,2020/9/1,38,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 1子句 謂詞邏輯中，把原子公式及原子公式的否定統(tǒng)稱(chēng)為文字 【定義41】任何文字的析取式稱(chēng)為子句。 例如PQ、P（x，f(x)，y）Q(y)R(f(x) 都是子句 【定義42】不包含任何文字的子句稱(chēng)為空子句，表示為NIL 由于空子句不包含有文字，它不能被任何解釋滿足，所以空子句是永假的，不可滿足的 由子句構(gòu)成的集合稱(chēng)為子句集 謂詞邏輯中，任何一個(gè)謂詞公式都可以化成一個(gè)子句集,2020/9/1,39,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 1子句 將謂詞公式化為子句集的步驟： (1)利用PQ = PQ；PQ =（P

23、Q）（PQ）等價(jià)關(guān)系消去蘊(yùn)含符“”和雙條件符“” (2) 利用P = P；（PQ）= P Q；（PQ）= P Q；($x)P = (x)(P)；(x)P = ($x)(P)等價(jià)關(guān)系把否定符號(hào)“”移到緊靠謂詞位置上(3) 利用(x)P（x）= (y)P（y）；($x)P（x）= ($y)P（y）等價(jià)關(guān)系將變量標(biāo)準(zhǔn)化，即使每個(gè)量詞采用不同的變量 (4) 消去存在量詞$ 如果存在量詞不在任何一個(gè)全稱(chēng)量詞的轄域內(nèi)，則該存在量詞不依賴(lài)于任何其它的變量，因此可用一個(gè)新的個(gè)體常量代替 如將($x)P（x）化為P(A) 如果存在量詞是在全稱(chēng)量詞的轄域內(nèi)（如在公式(“y)（($x)P（x，y）中，變量x的取值依

24、賴(lài)于變量y的取值） 由Skolem函數(shù)表示依賴(lài)關(guān)系 注意，函數(shù)名應(yīng)是原合式公式中沒(méi)有的符號(hào) （續(xù)）,2020/9/1,40,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 1子句 將謂詞公式化為子句集的步驟： (5)將公式化為前束形把所有全稱(chēng)量詞（已不留下任何存在量詞，而且每個(gè)全稱(chēng)量詞都有自己的變量）移到公式的左邊，并使每個(gè)量詞的轄域包含這個(gè)量詞后面的整個(gè)部分，所得的公式稱(chēng)為前束形 (6)利用P（QR）=（PQ）（PR）；（PQ）（PR）= P（QR）等價(jià)關(guān)系將母式化為合取范式（子句的合取式） (7)略去全稱(chēng)量詞母式中的變量被默認(rèn)為是全稱(chēng)量詞量化的變量 (8)消去合取符號(hào)，把母式用子句集表示 如：PQ可表示為成子

25、句集： P Q (9)子句變量標(biāo)準(zhǔn)化重新命名變量，使每個(gè)子句中的變量符號(hào)不同,2020/9/1,41,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 1子句 【例41】將(x)P(x)Q(x)($ y)S(x,y)Q(x)(x)P(x)B(x)化成子句集 轉(zhuǎn)換過(guò)程遵照上述9個(gè)步驟： 錯(cuò) (1) (x)P（x）Q(x)($ y)S(x，y)Q(x)(x)P（x）B（x） (2) (x)P（x）Q(x)($ y)S(x，y)Q(x)(x)P（x）B（x） (3) (x)P（x）Q(x)($ y)S(x，y)Q(x)(w)P（w）B（w） (4) (x)P（x）Q(x )S(x，f (x) ) Q(x ) ( w) P

26、（w）B（w） (5) (x)(w)P（x）Q(x)S(x，f(x)Q(x)P（w）B（w） (6) (x)(w)P（x）S(x，f(x)Q(x)P（w）B（w） (7) P（x）S(x，f(x)Q(x)P（w）B（w） (8) 子句集為： P（x）S(x，f(x)）；Q(x)；P（w）B（w） (9) 子句變量標(biāo)準(zhǔn)化后，最終的子句集為： P（x）S（x，f(x)） Q（y） P（w）B（w）,2020/9/1,42,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 2置換和合一 為了使用推理規(guī)則，如假言推理、假言三段論等，一個(gè)推理系統(tǒng)必須決定兩個(gè)表達(dá)式是否相同或匹配： 兩個(gè)表達(dá)式匹配當(dāng)且僅當(dāng)其語(yǔ)法是等價(jià)的 一個(gè)表

27、達(dá)式的項(xiàng)可以是常量、變量或函數(shù)，合一就是尋找項(xiàng)對(duì)變量的置換而使表達(dá)式一致的過(guò)程，合一是人工智能中很重要的過(guò)程 如，為了使公式( x)P（x）與P（A）匹配，可以用常量A代替變量x，從而使兩個(gè)公式一致,2020/9/1,43,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 2置換和合一 置換可用有序?qū)Φ募蟬=t1/v1，t2/v2，tn/vn表示，其中ti/vi表示將表達(dá)式中所有的變量vi都用項(xiàng)ti代替，ti可以是變量、常量或函數(shù) 注意，一個(gè)變量不能用含有同一變量的項(xiàng)來(lái)代替 一般可用Es表示一個(gè)表達(dá)式E用一個(gè)置換s所得到的表達(dá)式的置換 如：P（z，f（w），A）= （P（x，f（y），A）s,2020/9/1,4

28、4,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 2置換和合一 例如有表達(dá)式P（x，f（y），A），通過(guò)不同的置換，可分別得到： P（z，f（w），A） 相應(yīng)的置換為 s1 = z/x ，w/y P（x，f（B），A） 相應(yīng)的置換為 s2 = B/ y P（g(z)，f（B），A） 相應(yīng)的置換為 s3 = g(z)/x ，B /y P（C，f（B），A） 相應(yīng)的置換為 s4 = C/x ，B/y ,2020/9/1,45,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 2置換和合一 置換是可結(jié)合的 用s1 s2表示兩個(gè)置換s1和 s2的合成，E表示一表達(dá)式，則有： （E s1）s2 = E（s1 s2） （s1 s2）s3= s1

29、（s2 s3） 把置換s作用于集合Ei中每一個(gè)公式得到的例的集合用Eis表示 如果存在一個(gè)置換s，使(E1)s=(E2)s=(E3)s=，則稱(chēng)公式集Ei是可合一的，置換s稱(chēng)為Ei的合一者 如：公式集P(x,f(y),B),P(x,f(B),B)的合一者為s = A/x,B/y,2020/9/1,46,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 2置換和合一 在P(x,f(y),B)s=P(x,f(B),B)s=P(A,f(B),B)s,s=A/x,B/y中，s并不是最簡(jiǎn)單的，因置換B/y就可使上述公式集合一 如果s是Ei的任一合一者，又存在某個(gè)s，使得公式Eis=Eig s，則稱(chēng)g為公式集Ei的最簡(jiǎn)單合一者m

30、gu（Most General Unifier） 置換 B/y 為公式集P(x，f( y )，B), P(x , f(B)，B)的最簡(jiǎn)單合一者,2020/9/1,47,2 歸結(jié)反演系統(tǒng),歸結(jié)原理2置換和合一 最簡(jiǎn)單的合一者的遞歸算法UNIFY（E1，E2） (1) if E1或E2是一個(gè)原子，如果有必要?jiǎng)t交換E1和E2的位置，使E1是一個(gè)原子，do： (2) if E1和E2是相同的，return NIL (3) else if E1是個(gè)變量，do： (4) if E1出現(xiàn)在E2中，return FAIL else return E2/E1 (5) if E2是一個(gè)變量，return E1/E

31、2 else return FAIL (6) else F1E1的第一個(gè)元素，T1E1的其余元素 (7) F2E2的第一個(gè)元素，T2E2的其余元素 (8) Z1UNIFY（F1，F(xiàn)2） (9) if Z1 = FAIL, return FAIL (10) G1Z1作用到T1的結(jié)果 (11) G2Z1作用到T2的結(jié)果 (12) Z2UNIFY（G1，G2） (13) if Z2 = FAIL, return FAIL else Return Z1 和Z2的合成,2020/9/1,48,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 3歸結(jié)原理 歸結(jié)原理又稱(chēng)為消解原理，它是定理證明基礎(chǔ) 由謂詞公式轉(zhuǎn)化為子句集的過(guò)程中

32、可以看出，在子句集中子句之間是合取關(guān)系，其中只要有一個(gè)子句不可滿足，則子句集就不可滿足。若一個(gè)子句集中包含空子句，則這個(gè)子句集一定是不可滿足的歸結(jié)原理就是基于這一認(rèn)識(shí)提出來(lái)的 【定義43】若P是原子謂詞公式，則稱(chēng)P與P為互補(bǔ)文字,2020/9/1,49,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 3歸結(jié)原理 (1) 基子句的歸結(jié) 所謂基子句，是指沒(méi)有變量的子句 【定義44】設(shè)C1與C2是子句集中的任意兩個(gè)基子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將二個(gè)子句余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱(chēng)一過(guò)程為歸結(jié)，稱(chēng)C12為基子句C1和C2的歸結(jié)式，稱(chēng)C1和C2為

33、C12的父輩子句,2020/9/1,50,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 3歸結(jié)原理 【例42】設(shè)C1=PQR，C2=PST歸結(jié)為： C12=QRST,2020/9/1,51,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 3歸結(jié)原理(多子句則逐步歸結(jié)) 【例43】設(shè)子句集S=PQ，QR，P，RT ，則其歸結(jié)過(guò)程如圖 歸結(jié)結(jié)果為T(mén),2020/9/1,52,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 3歸結(jié)原理 (2)含有變量的子句的歸結(jié) 在謂詞邏輯中，子句中含有變量 為將歸結(jié)原理應(yīng)用于含有變量的子句，應(yīng)找出一個(gè)置換，作用于給定的兩個(gè)子句，使它們包括互補(bǔ)的文字，然后才能進(jìn)行歸結(jié) 例:子句集S=P(x)Q(x)，P(A)R(y)，子句集

34、中的兩個(gè)子句不能直接歸結(jié)，但若對(duì)子句集先進(jìn)行置換s=A/x，則兩個(gè)子句分別為P(A)Q(A)和P(A)R(y)，這時(shí)再進(jìn)行歸結(jié)，歸結(jié)結(jié)果為Q(A)R(y),2020/9/1,53,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 3歸結(jié)原理 【定義45】設(shè)C1和C2是兩個(gè)沒(méi)有相同變量的子句，并分別表示成兩個(gè)文字集合Li和Mi，li是Li的一個(gè)子集，mi是Mi的一個(gè)子集，若s是集合li和mi的并集的最簡(jiǎn)合一者，則稱(chēng) C12 = Li-lisMi-mi s 為C1和C2的歸結(jié)式。 當(dāng)兩個(gè)子句作歸結(jié)時(shí)，子集li和mi的選取可能有多種形式，所以得到的歸結(jié)式不是唯一的,2020/9/1,54,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 3歸

35、結(jié)原理 例:設(shè)有兩個(gè)子句P(A)Q(x)R(x)和P(y)Q(B)，則由如下兩種歸結(jié)方法： 取li=P(A)，mi=P(y)，li和mi的最簡(jiǎn)合一者為s=A/y，此時(shí)歸結(jié)結(jié)果為Q(x)R(x)Q(B) 取li=Q(x)，mi=Q(B)，li和mi的最簡(jiǎn)合一者為s=B/x，此時(shí)歸結(jié)結(jié)果為P(A)R(B)P(y),2020/9/1,55,2 歸結(jié)反演系統(tǒng),歸結(jié)原理 3歸結(jié)原理 例的歸結(jié)過(guò)程：,2020/9/1,56,2 歸結(jié)反演系統(tǒng),歸結(jié)反演,初始公式,目標(biāo)公式,初始子句集,目標(biāo)子句,難；繁,初始子句集,空子句,可判定的！,永真：半可判定的,2020/9/1,57,2 歸結(jié)反演系統(tǒng),歸結(jié)反演 歸結(jié)

36、反演就是利用歸結(jié)和反演實(shí)現(xiàn)定理的證明 具體過(guò)程： (1) 將定理證明的前提謂詞公式轉(zhuǎn)化為子句集F (2) 將求證的目標(biāo)表示成合適的謂詞公式G（目標(biāo)公式） (3)將目標(biāo)公式的否定式G轉(zhuǎn)化成子句的形式，并加入到子句集F中，得到子句集S (4) 應(yīng)用歸結(jié)原理對(duì)子句集中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若歸結(jié)得到一個(gè)空子句N(xiāo)IL，則停止歸結(jié) 證明了G為真,2020/9/1,58,2 歸結(jié)反演系統(tǒng),歸結(jié)反演 【例44】 已知前提為F:(x)P(x,y)Q(y)(y)R(y)S(x,y) 求證結(jié)論G:(x)R(x)(x)(y)P(x,y)Q(y)成立 證明：先按前面所講的方

37、法將前提和結(jié)論化為子句集： 前提F所對(duì)應(yīng)的子句集為：P(x,y)Q(y)R(f(x) P(x,y)Q(y)S(x, f(x) 結(jié)論G否定對(duì)應(yīng)子句集為：R(z) P(A,B) Q(B),2020/9/1,59,2 歸結(jié)反演系統(tǒng),歸結(jié)反演 【例44】 歸結(jié)過(guò)程 經(jīng)過(guò)歸結(jié)最后得到NIL， 所以結(jié)論G成立,2020/9/1,60,2 歸結(jié)反演系統(tǒng),歸結(jié)反演 【例45】已知: 能閱讀的都是有文化的; 海豚是沒(méi)有文化的; 某些海豚是有智能的; 用歸結(jié)反演法證明:某些有智能的并不能閱讀 證明：設(shè) R(x)：x能閱讀 L(x): x有文化 D(x): x是海豚 I(x): x有智能,2020/9/1,61,2

38、 歸結(jié)反演系統(tǒng),歸結(jié)反演 【例45】 將前提形式化地表示為： (x)（R(x)L(x)） (y)（D(y) L(y)） (z)（D(z)I(z) 將結(jié)論形式化地表示為： (w)(I(w)R(w) 首先將前提化成子句集： R(x)L(x) D(y) L(y) D(A) I(A) 將結(jié)論的否定式為化成子句：I(w)R(w),2020/9/1,62,2 歸結(jié)反演系統(tǒng),歸結(jié)反演 【例45】 歸結(jié)后得到空子句N(xiāo)IL， 證明完畢,2020/9/1,63,2 歸結(jié)反演系統(tǒng),歸結(jié)反演 歸結(jié)反演過(guò)程主要就是證明一個(gè)集合S是不可滿足的過(guò)程，即從集合S中歸結(jié)出空子句的過(guò)程 算法描述： 過(guò)程RESOLUTION (1

39、) CLAUSESS (2) Until NIL是CLAUSES的成員，do: (3) Begin (4) 在CLAUSES中選擇兩個(gè)不同的可歸結(jié)的子句Ci和Cj (5) 計(jì)算Ci和Cj的歸結(jié)式Cij (6) CLAUSES附加Cij到CLAUSES產(chǎn)生的子句集 （7）end,2020/9/1,64,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略 對(duì)子句集進(jìn)行歸結(jié)時(shí)，關(guān)鍵的一步是從子句集中找出可進(jìn)行歸結(jié)的子句 由于事先不知道哪兩個(gè)子句可以進(jìn)行歸結(jié)，更不知道通過(guò)對(duì)哪些子句對(duì)的歸結(jié)可以盡快地得到空子句，因而必須對(duì)子句集中的所有子句逐對(duì)地進(jìn)行比較，對(duì)任何一對(duì)可歸結(jié)的子句對(duì)都進(jìn)行歸結(jié)，這樣的效率是很低的 歸結(jié)反

40、演的控制策略,2020/9/1,65,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略 1寬度優(yōu)先策略 基本思想：首先從基本子句集生成所有的歸結(jié)式，稱(chēng)為第一級(jí)歸結(jié)式。在這一輪歸結(jié)中，子句集中的每個(gè)子句都要和子句集中的其它子句比較以確定是否進(jìn)行歸結(jié)。然后，從基本子句集和第一級(jí)歸結(jié)式生成第二級(jí)歸結(jié)式。以此類(lèi)推，直到出現(xiàn)了空子句或者不能再歸結(jié)為止 寬度優(yōu)先策略是完備的，但會(huì)歸結(jié)出許多無(wú)用的子句，而且有一些歸結(jié)式還是重復(fù)的，所以是低效的，即浪費(fèi)時(shí)間又多占空間,2020/9/1,66,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略 1寬度優(yōu)先策略,2020/9/1,67,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略 2支持集策略 支

41、持集策略是一種改進(jìn)的歸結(jié)策略 對(duì)參加歸結(jié)的子句提出了如下限制：每一次歸結(jié)時(shí)，其父輩子句中至少有一個(gè)是由目標(biāo)公式的否定所得到的子句或者是它們的后代（即支持集） 可以證明，支持集策略是完備的，即若子句集是不可滿足的，則由支持集策略一定可以歸結(jié)出空子句 支持集策略相當(dāng)于在寬度優(yōu)先策略中引入了約束條件，因此效率比寬度優(yōu)先策略要高,2020/9/1,68,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略2支持集策略,2020/9/1,69,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略 3單文字子句優(yōu)先策略 如果一個(gè)子句只包含一個(gè)文字，則稱(chēng)它為單文字子句 單文字子句優(yōu)先策略要求參加歸結(jié)的子句中必須至少有一個(gè)是單文字子句 每次

42、歸結(jié)時(shí)優(yōu)先選擇單文字子句進(jìn)行歸結(jié)，所以得到的歸結(jié)式的文字?jǐn)?shù)目必然比其另外一個(gè)父輩子句少。這有利于歸結(jié)式向空子句的方向生成，提高了效率,2020/9/1,70,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略 3單文字子句優(yōu)先策略,2020/9/1,71,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略 4線性輸入形策略 歸結(jié)策略對(duì)參加歸結(jié)的子句提出了如下限制：參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是基本子句集中的子句 線性輸入形策略可提高效率，但不完備(祖先過(guò)濾策略能使之完備） 例見(jiàn)下頁(yè) 其它的歸結(jié)策略如祖先過(guò)濾策略、模型策略、有序策略等。在具體應(yīng)用中可根據(jù)實(shí)際情況選擇適當(dāng)?shù)臍w結(jié)策略，有時(shí)可把幾種策略組合在一起使用,20

43、20/9/1,72,2 歸結(jié)反演系統(tǒng),歸結(jié)反演的控制策略 4線性輸入形策略,2020/9/1,73,2 歸結(jié)反演系統(tǒng),應(yīng)用歸結(jié)反演求取問(wèn)題的答案 歸結(jié)反演除了可用于定理證明外，還可用來(lái)求取問(wèn)題的答案，其思想與定理證明類(lèi)似 用歸結(jié)反演求取問(wèn)題答案的一般步驟是： (1) 把已知前提用謂詞公式表示出來(lái)，并且化為子句集，設(shè)該子句集為S (2) 把目標(biāo)也用謂詞公式表示出來(lái) (3)在目標(biāo)公式的否定的子句形式中，附加上該子句的否定（即目標(biāo)公式否定之否定）。然后一起加入到子句集S中，得到子句集S (4) 對(duì)S進(jìn)行歸結(jié)，形成歸結(jié)反演樹(shù)修改的證明樹(shù) (5) 用根部的子句作為解答子句,2020/9/1,74,2 歸

44、結(jié)反演系統(tǒng),應(yīng)用歸結(jié)反演求取問(wèn)題的答案 【例46】已知：F1：王(Wang)先生是小李(Li)的老師， F2：小李與小張(Zhang)是同班同學(xué)。 F3：如果x和y是同班同學(xué)，則x的老師就是y的老師 求：小張的老師是誰(shuí)？ 解：先定義謂詞：T（x，y）：x是y的老師 C（x，y）：x與y是同班同學(xué) 把已知前提及目標(biāo)表示成謂詞公式： 前提 F1：T（Wang，Li） F2：C（ Li，Zhang） F3：C（x，y）T（z，x）T（z，y） 目標(biāo) G：(x)T(x，Zhang) G的否定：(x)T(x，Zhang),2020/9/1,75,2 歸結(jié)反演系統(tǒng),應(yīng)用歸結(jié)反演求取問(wèn)題的答案 【例46】將

45、以上前提和目標(biāo)的否定化成子句集： F1:T(Wang,Li) F2:C(Li,Zhang) F3:C(x,y)T(z,x)T(z,y) 目標(biāo)重言式：T(u,Zhang)T(u,Zhang) 根部子句：T(Wang,Zhang)， 這就是答案， 表示小張（Zhang）的老師是王（Wang）,2020/9/1,76,2 歸結(jié)反演系統(tǒng),應(yīng)用歸結(jié)反演求取問(wèn)題的答案 【例47】已知事實(shí)如下： (1) 對(duì)所有的x和y，如果x是y的父輩而y是z的父輩，則x是z的祖輩。 (2) 每個(gè)人都有父輩。 問(wèn)：是否存在具體的x和y，使得x是y的祖輩？ 解：先定義謂詞： P（x，y）：x是y的父輩 G（x，y）：x是y的

46、祖輩 把已知前提及目標(biāo)表示成謂詞公式： 前提1：P（x，y）P（y，z）G(x，z) 前提2：（y）（x）P（x，y） 目標(biāo)G：（x）（y）G（x，y） G的否定：（x）（y）G（x，y）,2020/9/1,77,2 歸結(jié)反演系統(tǒng),應(yīng)用歸結(jié)反演求取問(wèn)題的答案 【例47】將前提和目標(biāo)的否定化成子句集： 前提1：P（x，y） P（y，z）G(x，z) 前提2：P（f(w)，w） G的否定： G（u，v） 把它添加到目標(biāo)公式否定之否定的子句中去，得到重言式： G（u，v）G（u，v）。 通過(guò)歸結(jié)，在根部得到子句：G(f(f(v)，v)，這就是答案，表示v的父輩的父輩就為v的祖輩,2020/9/1,7

47、8,2 歸結(jié)反演系統(tǒng),應(yīng)用歸結(jié)反演求取問(wèn)題的答案 【例47】,2020/9/1,79,2 歸結(jié)反演系統(tǒng),應(yīng)用歸結(jié)反演求取問(wèn)題的答案 目標(biāo)公式中含有全稱(chēng)量詞稍復(fù)雜些 基于歸結(jié)原理的歸結(jié)反演推理比較簡(jiǎn)單且又便于在計(jì)算機(jī)上實(shí)現(xiàn)，所以對(duì)自動(dòng)定理證明領(lǐng)域影響較大。但是歸結(jié)反演要求把前提、結(jié)論等所有邏輯表達(dá)式轉(zhuǎn)化為子句集，因此喪失了許多有用的信息 如邏輯式PQ與子句PQ在邏輯上是等價(jià)的，但它們所表達(dá)的信息是不同的，相比之下，PQ的含義更易于理解 提出多種非子句定理證明方法 如自然演繹和基于規(guī)則的演繹法等,2020/9/1,80,3 基于規(guī)則的演繹推理,知識(shí)一般是由蘊(yùn)含式直接表示的，但在歸結(jié)反演中，必須首先

48、將它們轉(zhuǎn)化為子句的形式，所以這種推理是比較低效的 基于規(guī)則的演繹推理則是一種直接的推理方法。它不再把有關(guān)的知識(shí)轉(zhuǎn)化為子句集，而是把有關(guān)問(wèn)題的知識(shí)和信息劃分為規(guī)則與事實(shí)兩種類(lèi)型 規(guī)則：包含蘊(yùn)含形式的表達(dá)式表示 事實(shí)：無(wú)蘊(yùn)含式的表達(dá)式表示 畫(huà)出相應(yīng)的與/或圖，然后通過(guò)規(guī)則進(jìn)行演繹推理,2020/9/1,81,3 基于規(guī)則的演繹推理,基于規(guī)則的演繹推理可分為正向演繹推理、反向演繹推理和正反向混合演繹推理 在正向演繹推理中，作為F規(guī)則用的蘊(yùn)含式對(duì)事實(shí)的總數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算，直至得到該目標(biāo)公式的一個(gè)終止條件為止 在反向演繹推理中，作為B規(guī)則用的蘊(yùn)含式對(duì)目標(biāo)的總數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算，直至得到包含這些事實(shí)的終

49、止條件為止 在雙向演繹推理中，分別從兩個(gè)方向應(yīng)用不同的規(guī)則（F規(guī)則和B規(guī)則）進(jìn)行操作運(yùn)算,2020/9/1,82,3 基于規(guī)則的演繹推理,正向演繹推理 正向演繹推理對(duì)應(yīng)于41中介紹的正向推理，它是從已知事實(shí)出發(fā)，反復(fù)嘗試所有可利用的規(guī)則（F規(guī)則）進(jìn)行演繹推理，直至得到某個(gè)目標(biāo)公式的一個(gè)終止條件為止,2020/9/1,83,3 基于規(guī)則的演繹推理,正向演繹推理 （1）事實(shí)表達(dá)式及其與或圖表示 正向演繹要求事實(shí)用不包含蘊(yùn)含符號(hào)“”的與/或形表示 一個(gè)表達(dá)式轉(zhuǎn)化為標(biāo)準(zhǔn)的與/或形的步驟如下： 利用等價(jià)式PQ與PQ消去蘊(yùn)含符“” 把否定符號(hào)“”移到每個(gè)謂詞符號(hào)的前面 變量標(biāo)準(zhǔn)化，即重新命名變量，使不同量

50、詞約束變量有不同的名字 引入Skolem函數(shù)消去存在量詞 將公式化為前束形 略去全稱(chēng)量詞(默認(rèn)事實(shí)表達(dá)式中尚存的變量是全稱(chēng)量詞量化的變量) 重新命名變量，使同一變量不出現(xiàn)在不同的主要合取式中,2020/9/1,84,3 基于規(guī)則的演繹推理,正向演繹推理 （1）事實(shí)表達(dá)式及其與或圖表示 如表達(dá)式:（x）(y)Q(y,x)(R(y)P(y)S(x，y) 轉(zhuǎn)化為標(biāo)準(zhǔn)的與/或形: Q(z,A) R(y) P(y) S(A，y) 事實(shí)表達(dá)式的標(biāo)準(zhǔn)與/或形樹(shù):,2020/9/1,85,3 基于規(guī)則的演繹推理,正向演繹推理 （1）事實(shí)表達(dá)式及其與或圖表示 在與/或圖中，結(jié)點(diǎn)表示事實(shí)表達(dá)式及其子表達(dá)式 根結(jié)點(diǎn)

51、表示整個(gè)表達(dá)式，葉結(jié)點(diǎn)表示表達(dá)式中的單個(gè)文字 對(duì)于一個(gè)表示析取表達(dá)式（E1E2En）的結(jié)點(diǎn)，用一個(gè)n連接符（圖中的半圓弧）連接它的n個(gè)子表達(dá)式結(jié)點(diǎn)； 對(duì)于一個(gè)表示合取表達(dá)式（E1E2En）的結(jié)點(diǎn)，則直接用單線連接符與它的n個(gè)子表達(dá)式結(jié)點(diǎn)相連 事實(shí)表達(dá)式:用n連接符（一個(gè)合取記號(hào)）來(lái)分解析取式,2020/9/1,86,3 基于規(guī)則的演繹推理,正向演繹推理 （1）事實(shí)表達(dá)式及其與或圖表示 一重要性質(zhì)：由變換表達(dá)式得到的一組子句則可從與或圖中讀出，每子句相當(dāng)于與/或圖的一個(gè)解圖，每個(gè)子句是由葉結(jié)點(diǎn)組成的公式 從上上頁(yè)可以讀出上例表達(dá)式的三個(gè)子句： Q(z,A) S(A，y) R(y) S(A，y)

52、P(y) 這三個(gè)子句正是原表達(dá)式化成的子句集與/或圖可看成是一組子句的一個(gè)簡(jiǎn)潔的表達(dá)形式,2020/9/1,87,3 基于規(guī)則的演繹推理,正向演繹推理 （2）F規(guī)則的表示形式 基于規(guī)則的正向演繹推理中，通常要求F規(guī)則具有以下形式： L W 具體要求如下： L是單文字，W是任意的與或形表達(dá)式 L和W中的所有變量都是全稱(chēng)量詞量化的，默認(rèn)的全稱(chēng)量詞作用于整個(gè)蘊(yùn)含式 各條規(guī)則的變量各不相同，而且規(guī)則中的變量與事實(shí)表達(dá)式中的變量也不相同,2020/9/1,88,3 基于規(guī)則的演繹推理,正向演繹推理 （2）F規(guī)則的表示形式 將F規(guī)則的左部限制為單文字，是因?yàn)樵谶M(jìn)行演繹推理時(shí)，要用F規(guī)則作用于表示事實(shí)的與/

53、或圖，而該與/或圖的葉結(jié)點(diǎn)都是單文字，這樣就可用F規(guī)則的左部與葉結(jié)點(diǎn)進(jìn)行匹配，大大簡(jiǎn)化了規(guī)則的應(yīng)用過(guò)程,2020/9/1,89,3 基于規(guī)則的演繹推理,正向演繹推理 （2）F規(guī)則的表示形式 變換成標(biāo)準(zhǔn)形式的步驟： 暫時(shí)消去蘊(yùn)含符號(hào)“” 把否定號(hào)“”移到每個(gè)謂詞的前面 引入Skolem函數(shù)消去存在量詞 將公式化為前束形，并略去全稱(chēng)量詞 恢復(fù)為蘊(yùn)含式,2020/9/1,90,3 基于規(guī)則的演繹推理,正向演繹推理 （2）F規(guī)則的表示形式 變換成標(biāo)準(zhǔn)形式的例： 原公式(x)(y)(z)P(x,y,z)(u)Q(x,u) 消蘊(yùn)含符(x)(y)(z)P(x,y,z)(u)Q(x,u) 否定號(hào)移入(x)(y

54、)(z)P(x,y,z)(u)Q(x,u) Skolem函數(shù)(x)(y)P(x,y,f(x,y)(u)Q(x,u) 前束形/略全稱(chēng)量詞P(x,y,f(x,y)Q(x,u) 恢復(fù)蘊(yùn)含式P(x,y,f(x,y)Q(x,u),2020/9/1,91,3 基于規(guī)則的演繹推理,正向演繹推理 （3）目標(biāo)公式的表示形式 在基于規(guī)則的正向演繹推理中，要求目標(biāo)公式用子句表示，否則就要化成子句形式,2020/9/1,92,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過(guò)程 基于規(guī)則的正向演繹推理應(yīng)用F規(guī)則作用于表示事實(shí)的與/或圖，改變與/或圖的結(jié)構(gòu)，從而產(chǎn)生新的事實(shí)，直至推出了目標(biāo)公式，則推理就成功結(jié)束 正向演

55、繹中的目標(biāo)公式規(guī)定為文字的析取式，當(dāng)一個(gè)目標(biāo)文字和與/或圖中的一個(gè)文字匹配時(shí)，可以將表示該目標(biāo)文字的結(jié)點(diǎn)通過(guò)匹配弧連接到與/或圖中相應(yīng)的文字的結(jié)點(diǎn)上 表示目標(biāo)文字的結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)，當(dāng)演繹產(chǎn)生的與/或圖包括一個(gè)在目標(biāo)結(jié)點(diǎn)上結(jié)束的解圖時(shí)，推理便成功結(jié)束,2020/9/1,93,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過(guò)程 推理過(guò)程為： 首先用與/或圖把已知事實(shí)表示出來(lái) 用F規(guī)則的左部和與/或圖的葉結(jié)點(diǎn)進(jìn)行匹配，并將匹配成功的F規(guī)則加入到與/或圖中，即利用F規(guī)則轉(zhuǎn)換與/或圖 重復(fù)第步，直到產(chǎn)生一個(gè)含有以目標(biāo)結(jié)點(diǎn)作為終止結(jié)點(diǎn)的解圖為止,2020/9/1,94,3 基于規(guī)則的演繹推理,正向演繹推

56、理 （4）推理過(guò)程 【例48】設(shè)已知事實(shí)為：AB F規(guī)則為：ACD ，BEG 目標(biāo)公式為：CGF 證明：1.將事實(shí)表達(dá)式用與/或圖表示,2020/9/1,95,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過(guò)程 【例48】證明 2.用F規(guī)則的左部與上頁(yè)中的葉結(jié)點(diǎn)匹配，并轉(zhuǎn)換與或圖新與/或圖 圖中包括一個(gè)在目標(biāo)結(jié)點(diǎn)上結(jié)束的解圖，該解圖對(duì)應(yīng)的子句為CG（注意此子句與目標(biāo)公式CGF不同，但比目標(biāo)公式更一般，所以目標(biāo)公式成立）,2020/9/1,96,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過(guò)程 【例48】證明,2020/9/1,97,3 基于規(guī)則的演繹推理,正向演繹推理 （4）推理過(guò)程 【

57、例48】驗(yàn)證其推理的正確性，再用歸結(jié)反演來(lái)證明 由已知事實(shí)、F規(guī)則及目標(biāo)的 否定所構(gòu)成的子句集為： AB AC，AD BE，BG C，G，F(xiàn) 子句的歸結(jié)過(guò)程：（歸結(jié)得空子句N(xiāo)IL）,2020/9/1,98,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達(dá)式 如果事實(shí)表達(dá)式、規(guī)則和目標(biāo)表達(dá)式中有變量，則在推理中需要用最一般的合一進(jìn)行變量的代換,2020/9/1,99,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達(dá)式 【例49】設(shè)已知 事實(shí)為： P(A)Q(A)R(A) F規(guī)則為：R1：P(x)S(x) R2：Q(y)N(y) 證明目標(biāo)公式：S(z)N(z) 證明： 解圖對(duì)應(yīng)

58、的子句為： S(z) N(z),2020/9/1,100,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達(dá)式 【例49】驗(yàn)證（歸結(jié)反演） 已知事實(shí)、F規(guī)則及目標(biāo)的否定 所構(gòu)成的子句集為： P(A)Q(A)，P(A)R(A) P(x)S(x) Q(y)N(y) S(z)，N(z) 歸結(jié)反演圖： 歸結(jié)出空子句，證明目標(biāo)公式成立,2020/9/1,101,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達(dá)式 當(dāng)事實(shí)表達(dá)式、F規(guī)則和目標(biāo)表達(dá)式中包含變量時(shí)，只有當(dāng)解圖中所用的置換是一致時(shí)，該解圖對(duì)應(yīng)的子句才成立 在【例49】解圖中使用的置換A/x，A/z和A/y，A/z是一致的，所以該

59、子句成立 將兩個(gè)置換的合一復(fù)合A/x，A/y，A/z作用于子句S(z)N(z)得到：S(A)N(A)，這才是真正的結(jié)論,2020/9/1,102,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達(dá)式 【定義46】設(shè)有一個(gè)置換集U=u1,u2,un ,每個(gè)ui是一個(gè)置換對(duì)的集合， ui=ti1/vi1 , ti2 /vi2, , tim (i)/vim(i) 其中t為項(xiàng)，v為變量， 令： U1=( v11, ,v1m(1),v21, ,v2m(2) ,vnm(n) U2=( t11, , t1m(1), t21, , t2m(2) ,tnm(n) 則置換U是一致的充要條件是U1和U2可合一。而U的合一復(fù)合u=mgu(U1,U2),2020/9/1,103,3 基于規(guī)則的演繹推理,正向演繹推理 （5）含有變量的表達(dá)式 置換的一致性和置換的合一復(fù)合例： 1)u1=A/x,A/z, u2=A/y, A/z, 則U=u1，u2是一致的，其合一復(fù)合為 A/x，A/y, A/z 2)u