人工智能學科體系ppt課件

1、人工智能學科體系人工智能學科體系 人工智能學科體系的層次人工智能學科體系的層次 人工智能實際根底人工智能實際根底 數(shù)學根底數(shù)學根底: :數(shù)理邏輯，計算的數(shù)學實際，離散數(shù)學數(shù)理邏輯，計算的數(shù)學實際，離散數(shù)學, ,模糊數(shù)學模糊數(shù)學 思想科學實際思想科學實際: :認知心思學認知心思學, ,邏輯或籠統(tǒng)思想學邏輯或籠統(tǒng)思想學, ,籠統(tǒng)籠統(tǒng)或直感思想學或直感思想學 計算機工程技術(shù)計算機工程技術(shù): :硬件硬件, ,軟件技術(shù)軟件技術(shù) 人工智能原理人工智能原理 知識的表達知識的表達, ,知識的處置知識的處置, ,知識的獲取與學習知識的獲取與學習, ,利用知利用知識求解問題識求解問題 人工智能工程系統(tǒng)人工智能工程

2、系統(tǒng) 專家咨詢系統(tǒng)專家咨詢系統(tǒng), ,專家系統(tǒng)開發(fā)工具與環(huán)境專家系統(tǒng)開發(fā)工具與環(huán)境, ,自然言語自然言語了解系統(tǒng)了解系統(tǒng), ,圖像了解與識別系統(tǒng)圖像了解與識別系統(tǒng), ,智能機器人系統(tǒng)智能機器人系統(tǒng)數(shù)理邏輯數(shù)理邏輯 數(shù)理邏輯：用數(shù)學方法來研討推理的方式構(gòu)造和數(shù)理邏輯：用數(shù)學方法來研討推理的方式構(gòu)造和推理規(guī)律的數(shù)學學科推理規(guī)律的數(shù)學學科 與數(shù)學其它分支、計算機科學、與數(shù)學其它分支、計算機科學、AIAI、言語學有親、言語學有親密的聯(lián)絡(luò)密的聯(lián)絡(luò) 數(shù)理邏輯的內(nèi)容數(shù)理邏輯的內(nèi)容 邏輯演算邏輯演算 命題邏輯命題邏輯 謂詞邏輯謂詞邏輯 證明論證明論 公理集合論公理集合論 遞歸論遞歸論 模型論模型論提綱提綱命題邏

3、輯命題邏輯:客觀世界的各種客觀世界的各種現(xiàn)實現(xiàn)實一階謂詞邏輯：邏輯論證一階謂詞邏輯：邏輯論證的符號化，可以表示復雜的符號化，可以表示復雜的問題具有較強的表達的問題具有較強的表達才干才干 用方式邏輯尤其是一階謂詞邏輯表示知識是用方式邏輯尤其是一階謂詞邏輯表示知識是AI 研討中提出運用的一種普遍方法。研討中提出運用的一種普遍方法。 命題邏輯和謂詞邏輯是最先運用于人工智能的兩命題邏輯和謂詞邏輯是最先運用于人工智能的兩種邏輯，謂詞邏輯是在命題邏輯根底上開展起來種邏輯，謂詞邏輯是在命題邏輯根底上開展起來的，命題邏輯可以看作是謂詞邏輯的一種特殊方的，命題邏輯可以看作是謂詞邏輯的一種特殊方式。式。一、命題邏

4、輯一、命題邏輯 命題命題 定義：可以判別真假的陳說句定義：可以判別真假的陳說句 真值真值 真：正確的判別真：正確的判別; ;真值真值1,T1,T 假：錯誤的判別假：錯誤的判別; ;真值真值0,F0,F 例子：例子： 2 2是素數(shù)是素數(shù) 雪是黑色的雪是黑色的 3 3可以被可以被2 2整除整除 地球以外的星球上也有人地球以外的星球上也有人一些不是命題的句子一些不是命題的句子 X+y5 X,y未知，真假不定未知，真假不定 這朵花多美呀！這朵花多美呀！ 感慨句感慨句 明天下午有會嗎？明天下午有會嗎？ 疑問句疑問句 請他把門關(guān)上！請他把門關(guān)上！ 祈使句祈使句判別能否為命題的方法判別能否為命題的方法 陳說

5、句陳說句 真值確定真值確定 真值是確定的真值是確定的 可以不知道可以不知道原子命題與命題符號化原子命題與命題符號化 原子命題簡單命題原子命題簡單命題 不可以再分解的命題不可以再分解的命題 命題符號化命題符號化 運用小寫的字母表示命題運用小寫的字母表示命題 放在命題的前面放在命題的前面 p,q,r, pi,qi,rip,q,r, pi,qi,ri p:2p:2是素數(shù)是素數(shù) 真命題真命題 q:q:雪是黑的雪是黑的 2 2假命題假命題命題常量和命題變量命題常量和命題變量 命題常量：其真值是確定的簡單命題命題常量：其真值是確定的簡單命題 命題變量命題變元命題變量命題變元 定義：真值不確定的簡單陳說句定

6、義：真值不確定的簡單陳說句 表示：也用小寫字母表示：表示：也用小寫字母表示：p,q,r, pi,qi,rip,q,r, pi,qi,ri 性質(zhì)：命題變量不是命題性質(zhì)：命題變量不是命題 例子：例子：X+y5X+y5復合命題復合命題 定義：由簡單命題用結(jié)合詞結(jié)合而成的命題定義：由簡單命題用結(jié)合詞結(jié)合而成的命題 例子例子 3 3不是偶數(shù)不是偶數(shù) 2 2是素數(shù)和偶數(shù)是素數(shù)和偶數(shù) 林芳學過英語或日語林芳學過英語或日語 假設(shè)角假設(shè)角A A和角和角B B是對頂角，那么角是對頂角，那么角A A和角和角B B相相等等否認、合取結(jié)合詞否認、合取結(jié)合詞 定義定義1 1：設(shè)：設(shè)p p為任一命題，復合命題為任一命題，復

7、合命題“非非p p稱為稱為p p的否認的否認式，記做式，記做pp。 為否認結(jié)合詞，為否認結(jié)合詞， p p為真當且僅當為真當且僅當p p為假。為假。 p:3p:3是偶數(shù)是偶數(shù) p:3p:3不是偶數(shù)不是偶數(shù) 定義定義2 2：設(shè)：設(shè)p,qp,q為二命題，復合命題為二命題，復合命題“p p并且并且q q稱作稱作p p和和q q的合取式，記做的合取式，記做pqpq， 為合取結(jié)合詞，為合取結(jié)合詞，pqpq為真當且為真當且僅當僅當p p，q q同時為真同時為真 p:p:李平聰明李平聰明 q:q:李平用功李平用功 pqpq：李平不但聰明，而且用功：李平不但聰明，而且用功 p qp q：李平聰明：李平聰明, ,

8、但不用功但不用功析取結(jié)合詞析取結(jié)合詞 定義定義3：設(shè)：設(shè)p,q為二命題，復合命題為二命題，復合命題“p或或q稱作稱作p和和q的析取式，記做的析取式，記做p q， 為析取結(jié)合詞，為析取結(jié)合詞， pq為真當且僅當為真當且僅當p和和q中至少有一個為真中至少有一個為真 p:李平聰明李平聰明 q:李平用功李平用功 pq：李平聰明或者用功：李平聰明或者用功 pq：李平聰明或者不用功：李平聰明或者不用功蘊涵結(jié)合詞蘊涵結(jié)合詞 定義定義4 4：設(shè)：設(shè)p,qp,q為二命題，復合命題為二命題，復合命題“假設(shè)假設(shè)p p，那么，那么q q稱稱作作p p和和q q的蘊涵式，記做的蘊涵式，記做pqpq， 為蘊涵結(jié)合詞，為蘊

9、涵結(jié)合詞， pq pq為假當且僅當為假當且僅當p p為真，為真，q q為假為假 假設(shè)假設(shè)pqpq為真，記做為真，記做p pq q，稱為定理，稱為定理 與自然言語不一樣，蘊涵式的前件和后件可以沒有內(nèi)在與自然言語不一樣，蘊涵式的前件和后件可以沒有內(nèi)在聯(lián)絡(luò)聯(lián)絡(luò) 例如：假設(shè)例如：假設(shè)2 22424，那么太陽從西邊出來，那么太陽從西邊出來 蘊涵式的真值表蘊涵式的真值表蘊涵結(jié)合詞蘊涵結(jié)合詞 將以下命題符號化將以下命題符號化 只需不下雨，我就騎自行車上班只需不下雨，我就騎自行車上班 只需不下雨，我才騎自行車上班只需不下雨，我才騎自行車上班 p:p:下雨下雨 q:q:騎自行車上班騎自行車上班 pqpq qp

10、qp等價結(jié)合詞等價結(jié)合詞 定義定義5 5：設(shè)：設(shè)p,qp,q為二命題，復合命題為二命題，復合命題“p p當且僅當當且僅當q q稱作稱作p p和和q q的等價式，記做的等價式，記做p p q q，為等價結(jié)合詞，為等價結(jié)合詞， p pq q為為假當且僅當假當且僅當p p與與q q的真值不一樣的真值不一樣 與自然言語不一樣，等價式的與自然言語不一樣，等價式的2 2個命題可以沒有內(nèi)在聯(lián)絡(luò)個命題可以沒有內(nèi)在聯(lián)絡(luò) 例如：例如：2 22424，當且僅當太陽從西邊出來，當且僅當太陽從西邊出來 蘊涵式的真值表蘊涵式的真值表邏輯結(jié)合詞的優(yōu)先級邏輯結(jié)合詞的優(yōu)先級命題符號化的例子命題符號化的例子 分析出簡單命題，將之

11、符號化分析出簡單命題，將之符號化 用結(jié)合詞將簡單命題結(jié)合起來，構(gòu)成復合命題的用結(jié)合詞將簡單命題結(jié)合起來，構(gòu)成復合命題的符號化符號化 例子：例子： 1 1：小王是游泳冠軍或是百米賽跑冠軍：小王是游泳冠軍或是百米賽跑冠軍 2 2：假設(shè)我上街，我就去書店看看，除非我很累：假設(shè)我上街，我就去書店看看，除非我很累 1 1：pq,pq,其中：其中：q:q:小王是游泳冠軍；小王是游泳冠軍；q:q:小王是百小王是百米賽跑冠軍米賽跑冠軍 2 2：r (pq),r (pq),其中其中p:p:我上街我上街,q:,q:我去書店看看我去書店看看, r:, r:我很累我很累命題公式及分類命題公式及分類 復合命題：復合命題

12、：p,pq, pq,pq,pp,pq, pq,pq,pq q 假設(shè)假設(shè)p,qp,q為命題常量，這些復合命題為命題為命題常量，這些復合命題為命題 假設(shè)假設(shè)p,qp,q為命題變量，這些復合命題為命題為命題變量，這些復合命題為命題公式公式 命題公式：由命題常量、命題變量、邏輯命題公式：由命題常量、命題變量、邏輯結(jié)合詞、括號等構(gòu)成的有效字符串結(jié)合詞、括號等構(gòu)成的有效字符串命題公式及分類命題公式及分類 定義定義6 6： 1. 1. 單個命題常項或變項單個命題常項或變項p,q,r,pi,qi,ri ,0,1p,q,r,pi,qi,ri ,0,1是是合式公式合式公式 2. 2. 假設(shè)假設(shè)A A是合式公式，那

13、么是合式公式，那么AA為合式公式為合式公式 3. 3. 假設(shè)假設(shè)A,BA,B是合式公式，那么是合式公式，那么ABAB, ,A A B B , ,ABAB , , A BA B也是合式公式也是合式公式 4. 4. 只需有限次地運用只需有限次地運用1 13 3組成的符號串才是合組成的符號串才是合式公式式公式 命題邏輯下的合式公式：命題公式，公式命題邏輯下的合式公式：命題公式，公式 例子：例子：q qvrq qvr公式的層次公式的層次 定義定義7 7 假設(shè)假設(shè)A A為單個命題常項或變項為單個命題常項或變項p,q,r,pi,qi, p,q,r,pi,qi, ri, ,0,1ri, ,0,1，那么稱，那

14、么稱A A為為0 0層公式層公式 稱稱A A是是n+1 (n=0)n+1 (n=0)層公式是指層公式是指A A符合以下情況之符合以下情況之一：一： A A B,B B,B為為n n層公式層公式 A A BC, BC, 其中其中B B，C C分別為分別為i,ji,j層公式，且層公式，且n= n= max(i,j)max(i,j) A A BC, BC, 其中其中B,CB,C的層次同的層次同2 2 A A B C, B C, 其中其中B,CB,C的層次同的層次同2 2 A A B B C, C, 其中其中B,CB,C的層次同的層次同2 2命題公式的賦值或解釋命題公式的賦值或解釋 命題公式中命題常項

15、和變項，不是命題，只需對命題公式中命題常項和變項，不是命題，只需對命題公式中的一切命題變項進展賦值，公式的真命題公式中的一切命題變項進展賦值，公式的真值才可以確定下來，才可以變成命題值才可以確定下來，才可以變成命題 定義定義8 8： 設(shè)設(shè)A A為一個命題公式，為一個命題公式，p1,p2,pnp1,p2,pn為出如今為出如今A A中中的一切命題變項，給指定一組真值，稱為對的一切命題變項，給指定一組真值，稱為對A A的的一個賦值或解釋。假設(shè)指定的一組值使一個賦值或解釋。假設(shè)指定的一組值使A A的值為的值為真，那么稱這組值為成真賦值，假設(shè)指定的一組真，那么稱這組值為成真賦值，假設(shè)指定的一組值使值使A

16、 A的值為假，那么稱這組值為成假賦值。的值為假，那么稱這組值為成假賦值。公式的真值表公式的真值表 真值表：含有真值表：含有n n個變項的公式，其賦值有個變項的公式，其賦值有2n2n個，個，將每一個賦值及公式在此賦值下的真值構(gòu)成的表將每一個賦值及公式在此賦值下的真值構(gòu)成的表 例子例子: (p(pq) q: (p(pq) q公式的性質(zhì)公式的性質(zhì) 定義定義9 9 設(shè)設(shè)A A為一個命題公式為一個命題公式 假設(shè)假設(shè)A A在它的各種賦值下取值均為真，那么稱在它的各種賦值下取值均為真，那么稱A A為重言式或永真式真值表最后一列全為為重言式或永真式真值表最后一列全為1 1 假設(shè)假設(shè)A A在它的各種賦值下取值均

17、為假，那么稱在它的各種賦值下取值均為假，那么稱A A為矛盾式或永假式真值表最后一列全為為矛盾式或永假式真值表最后一列全為0 0 假設(shè)假設(shè)A A至少存在一組賦值是成真賦值，那么稱至少存在一組賦值是成真賦值，那么稱A A為可滿足式真值表最后一列有為可滿足式真值表最后一列有1 1等值演算等值演算 判別公式性質(zhì)的方法判別公式性質(zhì)的方法 真值表真值表 等值演算將之演算成簡單方式，判別其性質(zhì)等值演算將之演算成簡單方式，判別其性質(zhì) 定義定義1010 設(shè)設(shè)A,BA,B為為2 2個命題公式，假設(shè)等價式個命題公式，假設(shè)等價式A BA B是重言是重言式，那么稱式，那么稱A A與與B B是等值的，記做是等值的，記做A

18、 BA B ：不是邏輯結(jié)合詞，一個等值的記號，不可以：不是邏輯結(jié)合詞，一個等值的記號，不可以用數(shù)值上的相等替代用數(shù)值上的相等替代 等值本質(zhì)上是指：公式等值本質(zhì)上是指：公式A A和和B B在任何解釋下都相在任何解釋下都相等等邏輯等值式邏輯等值式邏輯等值式邏輯等值式邏輯等值式邏輯等值式等值演算等值演算 利用等值式，將一個公式變換成另外一種方式的利用等值式，將一個公式變換成另外一種方式的過程過程 例子例子等值演算等值演算等值演算等值演算簡單析取式及簡單合取式簡單析取式及簡單合取式 簡單析取式和簡單合取式簡單析取式和簡單合取式 定義定義1010：僅由有限個命題變項或其否認構(gòu)成的析：僅由有限個命題變項或

19、其否認構(gòu)成的析取式稱為，簡單析取式；僅由有限個命題變項或取式稱為，簡單析取式；僅由有限個命題變項或其否認構(gòu)成的合取式稱為，簡單合取式其否認構(gòu)成的合取式稱為，簡單合取式 例子：例子： 簡單析取式：簡單析取式： p, q, pq, pq, pqrp, q, pq, pq, pqr 簡單合取式：簡單合取式： p, q, pq, pq, pqrp, q, pq, pq, pqr合取范式合取范式 定義定義1111： 僅有有限個簡單析取式構(gòu)成的合取式稱為僅有有限個簡單析取式構(gòu)成的合取式稱為合取范式合取范式 A=A1A2AnA=A1A2An 其中其中A1A1，A2A2，AnAn為簡單析取式為簡單析取式 例子

20、：例子： A=(pqr)(pq)(qq)A=(pqr)(pq)(qq) 任何公式都有與其對應(yīng)的合取范式任何公式都有與其對應(yīng)的合取范式化成合取范式的步驟化成合取范式的步驟 1. 消去對消去對，來說冗余的結(jié)合詞來說冗余的結(jié)合詞 2. 否認結(jié)合詞的消除或內(nèi)移否認結(jié)合詞的消除或內(nèi)移 3. 利用分配率利用分配率合取范式合取范式 原子：命題常項或變項原子：命題常項或變項 文字：原子或原子的否認文字：原子或原子的否認 子句：文字的析取子句：文字的析取 合取范式：子句的合取合取范式：子句的合取 子句集：合取范式的集合表示子句集：合取范式的集合表示 每一個合取項作為集合的元素每一個合取項作為集合的元素 元素之間

21、的關(guān)系為合取元素之間的關(guān)系為合取命題邏輯的問題命題邏輯的問題 命題作為命題演算的根本單位，不再分解命題作為命題演算的根本單位，不再分解 無法研討命題內(nèi)部的構(gòu)造和命題之間的聯(lián)絡(luò)無法研討命題內(nèi)部的構(gòu)造和命題之間的聯(lián)絡(luò) 例子：蘇格拉底三段論例子：蘇格拉底三段論 p:p:凡人都是要死的凡人都是要死的 q:q:蘇格拉底是人蘇格拉底是人 r: r:蘇格拉底是要死的蘇格拉底是要死的 命題符號化：命題符號化： (pq)r (pq)r 真值不定！真值不定！ 處理問題的方法處理問題的方法 將命題進一步分解成：個體詞，謂詞和量詞等將命題進一步分解成：個體詞，謂詞和量詞等 研討它們的方式構(gòu)造和邏輯關(guān)系，總結(jié)出正確地推

22、理方研討它們的方式構(gòu)造和邏輯關(guān)系，總結(jié)出正確地推理方式和規(guī)那么式和規(guī)那么 一階謂詞邏輯一階謂詞邏輯二、一階謂詞邏輯二、一階謂詞邏輯 簡單命題的分解：個體詞和謂詞簡單命題的分解：個體詞和謂詞 個體詞個體詞 指可以獨立存在的客體指可以獨立存在的客體 可以表示詳細的事物：李明，玫瑰花，自然數(shù)可以表示詳細的事物：李明，玫瑰花，自然數(shù) 可以表示籠統(tǒng)的概念：思想可以表示籠統(tǒng)的概念：思想 謂詞謂詞 用于描寫個體詞的性質(zhì)或個體詞之間的關(guān)系的詞用于描寫個體詞的性質(zhì)或個體詞之間的關(guān)系的詞 2 2是有理數(shù)，是有理數(shù)， 是有理數(shù)是有理數(shù) 小李比小王高，小李比小王高， 比比高高個體常項、個體變項和個體域個體常項、個體變

23、項和個體域 個體常項個體常項 定義：表示詳細或特定的詞定義：表示詳細或特定的詞 表示：小寫的英文字母表示：小寫的英文字母a,b,c,a,b,c,表示表示 個體確定下來個體確定下來 個體變項個體變項 定義：泛指的個體的詞定義：泛指的個體的詞 表示：小寫的英文字母表示：小寫的英文字母x,y,z,x,y,z,表示表示 個體沒有確定下來個體沒有確定下來 個體域個體域 個體變項的取值范圍個體變項的取值范圍 可以是一個有限的集合可以是一個有限的集合a,b,ca,b,c 也可以是一個無限的集合：全體自然數(shù)，全體實數(shù)也可以是一個無限的集合：全體自然數(shù)，全體實數(shù) 全總個體域：宇宙間的一切事物組成的個體域全總個體

24、域：宇宙間的一切事物組成的個體域謂詞常項、謂詞變項謂詞常項、謂詞變項 謂詞常項謂詞常項 定義：表示詳細性質(zhì)或關(guān)系的詞定義：表示詳細性質(zhì)或關(guān)系的詞 表示：大寫英文字母表示：大寫英文字母F,G,H,F,G,H, 謂詞變項謂詞變項 定義：表示籠統(tǒng)或泛指的性質(zhì)或關(guān)系的詞定義：表示籠統(tǒng)或泛指的性質(zhì)或關(guān)系的詞 表示：大寫英文字母表示：大寫英文字母F,G,H,F,G,H, F(x): x F(x): x很高，很高，x x是無理數(shù)是無理數(shù),;,; L(x,y):x L(x,y):x比比y y學習好學習好, x, x比比y y大大,;,;謂詞的元數(shù)謂詞的元數(shù) 謂詞的元數(shù)：謂詞中包含的個體詞的個數(shù)謂詞的元數(shù)：謂詞

25、中包含的個體詞的個數(shù) n n元謂詞：包含有元謂詞：包含有n n個個體詞的謂詞個個體詞的謂詞 F(x)F(x)一元謂詞一元謂詞 L(x,y)L(x,y)二元謂詞二元謂詞 有時有時n n元謂詞：包含有元謂詞：包含有n n個個體變項的謂詞個個體變項的謂詞 F(a): 0F(a): 0元謂詞元謂詞 L(x,a):1L(x,a):1元謂詞元謂詞謂詞符號化的例子謂詞符號化的例子 2是素數(shù)且是偶數(shù)是素數(shù)且是偶數(shù) F(x): x是素數(shù)是素數(shù);G(x)：x是偶數(shù)是偶數(shù) a:2 F(a)G(a) 假設(shè)假設(shè)2大于大于3，那么，那么2大于大于4 L(x,y): x大于大于y a:2; b:3 ; c:4 L(a,b)

26、L(b,c)全稱量詞和存在量詞全稱量詞和存在量詞 謂詞符號化下面的句子謂詞符號化下面的句子 一切的人都是要死的一切的人都是要死的 有的人活到有的人活到100100歲以上歲以上 量詞：表示數(shù)量的詞量詞：表示數(shù)量的詞 全稱量詞全稱量詞 對應(yīng)于日常言語中的對應(yīng)于日常言語中的“一切，一切，“恣意的恣意的， “一切的一切的 表示：表示： xF(x xF(x全稱量詞和存在量詞全稱量詞和存在量詞 存在量詞存在量詞 對應(yīng)于日常言語中的對應(yīng)于日常言語中的“存在著，存在著，“有一有一個，個，“至少一個等詞至少一個等詞 表示：表示： xF(x) xF(x)謂詞符號化的例子謂詞符號化的例子 一切的人都是要死的一切的人

27、都是要死的 定義謂詞：定義謂詞：F(xF(x，x x是要死的是要死的 個體域為全體人類時：個體域為全體人類時： xF(x xF(x 全總個體域全總個體域( (沒有聲明個體域沒有聲明個體域) )： x(M(x) F(x) x(M(x) F(x) 特性謂詞：特性謂詞：M(x)M(x) 有的人活到有的人活到100100歲以上歲以上 定義謂詞：定義謂詞：G(xG(xx x活到活到100100歲以上歲以上 個體域為全體人類時：個體域為全體人類時： xG(x xG(x 全總個體域全總個體域( (沒有聲明個體域沒有聲明個體域) )： x(M(x)G(x) x(M(x)G(x)量詞運用的本卷須知量詞運用的本卷

28、須知1. 不同的個體域，符號化的方式能夠不一樣不同的個體域，符號化的方式能夠不一樣2. 假設(shè)沒有給出個體域，都應(yīng)以全總個體域為個假設(shè)沒有給出個體域，都應(yīng)以全總個體域為個體域體域3. 引入特性謂詞后，運用全稱量詞和存在量詞符引入特性謂詞后，運用全稱量詞和存在量詞符號化的方式不一樣號化的方式不一樣4. 個體詞和謂詞的涵義確定之后，個體詞和謂詞的涵義確定之后，n元謂詞轉(zhuǎn)化成元謂詞轉(zhuǎn)化成命題至少要命題至少要n個量詞個量詞量詞運用的本卷須知量詞運用的本卷須知5. 當個體域為有限集時，當個體域為有限集時，D=a1,a2,an,由由量詞的意義可以看出，對于恣意的謂詞量詞的意義可以看出，對于恣意的謂詞F(x)

29、，都有都有 xF(x) F(a1)F(a2)F(an) xF(x) F(a1)F(a2)F(an)6. 多個量詞同時出現(xiàn)，不可以隨意顛倒它們的次多個量詞同時出現(xiàn)，不可以隨意顛倒它們的次序序 x yH(x, y) x yH(x, y)一階謂詞邏輯中的命題符號化一階謂詞邏輯中的命題符號化 凡是有理數(shù)都可以表示成分數(shù)凡是有理數(shù)都可以表示成分數(shù) 不用引入特性謂詞的情況不用引入特性謂詞的情況 xF(x) xF(x) 引入特性謂詞的情況引入特性謂詞的情況 x(R(x) F(x) x(R(x) F(x)一階謂詞邏輯中的命題符號化一階謂詞邏輯中的命題符號化 沒有不犯錯誤的人沒有不犯錯誤的人 沒有指定個體域，以

30、全總個體域作為個體域沒有指定個體域，以全總個體域作為個體域 謂詞：謂詞：M(x) xM(x) x是人；是人；F(x): xF(x): x犯錯誤犯錯誤 x(M(x)F(x) x(M(x)F(x) 在北京任務(wù)的人未必是北京人在北京任務(wù)的人未必是北京人 F(x): xF(x): x在北京任務(wù)；在北京任務(wù)； G(x): x G(x): x是北京人是北京人 x(F(x)G(x) x(F(x)G(x)謂詞公式的字母表謂詞公式的字母表 定義定義11 11 字母表字母表 個體常項個體常項:a,b,c, ai,bi,ci, i=1:a,b,c, ai,bi,ci, i=1 個體變項個體變項:x,y,z, xi,

31、yi,zi, i=1:x,y,z, xi,yi,zi, i=1 函數(shù)符號函數(shù)符號:f,g,h, fi,gi,hi, i=1:f,g,h, fi,gi,hi, i=1 謂詞符號謂詞符號:F,G,H, Fi,Gi,Hi, i=1:F,G,H, Fi,Gi,Hi, i=1 量詞符號量詞符號: , : , 結(jié)合詞符：結(jié)合詞符： , , , , , , , , 逗號和括號：逗號和括號： ，項的遞歸定義項的遞歸定義 定義定義1212 1. 1. 個體常項和變項是項個體常項和變項是項 2. 2. 假設(shè)假設(shè)(x1,x2,xn)(x1,x2,xn)是恣意的是恣意的n n元函數(shù)，元函數(shù)，x1,x2,xnx1,x2

32、,xn是項，那么是項，那么(x1,x2,xn)(x1,x2,xn)是是項項 3. 3. 只需有限次地運用只需有限次地運用1 1，2 2生成的符號才是生成的符號才是項項 a,b,x,y, f(x,y), f(x,g(a,b,z)a,b,x,y, f(x,y), f(x,g(a,b,z)合式公式謂詞公式合式公式謂詞公式 原子公式原子公式 定義定義1313：設(shè)：設(shè)R(x1,x2,.,xn)R(x1,x2,.,xn)是恣意的是恣意的n n元謂詞，元謂詞，t1,t2,tnt1,t2,tn為項，那么為項，那么R(t1,t2,tn)R(t1,t2,tn)稱為原子公稱為原子公式式 合式公式，定義合式公式，定義

33、1414： 1. 1. 原子公式是合式公式原子公式是合式公式 2. 2. 假設(shè)假設(shè)A A是合式公式，那么是合式公式，那么AA為合式公式為合式公式 3. 3. 假設(shè)假設(shè)A,BA,B是合式公式，那么是合式公式，那么ABAB, ,A A B B , , ABAB , , A BA B也是合式公式也是合式公式 4. 4. 假設(shè)假設(shè)A A是合式公式，那么是合式公式，那么 xA xA， xA xA也是合式也是合式公式公式 5. 5. 只需有限次地運用只需有限次地運用1 14 4組成的符號串才是合組成的符號串才是合式公式謂詞公式式公式謂詞公式指點變項、轄域指點變項、轄域 定義定義1515：在合式公式：在合式

34、公式 xA xA和和 xA xA中，稱中，稱x x為指為指點變項，稱點變項，稱A A為相應(yīng)量詞的轄域。在轄域中，為相應(yīng)量詞的轄域。在轄域中，x x的的一切出現(xiàn)稱為約束出現(xiàn)即一切出現(xiàn)稱為約束出現(xiàn)即x x受相應(yīng)量詞指點變受相應(yīng)量詞指點變項的約束，項的約束，A A中不是約束出現(xiàn)的其它變項稱為中不是約束出現(xiàn)的其它變項稱為自在出現(xiàn)。自在出現(xiàn)。 通常用通常用A(x)A(x)表示表示x x是自在出現(xiàn)的恣意公式是自在出現(xiàn)的恣意公式 例子例子 x(F(x) yH(x,y) x(F(x) yH(x,y) xF(x)G(x,y) xF(x)G(x,y) x y(R(x,y)L(y,z) xH(x,y) x y(R(

35、x,y)L(y,z) xH(x,y)閉式閉式 定義定義1616：設(shè)：設(shè)A A為任一公式，假設(shè)為任一公式，假設(shè)A A中無自在中無自在出現(xiàn)的個體變項，那么稱出現(xiàn)的個體變項，那么稱A A是封鎖的合式公是封鎖的合式公式，簡稱閉式。式，簡稱閉式。 例子：例子：換名規(guī)那么和替代規(guī)那么換名規(guī)那么和替代規(guī)那么 為了防止出現(xiàn)某個變項既是自在出現(xiàn)的又是約束為了防止出現(xiàn)某個變項既是自在出現(xiàn)的又是約束出現(xiàn)的，運用以下出現(xiàn)的，運用以下2 2種方法種方法 換名規(guī)那么：將量詞轄域種出現(xiàn)的某個約束出現(xiàn)換名規(guī)那么：將量詞轄域種出現(xiàn)的某個約束出現(xiàn)的個體變項及對應(yīng)的指點變項，改成另外一個轄的個體變項及對應(yīng)的指點變項，改成另外一個轄

36、域中未曾出現(xiàn)過的個體變項符號，公式其它部分域中未曾出現(xiàn)過的個體變項符號，公式其它部分不變不變 xF(x)G(x,y) zF(z)G(x,y) xF(x)G(x,y) zF(z)G(x,y) 替代規(guī)那么：對某個自在出現(xiàn)的個體變項用與原替代規(guī)那么：對某個自在出現(xiàn)的個體變項用與原公式中的一切個體變項符號不同的變項符號來替公式中的一切個體變項符號不同的變項符號來替代，且處處替代代，且處處替代 xF(x)G(x,y) xF(x)G(z,y) xF(x)G(x,y) xF(x)G(z,y)公式的解釋公式的解釋 公式的解釋：一階謂詞公式中含有：個體常項，個體變項自在出現(xiàn)或約束出現(xiàn)的，函數(shù)變項，謂詞變項等。對

37、各種變項指定特殊的常項來替代，就構(gòu)成公式的一個解釋。 解釋，定義17 一個解釋I由下面的4個部分構(gòu)成 1. 非空個體域D 2. D上的一部分特定的元素 3. D上的一些特定的函數(shù) 4. D上的一些特定的謂詞解釋的例子解釋的例子 解釋解釋 DI=2,3DI=2,3 DIDI上的特定元素上的特定元素 函數(shù)：函數(shù)：f(2)=3,f(3)=2f(2)=3,f(3)=2 謂詞：謂詞：F(2)=0;f(3)=1F(2)=0;f(3)=1 G(x,y) G(x,y)為為G(i,j)=1, i,j=2,3;G(i,j)=1, i,j=2,3; L(x,y) L(x,y)為為L(2,2)=L(3,3)=1L(2

38、,2)=L(3,3)=1 L(3,2)=L(2,3)=0; L(3,2)=L(2,3)=0; 公式的解釋公式的解釋公式的性質(zhì)公式的性質(zhì) 定義定義1818 設(shè)設(shè)A A為一個公式為一個公式( (謂詞公式謂詞公式) ) 假設(shè)假設(shè)A A在它的任何解釋下取值均為真，那么在它的任何解釋下取值均為真，那么稱稱A A為邏輯有效式或永真式為邏輯有效式或永真式 假設(shè)假設(shè)A A在它的任何解釋下取值均為假，那么在它的任何解釋下取值均為假，那么稱稱A A為矛盾式或永假式為矛盾式或永假式 假設(shè)假設(shè)A A至少存在一組解釋是成真賦值，那么至少存在一組解釋是成真賦值，那么稱稱A A為可滿足式為可滿足式代換實例代換實例 定義定義

39、1919：設(shè)：設(shè)A0A0是含命題變項是含命題變項p1,p2,pnp1,p2,pn的命題的命題公式，公式，A1,A2,AnA1,A2,An是是n n個謂詞公式，用個謂詞公式，用Ai(i=1n)Ai(i=1n)處處替代處處替代pipi，所得到的公式稱為，所得到的公式稱為A0A0的的代換實例代換實例 例子例子 命題公式：命題公式：pqpq A1 xF(x) A1 xF(x) A2 G(x,y) A2 G(x,y) 代換實例：代換實例： ( xF(x)G(x,y) ( xF(x)G(x,y)代換實例的一個結(jié)論代換實例的一個結(jié)論 命題公式的重言式的代換實例在謂詞邏輯中，依然是重言式； 命題公式的矛盾式的

40、代換實例在謂詞邏輯中，依然是矛盾式； 例子：一階邏輯等值式一階邏輯等值式 定義定義2020：設(shè)：設(shè)A,BA,B是一階邏輯中的恣意是一階邏輯中的恣意2 2公式，假公式，假設(shè)設(shè)A BA B是邏輯有效式，那么稱是邏輯有效式，那么稱A A與與B B是等值的，是等值的，記做記做A BA B，稱，稱A BA B為等值式為等值式 命題邏輯中的命題邏輯中的2424條等值式的代換實例也是邏輯等條等值式的代換實例也是邏輯等值式值式謂詞邏輯中的邏輯等值式謂詞邏輯中的邏輯等值式1 定理定理1：量詞否認等值式：量詞否認等值式謂詞邏輯中的邏輯等值式謂詞邏輯中的邏輯等值式2 定理定理2 2：量詞的轄域收縮和擴張等值式：量詞

41、的轄域收縮和擴張等值式謂詞邏輯中的邏輯等值式謂詞邏輯中的邏輯等值式3 定理定理3 3：量詞分配等值式：量詞分配等值式謂詞邏輯中的邏輯等值式謂詞邏輯中的邏輯等值式4 定理定理4 4 量詞的性質(zhì)一樣，可以交換位置量詞的性質(zhì)一樣，可以交換位置 量詞的性質(zhì)不同，不可交換位置量詞的性質(zhì)不同，不可交換位置前束范式前束范式 定義定義2121：設(shè)：設(shè)A A為一謂詞公式，假設(shè)為一謂詞公式，假設(shè)A A具有如具有如下方式：下方式： Q1x1Q2x2QkxkB Q1x1Q2x2QkxkB 那么稱那么稱A A是前束范式。其中每一個是前束范式。其中每一個QiQi為為 或或 B B為不含量詞的謂詞公式母式為不含量詞的謂詞公

42、式母式 例如：例如： x y(F(x,y)G(x,y) x y(F(x,y)G(x,y) 前束范式前束范式 x(F(x) y(G(y)H(x) x(F(x) y(G(y)H(x) 非前束范式非前束范式前束范式例題前束范式例題 求以下公式的前束范式求以下公式的前束范式謂詞公式的合取范式和子句集謂詞公式的合取范式和子句集 對任一公式對任一公式 量詞轄域擴張和收縮定理，得到前束范式量詞轄域擴張和收縮定理，得到前束范式 對于母式，等值演算得到合取范式對于母式，等值演算得到合取范式 合取項的集合，構(gòu)成了該公式的子句集合取項的集合，構(gòu)成了該公式的子句集S S 前束范式前束范式 母式母式 原子：謂詞原子：謂

43、詞 文字：謂詞或謂詞的否認文字：謂詞或謂詞的否認 子句：文字的析取子句：文字的析取 合取范式：子句的合取合取范式：子句的合取 子句集：合取范式的集合方式，元素之間的關(guān)系子句集：合取范式的集合方式，元素之間的關(guān)系為合取關(guān)系為合取關(guān)系 一階謂詞邏輯一階謂詞邏輯 語法和語義：謂詞邏輯的根本組成、語法和語義：謂詞邏輯的根本組成、謂詞符號、常量符號、變量符號、謂詞符號、常量符號、變量符號、函數(shù)符號、項的遞歸定義、原子、函數(shù)符號、項的遞歸定義、原子、謂詞演算言語的語義謂詞演算言語的語義 連詞和量詞：適宜公式、連詞、合連詞和量詞：適宜公式、連詞、合取、析取、蘊含、否認、等價、命取、析取、蘊含、否認、等價、命

44、題演算、全稱量詞、存在量詞、約題演算、全稱量詞、存在量詞、約束變量、自在變量、句子、一階謂束變量、自在變量、句子、一階謂詞演算詞演算表示方法表示方法 邏輯表示法邏輯表示法 謂詞邏輯的根本組成：謂詞符號、變量符號、函謂詞邏輯的根本組成：謂詞符號、變量符號、函數(shù)符號和常量符號，并用圓括弧、方括弧、花括數(shù)符號和常量符號，并用圓括弧、方括弧、花括弧和逗號隔開，以表示論域內(nèi)的關(guān)系?；『投禾柛糸_，以表示論域內(nèi)的關(guān)系。 謂詞符號：表示個體所具有的性質(zhì)，或者假設(shè)干謂詞符號：表示個體所具有的性質(zhì)，或者假設(shè)干個體之間的關(guān)系的符號。習慣用大寫字母個體之間的關(guān)系的符號。習慣用大寫字母P，Q，R或或GREATER，LO

45、VE表示。表示。 常量符號：用來表示論域內(nèi)的物體或?qū)嶓w，它可常量符號：用來表示論域內(nèi)的物體或?qū)嶓w，它可以是實踐的物體和人，也可以是概念或具有名字以是實踐的物體和人，也可以是概念或具有名字的任何事情。普通用英文字母表中前幾個帶下標的任何事情。普通用英文字母表中前幾個帶下標或不帶下標的小寫字母表示。如或不帶下標的小寫字母表示。如a，b，. ，a1，b2，c3，. 。 變量符號：不用明確涉及是哪一個實體。習慣上變量符號：不用明確涉及是哪一個實體。習慣上用帶下標或不帶下標的小寫字母表示。如用帶下標或不帶下標的小寫字母表示。如x，y，. ，x1，y2， 。 函數(shù)符號：表示論域內(nèi)的函數(shù)。習慣用小寫字母函數(shù)

46、符號：表示論域內(nèi)的函數(shù)。習慣用小寫字母f，g，h表示。表示。例如，要表示例如，要表示“機器人機器人ROBOT在在1號房間號房間ROOM1內(nèi)，簡單的原子公式如下：內(nèi)，簡單的原子公式如下：INROOMROBOT，r1式中，式中，INROOM為謂詞符號，為謂詞符號，ROBOT和和r1為常量符為常量符號。號。 又如，要表示又如，要表示“李李LI的母親與他的父親結(jié)婚，的母親與他的父親結(jié)婚， 原子公式如下：原子公式如下：MARRIEDfatherLI，motherLI式中，函數(shù)符號式中，函數(shù)符號mother、father分別用來表示某人與分別用來表示某人與他她的母親、父親之間的映射。他她的母親、父親之間的

47、映射。 謂詞演算言語的語義：謂詞演算言語的語義： 對于每個謂詞符號，必需規(guī)定定義域內(nèi)的對于每個謂詞符號，必需規(guī)定定義域內(nèi)的一個相應(yīng)關(guān)系；一個相應(yīng)關(guān)系； 對于每個常量符號，必需規(guī)定定義域內(nèi)相對于每個常量符號，必需規(guī)定定義域內(nèi)相應(yīng)的一個實體；應(yīng)的一個實體； 對于每個函數(shù)符號，必需規(guī)定定義域內(nèi)相對于每個函數(shù)符號，必需規(guī)定定義域內(nèi)相應(yīng)的一個函數(shù)。應(yīng)的一個函數(shù)。 對于已定義了的某個解釋的一個原子公式，對于已定義了的某個解釋的一個原子公式，只需當其對應(yīng)的語句在定義域內(nèi)為真時，只需當其對應(yīng)的語句在定義域內(nèi)為真時，才具有值才具有值T真；而當其對應(yīng)的語句在定真；而當其對應(yīng)的語句在定義域內(nèi)為假時，該原子公式才具有

48、值義域內(nèi)為假時，該原子公式才具有值F假。因此，假。因此，INROOMROBOT，r1具有值具有值T，而，而INROOMROBOT，r2那那么具有值么具有值F。 當一個原子公式含變量符號時，對定義域當一個原子公式含變量符號時，對定義域內(nèi)實體的變量能夠有幾個設(shè)定。對某幾個內(nèi)實體的變量能夠有幾個設(shè)定。對某幾個設(shè)定的變量，原子公式取值設(shè)定的變量，原子公式取值T；而對另外幾；而對另外幾個設(shè)定的變量，原子公式取值個設(shè)定的變量，原子公式取值F。表示方法表示方法 邏輯表示法邏輯表示法 一階謂詞邏輯是謂詞邏輯中最直觀的一種邏輯。一階謂詞邏輯是謂詞邏輯中最直觀的一種邏輯。它以謂詞方式來表示動作的主題、客體?？腕w它

49、以謂詞方式來表示動作的主題、客體。客體可以多個?？梢远鄠€。如：張三與李四打網(wǎng)球如：張三與李四打網(wǎng)球Zhang and Li play tennis，可寫為：，可寫為：play (Zhang, Li, tennis)這里謂詞是這里謂詞是play，動詞主體是，動詞主體是Zhang和和 Li，而客體是而客體是tennis。 謂詞邏輯規(guī)范表達式：謂詞邏輯規(guī)范表達式：P ( x1, x2, x3, )， 這里這里P是謂詞是謂詞, xi是主體是主體與客體。與客體。表示方法表示方法 邏輯表示法邏輯表示法 謂詞比命題更加細致地描寫知識：謂詞比命題更加細致地描寫知識： 表達才干強表達才干強 如：北京是個城市，如

50、：北京是個城市， City(x)把城市這個概念分割出來。把把城市這個概念分割出來。把“城市城市 與與“北京兩個概念銜接在一同，而且闡北京兩個概念銜接在一同，而且闡明明“北京是北京是“城市的子概念。有層城市的子概念。有層 謂詞可以代表變化的情況謂詞可以代表變化的情況 如：如：City(北京北京),真。真。 City(煤球煤球)，假，假表示方法表示方法 邏輯表示法邏輯表示法在不同的知識之間建立聯(lián)絡(luò)在不同的知識之間建立聯(lián)絡(luò)如：如：Human(x) Lawed(x)， 人人都受人人都受法律控制，法律控制，x是同一個人。是同一個人。 Commit(x) Punished(x)， x不一定是不一定是人也可

51、以是動物。人也可以是動物。 而，而，Human(x) Lawed(x)commit(x) Punished(x)， 意為假設(shè)由于某個意為假設(shè)由于某個x是人而受法律控制，是人而受法律控制，那么這個人犯了罪就一定要遭到懲罰。那么這個人犯了罪就一定要遭到懲罰。表示方法表示方法 邏輯表示法邏輯表示法 謂詞邏輯法是運用最廣的方法之一，其緣由是：謂詞邏輯法是運用最廣的方法之一，其緣由是： 謂詞邏輯與數(shù)據(jù)庫，特別是關(guān)系數(shù)據(jù)庫就有親謂詞邏輯與數(shù)據(jù)庫，特別是關(guān)系數(shù)據(jù)庫就有親密的關(guān)系。在關(guān)系數(shù)據(jù)庫中，邏輯代數(shù)表達式密的關(guān)系。在關(guān)系數(shù)據(jù)庫中，邏輯代數(shù)表達式是謂詞表達式之一。因此，假設(shè)采用謂詞邏輯是謂詞表達式之一。因

52、此，假設(shè)采用謂詞邏輯作為系統(tǒng)的實際背景，那么可將數(shù)據(jù)庫系統(tǒng)擴作為系統(tǒng)的實際背景，那么可將數(shù)據(jù)庫系統(tǒng)擴展改呵斥知識庫。展改呵斥知識庫。 一階謂詞邏輯具有完備的邏輯推理算法。假設(shè)一階謂詞邏輯具有完備的邏輯推理算法。假設(shè)對邏輯的某些外延擴展后，那么可把大部分的對邏輯的某些外延擴展后，那么可把大部分的知識表達成一階謂詞邏輯的方式。知識易表知識表達成一階謂詞邏輯的方式。知識易表達達 表示方法表示方法 邏輯表示法邏輯表示法 謂詞邏輯法是運用最廣的方法之一，其緣由是：謂詞邏輯法是運用最廣的方法之一，其緣由是： 謂詞邏輯本身具有比較扎實的數(shù)學根底，知識謂詞邏輯本身具有比較扎實的數(shù)學根底，知識的表達方式?jīng)Q議了系

53、統(tǒng)的主要構(gòu)造。因此，對的表達方式?jīng)Q議了系統(tǒng)的主要構(gòu)造。因此，對知識表達方式的嚴密科學性要求就比較容易得知識表達方式的嚴密科學性要求就比較容易得到滿足。這樣對方式實際的擴展導致了整個系到滿足。這樣對方式實際的擴展導致了整個系統(tǒng)框架的開展。統(tǒng)框架的開展。 邏輯推理是公理集合中演繹而得出結(jié)論的過程。邏輯推理是公理集合中演繹而得出結(jié)論的過程。由于邏輯及方式系統(tǒng)具有的重要性質(zhì)，可以保由于邏輯及方式系統(tǒng)具有的重要性質(zhì)，可以保證知識庫中新舊知識在邏輯上的一致性或經(jīng)證知識庫中新舊知識在邏輯上的一致性或經(jīng)過相應(yīng)的一套處置過程檢驗、和所演繹出來過相應(yīng)的一套處置過程檢驗、和所演繹出來的結(jié)論的正確性。而其它的表示方法

54、在這點上的結(jié)論的正確性。而其它的表示方法在這點上還不能與其相比。還不能與其相比。 表示方法表示方法 邏輯表示法邏輯表示法 為此邏輯表示法在實踐人工智能系統(tǒng)上為此邏輯表示法在實踐人工智能系統(tǒng)上得到運用。得到運用。存在問題：存在問題：謂詞表示越細，推理越慢、效率越低，但謂詞表示越細，推理越慢、效率越低，但表示清楚。實踐中是要折衷的。表示清楚。實踐中是要折衷的。置換置換 置換是形如置換是形如t1/v1t1/v1，.，tn/vntn/vn的一個有限集。的一個有限集。其中其中vivi是變量，而是變量，而titi是不同于是不同于vivi的項常量、變的項常量、變量、函數(shù)，且量、函數(shù)，且vivjvivjiji

55、j，i i，j=1j=1，2 2，. . ，n n。 假元推理，就是由適宜公式假元推理，就是由適宜公式W1W1和和W1W2W1W2產(chǎn)生適宜產(chǎn)生適宜公式公式W2W2的運算。的運算。 全稱化推理，是由適宜公式全稱化推理，是由適宜公式( (x)W(x)x)W(x)產(chǎn)生適宜產(chǎn)生適宜公式公式W(A)W(A)，其中，其中A A為恣意常量符號。為恣意常量符號。 一個表達式的置換就是在該表達式中用置換項置一個表達式的置換就是在該表達式中用置換項置換變量。換變量。 普通說來，置換是可結(jié)合的，但置換是不可交換普通說來，置換是可結(jié)合的，但置換是不可交換的。的。置換置換 例例1：表達式：表達式Px，fy，B 的的4

56、個置換為個置換為s1=z/x，w/ys2=A/ys3=q(z)/x，A/ys4=c/x，A/y將它們分別作用于表達式，得：將它們分別作用于表達式，得：Px，fy，Bs1=Pz，fw，BPx，fy，Bs2=Px，fA，BPx，fy，Bs3=Pqz，fA，BPx，fy，Bs4=Pc，fA，B合一合一 尋覓項對變量的置換，以使兩表達式一致，叫做尋覓項對變量的置換，以使兩表達式一致，叫做合一合一(unification)(unification)。假設(shè)一個置換。假設(shè)一個置換s s作用于表達作用于表達式集式集EiEi的每個元素，那么用的每個元素，那么用EiEis s來表示來表示置換例的集。置換例的集。

57、稱表達式集稱表達式集EiEi是可合一的，假設(shè)存在一個置是可合一的，假設(shè)存在一個置換換s s使得：使得：E1s=E2s=E3s=E1s=E2s=E3s=那么稱此那么稱此s s為為EiEi的的合一者，由于合一者，由于s s的作用是使集合的作用是使集合EiEi成為單一成為單一方式。方式。合一合一 例例2：表達式集：表達式集 Px，fy， B， Px，fB，B的合一者為的合一者為 s=A/x，B/y 由于由于 Px，fy，Bs= Px，fB，Bs=PA，fB，B假設(shè)假設(shè)s是的任一合一者，有存在某個是的任一合一者，有存在某個s，使得，使得Eis=Eis成立成立,那么稱那么稱為的最通用為的最通用(最普通最

58、普通)的合一者的合一者,記記為為mgu.如上例如上例s是的一個合一者，但不是最簡單的合一是的一個合一者，但不是最簡單的合一者，其最簡單的合一者為者，其最簡單的合一者為=B/y分歧集分歧集 設(shè)有一非空有限公式集設(shè)有一非空有限公式集F=F1，F(xiàn)2， ，F(xiàn)n,從從F中個公式的第一符號同時向右比較中個公式的第一符號同時向右比較,直直到發(fā)現(xiàn)第一個彼此不僅、不盡一樣的符號到發(fā)現(xiàn)第一個彼此不僅、不盡一樣的符號為止為止,從從F的各個公式中取出那些以第一個的各個公式中取出那些以第一個不一致符號開場的最大的子表達式為元素不一致符號開場的最大的子表達式為元素,組成一個集合組成一個集合D,稱為稱為F的分歧集的分歧集.

59、合一算法合一算法 合一算法：設(shè)合一算法：設(shè)F非空集合有限表達集合非空集合有限表達集合,那么可那么可按以下步驟求其按以下步驟求其mgu： 置置k=0，F(xiàn)k=F，k=空置換，不含元素的置空置換，不含元素的置換換 假設(shè)假設(shè)Fk只含有一個表達式，那么算法停頓，只含有一個表達式，那么算法停頓，k=mgu。 找出找出Fk的分歧集的分歧集Dk。 假設(shè)假設(shè)Dk中存在元素中存在元素ak和和tk，其中，其中ak是變元，是變元，tk是工程，且是工程，且ak不在不在tk中出現(xiàn)，那么置：中出現(xiàn)，那么置： k+1=k，F(xiàn)k+1=Fktk/ak， k=k+1，轉(zhuǎn)步驟，轉(zhuǎn)步驟2 算法停頓，算法停頓，F(xiàn)的的mgu不存在。不存在

60、。 合一算法舉例合一算法舉例 例例3 求公式集求公式集 F=P(a,x,f(g(y),P(z,h(z,u),f(u) 的最普通合一者的最普通合一者合一算法舉例續(xù)合一算法舉例續(xù) K=0:F0=F, 0= F0不是單一表達式，有不是單一表達式，有D0=a,z,其中其中z是變元，且是變元，且不在不在a中出現(xiàn)，那么中出現(xiàn)，那么 1= 0a/z= a/z= a/z F1=F0a/z=P(a,x,f(g(y),P(a,h(a,u),f(u) K=1:F1不是單一表達式，有不是單一表達式，有D1=x,h(a,u) 2= 1h(a,u)/x=a/z,h(a,u)/x F2=F1h(a,u)/x=P(a,h(a