【文章內(nèi)容簡(jiǎn)介】 (= x)P ( ~ P ~ x) (= x)P ( ~ Q ~ P ~ Q) (P ~ Q ~ P ~ Q) (P ~ ? ? ? ? ? = ? ? = ? 智能科學(xué)與技術(shù)系 3)對(duì)變量標(biāo)準(zhǔn)化 改變變量名，使不同的變量不同名 4)消去存在量詞 (具體化 Skolemnizing)， 兩種情況： 1. 存在量詞不在全稱量詞的轄域內(nèi) ——用新的個(gè)體常量替換受存在量詞約束的變?cè)? 2. 存在量詞在全稱量詞的轄域內(nèi) Skolem函數(shù) ， 即具體化函數(shù) x)Q(x) ( x)P(x) ( ? ? ? y)Q(y) ( x)P(x) ( ? ? ? ) a ( Q ) x ( P ) x ( ? ? ? ) y ( Q ) y ( ) x ( P ) x ( ? ? ? ) y , x ,..., x , x ( P ) y )( x )...( x )( x ( n 2 1 n 2 1 ? ? ? ? ) x ,..., x , x ( f , x ,..., x , x ( P ) x )...( x )( x ( ) n 2 1 n 2 1 n 2 1 ? ? ? ? 智能科學(xué)與技術(shù)系 5)化為前束形式 把全稱量詞提到最外層 前束形 := (前綴 ) {母式 } ↑ ↑ 全稱量詞串 無(wú)量詞公式 6)把母式化為合取范式 7)消去全稱量詞 8)消去連詞符號(hào) ∧ ，寫成子句集 9)變量分離標(biāo)準(zhǔn)化 改變變量名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中 智能科學(xué)與技術(shù)系 消解式的定義 命題邏輯的消解式 設(shè) C1與 C2是子句集中的任意兩個(gè)子句，如果 C1中的文字 L1與C2中的文字 L2互補(bǔ)，那么從 C1和 C2中分別消去 L1和 L2，并將兩個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句 C12，則稱這一過(guò)程為消解，稱 C12為 C1和 C2的消解式， C1， C2為 C12的親本子句 例：子句 C1=P∨ C139。 C2=~P∨ C239。 消解式 C12=C139?！?C239。 一階謂詞邏輯的消解式 設(shè) C1與 C2是兩個(gè)沒(méi)有相同變?cè)淖泳洌?L1和 L2分別是 C1和 C2中的文字，若 σ是 L1和 ~L2的最一般合一者，則稱 C12=(C1σ {L1σ})∪ (C2σ {L2σ}) 為 C1和 C2的二元消解式， L1和 L2為消解式上的文字 智能科學(xué)與技術(shù)系 怎么利用消解原理進(jìn)行證明？ 消解反演 通俗的說(shuō)就是 “ 反證法 ” 要證命題 A恒為真，等價(jià)于證 ﹁ A恒為假 證明過(guò)程 否定結(jié)論 R，得 ﹁ R ； 把 ﹁ R添加到已知前提集合 F中去； 把新產(chǎn)生的集合｛ ﹁ R ， F｝化成范式； 應(yīng)用消解原理，不斷求消解式，直到得到一個(gè)表示矛盾的空子句 智能科學(xué)與技術(shù)系 假設(shè)：所有不貧窮并且聰明的人都是快樂(lè)的，那些看書(shū)的人是聰明的。李明能看書(shū)且不貧窮，快樂(lè)的人過(guò)著激動(dòng)人心的生活。 求證：李明過(guò)著激動(dòng)人心的生活。 解：先定義謂詞： Poor(x) x是貧窮的 Smart(x) x是聰明的 Happy(x) x是快樂(lè)的 Read(x) x能看書(shū) Exciting(x) x過(guò)著激動(dòng)人心的生活 消解反演示例 —“激動(dòng)人心的生活 ” 問(wèn)題 智能科學(xué)與技術(shù)系 消解反演示例 —“激動(dòng)人心的生活 ” 問(wèn)題 問(wèn)題謂詞表示： “ 所有不貧窮并且聰明的人都是快樂(lè)的 ” (?x)((~Poor(x)∧ Smart(x))→Happy(x)) “那些看書(shū)的人是聰明的 ” (?y) (Read(y) → Smart(y)) “李明能看書(shū)且不貧窮 ” Read(Liming)∧ ~Poor(Liming) “快樂(lè)的人過(guò)著激動(dòng)人心的生活 ” (?z) (Happy(z)→Exciting(z)) 目標(biāo) “ 李明過(guò)著激動(dòng)人心的生活 ” 的否定 ~Exciting(Liming) 智能科學(xué)與技術(shù)系 消解反演示例 —“激動(dòng)人心的生活 ” 問(wèn)題 將上述謂詞公式轉(zhuǎn)化為子句集如下： (1) Poor(x)∨ ~Smart(x)∨ Happy(x) (2) ~Read(y)∨ Smart(y) (3) Read(Liming) (4) ~Poor(Liming) (5) ~Happy(z)∨ Exciting(z) (6) ~Exciting(Liming) (結(jié)論的否定 ) 智能科學(xué)與技術(shù)系 消解反演示例 —“激動(dòng)人心的生活 ” 問(wèn)題 ~Exciting(Liming) ~Happy(z)∨ Exciting(z) ~Happy(Liming) Happy(x))∨ ~Smart(x)∨ Happy(x) Poor(Liming)∨ ~Smart(Liming) ~Read(y)∨ Smart(y ) Poor(Liming)∨ ~Read(Liming) ~Poor(Liming) ~Read(Liming) Read(Liming) NIL {Liming/z} {Liming/x} {Liming/y} 智能科學(xué)與技術(shù)系 消解原理的局限性 消解原理推進(jìn)了用邏輯方法進(jìn)行機(jī)器證明的研究，使得自動(dòng)定理證明領(lǐng)域發(fā)生了質(zhì)的變化。 但是 要求把邏輯公式轉(zhuǎn)化為某種范式，喪失了其固有的邏輯蘊(yùn)含語(yǔ)義 。例如： 如果一個(gè)人發(fā)燒、肚子痛，那么很可能是感染了。 ?x (has_fever(x) ∧ tummy_pain(x) → has_an_infection(x)) ? has_fever(x)∨ ? tummy_pain(x) ∨ has_an_infection(x) 表達(dá)能力的局限性 , 限制了應(yīng)用范圍 后來(lái)有許多重要改進(jìn)：語(yǔ)義歸結(jié)（ 消解 ）、鎖歸結(jié)（ 消解） 、線性歸結(jié)（ 消解） 等。 智能科學(xué)與技術(shù)系 問(wèn)題求解與圖搜索策略 ?問(wèn)題求解 ?問(wèn)題表示 ?解的搜索 智能科學(xué)與技術(shù)系 問(wèn)題求解 —什么是問(wèn)題求解 問(wèn)題求解是人工智能的核心問(wèn)題之一 問(wèn)題求解的目的 機(jī)器自動(dòng)找出某問(wèn)題的正確解決策略 更進(jìn)一步，能夠舉一反三，具有解決同類問(wèn)題的能力 是從人工智能初期的智力難題、棋類游戲、簡(jiǎn)單數(shù)學(xué)定理證明等問(wèn)題的研究中開(kāi)始形成和發(fā)展起來(lái)的一大類技術(shù) 求解的手段多種多樣 其中搜索技術(shù)是問(wèn)題求解的主要手段之一 問(wèn)題表示 解的搜索 智能科學(xué)與技術(shù)系 八數(shù)碼難題 在 3 3的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有 1至 8的某一數(shù)字。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。 1 2 3 8 4 5 6 7 初始狀態(tài) 8 1 3 2 4 5 6 7 目標(biāo)狀態(tài) 如何將棋盤從某一初始狀態(tài)變成最后的目標(biāo)狀態(tài)？ 問(wèn)題求解 —問(wèn)題示例 智能科學(xué)與技術(shù)系 問(wèn)題示例 49 怎樣找到兩點(diǎn)之間的最短路徑呢？ 問(wèn)題有了，可怎么讓計(jì)算機(jī)知道這些問(wèn)題呢？ 智能科學(xué)與技術(shù)系 問(wèn)題表示 ——狀態(tài)空間圖 例： 真空吸塵器的世界 假設(shè)：吸塵器的世界只有兩塊地毯大小，地毯或者是臟的，或者是干凈的 吸塵器能做的動(dòng)作只有三個(gè) {向左 (Left)，向右 (Right)，吸塵 (Suck)} 一共有多