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

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

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

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

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

5、據(jù)(事實(shí))集到綜合數(shù)據(jù)庫(kù)；(2) Repeat 取出第i條規(guī)則； 規(guī)則i 所有前件與綜合數(shù)據(jù)庫(kù)的所有事實(shí)進(jìn)行比較； if 規(guī)則匹配成功 then 把規(guī)則加入沖突集； if 沖突集為空 then goto (3)； 沖突消解； 把所選擇規(guī)則的結(jié)論加入綜合數(shù)據(jù)庫(kù)； if 到達(dá)目標(biāo)節(jié)點(diǎn) then goto (3)； i=i+1； (3) 結(jié)束。2022/7/2813例：初始狀態(tài) Start 目標(biāo)狀態(tài) Goal規(guī)則庫(kù)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í)行過(guò)程動(dòng)態(tài)庫(kù)沖突集觸發(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ā)的或根本沒(méi)有被觸發(fā)的規(guī)則 如果出現(xiàn)“平局”，選取其中的第一個(gè)規(guī)則2022/7/2814二、反向推理基本原理：將目標(biāo)與規(guī)則庫(kù)中規(guī)則的動(dòng)作部分匹配，然后把匹配規(guī)則的條件作為要證明的子目標(biāo)，求得已知事實(shí)。反向推理方式又稱(chēng)為目標(biāo)驅(qū)動(dòng)方式

7、推理過(guò)程如規(guī)則1：P1P2 規(guī)則2：P2P3 規(guī)則3： P3q3應(yīng)用反向推理方法獲取目標(biāo)q3的過(guò)程：2022/7/2815例：初始狀態(tài) Start 目標(biāo)狀態(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í)行過(guò)程動(dòng)態(tài)庫(kù)沖突集觸發(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ā)的或根本沒(méi)有被觸發(fā)的規(guī)則 如果出現(xiàn)“平局”，選取其中的第一個(gè)規(guī)則2022/7/2816三、雙向推理雙向推理是一種既正向又反向的推理。推理從兩個(gè)方向同時(shí)進(jìn)行，直至某個(gè)中間界面上兩個(gè)方向結(jié)果相符便成功結(jié)束?？刂撇呗员惹皟煞N方法都要復(fù)雜。2022/7/281

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

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

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

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

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

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

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

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

17、一階謂詞第一節(jié) 一階謂詞邏輯基礎(chǔ) 謂詞用來(lái)描述個(gè)體（可以獨(dú)立存在的事物）之間的關(guān)系或?qū)傩?022/7/2830一、謂詞邏輯的符號(hào)體系 常量以小寫(xiě)字母組成的符號(hào)串 變量符號(hào)習(xí)慣上是大寫(xiě)字母開(kāi)始 函數(shù)符號(hào)通常以小寫(xiě)字母或小寫(xiě)字母串表示 謂詞符號(hào)通常以小寫(xiě)字母或小寫(xiě)字母串表示，不可拆散 逗號(hào)及括號(hào)(圓括號(hào)、方括號(hào)、花括號(hào)) 將變量符號(hào)、函數(shù)符號(hào)、謂詞符號(hào)及常量隔開(kāi)，僅用于構(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) 蘊(yùn)含 (IFTHEN) owns ( she，book-1) color(book-1，blue) 等價(jià)(雙條件)2022/7/2832量詞 量詞是由量詞符號(hào)和被量化的變?cè)M成的表達(dá)式：全稱(chēng)量詞符號(hào)，表示所有的。 例如，所有的籃球運(yùn)動(dòng)員都很高，表示為 (X) (basketball_player(X) tall(X)：存在量詞符號(hào)，表示存在某一些。 例如，一些人喜歡狗，表示為 (X ) (person(X) likes(X, dog

19、)2022/7/2833二、謂詞邏輯的知識(shí)表示 若量詞僅對(duì)謂詞的個(gè)體(變量)而不能對(duì)謂詞自身起限定作用，即把謂詞名視為常量，稱(chēng)其為一階謂詞。 一階謂詞邏輯可嚴(yán)密而精確地表達(dá)復(fù)雜的人類(lèi)知識(shí)，在很多領(lǐng)域可以得到直接的應(yīng)用。 可以表示： 事物的狀態(tài)、屬性、概念的事實(shí)性知識(shí)； 否定、析取或合取符號(hào)連接起來(lái)的謂詞公式 事物的因果關(guān)系 蘊(yùn)含式表示 x y2022/7/2834 1 形式化的領(lǐng)域 在形式化的領(lǐng)域中，知識(shí)或信息是用對(duì)象和它們的屬性，以及它們之間的關(guān)系表示的。 關(guān)系數(shù)據(jù)庫(kù)可以認(rèn)為是采用了一階謂詞邏輯的形式，每個(gè)關(guān)系類(lèi)型對(duì)應(yīng)著一個(gè)謂詞。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)容主要針對(duì)一階謂詞邏輯。 設(shè)有三個(gè)積木塊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個(gè)體變量謂詞演算的合式公式( WFF well-formed formula)原子公式是合式公式。若A是合式公式，則A也是合式公式。若A，B是合式公式，則AB，AB，AB，AB，也都是合式公式。若A是合式公式，X是個(gè)體變量，則(X)A，(X)A也是合式公式只有按a)d)所得的公式才是合式公式。2022/7/2838第二節(jié) 邏輯推理如果謂詞公式p對(duì)任意非空個(gè)體域上的任一解釋都取得真值true，則稱(chēng)p永真。對(duì)于謂詞公式p，如果至少存在非空個(gè)體域D上的一個(gè)解釋?zhuān)构絧在此解釋下的真值為true，則稱(chēng)公式p在D上是可滿(mǎn)足的。謂詞公式的可滿(mǎn)

22、足性也稱(chēng)為相容性。如果謂詞公式p對(duì)非空個(gè)體域D上的任一解釋都取真值false，則稱(chēng)P永假。謂詞公式的永假性又稱(chēng)不可滿(mǎn)足性或不相容性。 2022/7/2839一、等價(jià)式交換律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補(bǔ)余律 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è)已知如下事實(shí)： (1) 只要是需要編程序的課，王程都喜歡。 (2) 所有的程序設(shè)計(jì)語(yǔ)言課都是需要編程序的課 (3) C是一門(mén)程序設(shè)計(jì)語(yǔ)言課。求證：王程喜歡C這門(mén)

24、課。證明：首先定義謂詞 program (X) X是需要編程序的課。 like (X,Y) X喜歡Y。 language (X) X 是門(mén)程序設(shè)計(jì)語(yǔ)言課。program (X)like (wang, X) (X)( language (X) program (X) language (C)2022/7/2844把已知事實(shí)及待求解問(wèn)題用謂詞公式表示如下： program (X) like ( wang, X)、 (X)( language (X) program (X)、language (C) 應(yīng)用推理規(guī)則進(jìn)行推理： 全稱(chēng)例化 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這門(mén)課。 把一個(gè)真的謂詞公式中的任意的全稱(chēng)量詞變量替換為定義域中的任意的適當(dāng)項(xiàng)。2022/7/2845二、歸結(jié)(消解)原理簡(jiǎn)介 1965年Robinson發(fā)現(xiàn)的歸結(jié)原理(refutation)。是以邏輯演繹為基礎(chǔ)進(jìn)行邏輯推理。它的基本思想可用如下定理解釋?zhuān)?定理 Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng) (P) (Q)是不可滿(mǎn)足的。 把已知條件表示謂詞公式，再化為一組子句； 欲證的

26、目標(biāo)也化為一個(gè)子句的否定， 把目標(biāo)子句與條件子句合在一起推理，若能推出矛盾(空子句)，則可證明此目標(biāo)是成立的。2022/7/2846 已知兩子句 C1=P C1 和 C2= P C2 ， C1不等于C2，其中一個(gè)所含的 P，剛好是另一個(gè)子句中P 的否定，根據(jù)這兩個(gè)子句，推出一個(gè)新子句，即R(C1, C2)= C1 C2 ，稱(chēng)作這兩個(gè)子句的歸結(jié)式。 P、P為互補(bǔ)對(duì)。 實(shí)現(xiàn)歸結(jié)推理的關(guān)鍵步驟是置換合一與尋求子句集中的互補(bǔ)對(duì)。2022/7/2847歸結(jié)式 PQ PQ歸結(jié)式 Q父輩1 析取三段論 2 合并3 重言式4 空子句(矛盾)5 假言三段論P(yáng) 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自動(dòng)歸結(jié)證明的過(guò)程：(1)否定G，得 G；(2) 把G添加到S中，得新集合S, G；(3) 把新產(chǎn)生的集合S, G化成子句集；(4) 重復(fù)歸結(jié)過(guò)程，推導(dǎo)出一個(gè)表示矛盾的空子句。 2022/7/2849WFF化為子句的基本步驟重復(fù)運(yùn)用蘊(yùn)含等價(jià)式，消去蘊(yùn)含 p(X) q(X) p(X) q(X)減少的轄域，使最多只作用一個(gè)謂詞上(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 消去存在量詞，形成對(duì)應(yīng)的S范式標(biāo)準(zhǔn)式(X) p(X) q (g(X) W=g(X)利用分配律，把母式化成析取式的合取式。p(X) (q(X) r(X) (p(X) q(X) (p(X) r(X)以逗號(hào)替代所有的 ，形成子句集母式Skolem函數(shù)2022/7/2851例 已知每個(gè)使用Internet的人都想從網(wǎng)絡(luò)獲得信息，證明如網(wǎng)絡(luò)沒(méi)有信息就不會(huì)有人使用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) 消去蘊(yùn)含 辦法：P(x) Q(x) P(x) Q(x)W = (x)(y)(U(x, y)I(y)(u)(F(u)E(x, u)(2) 把的轄域減少到最多只作用于一個(gè)謂詞 利用(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)以逗號(hào)替代所有的(消去符號(hào))，形成子句集S = U(x, y) I(y)(F(f(x), U(x, y) I(y)E(x, f(x) 前提 W 對(duì)應(yīng)子句集的兩個(gè)子句

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) 隱去全稱(chēng)量詞，得到G對(duì)應(yīng)子句集的三個(gè)子句： F(c) I(y) U(x，y) 2022/7/2855對(duì)(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é)反演樹(shù)2022/7/2856歸結(jié)策略 歸結(jié)演繹推理實(shí)際上就是從子句集中不斷尋找可進(jìn)行歸結(jié)的子句對(duì)，并通過(guò)對(duì)這些子句對(duì)的歸結(jié)，最終得出一個(gè)空子句的過(guò)

33、程。 盲目地全面進(jìn)行歸結(jié)，產(chǎn)生許多無(wú)用的歸結(jié)式，嚴(yán)重的是會(huì)產(chǎn)生組合爆炸問(wèn)題。 常用的歸結(jié)策略可分為兩大類(lèi):刪除策略通過(guò)刪除某些無(wú)用的子句來(lái)縮小歸結(jié)范圍；限制策略通過(guò)對(duì)參加歸結(jié)的子句進(jìn)行某些限制，來(lái)減少歸結(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的兩個(gè)邊(

34、角)等E(BD,CD), E(BD, CD) 直角三角形兩邊相等，第三遍也相等。ABCD2022/7/2858問(wèn)題求解例 已知：張和李是同班同學(xué)。如果x和y是同班同學(xué)，則x的教室也是y的教室?，F(xiàn)在張?jiān)?02教室上課。 問(wèn)：現(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問(wèn)題求解（續(xù)）把目標(biāo)的否定用謂詞公式表示如下 (v)At(1i，v)把目標(biāo)的否定化成子句式，并用重言式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的基本等價(jià)式及推理規(guī)則現(xiàn)一并歸納于下： 1 雙重否定律(否定之否定) (P) P 2 蘊(yùn)含等價(jià)式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/