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

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

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

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

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

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

6、1989年,首次召開中國人工智能聯(lián)合會議,1987年,《模式識別與人工智能》雜志創(chuàng)刊,1993年,智能控制和智能自動化被列入國家科技攀登計劃,1997年,由本人編寫的《人工智能原理及應用》出版,,,1.3 人工智能的研究目標與研究途徑,研究目標分為近期目標和遠期目標：,近期目標是，使現(xiàn)有的計算機更聰明、更有用；,遠期目標是，構(gòu)造智能機器。,關于人工智能的研究途徑有兩種不同觀點：,主張用生物學的方法進行研究------產(chǎn)生出一大學派叫

7、做連接主義(Connectionism),主張用計算機科學的方法進行研究------產(chǎn)生出一大學派叫做符號主義(Symbolism),,Agent一詞的兩種解釋：一是，對環(huán)境的認識以及對環(huán)境產(chǎn)生作用的行為者；二是，代理人。 傾向于第一種解釋的主要是AI領域的研究者M. Minsky指出：“當你試圖說明完成一些任務的機器并試圖了解它是如何工作時,即將其處理為黑箱時,就稱其為Agent"。 軟件界的研究人員

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

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

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

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

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

13、on System）、智能決策支持系統(tǒng)（IDSS Intelligent Decision Support System）等。 智能管理系統(tǒng)（IMS Intelligent Management System）不僅比常規(guī)的計算機管理系統(tǒng)MIS、OAS、DSS等具有更高的智能水平，可以為非結(jié)構(gòu)化半結(jié)構(gòu)化的管理決策提供信息服務和決策支持；而且具有更全面的管理功能，可同時具備信息管理、事務處理、決策支持等多種功能。,,,自動程序設計：

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

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

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

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

18、#172;， ?， ?， ?， ?* 聯(lián)結(jié)詞相同時，從左至右運算。解釋的個數(shù)：如果一個公式G中有n個不同的原子公式（或簡稱原子），則G有2n個不同的解釋，于是G在2n個解釋下有2n個真值。如果將這些真值和它們的解釋列成表，就是G的真值表。,2.1.3 等價命題公式,如果兩個命題公式所含原子公式相同，且在任一解釋下，兩個命題公式的值相同，則稱這兩個命題公式為等價命題公式或等價公式。,常用的等價公式有：,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,證明兩個公式等價，可用真值表，也可用基本公式。,例如 要證明公式 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 永真蘊涵式,若命題公式G ? H是恒真的，稱其為永真蘊涵式。記為G?H，讀做“G蘊涵H”，也稱“G是H的邏輯結(jié)果”。,常用的永

22、真蘊涵式：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),公式的標準形式：范式,析取范式 (disjunctive normal form,DNF) ：一個由原子和原子的非組成的析取式，如果與給定的命題公式A等價，則稱它是A的析取范式。記作：,A=A1 ? A2 ?... ?

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

25、 2. 一個公式的析取范式和合取范式都不是唯一的； 3. 運算符最少的范式稱為最簡范式。,,2.2 謂詞與量詞,在命題演算中，基本元素是原子命題，而不考慮命題的內(nèi)部結(jié)構(gòu)和成分。,在形式邏輯中有一個三段論法：,P:“所有的人都會犯錯誤”Q:“張三是人”R:“張三會犯錯誤”,R應該是P和Q的邏輯結(jié)論。但在命題邏輯中無法準確表達這三個命題的邏輯關系。,因為( P ? Q ) ? R 不是恒真的。如：

26、取解釋:I=P/T,Q/T,R/F 則公式為假值F. 就是說解釋I 弄假了此公式。,為準確表達此類公式，必須引進謂詞和量詞的概念。,2.2.1謂詞,先看幾個命題：,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”為個體;,代表個體的變元稱為個體變元；,刻畫個體性質(zhì)或個

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

28、(M(x) ?R(x))M(“張三”)R(“張三”),在謂詞前加上?x,叫做變元被全稱量化；在謂詞前加上? x,叫做變元被存在量化。量化的目的是約束變元。,2.2.3 約束變元、自由變元、改名規(guī)則,量詞的轄域約束出現(xiàn)自由出現(xiàn),改名規(guī)則：在同一公式中，一個變元既以約束出現(xiàn)，有以自由出現(xiàn)。就需要對變元改名。改名規(guī)則是：,1. 變元若要改名，則該變元在量詞及其轄域中的所有出現(xiàn)均須一起更改，其余部分不變；2. 變元改名時所選用的

29、符號，必須是量詞轄域內(nèi)未出現(xiàn)的符號。一般還應是公式中未出現(xiàn)的符號。,,2.3 謂詞公式及其解釋,在定義謂詞公式前,先介紹“符號”的概念： “項”的定義；原子的定義：,符號：常元符號,變元符號,函數(shù)符號,謂詞符號,關于項的定義：1. 常元符號是項；2. 變元符號是項；3. 若f是n元函數(shù)符號，t1,…, tn 是項， 則f( t1,…, tn )是項；4. 所有項都是有限次使用1,2,3生成的符號串。,原子的定義：若P

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

31、符號的一組指定組成：,1.對每個常元符號，指定D中一個元素。2.對每個n元函數(shù)符號，指定一個函數(shù)，即指定Dn到D的一個映射。3.對每個n元謂詞符號，指定一個謂詞，即指定Dn到{T,F}的一個映射。,[例2.1]給以下公式指定一個解釋：,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可滿足，簡稱I滿足G;若I使G為F值，稱I不滿足G，或稱I弄假G。,如果不存在解釋I滿足公式G，公式G成為不可滿足的。如果公式G的所有解釋I都滿足G,公式G稱為恒真的。,,2.4 謂詞公式

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

34、:“所有的人都會犯錯誤”Q:“張三是人”R:“張三會犯錯誤”,?x(M(x) ?R(x))M(“張三”)R(“張三”),需要證明R是(P ? Q)的邏輯結(jié)論。即證明P?Q ?R 為恒真。證：設I是P,Q,R的一個解釋（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 謂詞公式的標準形式,2.5.1 前束范式一個謂詞公式，如果量詞非否定地放在全式的開頭，而量詞的轄域都延伸到整個謂詞公式，則稱這樣的公式為前束范式。,一般地，謂詞邏輯中的公式G如果有如下形狀：Q1x1,…Qn xn M(x1,…,xn)則稱G為前束范式。其中Qi是?xi或?xi, i =1,…,n

36、，M(x1,…,xn)是不含量詞的公式。 Q1x1,…Qn xn稱為首標，M稱為母式。如：,?x?y?z(P(x,y ) ?Q(x,z))?x?y?zP(x,y,z)都是前束范式。,利用改名規(guī)則、量詞否定公式和量詞轄域擴張公式等，可把任一謂詞公式化成前束范式。例如：,~?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：使用以下基本等價公式，將G中的?和?刪去：F ? H=(F ? H) ?(H ? F)F ? H=~F ? H,步驟2：使用~(~F)=F，摩根定律及以下等價公式，將謂詞公式中的所有 否定號~放在原子之前：~?xG(x)=?x~G(x)~?xG(x)=?x~G(x),

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

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

41、r左邊有全稱量詞Qs1 xs1 ,…,Qsm xsm,而m?1，1 ? s1?s2?...?s m?r，則取異于出現(xiàn)在M中的所有函數(shù)符號的m元函數(shù)符號f(xs1,…,xsm)，用f(xs1,…,xsm)代表出現(xiàn)在M中的所有xr,然后在首標中刪除存在量詞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標準型。,解：消去?x,因為其左邊沒有全稱量詞，于是引入常量a代替P(x,y,z,u,v,w) 中的所有x,得： ?y?z?u?v?wP(a,y,z,u,v,w),消去?u，因為其左邊有全稱量詞?y?z，于是引入一

44、個二元函數(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?z?v，于是引入一個三元函數(shù)g(y,z,v)，代替P(a,y,z,f(y,z),v,w)中的所有w。最后得到的Skolem 標準型為：?y?z?vP(a,y,z,f(y,z),v,g(y,z,v)),注意：1.公式的Skolem 標準型與原公式并不等值；2.公式

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

46、去掉全稱量詞，最后用符號“，”代替符號“?”。外層括號用{}。,如公式：G=?x?y?z((P(x,y) ? R(x,y,z)) ?(Q(x,z) ? R(x,y,z))),G的Skolem標準型為：?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都可以建立其對應的S子句集。這樣對公式的討論就可以用對集合的討論來代替。,引進子句集S的目的就是要簡化對A1 ? A2 ? A3?B的證明，而證明A1 ? A2 ? A3?B只需證明G= A1 ? A2 ? A3 ? ~B的子句集不可滿足即可。,定理設S是公式G的子句集。于是，G是不可滿足的，當且僅當S是不可滿足的。,子句集概念的推廣：,設G=

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

49、義：H0是出現(xiàn)于子句集S的常量符號集合。如果S中無常量符號出現(xiàn)，則H0由一個常量符號a組成。對于 i =1,2,…n 令Hi=Hi-1 ?{所有型如fn(t1,t2,…tn)的項的集合} 其中fn(t1,t2,…tn)是出現(xiàn)在S中的n元函數(shù)符號，tj ? Hi-1 j=1,2,…,n。于是稱Hi為S的i級常量集，H? 稱為S的海伯倫（Herbrand）域,簡稱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域。,解：該子句集中既無個體常量，又無函數(shù)，所以可任意指定一個常量a作為個體常量，從而得到：H0=H1=…=H? ={a},對于沒有變量符號出現(xiàn)的項、項集、原子、原子集合、文字、子句和子句集，分別稱之為

52、基項、基項集、基原子、基原子集合、基文字、基子句和基子句集。,關于原子集的定義：設S是子句集。集合A={所有形如P(t1,…,tn)的元素}稱作子句集S的原子集。其中P(t1,…,tn)是出現(xiàn)于S中的任一謂詞符號，而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))),...},關于基例的定義：將S中的某子句C中所有變量符號均以S的H域的元素代入時，所得的基子句C'稱作C的一個基例。,例：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)的基例。,關于海伯倫解釋的定義：,設S是子句集，H是S的海伯倫域，I是S在H上的一個解釋。稱I為S的一個H解釋，如果滿足如下條件：,（1）I映射S中的所有常量符號到自身；（2）若f是S中n元函數(shù)符號，h1,…h(huán)n是H中元素，則I指定映射：（ h1,…h(huán)n ） ?f(h1,…h(huán)n),設A={A1,A2

55、,…,An}是S的原子集。于是S的一個解釋I可以方便地表示為如下一個集合：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 海伯倫解釋與普通解釋的關系,子句集S的一個解釋，不是必須定義在H域上，即使定義在H域上，也不一定是一個

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的一個解釋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)),...},其次，對A中每一個成員，用解釋I進行估值：,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的一個解釋I（普通解釋）如下：,如果子句集S中沒有常量符號，則將S的H域中初始元素a映射到D中任一元素，依照上例的方法，也可以構(gòu)造S的一個H解釋I*，使得若I滿足S，則I*也滿足S。,[例3.6]S={P(x),Q(y,f(y,z))},令S的

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

62、，則H0={a}。于是a?可以是D中隨便哪個元素。,2.對任意(h1,…,hn) ? Hin，及S中的任意n元函數(shù)符號f(x1,…,xn)，令(f (h1,…,hn) )? 是(h1?,…,hn?)在I下的H解釋I *有如下規(guī)定。 若(h1,…,hn) =Hn，P (x1,…,xn)是n元函數(shù)符號，則規(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.則對應于I的任意一個H解釋I*也滿足S。,定理子句集S是不可滿足的，當且僅當S被所有的H解釋弄假。,3.2 海伯倫定理,要證明子句集S是不可滿足的，只需要考慮在H域上的所有H解釋即可。但是所有的H解釋也是無限的。海伯倫定理就是用語義樹的方法，把需要考慮無窮個H解釋的問題，變成只考慮有

64、限個解釋的問題。,3.2.1 語義樹（解釋樹）,設子句集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,語義樹：,通常以I(N)表示從根結(jié)點N0到到葉結(jié)點分枝上所標記文字的并集。如：I(N36)={~P,Q,~

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

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

67、(x)/z}就是一個替換。,替換可作用與某個謂詞公式上，也可作用于某個項上。,令替換?= {t1/v1 ,…,t n/vn} ，作用于E，而E是一謂詞公式。就是將E中出現(xiàn)的vi均以ti代入(i=1,2,…,n), 作用的結(jié)果用E?表示，并稱E?為E的一個例。若t是項， ?作用于項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)),當E是子句集S的一個子句，用?作用于E，當?中的v1,…,vn含有E的所有變量， t1,…,tn又是H的元素時， E? 便是S的子句E的基例。,[例3.8]子句集S={P(x,y),Q(x,a) ? R(y,b)},此子句集的H域：H={a,b},P(x,y)是S的一個子句，以?= {a/x,b/y}作用于P(x,y)，得到P(a,b)。,P(a,b)就是