【正文】 ?p符號 (?x)P(x)：來表示某個(gè)論域中 至少存在一個(gè) 個(gè)體 x，使 P(x)真值為 T。p （ 2）量詞n 全稱量詞 ? 存在量詞 ?2023/2/27p （ 1）連詞n 通過連詞產(chǎn)生的復(fù)合謂詞公式（邏輯語句）的 真值表 ：P Q P P∧ Q P∨ Q P Q P QT T F T T T TF T T F T T FT F F F T F FF F T F F T T2023/2/27（等價(jià)）連接 謂詞公式 產(chǎn)生 等價(jià)式 ；正、逆向蘊(yùn)涵式的合取。p （ 1）連詞（非）加在 謂詞公式 前面，稱為否定，或取反。n “謂詞公式 是謂詞邏輯的基本單元，也稱為 原子公式 。? 謂詞演算 —— 人工智能系統(tǒng)最常用的知識表示方法，? 廣泛地應(yīng)用于各種人工智能系統(tǒng)的設(shè)計(jì)。n 缺點(diǎn)： 容易產(chǎn)生組合爆炸，推理過程中得到的中間結(jié)論一般呈指數(shù)形式遞增。n 所以，不知道新聞。星期六 23自然演繹推理的基本概念n 如果上網(wǎng)，則能知道新聞。 n 金星會(huì)顯示出位相變化。星期六 20自然演繹推理的基本概念 n T規(guī)則： 推理時(shí)，如果前面步驟中有一個(gè)或多個(gè)公式永真蘊(yùn)涵公式 S，則可把 S引入推理過程中。星期六 18 自然演繹推理2023/2/27星期六 17推理的控制策略⑥ 按條件個(gè)數(shù)排序l 多條規(guī)則生成的結(jié)論相同的情況下，由于條件個(gè)數(shù)較少的規(guī)則匹配所花費(fèi)的時(shí)間較少而且容易實(shí)現(xiàn)，所以將條件少的規(guī)則賦予較高的優(yōu)先級，優(yōu)先被啟用。根據(jù)匹配程度來決定哪一個(gè)產(chǎn)生式規(guī)則優(yōu)先被應(yīng)用。① 按就近原則排序l 該策略把最近被使用過的規(guī)則賦予較高的優(yōu)先級。 出現(xiàn)沖突的情況252。 雙向推理是指正向推理與逆向推理同時(shí)進(jìn)行，且在推理過程中的某一步驟上 “碰頭 ”的一種推理。目 正向推理 逆向推理驅(qū)動(dòng)方式 數(shù)據(jù)驅(qū)動(dòng) 目標(biāo)驅(qū)動(dòng)推理方法 從一組數(shù)據(jù)出發(fā)向前推導(dǎo)結(jié)論 從可能的解出發(fā)向后推理驗(yàn)證解答啟動(dòng)方法 從一個(gè)事件啟動(dòng) 由詢問關(guān)于目標(biāo)狀態(tài)的一個(gè)問題啟動(dòng)透明程度 不能解釋其推理過程 可解釋其推理過程推理方向 由底向上推理 由頂向下推理典型系統(tǒng) CLIPS， OPS PROLOG2023/2/27② 逆向推理 逆向推理是以某個(gè)假設(shè)目標(biāo)為出發(fā)點(diǎn)的一種推理，又稱為目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理、目標(biāo)制導(dǎo)推理及后件推理2023/2/272023/2/27星期六 5推理方式及其分類n 在任何情況下，由演繹推導(dǎo)出的結(jié)論都是蘊(yùn)涵在大前提的一般性知識中n 只要大前提和小前提是正確的，則由它們推出的結(jié)論必然是正確的(2) 歸納推理n歸納推理是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種 從個(gè)別到一般 的推理n歸納推理： 完全歸納推理 、 不完全歸納推理n完全歸納推理是在進(jìn)行歸納時(shí)考察了相應(yīng)事物的全部對象，并根據(jù)這些對象是否都具有某種屬性，從而推出這個(gè)事物是否具有這個(gè)屬性n不完全歸納推理是指只考察了相應(yīng)事物的部分對象就得出了結(jié)論2023/2/27 三段論式包括167。星期六 3什么是推理p 推理就是 按某種策略由已知判斷推出另一判斷的思維過程p 已知判斷：包括已掌握的與求解問題有關(guān)的知識及關(guān)于問題的已知事實(shí) 推理的結(jié)論：由已知判斷推出新判斷p 推理由程序程序?qū)崿F(xiàn)，稱為 推理機(jī)2023/2/272023/2/27星期六 4推理方式及其分類 演繹推理、歸納推理、默認(rèn)推理p推理的基本任務(wù)是 從一種判斷推出另一種判斷p按判斷 推出的途徑 來劃分，可分為演繹推理、歸納推理及默認(rèn)推理（ 1）演繹推理167。大前提：已知的一般性知識或假設(shè)167。星期六 6推理方式及其分類n 枚舉歸納推理：若已知某類事物的有限可數(shù)個(gè)具體事物都具有某種屬性，則可推出該類事物都具有此屬性n 類比推理：在兩個(gè)或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們在其他屬性上也相同或相似的一種推理(3) 默認(rèn)推理n又稱缺省推理，它是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理n擺脫了需要知道全部事實(shí)才能進(jìn)行推理的需求，使得在知識不完全的情況下也能進(jìn)行推理2023/2/27星期六 9推理的控制策略p 推理過程是一個(gè)思維過程，即 求解問題的過程p 推理的控制策略主要包括推理方向、搜索策略、沖突消解策略、求解策略及限制策略等推理方向n 推理方向用于確定推理的驅(qū)動(dòng)方式，分為正向推理、逆向推理、混合推理及雙向推理四種知識庫綜合數(shù)據(jù)庫推理機(jī)2023/2/27星期六 11正、逆向推理比較星期六 12推理的控制策略③ 混合推理p 已知的事實(shí)不充分。167。對正向推理而言，如果有多條產(chǎn)生式規(guī)則的前件都和已知的事實(shí)匹配成功；或者有多組不同的已知事實(shí)都與同一條產(chǎn)生式規(guī)則的前件匹配成功；或者兩種情況同時(shí)出現(xiàn)2023/2/27 ② 按已知事實(shí)的新鮮性排序 l 一般我們認(rèn)為新鮮事實(shí)是對舊知識的更新和改進(jìn)，比老知識更有效，即后生成的事實(shí)比先生成的事實(shí)具有較大的優(yōu)先性。④ 按領(lǐng)域問題特點(diǎn)排序 l 該方法按照求解問題領(lǐng)域的特點(diǎn)將知識排成固定的次序。 ⑦ 按規(guī)則的次序排序 l 該策略是以知識庫中預(yù)先存入規(guī)則的排列順序作為知識排序的依據(jù)，排在前面的規(guī)則具有較高的優(yōu)先級。星期六 19自然演繹推理的基本概念 n 反證法： ，當(dāng)且僅當(dāng) 。p 假言推理 表示：由 及 P為真，可推出 Q為真 p 拒取式推理 表示：由 為真及 Q為假，可推出 P為假 2023/2/27n 所以，行星系統(tǒng)是以太陽為中心的。 n又如下列推理：這就是使用了否定前件的推理 ,違反了邏輯規(guī)則 ,顯然是不正確的 ,因?yàn)橥ㄟ^收聽廣播、看電視等，也會(huì)知道新聞。2023/2/27? 謂詞演算（或更廣義地，形式邏輯）是人工智能研究的重要基礎(chǔ)之一。2023/2/27（與）連接 謂詞公式 ，稱為 合取 ；產(chǎn)生的 邏輯語句 稱為 合取式 ，每個(gè)成分成為 合取項(xiàng)。2023/2/27星期六 29p 連詞和量詞n 命題 —— 不包含 變量 的 謂詞公式 和 邏輯語句 ；n 命題邏輯 —— 基于 命題 的 謂詞邏輯 稱為 命題邏輯 ， 命題邏輯是謂詞邏輯的子集 。星期六 30p 連詞和量詞 —— （ 2）量詞n 全稱量詞 ?p符號 (?x)P(x)：表示對于某個(gè)論域中的 所有（任意一個(gè)） 個(gè)體 x,條條大路通羅馬Mary給每個(gè)人一本書Mary給每人某個(gè)同樣的東西量詞可以嵌套使用可以有不受量詞約束的變量2023/2/27真值為 T。)函數(shù)名進(jìn)行了量化；n P(x,Q(y))參數(shù)項(xiàng)是謂詞公式；2023/2/27星期六 34合適公式的性質(zhì)合適公式等價(jià)關(guān)系 : 1. 否定之否定 172。Q 172。星期六 35合適公式的性質(zhì)6. 結(jié)合律 　 　 (P∧Q)∧R ? P∧(Q∧R ）　　 (P∨Q)∨R ? P∨ （ Q∨R ） 7. 逆否律 Q? 172。(?x)P(x) ?（ ?x)(172。(Q2x2)…(Q kxk)M，其中p MP(x， z)∨ ~P(y， z))∨ (?u)Q(x， y， u)??x)(?y)(?z)(?u)(~反演法利用了一個(gè)標(biāo)準(zhǔn)型，這個(gè)標(biāo)準(zhǔn)型就是 Skolem標(biāo)準(zhǔn)型。 從一階邏輯的公式變換到 Skolem標(biāo)準(zhǔn)型 不是等值變換，因?yàn)?Skolem標(biāo)準(zhǔn)型與原公式不等值。星期六 43合適公式的標(biāo)準(zhǔn)化合適公式的標(biāo)準(zhǔn)化 ★p 標(biāo)準(zhǔn)化需求n 常見的基于謂詞演算的推理： 歸結(jié)反演 、 (正向 /逆向 )演繹推理p 要求以 量詞前束范式 來表示合適公式n 量詞前束范式 形式如下：p (Q1x1) ∨ Lim(i=1,2,…,n)pLij=Pij|?Pij:文字（ Literal） ，是 謂詞公式 Pij或 其取反2023/2/27星期六 45p 合取范式的標(biāo)準(zhǔn)化過程p ① 消去多余的量詞（很少出現(xiàn)）n 若 一個(gè)量詞的轄域內(nèi)并未出現(xiàn)量詞的約束變量 ，則該量詞是多余的，應(yīng)該刪除；n 例， (?x)P(y)，則 (?x)可以消去，得到 P(y)；n 正常情況下，合適公式中不應(yīng)出現(xiàn)多余的量詞。?Q(x,y)?Q(x,y)星期六 46p 合取范式的標(biāo)準(zhǔn)化過程p ③ 內(nèi)移否定符號n 使否定只出現(xiàn)在原子謂詞公式前，構(gòu)成 否定文字 ；n 狄 .摩根定律：p ?(P?∧ PPn 量詞否定：p ?(?x)(?P(x))(?x)標(biāo)準(zhǔn)化而得到（ ?x） {p(x)=（ ?y） Q（ y） }∨ P(z,g(z))]n ?在 多個(gè) ?的轄域內(nèi)p (?x)(?y)(?z)(?w)P(x,y,z,w)p 用多元函數(shù) g(x,y,z)來取代約束變量 w，消去存在量詞 ?w；p (?x)(?y)(?z)P(x,y,z,g(x,y,z))n ?在 ?的轄域外p(?w)(?z)∨ P(z,A)] 前兩種叫 Skolem函數(shù)，第三種叫 Skolem常量2023/2/27在消去存在量詞的過程中，需要用到 Skolem函數(shù)或Skolem常量。所使用的常量符號必須是 新的 ，它未曾在公式其他地方使用過。Skolem變換 不是等價(jià)變換，但變換前后的值永假性保持不變 。p ⑧ 把母式轉(zhuǎn)化為 合取范式n 分配律 ： PR)Q)R)2023/2/27?P(f(x,y))]∧ ?(?y)(?w)[Q(x,y)?P(y,w)]}}② 消去蘊(yùn)涵符號?(?x){?P(x)∨{(?y)[?P(y)∨ P(f(x,y))]∧ ?(?y)(?w)[?Q(x,y)∨ P(y,w)]}}2023/2/27星期六 55p 合取范式的標(biāo)準(zhǔn)化過程n 例、化簡合適公式{P(A)∧{(?y)[P(y)∧ ?P(f(A,y))]∨ (?z)[?Q(A,z)∨ P(z,g(z))]}}⑥ 全稱量詞前束化(?y)(?z){P(A)∧{[P(y)∧ ?P(f(A,y))]∨ [?Q(A,z)∨ P(z,g(z))]}}2023/2/27歸結(jié)演繹推理歸結(jié)演繹推理p 自動(dòng)定理證明一般表示形式為：p F1∧ F2∧ … ∧ Fn?Wn F1,F2,…星期六 59歸結(jié)演繹推理歸結(jié)演繹推理p 海伯倫（ Herbrand）n 提出的 H域（海伯倫域） 和 海伯倫定理 ；n 為 自動(dòng)定理證明 奠定了理論基礎(chǔ)；p 魯賓遜（ Robinson）n 提出的 歸結(jié)原理 ；n 使 自動(dòng)定理證明 成為可能。 ∧ WnpWi=Li1∨ Li2∨ …星期六 62歸結(jié)演繹推理歸結(jié)演繹推理1） H域和海伯倫定理p 子句和子句集n 子句 —— 僅由 文字 的 析取 ∨ 構(gòu)成的合適公式n 合取范式表示為 子句集 ，子句間隱含具有 合取關(guān)系(?y)Q(x)]Q(x)(?y)∧(?y)(?z)[P(y)∨ ?Q(A,z)∨ P(z,g(z))],(?y)代替 ~（ A∨ B）以 A代替 ~（ ~A）以 (?x){~量詞有其自己唯一的啞元。星期六 65 星期六 66現(xiàn)在已不存在任何存在量詞，而且每個(gè)全稱量詞都有自己的變量，把所有全稱量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。(?x)(?y){P(x)∨ 全稱量詞的次序也不重要了。反復(fù)代替的結(jié)果，最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取。S后， F和 S在永假性上是等價(jià)的2023/2/27P(A) 星期六 70歸結(jié)演繹推理歸結(jié)演繹推理1） H域和海伯倫定理p H域 （了解）n 證明 子句集 S的不可滿足性 與證明 合適公式永真性 類似p 由于個(gè)體 論域 的任意性和 解釋 個(gè)數(shù)的無限性，使得證明工作 十分困難 。2023/2/27星期六 72歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理 ★p 動(dòng)機(jī)n 為提高判定子句集 S不可滿足的有效性 ，魯賓遜于 1965年提出了 歸結(jié) (Resolution)原理 ，也稱為 消解原理 。C2=?L∨ C2’p① 從 C1和 C2中 消去互補(bǔ)文字 L和 ?L；p② C1’和 C2’通過 ∨ 組成新的子句C=C1’∨ R(f(x))R(y)C1’ C2’2023/2/27星期六 75歸結(jié)演繹推理歸結(jié)演繹推理2）歸結(jié)原理p 歸結(jié)方法p (3)空子句n 設(shè) C1=L、 星期六 77(3) 重言式父輩子句 P∨ Q ~P∨ ~ Q消解式 Q ∨ ~ QC1=P∨ Q,C2=~P∨ ~Q父輩子句 P∨ Q ~P∨ ~ Q消解式 P ∨ ~ P或者2023/2/27p 基本思路 ★n 通過 歸結(jié)方法 不斷 擴(kuò)充 待判定的 子句集 S，并設(shè)法使