西電人工智能4知識表示方法part2

1、西安電子科技大學西安電子科技大學Artificial Intelligence (AI)人工智能人工智能主講：戚玉濤Email：qi_第二章：知識第二章：知識表示方法表示方法西安電子科技大學西安電子科技大學內容提要1.1.狀態(tài)空間法狀態(tài)空間法2.2.問題歸約法問題歸約法3.3.謂詞邏輯法謂詞邏輯法4.4.語義網(wǎng)絡法語義網(wǎng)絡法5.5.其他方法其他方法西安電子科技大學西安電子科技大學問題歸約法v 問題歸約（問題歸約（Problem Reduction） 是另外一種是另外一種基于狀態(tài)空間基于狀態(tài)空間的問題描述與求解方法的問題描述與求解方法 已知問題的描述，通過一系列已知問題的描述，通過一系列變換變換

2、把此問題變?yōu)橐粋€把此問題變?yōu)橐粋€子問題子問題集合集合 這些子問題的解可以這些子問題的解可以直接得到（本原問題）直接得到（本原問題），從而解決了初，從而解決了初始問題始問題西安電子科技大學西安電子科技大學問題歸約法v 問題歸約法的組成部分問題歸約法的組成部分一個初始問題描述；一個初始問題描述；一套把問題變換為子問題的一套把問題變換為子問題的操作符操作符；一套一套本原問題本原問題描述。描述。( (本原問題本原問題: :不能再分解或變換且不能再分解或變換且直接可解的子問題直接可解的子問題) )v 問題歸約的實質：問題歸約的實質：從目標（要解決的問題）出發(fā)從目標（要解決的問題）出發(fā)逆向推理逆向推理，建

3、立子問題，建立子問題以及子問題的子問題，直到最后把初始問題歸約為以及子問題的子問題，直到最后把初始問題歸約為一一個本原問題集合個本原問題集合。西安電子科技大學西安電子科技大學問題歸約法v 問題歸約法舉例：問題歸約法舉例：漢諾塔問題（漢諾塔問題（ Hanoi ） p 從從1移到移到3p 每次移動一個盤子每次移動一個盤子p 大盤在下小盤在上大盤在下小盤在上123CBA初始狀態(tài)（初始狀態(tài)（111）目標狀態(tài)（目標狀態(tài)（333）CBA西安電子科技大學西安電子科技大學漢諾塔問題v 原始問題可以歸約為下列原始問題可以歸約為下列3 3個子問題：個子問題：子問題子問題1 1：子問題子問題2 2：子問題子問題3

4、3：西安電子科技大學西安電子科技大學漢諾塔問題v 歸約過程（歸約過程（3 3個圓盤）個圓盤）西安電子科技大學西安電子科技大學漢諾塔問題v 漢諾塔問題歸約圖漢諾塔問題歸約圖本原問題本原問題本原問題本原問題與或圖與或圖CBA西安電子科技大學西安電子科技大學問題歸約法v 與或圖表示：與或圖表示：用一個類似于圖的結構來表示把問題歸約為用一個類似于圖的結構來表示把問題歸約為后繼問題的替換集合。后繼問題的替換集合。與圖：與圖：把一個復雜問題把一個復雜問題分解為若干個較為簡單的分解為若干個較為簡單的子問題，形成子問題，形成“與與”樹。樹?；驁D：或圖：把原問題變換為把原問題變換為若干個較為容易求解的新若干個較

5、為容易求解的新問題，形成問題，形成“或或”樹。樹。西安電子科技大學西安電子科技大學問題歸約法v 與或圖表示：與或圖表示：BCDEFGAHMBCDEFGAN子問題替代集合結構圖子問題替代集合結構圖與或圖與或圖西安電子科技大學西安電子科技大學問題歸約法v 一些關于與或圖的術語一些關于與或圖的術語起始節(jié)點起始節(jié)點對應于原對應于原始問題描始問題描述述終葉節(jié)點對應于本原問題終葉節(jié)點對應于本原問題西安電子科技大學西安電子科技大學問題歸約法v 與或圖的構成規(guī)則與或圖的構成規(guī)則 1 1）與或圖中的每個節(jié)點代表一）與或圖中的每個節(jié)點代表一個要解決的單一問題或問題集合。個要解決的單一問題或問題集合。圖中所含起始節(jié)

6、點對應于原始問圖中所含起始節(jié)點對應于原始問題題A A。 2 2）對應于本原問題的節(jié)點稱為）對應于本原問題的節(jié)點稱為終葉節(jié)點，它沒有后繼節(jié)點。終葉節(jié)點，它沒有后繼節(jié)點。 3 3）對于把算符應用于問題）對于把算符應用于問題A A的每的每種可能情況，都把問題變換為一種可能情況，都把問題變換為一個子問題集合；有向弧線自個子問題集合；有向弧線自A A指指向后繼節(jié)點表示所求得的子問題向后繼節(jié)點表示所求得的子問題集合。集合。HMBCDEFGAN西安電子科技大學西安電子科技大學問題歸約法v 與或圖的構成規(guī)則與或圖的構成規(guī)則 4 4）一般對于代表兩個或兩個以上）一般對于代表兩個或兩個以上子問題集合的每個節(jié)點，有

7、向弧子問題集合的每個節(jié)點，有向弧線從此節(jié)點指向次子問題集合中線從此節(jié)點指向次子問題集合中的各個節(jié)點。由于只有當集合中的各個節(jié)點。由于只有當集合中所有項都有解時，這個子問題的所有項都有解時，這個子問題的集合才能獲得解答，所以這些子集合才能獲得解答，所以這些子問題節(jié)點叫做與節(jié)點。問題節(jié)點叫做與節(jié)點。 5 5）特殊情況下，當只有一個算符）特殊情況下，當只有一個算符可應用于問題可應用于問題A A，而且這個算符產(chǎn)，而且這個算符產(chǎn)生具有一個以上子問題的某個集生具有一個以上子問題的某個集合時，由上述規(guī)則合時，由上述規(guī)則3 3）和規(guī)則）和規(guī)則4 4）所產(chǎn)生的圖可以得到簡化。所產(chǎn)生的圖可以得到簡化。MDEFAA

8、DEF簡化簡化西安電子科技大學西安電子科技大學問題歸約法v與或圖的搜索：與或圖的搜索：目的在于表明起始節(jié)點是有解的。目的在于表明起始節(jié)點是有解的。v可解節(jié)點可解節(jié)點終葉節(jié)點是可解節(jié)點（對應于本原問題）。終葉節(jié)點是可解節(jié)點（對應于本原問題）。如果某個非終葉節(jié)點含有如果某個非終葉節(jié)點含有或后繼節(jié)點或后繼節(jié)點，那么只要當其后，那么只要當其后繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。的。如果某個非終葉節(jié)點含有如果某個非終葉節(jié)點含有與后繼節(jié)點與后繼節(jié)點，那么只有當其后，那么只有當其后繼節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。繼節(jié)點全部為可解時，

9、此非終葉節(jié)點才是可解的。西安電子科技大學西安電子科技大學問題歸約法v不可解節(jié)點不可解節(jié)點沒有后裔的非終葉節(jié)點為不可解節(jié)點。沒有后裔的非終葉節(jié)點為不可解節(jié)點。 如果某個非終葉節(jié)點含有如果某個非終葉節(jié)點含有或后繼節(jié)點或后繼節(jié)點，那么只有當其，那么只有當其全全部后裔為不可解時部后裔為不可解時，此非終葉節(jié)點才是不可解的。，此非終葉節(jié)點才是不可解的。 如果某個非終葉節(jié)點含有如果某個非終葉節(jié)點含有與后繼節(jié)點與后繼節(jié)點，那么只要當其，那么只要當其后后裔至少有一個為不可解時裔至少有一個為不可解時，此非終葉節(jié)點才是不可解的。，此非終葉節(jié)點才是不可解的。v解樹解樹由可解節(jié)點所構成，并且由這些可解節(jié)點可推出初始節(jié)由

10、可解節(jié)點所構成，并且由這些可解節(jié)點可推出初始節(jié)點為可解節(jié)點的子樹稱為解樹。點為可解節(jié)點的子樹稱為解樹。解樹中一定包含初始節(jié)點，它對應于原始問題。解樹中一定包含初始節(jié)點，它對應于原始問題。西安電子科技大學西安電子科技大學問題歸約法ttttttttt有解節(jié)點有解節(jié)點無解節(jié)點無解節(jié)點終葉節(jié)點終葉節(jié)點與或圖例子與或圖例子原始問題原始問題有一有一個以上的解個以上的解原始問題原始問題有有解解西安電子科技大學西安電子科技大學內容提要1.1.狀態(tài)空間法狀態(tài)空間法2.2.問題歸約法問題歸約法3.3.謂詞邏輯法謂詞邏輯法4.4.語義網(wǎng)絡法語義網(wǎng)絡法5.5.其他方法其他方法西安電子科技大學西安電子科技大學謂詞邏輯法

11、v命題邏輯與謂詞邏輯命題邏輯與謂詞邏輯命題邏輯與謂詞邏輯是最先用于人工智能的兩種邏輯，命題邏輯與謂詞邏輯是最先用于人工智能的兩種邏輯，對于知識的形式化表示，特別是定理的證明發(fā)揮了重對于知識的形式化表示，特別是定理的證明發(fā)揮了重要作用要作用雖然命題邏輯能夠把客觀世界的各種事實表示為邏輯雖然命題邏輯能夠把客觀世界的各種事實表示為邏輯命題，但是它具有較大的局限性。命題邏輯只能進行命題，但是它具有較大的局限性。命題邏輯只能進行命題間命題間關系關系的推理，無法解決與的推理，無法解決與命題結構命題結構和和成分成分有關有關的推理問題，的推理問題，不適合表示比較復雜的問題不適合表示比較復雜的問題。謂詞邏輯是在

12、命題邏輯的基礎上發(fā)展而來的，命題邏謂詞邏輯是在命題邏輯的基礎上發(fā)展而來的，命題邏輯可以看作是謂詞邏輯的一種特殊形式。輯可以看作是謂詞邏輯的一種特殊形式。西安電子科技大學西安電子科技大學謂詞邏輯法v命題命題命題是具有真假意義的語句命題是具有真假意義的語句命題代表人們進行思維時的一種判斷，若命題的意義命題代表人們進行思維時的一種判斷，若命題的意義為真，稱它的真值為為真，稱它的真值為“真真”，記作，記作“T”；若命題的意；若命題的意義為假，稱它的真值為義為假，稱它的真值為“假假”，記作，記作“F”。例如：。例如：p“西安是陜西省省會西安是陜西省省會”“”“10大于大于6”是真值為是真值為“T”的命題

13、的命題p“月亮是方的月亮是方的”“”“煤炭是白的煤炭是白的”是真值為是真值為“F”的命題的命題一個命題不能同時即為真又為假，但可以在一定條件一個命題不能同時即為真又為假，但可以在一定條件下為真，在另一種條件下為假。例如：下為真，在另一種條件下為假。例如：p“1+1=10”1+1=10”在二進制情況下為真，十進制情況下為假在二進制情況下為真，十進制情況下為假西安電子科技大學西安電子科技大學謂詞邏輯法v命題命題沒有真假意義的語句，如感嘆句、疑問句等，不是命沒有真假意義的語句，如感嘆句、疑問句等，不是命題。題。通常用大寫英文字母表示一個命題，例如：通常用大寫英文字母表示一個命題，例如： p P P：

14、西安是座古老的城市：西安是座古老的城市v命題邏輯的局限性？命題邏輯的局限性？客觀事物的結構及邏輯特征？客觀事物的結構及邏輯特征？不同事物間的共同特征？不同事物間的共同特征？西安電子科技大學西安電子科技大學謂詞邏輯法v命題邏輯的局限性？命題邏輯的局限性？命題這種表示方法無法把它所描述的客觀事物的結構命題這種表示方法無法把它所描述的客觀事物的結構及邏輯特征反映出來，也不能把不同事物間的共同特及邏輯特征反映出來，也不能把不同事物間的共同特征表述出來征表述出來例如，用字母例如，用字母P P表示表示“小張是老張的兒子小張是老張的兒子”這一命題，這一命題，則無法表述出老張與小張是父子關系則無法表述出老張與

15、小張是父子關系又如，又如，“張三是學生張三是學生”，“李四是學生李四是學生”這兩個命題，這兩個命題，用命題邏輯表示時，無法把兩者的共同特征用命題邏輯表示時，無法把兩者的共同特征“都是學都是學生生”形式的表示出來形式的表示出來可否用可否用 Student（“張三張三”），）， Student（“李四李四”）表示上述命題？表示上述命題？謂詞邏輯謂詞邏輯西安電子科技大學西安電子科技大學謂詞邏輯法v謂詞謂詞在謂詞邏輯中，命題是用形如在謂詞邏輯中，命題是用形如P(x1,x2,xn)的謂詞來表的謂詞來表述的。一個謂詞可分為述的。一個謂詞可分為謂詞名謂詞名與與個體個體兩個部分兩個部分個體：個體： 是命題的主

16、語，表示獨立存在的事物或某個抽是命題的主語，表示獨立存在的事物或某個抽象的概念象的概念p “x1,x2,xn”是個體，一般用小寫字母表示是個體，一般用小寫字母表示p 個體可以是個體常量、變元或函數(shù)個體可以是個體常量、變元或函數(shù)謂詞名：謂詞名：表示個體的性質、狀態(tài)或個體之間的關系表示個體的性質、狀態(tài)或個體之間的關系p “P”是謂詞名，一般用大寫字母表示是謂詞名，一般用大寫字母表示p 稱稱P 是一個是一個n元謂詞。元謂詞。西安電子科技大學西安電子科技大學謂詞邏輯法v謂詞謂詞對于命題對于命題“張三是學生張三是學生” ，用謂詞可以表示為：，用謂詞可以表示為：Student（“張三張三”）。其中，）。其

17、中， Student是謂詞名，是謂詞名， “張張三三”是個體，是個體， Student刻畫了刻畫了“張三張三”是個學生這一特是個學生這一特征。征。在謂詞中，個體可以是常量，也可以是變元，還可以在謂詞中，個體可以是常量，也可以是變元，還可以是一個函數(shù)。例如，對于命題是一個函數(shù)。例如，對于命題“x10”可以表示為可以表示為more（x,10），其中），其中x是變元。又如，命題是變元。又如，命題“小張的父親是小張的父親是老師老師”，可以表示為，可以表示為Teacher（father（Zhang），其），其中，中， father（Zhang）是一個函數(shù)。）是一個函數(shù)。當謂詞中的變元都用特定的個體取代時

18、，謂詞就具有當謂詞中的變元都用特定的個體取代時，謂詞就具有一個確定的真值一個確定的真值“T”或或 “F” 。西安電子科技大學西安電子科技大學謂詞邏輯法v謂詞謂詞在在n元謂詞元謂詞 P(x1,x2,xn)中，若每個個體均為常量、變中，若每個個體均為常量、變元或函數(shù)，則稱它為元或函數(shù)，則稱它為一階謂詞一階謂詞。如果某個個體本身又是一個一階謂詞，則稱它為如果某個個體本身又是一個一階謂詞，則稱它為二階二階謂詞謂詞，如此類推。，如此類推。個體變元的取值范圍稱為個體變元的取值范圍稱為個體域個體域。個體域可以是有限。個體域可以是有限的，也可以是無限的。例如用的，也可以是無限的。例如用I（x）表示）表示“x是

19、整數(shù)是整數(shù)”，則個體域為所有整數(shù)，是無限的。則個體域為所有整數(shù)，是無限的。謂詞與函數(shù)不同謂詞與函數(shù)不同，謂詞的真值是，謂詞的真值是”T“或或”F“，而函數(shù)，而函數(shù)的值是個體域中的一個個體，無真值可言。的值是個體域中的一個個體，無真值可言。西安電子科技大學西安電子科技大學謂詞邏輯法v謂詞演算謂詞演算謂詞邏輯語言的語法和語義謂詞邏輯語言的語法和語義p基本符號：基本符號：謂詞符號、變量符號、函數(shù)符號、常量符號、謂詞符號、變量符號、函數(shù)符號、常量符號、括號和逗號括號和逗號p原子公式：原子公式：原子公式由若干謂詞符號和項組成原子公式由若干謂詞符號和項組成 謂詞符號謂詞符號規(guī)定定義域內的一個相應關系規(guī)定定

20、義域內的一個相應關系 常量符號常量符號是最簡單的項，表示論域內的物體或實體是最簡單的項，表示論域內的物體或實體 變量符號變量符號也是項，不明確涉及是哪一個實體也是項，不明確涉及是哪一個實體 函數(shù)符號函數(shù)符號表示論域內的函數(shù)，是從論域內的一個實體到另表示論域內的函數(shù)，是從論域內的一個實體到另外一個實體的映射外一個實體的映射 例如：原子公式例如：原子公式 Married father(LI) , mother(LI) 表示表示“李（李（LI LI）的父親和他的母親結婚）的父親和他的母親結婚”西安電子科技大學西安電子科技大學謂詞邏輯法連詞和量詞連詞和量詞p連詞連詞 合取：合?。悍柗枴?”， 表示

21、所連結的兩個命題之間具有表示所連結的兩個命題之間具有“與與”的關系。的關系。 析取：析取： 符號符號“ ”，表示所連結的兩個命題之間具有，表示所連結的兩個命題之間具有“或或”的關系的關系 蘊涵：蘊涵：符號符號“ ” ，表示，表示“若若則則”的語義。的語義。PQPQ讀讀作作“如果如果P P，則，則QQ”其中，其中，P P稱為條件的前件，稱為條件的前件，QQ稱為條件稱為條件的后件。的后件。 非：非：符號符號“ ”，表示對其后面的命題的否定，表示對其后面的命題的否定 雙條件：雙條件：符號符號“ ”，表示，表示“當且僅當當且僅當”的語義。的語義。 P PQQ讀作讀作“P P當且僅當當且僅當QQ”。西安

22、電子科技大學西安電子科技大學謂詞邏輯法p量詞量詞 全稱量詞：全稱量詞：符號符號“ ”，意思是意思是“所有的所有的”、“任一個任一個” x x讀作讀作“對一切對一切x x”, ,或或“對每一對每一x x”，或，或“對任一對任一x x”。命題命題( ( x)P(x)x)P(x)為真，當且僅當對論域中的所有為真，當且僅當對論域中的所有x x，都有，都有P(x)P(x)為真為真命題命題( ( x)P(x)x)P(x)為假，當且僅當至少存在論域中的一個為假，當且僅當至少存在論域中的一個x x，使得使得P(x)P(x)為假為假 存在量詞：存在量詞：符號符號“ ”，意思是意思是“至少有至少有”、“存在存在”

23、 x x讀作讀作“存在一個存在一個x x”, ,或或“對某些對某些x x”，或，或“至少有一至少有一x x”。命題命題( ( x)P(x)x)P(x)為真，當且僅當至少存在論域中的一個為真，當且僅當至少存在論域中的一個x x，使得使得P(x)P(x)為真為真命題命題( ( x)P(x) x)P(x)為假，當且僅當對論域中的所有為假，當且僅當對論域中的所有x x，都有，都有P(x)P(x)為假為假 西安電子科技大學西安電子科技大學謂詞邏輯法v謂詞公式謂詞公式 原子謂詞公式：原子謂詞公式：是由謂詞符號和若干項組成的謂詞演算。是由謂詞符號和若干項組成的謂詞演算。 分子謂詞公式：分子謂詞公式：可以用可

24、以用連詞連詞把原子謂詞公式組成復合謂詞公式，把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。并把它叫做分子謂詞公式。 合式公式（合式公式（WFF，Well-formed Formulas）：）：通常把通常把合式公式合式公式叫叫做做謂詞公式謂詞公式，遞歸定義如下：，遞歸定義如下：p(1) 原子謂詞公式是合式公式原子謂詞公式是合式公式p(2) 若若A為合式公式，則為合式公式，則 A也是一個合式公式也是一個合式公式p(3) 若若A,B是合式公式，則是合式公式，則AB，AB，AB，AB也都是合式公也都是合式公式式p(4) 若若A是合式公式，是合式公式，x為為A中的自由變元，則中的自由變元，則

25、( x)A和和( x)A都是合式都是合式公式公式p(5) 只有按上述規(guī)則只有按上述規(guī)則(1)至至(4)求得的那些公式，才是合式公式。求得的那些公式，才是合式公式。西安電子科技大學西安電子科技大學謂詞邏輯法v謂詞公式謂詞公式 用謂詞公式表示知識時，需要首先用謂詞公式表示知識時，需要首先定義謂詞定義謂詞，然后再用，然后再用連接連接詞把有關的謂詞連接起來，形成一個謂詞公式表達一個完整詞把有關的謂詞連接起來，形成一個謂詞公式表達一個完整的意義。的意義。 例例1：設有下列知識設有下列知識 劉歡比他父親出名。劉歡比他父親出名。 高揚是計算機系的一名學生，但他不喜歡編程高揚是計算機系的一名學生，但他不喜歡編

26、程 。 任何整數(shù)或者為正或者為負。任何整數(shù)或者為正或者為負。為了用謂詞公式表示上述知識，首先需要定義謂詞：為了用謂詞公式表示上述知識，首先需要定義謂詞： FAMOUS (x, y) : x比比y出名出名 COMPUTER ( x ) : x 是計算機系的是計算機系的 LIKE (x, y ) : x 喜歡喜歡 y西安電子科技大學西安電子科技大學謂詞邏輯法 I(x)表示表示“x是整數(shù)是整數(shù)” P(x)表示表示“x是正數(shù)是正數(shù)” N(x)表示表示“x是負數(shù)是負數(shù)” 此時可用謂詞公式把上述知識表示為此時可用謂詞公式把上述知識表示為: 劉歡比他父親出名劉歡比他父親出名: FAMOUS ( liuhua

27、n, father ( liuhuan ) 高揚是計算機系的一名學生，但他不喜歡編程高揚是計算機系的一名學生，但他不喜歡編程 : COMPUTER(gaoyang)LIKE(gaoyang, programing) 任何整數(shù)或者為正或者為負任何整數(shù)或者為正或者為負: ( x)(I(x) (P(x) N(x)西安電子科技大學西安電子科技大學謂詞邏輯法v謂詞公式謂詞公式 例例2：用謂詞邏輯描述右圖中的房子的概念用謂詞邏輯描述右圖中的房子的概念p個體個體 ：A , Bp謂詞謂詞 ：SUPPORT( x,y )：表示：表示 x 被被 y支撐著支撐著 WEDRE ( x )：表示：表示 x 是楔形塊是楔

28、形塊 BRICK( y )：表示：表示 y 是長方塊是長方塊 p其中其中 x , y是個體變元，它們的個體域是個體變元，它們的個體域A,Bp房子的概念可以表示成一組合式謂詞公式的合取式：房子的概念可以表示成一組合式謂詞公式的合取式： SUPPORT(A,B) WEDGE( A ) BRICK( B )西安電子科技大學西安電子科技大學謂詞邏輯法v合式公式的性質合式公式的性質若若P、Q是兩個合式公式，則由這兩個合式公式所組成是兩個合式公式，則由這兩個合式公式所組成的復合表達式可由下列真值表給出。的復合表達式可由下列真值表給出。PQPPQPQPQPQTTFTTTTTFFTFFFFTTTFTFFFTF

29、FTT西安電子科技大學西安電子科技大學謂詞邏輯法v合式公式的性質合式公式的性質 如果兩個合式公式，無論如何解釋，其真值表都是相同的，如果兩個合式公式，無論如何解釋，其真值表都是相同的，那么我們就稱此兩合式公式是那么我們就稱此兩合式公式是等價的等價的。 應用上述真值表可以確立下列等價關系：應用上述真值表可以確立下列等價關系：p（1）否定之否定：）否定之否定： ( P ) = Pp（2）( P Q ) = ( P Q ) ，或者，或者( P Q ) = ( P Q ）p（3）狄）狄 摩根定律：摩根定律： ( P Q ) = P Q ( P Q ) = P Qp（4）分配律：）分配律： P ( Q

30、R ) = ( P Q ) ( P R ) P ( Q R ) = ( P Q ) ( P R )西安電子科技大學西安電子科技大學謂詞邏輯法p（5）交換律：）交換律： P Q = Q P P Q = Q Pp（6）結合律：）結合律： P ( Q R ) = ( P Q ) R P ( Q R ) = ( P Q ) Rp（7）逆否率：）逆否率： ( P Q ) = ( Q P ) p（8）泛界律：）泛界律： P F = P , P T = P P F = F , P T = T p（9）互余律：）互余律： P P = T, P P = F西安電子科技大學西安電子科技大學謂詞邏輯法此外還可以確立

31、下列等價關系：此外還可以確立下列等價關系：p ( x) P(x) = ( x) P(x) p ( x) P(x) = ( x) P(x) p ( x) P(x) Q(x) = ( x) P(x) ( x) Q(x)p ( x) P(x) Q(x) = ( x) P(x) ( x) Q(x) p ( x) P(x) = ( y) P(y) p ( x) P(x) = ( y) P(y) 西安電子科技大學西安電子科技大學謂詞邏輯法v置換與合一置換與合一置換置換p 推理規(guī)則：推理規(guī)則：用合式公式的集合產(chǎn)生新的合式公式用合式公式的集合產(chǎn)生新的合式公式 假元推理假元推理 全稱化推理全稱化推理 綜合推理綜

32、合推理 W2W1 W1 W2 W(A)( x) W(x) 任意常量任意常量A W2(A) W1(A)( x) W1(x) W2(x)尋找尋找A對對x的的置置換換，使，使W1(A)與與W1(x)一致一致西安電子科技大學西安電子科技大學謂詞邏輯法v置換與合一置換與合一置換（置換（SubstitutionSubstitution）p置換的定義：置換的定義：置換是用置換是用變元、常量、函數(shù)變元、常量、函數(shù)來替換來替換變變元元，使該變元不在公式中出現(xiàn)使該變元不在公式中出現(xiàn)。p置換是形如置換是形如 t1/x1, t2/x2, ， tn/xn的有限集合。的有限集合。 t1，t2， ， tn是項是項 x1，x

33、2， ， xn是互不相同的變元是互不相同的變元 ti/xi表示用表示用ti項替換變元項替換變元xi，不允許，不允許ti和和xi相同，也相同，也不允許變元不允許變元xi循環(huán)地出現(xiàn)在另一個循環(huán)地出現(xiàn)在另一個tj中中西安電子科技大學西安電子科技大學謂詞邏輯法v置換與合一置換與合一置換（置換（SubstitutionSubstitution）p例如例如 a/x , f(b)/y ，w/z 是一個置換是一個置換 g(y)/x , f(x)/y 不是一個置換不是一個置換 g(a)/x , f(x)/y 不是一個置換不是一個置換西安電子科技大學西安電子科技大學謂詞邏輯法v置換與合一置換與合一置換（置換（Su

34、bstitutionSubstitution）p例例2.2（P40），表達式），表達式 Px, f(y), B的置換為的置換為 s1= z/x, w/y； s2= A/y；s3= q(z)/x , A/y； s4= c/x , A/y 用用Es表示一個表達式表示一個表達式E用置換用置換s所得到的表達式的置所得到的表達式的置換。于是，換。于是，Px, f(y), B的的4個置換如下：個置換如下： Px, f(y), B s1 = Pz, f(w), B Px, f(y), B s2 = Px, f(A), B Px, f(y), B s3 = Pq(z), f(A), B Px, f(y), B

35、 s4 = Pc, f(A), B 西安電子科技大學西安電子科技大學謂詞邏輯法v置換與合一置換與合一置換（置換（SubstitutionSubstitution）p置換是可結合的置換是可結合的用用s1s2表示兩個置換表示兩個置換s1和和s2的的合成合成，L表示一個表達表示一個表達式，則有式，則有 （Ls1）s2 = L（s1s2 ） 即用即用s1和和s2相繼作用于表達式相繼作用于表達式L是與用是與用s1s2作用于作用于L一樣的一樣的進一步推廣：（進一步推廣：（s1s2）s3 = s1（s2s3 ）p一般說來，置換是不可交換的，即一般說來，置換是不可交換的，即 s1s2 s2s1西安電子科技大學

36、西安電子科技大學謂詞邏輯法v置換與合一置換與合一合一（合一（UnificationUnification）p合一的定義：合一的定義：尋找項對變量的尋找項對變量的置換置換，以使，以使兩表達式一致兩表達式一致。p如果一個置換如果一個置換s作用于表達式集合作用于表達式集合Ei的每個元素，用的每個元素，用Eis表表示置換的集。稱表達式示置換的集。稱表達式Ei是是可合一可合一的，如果存在一個置換的，如果存在一個置換s使使得：得： E1s = E2s = E3s = 那么，稱此那么，稱此s為為Ei的的合一者合一者（unifier），因為），因為s的作用是使集的作用是使集合合Ei成為單一形式。成為單一形式。

37、p例如，設有公式集例如，設有公式集 E= P( x, y, f(y), P( a, g(x), z) 則下式是它的一個合一：則下式是它的一個合一： s=a/x, g(a)/y, f(g(a)/z西安電子科技大學西安電子科技大學謂詞邏輯法v 謂詞邏輯法舉例：謂詞邏輯法舉例：猴子和香蕉問題猴子和香蕉問題描述狀態(tài)的謂詞：描述狀態(tài)的謂詞：pAT(x, y)：x在在y處處pONBOX：猴子在箱子上猴子在箱子上pHB：猴子得到香蕉猴子得到香蕉個體域：個體域：px ：monkey, box, bananapy：a, b, c問題的初始狀態(tài)問題的初始狀態(tài)pAT(monkey, a) pAT(box, b)p

38、ONBOX p HB問題的目標狀態(tài)問題的目標狀態(tài)pAT(monkey, c) pAT(box, c)pONBOX pHB西安電子科技大學西安電子科技大學猴子和香蕉問題描述操作的謂詞描述操作的謂詞p Goto(u, v)：猴子從猴子從u處走到處走到v處處 條件：條件：ONBOX ，AT(monkey, u) 動作動作：刪除表：刪除表：AT(monkey, u)；添加表：；添加表：AT(monkey, v)pPushbox(v, w)：猴子推著箱子從猴子推著箱子從v處移到處移到w處處 條件：條件： ONBOX ，AT(monkey, v)，AT(box, v) 動作：動作：刪除表：刪除表：AT(monkey, v)，AT(box, v) 添加表：添加表：AT(monkey, w)，AT(box,w)pClimbbox：猴子爬上箱子猴子爬上箱子 條件：條件： ONBOX ，AT(monkey, w)，AT(box,w) 動作動作：刪除表：刪除表： ONBOX；添加表：；