第四章 確定性推理

1、2022-4-191o 推理就是按某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過推理就是按某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過程；程；o 已知知識(shí)和事實(shí)（已知判斷）：包括已掌握的與求解已知知識(shí)和事實(shí)（已知判斷）：包括已掌握的與求解問題有關(guān)的知識(shí)及關(guān)于問題的已知事實(shí)；問題有關(guān)的知識(shí)及關(guān)于問題的已知事實(shí)； 推理的結(jié)論：由已知判斷推出新判斷；推理的結(jié)論：由已知判斷推出新判斷；o 推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。2022-4-1921、演繹推理、歸納推理、默認(rèn)推理、演繹推理、歸納推理、默認(rèn)推理推理的基本任務(wù)是從一種判斷推出另一種判斷推理的基本任務(wù)是從一種判斷推出另一種判斷按判斷推

2、出的途徑來劃分，可分為按判斷推出的途徑來劃分，可分為演繹推理、歸納推理演繹推理、歸納推理及默認(rèn)推理及默認(rèn)推理（1）演繹推理）演繹推理演繹推理是從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過程演繹推理是從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過程演繹推理有多種形式，經(jīng)常用的是三段論式演繹推理有多種形式，經(jīng)常用的是三段論式三段論式包括三段論式包括大前提：已知的一般性知識(shí)或假設(shè)大前提：已知的一般性知識(shí)或假設(shè)小前提：關(guān)于所研究的具體情況或個(gè)別事實(shí)的判斷小前提：關(guān)于所研究的具體情況或個(gè)別事實(shí)的判斷結(jié)論：由大前提推出的適合于小前提所示情況的新判斷結(jié)論：由大前提推出的適合于小前提所示情況的新判斷2022-4-193n

3、在任何情況下，由演繹推導(dǎo)出的結(jié)論都是蘊(yùn)涵在大前在任何情況下，由演繹推導(dǎo)出的結(jié)論都是蘊(yùn)涵在大前提的一般性知識(shí)中（提的一般性知識(shí)中（沒有增加新知識(shí)沒有增加新知識(shí)）n 只要大前提和小前提是正確的，則由它們推出的結(jié)論只要大前提和小前提是正確的，則由它們推出的結(jié)論必然是正確的。必然是正確的。(2) 歸納推理歸納推理歸納推理是從足夠多的事例中歸納出一般性結(jié)論的推歸納推理是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種從個(gè)別到一般的推理理過程，是一種從個(gè)別到一般的推理歸納推理：完全歸納推理、不完全歸納推理歸納推理：完全歸納推理、不完全歸納推理完全歸納推理是在進(jìn)行歸納時(shí)考察了相應(yīng)事物的全部完全歸納推理是在

4、進(jìn)行歸納時(shí)考察了相應(yīng)事物的全部對(duì)象，并根據(jù)這些對(duì)象是否都具有某種屬性，從而推對(duì)象，并根據(jù)這些對(duì)象是否都具有某種屬性，從而推出這個(gè)事物是否具有這個(gè)屬性出這個(gè)事物是否具有這個(gè)屬性不完全歸納推理是指只考察了相應(yīng)事物的部分對(duì)象就不完全歸納推理是指只考察了相應(yīng)事物的部分對(duì)象就得出了結(jié)論得出了結(jié)論2022-4-194n 枚舉歸納推理：若已知某類事物的有限可數(shù)個(gè)具體事枚舉歸納推理：若已知某類事物的有限可數(shù)個(gè)具體事物都具有某種屬性，則可推出該類事物都具有此屬性物都具有某種屬性，則可推出該類事物都具有此屬性n 類比推理：在兩個(gè)或兩類事物有許多屬性都相同或相類比推理：在兩個(gè)或兩類事物有許多屬性都相同或相似的基礎(chǔ)上

5、，推出它們?cè)谄渌麑傩陨弦蚕嗤蛳嗨频乃频幕A(chǔ)上，推出它們?cè)谄渌麑傩陨弦蚕嗤蛳嗨频囊环N推理一種推理(3) 默認(rèn)推理默認(rèn)推理又稱缺省推理，它是在知識(shí)不完全的情況下假設(shè)某些又稱缺省推理，它是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理?xiàng)l件已經(jīng)具備所進(jìn)行的推理擺脫了需要知道全部事實(shí)才能進(jìn)行推理的需求，使得擺脫了需要知道全部事實(shí)才能進(jìn)行推理的需求，使得在知識(shí)不完全的情況下也能進(jìn)行推理在知識(shí)不完全的情況下也能進(jìn)行推理2022-4-1952 2、確定性推理、不確定性推理、確定性推理、不確定性推理按推理時(shí)所用知識(shí)的確定性來劃分，推理可分為確定按推理時(shí)所用知識(shí)的確定性來劃分，推理可分為確定性推理、不確

6、定性推理性推理、不確定性推理確定性推理：推理時(shí)所用的知識(shí)都是精確的，推出的確定性推理：推理時(shí)所用的知識(shí)都是精確的，推出的結(jié)論也是確定的，其真值或者為真，或?yàn)榧?，沒有第結(jié)論也是確定的，其真值或者為真，或?yàn)榧?，沒有第三種情況出現(xiàn)三種情況出現(xiàn)不確定性推理：推理時(shí)所用的知識(shí)不都是精確的，推不確定性推理：推理時(shí)所用的知識(shí)不都是精確的，推出的結(jié)論也不完全是肯定的，真值位于真與假之間，出的結(jié)論也不完全是肯定的，真值位于真與假之間，命題的外延模糊不清命題的外延模糊不清2022-4-1963 3、單調(diào)推理、非單調(diào)推理、單調(diào)推理、非單調(diào)推理按推理過程中推出的結(jié)論是否單調(diào)地增加，或推出的按推理過程中推出的結(jié)論是否單

7、調(diào)地增加，或推出的結(jié)論是否越來越接近目標(biāo)，可分為單調(diào)推理和非單調(diào)結(jié)論是否越來越接近目標(biāo)，可分為單調(diào)推理和非單調(diào)推理推理單調(diào)推理：在推理過程中隨著推理的向前推進(jìn)及新知單調(diào)推理：在推理過程中隨著推理的向前推進(jìn)及新知識(shí)的加入，推出的結(jié)論是呈單調(diào)增加的趨勢(shì)，并且越識(shí)的加入，推出的結(jié)論是呈單調(diào)增加的趨勢(shì)，并且越來越接近最終目標(biāo)，在推理過程中不出現(xiàn)反復(fù)的情況來越接近最終目標(biāo)，在推理過程中不出現(xiàn)反復(fù)的情況非單調(diào)推理：在推理過程中由于新知識(shí)的加入，不僅非單調(diào)推理：在推理過程中由于新知識(shí)的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使得推理退沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新

8、開始。該推理一般是在知識(shí)回到前面的某一步，重新開始。該推理一般是在知識(shí)不完全的情況下進(jìn)行的。不完全的情況下進(jìn)行的。2022-4-1972022-4-1974 4、啟發(fā)式推理、非啟發(fā)式推理、啟發(fā)式推理、非啟發(fā)式推理按推理過程中是否運(yùn)用啟發(fā)式知識(shí)分類：按推理過程中是否運(yùn)用啟發(fā)式知識(shí)分類：?jiǎn)l(fā)式推理：在推理過程中運(yùn)用了與問題有關(guān)啟發(fā)式啟發(fā)式推理：在推理過程中運(yùn)用了與問題有關(guān)啟發(fā)式知識(shí)，即解決問題的策略、技巧和經(jīng)驗(yàn)，加快了推理知識(shí)，即解決問題的策略、技巧和經(jīng)驗(yàn)，加快了推理過程，提高了搜索效率。過程，提高了搜索效率。非啟發(fā)式推理：在推理過程中只按照一般的控制邏輯非啟發(fā)式推理：在推理過程中只按照一般的控制

9、邏輯進(jìn)行推理。缺乏對(duì)求解問題的針對(duì)性，推理效率較低，進(jìn)行推理。缺乏對(duì)求解問題的針對(duì)性，推理效率較低，容易出現(xiàn)組合爆炸問題。容易出現(xiàn)組合爆炸問題。2022-4-1982022-4-198推理的控制策略推理的控制策略o 推理過程是一個(gè)思維過程，即推理過程是一個(gè)思維過程，即求解問題的過程求解問題的過程o 推理的控制策略主要包括推理方向、搜索策略、推理的控制策略主要包括推理方向、搜索策略、沖突消解策略、求解策略及限制策略等沖突消解策略、求解策略及限制策略等1 1、推理方向、推理方向n 推理方向用于確定推理的驅(qū)動(dòng)方式，分為正向推理方向用于確定推理的驅(qū)動(dòng)方式，分為正向推理、逆向推理、混合推理及雙向推理四種

10、推理、逆向推理、混合推理及雙向推理四種知識(shí)庫知識(shí)庫綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫推理機(jī)推理機(jī)2022-4-199推理的控制策略推理的控制策略 正向推理正向推理 正向推理是從初始狀態(tài)出發(fā)，使用規(guī)則，正向推理是從初始狀態(tài)出發(fā)，使用規(guī)則，到達(dá)目標(biāo)狀態(tài)。又稱為數(shù)據(jù)驅(qū)動(dòng)推理、前向鏈到達(dá)目標(biāo)狀態(tài)。又稱為數(shù)據(jù)驅(qū)動(dòng)推理、前向鏈推理、模式制導(dǎo)推理及前件推理。推理、模式制導(dǎo)推理及前件推理。 逆向推理逆向推理 逆向推理是以某個(gè)假設(shè)目標(biāo)為出發(fā)點(diǎn)的逆向推理是以某個(gè)假設(shè)目標(biāo)為出發(fā)點(diǎn)的一種推理，又稱為目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理一種推理，又稱為目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理、目標(biāo)制導(dǎo)推理及后件推理。、目標(biāo)制導(dǎo)推理及后件推理。2022-4-19

11、10正、逆向推理比較正、逆向推理比較 項(xiàng)項(xiàng) 目目正向推理正向推理逆向推理逆向推理驅(qū)動(dòng)方式驅(qū)動(dòng)方式數(shù)據(jù)驅(qū)動(dòng)數(shù)據(jù)驅(qū)動(dòng)目標(biāo)驅(qū)動(dòng)目標(biāo)驅(qū)動(dòng)推理方法推理方法從一組數(shù)據(jù)出發(fā)向前推導(dǎo)結(jié)論從一組數(shù)據(jù)出發(fā)向前推導(dǎo)結(jié)論從可能的解出發(fā)向后推理驗(yàn)證解答從可能的解出發(fā)向后推理驗(yàn)證解答啟動(dòng)方法啟動(dòng)方法從一個(gè)事件啟動(dòng)從一個(gè)事件啟動(dòng)由詢問關(guān)于目標(biāo)狀態(tài)的一個(gè)問題啟動(dòng)由詢問關(guān)于目標(biāo)狀態(tài)的一個(gè)問題啟動(dòng)透明程度透明程度不能解釋其推理過程不能解釋其推理過程可解釋其推理過程可解釋其推理過程推理方向推理方向由底向上推理由底向上推理由頂向下推理由頂向下推理典型系統(tǒng)典型系統(tǒng)CLIPSCLIPS，OPSOPSPROLOGPROLOG2022-4-

12、1911推理的控制策略推理的控制策略混合推理混合推理o已知的事實(shí)不充分。通過正向推理先把其運(yùn)用條件不能已知的事實(shí)不充分。通過正向推理先把其運(yùn)用條件不能完全匹配的知識(shí)都找出來，并把這些知識(shí)可導(dǎo)出的結(jié)論完全匹配的知識(shí)都找出來，并把這些知識(shí)可導(dǎo)出的結(jié)論作為假設(shè)，然后分別對(duì)這些假設(shè)進(jìn)行逆向推理。作為假設(shè)，然后分別對(duì)這些假設(shè)進(jìn)行逆向推理。o由正向推理推出的結(jié)論可信度不高。由正向推理推出的結(jié)論可信度不高。o希望得到更多的結(jié)論。希望得到更多的結(jié)論。o推理的形式：推理的形式：n先正向再逆向先正向再逆向，通過正向推理，即從已知事實(shí)演繹出，通過正向推理，即從已知事實(shí)演繹出部分結(jié)果，然后再用逆向推理證實(shí)該目標(biāo)或提高

13、部分結(jié)果，然后再用逆向推理證實(shí)該目標(biāo)或提高 其其可信度可信度n先逆向再正向先逆向再正向，先假設(shè)一個(gè)目標(biāo)進(jìn)行逆向推理，然后，先假設(shè)一個(gè)目標(biāo)進(jìn)行逆向推理，然后再利用逆向推理中得到的信息進(jìn)行正向推理，以推出再利用逆向推理中得到的信息進(jìn)行正向推理，以推出更多的結(jié)論更多的結(jié)論2022-4-1912推理的控制策略推理的控制策略 雙向推理雙向推理雙向推理是指正向推理與逆向推理同時(shí)進(jìn)行，且在雙向推理是指正向推理與逆向推理同時(shí)進(jìn)行，且在推理過程中的某一步驟上推理過程中的某一步驟上“碰頭碰頭”的一種推理。的一種推理。正向推理所得的中間結(jié)論恰好是逆向推理此時(shí)要求正向推理所得的中間結(jié)論恰好是逆向推理此時(shí)要求的證據(jù)的證

14、據(jù)2 2、求解策略、求解策略 推理是只求一個(gè)解還是求所有解以及最優(yōu)解等推理是只求一個(gè)解還是求所有解以及最優(yōu)解等3 3、限制策略、限制策略 對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn)行限制對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn)行限制2022-4-19134 4、沖突消解策略 o 在推理過程中，匹配會(huì)出現(xiàn)三種情況在推理過程中，匹配會(huì)出現(xiàn)三種情況已知事實(shí)不能與知識(shí)庫中的任何知識(shí)匹配成功已知事實(shí)不能與知識(shí)庫中的任何知識(shí)匹配成功已知事實(shí)恰好只與知識(shí)庫中的一個(gè)知識(shí)匹配成功已知事實(shí)恰好只與知識(shí)庫中的一個(gè)知識(shí)匹配成功已知事實(shí)可與知識(shí)庫中的多個(gè)知識(shí)匹配成功；或者有已知事實(shí)可與知識(shí)庫中的多個(gè)知識(shí)匹配成功；或者有多個(gè)（組）已知

15、事實(shí)都可與知識(shí)庫中某一知識(shí)匹配成多個(gè)（組）已知事實(shí)都可與知識(shí)庫中某一知識(shí)匹配成功；或者有多個(gè)（組）已知事實(shí)可與知識(shí)庫中的多個(gè)功；或者有多個(gè)（組）已知事實(shí)可與知識(shí)庫中的多個(gè)知識(shí)匹配成功知識(shí)匹配成功出現(xiàn)沖突的情況出現(xiàn)沖突的情況對(duì)正向推理而言，如果有多條產(chǎn)生式規(guī)則的前件都和對(duì)正向推理而言，如果有多條產(chǎn)生式規(guī)則的前件都和已知的事實(shí)匹配成功；或者有多組不同的已知事實(shí)都已知的事實(shí)匹配成功；或者有多組不同的已知事實(shí)都與同一條產(chǎn)生式規(guī)則的前件匹配成功；或者兩種情況與同一條產(chǎn)生式規(guī)則的前件匹配成功；或者兩種情況同時(shí)出現(xiàn)同時(shí)出現(xiàn)推理的控制策略推理的控制策略2022-4-1914推理的控制策略推理的控制策略對(duì)逆向推

16、理而言，如果有多條產(chǎn)生式的后件都和同一對(duì)逆向推理而言，如果有多條產(chǎn)生式的后件都和同一假設(shè)匹配成功，或者有多條產(chǎn)生式后件可與多個(gè)假設(shè)假設(shè)匹配成功，或者有多條產(chǎn)生式后件可與多個(gè)假設(shè)匹配成功。匹配成功。按就近原則排序按就近原則排序l該策略把最近被使用過的規(guī)則賦予較高的優(yōu)先級(jí)。該策略把最近被使用過的規(guī)則賦予較高的優(yōu)先級(jí)。 按已知事實(shí)的新鮮性排序按已知事實(shí)的新鮮性排序 l一般我們認(rèn)為新鮮事實(shí)是對(duì)舊知識(shí)的更新和改進(jìn)，比一般我們認(rèn)為新鮮事實(shí)是對(duì)舊知識(shí)的更新和改進(jìn)，比老知識(shí)更有效，即后生成的事實(shí)比先生成的事實(shí)具有老知識(shí)更有效，即后生成的事實(shí)比先生成的事實(shí)具有較大的優(yōu)先性。較大的優(yōu)先性。 2022-4-1915

17、推理的控制策略推理的控制策略按匹配度排序按匹配度排序 l在不確定推理時(shí)，匹配度不僅可確定兩個(gè)知識(shí)模式是在不確定推理時(shí)，匹配度不僅可確定兩個(gè)知識(shí)模式是否可匹配，還可用于沖突消解。根據(jù)匹配程度來決定否可匹配，還可用于沖突消解。根據(jù)匹配程度來決定哪一個(gè)產(chǎn)生式規(guī)則優(yōu)先被應(yīng)用。哪一個(gè)產(chǎn)生式規(guī)則優(yōu)先被應(yīng)用。按領(lǐng)域問題特點(diǎn)排序按領(lǐng)域問題特點(diǎn)排序 l該方法按照求解問題領(lǐng)域的特點(diǎn)將知識(shí)排成固定的次該方法按照求解問題領(lǐng)域的特點(diǎn)將知識(shí)排成固定的次序。序。 按上下文限制排序按上下文限制排序l該策略將知識(shí)按照所描述的上下文分成若干組，在推該策略將知識(shí)按照所描述的上下文分成若干組，在推理過程中根據(jù)當(dāng)前數(shù)據(jù)庫中的已知事實(shí)與

18、上下文的匹理過程中根據(jù)當(dāng)前數(shù)據(jù)庫中的已知事實(shí)與上下文的匹配情況，確定選擇某組中的某條知識(shí)。配情況，確定選擇某組中的某條知識(shí)。 2022-4-1916推理的控制策略推理的控制策略按條件個(gè)數(shù)排序按條件個(gè)數(shù)排序l多條規(guī)則生成的結(jié)論相同的情況下，由于條件個(gè)多條規(guī)則生成的結(jié)論相同的情況下，由于條件個(gè)數(shù)較少的規(guī)則匹配所花費(fèi)的時(shí)間較少而且容易實(shí)數(shù)較少的規(guī)則匹配所花費(fèi)的時(shí)間較少而且容易實(shí)現(xiàn)，所以將條件少的規(guī)則賦予較高的優(yōu)先級(jí)，優(yōu)現(xiàn)，所以將條件少的規(guī)則賦予較高的優(yōu)先級(jí)，優(yōu)先被啟用。先被啟用。 按規(guī)則的次序排序按規(guī)則的次序排序 l該策略是以知識(shí)庫中預(yù)先存入規(guī)則的排列順序作該策略是以知識(shí)庫中預(yù)先存入規(guī)則的排列順序作

19、為知識(shí)排序的依據(jù)，排在前面的規(guī)則具有較高的為知識(shí)排序的依據(jù)，排在前面的規(guī)則具有較高的優(yōu)先級(jí)。優(yōu)先級(jí)。 2022-4-1917o 定義：定義：自然演繹推理是指從一組已知的事實(shí)出發(fā)，直接運(yùn)用自然演繹推理是指從一組已知的事實(shí)出發(fā)，直接運(yùn)用命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過程命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過程。 o 推理規(guī)則：推理規(guī)則：n P規(guī)則：在推理的任何步驟上都可引入前提規(guī)則：在推理的任何步驟上都可引入前提n T規(guī)則：推理時(shí)，如果前面步驟中有一個(gè)或多個(gè)公式永規(guī)則：推理時(shí)，如果前面步驟中有一個(gè)或多個(gè)公式永真蘊(yùn)涵公式真蘊(yùn)涵公式S，則可把，則可把S引入推理過程中。引入推理過程中。n

20、CP規(guī)則：如果能從規(guī)則：如果能從R和前提集合中推出和前提集合中推出S來，則可從前來，則可從前提集合推出提集合推出 來。來。n 反證法：反證法： ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng) 。即：。即：Q為為P的邏輯結(jié)論，當(dāng)且僅當(dāng)?shù)倪壿嫿Y(jié)論，當(dāng)且僅當(dāng) 是不可滿足的。是不可滿足的。SR QP FQPQP2022-4-1918o 假言推理假言推理 表示：由表示：由 及及P為真，可推出為真，可推出Q為真為真 o 拒取式推理拒取式推理 表示：由表示：由 為真及為真及Q為假，可推出為假，可推出P為假為假 QQPP,QP PQQP,QP 2022-4-1919n 肯定后件肯定后件(Q)(Q)的錯(cuò)誤：當(dāng)?shù)腻e(cuò)誤：當(dāng)PQPQ為真時(shí)為真

21、時(shí), ,希望通過肯希望通過肯定后件定后件Q Q推出前件推出前件P P為真為真, ,這是不允許的這是不允許的. .n 否定前件否定前件(P)(P)的錯(cuò)誤：當(dāng)?shù)腻e(cuò)誤：當(dāng)PQPQ為真時(shí)為真時(shí), ,希望通過否希望通過否定前件定前件P P推出后件推出后件Q Q為假為假, ,這也是不允許的這也是不允許的. .n避免產(chǎn)生兩類錯(cuò)誤：避免產(chǎn)生兩類錯(cuò)誤：2022-4-1920n 如果行星系統(tǒng)是以太陽為中心的如果行星系統(tǒng)是以太陽為中心的, ,則金星會(huì)顯示則金星會(huì)顯示出位相變化。出位相變化。 n 金星會(huì)顯示出位相變化。金星會(huì)顯示出位相變化。n 所以，行星系統(tǒng)是以太陽為中心的。所以，行星系統(tǒng)是以太陽為中心的。n如伽利略

22、在論證哥白尼的日心說時(shí)如伽利略在論證哥白尼的日心說時(shí), ,曾使用曾使用了下列推理：了下列推理：這就是使用了肯定后件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則,他為此曾遭到非難。2022-4-1921n 如果上網(wǎng)，則能知道新聞。如果上網(wǎng)，則能知道新聞。 n 沒有上網(wǎng)。沒有上網(wǎng)。 n 所以，不知道新聞。所以，不知道新聞。n又如下列推理：又如下列推理：這就是使用了否定前件的推理,違反了邏輯規(guī)則,顯然是不正確的,因?yàn)橥ㄟ^收聽廣播、看電視等，也會(huì)知道新聞。2022-4-1922o 例： 設(shè)已知事實(shí) （1）只要不怕困難的人，就會(huì)獲得勝利。 （2）運(yùn)動(dòng)員都是不怕困難的人。 （3）王力是運(yùn)動(dòng)員。 求證：王力會(huì)獲得勝利。

23、 2022-4-1923o 自然演繹推理的優(yōu)缺點(diǎn)自然演繹推理的優(yōu)缺點(diǎn)n 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 定理證明過程自然，容易理解，而且它擁有豐富的定理證明過程自然，容易理解，而且它擁有豐富的推理規(guī)則，推理過程靈活，便于在它的推理規(guī)則推理規(guī)則，推理過程靈活，便于在它的推理規(guī)則中嵌入領(lǐng)域啟發(fā)式知識(shí)。中嵌入領(lǐng)域啟發(fā)式知識(shí)。n 缺點(diǎn)：缺點(diǎn)： 容易產(chǎn)生組合爆炸，推理過程中得到的中間結(jié)論一容易產(chǎn)生組合爆炸，推理過程中得到的中間結(jié)論一般呈指數(shù)形式遞增。般呈指數(shù)形式遞增。2022-4-1924 人的問題求解行為更像是一個(gè)人的問題求解行為更像是一個(gè)解答識(shí)別解答識(shí)別過程而非過程而非解答搜索解答搜索過程過程 識(shí)別解答或部分解答依賴

24、于應(yīng)用領(lǐng)域特有的知識(shí)，識(shí)別解答或部分解答依賴于應(yīng)用領(lǐng)域特有的知識(shí)， 符號(hào)推理則成為基于知識(shí)來求解問題的主要手段。符號(hào)推理則成為基于知識(shí)來求解問題的主要手段。 符號(hào)推理的重要方式是演繹推理符號(hào)推理的重要方式是演繹推理 它的基礎(chǔ)為謂詞演算它的基礎(chǔ)為謂詞演算一種一種形式語言形式語言 將各種陳述性（說明性）的描述以將各種陳述性（說明性）的描述以形式化形式化的方式表示，以的方式表示，以便對(duì)它們便對(duì)它們 作處理。作處理。 謂詞演算謂詞演算人工智能系統(tǒng)最常用的知識(shí)表示方法，人工智能系統(tǒng)最常用的知識(shí)表示方法， 廣泛地應(yīng)用于各種人工智能系統(tǒng)的設(shè)計(jì)。廣泛地應(yīng)用于各種人工智能系統(tǒng)的設(shè)計(jì)。 謂詞演算（或更廣義地，形式

25、邏輯）是人工智能研究的重要基礎(chǔ)謂詞演算（或更廣義地，形式邏輯）是人工智能研究的重要基礎(chǔ)之一。之一。 主要內(nèi)容：主要內(nèi)容： 謂詞演算謂詞演算 H H域和海伯倫定理域和海伯倫定理 歸結(jié)演繹歸結(jié)演繹 歸結(jié)反演歸結(jié)反演 歸結(jié)演繹推理歸結(jié)演繹推理 2022-4-1925o 1、謂詞公式、謂詞公式n “謂詞公式謂詞公式”的一般形式：的一般形式：o P(x1,x2,xn)，其中，其中，o P謂詞符號(hào)謂詞符號(hào)（簡(jiǎn)稱謂詞）；（簡(jiǎn)稱謂詞）；o Xi(i=1,2,n)參數(shù)項(xiàng)參數(shù)項(xiàng)（簡(jiǎn)稱項(xiàng)），項(xiàng)可以（簡(jiǎn)稱項(xiàng)），項(xiàng)可以是常量是常量、變量變量或或函數(shù)函數(shù)；o P(x1,x2,xn)n元謂詞公式；元謂詞公式；n “謂詞公式

26、謂詞公式”的基本組成：的基本組成：o 謂詞符號(hào)謂詞符號(hào)、常量符號(hào)常量符號(hào)、變量符號(hào)變量符號(hào)、函數(shù)符號(hào)函數(shù)符號(hào)；o 用用括號(hào)括號(hào)和和逗號(hào)逗號(hào)隔開，隔開，表示論域內(nèi)的關(guān)系表示論域內(nèi)的關(guān)系。n “謂詞公式謂詞公式是謂詞邏輯的基本單元，也稱為是謂詞邏輯的基本單元，也稱為原子公式原子公式。2022-4-1926o2、連詞和量詞、連詞和量詞n通過引入通過引入連詞連詞和和量詞量詞，可以把，可以把謂詞公式（原子公式）謂詞公式（原子公式）組合為組合為復(fù)合謂詞復(fù)合謂詞公式公式。n復(fù)合謂詞公式復(fù)合謂詞公式也稱為也稱為邏輯語句邏輯語句。o（1）連詞）連詞（非）加在（非）加在謂詞公式謂詞公式前面，稱為否定，或取反。前面

27、，稱為否定，或取反。（與）連接（與）連接謂詞公式謂詞公式，稱為，稱為合取合取；產(chǎn)生的產(chǎn)生的邏輯語句邏輯語句稱為稱為合取式合取式，每個(gè)成分成為，每個(gè)成分成為合取項(xiàng)。合取項(xiàng)。（或）連接（或）連接謂詞公式謂詞公式，稱為，稱為析取析?。划a(chǎn)生的產(chǎn)生的邏輯語句邏輯語句稱為稱為析取式析取式，每個(gè)成分成為，每個(gè)成分成為析取項(xiàng)。析取項(xiàng)。（蘊(yùn)涵）連接（蘊(yùn)涵）連接謂詞公式謂詞公式產(chǎn)生產(chǎn)生蘊(yùn)涵式蘊(yùn)涵式；左部稱為左部稱為前項(xiàng)前項(xiàng)，右部稱為，右部稱為后項(xiàng)后項(xiàng)。（等價(jià)）連接（等價(jià)）連接謂詞公式謂詞公式產(chǎn)生產(chǎn)生等價(jià)式等價(jià)式；正、逆向蘊(yùn)涵式的合取。；正、逆向蘊(yùn)涵式的合取。2022-4-19o 2、連詞和量詞、連詞和量詞n通過引

28、入連詞和量詞，可以把通過引入連詞和量詞，可以把原子公式原子公式組合為組合為復(fù)合謂詞公式復(fù)合謂詞公式。n復(fù)合謂詞公式也稱為復(fù)合謂詞公式也稱為邏輯語句邏輯語句。o （1）連詞）連詞n通過連詞產(chǎn)生的復(fù)合謂詞公式（邏輯語句）的通過連詞產(chǎn)生的復(fù)合謂詞公式（邏輯語句）的真值表真值表：PQ PPQPQP QP QTTFTTTTFTTFTTFTFFFTFFFFTFFTT2022-4-1928o 2、連詞和量詞、連詞和量詞n 命題命題不包含不包含變量變量的的謂詞公式謂詞公式和和邏輯語句邏輯語句；n 命題邏輯命題邏輯基于基于命題命題的的謂詞邏輯謂詞邏輯稱為稱為命題邏輯命題邏輯，命題邏輯是謂詞邏輯的子集命題邏輯是謂

29、詞邏輯的子集。n 命題邏輯命題邏輯缺乏有效的表達(dá)缺乏有效的表達(dá)一般性概念一般性概念的能力的能力o 無法把每個(gè)知識(shí)單元抽象、細(xì)分；無法把每個(gè)知識(shí)單元抽象、細(xì)分；o 如，如，“條條大路通羅馬條條大路通羅馬”。o Lead(Road1,Roma)o Lead(Road2,Roma)n謂詞邏輯謂詞邏輯中引入中引入變量變量和對(duì)變量進(jìn)行約束的和對(duì)變量進(jìn)行約束的量詞量詞。o （2）量詞）量詞n全稱量詞全稱量詞存在量詞存在量詞 2022-4-1929o 2、連詞和量詞、連詞和量詞（2）量詞）量詞n全稱量詞全稱量詞o 符號(hào)符號(hào)( x)P(x)：表示對(duì)于某個(gè)論域中的：表示對(duì)于某個(gè)論域中的所有（任意一所有（任意一個(gè)

30、）個(gè)）個(gè)體個(gè)體x, 都有都有P(x)真值為真值為T。n存在量詞存在量詞 o 符號(hào)符號(hào)( x)P(x)：來表示某個(gè)論域中：來表示某個(gè)論域中至少存在一個(gè)至少存在一個(gè)個(gè)體個(gè)體x，使，使P(x) 真值為真值為T),()()(RomaxLeadxRoadx條條大路通羅馬條條大路通羅馬),()()()(yxMaryGiveyBookxPersonyxMary給每個(gè)人一本書給每個(gè)人一本書),()()(yxMaryGivexPersonxMary給每人某個(gè)同樣的東西給每人某個(gè)同樣的東西量詞可以嵌套使用量詞可以嵌套使用可以有不受量詞約束的變量可以有不受量詞約束的變量2022-4-1930o 2、連詞和量詞、連詞

31、和量詞（2）量詞）量詞n全稱量詞全稱量詞o 符號(hào)符號(hào)( x)P(x)：表示對(duì)于某個(gè)論域中的：表示對(duì)于某個(gè)論域中的所有（任意一所有（任意一個(gè)）個(gè)）個(gè)體個(gè)體x, 都有都有P(x)真值為真值為T。n存在量詞存在量詞 o 符號(hào)符號(hào)( x)P(x)：來表示某個(gè)論域中：來表示某個(gè)論域中至少存在一個(gè)至少存在一個(gè)個(gè)體個(gè)體x，使，使P(x) 真值為真值為T),()()(RomaxLeadxRoadx條條大路通羅馬條條大路通羅馬),()()(GrayxColorxRobotx所有機(jī)器人都是灰色的所有機(jī)器人都是灰色的2022-4-1931o 一階謂詞邏輯一階謂詞邏輯n 定義：定義：若限定若限定不允許不允許對(duì)對(duì)謂詞謂

32、詞和和函數(shù)名函數(shù)名進(jìn)行進(jìn)行量化量化處理，且處理，且參數(shù)項(xiàng)參數(shù)項(xiàng)不能是不能是謂詞公式謂詞公式，則這樣的謂，則這樣的謂詞邏輯是詞邏輯是一階一階的。的。o 謂詞、函數(shù)名謂詞、函數(shù)名的出現(xiàn)位置的出現(xiàn)位置不允許使用變量不允許使用變量；o 參數(shù)項(xiàng)參數(shù)項(xiàng)不能是不能是謂詞公式謂詞公式；n ( P)P(A)-謂詞進(jìn)行了量化；謂詞進(jìn)行了量化；n ( y)Married(y(L1),Mary )-函數(shù)名進(jìn)行了量化；函數(shù)名進(jìn)行了量化；n P(x,Q(y)-參數(shù)項(xiàng)是謂詞公式；參數(shù)項(xiàng)是謂詞公式；2022-4-1932o 1、合式公式的定義、合式公式的定義n合式公式合式公式適合于適合于一階謂詞邏輯一階謂詞邏輯n遵從以下遞歸

33、方式定義的遵從以下遞歸方式定義的邏輯語句邏輯語句稱為稱為合式公式合式公式n單一謂詞公式是合式公式；單一謂詞公式是合式公式；n若若A A是合式公式，則是合式公式，則 A A也是合式公式；也是合式公式；n若若A A和和B B都是合式公式，則都是合式公式，則A AB B、 A AB B、 A AB B和和A AB B也都是合式公式；也都是合式公式；n若若A A是合式公式，是合式公式，x x是約束變量，則是約束變量，則( ( x x)A)A和和( ( x x)A)A也也都是合式公式；都是合式公式；n只有按上述規(guī)則只有按上述規(guī)則- -求得的公式，才是合式公式。求得的公式，才是合式公式。n連詞優(yōu)先級(jí)別連詞

34、優(yōu)先級(jí)別是是 ，、，、，但可通過，但可通過括號(hào)括號(hào)改改變優(yōu)先級(jí)。變優(yōu)先級(jí)。 一、合式公式一、合式公式2022-4-1933一、合式公式一、合式公式o 1、合式公式的定義、合式公式的定義n例例2 2、“所有人所有人(Person)(Person)都喜歡都喜歡(Like)(Like)一種游戲一種游戲(Game)”(Game)”o 謂詞公式謂詞公式n Person(x)Person(x)n Like(x,y)Like(x,y)n Game(y)Game(y)o 量詞量詞n ( ( x x)Person(x)Person(x)表示表示所有所有人；人；n ( ( y)y)Game(y)Game(y)表示

35、表示一種一種游戲；游戲；o 合式公式合式公式n ( ( x x)()( y)Person(x)y)Person(x)Game(y)Game(y)Like(x,y)Like(x,y) 2022-4-1934一、合式公式一、合式公式o2、合式公式的解釋、合式公式的解釋n命題邏輯命題邏輯不存在變量不存在變量o給命題中包含的給命題中包含的各個(gè)原子公式指派真值各個(gè)原子公式指派真值（T或或F），稱這種指派為），稱這種指派為命題命題的一個(gè)的一個(gè)解釋解釋；o解釋確定后，可依據(jù)連接原子公式的解釋確定后，可依據(jù)連接原子公式的連詞連詞的作用求出命題的真值的作用求出命題的真值（T或或F）。）。n謂詞邏輯謂詞邏輯涉及變

36、量涉及變量o不可能直接給原子公式指派真值不可能直接給原子公式指派真值；o定義一個(gè)擬觀察個(gè)體的可能定義一個(gè)擬觀察個(gè)體的可能論域論域；o確定原子公式中確定原子公式中變量項(xiàng)變量項(xiàng)和和函數(shù)項(xiàng)函數(shù)項(xiàng)在論域中的在論域中的取值取值；o給原子公式給原子公式指派真值指派真值。o解釋確定后，可依據(jù)連接原子公式的解釋確定后，可依據(jù)連接原子公式的連詞連詞的作用求出合式公式的的作用求出合式公式的真值（真值（T或或F）。）。2022-4-1935一、合式公式一、合式公式o 2、合式公式的解釋、合式公式的解釋n例例3 3、合式公式、合式公式( ( x x)()( y)P(x)y)P(x)Q(f(x),y)Q(f(x),y)

37、一個(gè)解釋的一個(gè)解釋的建立。建立。n設(shè)定論域設(shè)定論域D=1,2; D=1,2; x xD,yD,yD Dn對(duì)于對(duì)于x x的每個(gè)取值的每個(gè)取值o 函數(shù)函數(shù)f(x)f(x)：f(1)=2,f(2)=2;f(1)=2,f(2)=2;n對(duì)于對(duì)于x x的每個(gè)取值的每個(gè)取值o 原子公式原子公式P(x)P(x)：P(1)=T,P(2)=TP(1)=T,P(2)=T；n對(duì)于對(duì)于f(x)f(x)和和y y的每個(gè)取值組合的每個(gè)取值組合( (只有只有2 2個(gè)：個(gè)：2 2、1 1；2 2、2)2)o 原子公式原子公式Q(f(x),y)Q(f(x),y)：Q(2,1)=TQ(2,1)=T, Q(2,2)=F, Q(2,2

38、)=F；n上述上述指派指派就確定了該合式公式的就確定了該合式公式的一個(gè)解釋一個(gè)解釋；n在在這個(gè)解釋這個(gè)解釋下，合式公式有下，合式公式有真值真值T T；2022-4-1936一、合式公式一、合式公式o 3、合式公式的永真性和可滿足性、合式公式的永真性和可滿足性n(1)(1)合式公式的永真性合式公式的永真性o 若若P P在某個(gè)論域在某個(gè)論域D D上的上的所有所有可能的解釋都有真值可能的解釋都有真值T T，則稱，則稱P P在在D D上是上是永真的永真的；o 若若P P在在每個(gè)每個(gè)可能的非空論域可能的非空論域D D上均永真，則稱上均永真，則稱P P是是永真的永真的。n(2)(2)合式公式的可滿足性合式

39、公式的可滿足性o 若若P P在某個(gè)論域在某個(gè)論域D D上的上的至少至少可以建立一個(gè)解釋，使可以建立一個(gè)解釋，使P P有真值有真值T T，則稱則稱P P在在D D上是上是可滿足的可滿足的；o 若若至少至少有一個(gè)非空論域有一個(gè)非空論域D D使使P P可滿足，則稱可滿足，則稱P P是是可滿足的可滿足的。n(3)(3)合式公式的永假性合式公式的永假性o 若若P P在某個(gè)論域在某個(gè)論域D D上的上的所有所有可能的解釋都有真值可能的解釋都有真值F F，則稱，則稱P P在在D D上是上是永假的永假的；o 若若P P在在每個(gè)每個(gè)可能的非空論域可能的非空論域D D上均永假，則稱上均永假，則稱P P是是永假的永假

40、的。2022-4-1937一、合式公式一、合式公式o 4、合式公式的性質(zhì)、合式公式的性質(zhì)n合式公式合式公式優(yōu)點(diǎn)優(yōu)點(diǎn)：o 具有強(qiáng)大的形式化表示功能；具有強(qiáng)大的形式化表示功能；n合式公式合式公式缺點(diǎn)缺點(diǎn)：o 包括了多種連詞和量詞以及它們的嵌套應(yīng)用，包括了多種連詞和量詞以及它們的嵌套應(yīng)用，表示形式過表示形式過于復(fù)雜于復(fù)雜；o 不利于演繹推理系統(tǒng)的設(shè)計(jì)和高效運(yùn)作不利于演繹推理系統(tǒng)的設(shè)計(jì)和高效運(yùn)作。n化簡(jiǎn)合式公式化簡(jiǎn)合式公式到某些約定的標(biāo)準(zhǔn)形式是很有意義。到某些約定的標(biāo)準(zhǔn)形式是很有意義。o 合取范式合取范式o 析取范式析取范式n合式公式的性質(zhì)合式公式的性質(zhì)則為化簡(jiǎn)工作提供了依據(jù)。則為化簡(jiǎn)工作提供了依據(jù)。

41、2022-4-1938一、合式公式一、合式公式o4、合式公式的性質(zhì)、合式公式的性質(zhì)n十種常用性質(zhì)十種常用性質(zhì)n(1)雙重否定：雙重否定：o ( P) Pn(2)蘊(yùn)涵式轉(zhuǎn)化：蘊(yùn)涵式轉(zhuǎn)化：oP Q P Qn(3)狄狄.摩根定律：摩根定律：o (P Q) P Qo (P Q) P Qn(4)分配律分配律oP (Q R) (P Q) (P R) oP (Q R) (P Q) (P R)n(5)交換律交換律oP Q Q PoP Q Q Pn(6)結(jié)合律結(jié)合律o(P Q) R P (Q R)o(P Q) R P (Q R)2022-4-1939一、合式公式一、合式公式o4、合式公式的性質(zhì)、合式公式的性質(zhì)n

42、十種常用性質(zhì)十種常用性質(zhì)n(7)逆否律逆否律o P Q Q Pn(8)量詞否定量詞否定o ( x) P(x) ( x) ( P(x) o ( x) P(x) ( x) ( P(x) n(9)量詞分配量詞分配o ( x) P(x) Q(x) ( x)P(x) ( x) Q(x)o ( x) P(x) Q(x) ( x)P(x) ( x) Q(x) n(10)約束變量的虛元化約束變量的虛元化o 約束變量名的變換不影響合式公式的真值約束變量名的變換不影響合式公式的真值o ( x) P(x) ( y) P(y) o ( x) P(x) ( y) P(y) 2022-4-1940一、合式公式一、合式公式

43、o4、合式公式的性質(zhì)、合式公式的性質(zhì)n(9)量詞分配量詞分配o ( x) P(x) Q(x) ( x)P(x) ( y) Q(y)o ( x) P(x) Q(x) ( x)P(x) ( y) Q(y) n(10)約束變量的虛元化約束變量的虛元化o 約束變量名的變換不影響合式公式的真值約束變量名的變換不影響合式公式的真值o ( x) P(x) ( y) P(y) o ( x) P(x) ( y) P(y) 2022-4-1941 二、合式公式的標(biāo)準(zhǔn)化二、合式公式的標(biāo)準(zhǔn)化o 1、標(biāo)準(zhǔn)化需求、標(biāo)準(zhǔn)化需求n常見的基于謂詞演算的推理：常見的基于謂詞演算的推理：歸結(jié)反演歸結(jié)反演、(正向正向/逆向逆向)演繹

44、推理演繹推理o要求以要求以量詞前束范式量詞前束范式來表示合式公式來表示合式公式n量詞前束范式量詞前束范式形式如下：形式如下：o(Q1x1) (Q2x2)(Qkxk)M，其中，其中oM 母式，不包括任何量詞；母式，不包括任何量詞；oQixiQi可以是可以是量詞量詞符號(hào)符號(hào) 或或 ；xi是量詞的是量詞的約束變量約束變量(i=1,2,k)n歸結(jié)反演歸結(jié)反演要求要求M標(biāo)準(zhǔn)化為標(biāo)準(zhǔn)化為合取范式合取范式，定義如下：，定義如下：o M=W1W2 Wno Wi=Li1Li2 Lim(i=1,2,n)o Lij=Pij| Pij:文字（文字（Literal），是，是謂詞公式謂詞公式Pij或或其取反其取反2022

45、-4-1942 二、合式公式的標(biāo)準(zhǔn)化二、合式公式的標(biāo)準(zhǔn)化o 1、標(biāo)準(zhǔn)化需求、標(biāo)準(zhǔn)化需求n常見的基于謂詞演算的推理：常見的基于謂詞演算的推理：歸結(jié)反演歸結(jié)反演、規(guī)則演繹規(guī)則演繹o要求以要求以量詞前束范式量詞前束范式來表示合式公式來表示合式公式n量詞前束范式量詞前束范式形式如下：形式如下：o(Q1x1) (Q2x2)(Qkxk)Mn歸結(jié)反演歸結(jié)反演要求要求M標(biāo)準(zhǔn)化為標(biāo)準(zhǔn)化為合取范式合取范式，定義如下：，定義如下：o M=W1W2 Wno Wi=Li1Li2 Lim(i=1,2,n)o Lij=Pij| Pij:文字（文字（Literal），是原子謂詞公式，是原子謂詞公式Pij或其取反或其取反n析取

46、范式析取范式定義：定義：o M=W1W2Wno Wi=Li1Li2Lim(i=1,2,n)o Lij=Pij| Pij:文字（文字（Literal），是原子謂詞公式，是原子謂詞公式Pij或其取反或其取反2022-4-1943o 定義定義 設(shè)設(shè)F F為一謂詞公式，如果其中的所有量詞均非否為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，而它們的轄域?yàn)檎麄€(gè)公式，定地出現(xiàn)在公式的最前面，而它們的轄域?yàn)檎麄€(gè)公式，則稱則稱F F為為前束范式前束范式(prenex normal form)(prenex normal form)。一般地，一般地，前束范式可以寫成前束范式可以寫成: :其 中其

47、中 為為 前 綴前 綴 ， 是一個(gè)由全稱量詞或存在量詞組成的是一個(gè)由全稱量詞或存在量詞組成的量詞串量詞串， 為為母式母式，它是一個(gè)不含任何量詞的謂詞公，它是一個(gè)不含任何量詞的謂詞公式。式。111()()(,.,)nnnQ xQ xM xx(1,2,., )iQ in1 1()()nnQ xQ x1( ,.,)nM xx前束標(biāo)準(zhǔn)型前束標(biāo)準(zhǔn)型n在一階邏輯中，為了簡(jiǎn)化定理證明程序需要引入所在一階邏輯中，為了簡(jiǎn)化定理證明程序需要引入所謂的謂的“前束標(biāo)準(zhǔn)型前束標(biāo)準(zhǔn)型”。2022-4-1944 下面是一些前束范式的例子：下面是一些前束范式的例子： 為了把一個(gè)公式化為前束范式，首先看一下包含為了把一個(gè)公式化

48、為前束范式，首先看一下包含一階邏輯特有的等價(jià)式對(duì)，如下所示。一階邏輯特有的等價(jià)式對(duì)，如下所示。 ()()( ( , )( )()()( , )( )()()()( ( , )( )xyP x yQ yxyP x yQ yxyzP x yQ z前束標(biāo)準(zhǔn)型前束標(biāo)準(zhǔn)型2022-4-1945(1) ()( )()( )Qx F xGQxF xG(2) ()( )()( )Qx F xGQxF xG1212(3)() ( )()( )()()( ( )( )Qx F xQ x H xQx Q z F xH z1212(4) () ( )()( )()()( ( )( )Q x F xQ x H xQ x

49、 Q z F xH z 在上述等價(jià)公式對(duì)中在上述等價(jià)公式對(duì)中，F(xiàn)(x)和和 H(x)都表示含未都表示含未量化變量量化變量x的公式的公式，G表示不含未量化變量表示不含未量化變量x的公的公式，式，Q1,Q2 或?yàn)榛驗(yàn)?或?yàn)榛驗(yàn)?。 對(duì)對(duì)(3)和和(4)，要求要求z不出現(xiàn)在不出現(xiàn)在F(x) 中，并且符合約中，并且符合約束變量的換名原則。束變量的換名原則。 前束標(biāo)準(zhǔn)型前束標(biāo)準(zhǔn)型2022-4-1946 使用前面定義的等價(jià)式，總可以把一個(gè)公式化為使用前面定義的等價(jià)式，總可以把一個(gè)公式化為前束標(biāo)準(zhǔn)型。前束標(biāo)準(zhǔn)型。 變換過程如下：變換過程如下： (1) (1) 使用等價(jià)式中的連接詞轉(zhuǎn)化規(guī)律消去公式中的使用等價(jià)

50、式中的連接詞轉(zhuǎn)化規(guī)律消去公式中的連接詞連接詞, , 。 (2) (2) 反復(fù)使用雙重否定律和德反復(fù)使用雙重否定律和德摩根律將摩根律將“( (或或) )”移到原子之前。移到原子之前。 (3) (3) 必要時(shí)重新命名量化的變量。必要時(shí)重新命名量化的變量。 (4) (4) 使用量詞分配律和等價(jià)式，把所有量詞都移到使用量詞分配律和等價(jià)式，把所有量詞都移到整個(gè)公式的最左邊以得出一個(gè)范式。整個(gè)公式的最左邊以得出一個(gè)范式。 前束標(biāo)準(zhǔn)型前束標(biāo)準(zhǔn)型2022-4-1947 二、合式公式的標(biāo)準(zhǔn)化二、合式公式的標(biāo)準(zhǔn)化o 2、合取范式的標(biāo)準(zhǔn)化過程、合取范式的標(biāo)準(zhǔn)化過程n應(yīng)用應(yīng)用合式公式性質(zhì)合式公式性質(zhì)將公式逐步轉(zhuǎn)化的過

51、程。將公式逐步轉(zhuǎn)化的過程。n轉(zhuǎn)化步驟沒有嚴(yán)格的規(guī)定轉(zhuǎn)化步驟沒有嚴(yán)格的規(guī)定n較合理的化簡(jiǎn)過程，分為較合理的化簡(jiǎn)過程，分為8步：步：o 消去多余的量詞（很少出現(xiàn)）；消去多余的量詞（很少出現(xiàn)）；o 消去蘊(yùn)涵符號(hào)；消去蘊(yùn)涵符號(hào)；o 內(nèi)移否定符號(hào)；內(nèi)移否定符號(hào)；o 變量換名；變量換名；o 消去存在量詞；消去存在量詞；o 全稱量詞前束化；全稱量詞前束化；o 消去全稱量詞；消去全稱量詞；o 把把母式母式轉(zhuǎn)化為轉(zhuǎn)化為合取范式合取范式。2022-4-1948 二、合式公式的標(biāo)準(zhǔn)化二、合式公式的標(biāo)準(zhǔn)化o 2、合取范式的標(biāo)準(zhǔn)化過程、合取范式的標(biāo)準(zhǔn)化過程o 消去多余的量詞（很少出現(xiàn)）消去多余的量詞（很少出現(xiàn)）n若若一

52、個(gè)量詞的轄域內(nèi)并未出現(xiàn)量詞的約束變量一個(gè)量詞的轄域內(nèi)并未出現(xiàn)量詞的約束變量，則該量詞是多，則該量詞是多余的，應(yīng)該刪除；余的，應(yīng)該刪除；n例，例，( x)P(y)，則，則( x)可以消去，得到可以消去，得到P(y)；n正常情況下，合式公式中不應(yīng)出現(xiàn)多余的量詞。正常情況下，合式公式中不應(yīng)出現(xiàn)多余的量詞。o 消去蘊(yùn)涵符號(hào)消去蘊(yùn)涵符號(hào)n蘊(yùn)涵式轉(zhuǎn)化蘊(yùn)涵式轉(zhuǎn)化：P Q P Q；n例，例， Q(x,y) P(y) Q(x,y) P(y)。2022-4-1949 二、合式公式的標(biāo)準(zhǔn)化二、合式公式的標(biāo)準(zhǔn)化o2、合取范式的標(biāo)準(zhǔn)化過程、合取范式的標(biāo)準(zhǔn)化過程o內(nèi)移否定符號(hào)內(nèi)移否定符號(hào)n使否定只出現(xiàn)在原子謂詞公式前，構(gòu)

53、成使否定只出現(xiàn)在原子謂詞公式前，構(gòu)成否定文字否定文字；n狄狄.摩根定律：摩根定律：o (P Q) P Qo (P Q) P Qn雙重否定：雙重否定： ( P) Pn量詞否定：量詞否定：o ( x) P(x) ( x) ( P(x) o ( x) P(x) ( x) ( P(x) n例，例， ( y) P(y)P(f(x,y)( y)P(y) P(f(x,y)o變量換名變量換名n“全稱量詞前束化全稱量詞前束化”后，同名變量的轄域無法區(qū)分，所以為避免差錯(cuò)，后，同名變量的轄域無法區(qū)分，所以為避免差錯(cuò)，必須換名；必須換名；n約束變量的虛元性約束變量的虛元性進(jìn)行變換；進(jìn)行變換；o( x) P(x) (

54、y) P(y) o( x) P(x) ( y) P(y)2022-4-1950o消去存在量詞消去存在量詞Skolem標(biāo)準(zhǔn)化過程111().()(,.,)nnnQ xQ x M xxStep1: 化成前束范式化成前束范式:Step2: 使用下述方法可以消去前綴中存在的所有量詞：使用下述方法可以消去前綴中存在的所有量詞： 令令 是是 中出現(xiàn)的存在量詞中出現(xiàn)的存在量詞 。rQ1 1().()n nQ xQ x(1)r n Case1: 若在若在 之前不出現(xiàn)全稱量詞，則選擇一個(gè)與之前不出現(xiàn)全稱量詞，則選擇一個(gè)與M中出現(xiàn)的所有常量都不相同的新常量中出現(xiàn)的所有常量都不相同的新常量c，用，用c代替代替M中出

55、中出現(xiàn)的所有現(xiàn)的所有xr，并且由前綴中刪去，并且由前綴中刪去(Qrxr) 。rQCase2: 若在若在 之前出現(xiàn)全稱量詞之前出現(xiàn)全稱量詞 ，則選擇一，則選擇一個(gè)與個(gè)與M中出現(xiàn)的任一函數(shù)符號(hào)都不相同的新中出現(xiàn)的任一函數(shù)符號(hào)都不相同的新m元函數(shù)符元函數(shù)符號(hào)號(hào)f，用，用 代替代替M中的所有中的所有xr ，并且由前綴中，并且由前綴中刪去刪去(Qrxr) 。rQ1,.,ssmQQ1(,.,)ssmf xx 按上述方法刪去前綴中的所有存在量詞之后得出的公式稱為按上述方法刪去前綴中的所有存在量詞之后得出的公式稱為合式公式的合式公式的Skolem標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型。替代存在量化變量的常量。替代存在量化變量的常量c(

56、視為視為0元元函數(shù)函數(shù))和函數(shù)和函數(shù)f稱為稱為Skolem函數(shù)。函數(shù)。2022-4-1951( , , , , ,)x y z u v wP x y z u v w 在公式中在公式中， 的前面沒有全稱量詞的前面沒有全稱量詞， 的前面有全稱量的前面有全稱量詞詞 和和 , 在在 的前面有全稱量詞的前面有全稱量詞 ， 和和 。所。所以，在以，在 中，用常數(shù)中，用常數(shù)a代替代替x, 用二元函數(shù)用二元函數(shù)f(y,z)代代替替u, 用三元函數(shù)用三元函數(shù)g(y,z,v)代替代替w,去掉前綴中的所有存在量詞之去掉前綴中的所有存在量詞之后得出后得出Skolem標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型：()y()w()y() z()v( ,

57、 , , , ,)P x y z u v w(z)()u() x例題分析例例4.1 化公式化公式為為Skolem標(biāo)準(zhǔn)型。標(biāo)準(zhǔn)型。),(,),(,(vzygvzyfzyavPzy2022-4-1952 二、合式公式的標(biāo)準(zhǔn)化二、合式公式的標(biāo)準(zhǔn)化o2、合取范式的標(biāo)準(zhǔn)化過程、合取范式的標(biāo)準(zhǔn)化過程o消去存在量詞消去存在量詞n 在在 的轄域內(nèi)的轄域內(nèi)o ( z)( w) Q(x,z) P(z,w)o w依賴于依賴于z，由函數(shù)，由函數(shù)w=g(z)來定義這種依賴關(guān)系；來定義這種依賴關(guān)系；o 用用g(z)來取代約束變量來取代約束變量w，消去存在量詞，消去存在量詞 w；o ( z) Q(x,z) P(z,g(z)

58、n 在在多個(gè)多個(gè) 的轄域內(nèi)的轄域內(nèi)o ( x)( y)( z)( w)P(x,y,z,w)o 用多元函數(shù)用多元函數(shù)g(x,y,z)來取代約束變量來取代約束變量w，消去存在量詞，消去存在量詞 w；o ( x)( y)( z)P(x,y,z,g(x,y,z)n 在在 的轄域外的轄域外o ( w)( z) Q(x,z) P(z,w)o 用用任意常量任意常量A取代約束變量取代約束變量w，消去存在量詞，消去存在量詞 wo ( z) Q(x,z) P(z,A)前兩種叫前兩種叫Skolem函數(shù)，第三函數(shù)，第三種叫種叫Skolem常量常量2022-4-1953總結(jié)：總結(jié)：Skolem函數(shù)和函數(shù)和Skolem常

59、量常量 在消去存在量詞的過程中，需要用到在消去存在量詞的過程中，需要用到Skolem函數(shù)或函數(shù)或Skolem常量。若常量。若存在量詞是在全稱量詞的轄域內(nèi)存在量詞是在全稱量詞的轄域內(nèi)，用用Skolem函數(shù)消去存在量詞函數(shù)消去存在量詞。 Skolem函數(shù)所使用函數(shù)所使用的函數(shù)符號(hào)必須是的函數(shù)符號(hào)必須是新的新的，即不允許是公式中已經(jīng)出現(xiàn)，即不允許是公式中已經(jīng)出現(xiàn)過的函數(shù)符號(hào)。過的函數(shù)符號(hào)。 若要消去的若要消去的存在量詞不在任何一個(gè)全稱量詞的轄域內(nèi)存在量詞不在任何一個(gè)全稱量詞的轄域內(nèi)，用不含變量的，用不含變量的Skolem函數(shù)即函數(shù)即Skolem常量消去存常量消去存在量詞在量詞。所使用的常量符號(hào)必須是

60、。所使用的常量符號(hào)必須是新的新的，它未曾在公，它未曾在公式其他地方使用過。式其他地方使用過。 Skolem變換變換不是等價(jià)變換，但變換前后的值永假性不是等價(jià)變換，但變換前后的值永假性保持不變保持不變。2022-4-1954 二、合式公式的標(biāo)準(zhǔn)化二、合式公式的標(biāo)準(zhǔn)化o 2、合取范式的標(biāo)準(zhǔn)化過程、合取范式的標(biāo)準(zhǔn)化過程o 全稱量詞前束化全稱量詞前束化n經(jīng)過經(jīng)過“變量換名變量換名”后，所有量詞的約束變量均有不同的后，所有量詞的約束變量均有不同的名字；名字；n只要簡(jiǎn)單地將只要簡(jiǎn)單地將 移到合式公式的最前面；移到合式公式的最前面；n約束變量的作用范圍不會(huì)變化。約束變量的作用范圍不會(huì)變化。o 消去全稱量詞消