湖北工業(yè)大學(xué)2015年12月人工智能匯編

1、人 工 智 能廖家平共二百二十二頁(yè)第1章 人工智能(rn n zh nn)綜述第2章 數(shù)理邏輯(shl-lu j)基礎(chǔ)第3章 歸結(jié)推理方法第4章 用于人工智能的Prolog語(yǔ)言第5章 知識(shí)表示第6章 產(chǎn)生式系統(tǒng)的搜索策略第7章 專(zhuān)家系統(tǒng)第8章 知識(shí)獲取與機(jī)器學(xué)習(xí)THE END共二百二十二頁(yè)第1章 人工智能(rn n zh nn)綜述本章(bn zhn)主要內(nèi)容：智能與人工智能人工智能發(fā)展的歷史回顧人工智能的研究目標(biāo)與研究途徑人工智能的研究領(lǐng)域共二百二十二頁(yè)1.1 智能(zh nn)與人工智能(zh nn)關(guān)于智能的幾種解釋?zhuān)褐悄苁侨藗兲幚硎挛?、解決問(wèn)題時(shí)表現(xiàn)出來(lái)(ch li)的智慧和能力。智能

2、是知識(shí)和智力的總和。目前尚不能給智能一個(gè)確切的定義。智能所具有的一些基本特征：記憶與思維能力感知能力自適應(yīng)能力表達(dá)能力自學(xué)習(xí)能力共二百二十二頁(yè)有關(guān)人工智能的幾種(j zhn)說(shuō)明：智能機(jī)器：能夠在各類(lèi)環(huán)境中自主(zzh)地或交互地執(zhí)行各種擬人的機(jī)器人工智能（學(xué)科）：是計(jì)算機(jī)科學(xué)中涉及研究、設(shè)計(jì)和應(yīng)用智能機(jī)器的一個(gè)分支。人工智能（能力）：是智能機(jī)器所執(zhí)行的與人類(lèi)智能有關(guān)的功能，如判斷、推理、證明、識(shí)別、感知、理解、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問(wèn)題求解等思維活動(dòng)。簡(jiǎn)單地講，人工智能是關(guān)于： 機(jī)器智能和智能機(jī)器的研究共二百二十二頁(yè)人工智能(rn n zh nn)是工程技術(shù)學(xué)科，同時(shí)也是理論研究學(xué)科。 作

3、為工程技術(shù)學(xué)科，人工智能的目的是：提出(t ch)建造人工智能系統(tǒng)的新技術(shù)、新方法和新理論，并在此基礎(chǔ)上研制出具有只能行為的計(jì)算機(jī)系統(tǒng)。 作為理論研究學(xué)科，人工智能的目的是：提出能夠描述和解釋智能行為的概念與理論，為建造人工智能系統(tǒng)提供理論依據(jù)。 長(zhǎng)期以來(lái)，圍繞人工智能有很多爭(zhēng)議。“機(jī)器是否能思考？”這一問(wèn)題吸引了許多哲學(xué)家、科學(xué)家和工程師。 計(jì)算機(jī)科學(xué)的創(chuàng)始人之一，艾侖圖靈(Alan Turing)談到這一問(wèn)題：共二百二十二頁(yè)Alan Turing Alan Turing指出：“機(jī)器是否能思考”這一問(wèn)題的答案取決與人們(rn men)如何定義“機(jī)器”和“思考”。也許還可以指出，這一問(wèn)題還取決

4、于如何定義“能”。先考慮(kol)“機(jī)器”這一詞。再看看“思考”這個(gè)詞。共二百二十二頁(yè)1.2 人工智能發(fā)展(fzhn)的歷史回顧 20世紀(jì)(shj)30年代和40年代： 20世紀(jì)50年代：John McCarthy數(shù)學(xué)邏輯和關(guān)于計(jì)算的新思想第一次人工智能討論會(huì) 20世紀(jì)60年代：第一屆國(guó)際人工智能聯(lián)合會(huì)議 20世紀(jì)70年代：人工智能?chē)?guó)際雜志創(chuàng)刊 20世紀(jì)80年代：專(zhuān)家系統(tǒng)和知識(shí)工程在全世界迅速發(fā)展國(guó)外的發(fā)展情況共二百二十二頁(yè)國(guó)內(nèi)的發(fā)展(fzhn)情況 1978年國(guó)家“智能模擬(mn)”研究計(jì)劃 1984年召開(kāi)智能計(jì)算機(jī)及系統(tǒng)全國(guó)學(xué)術(shù)討論會(huì)把智能計(jì)算機(jī)系統(tǒng)、智能機(jī)器人和智能信息處理列入國(guó)家高技術(shù)

5、研究計(jì)劃。 1986年 1989年首次召開(kāi)中國(guó)人工智能聯(lián)合會(huì)議 1987年模式識(shí)別與人工智能雜志創(chuàng)刊 1993年智能控制和智能自動(dòng)化被列入國(guó)家科技攀登計(jì)劃 1997年由本人編寫(xiě)的人工智能原理及應(yīng)用出版共二百二十二頁(yè)1.3 人工智能的研究(ynji)目標(biāo)與研究(ynji)途徑 研究目標(biāo)(mbio)分為近期目標(biāo)和遠(yuǎn)期目標(biāo)：近期目標(biāo)是，使現(xiàn)有的計(jì)算機(jī)更聰明、更有用；遠(yuǎn)期目標(biāo)是，構(gòu)造智能機(jī)器。 關(guān)于人工智能的研究途徑有兩種不同觀點(diǎn)：主張用生物學(xué)的方法進(jìn)行研究-產(chǎn)生出一大學(xué)派叫做連接主義(Connectionism)主張用計(jì)算機(jī)科學(xué)的方法進(jìn)行研究-產(chǎn)生出一大學(xué)派叫做符號(hào)主義(Symbolism)共二百二

6、十二頁(yè)Agent一詞的兩種解釋?zhuān)阂皇?，?duì)環(huán)境的認(rèn)識(shí)以及對(duì)環(huán)境產(chǎn)生作用的行為者；二是，代理人。 傾向于第一種解釋的主要是AI領(lǐng)域的研究者M(jìn). Minsky指出：“當(dāng)你試圖說(shuō)明完成一些任務(wù)的機(jī)器并試圖了解它是如何工作時(shí),即將其處理為黑箱時(shí),就稱(chēng)其為Agent。 軟件界的研究(ynji)人員傾向于第二種解釋?zhuān)捍砣?。Agent是計(jì)算機(jī)軟件，代表用戶(hù)，以主動(dòng)服務(wù)方式完成一定操作的計(jì)算實(shí)體。Agent是具有信息處理能力的主動(dòng)實(shí)體，其結(jié)構(gòu)包含下述模塊：感知器、效應(yīng)器、信息處理器、目標(biāo)模塊、通信機(jī)制。 共二百二十二頁(yè) 僅代理用戶(hù)某種任務(wù)的軟件不能稱(chēng)為智能Agent。智能性，如理解用戶(hù)用自然語(yǔ)言表達(dá)的對(duì)信息資

7、源和計(jì)算資源的需求，幫助用戶(hù)在一定程度上克服信息內(nèi)容的語(yǔ)言障礙，捕捉用戶(hù)的偏好和興趣，推測(cè)用戶(hù)的意圖并為其代勞等。只有代理性、智能性、自主性均達(dá)到相當(dāng)水準(zhǔn)的系統(tǒng)才有條件稱(chēng)為智能Agent。 比爾?蓋茨把智能Agent稱(chēng)為“軟的軟件”，他說(shuō)：“一旦程序?qū)懞昧?，它就一成不變。軟的軟件隨著你的使用好象會(huì)變得越來(lái)越聰明”，“你可以把Agent當(dāng)作直接內(nèi)置在軟件中的合作者，它會(huì)記住你擅長(zhǎng)什么，你過(guò)去做過(guò)些什么，并試著預(yù)測(cè)(yc)難題，并提出解決辦法”。共二百二十二頁(yè)1.4 人工智能(rn n zh nn)的研究領(lǐng)域?qū)＜蚁到y(tǒng)(zhun ji x tn)與知識(shí)工程自動(dòng)定理證明與自動(dòng)推理機(jī)器學(xué)習(xí)自然語(yǔ)言理解智

8、能管理系統(tǒng)自動(dòng)程序設(shè)計(jì)感知系統(tǒng)智能機(jī)器人共二百二十二頁(yè) 專(zhuān)家系統(tǒng)是一個(gè)智能計(jì)算機(jī)程序系統(tǒng)。其內(nèi)部具有大量專(zhuān)家水平的知識(shí)和經(jīng)驗(yàn)，能夠利用人類(lèi)專(zhuān)家的知識(shí)和解決問(wèn)題的方法來(lái)解決該領(lǐng)域的問(wèn)題。也就是說(shuō)，專(zhuān)家系統(tǒng)是一個(gè)具有大量知識(shí)與經(jīng)驗(yàn)的程序系統(tǒng)。它應(yīng)用人工智能技術(shù)，根據(jù)(gnj)某個(gè)領(lǐng)域一個(gè)或多個(gè)人類(lèi)專(zhuān)家提供的知識(shí)和經(jīng)驗(yàn)進(jìn)行推理和判斷，模擬人類(lèi)專(zhuān)家的決策過(guò)程，以解決那些需要專(zhuān)家決定的復(fù)雜問(wèn)題。共二百二十二頁(yè) 自動(dòng)定理證明是人工智能最早得到應(yīng)用的領(lǐng)域(ln y)。對(duì)于一個(gè)數(shù)學(xué)定理，給出嚴(yán)格的數(shù)學(xué)證明，是一項(xiàng)高智能的工作。不僅需要很強(qiáng)的推理能力，而且需要人們有著深刻的洞察力，能預(yù)見(jiàn)出在證明主要定理之前，應(yīng)

9、先證明哪些引理，作好必要的準(zhǔn)備，最后證明主要定理。共二百二十二頁(yè) 機(jī)器學(xué)習(xí)領(lǐng)域的研究工作主要(zhyo)從三個(gè)方面進(jìn)行：一是面向任務(wù)的研究，研究和分析改進(jìn)一組預(yù)定任務(wù)的執(zhí)行性能的學(xué)習(xí)系統(tǒng)；二是認(rèn)識(shí)模擬，研究人類(lèi)學(xué)習(xí)過(guò)程并進(jìn)行計(jì)算機(jī)模擬；三是理論性分析，從理論上探索各種可能的學(xué)習(xí)方法和獨(dú)立于應(yīng)用領(lǐng)域的算法。共二百二十二頁(yè) 自然語(yǔ)言理解就是研究如何讓機(jī)器理解人類(lèi)的自然語(yǔ)言。機(jī)器翻譯也屬于(shy)自然語(yǔ)言理解的范疇，它是研究把一種語(yǔ)言自動(dòng)的翻譯成另一種語(yǔ)言。自然語(yǔ)言理解這一課題雖然困難，但對(duì)人工智能的發(fā)展卻起著重要的作用。共二百二十二頁(yè) 智能管理是人工智能在管理領(lǐng)域中的應(yīng)用，發(fā)展了“智能管理”新技

10、術(shù)和新一代的計(jì)算機(jī)管理系統(tǒng) “智能管理系統(tǒng)”，如：智能管理信息系統(tǒng)（IMIS Intelligent Management Information System）、智能辦公自動(dòng)化系統(tǒng)（IOAS Intelligent Office Automation System）、智能決策支持系統(tǒng)（IDSS Intelligent Decision Support System）等。 智能管理系統(tǒng)（IMS Intelligent Management System）不僅比常規(guī)的計(jì)算機(jī)管理系統(tǒng)MIS、OAS、DSS等具有更高的智能水平，可以為非結(jié)構(gòu)化半結(jié)構(gòu)化的管理決策提供(tgng)信息服務(wù)和決策支持；而且

11、具有更全面的管理功能，可同時(shí)具備信息管理、事務(wù)處理、決策支持等多種功能。共二百二十二頁(yè) 自動(dòng)程序設(shè)計(jì)：包括程序綜合與程序驗(yàn)證兩方面的內(nèi)容。前者用以實(shí)現(xiàn)(shxin)自動(dòng)編程，即用戶(hù)只需告訴計(jì)算機(jī)“做什么”，無(wú)須告訴“怎樣做”；后者是指程序的自動(dòng)驗(yàn)證，自動(dòng)完成正確性檢查。共二百二十二頁(yè) 人工智能的感知(gnzh)系統(tǒng)的任務(wù)，就是為計(jì)算機(jī)配置各種感覺(jué)器官，是其具有感知能力，能夠識(shí)別各種圖形、文字及各種語(yǔ)言信號(hào)。共二百二十二頁(yè) 智能機(jī)器人是模擬(mn)人類(lèi)行為的機(jī)器。它是人工智能中感知系統(tǒng)、問(wèn)題求解系統(tǒng)、計(jì)劃產(chǎn)生系統(tǒng)等領(lǐng)域技術(shù)的綜合應(yīng)用。共二百二十二頁(yè)第2章 數(shù)理邏輯(shl-lu j)基礎(chǔ)本章主要

12、(zhyo)內(nèi)容：命題邏輯謂詞與量詞謂詞公式及其解釋謂詞公式的標(biāo)準(zhǔn)形式謂詞公式的等價(jià)與蘊(yùn)涵共二百二十二頁(yè)2.1 命題邏輯一個(gè)(y )命題是一個(gè)(y )或真或假不能兩者都是的斷言。斷言(dunyn)是指一陳述語(yǔ)句。簡(jiǎn)單地說(shuō)，命題是指一句有真假意義的陳述句。命題為真，記為 T 命題為假，記為 F命題變?cè)?P, Q, R表示；一個(gè)命題P如果是真值未指定任意命題，稱(chēng)P為命題變?cè)Ｈ绻鸓是一個(gè)真值已經(jīng)指定的命題，稱(chēng)為命題常元。命題常元只有 T 和 F。 共二百二十二頁(yè)2.1.l 命題(mng t)聯(lián)結(jié)詞（邏輯聯(lián)結(jié)詞、邏輯運(yùn)算符）復(fù)合命題(mng t)：?jiǎn)蝹€(gè)命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)構(gòu)成的新命題。常用的5種聯(lián)結(jié)

13、詞：復(fù)合命題與原命題的真值關(guān)系P Q P PQ PQ PQ PQF F T F F T TT F F T F F FF T T T F T FT T F T T T T否定 合取 析取 蘊(yùn)涵 等值 共二百二十二頁(yè)2.1.2 命題(mng t)公式及其解釋原子公式：?jiǎn)蝹€(gè)命題(mng t)變?cè)?、單個(gè)命題(mng t)常元稱(chēng)為原子公式。命題公式：由如下規(guī)則生成的公式稱(chēng)為命題公式：1. 單個(gè)原子公式是命題公式。2. 若A ,B是命題公式，則A , AB , AB , A B , A B是公式。3. 所有命題公式都是有限次應(yīng)用1、2得到的符號(hào)串。命題公式的解釋?zhuān)航o命題公式中的每一個(gè)命題變?cè)付ㄒ粋€(gè)真假值

14、， 這一組真假值，就是命題公式的一個(gè)解釋。用I表示。例如：公式G= (AB) C 的一個(gè)解釋是：I1(G) = A/T, B/F, C/T 在解釋I1(G)下G為真。永真公式與永假公式：如果公式在它所有的解釋I下，其值都為T(mén)，則稱(chēng)公式G為恒真的；如果其值都為F，則稱(chēng)公式G為恒假的（不可滿(mǎn)足的）。共二百二十二頁(yè)注意(zh y)：關(guān)于五個(gè)聯(lián)結(jié)詞的約定：* 結(jié)合力的強(qiáng)弱順序： ， ， ， ， * 聯(lián)結(jié)詞相同時(shí)，從左至右運(yùn)算。解釋的個(gè)數(shù)：如果一個(gè)公式G中有n個(gè)不同的原子公式（或簡(jiǎn)稱(chēng)原子），則G有2n個(gè)不同的解釋?zhuān)谑荊在2n個(gè)解釋下有2n個(gè)真值。如果將這些真值和它們的解釋列成表，就是G的真值表。共二百

15、二十二頁(yè)2.1.3 等價(jià)(dngji)命題公式如果(rgu)兩個(gè)命題公式所含原子公式相同，且在任一解釋下，兩個(gè)命題公式的值相同，則稱(chēng)這兩個(gè)命題公式為等價(jià)命題公式或等價(jià)公式。常用的等價(jià)公式有：1. (P Q)= (P Q) (Q P)P Q P Q Q P (P Q) (Q P) P QT T T T T TT F F T F FF T T F F FF F T T T T2.(P Q)=(P Q)共二百二十二頁(yè)3. (P)= P4.交換律：P Q=Q P P Q=Q P5.結(jié)合律：P (Q R)=(P Q) R P (Q R)=(P Q) R6.分配律：P (Q R)=(P Q) (P R)

16、P (Q R)=(P Q) (P R)7.泛界律：P F=P ,P T=P P F=F ,P T=T 8.互余律：P P=T,P P=F9.德 摩根定律(dngl)：(P Q)=P Q (P Q)=P Q共二百二十二頁(yè)證明兩個(gè)(lin )公式等價(jià)，可用真值表，也可用基本公式。例如 要證明(zhngmng)公式 P Q=Q P證 P Q = P Q = P ( Q )=(Q) P=Q P若要證明公式P P Q=P證 P P Q = P ( P Q) = P (Q Q) ( P Q)= (P Q) (P Q) ( P Q)=( P Q) ( P Q) = P (Q Q)=P共二百二十二頁(yè)2.1.4

17、 永真蘊(yùn)涵(ynhn)式 若命題公式G H是恒真的，稱(chēng)其為永真蘊(yùn)涵式。記為GH，讀做“G蘊(yùn)涵H”，也稱(chēng)“G是H的邏輯(lu j)結(jié)果”。常用的永真蘊(yùn)涵式：1. P P Q 證P P Q = P (P Q) = P P Q = T Q = T2. P Q P證P Q P =(P Q) P= P Q P=T Q= T共二百二十二頁(yè)3. P (P Q) Q4.( P Q) Q P5. P (P Q) Q6.(P Q) (Q R) (P R)7.( P Q) ( (Q R) ( P R)8.(P Q) ( R S) (P R Q S)9.( P Q) ( Q R) ( P R)共二百二十二頁(yè)公式的標(biāo)準(zhǔn)

18、(biozhn)形式：范式 析取范式 (disjunctive normal form,DNF) ：一個(gè)(y )由原子和原子的非組成的析取式，如果與給定的命題公式A等價(jià)，則稱(chēng)它是A的析取范式。記作：A=A1 A2 . An n1其中， A1 ,A2, . An 是原子或是原子非的合取式。 合取范式 (conjunctive normal form,CNF) ：一個(gè)由原子和原子的非組成的合取式，如果與給定的命題公式A等價(jià)，則稱(chēng)它是A的合取范式。記作：A=A1 A2 . An n1其中， A1 ,A2, . An 是原子或是原子非的析取式。注意：1. 任何一個(gè)命題公式豆科儀轉(zhuǎn)化成它的析取范式或合取

19、范式; 2. 一個(gè)公式的析取范式和合取范式都不是唯一的； 3. 運(yùn)算符最少的范式稱(chēng)為最簡(jiǎn)范式。共二百二十二頁(yè)2.2 謂詞(wi c)與量詞在命題演算中，基本元素是原子(yunz)命題，而不考慮命題的內(nèi)部結(jié)構(gòu)和成分。在形式邏輯中有一個(gè)三段論法：P:“所有的人都會(huì)犯錯(cuò)誤”Q:“張三是人”R:“張三會(huì)犯錯(cuò)誤” R應(yīng)該是P和Q的邏輯結(jié)論。但在命題邏輯中無(wú)法準(zhǔn)確表達(dá)這三個(gè)命題的邏輯關(guān)系。因?yàn)? P Q ) R 不是恒真的。如：取解釋:I=P/T,Q/T,R/F 則公式為假值F. 就是說(shuō)解釋I 弄假了此公式。為準(zhǔn)確表達(dá)此類(lèi)公式，必須引進(jìn)謂詞和量詞的概念。共二百二十二頁(yè)2.2.1謂詞(wi c)先看幾個(gè)(j

20、 )命題：1. 3是質(zhì)數(shù)2. 王二生于武漢市3. 7=23 x是質(zhì)數(shù)x生于武漢市x=y zF(x)G(x,y)H(x,y,z)稱(chēng)“3”、“王二”、“武漢市”、“7”、“2”、“3”為個(gè)體;代表個(gè)體的變?cè)Q(chēng)為個(gè)體變?cè)?；刻?huà)個(gè)體性質(zhì)或個(gè)體之間關(guān)系的詞叫謂詞?！笆琴|(zhì)數(shù)”、“生于”、“=. .”都是謂詞。共二百二十二頁(yè)2.2.2 量詞(lingc)量詞分為(fn wi)全稱(chēng)量詞和存在量詞。符號(hào)“”表示全稱(chēng)量詞。符號(hào)“”表示存在量詞。 x讀作“對(duì)一切x”,或“對(duì)每一x”，或“對(duì)任一x”。x是所作用的個(gè)體變?cè)?x讀作“存在一個(gè)x”,或“對(duì)某些x”，或“至少有一x”。x是所作用的個(gè)體變?cè)?。再看前面的三段?/p>

21、法：P:“所有的人都會(huì)犯錯(cuò)誤”Q:“張三是人”R:“張三會(huì)犯錯(cuò)誤”x(M(x) R(x)M(“張三”)R(“張三”)共二百二十二頁(yè)在謂詞前加上x(chóng),叫做變?cè)蝗Q(chēng)(qun chn)量化；在謂詞前加上 x,叫做變?cè)淮嬖诹炕?。量化的目的是約束變?cè)?.2.3 約束(yush)變?cè)?、自由變?cè)⒏拿?guī)則量詞的轄域約束出現(xiàn)自由出現(xiàn) 改名規(guī)則：在同一公式中，一個(gè)變?cè)纫约s束出現(xiàn)，有以自由出現(xiàn)。就需要對(duì)變?cè)拿?。改名?guī)則是：1. 變?cè)粢拿瑒t該變?cè)诹吭~及其轄域中的所有出現(xiàn)均須一起更改，其余部分不變；2. 變?cè)拿麜r(shí)所選用的符號(hào)，必須是量詞轄域內(nèi)未出現(xiàn)的符號(hào)。一般還應(yīng)是公式中未出現(xiàn)的符號(hào)。共二百二十二頁(yè)

22、2.3 謂詞公式(gngsh)及其解釋在定義謂詞公式(gngsh)前,先介紹“符號(hào)”的概念： “項(xiàng)”的定義；原子的定義：符號(hào)：常元符號(hào)變?cè)?hào)函數(shù)符號(hào)謂詞符號(hào)關(guān)于項(xiàng)的定義：1. 常元符號(hào)是項(xiàng)；2. 變?cè)?hào)是項(xiàng)；3. 若f是n元函數(shù)符號(hào)，t1, tn 是項(xiàng)， 則f( t1, tn )是項(xiàng)；4. 所有項(xiàng)都是有限次使用1,2,3生成的符號(hào)串。原子的定義：若P(x1, xn)是n元謂詞符號(hào)， t1, tn 是項(xiàng)， 則P(t1, tn)共二百二十二頁(yè)謂詞公式(gngsh)（公式(gngsh)）的定義：1. 原子公式是公式；2. 若H,G是公式，則H , H G , H G , H G , H G是公式

23、；3. 若G是公式，x是G中的自由變?cè)?，則xG xG是公式；4. 所有(suyu)公式都是有限次應(yīng)用1、2、3得到的符號(hào)串。解釋的定義：公式G的一個(gè)解釋I，是由非空集D和下列對(duì)G中常元符號(hào)、函數(shù)符號(hào)、謂詞符號(hào)的一組指定組成：1.對(duì)每個(gè)常元符號(hào)，指定D中一個(gè)元素。2.對(duì)每個(gè)n元函數(shù)符號(hào)，指定一個(gè)函數(shù)，即指定Dn到D的一個(gè)映射。3.對(duì)每個(gè)n元謂詞符號(hào)，指定一個(gè)謂詞，即指定Dn到T,F的一個(gè)映射。共二百二十二頁(yè)例2.1給以下(yxi)公式指定一個(gè)解釋?zhuān)?. x P(f(x) Q(x,f(a)2. x(P(x) Q(x,a)可指定如下(rxi)解釋I：D=1,2a/1f(1)/2 f(2)/1P(1)

24、/FP(2)/TQ(1,1)/T Q(1,2)/T Q(2,1)/FQ(2,2)/T在此解釋I下，公式 x P(f(x) Q(x,f(a)為T(mén)值。而公式x(P(x) Q(x,a)在此解釋下為F值。如果存在I使G為T(mén)值，則稱(chēng)G可滿(mǎn)足，簡(jiǎn)稱(chēng)I滿(mǎn)足G;若I使G為F值，稱(chēng)I不滿(mǎn)足G，或稱(chēng)I弄假G。如果不存在解釋I滿(mǎn)足公式G，公式G成為不可滿(mǎn)足的。如果公式G的所有解釋I都滿(mǎn)足G,公式G稱(chēng)為恒真的。共二百二十二頁(yè)2.4 謂詞公式(gngsh)的等價(jià)與蘊(yùn)涵兩個(gè)謂詞公式等價(jià)： 設(shè)P與Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域，若D上的任何一個(gè)解釋?zhuān)琍與Q都有相同的值，則稱(chēng)公式P和公式Q在D上是等價(jià)的。謂詞公式的蘊(yùn)

25、涵： 設(shè)P與Q是兩個(gè)謂詞公式，如果PQ是恒真的，則稱(chēng)P蘊(yùn)涵Q。且稱(chēng)Q為P的邏輯結(jié)論，稱(chēng)P為Q的前提，記作 PQ。 顯然(xinrn)，若Q是P的邏輯結(jié)論，則對(duì)P,Q的任意一個(gè)解釋I,如果P在I下為真，那么Q在I下也為真。反之亦然。共二百二十二頁(yè)P(yáng):“所有(suyu)的人都會(huì)犯錯(cuò)誤”Q:“張三是人”R:“張三會(huì)犯錯(cuò)誤”x(M(x) R(x)M(“張三(zhn sn)”)R(“張三”)需要證明R是(P Q)的邏輯結(jié)論。即證明PQ R 為恒真。證：設(shè)I是P,Q,R的一個(gè)解釋?zhuān)↖指定“張三”為始量），且I滿(mǎn)足（P Q),即I滿(mǎn)足x(M(x) R(x) M(“張三”)，所以I滿(mǎn)足R(“張三”）。 否則，

26、R（“張三”）在I下為假，于是（M(“張三”) R(“張三”)）在I下為假，故x(M(x) R(x)在I下為假，矛盾。所以R(“張三”)在I下為真。三段法的證明：共二百二十二頁(yè)2.5 謂詞公式的標(biāo)準(zhǔn)(biozhn)形式2.5.1 前束范式一個(gè)謂詞公式，如果(rgu)量詞非否定地放在全式的開(kāi)頭，而量詞的轄域都延伸到整個(gè)謂詞公式，則稱(chēng)這樣的公式為前束范式。一般地，謂詞邏輯中的公式G如果有如下形狀：Q1x1,Qn xn M(x1,xn)則稱(chēng)G為前束范式。其中Qi是xi或xi, i =1,n，M(x1,xn)是不含量詞的公式。 Q1x1,Qn xn稱(chēng)為首標(biāo)，M稱(chēng)為母式。如：xyz(P(x,y ) Q(

27、x,z)xyzP(x,y,z)都是前束范式。共二百二十二頁(yè) 利用改名規(guī)則、量詞否定公式和量詞轄域擴(kuò)張公式等，可把任一謂詞(wi c)公式化成前束范式。例如：x(P(x) xQ(x)=x(P(x) xQ(x)=x(P(x) xQ(x)= x(P(x) xQ(x)= x(P(x) yQ(y) xy(P(x) Q(y)例2.2將公式(gngsh)xy(z (P(x,z) P(y,z) uQ(x,y,u)化為前束范式：解： xy(z (P(x,z) P(y,z) uQ(x,y,u)= xy(z (P(x,z) P(y,z) uQ(x,y,u)= xy(z (P(x,z) P(y,z) uQ(x,y,u

28、)=xyzu (P(x,z) P(y,z) Q(x,y,u)共二百二十二頁(yè)步驟1：使用以下(yxi)基本等價(jià)公式，將G中的和刪去：F H=(F H) (H F)F H=F H步驟2：使用(F)=F，摩根定律及以下等價(jià)公式，將謂詞(wi c)公式中的所有 否定號(hào)放在原子之前：xG(x)=xG(x)xG(x)=xG(x)步驟3：如果需要，則將約束變量改名。步驟4：利用等價(jià)公式將所有量詞提到公式的最前面。將任意謂詞公式化為前束范式的四個(gè)步驟：共二百二十二頁(yè)2.5.2 Skolem范式(fn sh)Skolem范式是謂詞邏輯中公式的又一種標(biāo)準(zhǔn)形式(xngsh)。設(shè)公式G的形式如下：Q1x1,Qn xn

29、 M(x1,xn)其中Qi是xi或xi, i =1,n，M(x1,xn)是不含量詞的公式。將上式中的M(x1,xn)化為等值的和取范式，然后將所有的存在量詞消去，便可得到公式G的Skolem范式。消去G中的存在量詞的方法如下：設(shè)Qrxr (1 r n )是第一個(gè)出現(xiàn)在Q1x1, Qrxr ,Qn xn M(x1,xn)中的存在量詞，即Q1x1, Qr-1xr-1 均為全稱(chēng)量詞。若r=1，即Qrxr 左邊沒(méi)有全稱(chēng)量詞，則取異于M(x1,xn)中所有常量符號(hào)的常量符號(hào)C,并用C代表M(x1,xn)中的xr，然后在首標(biāo)中Qrxr。若1r n，即Qrxr左邊有全稱(chēng)量詞Qs1 xs1 ,Qsm xsm而

30、m1，1 s1s2.s mr，則取異于出現(xiàn)在M中的所有函數(shù)符號(hào)的m元函數(shù)符號(hào)f(xs1,xsm)，用f(xs1,xsm)代表出現(xiàn)在M中的所有xr,然后在首標(biāo)中刪除存在量詞Qrxr。共二百二十二頁(yè)例2.3將公式G=xyz(P(x,y)Q(x,z) R(x,y,z)化成(hu chn)Skolem范式。解：先將M(x,y,z)化成(hu chn)合取范式：M(x,y,z)= (P(x,y) Q(x,z) R(x,y,z)= (P(x,y) R(x,y,z) (Q(x,z) R(x,y,z) G= xyz(P(x,y) R(x,y,z) (Q(x,z) R(x,y,z) 消去y得到：xz(P(x,f

31、(x) R(x,f(x),z) (Q(x,z) R(x,f(x),z) 消去z得到：x (P(x,f(x) R(x,f(x),g(x) (Q(x,g(x) R(x,f(x),g(x)此式就是公式G的Skolem范式。 共二百二十二頁(yè)例2.4將公式(gngsh)G=xyzuvwP(x,y,z,u,v,w)化成Skolem標(biāo)準(zhǔn)型。解：消去x,因?yàn)槠渥筮?zu bian)沒(méi)有全稱(chēng)量詞，于是引入常量a代替P(x,y,z,u,v,w) 中的所有x,得： yzuvwP(a,y,z,u,v,w)消去u，因?yàn)槠渥筮呌腥Q(chēng)量詞yz，于是引入一個(gè)二元函數(shù)f(y,z)代替P(a,y,z,u,v,w)中的所有u，得：

32、 yzvwP(a,y,z,f(y,z),v,w)消去w ，因?yàn)槠渥筮呌腥Q(chēng)量詞 yzv，于是引入一個(gè)三元函數(shù)g(y,z,v)，代替P(a,y,z,f(y,z),v,w)中的所有w。最后得到的Skolem 標(biāo)準(zhǔn)型為：yzvP(a,y,z,f(y,z),v,g(y,z,v)注意：1.公式的Skolem 標(biāo)準(zhǔn)型與原公式并不等值；2.公式的Skolem 標(biāo)準(zhǔn)型與原公式在不可滿(mǎn)足的意義上相等。共二百二十二頁(yè)2.5.3 子句(z j)與子句(z j)集若干文字(wnz)的一個(gè)析取式成為子句。如：P(x,y) Q(x,y,z) R(u)沒(méi)有文字的子句成為空子句。只有一個(gè)文字的子句成為單元子句。將公式G化為S

33、kolem 標(biāo)準(zhǔn)型，其母式M已為合取范式，M中的沒(méi)一個(gè)合取項(xiàng)都是一個(gè)子句，M中這些子句的集合用S表示，稱(chēng)為公式G的子句集。從公式G得到子句集S的方法是：先從公式G得到Skolem 標(biāo)準(zhǔn)型，然后去掉全稱(chēng)量詞，最后用符號(hào)“，”代替符號(hào)“”。外層括號(hào)用。如公式：G=xyz(P(x,y) R(x,y,z) (Q(x,z) R(x,y,z)G的Skolem標(biāo)準(zhǔn)型為：x (P(x,f(x) R(x,f(x),g(x) (Q(x,g(x) R(x,f(x),g(x)G的子句集S為： (P(x,f(x) R(x,f(x),g(x)，(Q(x,g(x) R(x,f(x),g(x)子句集中S中的每一個(gè)子句中的變量

34、都是由全稱(chēng)量詞約束著。共二百二十二頁(yè) 對(duì)任一公式G都可以建立其對(duì)應(yīng)的S子句集。這樣對(duì)公式的討論就可以用對(duì)集合(jh)的討論來(lái)代替。引進(jìn)子句集S的目的就是要簡(jiǎn)化(jinhu)對(duì)A1 A2 A3B的證明，而證明A1 A2 A3B只需證明G= A1 A2 A3 B的子句集不可滿(mǎn)足即可。定理設(shè)S是公式G的子句集。于是，G是不可滿(mǎn)足的，當(dāng)且僅當(dāng)S是不可滿(mǎn)足的。子句集概念的推廣：設(shè)G= G1 . Gn ，Si是Gi化為Skolem范式后其木式給出的子句集，i=1,2,n。令S=S1. S n。于是G是不可滿(mǎn)足的，當(dāng)且僅當(dāng)S是不可滿(mǎn)足的。也稱(chēng)S是個(gè)G的子句集。共二百二十二頁(yè)第3章 歸結(jié)(guji)推理方法子

35、句(z j)集的海伯倫域海伯倫定理替換與合一算法歸結(jié)反演歸結(jié)原理本章主要內(nèi)容：（討論：如何證明一個(gè)子句集不可滿(mǎn)足）歸結(jié)控制策略課堂練習(xí)一共二百二十二頁(yè)3.1 子句(z j)集的海伯倫域3.1.1 海伯倫域與海伯倫解釋(jish)定義：H0是出現(xiàn)于子句集S的常量符號(hào)集合。如果S中無(wú)常量符號(hào)出現(xiàn)，則H0由一個(gè)常量符號(hào)a組成。對(duì)于 i =1,2,n 令Hi=Hi-1 所有型如fn(t1,t2,tn)的項(xiàng)的集合 其中fn(t1,t2,tn)是出現(xiàn)在S中的n元函數(shù)符號(hào)，tj Hi-1 j=1,2,n。于是稱(chēng)Hi為S的i級(jí)常量集，H 稱(chēng)為S的海伯倫（Herbrand）域,簡(jiǎn)稱(chēng)S的H域。例3.1子句集S為：

36、S=P(f(x),a,g(y),b)求子句集S的H域。解：根據(jù)定義H0=a,bH1=H0 f(a), f(b), g(a), g(b)=a,b, f(a), f(b), g(a),g(b)H2=H1 f(a), f(b), g(a),g(b),f(f(a), f(f(b), g(f(a),g(f(b), f(g(a), f(g(b), g(g(a),g(g(b)= a,b, f(a), f(b), g(a),g(b),f(f(a), f(f(b), g(f(a),g(f(b), f(g(a), f(g(b), g(g(a),g(g(b).共二百二十二頁(yè)例3.2求子句(z j)集S=P(x),Q

37、(y) R(y)的H域。解：該子句集中既無(wú)個(gè)體常量，又無(wú)函數(shù)，所以可任意指定一個(gè)常量a作為個(gè)體常量，從而(cng r)得到：H0=H1=H =a對(duì)于沒(méi)有變量符號(hào)出現(xiàn)的項(xiàng)、項(xiàng)集、原子、原子集合、文字、子句和子句集，分別稱(chēng)之為基項(xiàng)、基項(xiàng)集、基原子、基原子集合、基文字、基子句和基子句集。關(guān)于原子集的定義：設(shè)S是子句集。集合A=所有形如P(t1,tn)的元素稱(chēng)作子句集S的原子集。其中P(t1,tn)是出現(xiàn)于S中的任一謂詞符號(hào)，而t1,tn是S的H域的任意元素。例3.2中 S的原子集為 A=P(a),Q(a),R(a)例 3.3S=P(x) Q(x),R(f(y)根據(jù)定義有：H=a,f(a),f(f(a

38、),A=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),P(f(f(a), Q (f(f(a),R (f(f(a),.共二百二十二頁(yè) 關(guān)于基例的定義：將S中的某子句C中所有變量符號(hào)(fho)均以S的H域的元素代入時(shí)，所得的基子句C稱(chēng)作C的一個(gè)基例。例：S=P(x),Q(f(y) R(y)有：H=a,f(a),f(f(a),P(a),P(f(a)都稱(chēng)作(chn zu)子句C=P(x)的基例；Q(f(a) R(a),Q(f(f(a) R(f(a)都是Q(f(y) R(y)的基例。關(guān)于海伯倫解釋的定義：設(shè)S是子句集，H是S的海伯倫域，I是S在H上的一個(gè)解釋。稱(chēng)I為S的一個(gè)H解

39、釋?zhuān)绻麧M(mǎn)足如下條件：（1）I映射S中的所有常量符號(hào)到自身；（2）若f是S中n元函數(shù)符號(hào)，h1,hn是H中元素，則I指定映射：（ h1,hn ） f(h1,hn)共二百二十二頁(yè)設(shè)A=A1,A2,An是S的原子集。于是S的一個(gè)解釋I可以方便(fngbin)地表示為如下一個(gè)集合：I=m1,m2,m nMi =Ai當(dāng)Ai被I指定為T(mén)Ai當(dāng)Ai被指定為Fi=1,2,n例3.4S=P(x)Q(x),R(f(y) 于是(ysh)：S的H域=a,f(a),f(f(a),.S的原子集：A=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),P(f(f(a),.S的H解釋為：I1=P(a),

40、Q(a),R(a),P(f(a),Q(f(a),R(f(a),P(f(f(a),.I2=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),P(f(f(a),.I3=P(a),Q(a),R(a),P(f(a),Q(f(a),R(f(a),P(f(f(a),.共二百二十二頁(yè)3.1.2 海伯倫解釋與普通(ptng)解釋的關(guān)系子句集S的一個(gè)解釋?zhuān)皇潜仨?bx)定義在H域上，即使定義在H域上，也不一定是一個(gè)H解釋。D=1,2a/2f(1,1)/1f(1,2)/2f(2,1)/2f(2,2)/1P(1)/TP(2)/FQ(1,1)/F Q(1,2)/T Q(2,1)/F Q(2,2

41、)/T依照I可以構(gòu)造S的一個(gè)解釋I*,使得若S在I下為真則S在I*下也為真。首先找出S的原子集：A=P(a),Q(a,a),P(f(a,a),Q(a,f(a,a),Q(f(a,a),a),Q(f(a,a),f(a,a),.其次，對(duì)A中每一個(gè)成員，用解釋I進(jìn)行估值：P(a)=P(2)=FQ(a,a)=Q(2,2)=TP(f(a,a)=P(f(2,2)=P(1)=TQ(a,f(a,a)=Q(2,f(2,2)=Q(2,1)=FQ(f(a,a),a)=Q(f(2,2),2)=Q(1,2)=TQ(f(a,a),f(a,a)=Q(f(2,2),f(2,2)=F.I*=P(a),Q(a,a),P(f(a,a

42、),Q(a,f(a,a),Q(f(a,a),a),Q(f(a,a),f(a,a),.于是，可以構(gòu)造S的H解釋例3.5 有子句集 S=P(x),Q(y,f(y,a)指定S的一個(gè)解釋I（普通解釋?zhuān)┤缦拢汗捕俣?yè)如果子句(z j)集S中沒(méi)有常量符號(hào)，則將S的H域中初始元素a映射到D中任一元素，依照上例的方法，也可以構(gòu)造S的一個(gè)H解釋I*，使得若I滿(mǎn)足S，則I*也滿(mǎn)足S。例3.6S=P(x),Q(y,f(y,z)令S的一個(gè)(y )解釋I如下：D=1,2 f(1,1)/1 f(1,2)/2 f(2,1)/2 f(2,2)/2P(1)/T P(2)/F Q(1,1)/F Q(1,2)/T Q(2,1

43、)/F Q(2,2)/T指定a對(duì)應(yīng)1得H解釋:I1* =P(a),Q(1,1),P(f(a,a),Q(a,f(a,a),Q(f(a,a),a),Q(f(a,a),f(a,a),.指定a對(duì)應(yīng)2得H解釋:I2* =P(a), Q(1,1),P(f(a,a), Q(a,f(a,a), Q(f(a,a),a), Q(f(a,a),f(a,a),.以上根據(jù)解釋I構(gòu)造的S的H解釋I*，稱(chēng)為對(duì)應(yīng)與I的H解釋。共二百二十二頁(yè)定義(dngy)：設(shè)I是子句集S在區(qū)域D上的解釋?zhuān)侨缦逻f歸定義的H到D的映射：1.若S中有常量符號(hào)，則H0是出現(xiàn)在S中的所有常量符號(hào)的集合。于是對(duì)任意(rny)a H0, a表示a在I下

44、的映象。 若S中無(wú)常量符號(hào)，則H0=a。于是a可以是D中隨便哪個(gè)元素。2.對(duì)任意(h1,hn) Hin，及S中的任意n元函數(shù)符號(hào)f(x1,xn)，令(f (h1,hn) ) 是(h1,hn)在I下的H解釋I *有如下規(guī)定。 若(h1,hn) =Hn，P (x1,xn)是n元函數(shù)符號(hào)，則規(guī)定T1*(P (h1,hn) )=T1(P (h1,hn)其中T1(P (h1,hn) 表示P (h1,hn)在I下的真值，T1*(P (h1,hn) )表示P (h1,hn)在I*下的真值。引理如果某區(qū)域D上的解釋I滿(mǎn)足子句集S.則對(duì)應(yīng)于I的任意一個(gè)H解釋I*也滿(mǎn)足S。定理子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)S被所

45、有的H解釋弄假。共二百二十二頁(yè)3.2 海伯倫定理(dngl) 要證明子句集S是不可滿(mǎn)足的，只需要考慮在H域上的所有H解釋即可。但是所有的H解釋也是無(wú)限的。海伯倫定理就是用語(yǔ)義樹(shù)的方法，把需要考慮無(wú)窮個(gè)H解釋的問(wèn)題(wnt)，變成只考慮有限個(gè)解釋的問(wèn)題(wnt)。3.2.1 語(yǔ)義樹(shù)（解釋樹(shù)）設(shè)子句集S的原子集A=P,Q,RN38N37N36N34N35N33N32N31N24N23N22N21N12N11N0RQPPQQQRRRRRRR語(yǔ)義樹(shù)：通常以I(N)表示從根結(jié)點(diǎn)N0到到葉結(jié)點(diǎn)分枝上所標(biāo)記文字的并集。如：I(N36)=P,Q,R共二百二十二頁(yè)3.2.2 海伯倫定理(dngl)定理(dngl

46、)（海伯倫定理(dngl)1）子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義樹(shù)是一棵有限的封閉語(yǔ)義樹(shù)。定理（海伯倫定理2）子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)存在S的一個(gè)有限不可滿(mǎn)足的基例集S。 對(duì)一階謂詞描述下的A1A2A3B的證明問(wèn)題，對(duì)此已經(jīng)作了足夠的準(zhǔn)備。首先將這個(gè)問(wèn)題化成G= A1A2A3B的不可滿(mǎn)足問(wèn)題，進(jìn)而將G化成Skolem標(biāo)準(zhǔn)型，并建立相應(yīng)的子句集S，再將一般論域D上的討論簡(jiǎn)化成H域上的討論，最后引入語(yǔ)義樹(shù)。共二百二十二頁(yè)3.3 替換(t hun)與合一算法3.3.1 替換與最一般(ybn)合一替換一個(gè)替換是型如t1/v1 ,t n/vn 的一個(gè)有限集其中vi是變量，而ti是不同

47、于vi 的項(xiàng)（常量、變量、函數(shù)），且vi vj (i j ) ，i,j=1,2,n。稱(chēng)為ti替換分子， vi為替換分母。當(dāng)t1,tn是基項(xiàng)時(shí)，稱(chēng)此替換為基替換。不含任何元素的替換為空替換，以表示。例如a/x,b/y,f(x)/z就是一個(gè)替換。替換可作用與某個(gè)謂詞公式上，也可作用于某個(gè)項(xiàng)上。令替換= t1/v1 ,t n/vn ，作用于E，而E是一謂詞公式。就是將E中出現(xiàn)的vi均以ti代入(i=1,2,n), 作用的結(jié)果用E表示，并稱(chēng)E為E的一個(gè)例。若t是項(xiàng)， 作用于項(xiàng)t也是將t中出現(xiàn)的vi均以ti代入，作用的結(jié)果用t表示。共二百二十二頁(yè)例3.7令= a/x,f(b)/y,c/z E=P(x,y

48、,z)t=g(x,y)于是(ysh)E的例為 E =P(a,f(b),c) 而 t=g(a,f(b)當(dāng)E是子句集S的一個(gè)子句，用作用(zuyng)于E，當(dāng)中的v1,vn含有E的所有變量， t1,tn又是H的元素時(shí)， E 便是S的子句E的基例。例3.8子句集S=P(x,y),Q(x,a) R(y,b)此子句集的H域：H=a,bP(x,y)是S的一個(gè)子句，以= a/x,b/y作用于P(x,y)，得到P(a,b)。P(a,b)就是S子句P(x,y)的基例。共二百二十二頁(yè)定義：設(shè)= t1/x1 ,t n/xn， =u1/y1 ,u m/vm是兩個(gè)(lin )替換。將下面集合t1 /x1 ,t n /x

49、n，u1/y1 ,u m/vm中符合下面條件的元素(yun s)刪除1. ui/yi ，當(dāng) yi x1,x n時(shí)；2. ti /xi ，當(dāng)ti =xi 時(shí)。如此得到一個(gè)替換，稱(chēng)為與的乘積，記作例3.9令=f(y)/x,z/y =a/x,b/y,y/z解：先作替換f(y) /x,z/y,a/x,b/y,y/z = f(b)/x,y/y,a/x,b/y,y/z其中a/x,b/y符合條件1，應(yīng)刪除。y/y符合條件2，也應(yīng)刪除，所以得：= f(b)/x,y/z當(dāng)子句 E=P(x,y,z)時(shí)E() =P(f(b),y,y)如果先用作用于E,則E=P(f(y),z,z)再用作用于E得(E) = P(f(b

50、),y,y)與用= f(b)/x,y/z直接作用于E的結(jié)果一樣。即：E() = (E) 求： 共二百二十二頁(yè)引理設(shè)，是三個(gè)替換(t hun)，于是： ()= ()設(shè)E是任一表達(dá)式E() ) =(E() ) =( (E) E( ) =(E)()=( (E) 所以(suy) E() ) = E( ) 由于E的任意性，故 ()= () 注意，在，中，交換律是不成立的。共二百二十二頁(yè) 為了在兩個(gè)中找出互補(bǔ)文字，常常需要去統(tǒng)一兩個(gè)或多個(gè)(du )表達(dá)式。即需要找一個(gè)替換，使得在此替換下，一些本來(lái)不同的表達(dá)式會(huì)一致起來(lái)。定義 替換稱(chēng)為表達(dá)式集合E1,E k的合一(h y)，當(dāng)且僅當(dāng)E1 = E2 =.=

51、Ek 。表達(dá)式集合E1,E k稱(chēng)為可合一的，如果存在關(guān)于此集合的一個(gè)合一。定義 表達(dá)式集合E1,E k的合一稱(chēng)為是最一般合一（most general unifier）記作mgu，當(dāng)且僅當(dāng)對(duì)此集合的每一個(gè)合一，都存在替換，使得= 。例3.10表達(dá)式集合P(a,y),P(x,f(b)是可合一的，其合一為：=a/x,f(b)/y例3.11表達(dá)式集合P(x),P(f(y)是可合一的,其最一般合一為：=f(y)/x因?yàn)閷?duì)此表達(dá)式集合的任一合一=f(a)/x, a/y 都有替換=a/y，使= =f(a)/x, a/y共二百二十二頁(yè)3.3.2 合一(h y)算法定義 設(shè)W是非空表達(dá)式集合，W的差異集合是如

52、下一個(gè)集合：首先找出W的所有(suyu)表達(dá)式中不相同的第一個(gè)符號(hào)，然后從W的每個(gè)表達(dá)式中抽出占有這個(gè)位置的子表達(dá)式。所有這些子表達(dá)式的集合就是W 的差異集合。例3.12求表達(dá)式集合W=P(x,f(x,z),z),P(x,a),P(x,g(h(k(x),z)的差異集合解： 從P(x,f(x,z),z)中抽出f(x,z) 從P(x,a)中抽出a 從P(x,g(h(k(x),z)中抽出g(h(k(x)得到W的差異集合=f(x,z),a,g(h(k(x)。若W是非空表達(dá)式集合，D是W的差異集合，則有下面的結(jié)論：1.若D中無(wú)變量符號(hào)，則W是不可合一的，例如W=P(f(x),P(g(x)D=f(x),g

53、(x)只有函數(shù)符號(hào)2.若D中只有一個(gè)元素，則W是不可合一的，例如W=P(x),P(x,y) D=y3.若D中有變量符號(hào)x和項(xiàng)t，且x出現(xiàn)在t中，則W是不可合一的，例如W=P(x),P(f(x) D=x,f(x)x出現(xiàn)在項(xiàng)f(x)中共二百二十二頁(yè)最一般合一(h y)算法（mgu算法）：步驟(bzhu)1：令W=E1,E2步驟2：令k=0, Wk=W, k=步驟3：如果Wk只有一個(gè)元素，則停止， k是W的最一般合一；否則，找出Wk的差異集合Dk。步驟4：若D k中存在元素vk、t k，其中vk是變量符號(hào)，并且不出現(xiàn)在t k中，則轉(zhuǎn)到步驟5；否則，W是不可合一的，算法停止。步驟5：令k+1= k t

54、 k /vk， Wk+1=Wk+1 步驟6：K+1K,轉(zhuǎn)到步驟3。若E1,E2可合一，算法必停于步驟3。共二百二十二頁(yè)例3.13有公式(gngsh)E1=P(a,x,f(g(y) , E2=P(z,f(a),f(u) 求E1,E2的最一般合一mgu。解：根據(jù)(gnj)算法1.W=E1 , E2=P(a,x,f(g(y) , P(z,f(a),f(u) 2.W0=W, 0= 3. W0未合一，找出W0的差異集合D0=a,z4.取v0=z，t0=a5.令1= 0t0 /v0=a/zW1= W0 1 =P(a,x,f(g(y) , P(a,f(a),f(u) 3. W1未合一，找出W1的差異集合D1

55、=x,f(a)4.取v1=x，t1=f(a)5.令2= 1t1 /v1=a/z,f(a)/xW2= W12 =P(a,f(a),f(g(y) , P(a,f(a),f(u) 3. W2未合一，找出W1的差異集合D2=g(y),u4.取v2=u，t2=g(y)5.令3= 2t2 /v2=a/z,f(a)/x,g(y)/u W3= W23=P(a,f(a),f(g(y) , P(a,f(a),f(g(y) 3. W3已合一，此時(shí)3= a/z,f(a)/x,g(y)/u 是E1,E2的最一般合一mgu。共二百二十二頁(yè)例3.14有公式E1=Q(f(a),g(x) , E2=Q(y,y) 求E1,E2的

56、最一般(ybn)合一mgu。解：根據(jù)(gnj)算法1.令W=E1 , E2=Q(f(a),g(x) , Q(y,y)2.W0=W, 0= 3. W0未合一，找出W0的差異集合D0=f(a),y4.取v0=y，t0=f(a)5.令1= 0t0 /v0=f(a)/yW1= W0 1 =Q(f(a),g(x) , Q(f(a),f(a)3. W1未合一，找出W1的差異集合D1=g(x),f(a)4. D1中無(wú)變量符號(hào)，算法停止，W不可合一。共二百二十二頁(yè)3.4 歸結(jié)(guji)原理 歸結(jié)原理也稱(chēng)消解原理，它可直接應(yīng)用到任意子句集S上，去檢驗(yàn)S的不可(bk)滿(mǎn)足性。 歸結(jié)原理的本質(zhì)思想是去檢查子句集S

57、是否包含一個(gè)空子句，如果S包含，則S是不可滿(mǎn)足的。如果S不包含，則去檢查是否可由S推導(dǎo)出來(lái)。當(dāng)然這個(gè)推理規(guī)則必須保證推出的子句是原親本子句的邏輯結(jié)果。歸結(jié)原理就是這樣一種推理規(guī)則。共二百二十二頁(yè)3.4.1 命題邏輯中的歸結(jié)(guji)原理 定義：設(shè)C1與C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2,并將兩個(gè)子句中的余下部分析取，構(gòu)成一個(gè)新的子句C12，則稱(chēng)這一過(guò)程(guchng)為歸結(jié)。稱(chēng)C12是C1和C2的歸結(jié)式。稱(chēng)C1和C2是C12的親本子句。例3.15設(shè)C1=PQRC2=Q S可見(jiàn)C1中的文字L1=Q與C2中的文字L2=Q

58、互補(bǔ)。因此可通過(guò)歸結(jié)得：C12=PR S例3.16設(shè) C1=P， C2=P文字P與文字P互補(bǔ)，通過(guò)歸結(jié)可得：C12= 例3.17設(shè)C1=PQC2=Q R C3=P首先對(duì)C1，C2進(jìn)行歸結(jié)，得到 C12=PR 再對(duì)C12，C3進(jìn)行歸結(jié)，得 C123=R 共二百二十二頁(yè)定理：歸結(jié)式C12是其親本子句(z j)C1和C2的邏輯結(jié)論。證明 設(shè)C1=LC1， C2=LC2，通過(guò)(tnggu)歸結(jié)可得到C12=C1C2C1和C2是C12的親本子句。 C1L= C1LL C2 =LC2 C1C2 = ( C1L) (LC2 )由假言三段論得到：( C1L) (LC2 ) ( C1C2 ) C1C2= C1C

59、2 = C12 C1C2 C12共二百二十二頁(yè)由以上定理可得到如下兩個(gè)(lin )推論： 1.設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若用C12代替C1和C2后得到新子句集S1，則由S1的不可(bk)滿(mǎn)足性可推出原子句集S的不可滿(mǎn)足性。即：S1不可滿(mǎn)足S不可滿(mǎn)足 2.設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若把C12加入到S中，得到新子句集S2，則S與S2在不可滿(mǎn)足的意義上是等價(jià)的。即： S2不可滿(mǎn)足=S不可滿(mǎn)足 為了證明子句集S的不可滿(mǎn)足，只要對(duì)S中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入子句集S，或用歸結(jié)式代替它的親本子句，然后證明新子句集不可滿(mǎn)足就可以

60、了。如果經(jīng)過(guò)歸結(jié)能得到空子句，根據(jù)空子句的不可滿(mǎn)足性，立即得到原子句集不可滿(mǎn)足的結(jié)論。 在命題邏輯中，對(duì)不可滿(mǎn)足的子句集S，歸結(jié)原理是完備的。這就是說(shuō)：若子句集S不可滿(mǎn)足，則必然存在一個(gè)從S到空子句的歸結(jié)演繹；若存在一個(gè)從S到空子句的歸結(jié)演繹，則S一定是不可滿(mǎn)足的。 對(duì)于可滿(mǎn)足的子句集S，用歸結(jié)原理得不到任何結(jié)論。共二百二十二頁(yè)3.4.2 謂詞邏輯(lu j)中的歸結(jié)原理 在謂詞邏輯中，由于子句中含有變?cè)圆荒苤苯酉セパa(bǔ)文字(wnz)，需要用最一般合一對(duì)變?cè)M(jìn)行代換，然后才能進(jìn)行歸結(jié)。例如：有子句 C1=P(x)Q(x) C2=P(a)R(y)C1的P(x)與C2的P(a)不同，所以不能