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

1、第1章 人工智能綜述,第2章 數(shù)理邏輯基礎(chǔ),第3章 歸結(jié)推理方法,第4章 用于人工智能的Prolog語(yǔ)言,第5章 知識(shí)表示,第6章 產(chǎn)生式系統(tǒng)的搜索策略,第7章 專家系統(tǒng),第8章 知識(shí)獲取與機(jī)器學(xué)習(xí),THE END,第1章 人工智能綜述,本章主要內(nèi)容：,智能與人工智能,人工智能發(fā)展的歷史回顧,人工智能的研究目標(biāo)與研究途徑,人工智能的研究領(lǐng)域,,1.1 智能與人工智能,關(guān)于智能的幾種解釋：

2、智能是人們處理事物、解決問(wèn)題時(shí)表現(xiàn)出來(lái)的智慧和能力。智能是知識(shí)和智力的總和。,目前尚不能給智能一個(gè)確切的定義。,智能所具有的一些基本特征：,記憶與思維能力,感知能力,自適應(yīng)能力,表達(dá)能力,自學(xué)習(xí)能力,,有關(guān)人工智能的幾種說(shuō)明：,智能機(jī)器：能夠在各類環(huán)境中自主地或交互地執(zhí)行各種擬人的機(jī)器,人工智能（學(xué)科）：是計(jì)算機(jī)科學(xué)中涉及研究、設(shè)計(jì)和應(yīng)用智能機(jī)器的一個(gè)分支。,人工智能（能力）：是智能機(jī)器所執(zhí)行的與人類智能有關(guān)的功能，如判斷、推理、證

3、明、識(shí)別、感知、理解、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問(wèn)題求解等思維活動(dòng)。,簡(jiǎn)單地講，人工智能是關(guān)于： 機(jī)器智能和智能機(jī)器的研究,,人工智能是工程技術(shù)學(xué)科，同時(shí)也是理論研究學(xué)科。,作為工程技術(shù)學(xué)科，人工智能的目的是：提出建造人工智能系統(tǒng)的新技術(shù)、新方法和新理論，并在此基礎(chǔ)上研制出具有只能行為的計(jì)算機(jī)系統(tǒng)。,作為理論研究學(xué)科，人工智能的目的是：提出能夠描述和解釋智能行為的概念與理論，為建造人工智能系統(tǒng)提供理論依據(jù)。,,長(zhǎng)期以來(lái)，圍繞人工智能有很

4、多爭(zhēng)議。“機(jī)器是否能思考？”這一問(wèn)題吸引了許多哲學(xué)家、科學(xué)家和工程師。,計(jì)算機(jī)科學(xué)的創(chuàng)始人之一，艾侖?圖靈(Alan Turing)談到這一問(wèn)題：,Alan Turing,Alan Turing指出：“機(jī)器是否能思考”這一問(wèn)題的答案取決與人們?nèi)绾味x“機(jī)器”和“思考”。也許還可以指出，這一問(wèn)題還取決于如何定義“能”。,,先考慮“機(jī)器”這一詞。,再看看“思考”這個(gè)詞。,1.2 人工智能發(fā)展的歷史回顧,20世紀(jì)30年代和40年代：,20世紀(jì)

5、50年代：,John McCarthy,數(shù)學(xué)邏輯和關(guān)于計(jì)算的新思想,第一次人工智能討論會(huì),20世紀(jì)60年代：,第一屆國(guó)際人工智能聯(lián)合會(huì)議,20世紀(jì)70年代：,《人工智能》國(guó)際雜志創(chuàng)刊,20世紀(jì)80年代：,專家系統(tǒng)和知識(shí)工程在全世界迅速發(fā)展,國(guó)外的發(fā)展情況,,國(guó)內(nèi)的發(fā)展情況,1978年,國(guó)家“智能模擬”研究計(jì)劃,1984年,召開(kāi)智能計(jì)算機(jī)及系統(tǒng)全國(guó)學(xué)術(shù)討論會(huì),把智能計(jì)算機(jī)系統(tǒng)、智能機(jī)器人和智能信息處理列入國(guó)家高技術(shù)研究計(jì)劃。,1986年,

6、1989年,首次召開(kāi)中國(guó)人工智能聯(lián)合會(huì)議,1987年,《模式識(shí)別與人工智能》雜志創(chuàng)刊,1993年,智能控制和智能自動(dòng)化被列入國(guó)家科技攀登計(jì)劃,1997年,由本人編寫的《人工智能原理及應(yīng)用》出版,,,1.3 人工智能的研究目標(biāo)與研究途徑,研究目標(biāo)分為近期目標(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é)派叫

7、做連接主義(Connectionism),主張用計(jì)算機(jī)科學(xué)的方法進(jìn)行研究------產(chǎn)生出一大學(xué)派叫做符號(hào)主義(Symbolism),,Agent一詞的兩種解釋：一是，對(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í),就稱其為Agent"。 軟件界的研究人員

8、傾向于第二種解釋：代理人。Agent是計(jì)算機(jī)軟件，代表用戶，以主動(dòng)服務(wù)方式完成一定操作的計(jì)算實(shí)體。Agent是具有信息處理能力的主動(dòng)實(shí)體，其結(jié)構(gòu)包含下述模塊：感知器、效應(yīng)器、信息處理器、目標(biāo)模塊、通信機(jī)制。,僅代理用戶某種任務(wù)的軟件不能稱為智能Agent。智能性，如理解用戶用自然語(yǔ)言表達(dá)的對(duì)信息資源和計(jì)算資源的需求，幫助用戶在一定程度上克服信息內(nèi)容的語(yǔ)言障礙，捕捉用戶的偏好和興趣，推測(cè)用戶的意圖并為其代勞等。只有代理性、智能性、自主性均

9、達(dá)到相當(dāng)水準(zhǔn)的系統(tǒng)才有條件稱為智能Agent。 比爾?蓋茨把智能Agent稱為“軟的軟件”，他說(shuō)：“一旦程序?qū)懞昧?，它就一成不變。軟的軟件隨著你的使用好象會(huì)變得越來(lái)越聰明”，“你可以把Agent當(dāng)作直接內(nèi)置在軟件中的合作者，它會(huì)記住你擅長(zhǎng)什么，你過(guò)去做過(guò)些什么，并試著預(yù)測(cè)難題，并提出解決辦法”。,,,1.4 人工智能的研究領(lǐng)域,專家系統(tǒng)與知識(shí)工程,自動(dòng)定理證明與自動(dòng)推理,機(jī)器學(xué)習(xí),自然語(yǔ)言理解,智能管理系統(tǒng),自動(dòng)程序設(shè)計(jì),感

10、知系統(tǒng),智能機(jī)器人,專家系統(tǒng)是一個(gè)智能計(jì)算機(jī)程序系統(tǒng)。其內(nèi)部具有大量專家水平的知識(shí)和經(jīng)驗(yàn)，能夠利用人類專家的知識(shí)和解決問(wèn)題的方法來(lái)解決該領(lǐng)域的問(wèn)題。也就是說(shuō)，專家系統(tǒng)是一個(gè)具有大量知識(shí)與經(jīng)驗(yàn)的程序系統(tǒng)。它應(yīng)用人工智能技術(shù)，根據(jù)某個(gè)領(lǐng)域一個(gè)或多個(gè)人類專家提供的知識(shí)和經(jīng)驗(yàn)進(jìn)行推理和判斷，模擬人類專家的決策過(guò)程，以解決那些需要專家決定的復(fù)雜問(wèn)題。,,自動(dòng)定理證明是人工智能最早得到應(yīng)用的領(lǐng)域。對(duì)于一個(gè)數(shù)學(xué)定理，給出嚴(yán)格的數(shù)學(xué)證明，是一項(xiàng)高智能的

11、工作。不僅需要很強(qiáng)的推理能力，而且需要人們有著深刻的洞察力，能預(yù)見(jiàn)出在證明主要定理之前，應(yīng)先證明哪些引理，作好必要的準(zhǔn)備，最后證明主要定理。,,機(jī)器學(xué)習(xí)領(lǐng)域的研究工作主要從三個(gè)方面進(jìn)行：一是面向任務(wù)的研究，研究和分析改進(jìn)一組預(yù)定任務(wù)的執(zhí)行性能的學(xué)習(xí)系統(tǒng)；二是認(rèn)識(shí)模擬，研究人類學(xué)習(xí)過(guò)程并進(jìn)行計(jì)算機(jī)模擬；三是理論性分析，從理論上探索各種可能的學(xué)習(xí)方法和獨(dú)立于應(yīng)用領(lǐng)域的算法。,,,自然語(yǔ)言理解就是研究如何讓機(jī)器理解人類的自然語(yǔ)言。機(jī)器翻譯也屬

12、于自然語(yǔ)言理解的范疇，它是研究把一種語(yǔ)言自動(dòng)的翻譯成另一種語(yǔ)言。自然語(yǔ)言理解這一課題雖然困難，但對(duì)人工智能的發(fā)展卻起著重要的作用。,智能管理是人工智能在管理領(lǐng)域中的應(yīng)用，發(fā)展了“智能管理”新技術(shù)和新一代的計(jì)算機(jī)管理系統(tǒng) “智能管理系統(tǒng)”，如：智能管理信息系統(tǒng)（IMIS Intelligent Management Information System）、智能辦公自動(dòng)化系統(tǒng)（IOAS Intelligent Office Automati

13、on 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)化的管理決策提供信息服務(wù)和決策支持；而且具有更全面的管理功能，可同時(shí)具備信息管理、事務(wù)處理、決策支持等多種功能。,,,自動(dòng)程序設(shè)計(jì)：

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

15、量詞,謂詞公式及其解釋,謂詞公式的標(biāo)準(zhǔn)形式,謂詞公式的等價(jià)與蘊(yùn)涵,2.1 命題邏輯,一個(gè)命題是一個(gè)或真或假不能兩者都是的斷言。,斷言是指一陳述語(yǔ)句。,簡(jiǎn)單地說(shuō)，命題是指一句有真假意義的陳述句。,命題為真，記為 T 命題為假，記為 F,命題變?cè)?P, Q, R…表示；,一個(gè)命題P如果是真值未指定任意命題，稱P為命題變?cè)?如果P是一個(gè)真值已經(jīng)指定的命題，稱為命題常元。,命題常元只有 T 和 F。,,2.1.l 命題聯(lián)結(jié)

16、詞（邏輯聯(lián)結(jié)詞、邏輯運(yùn)算符）,復(fù)合命題：?jiǎn)蝹€(gè)命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)構(gòu)成的新命題。,常用的5種聯(lián)結(jié)詞：,復(fù)合命題與原命題的真值關(guān)系,2.1.2 命題公式及其解釋,原子公式：?jiǎn)蝹€(gè)命題變?cè)?、單個(gè)命題常元稱為原子公式。,命題公式：由如下規(guī)則生成的公式稱為命題公式：1. 單個(gè)原子公式是命題公式。2. 若A ,B是命題公式，則~A , A?B , A?B , A ?B , A ? B是公式。3. 所有命題公式都是有限次應(yīng)用1、2得到的符號(hào)串。,命

17、題公式的解釋：給命題公式中的每一個(gè)命題變?cè)付ㄒ粋€(gè)真假值， 這一組真假值，就是命題公式的一個(gè)解釋。用I表示。,例如：公式G= (A?B) ?C 的一個(gè)解釋是：,I1(G) = A/T, B/F, C/T,在解釋I1(G)下G為真。,永真公式與永假公式：如果公式在它所有的解釋I下，其值都為T，則稱公式G為恒真的；如果其值都為F，則稱公式G為恒假的（不可滿足的）。,注意：關(guān)于五個(gè)聯(lián)結(jié)詞的約定：* 結(jié)合力的強(qiáng)弱順序： &

18、#172;， ?， ?， ?， ?* 聯(lián)結(jié)詞相同時(shí)，從左至右運(yùn)算。解釋的個(gè)數(shù)：如果一個(gè)公式G中有n個(gè)不同的原子公式（或簡(jiǎn)稱原子），則G有2n個(gè)不同的解釋，于是G在2n個(gè)解釋下有2n個(gè)真值。如果將這些真值和它們的解釋列成表，就是G的真值表。,2.1.3 等價(jià)命題公式,如果兩個(gè)命題公式所含原子公式相同，且在任一解釋下，兩個(gè)命題公式的值相同，則稱這兩個(gè)命題公式為等價(jià)命題公式或等價(jià)公式。,常用的等價(jià)公式有：,1. (P ? Q)=

19、 (P ? Q) ? (Q ? P),2.(P ? Q)=(¬P ? Q),3. ¬(¬P)= P4.交換律：P ? Q=Q ? P P ? Q=Q ? P,5.結(jié)合律：P ?(Q ? R)=(P ? Q) ? R P ? (Q ? R)=(P ? Q) ?R,6.分配律：P ?(Q ?R)=(P ? Q) ? (P ? R) P ? (Q ? R)=(P ?Q) ? (

20、P ?R),7.泛界律：P ? F=P ,P ? T=P P ? F=F ,P ? T=T,8.互余律：P ? ~P=T,P ? ~P=F,9.德 ? 摩根定律：~(P ? Q)=~P ? ~Q ~(P ? Q)=~P ? ~Q,證明兩個(gè)公式等價(jià)，可用真值表，也可用基本公式。,例如 要證明公式 P ? Q=~Q ? ~P,[證] P ? Q =~ P ? Q,=~ P ?~ (~ Q ),=~(~Q) ?

21、~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,2.1.4 永真蘊(yùn)涵式,若命題公式G ? H是恒真的，稱其為永真蘊(yùn)涵式。記為G?H，讀做“G蘊(yùn)涵H”，也稱“G是H的邏輯結(jié)果”。,常用的永

22、真蘊(yùn)涵式：1. P ? P ? Q,[證]P ? P ? Q = ~P ? (P ?Q),= ~P ? P ?Q,= T ? Q = T,2. P ? Q ? P,[證]P ? Q ? P =~(P ? Q) ? P,= ~P ? ~Q ?P,=T ?~Q= T,3. P ? (P ? Q) ? Q,4.( P ? Q) ? ~Q ? ~P,5. ~P ?(P ? Q) ? Q,6.(P ? Q) ?(Q ? R) ? (P ?

23、 R),7.( P ? Q) ?( (Q ? R) ?( P ? R)),8.((P ? Q) ?( R ? S)) ? (P ? R ? Q ? S),9.(( P ? Q) ?( Q ? R)) ?( P ? R),公式的標(biāo)準(zhǔn)形式：范式,析取范式 (disjunctive normal form,DNF) ：一個(gè)由原子和原子的非組成的析取式，如果與給定的命題公式A等價(jià)，則稱它是A的析取范式。記作：,A=A1 ? A2 ?... ?

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

25、 2. 一個(gè)公式的析取范式和合取范式都不是唯一的； 3. 運(yùn)算符最少的范式稱為最簡(jiǎn)范式。,,2.2 謂詞與量詞,在命題演算中，基本元素是原子命題，而不考慮命題的內(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 不是恒真的。如：

26、取解釋:I=P/T,Q/T,R/F 則公式為假值F. 就是說(shuō)解釋I 弄假了此公式。,為準(zhǔn)確表達(dá)此類公式，必須引進(jìn)謂詞和量詞的概念。,2.2.1謂詞,先看幾個(gè)命題：,1. 3是質(zhì)數(shù)2. 王二生于武漢市3. 7=2?3,x是質(zhì)數(shù)x生于武漢市x=y ? z,F(x)G(x,y)H(x,y,z),稱“3”、“王二”、“武漢市”、“7”、“2”、“3”為個(gè)體;,代表個(gè)體的變?cè)Q為個(gè)體變?cè)?刻畫個(gè)體性質(zhì)或個(gè)

27、體之間關(guān)系的詞叫謂詞。,“是質(zhì)數(shù)”、“生于”、“…=... ?...”都是謂詞。,2.2.2 量詞,量詞分為全稱量詞和存在量詞。,符號(hào)“?”表示全稱量詞。符號(hào)“?”表示存在量詞。,?x讀作“對(duì)一切x”,或“對(duì)每一x”，或“對(duì)任一x”。x是?所作用的個(gè)體變?cè)?? x讀作“存在一個(gè)x”,或“對(duì)某些x”，或“至少有一x”。x是?所作用的個(gè)體變?cè)?再看前面的三段論法：,P:“所有的人都會(huì)犯錯(cuò)誤”Q:“張三是人”R:“張三會(huì)犯錯(cuò)誤”,?x

28、(M(x) ?R(x))M(“張三”)R(“張三”),在謂詞前加上?x,叫做變?cè)蝗Q量化；在謂詞前加上? x,叫做變?cè)淮嬖诹炕?。量化的目的是約束變?cè)?2.2.3 約束變?cè)?、自由變?cè)?、改名?guī)則,量詞的轄域約束出現(xiàn)自由出現(xiàn),改名規(guī)則：在同一公式中，一個(gè)變?cè)纫约s束出現(xiàn)，有以自由出現(xiàn)。就需要對(duì)變?cè)拿８拿?guī)則是：,1. 變?cè)粢拿?，則該變?cè)诹吭~及其轄域中的所有出現(xiàn)均須一起更改，其余部分不變；2. 變?cè)拿麜r(shí)所選用的

29、符號(hào)，必須是量詞轄域內(nèi)未出現(xiàn)的符號(hào)。一般還應(yīng)是公式中未出現(xiàn)的符號(hào)。,,2.3 謂詞公式及其解釋,在定義謂詞公式前,先介紹“符號(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

30、(x1,…, xn)是n元謂詞符號(hào)， t1,…, tn 是項(xiàng)， 則P(t1,…, tn),謂詞公式（公式）的定義：,1. 原子公式是公式；2. 若H,G是公式，則~H , H ? G , H ?G , H ?G , H ? G是公式；3. 若G是公式，x是G中的自由變?cè)瑒t?xG ? xG是公式；4. 所有公式都是有限次應(yīng)用1、2、3得到的符號(hào)串。,解釋的定義：,公式G的一個(gè)解釋I，是由非空集D和下列對(duì)G中常元符號(hào)、函數(shù)符號(hào)、謂詞

31、符號(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è)映射。,[例2.1]給以下公式指定一個(gè)解釋：,1. ? x P(f(x)) ? Q(x,f(a))2. ?x(P(x) ? Q(x,a)),可指定如下解釋I：D={1,2}a/1f(1)/2 f(2)/1P(1)/FP(2)/T

32、Q(1,1)/T Q(1,2)/T Q(2,1)/FQ(2,2)/T在此解釋I下，公式? x P(f(x)) ? Q(x,f(a))為T值。,而公式?x(P(x) ? Q(x,a))在此解釋下為F值。,如果存在I使G為T值，則稱G可滿足，簡(jiǎn)稱I滿足G;若I使G為F值，稱I不滿足G，或稱I弄假G。,如果不存在解釋I滿足公式G，公式G成為不可滿足的。如果公式G的所有解釋I都滿足G,公式G稱為恒真的。,,2.4 謂詞公式

33、的等價(jià)與蘊(yùn)涵,兩個(gè)謂詞公式等價(jià)： 設(shè)P與Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域，若D上的任何一個(gè)解釋，P與Q都有相同的值，則稱公式P和公式Q在D上是等價(jià)的。謂詞公式的蘊(yùn)涵： 設(shè)P與Q是兩個(gè)謂詞公式，如果P?Q是恒真的，則稱P蘊(yùn)涵Q。且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記作 P?Q。 顯然，若Q是P的邏輯結(jié)論，則對(duì)P,Q的任意一個(gè)解釋I,如果P在I下為真，那么Q在I下也為真。反之亦然。,P

34、:“所有的人都會(huì)犯錯(cuò)誤”Q:“張三是人”R:“張三會(huì)犯錯(cuò)誤”,?x(M(x) ?R(x))M(“張三”)R(“張三”),需要證明R是(P ? Q)的邏輯結(jié)論。即證明P?Q ?R 為恒真。證：設(shè)I是P,Q,R的一個(gè)解釋（I指定“張三”為始量），且I滿足（P ?Q),即I滿足?x(M(x) ?R(x)) ? M(“張三”)，所以I滿足R(“張三”）。 否則，R（“張三”）在I下為假，于是（M(“張三”) ?R(“張

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

36、，M(x1,…,xn)是不含量詞的公式。 Q1x1,…Qn xn稱為首標(biāo)，M稱為母式。如：,?x?y?z(P(x,y ) ?Q(x,z))?x?y?zP(x,y,z)都是前束范式。,利用改名規(guī)則、量詞否定公式和量詞轄域擴(kuò)張公式等，可把任一謂詞公式化成前束范式。例如：,~?x(P(x) ??xQ(x))=~?x(~P(x) ? ?xQ(x))=?x(P(x) ? ~?xQ(x))= ?x(P(x) ? ?x~Q(x

37、))= ?x(P(x) ? ?y~Q(y)) ?x?y(P(x) ? ~Q(y)),[例2.2]將公式?x?y(?z (P(x,z) ? P(y,z)) ??uQ(x,y,u))化為前束范式：解： ?x?y(?z (P(x,z) ? P(y,z)) ??uQ(x,y,u))= ?x?y(~?z (P(x,z) ? P(y,z)) ? ?uQ(x,y,u))= ?x?y(?z (~P(x,z) ? ~P(y,z)) ?

38、 ?uQ(x,y,u))=?x?y?z?u (~P(x,z) ? ~P(y,z)) ? Q(x,y,u)),步驟1：使用以下基本等價(jià)公式，將G中的?和?刪去：F ? H=(F ? H) ?(H ? F)F ? H=~F ? H,步驟2：使用~(~F)=F，摩根定律及以下等價(jià)公式，將謂詞公式中的所有 否定號(hào)~放在原子之前：~?xG(x)=?x~G(x)~?xG(x)=?x~G(x),

39、步驟3：如果需要，則將約束變量改名。,步驟4：利用等價(jià)公式將所有量詞提到公式的最前面。,將任意謂詞公式化為前束范式的四個(gè)步驟：,2.5.2 Skolem范式,Skolem范式是謂詞邏輯中公式的又一種標(biāo)準(zhǔn)形式。設(shè)公式G的形式如下：Q1x1,…Qn xn M(x1,…,xn)其中Qi是?xi或?xi, i =1,…,n，M(x1,…,xn)是不含量詞的公式。將上式中的M(x1,…,xn)化為等值的和取范式，然后將所有的存在量詞

40、消去，便可得到公式G的Skolem范式。,消去G中的存在量詞的方法如下：設(shè)Qrxr (1? r ? n )是第一個(gè)出現(xiàn)在Q1x1,…, Qrxr ,…,Qn xn M(x1,…,xn)中的存在量詞，即Q1x1,…, Qr-1xr-1 均為全稱量詞。,若r=1，即Qrxr 左邊沒(méi)有全稱量詞，則取異于M(x1,…,xn)中所有常量符號(hào)的常量符號(hào)C,并用C代表M(x1,…,xn)中的xr，然后在首標(biāo)中Qrxr。,若1?r ? n，即Qrx

41、r左邊有全稱量詞Qs1 xs1 ,…,Qsm xsm,而m?1，1 ? s1?s2?...?s m?r，則取異于出現(xiàn)在M中的所有函數(shù)符號(hào)的m元函數(shù)符號(hào)f(xs1,…,xsm)，用f(xs1,…,xsm)代表出現(xiàn)在M中的所有xr,然后在首標(biāo)中刪除存在量詞Qrxr。,[例2.3]將公式G=?x?y?z((~P(x,y)?Q(x,z)) ?R(x,y,z))化成Skolem范式。,解：先將M(x,y,z)化成合取范式：M(x,y,z)=

42、((~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= ?x?y?z((~P(x,y) ? R(x,y,z)) ?(Q(x,z) ? R(x,y,z))) 消去?y得到：?x?z((~P(x,f(x)) ? R(x,f(x),z)) ?(Q(x,z) ? R(x,f(x),z))) 消去?z得到：?x ((~P(x,f(x))

43、? R(x,f(x),g(x))) ?(Q(x,g(x)) ? R(x,f(x),g(x))))此式就是公式G的Skolem范式。,[例2.4]將公式G=?x?y?z?u?v?wP(x,y,z,u,v,w)化成Skolem標(biāo)準(zhǔn)型。,解：消去?x,因?yàn)槠渥筮厸](méi)有全稱量詞，于是引入常量a代替P(x,y,z,u,v,w) 中的所有x,得： ?y?z?u?v?wP(a,y,z,u,v,w),消去?u，因?yàn)槠渥筮呌腥Q量詞?y?z，于是引入一

44、個(gè)二元函數(shù)f(y,z)代替P(a,y,z,u,v,w)中的所有u，得： ?y?z?v?wP(a,y,z,f(y,z),v,w),消去?w ，因?yàn)槠渥筮呌腥Q量詞 ?y?z?v，于是引入一個(gè)三元函數(shù)g(y,z,v)，代替P(a,y,z,f(y,z),v,w)中的所有w。最后得到的Skolem 標(biāo)準(zhǔn)型為：?y?z?vP(a,y,z,f(y,z),v,g(y,z,v)),注意：1.公式的Skolem 標(biāo)準(zhǔn)型與原公式并不等值；2.公式

45、的Skolem 標(biāo)準(zhǔn)型與原公式在不可滿足的意義上相等。,2.5.3 子句與子句集,若干文字的一個(gè)析取式成為子句。如：,P(x,y) ? ~Q(x,y,z) ? R(u),沒(méi)有文字的子句成為空子句。只有一個(gè)文字的子句成為單元子句。,將公式G化為Skolem 標(biāo)準(zhǔn)型，其母式M已為合取范式，M中的沒(méi)一個(gè)合取項(xiàng)都是一個(gè)子句，M中這些子句的集合用S表示，稱為公式G的子句集。,從公式G得到子句集S的方法是：先從公式G得到Skolem 標(biāo)準(zhǔn)型，然后

46、去掉全稱量詞，最后用符號(hào)“，”代替符號(hào)“?”。外層括號(hào)用{}。,如公式：G=?x?y?z((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

47、(x),g(x)))},子句集中S中的每一個(gè)子句中的變量都是由全稱量詞約束著。,對(duì)任一公式G都可以建立其對(duì)應(yīng)的S子句集。這樣對(duì)公式的討論就可以用對(duì)集合的討論來(lái)代替。,引進(jìn)子句集S的目的就是要簡(jiǎn)化對(duì)A1 ? A2 ? A3?B的證明，而證明A1 ? A2 ? A3?B只需證明G= A1 ? A2 ? A3 ? ~B的子句集不可滿足即可。,定理設(shè)S是公式G的子句集。于是，G是不可滿足的，當(dāng)且僅當(dāng)S是不可滿足的。,子句集概念的推廣：,設(shè)G=

48、 G1 ?... ? Gn ，Si是Gi化為Skolem范式后其木式給出的子句集，i=1,2,…n。令S=S1?... ? S n。于是G是不可滿足的，當(dāng)且僅當(dāng)S是不可滿足的。也稱S是個(gè)G的子句集。,,第3章 歸結(jié)推理方法,子句集的海伯倫域,海伯倫定理,替換與合一算法,歸結(jié)反演,歸結(jié)原理,本章主要內(nèi)容：（討論：如何證明一個(gè)子句集不可滿足）,歸結(jié)控制策略,,課堂練習(xí)一,3.1 子句集的海伯倫域,3.1.1 海伯倫域與海伯倫解釋,定

49、義：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。于是稱Hi為S的i級(jí)常量集，H? 稱為S的海伯倫（Herbrand）域,簡(jiǎn)稱S的H域。,[例3.1]子句集S為：S={P(f(x),a,g(y

50、),b)}求子句集S的H域。,解：根據(jù)定義H0={a,b}H1=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

51、),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))}…...,[例3.2]求子句集S={P(x),Q(y) ? R(y)}的H域。,解：該子句集中既無(wú)個(gè)體常量，又無(wú)函數(shù)，所以可任意指定一個(gè)常量a作為個(gè)體常量，從而得到：H0=H1=…=H? ={a},對(duì)于沒(méi)有變量符號(hào)出現(xiàn)的項(xiàng)、項(xiàng)集、原子、原子集合、文字、子句和子句集，分別稱之為

52、基項(xiàng)、基項(xiàng)集、基原子、基原子集合、基文字、基子句和基子句集。,關(guān)于原子集的定義：設(shè)S是子句集。集合A={所有形如P(t1,…,tn)的元素}稱作子句集S的原子集。其中P(t1,…,tn)是出現(xiàn)于S中的任一謂詞符號(hào)，而t1,…,tn是S的H域的任意元素。,例3.2中 S的原子集為 A={P(a),Q(a),R(a)},[例 3.3]S={P(x) ? Q(x),R(f(y))}根據(jù)定義有：H={a,f(a),f(f(a)

53、),…}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))),...},關(guān)于基例的定義：將S中的某子句C中所有變量符號(hào)均以S的H域的元素代入時(shí)，所得的基子句C'稱作C的一個(gè)基例。,例：S={P(x),Q(f(y)) ? R(y)}有：H={a,f(a),f(f(a),…}P(a),P(f(a))都

54、稱作子句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è)解釋。稱I為S的一個(gè)H解釋，如果滿足如下條件：,（1）I映射S中的所有常量符號(hào)到自身；（2）若f是S中n元函數(shù)符號(hào)，h1,…h(huán)n是H中元素，則I指定映射：（ h1,…h(huán)n ） ?f(h1,…h(huán)n),設(shè)A={A1,A2

55、,…,An}是S的原子集。于是S的一個(gè)解釋I可以方便地表示為如下一個(gè)集合：I={m1,m2,…,m n},,[例3.4]S={P(x)?Q(x),R(f(y))},于是：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),Q(a),R(a),P(f(a)),Q(f(a)

56、),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))),...}…...,3.1.2 海伯倫解釋與普通解釋的關(guān)系,子句集S的一個(gè)解釋，不是必須定義在H域上，即使定義在H域上，也不一定是一個(gè)

57、H解釋。,D={1,2}a/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)/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

58、,a)),...},其次，對(duì)A中每一個(gè)成員，用解釋I進(jìn)行估值：,P(a)=P(2)=F,Q(a,a)=Q(2,2)=T,P(f(a,a))=P(f(2,2))=P(1)=T,Q(a,f(a,a))=Q(2,f(2,2)=Q(2,1)=F,Q(f(a,a),a)=Q(f(2,2),2)=Q(1,2)=T,Q(f(a,a),f(a,a))=Q(f(2,2),f(2,2))=F,…...,I*={~P(a),Q(a,a),P(f(a,a)),

59、~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（普通解釋）如下：,如果子句集S中沒(méi)有常量符號(hào)，則將S的H域中初始元素a映射到D中任一元素，依照上例的方法，也可以構(gòu)造S的一個(gè)H解釋I*，使得若I滿足S，則I*也滿足S。,[例3.6]S={P(x),Q(y,f(y,z))},令S的

60、一個(gè)解釋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)/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得

61、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*，稱為對(duì)應(yīng)與I的H解釋。,定義：設(shè)I是子句集S在區(qū)域D上的解釋，?是如下遞歸定義的H到D的映射：,1.若S中有常量符號(hào)，則H0是出現(xiàn)在S中的所有常量符號(hào)的集合。于是對(duì)任意a ? H0, a?表示a在I下的映象。 若S中無(wú)常量符號(hào)

62、，則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 (

63、h1?,…,hn?)在I下的真值，T1*(P (h1,…,hn) )表示P (h1,…,hn)在I*下的真值。,引理如果某區(qū)域D上的解釋I滿足子句集S.則對(duì)應(yīng)于I的任意一個(gè)H解釋I*也滿足S。,定理子句集S是不可滿足的，當(dāng)且僅當(dāng)S被所有的H解釋弄假。,3.2 海伯倫定理,要證明子句集S是不可滿足的，只需要考慮在H域上的所有H解釋即可。但是所有的H解釋也是無(wú)限的。海伯倫定理就是用語(yǔ)義樹的方法，把需要考慮無(wú)窮個(gè)H解釋的問(wèn)題，變成只考慮有

64、限個(gè)解釋的問(wèn)題。,3.2.1 語(yǔ)義樹（解釋樹）,設(shè)子句集S的原子集A={P,Q,R},,,,,,,,,,,,,,,,,,,,,,,,,,,,,,N38,N37,N36,N34,N35,N33,N32,N31,N24,N23,N22,N21,N12,N11,N0,R,Q,~P,P,~Q,Q,~Q,R,R,R,~R,~R,~R,~R,語(yǔ)義樹：,通常以I(N)表示從根結(jié)點(diǎn)N0到到葉結(jié)點(diǎn)分枝上所標(biāo)記文字的并集。如：I(N36)={~P,Q,~

65、R},3.2.2 海伯倫定理,定理（海伯倫定理1）子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義樹是一棵有限的封閉語(yǔ)義樹。,定理（海伯倫定理2）子句集S是不可滿足的，當(dāng)且僅當(dāng)存在S的一個(gè)有限不可滿足的基例集S'。,對(duì)一階謂詞描述下的A1?A2?A3?B的證明問(wèn)題，對(duì)此已經(jīng)作了足夠的準(zhǔn)備。首先將這個(gè)問(wèn)題化成G= A1?A2?A3?~B的不可滿足問(wèn)題，進(jìn)而將G化成Skolem標(biāo)準(zhǔn)型，并建立相應(yīng)的子句集S，再將一般論域D上的討論簡(jiǎn)化

66、成H域上的討論，最后引入語(yǔ)義樹。,3.3 替換與合一算法,3.3.1 替換與最一般合一替換,一個(gè)替換是型如{t1/v1 ,…,t n/vn} 的一個(gè)有限集,其中vi是變量，而ti是不同于vi 的項(xiàng)（常量、變量、函數(shù)），且vi? vj (i ? j ) ，i,j=1,2,…,n。稱為ti替換分子， vi為替換分母。,當(dāng)t1,…,tn是基項(xiàng)時(shí)，稱此替換為基替換。,不含任何元素的替換為空替換，以?表示。,例如{a/x,b/y,f

67、(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?表示，并稱E?為E的一個(gè)例。若t是項(xiàng)， ?作用于項(xiàng)t也是將t中出現(xiàn)的vi均以ti代入，作用的結(jié)果用t?表示。,[例3.7]令?= {a/x,f(b)/y,c/z},E=P(x,y,z),t=g(x,y),于是

68、E的例為 E? =P(a,f(b),c),而 t?=g(a,f(b)),當(dāng)E是子句集S的一個(gè)子句，用?作用于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,b},P(x,y)是S的一個(gè)子句，以?= {a/x,b/y}作用于P(x,y)，得到P(a,b)。,P(a,b)就是