第三~四講-產(chǎn)生式及一階謂詞課件

1、第三講 產(chǎn)生式表示法及應(yīng)用2022/7/28 “產(chǎn)生式” 的概念由邏輯學(xué)家Post l943年提出，產(chǎn)生式表示法又稱為產(chǎn)生式規(guī)則表示法，但由于缺乏控制策略，不適合開發(fā)實際的應(yīng)用系統(tǒng)。 1972年，Newell和Simon在研究人類的認知模型中開發(fā)了基于規(guī)則的產(chǎn)生式系統(tǒng)?，F(xiàn)在，已經(jīng)發(fā)展成為人工智能系統(tǒng)中最典型的一種基本結(jié)構(gòu)，是專家系統(tǒng)及其他應(yīng)用人工智能系統(tǒng)中最自然的知識表示及推理的基本模型。2022/7/282第一節(jié) 知識的表示方法一、確定性規(guī)則知識的表示方法PQ 或IF P THEN Q二、不確定性規(guī)則知識的表示方法PQ ( 置信度) 或IF P THEN Q ( 置信度) 2022/7/28

2、4第二節(jié) 產(chǎn)生式系統(tǒng)的組成 一個典型的產(chǎn)生式系統(tǒng)由規(guī)則庫、綜合數(shù)據(jù)庫、推理機三大部分組成。它們之間的關(guān)系如圖所示。推理機規(guī) 則 庫綜合數(shù)據(jù)庫2022/7/285一、 規(guī)則庫(知識庫)用于描述某領(lǐng)域內(nèi)知識的產(chǎn)生式（規(guī)則）集合，是某領(lǐng)域知識的存儲器。也稱知識庫。包含著將問題從初始狀態(tài)轉(zhuǎn)換成目標狀態(tài)（或解狀態(tài)）的那些變換規(guī)則。是專家系統(tǒng)的核心。2022/7/286二、 綜合數(shù)據(jù)庫存儲所求解問題的初始狀態(tài)及已知事實，推理的中間結(jié)果以及結(jié)論。隨著產(chǎn)生式系統(tǒng)問題求解(推理)過程的進展，綜合數(shù)據(jù)庫的有些內(nèi)容(如推理的中間結(jié)果)動態(tài)變化。綜合數(shù)據(jù)庫又稱為動態(tài)數(shù)據(jù)庫、短期數(shù)據(jù)庫緩沖器。綜合數(shù)據(jù)庫是產(chǎn)生式系統(tǒng)中主

3、要的數(shù)據(jù)結(jié)構(gòu)，可以通過簡單的表、數(shù)組、帶索引的文件結(jié)構(gòu)、關(guān)系數(shù)據(jù)庫等來實現(xiàn)。2022/7/287三、 推理機一個或一組程序，用來控制和協(xié)調(diào)規(guī)則庫與綜合數(shù)據(jù)庫的運行。包含推理方式和控制策略。2022/7/288第三節(jié) 產(chǎn)生式系統(tǒng)的控制策略一、作用 確定選用什么規(guī)則或如何應(yīng)用規(guī)則。二、組成 由匹配、選擇(沖突解決)、執(zhí)行三個階段組成。匹配 將當前綜合數(shù)據(jù)庫中的事實與規(guī)則中的條件進行比較沖突解決 根據(jù)預(yù)先確定的評價準則決定選擇被執(zhí)行規(guī)則執(zhí)行 把所選擇規(guī)則的結(jié)論添加到綜合數(shù)據(jù)庫，作為新的事實。2022/7/289綜合數(shù)據(jù)庫索引變量近似過濾專一性排序、規(guī)則排序、規(guī)模排序、折射、最新性、特殊性規(guī)則庫匹配沖

4、突集規(guī)則觸發(fā)規(guī)則執(zhí)行沖突消解推理控制2022/7/2810第四節(jié) 產(chǎn)生式系統(tǒng)的推理方式 產(chǎn)生式系統(tǒng)的問題求解過程事實上就是對解空間的搜索過程，又稱為推理過程，根據(jù)推理過程進行的方向或者搜索的方向可分為正向推理、反向推理、雙向推理。2022/7/2811一、正向推理它從已知事實出發(fā)，通過與規(guī)則庫中產(chǎn)生式的條件匹配，然后執(zhí)行匹配規(guī)則的動作，求得結(jié)論。正向推理方式又稱為數(shù)據(jù)驅(qū)動方式。推理過程 綜合數(shù)據(jù)庫中含有事實P1，則應(yīng)用則進行正向推理，即從P1出發(fā)推導(dǎo)出q3 的過程：如規(guī)則集：規(guī)則1：P1P2 規(guī)則2：P2P3 規(guī)則3：P3q32022/7/2812產(chǎn)生式系統(tǒng)正向推理的一種算法(1) 讀入初始數(shù)

5、據(jù)(事實)集到綜合數(shù)據(jù)庫；(2) Repeat 取出第i條規(guī)則； 規(guī)則i 所有前件與綜合數(shù)據(jù)庫的所有事實進行比較； if 規(guī)則匹配成功 then 把規(guī)則加入沖突集； if 沖突集為空 then goto (3)； 沖突消解； 把所選擇規(guī)則的結(jié)論加入綜合數(shù)據(jù)庫； if 到達目標節(jié)點 then goto (3)； i=i+1； (3) 結(jié)束。2022/7/2813例：初始狀態(tài) Start 目標狀態(tài) Goal規(guī)則庫R1：if P and Q then Goal R2：if R and S then PR3：if W and R then Q R4：if T and U then Q R5：if V

6、then SR6：if Start then V and R and Q執(zhí)行過程動態(tài)庫沖突集觸發(fā)規(guī)則0Start1Start, V, R, Q6, 552Start, V, R, Q, S6, 5, 223Start, V, R, Q, S,P6, 5, 2, 114Start, V, R, Q, S,P, Goal6, 5, 2, 1終止沖突原則： 選取最久以前被觸發(fā)的或根本沒有被觸發(fā)的規(guī)則 如果出現(xiàn)“平局”，選取其中的第一個規(guī)則2022/7/2814二、反向推理基本原理：將目標與規(guī)則庫中規(guī)則的動作部分匹配，然后把匹配規(guī)則的條件作為要證明的子目標，求得已知事實。反向推理方式又稱為目標驅(qū)動方式

7、推理過程如規(guī)則1：P1P2 規(guī)則2：P2P3 規(guī)則3： P3q3應(yīng)用反向推理方法獲取目標q3的過程：2022/7/2815例：初始狀態(tài) Start 目標狀態(tài) GoalR1：if P and Q then Goal R2：if R and S then PR3：if W and R then Q R4：if T and U then Q R5：if V then SR6：if Start then V and R and Q執(zhí)行過程動態(tài)庫沖突集觸發(fā)規(guī)則0Goal111Goal, P, Q1, 2, 3, 422Goal, P, Q, R, S1, 2, 3, 4, 533Goal, P, Q,

8、R, S,W1, 2, 3, 4, 544Goal, P, Q, R, S, W, T, U1, 2, 3, 4, 555Goal, P, Q, R, S, W, T, U, V1, 2, 3, 4, 5, 666Goal, P,Q, R, S, W, T, U, V, Start1, 2, 3, 4, 5, 6終止沖突原則： 選取最久以前被觸發(fā)的或根本沒有被觸發(fā)的規(guī)則 如果出現(xiàn)“平局”，選取其中的第一個規(guī)則2022/7/2816三、雙向推理雙向推理是一種既正向又反向的推理。推理從兩個方向同時進行，直至某個中間界面上兩個方向結(jié)果相符便成功結(jié)束?？刂撇呗员惹皟煞N方法都要復(fù)雜。2022/7/281

9、7第五節(jié) 對產(chǎn)生式系統(tǒng)的評價一、特點具有豐富的知識表示能力，可以簡單直觀的規(guī)則方式表達人類的經(jīng)驗性知識。知識表達模塊化、結(jié)構(gòu)化，每條規(guī)則具有相同的格式且相對獨立。規(guī)則的組合、修改、增、刪比較容易，規(guī)則的收集、整理比較方便。容易排除故障，當系統(tǒng)工作異常時，通過跟蹤產(chǎn)生式規(guī)則的觸發(fā)序列，就可容易地發(fā)現(xiàn)故障，為系統(tǒng)調(diào)試和維護提供便利條件。2022/7/2818產(chǎn)生式系統(tǒng)的規(guī)則鏈接推理過程相似于人類求解問題時的邏輯思維過程，可把產(chǎn)生式系統(tǒng)用作人類行為的啟發(fā)式模型，模擬人類的邏輯思維過程。推理方向的可逆性。由于產(chǎn)生式規(guī)則的前件和后件結(jié)構(gòu)類似，可同時進行正向和反向推理，即混合推理。2022/7/2819二

10、、適合場合 知識結(jié)構(gòu)類似于產(chǎn)生式規(guī)則的領(lǐng)域，如醫(yī)療診斷系統(tǒng)。其特點是領(lǐng)域知識比較零亂，由大量經(jīng)驗性的獨立事實和規(guī)則組成。 領(lǐng)域知識中包含一系列相互獨立的動作，可以自然地用產(chǎn)生式規(guī)則的后件來表達的領(lǐng)域，如醫(yī)院的病人監(jiān)護系統(tǒng)。 領(lǐng)域知識可方便地從應(yīng)用中分離出來的領(lǐng)域，如經(jīng)典分類學(xué)等。2022/7/2820三、缺陷推理效率低速度慢實時性能差容易產(chǎn)生組合爆炸 試驗表明，產(chǎn)生式系統(tǒng)在匹配階段所花費的時間大約為產(chǎn)生式系統(tǒng)工作周期的90。而沖突消解及執(zhí)行階段所花費的時間大約占工作周期的10。2022/7/2821 若欲求解的問題可視為問題空間中一個狀態(tài)到另一個狀態(tài)的變換序列，則可用產(chǎn)生式系統(tǒng)求解。諸如 8數(shù)

11、碼(8 Puzzle)、旅行商(traveling salesman)、漢諾塔(Tower of Hanoi)、傳教士與食人魔(Missionaries and cannibals)、符號積分(Symbolic integration)、猴子與香蕉(Monkey and bananas)等經(jīng)典人工智能問題的求解，以人類專家知識為基礎(chǔ)的專家系統(tǒng)的問題求解，從本質(zhì)上都可以看作是從初始狀態(tài)到目標狀態(tài)的推導(dǎo)變換過程，因而都可用產(chǎn)生式系統(tǒng)來求解。 2022/7/2822 專家系統(tǒng) 專家系統(tǒng)結(jié)構(gòu)選擇恰當與否，與專家系統(tǒng)的適用性和有效性密切相關(guān)的。用 戶 界 面推理執(zhí)行機構(gòu)動態(tài)庫知識庫知 識獲 取解 釋機

12、構(gòu)用 戶推理機根據(jù)動態(tài)庫的當前狀態(tài)，利用知識庫中的知識進行推理。用戶界面亦稱人機接口，完成信息的內(nèi)部形式和人可接收的形式之間進行轉(zhuǎn)換。動態(tài)庫是用來記錄控制信息、中間假設(shè)和中間結(jié)果知識獲取負責(zé)建立、修改與擴充知識庫，對知識庫的一致性、完整性等進行維護。包括:1與當前問題有關(guān)的數(shù)據(jù)信息；2 一般知識和領(lǐng)域知識。規(guī)則、網(wǎng)絡(luò)和過程等形式表示。2022/7/2823 專家系統(tǒng)的開發(fā)過程 專家系統(tǒng)是一個復(fù)雜的智能軟件，與一般軟件類似，但又有不同的特點。 一般軟件處理的對象是數(shù)值、文字、圖形等信息，且有固定的算法序列，而專家系統(tǒng)軟件處理的對象是以符號表示的知識，在運行過程中常有回溯發(fā)生，因此專家系統(tǒng)的開發(fā)過

13、程與一般軟件的開發(fā)有所不同。 專家系統(tǒng)的創(chuàng)始人費根鮑姆教授把開發(fā)專家系統(tǒng)的技術(shù)稱之為知識工程，即以知識獲取、知識表示、知識運用(推理)為中心。根據(jù)這個思想，可把專家系統(tǒng)的開發(fā)過程分為以下幾個階段。2022/7/2824 1 問題定義與系統(tǒng)分析 在著手開發(fā)一個專家系統(tǒng)時，首先應(yīng)了解清楚用戶的需求，確定欲解決的問題的范圍(領(lǐng)域)，系統(tǒng)所要達到的目標，系統(tǒng)功能，性能指標，輸入輸出，使用對象，人機接口形式，運行軟硬件環(huán)境等。在此基礎(chǔ)上進行系統(tǒng)可行性論證及經(jīng)濟效益或社會效益分析。最后寫出系統(tǒng)工作的數(shù)據(jù)(信息)流程圖，寫出分析報告及有關(guān)文檔。2022/7/28252 知識獲取 知識獲取階段的主要工作是根據(jù)

14、所確定的系統(tǒng)目標及限定的問題求解范圍，收集專家知識。在當前的技術(shù)條件下主要是通過走訪多個領(lǐng)域?qū)＜壹艾F(xiàn)場技術(shù)人員，查閱國內(nèi)外大量文獻資料來收集、歸納、整理領(lǐng)域知識。3 知識表示 知識表示階段的任務(wù)是根據(jù)領(lǐng)域知識的性質(zhì)，選擇一種或組合數(shù)種知識表示方法，如前面介紹過的謂詞邏輯表示法，框架表示法，產(chǎn)生式系統(tǒng)表示法等，把獲取到的專家知識邏輯地表達出來，并以適當?shù)男问酱鎯Φ接嬎銠C中。2022/7/2826 4 軟件實現(xiàn) 這一階段的工作與一般軟件設(shè)計類似，應(yīng)遵循軟件工程的原則，進行系統(tǒng)設(shè)計、編碼、測試，建立知識庫，實現(xiàn)推理機，動態(tài)存儲器，人機接口，知識獲取等專家系統(tǒng)程序模塊，構(gòu)成一個可運行的專家系統(tǒng)原型軟件

15、。2022/7/28275 系統(tǒng)測試與評價 專家系統(tǒng)開發(fā)是一個長期反饋的過程，對所生成的專家系統(tǒng)原型軟件必須反復(fù)進行測試，評價，發(fā)現(xiàn)并改正其中的錯誤，才能使之實用。 測試與評價的主要內(nèi)容包括： 知識表示模式的選取是否恰當； 知識庫中的知識的正確性，完整性，一致性如何； 知識庫維護是否容易； 所采用的推理方法和技術(shù)是否正確，推導(dǎo)出的結(jié)論是否可信，用戶是否滿意； 人機接口使用是否方便，實用； 系統(tǒng)的成本與效益情況等。2022/7/2828新一代專家系統(tǒng)新一代專家系統(tǒng)的特征：(1) 并行技術(shù)與分布處理(2) 多專家系統(tǒng)協(xié)同工作(synergetic expert system)(3) 具有自學(xué)習(xí)功能

16、(4) 引入新的推理機制(5) 具有自糾錯和自完善能力(6) 先進的智能人機接口第四講 基于邏輯的問題求解方法邏輯表示法 用數(shù)理邏輯表示知識經(jīng)典邏輯（標準邏輯）非經(jīng)典邏輯一階謂詞是一種形式語言，可以表示和推理客觀世界的屬性和關(guān)系。命題邏輯和一階謂詞邏輯模態(tài)邏輯、時序邏輯、非單調(diào)邏輯、多值邏輯2022/7/2829 命題 取值為真或假(表示是否成立)的句子 謂詞 帶有變量(參數(shù))的命題 謂詞 p (x1，x2，xn) 一元謂詞 謂詞與一個個體的屬性 blue ( desk ) 多元謂詞 謂詞與多個個體間的關(guān)系 TEACHER(x, y) 一階謂詞 xi 為常量、變元或函數(shù) 高階謂詞 xi 本身為

17、一階謂詞第一節(jié) 一階謂詞邏輯基礎(chǔ) 謂詞用來描述個體（可以獨立存在的事物）之間的關(guān)系或?qū)傩?022/7/2830一、謂詞邏輯的符號體系 常量以小寫字母組成的符號串 變量符號習(xí)慣上是大寫字母開始 函數(shù)符號通常以小寫字母或小寫字母串表示 謂詞符號通常以小寫字母或小寫字母串表示，不可拆散 逗號及括號(圓括號、方括號、花括號) 將變量符號、函數(shù)符號、謂詞符號及常量隔開，僅用于構(gòu)建公式，表示論域內(nèi)的關(guān)系。 函數(shù)與謂詞的形式分別為： 謂詞 p(x1，x2，xn) 函數(shù) f (xl，x2，xn)2022/7/2831連接詞：否定(非) inroom (robot，r2) 合取(與) like ( he，mus

18、ic) like (he，painting) 析取(或) plays ( liming，basketball) plays( liming ，football) 蘊含 (IFTHEN) owns ( she，book-1) color(book-1，blue) 等價(雙條件)2022/7/2832量詞 量詞是由量詞符號和被量化的變元所組成的表達式：全稱量詞符號，表示所有的。 例如，所有的籃球運動員都很高，表示為 (X) (basketball_player(X) tall(X)：存在量詞符號，表示存在某一些。 例如，一些人喜歡狗，表示為 (X ) (person(X) likes(X, dog

19、)2022/7/2833二、謂詞邏輯的知識表示 若量詞僅對謂詞的個體(變量)而不能對謂詞自身起限定作用，即把謂詞名視為常量，稱其為一階謂詞。 一階謂詞邏輯可嚴密而精確地表達復(fù)雜的人類知識，在很多領(lǐng)域可以得到直接的應(yīng)用。 可以表示： 事物的狀態(tài)、屬性、概念的事實性知識； 否定、析取或合取符號連接起來的謂詞公式 事物的因果關(guān)系 蘊含式表示 x y2022/7/2834 1 形式化的領(lǐng)域 在形式化的領(lǐng)域中，知識或信息是用對象和它們的屬性，以及它們之間的關(guān)系表示的。 關(guān)系數(shù)據(jù)庫可以認為是采用了一階謂詞邏輯的形式，每個關(guān)系類型對應(yīng)著一個謂詞。occupant( owen，301) telephone (

20、741，301)2022/7/28352 非形式化的領(lǐng)域例如 所有的整數(shù)不是偶數(shù)就是奇數(shù)定義 integer(X): X為整數(shù)； even(X): X為偶數(shù); odd(X): X為奇數(shù) 謂詞表示 ( X) (integer(X) even (X)odd (X) )2022/7/2836 在人工智能中常用的是一階謂詞邏輯，因此本章介紹的內(nèi)容主要針對一階謂詞邏輯。 設(shè)有三個積木塊a，b，c，它們之間的位置關(guān)系可用下列謂詞表示： on (a, b) on (b, c) on (a, c) on (a, b)on (b, c) on (a, c)2022/7/2837三、謂詞演算公式原子公式 不含任何

21、連接詞及量詞的謂詞公式 p ( X1, X2, ，Xn) ，X個體變量謂詞演算的合式公式( WFF well-formed formula)原子公式是合式公式。若A是合式公式，則A也是合式公式。若A，B是合式公式，則AB，AB，AB，AB，也都是合式公式。若A是合式公式，X是個體變量，則(X)A，(X)A也是合式公式只有按a)d)所得的公式才是合式公式。2022/7/2838第二節(jié) 邏輯推理如果謂詞公式p對任意非空個體域上的任一解釋都取得真值true，則稱p永真。對于謂詞公式p，如果至少存在非空個體域D上的一個解釋，使公式p在此解釋下的真值為true，則稱公式p在D上是可滿足的。謂詞公式的可滿

22、足性也稱為相容性。如果謂詞公式p對非空個體域D上的任一解釋都取真值false，則稱P永假。謂詞公式的永假性又稱不可滿足性或不相容性。 2022/7/2839一、等價式交換律PQ QP PQ QP 結(jié)合律(PQ) R P(QR) (PQ)R P(QR) 分配律P(QR) (PQ)(PR) P(QR) (PQ)(PR)摩根定理 (PQ) PQ (PQ) P Q 否定之否定 (P) P 2022/7/2840吸收律 P(PQ) P P(PQ) P補余律 PP TPP F逆否定律 PQ Q PPQ P Q量詞轉(zhuǎn)換律 (x)P(x) (x)(P(x) (x)P(x) ( x)(P(x)量詞分配律2022

23、/7/2841p(a)p(b)p(a)p(b)p(a)p(a)p(b)p(a)p(a)p(b)ttttttftttfttttfffttp(a)p(a)p(b) p(a)p(a)p(b)p(a)p(a)p(b) 或 p(a)p(a)p(b) 是永真的2022/7/2842二、自然演繹推理1 析取三段論 P, PQ Q2 假言推理 P, PQ Q3 假言三段論 PQ ，QR P R4 拒取三段論 Q, PQ P2022/7/2843 例 設(shè)已知如下事實： (1) 只要是需要編程序的課，王程都喜歡。 (2) 所有的程序設(shè)計語言課都是需要編程序的課 (3) C是一門程序設(shè)計語言課。求證：王程喜歡C這門

24、課。證明：首先定義謂詞 program (X) X是需要編程序的課。 like (X,Y) X喜歡Y。 language (X) X 是門程序設(shè)計語言課。program (X)like (wang, X) (X)( language (X) program (X) language (C)2022/7/2844把已知事實及待求解問題用謂詞公式表示如下： program (X) like ( wang, X)、 (X)( language (X) program (X)、language (C) 應(yīng)用推理規(guī)則進行推理： 全稱例化 language (Y) program (Y) 假言推理 lan

25、guage (C), language (Y) program (Y) program (C) 假言推理 program (C), program (X) like ( wang, X) like ( wang, C) 王程喜歡C這門課。 把一個真的謂詞公式中的任意的全稱量詞變量替換為定義域中的任意的適當項。2022/7/2845二、歸結(jié)(消解)原理簡介 1965年Robinson發(fā)現(xiàn)的歸結(jié)原理(refutation)。是以邏輯演繹為基礎(chǔ)進行邏輯推理。它的基本思想可用如下定理解釋： 定理 Q為P的邏輯結(jié)論，當且僅當 (P) (Q)是不可滿足的。 把已知條件表示謂詞公式，再化為一組子句； 欲證的

26、目標也化為一個子句的否定， 把目標子句與條件子句合在一起推理，若能推出矛盾(空子句)，則可證明此目標是成立的。2022/7/2846 已知兩子句 C1=P C1 和 C2= P C2 ， C1不等于C2，其中一個所含的 P，剛好是另一個子句中P 的否定，根據(jù)這兩個子句，推出一個新子句，即R(C1, C2)= C1 C2 ，稱作這兩個子句的歸結(jié)式。 P、P為互補對。 實現(xiàn)歸結(jié)推理的關(guān)鍵步驟是置換合一與尋求子句集中的互補對。2022/7/2847歸結(jié)式 PQ PQ歸結(jié)式 Q父輩1 析取三段論 2 合并3 重言式4 空子句(矛盾)5 假言三段論P PQ (PQ) 歸結(jié)式 Q父輩P Q P Q歸結(jié)式

27、Q Q 父輩P Q P Q P P P P歸結(jié)式 NIL 父輩PQ (PQ) QR (QR) 歸結(jié)式 PR (PR) 父輩2022/7/2848自動歸結(jié)證明的過程：(1)否定G，得 G；(2) 把G添加到S中，得新集合S, G；(3) 把新產(chǎn)生的集合S, G化成子句集；(4) 重復(fù)歸結(jié)過程，推導(dǎo)出一個表示矛盾的空子句。 2022/7/2849WFF化為子句的基本步驟重復(fù)運用蘊含等價式，消去蘊含 p(X) q(X) p(X) q(X)減少的轄域，使最多只作用一個謂詞上(p(X) q(X) q(X) q(X) (X) p(X) ( X) p(X)變量改名 ( X)p(X) (Y)p(Y) 移所有量

28、詞到前部，形成前束范式 (X) p(X) (W)q(W) 改為 (X) (W) p(X) q(W)2022/7/2850 消去存在量詞，形成對應(yīng)的S范式標準式(X) p(X) q (g(X) W=g(X)利用分配律，把母式化成析取式的合取式。p(X) (q(X) r(X) (p(X) q(X) (p(X) r(X)以逗號替代所有的 ，形成子句集母式Skolem函數(shù)2022/7/2851例 已知每個使用Internet的人都想從網(wǎng)絡(luò)獲得信息，證明如網(wǎng)絡(luò)沒有信息就不會有人使用Internet。證：設(shè)U (x, y)： 表示x使用y； G(v, u)： 表示v得到u； I(z)： 表示z是Inter

29、net； F (u)： 表示u是信息； 已知： W=(x) (y)(U(x, y) I(y) (u)( F(u)G (x, u) 結(jié)論：G(u) F (u) (x)(y)( I(y) U (x, y)2022/7/2852 條件：W= (x) (y)(U(x, y)I(y)(u)(F(u)E(x, u) 變換為子句集。(1) 消去蘊含 辦法：P(x) Q(x) P(x) Q(x)W = (x)(y)(U(x, y)I(y)(u)(F(u)E(x, u)(2) 把的轄域減少到最多只作用于一個謂詞 利用(P(x)Q(x) P(x)Q(x)；( x) P(x)( x)P(x) W = (x) (y)

30、(U(x, y)I(y)(u) (F(u)E(x, u) (x) (y) U(x, y)I(y)(u) (F(u)E(x, u)消存在量詞,形成S范式 W(x)(y) U(x, y)I(y) F(f(x)E(x, f(x)母式u=f(x)2022/7/2853 (4) 把母式化成合取范式 U(x, y)I(y)F(f(x)E(x, f(x) =U(x, y) I(y)(F(f(x) U(x, y) I(y)E(x, f(x) (5)以逗號替代所有的(消去符號)，形成子句集S = U(x, y) I(y)(F(f(x), U(x, y) I(y)E(x, f(x) 前提 W 對應(yīng)子句集的兩個子句

31、： U(x，y)I(y)(F(f(x) U(x，y)I(y)E(x，f(x) 2022/7/2854 結(jié)論：G(u)F(u)(x) (y)(I(y)U(x，y) 否定結(jié)論G，并化為S 范式 G = (u)F(u)(x)(y)(I(y)U(x，y) (u)F(u)(x)(y)(I(y)U(x，y) (u)F(u) (x)(y) (I(y)U(x，y) (x)(y)(u)F(u)I(y)U(x，y) 引入常量c，消去G中的存在量詞，得 (x)(y)F(c)I(y)U(x，y) 隱去全稱量詞，得到G對應(yīng)子句集的三個子句： F(c) I(y) U(x，y) 2022/7/2855對(1)施加置換 cf

32、(x)，再與(3)歸結(jié)得 (6) U(x, y)I(y)由(4)，(6)歸結(jié)，得 (7) I(y)(5)，(7)歸結(jié)，得 U(x, y) U(x, y) = 故，結(jié)論G得證。(1) U(x, y)I(y)(F(f(x)(2) U(x, y)I(y)E(x, f(x)(3) F(c) (4) I(y) (5) U(x, y)U(x, y)I(y)(F(f(x)F(c)cf(x)U(x, y)I(y) I(y) U(x, y) U(x, y) NIL歸結(jié)反演樹2022/7/2856歸結(jié)策略 歸結(jié)演繹推理實際上就是從子句集中不斷尋找可進行歸結(jié)的子句對，并通過對這些子句對的歸結(jié)，最終得出一個空子句的過

33、程。 盲目地全面進行歸結(jié)，產(chǎn)生許多無用的歸結(jié)式，嚴重的是會產(chǎn)生組合爆炸問題。 常用的歸結(jié)策略可分為兩大類:刪除策略通過刪除某些無用的子句來縮小歸結(jié)范圍；限制策略通過對參加歸結(jié)的子句進行某些限制，來減少歸結(jié)的盲目性，以盡快得到空子句。 2022/7/2857例 等腰三角形ABC，AD為底邊的高，試證明BD=CD.證明：已知: AB=AC ADBC 求證：BD=CDE(AB,AC)，E(ADB, ADC) ， E(ADB, 90) (x)(y)E(mx,my) E(nx,ny) E(lx,ly)子句：E(mx,my) E(nx,ny) E(lx,ly)E(rp, tq) 表示三角形p、q的兩個邊(

34、角)等E(BD,CD), E(BD, CD) 直角三角形兩邊相等，第三遍也相等。ABCD2022/7/2858問題求解例 已知：張和李是同班同學(xué)。如果x和y是同班同學(xué)，則x的教室也是y的教室?，F(xiàn)在張在302教室上課。 問：現(xiàn)在李在哪里上課?解：定義謂詞： C(x,y) x和y是同班同學(xué) At(x，u) x在u教室上課已知前提用謂詞公式表示， 并化為子句集：C(zhang，1i) C(zhang，1i)(x)(y)(u)(C(x,y)At(x,u)At(y,u) C(x,y)At(x,u)At(y,u) At (zhang, 302) At (zhang, 302)(C(x,y) At(x,u)

35、At(y,u)2022/7/2859問題求解（續(xù)）把目標的否定用謂詞公式表示如下 (v)At(1i，v)把目標的否定化成子句式，并用重言式At(li,v)At(li,v)替代子句集：C(zhang，1i)、C(x,y)At(x,u)At(y,u)、At(zhang，302)、At(li,v)At(li,v)At(li,v)At(li,v)C(x,y)At(x,u)At(y,u)At(li,v) C(x,li)At(x,v)C(zhang,1i)At(li,v) At(zhang,v)At(zhang, 302)At(li, 302) li/y, v/u zhang/x 302/v2022/7/

36、2860WFF的基本等價式及推理規(guī)則現(xiàn)一并歸納于下： 1 雙重否定律(否定之否定) (P) P 2 蘊含等價式P(x) Q(x) P(x) Q(x) 3 摩根定律 (P(x) Q(x) P(x) Q(x) (P(x) Q(x) P(x) Q(x) 4 逆否律 P(x) Q(x) Q(x) P(x) 5 分配律 P(x) (Q(x) R(x) (P(x) Q(x) (P(x) R(x) P(x) (Q(x) R(x) (P(x) Q(x) (P(x) R(x) 6 交換律 P(x) Q(x) Q(x) P(x) P(x) Q(x) Q(x) P(x) 7 結(jié)合律 (P(x) Q(x) R(x) P(x) (Q(x) R(x) (P(x) R(x) R(x) P(x) (Q(x) R(x)2022/