人工智能自動(dòng)推理

2023/1/111第4章

自動(dòng)推理2023/1/1124.1引言2023/1/113什么是推理推理就是按某種策略由已知判斷推出另一判斷的思維過程已知判斷：包括已掌握的與求解問題有關(guān)的知識(shí)及關(guān)于問題的已知事實(shí)推理的結(jié)論：由已知判斷推出新判斷推理由程序程序?qū)崿F(xiàn)，稱為推理機(jī)2023/1/114推理方式及其分類1、演繹推理、歸納推理、默認(rèn)推理推理的基本任務(wù)是從一種判斷推出另一種判斷按判斷推出的途徑來劃分，可分為演繹推理、歸納推理及默認(rèn)推理（1）演繹推理演繹推理是從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過程演繹推理有多種形式，經(jīng)常用的是三段論式三段論式包括大前提：已知的一般性知識(shí)或假設(shè)小前提：關(guān)于所研究的具體情況或個(gè)別事實(shí)的判斷結(jié)論：由大前提推出的適合于小前提所示情況的新判斷2023/1/115推理方式及其分類在任何情況下，由演繹推導(dǎo)出的結(jié)論都是蘊(yùn)涵在大前提的一般性知識(shí)中只要大前提和小前提是正確的，則由它們推出的結(jié)論必然是正確的(2)歸納推理歸納推理是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種從個(gè)別到一般的推理歸納推理：完全歸納推理、不完全歸納推理完全歸納推理是在進(jìn)行歸納時(shí)考察了相應(yīng)事物的全部對(duì)象，并根據(jù)這些對(duì)象是否都具有某種屬性，從而推出這個(gè)事物是否具有這個(gè)屬性不完全歸納推理是指只考察了相應(yīng)事物的部分對(duì)象就得出了結(jié)論2023/1/116推理方式及其分類枚舉歸納推理：若已知某類事物的有限可數(shù)個(gè)具體事物都具有某種屬性，則可推出該類事物都具有此屬性類比推理：在兩個(gè)或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們在其他屬性上也相同或相似的一種推理(3)默認(rèn)推理又稱缺省推理，它是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理擺脫了需要知道全部事實(shí)才能進(jìn)行推理的需求，使得在知識(shí)不完全的情況下也能進(jìn)行推理2023/1/117推理方式及其分類2、確定性推理、不確定性推理按推理時(shí)所用知識(shí)的確定性來劃分，推理可分為確定性推理、不確定性推理確定性推理（精確推理）：推理時(shí)所用的知識(shí)都是精確的，推出的結(jié)論也是確定的，其真值或者為真，或?yàn)榧?，沒有第三種情況出現(xiàn)不確定性推理（不精確推理）：推理時(shí)所用的知識(shí)不都是精確的，推出的結(jié)論也不完全是肯定的，真值位于真與假之間，命題的外延模糊不清2023/1/118推理方式及其分類3、單調(diào)推理、非單調(diào)推理按推理過程中推出的結(jié)論是否單調(diào)地增加，或推出的結(jié)論是否越來越接近目標(biāo)，可分為單調(diào)推理和非單調(diào)推理單調(diào)推理：在推理過程中隨著推理的向前及新知識(shí)的加入，推出的結(jié)論是呈單調(diào)增加的趨勢，并且越來越接近最終目標(biāo)，在推理過程中不出現(xiàn)反復(fù)的情況非單調(diào)推理：在推理過程中由于新知識(shí)的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始非單調(diào)推理往往在信息不完全或者情況發(fā)生變化時(shí)出現(xiàn)。2023/1/119推理的控制策略推理過程是一個(gè)思維過程，即求解問題的過程推理的控制策略主要包括推理方向、搜索策略、沖突消解策略、求解策略及限制策略等1、推理方向推理方向用于確定推理的驅(qū)動(dòng)方式，分為正向推理、逆向推理、混合推理及雙向推理四種知識(shí)庫綜合數(shù)據(jù)庫推理機(jī)2023/1/1110推理的控制策略正向推理正向推理是從初始狀態(tài)出發(fā)，使用規(guī)則，到達(dá)目標(biāo)狀態(tài)。又稱為數(shù)據(jù)驅(qū)動(dòng)推理、前向鏈推理、模式制導(dǎo)推理及前件推理。逆向推理逆向推理是以某個(gè)假設(shè)目標(biāo)為出發(fā)點(diǎn)的一種推理，又稱為目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理、目標(biāo)制導(dǎo)推理及后件推理2022/12/3111正、逆向推推理比較

項(xiàng)目正向推理逆向推理驅(qū)動(dòng)方式數(shù)據(jù)驅(qū)動(dòng)目標(biāo)驅(qū)動(dòng)推理方法從一組數(shù)據(jù)出發(fā)向前推導(dǎo)結(jié)論從可能的解出發(fā)向后推理驗(yàn)證解答啟動(dòng)方法從一個(gè)事件啟動(dòng)由詢問關(guān)于目標(biāo)狀態(tài)的一個(gè)問題啟動(dòng)透明程度不能解釋其推理過程可解釋其推理過程推理方向由底向上推理由頂向下推理典型系統(tǒng)CLIPS，OPSPROLOG2022/12/3112推理的控制制策略混合推理已知的事實(shí)實(shí)不充分。。通過正向向推理先把把其運(yùn)用條條件不能完完全匹配的的知識(shí)都找找出來，并并把這些知知識(shí)可導(dǎo)出出的結(jié)論作作為假設(shè)，，然后分別別對(duì)這些假假設(shè)進(jìn)行逆逆向推理由正向推理理推出的結(jié)結(jié)論可信度度不高希望得到更更多的結(jié)論論推理的形式式：先正向再逆逆向，通過正向向推理，即即從已知事事實(shí)演繹出出部分結(jié)果果，然后再再用逆向推推理證實(shí)該該目標(biāo)或提提高其可可信度先逆向再正正向，先假設(shè)一一個(gè)目標(biāo)進(jìn)進(jìn)行逆向推推理，然后后再利用逆逆向推理中中得到的信信息進(jìn)行正正向推理，，以推出更更多的結(jié)論論2022/12/3113推理的控控制策略略雙向推理理雙向推理理是指正正向推理理與逆向向推理同同時(shí)進(jìn)行行，且在在推理過過程中的的某一步步驟上“碰頭”的一種推推理。正向推理理所得的的中間結(jié)結(jié)論恰好好是逆向向推理此此時(shí)要求求的證據(jù)據(jù)2、求解策策略推理是只只求一個(gè)個(gè)解還是是求所有有解以及及最優(yōu)解解等3、限制策策略對(duì)推理的的深度、、寬度、、時(shí)間、、空間等等進(jìn)行限限制2022/12/3114推理的控控制策略略4、沖突消解解策略在推理過過程中，，匹配會(huì)會(huì)出現(xiàn)三三種情況況已知事實(shí)實(shí)不能與與知識(shí)庫庫中的任任何知識(shí)識(shí)匹配成成功已知事實(shí)實(shí)恰好只只與知識(shí)識(shí)庫中的的一個(gè)知知識(shí)匹配配成功已知事實(shí)實(shí)可與知知識(shí)庫中中的多個(gè)個(gè)知識(shí)匹匹配成功功；或者者有多個(gè)個(gè)（組））已知事事實(shí)都可可與知識(shí)識(shí)庫中某某一知識(shí)識(shí)匹配成成功；或或者有多多個(gè)（組組）已知知事實(shí)可可與知識(shí)識(shí)庫中的的多個(gè)知知識(shí)匹配配成功出現(xiàn)沖突突的情況況對(duì)正向推推理而言言，如果果有多條條產(chǎn)生式式規(guī)則的的前件都都和已知知的事實(shí)實(shí)匹配成成功；或或者有多多組不同同的已知知事實(shí)都都與同一一條產(chǎn)生生式規(guī)則則的前件件匹配成成功；或或者兩種種情況同同時(shí)出現(xiàn)現(xiàn)2022/12/3115推理的控控制策略略對(duì)逆向推推理而言言，如果果有多條條產(chǎn)生式式的后件件都和同同一假設(shè)設(shè)匹配成成功，或或者有多多條產(chǎn)生生式后件件可與多多個(gè)假設(shè)設(shè)匹配成成功。按就近原原則排序序該策略把把最近被被使用過過的規(guī)則則賦予較較高的優(yōu)優(yōu)先級(jí)。。按已知事事實(shí)的新新鮮性排排序一般我們們認(rèn)為新新鮮事實(shí)實(shí)是對(duì)舊舊知識(shí)的的更新和和改進(jìn)，，比老知知識(shí)更有有效，即即后生成成的事實(shí)實(shí)比先生生成的事事實(shí)具有有較大的的優(yōu)先性性。2022/12/3116推理的控制策策略按匹配度排序序在不確定推理理時(shí)，匹配度度不僅可確定定兩個(gè)知識(shí)模模式是否可匹匹配，還可用用于沖突消解解。根據(jù)匹配配程度來決定定哪一個(gè)產(chǎn)生生式規(guī)則優(yōu)先先被應(yīng)用。按領(lǐng)域問題特特點(diǎn)排序該方法按照求求解問題領(lǐng)域域的特點(diǎn)將知知識(shí)排成固定定的次序。按上下文限制制排序該策略將知識(shí)識(shí)按照所描述述的上下文分分成若干組，，在推理過程程中根據(jù)當(dāng)前前數(shù)據(jù)庫中的的已知事實(shí)與與上下文的匹匹配情況，確確定選擇某組組中的某條知知識(shí)。2022/12/3117推理的控制策策略按條件個(gè)數(shù)排排序多條規(guī)則生成成的結(jié)論相同同的情況下，，由于條件個(gè)個(gè)數(shù)較少的規(guī)規(guī)則匹配所花花費(fèi)的時(shí)間較較少而且容易易實(shí)現(xiàn)，所以以將條件少的的規(guī)則賦予較較高的優(yōu)先級(jí)級(jí)，優(yōu)先被啟啟用。按規(guī)則的次序序排序該策略是以知知識(shí)庫中預(yù)先先存入規(guī)則的的排列順序作作為知識(shí)排序序的依據(jù)，排排在前面的規(guī)規(guī)則具有較高高的優(yōu)先級(jí)。。2022/12/31184.3自然演繹推理理2022/12/3119自然演繹推理理的基本概念念定義：自然演繹推理理是指從一組組已知的事實(shí)實(shí)出發(fā)，直接接運(yùn)用命題邏邏輯或謂詞邏邏輯中的推理理規(guī)則推出結(jié)結(jié)論的過程。。推理規(guī)則：P規(guī)則：在推理的任何何步驟上都可可引入前提，，繼續(xù)進(jìn)行推推理。T規(guī)則：推理時(shí)，如果果前面步驟中中有一個(gè)或多多個(gè)公式永真真蘊(yùn)涵公式S，則可把S引入推理過程程中。反證法：，當(dāng)且僅當(dāng)。。即：：Q為P的邏輯結(jié)論，，當(dāng)且僅當(dāng)是是不可可滿足的。2022/12/3120自然演演繹推推理的的基本本概念念假言推推理表示：：由及及P為真，，可推推出Q為真拒取式式推理理表示：：由為為真真及Q為假，，可推推出P為假2022/12/3121自然演演繹推推理的的基本本概念念肯定后后件(Q)的錯(cuò)誤誤：當(dāng)當(dāng)P→Q為真時(shí)時(shí),希望通通過肯肯定后后件Q推出前前件P為真,這是不不允許許的.否定前前件(P)的錯(cuò)誤誤：當(dāng)當(dāng)P→Q為真時(shí)時(shí),希望通通過否否定前前件P推出后后件Q為假,這也是是不允允許的的.避免產(chǎn)產(chǎn)生兩兩類錯(cuò)錯(cuò)誤：：2022/12/3122自然演演繹推推理的的基本本概念念如果行行星系系統(tǒng)是是以太太陽為為中心心的,則金星星會(huì)顯顯示出出位相相變化化。金星會(huì)會(huì)顯示示出位位相變變化。。所以，，行星星系統(tǒng)統(tǒng)是以以太陽陽為中中心的的。如伽利利略在在論證證哥白白尼的的日心心說時(shí)時(shí),曾使用用了下下列推推理：：這就是是使用用了肯肯定后后件的的推理理，違違反了了經(jīng)典典邏輯輯的邏邏輯規(guī)規(guī)則,他為此此曾遭遭到非非難。。2022/12/3123自然演演繹推推理的的基本本概念念如果上上網(wǎng)，，則能能知道道新聞聞。沒有上上網(wǎng)。。所以，，不知知道新新聞。。又如下下列推推理：：這就是是使用用了否否定前前件的的推理理,違反了了邏輯輯規(guī)則則,顯然是是不正正確的的,因?yàn)橥ㄍㄟ^收收聽廣廣播、、看電電視等等，也也會(huì)知知道新新聞。。2022/12/3124自然然演演繹繹推推理理的的優(yōu)優(yōu)缺缺點(diǎn)點(diǎn)優(yōu)點(diǎn)點(diǎn)：：定理理證證明明過過程程自自然然，，容容易易理理解解，，而而且且它它擁擁有有豐豐富富的的推推理理規(guī)規(guī)則則，，推推理理過過程程靈靈活活，，便便于于在在它它的的推推理理規(guī)規(guī)則則中中嵌嵌入入領(lǐng)領(lǐng)域域啟啟發(fā)發(fā)式式知知識(shí)識(shí)。。缺點(diǎn)點(diǎn)：：容易易產(chǎn)產(chǎn)生生組組合合爆爆炸炸，，推推理理過過程程中中得得到到的的中中間間結(jié)結(jié)論論一一般般呈呈指指數(shù)數(shù)形形式式遞遞增增。。2022/12/3125人的的問問題題求求解解行行為為更更像像是是一一個(gè)個(gè)解答答識(shí)識(shí)別別過程程而而非非解答答搜搜索索過程程識(shí)別別解解答答或或部部分分解解答答依依賴賴于于應(yīng)應(yīng)用用領(lǐng)領(lǐng)域域特特有有的的知知識(shí)識(shí)，，符號(hào)號(hào)推推理理則則成成為為基基于于知知識(shí)識(shí)來來求求解解問問題題的的主主要要手手段段。。符號(hào)號(hào)推推理理的的重重要要方方式式是是演演繹繹推推理理它的的基基礎(chǔ)礎(chǔ)為為謂謂詞詞演演算算———一種種形式式語語言言將各各種種陳陳述述性性（（說說明明性性））的的描描述述以以形式式化化的方方式式表表示示，，以以便便對(duì)對(duì)它它們們作作處處理理。。謂詞詞演演算算———人工工智智能能系系統(tǒng)統(tǒng)最最常常用用的的知知識(shí)識(shí)表表示示方方法法，，廣泛泛地地應(yīng)應(yīng)用用于于各各種種人人工工智智能能系系統(tǒng)統(tǒng)的的設(shè)設(shè)計(jì)計(jì)。。謂詞詞演演算算（（或或更更廣廣義義地地，，形形式式邏邏輯輯））是是人人工工智智能能研研究究的的重重要要基基礎(chǔ)礎(chǔ)之之一一。。主要要內(nèi)內(nèi)容容：：謂詞詞演演算算H域和和海海伯伯倫倫定定理理歸結(jié)結(jié)原原理理歸結(jié)結(jié)反反演演歸結(jié)結(jié)演演繹繹推推理理★2022/12/3126回顧顧謂謂詞詞邏邏輯輯表表示示法法1、謂謂詞詞公公式式“謂謂詞詞公公式式””的的一一般般形形式式：：P(x1,x2,……,xn)，其其中中，，P————謂詞詞符符號(hào)號(hào)（簡簡稱稱謂謂詞詞））；；Xi(i=1,2,……,n)————參數(shù)數(shù)項(xiàng)項(xiàng)（簡簡稱稱項(xiàng)項(xiàng)）），，項(xiàng)項(xiàng)可可以以是常常量量、變量量或函數(shù)數(shù)；P(x1,x2,……,xn)————n元謂謂詞詞公公式式；；“謂謂詞詞公公式式””的的基基本本組組成成：：謂詞詞符符號(hào)號(hào)、常量量符符號(hào)號(hào)、變量量符符號(hào)號(hào)、函數(shù)數(shù)符符號(hào)號(hào)；用括號(hào)號(hào)和逗號(hào)號(hào)隔開開，，表示示論論域域內(nèi)內(nèi)的的關(guān)關(guān)系系。“謂謂詞詞公公式式是謂謂詞詞邏邏輯輯的的基基本本單單元元，，也也稱稱為為原子子公公式式。2022/12/31272、連連詞詞和和量量詞詞通過過引引入入連詞詞和量詞詞，可可以以把把謂詞詞公公式式（（原原子子公公式式））組合合為為復(fù)合合謂謂詞詞公公式式。復(fù)合合謂謂詞詞公公式式也稱稱為為邏輯輯語語句句。（1）連連詞詞（非）加加在謂詞公式式前面，稱稱為否定定，或取取反。（與）連連接謂詞公式式，稱為合??；產(chǎn)生的邏輯語句句稱為合取式，每個(gè)成成分成為為合取項(xiàng)。。（或）連連接謂詞公式式，稱為析??；產(chǎn)生的邏輯語句句稱為析取式，每個(gè)成成分成為為析取項(xiàng)。。（蘊(yùn)涵））連接謂詞公式式產(chǎn)生蘊(yùn)涵式；左部稱為為前項(xiàng)，右部稱稱為后項(xiàng)。（等價(jià)））連接謂詞公式式產(chǎn)生等價(jià)式；正、逆逆向蘊(yùn)涵涵式的合合取。2022/12/31282、連詞和和量詞通過引入入連詞和和量詞，，可以把把原子公式式組合為復(fù)合謂詞詞公式。復(fù)合謂詞詞公式也也稱為邏輯語句句。（1）連詞通過連詞詞產(chǎn)生的的復(fù)合謂謂詞公式式（邏輯輯語句））的真值表：PQPP∧QP∨QPQPQTTFTTTTFTTFTTFTFFFTFFFFTFFTT2022/12/31292、連詞和和量詞命題——不包含變量的謂詞公式式和邏輯語句句；命題邏輯輯——基于命題的謂詞邏輯輯稱為命題邏輯輯，命題邏輯輯是謂詞詞邏輯的的子集。命題邏輯輯缺乏有效效的表達(dá)達(dá)一般性概概念的能力無法把每每個(gè)知識(shí)識(shí)單元抽抽象、細(xì)細(xì)分；如，“條條條大路路通羅馬馬”。Lead(Road1,Roma)Lead(Road2,Roma)……謂詞邏輯輯中引入變量和對(duì)變量量進(jìn)行約約束的量詞。（2）量詞全稱量詞詞存在量詞詞2022/12/31302、連詞和和量詞——（2）量詞全稱量詞詞符號(hào)(x)P(x)：表示對(duì)對(duì)于某個(gè)個(gè)論域中中的所有（任任意一個(gè)個(gè)）個(gè)體x,都有P(x)真值為T。存在量詞詞符號(hào)(x)P(x)：來表示示某個(gè)論論域中至少存在在一個(gè)個(gè)體x，使P(x)真值為T。條條大路路通羅馬馬Mary給每個(gè)人人一本書書Mary給每人某某個(gè)同樣樣的東西西量詞可以以嵌套使使用可以有不不受量詞詞約束的的變量2022/12/31312、連詞和和量詞——（2）量詞全稱量詞詞符號(hào)(x)P(x)：表示對(duì)對(duì)于某個(gè)個(gè)論域中中的所有（任任意一個(gè)個(gè)）個(gè)體x,都有P(x)真值為T。存在量詞詞符號(hào)(x)P(x)：來表示示某個(gè)論論域中至少存在在一個(gè)個(gè)體x，使P(x)真值為T。條條大路路通羅馬馬所有機(jī)器器人都是是灰色的的2022/12/3132一階謂謂詞邏邏輯定義：：若限定定不允許許對(duì)謂詞和函數(shù)名名進(jìn)行量化處理，，且參數(shù)項(xiàng)項(xiàng)不能是是謂詞公公式，則這這樣的的謂詞詞邏輯輯是一階的。謂詞、、函數(shù)數(shù)名的出現(xiàn)現(xiàn)位置置不允許許使用用變量量；參數(shù)項(xiàng)項(xiàng)不能是是謂詞公公式；(P)P(A)-謂詞進(jìn)進(jìn)行了了量化化；(y)Married(y(L1),Mary)-函數(shù)名名進(jìn)行行了量量化；；P(x,Q(y))-參數(shù)項(xiàng)項(xiàng)是謂謂詞公公式；；2022/12/3133合適(式)公式1、合適適公式式的定定義合適公公式適合于于一階謂謂詞邏邏輯遵從以以下遞遞歸方方式定定義的的邏輯語語句稱為合適公公式①單一謂謂詞公公式是是合適適公式式；②若A是合適適公式式，則則A也是合合適公公式；；③若A和B都是合合適公公式，，則A∧B、A∨B、AB和AB也都是是合適適公式式；④若A是合適適公式式，x是約束束變量量，則則(x)A和(x)A也都是是合適適公式式；⑤只有按按上述述規(guī)則則①-④求得的的公式式，才才是合合適公公式。。連詞優(yōu)優(yōu)先級(jí)級(jí)別是，∧、∨∨，、，但可可通過過括號(hào)改變優(yōu)優(yōu)先級(jí)級(jí)。2022/12/3134合適公公式的的性質(zhì)質(zhì)合適公公式等等價(jià)關(guān)關(guān)系:否定之否定定?(?P)P蘊(yùn)涵式轉(zhuǎn)化化PQ?P∨Q狄摩根定律律?(P∨Q)?P∧?Q?(P∧Q)?P∨?Q分配律P∧(Q∨∨R)(P∧Q)∨(P∧∧R）P∨(Q∧∧R)(P∨Q)∧(P∨∨R)5.交換律P∨QQ∨PP∧QQ∧P2022/12/3135合適公式的的性質(zhì)6.結(jié)合律(P∧Q)∧RP∧(Q∧∧R）(P∨Q)∨RP∨（Q∨R）7.逆否律PQ?Q?P8.量詞否定?($x)P(x)(x)(?P(x))?(x)P(x)（x)(?P(x))2022/12/3136合適公式的的性質(zhì)9.量詞分配(x)[P(x)∧Q(x)](x)P(x)∧(x)Q(x)(x）[P(x)∨Q(x)]（x）P(x)∨∨(x)Q(x)10.約束變量的的虛元性(x)P(x)(y)P(y)(x)P(x)(y)P(y)(x)[P(x)∧∧Q(x)](x)P(x)∧∧(y)Q(y)(x)[P(x)∨∨Q(x)](x)P(x)∨∨(y)Q(y)2022/12/3137合適公式的的標(biāo)準(zhǔn)化★1、標(biāo)準(zhǔn)化需需求常見的基于于謂詞演算算的推理：：歸結(jié)反演、(正向/逆向)歸結(jié)演繹推推理要求以量詞前束范范式來表示合適適公式量詞前束范范式形式如下：：(Q1x1)(Q2x2)…(Qkxk)M，其中M——母式，不包包括任何量量詞；Qixi——Qi可以是量詞符號(hào)或；xi是量詞的約束變量(i=1,2,…,k)2022/12/3138前束范式例1：變公式（（x）P（x）=>（x）Q（x）為前束范范式~（x）P（x）∨（x）Q（x）（x）（~P（x））∨（x）Q（x）（x）（（~P（x）∨∨Q（x）））為為前前束束范范式式2022/12/3139前束束范范式式例2：(x)(y){((z)(P(x，z)∧∧P(y，z))=>(u)Q(x，y，u))}x)(y)(~((z)(P(x，z)∧∧P(y，z)))∨∨(u)Q(x，y，u))(x)(y)(z)(~P(x，z)∨∨~P(y，z))∨∨(u)Q(x，y，u)x)(y)(z)(u)(~P(x，z)∨∨~P(y，z)∨∨Q(x，y，u))2022/12/3140史柯柯倫倫標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型及及其其構(gòu)構(gòu)造造思思想想史柯柯倫倫（（Skolem）標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型：海海伯伯倫倫（（Herbrand）定定理理是是歸歸結(jié)結(jié)原原理理的的基基礎(chǔ)礎(chǔ)。。海海伯伯倫倫定定理理證證明明的的步步驟驟實(shí)實(shí)際際上上是是反反演演法法，，即即不不是是證證明明一一個(gè)個(gè)公公式式是是永永真真，，而而是是證證明明該該公公式式是是否否是是永假假的。。反反演演法法利利用用了了一一個(gè)個(gè)標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型，，這這個(gè)個(gè)標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型就就是是Skolem標(biāo)準(zhǔn)準(zhǔn)型型。。2022/12/3141一階階邏邏輯輯公公式式所所對(duì)對(duì)應(yīng)應(yīng)的的Skolem標(biāo)準(zhǔn)準(zhǔn)型型基基于于如如下下思思想想來來構(gòu)構(gòu)造造：：一階階邏邏輯輯的的一一個(gè)個(gè)公公式式被被變變換換為為前前束束范范式式。。其其中中前前束束是是一一個(gè)個(gè)存在在量量詞詞或全稱稱量量詞詞的序序列列，，母母式式中中不不在在含含有有量量詞詞。。因?yàn)闉槟改甘绞讲徊缓苛吭~詞，，所所以以可可以以變變換換為為合取取范式式。。通過過使使用用Skolem函數(shù)數(shù)，，可可以以在在前前束束中中將將存存在在量量詞詞消消去去，，而而不不影影響響公公式式的的永永假假性性。。2022/12/3142Skolem標(biāo)準(zhǔn)準(zhǔn)型型通過過變變換換消去去存存在在量量詞詞所得得到到的的公公式式稱稱為為Skolem標(biāo)準(zhǔn)準(zhǔn)型型，而而拿拿來來代代替替存存在在量量詞詞的的變變量量的的函函數(shù)數(shù)稱稱Skolem函數(shù)數(shù)。無無參參Skolem函數(shù)數(shù)有有時(shí)時(shí)稱稱Skolem常量量。從從一一階階邏邏輯輯的的公公式式變變換換到到Skolem標(biāo)準(zhǔn)準(zhǔn)型型不是是等值值變變換換，，因因?yàn)闉镾kolem標(biāo)準(zhǔn)準(zhǔn)型型與與原原公公式式不不等等值值。。但但它它們們保保持持永永假假性性。。2022/12/3143合適適公公式式的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化★1、標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化需需求求常見見的的基基于于謂謂詞詞演演算算的的推推理理：：歸結(jié)結(jié)反反演演、(正向向/逆向向)演繹繹推推理理要求以量詞前束范式式來表示合適公公式量詞前束范式式形式如下：(Q1x1)(Q2x2)…(Qkxk)M，其中M——母式，不包括括任何量詞；；Qixi——Qi可以是量詞符號(hào)或；xi是量詞的約束變量(i=1,2,…,k)歸結(jié)反演——要求M標(biāo)準(zhǔn)化為合取范式，定義如下：：M=W1∧W2∧…∧WnWi=Li1∨Li2∨…∨Lim(i=1,2,…,n)Lij=Pij|Pij:文字（Literal），是謂詞公式Pij或其取反2022/12/31442、合取范式的的標(biāo)準(zhǔn)化過程程應(yīng)用合適公式性質(zhì)質(zhì)將公式逐步轉(zhuǎn)轉(zhuǎn)化的過程。。轉(zhuǎn)化步驟沒有有嚴(yán)格的規(guī)定定較合理的化簡簡過程，分為為8步：①消去多余的的量詞（很少少出現(xiàn)）；②消去蘊(yùn)涵符符號(hào)；③減少否定的的轄域（內(nèi)移移否定符號(hào)））；④變量標(biāo)準(zhǔn)化化（變量換名名）；⑤消去存在量量詞(Skolem變換)；⑥全稱量詞前前束化（化為為前束形）；；⑦消去全稱量量詞；⑧把母式轉(zhuǎn)化為合取范式。2022/12/31452、合取范式的的標(biāo)準(zhǔn)化過程程①消去多余的的量詞（很少少出現(xiàn)）若一個(gè)量詞的轄轄域內(nèi)并未出出現(xiàn)量詞的約約束變量，則該量詞是是多余的，應(yīng)應(yīng)該刪除；例，(x)P(y)，則(x)可以消去，得得到P(y)；正常情況下，，合適公式中中不應(yīng)出現(xiàn)多多余的量詞。。②消去蘊(yùn)涵符符號(hào)蘊(yùn)涵式轉(zhuǎn)化：PQP∨∨Q；例，Q(x,y)P(y)Q(x,y)∨P(y)。2022/12/31462、合取范式的的標(biāo)準(zhǔn)化過程程③內(nèi)移否定符符號(hào)使否定只出現(xiàn)現(xiàn)在原子謂詞詞公式前，構(gòu)構(gòu)成否定文字；狄.摩根定律：(P∨Q)P∧Q(P∧Q)P∨∨Q雙重否定：(P)P量詞否否定：：(x)P(x)(x)(P(x))(x)P(x)(x)(P(x))例，(y)[P(y)∨P(f(x,y))](y)[P(y)∧P(f(x,y))]④變量換換名“⑥全稱稱量詞詞前束束化”后，，同名名變量量的轄轄域無無法區(qū)區(qū)分，，所以以為避避免差差錯(cuò)，，必須須換名名；約束變變量的的虛元元性進(jìn)行變變換；；(x){p(x)=>（x）Q（x）}標(biāo)準(zhǔn)化化而得得到（（x）{p(x)=>（y）Q（y）}2022/12/31472、合取取范式式的標(biāo)標(biāo)準(zhǔn)化化過程程⑤消去去存在在量詞詞（Skolem變換）在的轄域域內(nèi)(z)(w)[Q(x,z)∨∨P(z,w)]w依賴于于z，由函函數(shù)w=g(z)來定義義這種種依賴賴關(guān)系系；用g(z)來取代代約束束變量量w，消去去存在在量詞詞w；(z)[Q(x,z)∨∨P(z,g(z))]在多個(gè)的轄域域內(nèi)(x)(y)(z)(w)P(x,y,z,w)用多元元函數(shù)數(shù)g(x,y,z)來取代代約束束變量量w，消去去存在在量詞詞w；(x)(y)(z)P(x,y,z,g(x,y,z))在的轄轄域外外(w)(z)[Q(x,z)∨∨P(z,w)]用任意常常量A取代約約束變變量w，消去去存在在量詞詞w(z)[Q(x,z)∨∨P(z,A)]前兩種種叫Skolem函數(shù)，，第三三種叫叫Skolem常量2022/12/3148總結(jié)：：Skolem函數(shù)和Skolem常量★在消去去存在在量詞詞的過過程中中，需需要用用到Skolem函數(shù)或或Skolem常量。。若存在量量詞是是在全全稱量量詞的的轄域域內(nèi)，用Skolem函數(shù)消消去存存在量量詞。Skolem函數(shù)所所使用用的函函數(shù)符符號(hào)必必須是是新的，即不不允許許是公公式中中已經(jīng)經(jīng)出現(xiàn)現(xiàn)過的的函數(shù)數(shù)符號(hào)號(hào)。若要消消去的的存在量量詞不不在任任何一一個(gè)全全稱量量詞的的轄域域內(nèi)，用不不含變變量的的Skolem函數(shù)即即Skolem常量消消去存存在量量詞。所使使用的的常量量符號(hào)號(hào)必須須是新的，它未未曾在在公式式其他他地方方使用用過。。Skolem變換不是等等價(jià)變變換，，但變變換前前后的的值永永假性性保持持不變變。2022/12/31492、合取范范式的標(biāo)標(biāo)準(zhǔn)化過過程⑥全稱量量詞前束束化經(jīng)過“④變量換換名”后，所所有量詞詞的約束束變量均均有不同同的名字字；只要簡單單地將移到合適適公式的的最前面面；約束變量量的作用用范圍不不會(huì)變化化。⑦消去全全稱量詞詞經(jīng)過“⑤消去存存在量詞詞”后，所所有變量量均受的約束；；簡單地刪刪除，只留下下母式。。⑧把母式式轉(zhuǎn)化為為合取范式式分配律：P∨(Q∧∧R)(P∨Q)∧∧(P∨∨R)2022/12/31502、合取范范式的標(biāo)標(biāo)準(zhǔn)化過過程例、化簡簡合適公公式(x){P(x){(y)[P(y)P(f(x,y))]∧(y)(w)[Q(x,y)P(y,w)]}}2022/12/31512、合取范范式的標(biāo)標(biāo)準(zhǔn)化過過程例、化簡簡合適公公式(x){P(x){(y)[P(y)P(f(x,y))]∧(y)(w)[Q(x,y)P(y,w)]}}②消去蘊(yùn)涵涵符號(hào)(x){P(x)∨{(y)[P(y)∨P(f(x,y))]∧(y)(w)[Q(x,y)∨P(y,w)]}}2022/12/31522、合取范范式的標(biāo)標(biāo)準(zhǔn)化過過程例、化簡簡合適公公式(x){P(x)∨{(y)[P(y)∨P(f(x,y))]∧(y)(w)[Q(x,y)∨P(y,w)]}}③內(nèi)移否定定符號(hào)(x){P(x)∧{(y)[P(y)∧P(f(x,y))]∨(y)(w)[Q(x,y)∨P(y,w)]}}2022/12/31532、合取取范式式的標(biāo)標(biāo)準(zhǔn)化化過程程例、化化簡合合適公公式(x){P(x)∧∧{(y)[P(y)∧∧P(f(x,y))]∨(y)(w)[Q(x,y)∨P(y,w)]}}④變量換換名(x){P(x)∧∧{(y)[P(y)∧∧P(f(x,y))]∨(z)(w)[Q(x,z)∨P(z,w)]}}2022/12/31542、合取取范式式的標(biāo)標(biāo)準(zhǔn)化化過程程例、化化簡合合適公公式(x){P(x)∧∧{(y)[P(y)∧∧P(f(x,y))]∨(z)(w)[Q(x,z)∨P(z,w)]}}⑤消去存存在量量詞{P(A)∧{(y)[P(y)∧∧P(f(A,y))]∨(z)[Q(A,z)∨P(z,g(z))]}}2022/12/31552、合取取范式式的標(biāo)標(biāo)準(zhǔn)化化過程程例、化化簡合合適公公式{P(A)∧∧{(y)[P(y)∧∧P(f(A,y))]∨(z)[Q(A,z)∨P(z,g(z))]}}⑥全稱量量詞前前束化化(y)(z){P(A)∧∧{[P(y)∧∧P(f(A,y))]∨[Q(A,z)∨P(z,g(z))]}}2022/12/31562、合取取范式式的標(biāo)標(biāo)準(zhǔn)化化過程程例、化化簡合合適公公式(y)(z){P(A)∧∧{[P(y)∧∧P(f(A,y))]∨[Q(A,z)∨P(z,g(z))]}}⑦消去全全稱量量詞{P(A)∧∧{[P(y)∧∧P(f(A,y))]∨[Q(A,z)∨P(z,g(z))]}}2022/12/31572、合取范式式的標(biāo)準(zhǔn)化化過程例3、化簡合適適公式{P(A)∧∧{[P(y)∧∧P(f(A,y))]∨[Q(A,z)∨P(z,g(z))]}}⑧把母式轉(zhuǎn)化化為合取范式{P(A)∧∧{[P(y)∨Q(A,z)∨P(z,g(z))]∧[P(f(A,y))∨Q(A,z)∨P(z,g(z))]}}完成標(biāo)準(zhǔn)化化過程！2022/12/3158歸結(jié)演繹推推理自動(dòng)定理證證明一般表表示形式為為：F1∧F2∧…∧FnWF1,F2,…,Fn都是合適公公式，表示示公理或事實(shí)；W是合適公式式，表示待證明的定定理，稱為目標(biāo)公式；證明的方法法可分兩大大類：演繹法直接證明F1∧F2∧…∧FnW為永真；反證法間接證明(F1∧F2∧…∧FnW)為永假；證明F1∧F2∧…∧Fn∧W的永假即{F1,F2,……,Fn}∪{W}是一個(gè)矛盾盾集。2022/12/3159歸結(jié)演繹推推理海伯倫（Herbrand）提出的H域（海伯倫倫域）和海伯倫定理理；為自動(dòng)定理證證明奠定了理論論基礎(chǔ)；魯賓遜（Robinson）提出的歸結(jié)原理；使自動(dòng)定理證證明成為可能。。2022/12/3160歸結(jié)演繹推推理1）H域和海伯倫倫定理（了了解）1、子句和子子句集子句——僅由文字的析取∨構(gòu)成的合適適公式Wi=Li1∨Li2∨…∨Lim稱為子句；合取范式定義：M=W1∧W2∧…∧WnWi=Li1∨Li2∨…∨Lim(i=1,2,…,n)Lij=Pij|Pij:文字（Literal），是原子謂謂詞公式Pij或其取反合取范式可定義為子句的合取∧；合取范式表示為子句集，子句間隱隱含合取∧關(guān)系子句集{W1,W2,…,Wn}2022/12/3161歸結(jié)演繹推推理1）H域和海伯倫倫定理1、子句和子子句集子句——僅由文字的析取∨構(gòu)成的合適適公式合取范式表示為子句集，子句間隱隱含具有合合取關(guān)系{P(A)∧[P(y)∨Q(A,z)∨P(z,g(z))]∧[P(f(A,y))∨Q(A,z)∨P(z,g(z))]}可進(jìn)一步表表示為子句句集{P(A),P(y)∨Q(A,z)∨P(z,g(z)),P(f(A,y))∨Q(A,z)∨P(z,g(z))}2022/12/3162歸結(jié)演繹繹推理1）H域和海伯伯倫定理理1、子句和和子句集集子句——僅由文字的析取∨構(gòu)成的合合適公式式合取范式式表示為為子句集，子句間間隱含具具有合取關(guān)系系(y)(z){P(A)∧[P(y)∨Q(A,z)∨P(z,g(z))]∧[P(f(A,y))∨Q(A,z)∨P(z,g(z))]}量詞分配配：(x)[P(x)∧Q(x)](x)P(x)∧(x)Q(x)(y)(z)P(A)∧(y)(z)[P(y)∨∨Q(A,z)∨P(z,g(z))]∧(y)(z)[P(f(A,y))∨∨Q(A,z)∨P(z,g(z))]2022/12/3163歸結(jié)演繹繹推理1）H域和海伯伯倫定理理1、子句和和子句集集子句中的的變量都都是的約束變變量{(y)(z)P(A),(y)(z)[P(y)∨Q(A,z)∨P(z,g(z))],(y)(z)[P(f(A,y))∨Q(A,z)∨P(z,g(z))]}為了消除除子句間間不必要要的交互互作用，，保持子子句的獨(dú)獨(dú)立性，，需要做做變量換名名{P(A),P(y1)∨Q(A,z1)∨P(z1,g(z1)),P(f(A,y2))∨Q(A,z2)∨P(z2,g(z2))}將合適公公式化成成字句集集，只需需要在化化成合取取范式的的基礎(chǔ)上上，去掉掉∧符號(hào)以以及進(jìn)行行變量換名名即可。。★2022/12/3164總結(jié):子句集的的求取1.消去蘊(yùn)涵涵符號(hào)2.減少否定定符號(hào)的的轄域3.對(duì)變量標(biāo)標(biāo)準(zhǔn)化4.消去存在在量詞5.化為前束束形6.把母式化化為合取取范式7.消去全稱稱量詞8.消去連詞詞符號(hào)9.更換變量量名稱1.消去蘊(yùn)涵符號(hào)只應(yīng)用∨和~符號(hào)，以~A∨B替換A=>B。2.減少否定符號(hào)的轄域

每個(gè)否定符號(hào)~最多只用到一個(gè)謂詞符號(hào)上，并反復(fù)應(yīng)用狄摩根律。如

以~A∨~B代替~（A∧B）

以~A∧~B代替~（A∨B）

以A代替~（~A）

以(x){~A}代替~（x）A

以x){~A}代替~（x）A3.對(duì)變量標(biāo)準(zhǔn)化在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元（虛構(gòu)變量），它可以在該轄域內(nèi)處處統(tǒng)一的被另一個(gè)沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值。合適公式中變量的標(biāo)準(zhǔn)化意味著對(duì)啞元改名以保證每個(gè)量詞有其自己唯一的啞元。如，把(x){p(x)=>(x)Q(x)}

標(biāo)準(zhǔn)化而得到（x）{p(x)=>(y)Q(y)}子句：文文字的析析取組成成的公式式。如如：（P∨Q∨∨R）2022/12/31651.消去蘊(yùn)涵符號(hào)號(hào)2.減少否定符號(hào)號(hào)的轄域3.對(duì)變量標(biāo)準(zhǔn)化化4.消去存在量詞詞5.化為前束形6.把母式化為合合取范式7.消去全稱量詞詞8.消去連詞符號(hào)號(hào)9.更換變量名稱稱4.消去存在量詞在公式（y）[（x）P（x，y）]中，存在量詞是在全稱量詞的轄域內(nèi)，我們允許所存在的x可能依賴于y值。令這種依賴關(guān)系明顯地由函數(shù)g（y）所定義，它把每個(gè)y值映射到存在的那個(gè)x。這種函數(shù)就是Skolem函數(shù)。如果用Skolem函數(shù)代替存在的x，我們就可以消去全部存在量詞（y）P[g（y），y]Skolem函數(shù)的變量是由那些全稱量詞所約束的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。Skolem函數(shù)所使用的函數(shù)符號(hào)必須是新的。

如果要消去的存在量詞不在任何一個(gè)全稱量詞的轄域內(nèi)，那么我們就用不含變量的Skolem函數(shù)即常量。例如，（x）P（x）化為P（A），其中常量符號(hào)A用來表示我們知道的存在實(shí)體?？偨Y(jié):子句集的求取取2022/12/31661.消去蘊(yùn)涵符號(hào)號(hào)2.減少否定符號(hào)號(hào)的轄域3.對(duì)變量標(biāo)準(zhǔn)化化4.消去存在量詞詞5.化為前束形6.把母式化為合合取范式7.消去全稱量詞詞8.消去連詞符號(hào)號(hào)9.更換變量名稱稱5.化為前束形

現(xiàn)在已不存在任何存在量詞，而且每個(gè)全稱量詞都有自己的變量，把所有全稱量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。所得公式稱前束形。前束形公式由全稱量詞串組成的前綴和不含量詞的母式組成。(x)(y){P(x)∨P(y)}6.把母式化為合取范式

任何母式都可以寫成由一些謂詞公式和謂詞公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。反復(fù)應(yīng)用分配率，如把A∨{B∧C}化為{A∨B}∧{A∨C}7.消去全稱量詞

所有余下的量詞均被全稱量詞量化了。全稱量詞的次序也不重要了。因此，我們可以消去前綴。8.消去連詞符號(hào)∧

用{A，B}代替{A∧B}，以消去明顯的符號(hào)∧。反復(fù)代替的結(jié)果，最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取。任一只由文字的析取構(gòu)成的合適公式叫做一個(gè)子句。9.更換變量名稱

更換變量名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中。這樣合式公式F化為子句集S后，F(xiàn)和S在永假性上是等價(jià)的總結(jié):子句集的求取取2022/12/3167更換變量名稱稱P(A)P(y1)∨Q(A,z1)∨P(z1,g(z1))]P(f(A,y2))∨Q(A,z2)∨P(z2,g(z2))實(shí)例(x){P(x){(y)[P(y)P(f(x,y))]∧(y)(w)[Q(x,y)P(y,w)]}}消去連詞符號(hào)號(hào)∧P(A)P(y)∨Q(A,z)∨P(z,g(z))P(f(A,y))∨∨Q(A,z)∨P(z,g(z))前面出的計(jì)算算的合取范式是{P(A)∧{[P(y)∨Q(A,z)∨P(z,g(z))]∧[P(f(A,y))∨∨Q(A,z)∨P(z,g(z))]}}2022/12/3168歸結(jié)演演繹推推理1）H域和海海伯倫倫定理理1、子句句和子子句集集合適公公式F合取范范式子句集集S合適公公式F永假子句集集S的不可可滿足足性充分必必要條條件重要性性質(zhì)S的不可可滿足足性任意論論域D上的任任意解解釋I,S中都至少有一個(gè)個(gè)子句真值為為F2022/12/3169歸結(jié)演演繹推推理1）H域和海海伯倫倫定理理1、子句句和子子句集集合適公公式F合取范范式子句集集S合適公公式F永假子句集集S的不可可滿足足性充分必必要條條件合適公公式F子句集集S不等價(jià)價(jià)S是F的特例例重要性性質(zhì)S的不可可滿足足性任意論論域D上的任任意解解釋I,S中都至少有一個(gè)個(gè)子句真值為為F2022/12/3170歸結(jié)演演繹推推理1）H域和海海伯倫倫定理理2、H域（了解解）證明子句集集S的不可可滿足足性與證明明合適公公式永永真性性類似由于個(gè)個(gè)體論域的任意意性和和解釋個(gè)數(shù)的的無限限性，，使得得證明明工作作十分困困難。若能建建造一一個(gè)較較為簡簡單的的特殊論論域，使得得只要要證明明子句句集S在該域域不可可滿足足，就就可確確保子子句集集在任何可可能的的論域域上不可可滿足足，將將是十十分有有意義義的！海伯倫倫建立立的特特殊域域H就具有有這樣樣的性性質(zhì)。。H域性質(zhì)質(zhì)——對(duì)于子子句集集S的任一一可能能論域域D上的任任一解解釋I，總能能在S的H域上構(gòu)造造一個(gè)個(gè)相應(yīng)應(yīng)的解解釋I*，使子子句集集S具有相相同的的真值值。證明子句集集S的不可可滿足足性確定子子句集集S在H域上的所所有解解釋都都不可可滿足足。2022/12/3171歸結(jié)結(jié)演演繹繹推推理理1）H域和和海海伯伯倫倫定定理理3、海海伯伯倫倫定定理理（了了解解））子句句集集S中一一子子句句包包含含的的變變量量用用H域中元元素素取取代代后后，，產(chǎn)產(chǎn)生生的的子子句句稱稱為為基子子句句。海伯伯倫倫定定理理：子句句集集S不可可滿滿足足的的充要要條條件件是存存在在一一個(gè)個(gè)有有限限的的不不可可滿滿足足的的基基子子句句集集S’’。有限限的的不不可可滿滿足足的的基基子子句句集集S’子句句集集S不可可滿滿足足性性充分分必必要要條條件件2022/12/3172歸結(jié)結(jié)演演繹繹推推理理2）歸歸結(jié)結(jié)原原理理★動(dòng)機(jī)機(jī)為提提高高判判定定子子句句集集S不可可滿滿足足的的有有效效性性，魯魯賓賓遜遜于于1965年提提出出了了歸結(jié)結(jié)(Resolution)原理理，也也稱稱為為消解解原原理理。歸結(jié)結(jié)原原理理簡單單易易行行，便便于于計(jì)計(jì)算算機(jī)機(jī)實(shí)實(shí)現(xiàn)現(xiàn)和和執(zhí)執(zhí)行行，，從從而而使使定定理理的的機(jī)機(jī)器器自自動(dòng)動(dòng)證證明明成成為為現(xiàn)現(xiàn)實(shí)實(shí)，，也也成成為為人工工智智能能技技術(shù)術(shù)實(shí)實(shí)用用化化的的一一次次重重要要突突破破。2022/12/3173歸結(jié)演繹繹推理2）歸結(jié)原原理1、歸結(jié)方方法(1)歸結(jié)式（（消解式式*）設(shè)有兩個(gè)個(gè)子句C1=L∨C1’、C2=L∨C2’①從C1和C2中消去互補(bǔ)補(bǔ)文字L和L；②C1’和C2’通過∨組成新的的子句C=C1’∨C2’；稱C為C1和C2的歸結(jié)式（（消解式式）；例、兩個(gè)個(gè)子句C1=P(A)∨Q(x)∨R(f(x))C2=P(A)∨Q(y)∨∨R(y)消去互補(bǔ)文字字P(A)和P(A)后，生成成歸結(jié)式：C12=Q(x)∨∨R(f(x))∨Q(y)∨R(y)C1’C2’2022/12/3174歸結(jié)演繹繹推理2）歸結(jié)原原理1、歸結(jié)方方法(2)歸結(jié)式性性質(zhì)定理：兩個(gè)子句句C1和C2的歸結(jié)式式C是C1和C2的邏輯推推論任一使子子句C1和C2為真的解解釋I，必使歸歸結(jié)式C為真；歸結(jié)式C為假的解解釋I，子句C1或者C2為假；推論：設(shè)C1和C2是子句集集S中的兩個(gè)個(gè)子句，，并以C作為它們們的歸結(jié)結(jié)式；通過往S中加入C而產(chǎn)生的的擴(kuò)展子子句集S’與子句集集S在不可滿足足的意義上上是等價(jià)價(jià)的！歸結(jié)后擴(kuò)擴(kuò)展子句句集S’子句集S不可滿足足性等價(jià)價(jià)2022/12/3175歸結(jié)演繹繹推理2）歸結(jié)原原理1、歸結(jié)方方法(3)空子句設(shè)C1=L、C2=L，則歸結(jié)結(jié)式C為空；以□表示為空空的歸結(jié)結(jié)式C，并稱C=□為空子句；；因?yàn)镃1和C2是一對(duì)矛矛盾子句句，不可可同時(shí)滿滿足，所所以□是不可滿足足的子句；通過往S中加入□而產(chǎn)生的的擴(kuò)展子子句集S’不可滿足足；空子句□是用歸結(jié)原理理判定子句句集S不可滿足足的成功標(biāo)志志。歸結(jié)后的的擴(kuò)展子子句集S’子句集S不可滿足足性等價(jià)價(jià)2022/12/3176(1)假言推理父輩子句P~P∨Q（即P=>Q）消解式QC1=P,C2=~P∨Q（2）合并C1=P∨Q,C2=~P∨Q父輩子句P∨Q~P∨Q消解式Q∨Q＝Q對(duì)基子句的消消解2022/12/3177(3)重言式父輩子句P∨Q~P∨~Q消解式Q∨~QC1=P∨Q,C2=~P∨~Q父輩子句P∨Q~P∨~Q消解式P∨~P或者2022/12/3178(4)空子句(矛盾)P~PNIL（5）鏈?zhǔn)剑ㄈ味握摚﹡P∨R,(即P=>R)~R∨Q,(即R=>Q)~P∨Q,(即P=>Q)2022/12/3179歸結(jié)演繹推推理2）歸結(jié)原理理動(dòng)機(jī)為提高判定定子句集S不可滿足的的有效性，魯賓遜于于1965年提出了歸結(jié)(Resolution)原理，也稱為消解原理。歸結(jié)原理簡單易行，便于計(jì)算算機(jī)實(shí)現(xiàn)和和執(zhí)行，從從而使定理理的機(jī)器自自動(dòng)證明成成為現(xiàn)實(shí)，，也成為人工智能技技術(shù)實(shí)用化化的一次重重要突破?；舅悸贰锿ㄟ^歸結(jié)方法不斷擴(kuò)充待判定的子句集S，并設(shè)法使使其包含進(jìn)指示矛盾盾的空子句?？兆泳涫遣豢蓾M足足（即永假假）的子句句；2022/12/3180歸結(jié)演繹推推理2）歸結(jié)原理理2、歸結(jié)推理理過程——?dú)w結(jié)演繹樹樹(1)命題邏輯中中的歸結(jié)推推理過程子句中文字只是原子命命題公式或或其取反，，不帶變量；易于判別哪哪些子句對(duì)包含互補(bǔ)文字；例、子句集集S={P∨Q,P∨R,Q,R}的歸結(jié)演繹繹樹。2022/12/3181歸結(jié)演繹推推理2）歸結(jié)原理理2、歸結(jié)推理理過程(1)命題邏輯中中的歸結(jié)推推理過程例、子句集集S={P∨Q,P∨R,Q,R}的歸結(jié)演繹繹樹。擴(kuò)展子句集集S’包含空子句子句集S不可滿足2022/12/3182歸結(jié)演繹推推理2）歸結(jié)原理理-置換和合一一★2、歸結(jié)推理理過程(2)謂詞邏輯中中的歸結(jié)推推理過程子句中含有變量，不能直接發(fā)發(fā)現(xiàn)和消去去互補(bǔ)文字字；需對(duì)潛在的互補(bǔ)文字字先作變量置換和合一處理。。變量置換：：用置換項(xiàng)取代公式中中的變量；置換項(xiàng)可以是變量、常量或函數(shù)。置換元素——t/v（置換項(xiàng)/變量）置換——若干置換元素的集合；合一處理：：P(x,y,x,g(x)),P(A,B,A,z)2022/12/3183P(x,y,x,g(x)),P(A,B,A,z)我們們可可以以為為它它們們建建立立多個(gè)個(gè)置置換換：S1={A/x,B/y,g(x)/z}S2={f(w)/x,z/y,C/z}S3={B/x,f(w)/y,y/z}置換換結(jié)結(jié)果果為為：：{P(x,y,x,g(x)),P(A,B,A,z)}S1={P(A,B,A,g(A)),P(A,B,A,g(A))}{P(x,y,x,g(x)),P(A,B,A,z)}S2={P(f(w)),z,f(w),g(f(w)),P(A,B,A,C)}{P(x,y,x,g(x)),P(A,B,A,z)}S3={P(B,f(w),B,g(B)),P(A,B,A,y)}S1使?jié)撛谠诘幕セパa(bǔ)補(bǔ)文文字字中中的的原原子子謂謂詞詞公公式式變變?yōu)闉橥灰唬_確認(rèn)認(rèn)互互補(bǔ)補(bǔ)性性。。2022/12/3184置換換和和合合一一實(shí)實(shí)例例1將它它們們分分別別作作用用于于表表達(dá)達(dá)式式，，得得：：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]s3=P[q（z），，f（A），，B]P[x，f（y），，B]s4=P[c，f（A），B]表達(dá)式P[x，f（y），B]的4個(gè)置換為s1={z/x，w/y}s2={A/y}

s3={q（z）/x，A/y}s4={c/x，A/y}2022/12/3185置換和合一實(shí)實(shí)例2置換是可結(jié)合合的。用s1s2表示兩個(gè)置換換s1和s2的合成。L表示一表達(dá)式式，則有（（Ls1）s2=L（s1s2）（（s1s2）s3=s1（s2s3）

置換是不不可交換的。。即s1s2s2s12022/12/3186歸結(jié)演繹推理理2）歸結(jié)原理-置換和合一2、歸結(jié)推理過過程(2)謂詞邏輯中的的歸結(jié)推理過過程子句中含有變量，不能直接發(fā)現(xiàn)現(xiàn)和消去互補(bǔ)補(bǔ)文字；需對(duì)潛在的互補(bǔ)文字先先作變量置換和合一處理。變量置換：用置換項(xiàng)取代公式中的的變量；置換項(xiàng)可以是變量、常量或函數(shù)。置換元素——t/v（置換項(xiàng)/變量）置換——若干置換元素的集合；合一處理：通過多個(gè)變量置換，使相應(yīng)于潛在互補(bǔ)文字的原原子謂詞公式式同一化的過程。P(x,y,x,g(x)),P(A,B,A,z)2022/12/3187歸結(jié)演繹推理理2）歸結(jié)原理-置換和合一2、歸結(jié)推理過過程(2)謂詞邏輯中的的歸結(jié)推理過過程通過一個(gè)匹配過程去檢查兩個(gè)原子謂詞詞公式的可合一性，并同時(shí)建立用于實(shí)現(xiàn)合一一的置換?！酒ヅ溥^程】★①兩個(gè)原子謂詞公式式必須具有相同同的謂詞符號(hào)和參數(shù)項(xiàng)個(gè)數(shù)；②從左到右逐逐個(gè)檢查每對(duì)參數(shù)項(xiàng)的的可合一性；③若每對(duì)參數(shù)數(shù)項(xiàng)都可合一一，則合一處處理成功，并并建立用于實(shí)現(xiàn)合一一的置換。2022/12/3188歸結(jié)演演繹推推理2）歸結(jié)結(jié)原理理-置換和和合一一【匹配過過程】②從左到到右逐逐個(gè)檢查每對(duì)參參數(shù)項(xiàng)項(xiàng)的可合一一性；參數(shù)對(duì)對(duì)中有有一個(gè)個(gè)是變變量v（不關(guān)關(guān)心另另一個(gè)個(gè)t是否是是變量量）v初次出出現(xiàn)，參數(shù)數(shù)對(duì)可可合一一，以以另一一參數(shù)數(shù)t為置換換項(xiàng)，，構(gòu)成成置換換元素素t/v;v出現(xiàn)過過，則已已建立立相應(yīng)應(yīng)的置置換元元素，，就取取其置置換項(xiàng)項(xiàng)，代代替該該變量量，檢檢查是是否與與另一一參數(shù)數(shù)同一一；若若不同同一，，則處處理失失敗；；參數(shù)對(duì)對(duì)中沒沒有變變量，，則必必須相相同，，否則則合一一處理理失敗敗。2022/12/3189歸結(jié)演演繹推推理2）歸結(jié)結(jié)原理理-置換和和合一一2、歸結(jié)結(jié)推理理過程程(2)謂詞邏邏輯中中的歸歸結(jié)推推理過過程匹配過過程的的例子子P(x,y,x,g(x)),P(A,B,A,z)①兩個(gè)原子謂謂詞公公式必須具具有相相同的的謂詞和參數(shù)項(xiàng)項(xiàng)個(gè)數(shù)數(shù)；②從左左到右右逐個(gè)個(gè)檢查每對(duì)參參數(shù)項(xiàng)項(xiàng)的可合一一性；x和A，x初次出出現(xiàn)，可合合一，，建立立置換換元素素A/x;y和B，y初次出出現(xiàn)，可合合一，，建立立置換換元素素B/y;x和A，x出現(xiàn)過過，已經(jīng)經(jīng)建立立置換換元素素A/x，可合合一；；g(x)和z，z初次出出現(xiàn)，可合合一，，建立立置換換元素素g(x)/z；③若每每對(duì)參參數(shù)項(xiàng)項(xiàng)都可可合一一，則則合一處處理成成功。建立置置換S1={A/x,B/y,g(x)/z}2022/12/3190歸結(jié)演演繹推推理2）歸結(jié)結(jié)原理理-