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

第三講

產(chǎn)生式表示法

及

應(yīng)用2023/8/8第三講產(chǎn)生式表示法

及

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

PQ 或 IFPTHENQ二、不確定性規(guī)則知識(shí)的表示方法

PQ(置信度)或 IFPTHENQ(置信度)第一節(jié)知識(shí)的表示方法一、確定性規(guī)則知識(shí)的表示方法3第二節(jié)產(chǎn)生式系統(tǒng)的組成

一個(gè)典型的產(chǎn)生式系統(tǒng)由規(guī)則庫(kù)、綜合數(shù)據(jù)庫(kù)、推理機(jī)三大部分組成。它們之間的關(guān)系如圖所示。推理機(jī)規(guī)則庫(kù)綜合數(shù)據(jù)庫(kù)2023/8/84第二節(jié)產(chǎn)生式系統(tǒng)的組成一個(gè)典型的產(chǎn)生式系統(tǒng)由一、規(guī)則庫(kù)(知識(shí)庫(kù))用于描述某領(lǐng)域內(nèi)知識(shí)的產(chǎn)生式（規(guī)則）集合，是某領(lǐng)域知識(shí)的存儲(chǔ)器。也稱知識(shí)庫(kù)。包含著將問(wèn)題從初始狀態(tài)轉(zhuǎn)換成目標(biāo)狀態(tài)（或解狀態(tài)）的那些變換規(guī)則。是專家系統(tǒng)的核心。2023/8/85一、規(guī)則庫(kù)(知識(shí)庫(kù))用于描述某領(lǐng)域內(nèi)知識(shí)的產(chǎn)生式（規(guī)則）集二、綜合數(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ù)又稱為動(dòng)態(tài)數(shù)據(jù)庫(kù)、短期數(shù)據(jù)庫(kù)緩沖器。綜合數(shù)據(jù)庫(kù)是產(chǎn)生式系統(tǒng)中主要的數(shù)據(jù)結(jié)構(gòu)，可以通過(guò)簡(jiǎn)單的表、數(shù)組、帶索引的文件結(jié)構(gòu)、關(guān)系數(shù)據(jù)庫(kù)等來(lái)實(shí)現(xiàn)。2023/8/86二、綜合數(shù)據(jù)庫(kù)存儲(chǔ)所求解問(wèn)題的初始狀態(tài)及已知事實(shí)，推理的中三、推理機(jī)一個(gè)或一組程序，用來(lái)控制和協(xié)調(diào)規(guī)則庫(kù)與綜合數(shù)據(jù)庫(kù)的運(yùn)行。包含推理方式和控制策略。2023/8/87三、推理機(jī)一個(gè)或一組程序，用來(lái)控制和協(xié)調(diào)規(guī)則庫(kù)與綜合數(shù)據(jù)庫(kù)第三節(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í)。2023/8/88第三節(jié)產(chǎn)生式系統(tǒng)的控制策略一、作用匹配將當(dāng)前綜合數(shù)據(jù)庫(kù)索引變量近似過(guò)濾專一性排序、規(guī)則排序、規(guī)模排序、折射、最新性、特殊性規(guī)則庫(kù)匹配沖突集規(guī)則觸發(fā)規(guī)則執(zhí)行沖突消解推理控制2023/8/89綜合數(shù)據(jù)庫(kù)索引變量近似過(guò)濾專一性排序、規(guī)則排序、規(guī)模排序、折第四節(jié)產(chǎn)生式系統(tǒng)的推理方式

產(chǎn)生式系統(tǒng)的問(wèn)題求解過(guò)程事實(shí)上就是對(duì)解空間的搜索過(guò)程，又稱為推理過(guò)程，根據(jù)推理過(guò)程進(jìn)行的方向或者搜索的方向可分為正向推理、反向推理、雙向推理。2023/8/810第四節(jié)產(chǎn)生式系統(tǒng)的推理方式產(chǎn)生式系統(tǒng)的問(wèn)題求解過(guò)一、正向推理它從已知事實(shí)出發(fā)，通過(guò)與規(guī)則庫(kù)中產(chǎn)生式的條件匹配，然后執(zhí)行匹配規(guī)則的動(dòng)作，求得結(jié)論。正向推理方式又稱為數(shù)據(jù)驅(qū)動(dòng)方式。推理過(guò)程

綜合數(shù)據(jù)庫(kù)中含有事實(shí)P1，則應(yīng)用則進(jìn)行正向推理，即從P1出發(fā)推導(dǎo)出q3的過(guò)程：如規(guī)則集：規(guī)則1：P1→P2

規(guī)則2：P2→P3規(guī)則3：P3→q32023/8/811一、正向推理它從已知事實(shí)出發(fā)，通過(guò)與規(guī)則庫(kù)中產(chǎn)生式的條件匹配產(chǎn)生式系統(tǒng)正向推理的一種算法(1)讀入初始數(shù)據(jù)(事實(shí))集到綜合數(shù)據(jù)庫(kù)；(2)Repeat{取出第i條規(guī)則；規(guī)則i所有前件與綜合數(shù)據(jù)庫(kù)的所有事實(shí)進(jìn)行比較；

if規(guī)則匹配成功then把規(guī)則加入沖突集；

if沖突集為空thengoto(3)；沖突消解；把所選擇規(guī)則的結(jié)論加入綜合數(shù)據(jù)庫(kù)；

if到達(dá)目標(biāo)節(jié)點(diǎn)thengoto(3)；

i=i+1；}(3)結(jié)束。2023/8/812產(chǎn)生式系統(tǒng)正向推理的一種算法(1)讀入初始數(shù)據(jù)(事實(shí))集到例：初始狀態(tài)Start目標(biāo)狀態(tài)Goal規(guī)則庫(kù)R1：ifPandQthenGoalR2：ifRandSthenPR3：ifWandRthenQR4：ifTandUthenQR5：ifV thenSR6：ifStartthenVandRandQ執(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ī)則2023/8/813例：初始狀態(tài)Start目標(biāo)狀態(tài)二、反向推理基本原理：將目標(biāo)與規(guī)則庫(kù)中規(guī)則的動(dòng)作部分匹配，然后把匹配規(guī)則的條件作為要證明的子目標(biāo)，求得已知事實(shí)。反向推理方式又稱為目標(biāo)驅(qū)動(dòng)方式推理過(guò)程如規(guī)則1：P1→P2

規(guī)則2：P2→P3

規(guī)則3：P3→q3應(yīng)用反向推理方法獲取目標(biāo)q3的過(guò)程：2023/8/814二、反向推理基本原理：將目標(biāo)與規(guī)則庫(kù)中規(guī)則的動(dòng)作部分匹配，然例：初始狀態(tài)Start目標(biāo)狀態(tài)GoalR1：ifPandQthenGoalR2：ifRandSthenPR3：ifWandRthenQR4：ifTandUthenQR5：ifV thenSR6：ifStartthenVandRandQ執(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,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ī)則2023/8/815例：初始狀態(tài)Start目標(biāo)狀態(tài)三、雙向推理雙向推理是一種既正向又反向的推理。推理從兩個(gè)方向同時(shí)進(jìn)行，直至某個(gè)中間界面上兩個(gè)方向結(jié)果相符便成功結(jié)束?？刂撇呗员惹皟煞N方法都要復(fù)雜。2023/8/816三、雙向推理雙向推理是一種既正向又反向的推理。推理從兩個(gè)方向第五節(jié)對(duì)產(chǎn)生式系統(tǒng)的評(píng)價(jià)一、特點(diǎn)具有豐富的知識(shí)表示能力，可以簡(jiǎn)單直觀的規(guī)則方式表達(dá)人類的經(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ù)提供便利條件。2023/8/817第五節(jié)對(duì)產(chǎn)生式系統(tǒng)的評(píng)價(jià)一、特點(diǎn)具有豐富的知識(shí)表示能力，產(chǎn)生式系統(tǒng)的規(guī)則鏈接推理過(guò)程相似于人類求解問(wèn)題時(shí)的邏輯思維過(guò)程，可把產(chǎn)生式系統(tǒng)用作人類行為的啟發(fā)式模型，模擬人類的邏輯思維過(guò)程。推理方向的可逆性。由于產(chǎn)生式規(guī)則的前件和后件結(jié)構(gòu)類似，可同時(shí)進(jìn)行正向和反向推理，即混合推理。2023/8/818產(chǎn)生式系統(tǒng)的規(guī)則鏈接推理過(guò)程相似于人類求解問(wèn)題時(shí)的邏輯思維過(guò)二、適合場(chǎng)合知識(shí)結(jié)構(gòu)類似于產(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)典分類學(xué)等。2023/8/819二、適合場(chǎng)合知識(shí)結(jié)構(gòu)類似于產(chǎn)生式規(guī)則的領(lǐng)域，如醫(yī)療診斷系統(tǒng)三、缺陷推理效率低速度慢實(shí)時(shí)性能差容易產(chǎn)生組合爆炸

試驗(yàn)表明，產(chǎn)生式系統(tǒng)在匹配階段所花費(fèi)的時(shí)間大約為產(chǎn)生式系統(tǒng)工作周期的90％。而沖突消解及執(zhí)行階段所花費(fèi)的時(shí)間大約占工作周期的10％。2023/8/820三、缺陷推理效率低試驗(yàn)表明，產(chǎn)生式系統(tǒng)在匹配階段所花

若欲求解的問(wèn)題可視為問(wèn)題空間中一個(gè)狀態(tài)到另一個(gè)狀態(tài)的變換序列，則可用產(chǎn)生式系統(tǒng)求解。諸如8數(shù)碼(8Puzzle)、旅行商(travelingsalesman)、漢諾塔(TowerofHanoi)、傳教士與食人魔(Missionariesand

cannibals)、符號(hào)積分(Symbolicintegration)、猴子與香蕉(Monkeyandbananas)等經(jīng)典人工智能問(wèn)題的求解，以人類專家知識(shí)為基礎(chǔ)的專家系統(tǒng)的問(wèn)題求解，從本質(zhì)上都可以看作是從初始狀態(tài)到目標(biāo)狀態(tài)的推導(dǎo)變換過(guò)程，因而都可用產(chǎn)生式系統(tǒng)來(lái)求解。2023/8/821若欲求解的問(wèn)題可視為問(wèn)題空間中一個(gè)狀態(tài)到另一

專家系統(tǒng)

專家系統(tǒng)結(jié)構(gòu)選擇恰當(dāng)與否，與專家系統(tǒng)的適用性和有效性密切相關(guān)的。用戶界面推理執(zhí)行機(jī)構(gòu)動(dòng)態(tài)庫(kù)知識(shí)庫(kù)知識(shí)獲取解釋機(jī)構(gòu)用戶推理機(jī)根據(jù)動(dòng)態(tài)庫(kù)的當(dāng)前狀態(tài)，利用知識(shí)庫(kù)中的知識(shí)進(jìn)行推理。用戶界面亦稱人機(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ò)程等形式表示。2023/8/822專家系統(tǒng)專家系統(tǒng)結(jié)構(gòu)選擇恰當(dāng)與否，與專家系統(tǒng)的適用

專家系統(tǒng)的開(kāi)發(fā)過(guò)程

專家系統(tǒng)是一個(gè)復(fù)雜的智能軟件，與一般軟件類似，但又有不同的特點(diǎn)。一般軟件處理的對(duì)象是數(shù)值、文字、圖形等信息，且有固定的算法序列，而專家系統(tǒng)軟件處理的對(duì)象是以符號(hào)表示的知識(shí)，在運(yùn)行過(guò)程中常有回溯發(fā)生，因此專家系統(tǒng)的開(kāi)發(fā)過(guò)程與一般軟件的開(kāi)發(fā)有所不同。專家系統(tǒng)的創(chuàng)始人費(fèi)根鮑姆教授把開(kāi)發(fā)專家系統(tǒng)的技術(shù)稱之為知識(shí)工程，即以知識(shí)獲取、知識(shí)表示、知識(shí)運(yùn)用(推理)為中心。根據(jù)這個(gè)思想，可把專家系統(tǒng)的開(kāi)發(fā)過(guò)程分為以下幾個(gè)階段。2023/8/823專家系統(tǒng)的開(kāi)發(fā)過(guò)程2023/7/31231問(wèn)題定義與系統(tǒng)分析在著手開(kāi)發(fā)一個(gè)專家系統(tǒng)時(shí)，首先應(yīng)了解清楚用戶的需求，確定欲解決的問(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ì)效益分析。最后寫出系統(tǒng)工作的數(shù)據(jù)(信息)流程圖，寫出分析報(bào)告及有關(guān)文檔。2023/8/8241問(wèn)題定義與系統(tǒng)分析2023/7/31242知識(shí)獲取

知識(shí)獲取階段的主要工作是根據(jù)所確定的系統(tǒng)目標(biāo)及限定的問(wè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)表示法等，把獲取到的專家知識(shí)邏輯地表達(dá)出來(lái)，并以適當(dāng)?shù)男问酱鎯?chǔ)到計(jì)算機(jī)中。2023/8/8252知識(shí)獲取2023/7/31254軟件實(shí)現(xiàn)這一階段的工作與一般軟件設(shè)計(jì)類似，應(yīng)遵循軟件工程的原則，進(jìn)行系統(tǒng)設(shè)計(jì)、編碼、測(cè)試，建立知識(shí)庫(kù)，實(shí)現(xiàn)推理機(jī)，動(dòng)態(tài)存儲(chǔ)器，人機(jī)接口，知識(shí)獲取等專家系統(tǒng)程序模塊，構(gòu)成一個(gè)可運(yùn)行的專家系統(tǒng)原型軟件。2023/8/8264軟件實(shí)現(xiàn)2023/7/31265系統(tǒng)測(cè)試與評(píng)價(jià)專家系統(tǒng)開(kāi)發(fā)是一個(gè)長(zhǎng)期反饋的過(guò)程，對(duì)所生成的專家系統(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é)論是否可信，用戶是否滿意；人機(jī)接口使用是否方便，實(shí)用；系統(tǒng)的成本與效益情況等。2023/8/8275系統(tǒng)測(cè)試與評(píng)價(jià)2023/7/3127新一代專家系統(tǒng)新一代專家系統(tǒng)的特征：(1)

并行技術(shù)與分布處理(2)

多專家系統(tǒng)協(xié)同工作(synergeticexpertsystem)(3)

具有自學(xué)習(xí)功能(4)

引入新的推理機(jī)制(5)

具有自糾錯(cuò)和自完善能力(6)

先進(jìn)的智能人機(jī)接口2023/8/828新一代專家系統(tǒng)新一代專家系統(tǒng)的特征：2023/7/3128第四講基于邏輯的問(wèn)題求解方法邏輯表示法用數(shù)理邏輯表示知識(shí)

經(jīng)典邏輯（標(biāo)準(zhǔn)邏輯）

非經(jīng)典邏輯一階謂詞是一種形式語(yǔ)言，可以表示和推理客觀世界的屬性和關(guān)系。命題邏輯和一階謂詞邏輯模態(tài)邏輯、時(shí)序邏輯、非單調(diào)邏輯、多值邏輯2023/8/829第四講基于邏輯的問(wèn)題求解方法邏輯表示法用數(shù)理邏輯表示知29命題取值為真或假(表示是否成立)的句子謂詞帶有變量(參數(shù))的命題謂詞p(x1，x2，…，xn)

一元謂詞謂詞與一個(gè)個(gè)體的屬性blue(desk)

多元謂詞謂詞與多個(gè)個(gè)體間的關(guān)系TEACHER(x,y)

一階謂詞xi為常量、變?cè)蚝瘮?shù)高階謂詞

xi本身為一階謂詞第一節(jié)一階謂詞邏輯基礎(chǔ)謂詞用來(lái)描述個(gè)體（可以獨(dú)立存在的事物）之間的關(guān)系或?qū)傩?023/8/830命題取值為真或假(表示是否成立)的句子第一節(jié)一階謂30一、謂詞邏輯的符號(hào)體系常量 以小寫字母組成的符號(hào)串變量符號(hào) 習(xí)慣上是大寫字母開(kāi)始

函數(shù)符號(hào) 通常以小寫字母或小寫字母串表示謂詞符號(hào) 通常以小寫字母或小寫字母串表示，不可拆散逗號(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)2023/8/831一、謂詞邏輯的符號(hào)體系常量 以小寫字母組成的符號(hào)串202331連接詞～：否定(非)

～inroom(robot，r2)∧合取(與)like(he，music)∧like(he，painting)∨析取(或)

plays(liming，basketball)∨plays(liming

，football)→蘊(yùn)含(IF……THEN)owns(she，book-1)→color(book-1，blue)≡等價(jià)(雙條件)2023/8/832連接詞～：否定(非)2023/7/313232量詞量詞是由量詞符號(hào)和被量化的變?cè)M成的表達(dá)式：全稱量詞符號(hào)，表示所有的。例如，所有的籃球運(yùn)動(dòng)員都很高，表示為

(X)(basketball_player(X)tall(X))：存在量詞符號(hào)，表示存在某一些。例如，一些人喜歡狗，表示為

(X)(person(X)∧

likes(X,dog))2023/8/833量詞量詞是由量詞符號(hào)和被量化的變?cè)M成的表達(dá)式2033二、謂詞邏輯的知識(shí)表示若量詞僅對(duì)謂詞的個(gè)體(變量)而不能對(duì)謂詞自身起限定作用，即把謂詞名視為常量，稱其為一階謂詞。一階謂詞邏輯可嚴(yán)密而精確地表達(dá)復(fù)雜的人類知識(shí)，在很多領(lǐng)域可以得到直接的應(yīng)用?？梢员硎荆菏挛锏臓顟B(tài)、屬性、概念的事實(shí)性知識(shí)；否定、析取或合取符號(hào)連接起來(lái)的謂詞公式事物的因果關(guān)系蘊(yùn)含式表示

xy2023/8/834二、謂詞邏輯的知識(shí)表示若量詞僅對(duì)謂詞的個(gè)體(34

1

形式化的領(lǐng)域

在形式化的領(lǐng)域中，知識(shí)或信息是用對(duì)象和它們的屬性，以及它們之間的關(guān)系表示的。關(guān)系數(shù)據(jù)庫(kù)可以認(rèn)為是采用了一階謂詞邏輯的形式，每個(gè)關(guān)系類型對(duì)應(yīng)著一個(gè)謂詞。occupant(owen，301)telephone(741，301)2023/8/8351形式化的領(lǐng)域在形式化的領(lǐng)域中，知識(shí)或信息是用352非形式化的領(lǐng)域例如所有的整數(shù)不是偶數(shù)就是奇數(shù)定義integer(X):X為整數(shù)；

even(X):X為偶數(shù);

odd(X):X為奇數(shù)謂詞表示

(X)(integer(X)even

(X)∨odd

(X))2023/8/8362非形式化的領(lǐng)域例如所有的整數(shù)不是偶數(shù)就是奇36在人工智能中常用的是一階謂詞邏輯，因此本章介紹的內(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)2023/8/837在人工智能中常用的是一階謂詞邏輯，因此本章介紹的內(nèi)容37三、謂詞演算公式原子公式不含任何連接詞及量詞的謂詞公式

p(X1,X2,……，Xn)

，X—個(gè)體變量謂詞演算的合式公式(WFF—well-formedformula)原子公式是合式公式。若A是合式公式，則～A也是合式公式。若A，B是合式公式，則A∧B，A∨B，A→B，A≡B，也都是合式公式。若A是合式公式，X是個(gè)體變量，則(X)A，(X)A也是合式公式只有按a)—d)所得的公式才是合式公式。2023/8/838三、謂詞演算公式原子公式不含任何連接詞及量詞的謂38第二節(jié)邏輯推理如果謂詞公式p對(duì)任意非空個(gè)體域上的任一解釋都取得真值true，則稱p永真。對(duì)于謂詞公式p，如果至少存在非空個(gè)體域D上的一個(gè)解釋，使公式p在此解釋下的真值為true，則稱公式p在D上是可滿足的。謂詞公式的可滿足性也稱為相容性。如果謂詞公式p對(duì)非空個(gè)體域D上的任一解釋都取真值false，則稱P永假。謂詞公式的永假性又稱不可滿足性或不相容性。2023/8/839第二節(jié)邏輯推理如果謂詞公式p對(duì)任意非空個(gè)體域上的任一解39一、等價(jià)式交換律 PQQP PQQP

結(jié)合律 (PQ)RP(QR)

(PQ)RP(QR)分配律 P(QR)(PQ)(PR)

P(QR)(PQ)(PR)摩根定理 ~(PQ)~P~Q ~(PQ)~P~Q

否定之否定~(~P)P

2023/8/840一、等價(jià)式交換律 PQQP PQQ40吸收律

P(PQ)P

P(PQ)P補(bǔ)余律

P~PT P~PF逆否定律

PQ~Q~P PQ~PQ量詞轉(zhuǎn)換律

~(x)P(x)(x)(~P(x))

~(x)P(x)(x)(~P(x))量詞分配律2023/8/841吸收律 P(PQ)P P(PQ)P241p(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)]是永真的2023/8/842p(a)p(b)p(a)∨p(b)~p(a)∨[p(a)∨p42二、自然演繹推理1

析取三段論~P,PQQ2

假言推理P,PQQ3

假言三段論P(yáng)Q，QRPR4

拒取三段論~Q,PQ~P2023/8/843二、自然演繹推理1析取三段論~P,PQ43例設(shè)已知如下事實(shí)：

(1)

只要是需要編程序的課，王程都喜歡。

(2)

所有的程序設(shè)計(jì)語(yǔ)言課都是需要編程序的課

(3)

C是一門程序設(shè)計(jì)語(yǔ)言課。求證：王程喜歡C這門課。證明：首先定義謂詞

program(X)X是需要編程序的課。

like(X,Y)X喜歡Y。

language(X)X

是—門程序設(shè)計(jì)語(yǔ)言課。program(X)like(wang,X)

(X)(language(X)program(X))language(C)2023/8/844例設(shè)已知如下事實(shí)：program(X)like(44把已知事實(shí)及待求解問(wèn)題用謂詞公式表示如下：

program(X)like(wang,X)、

(X)(language(X)program(X))、language(C)

應(yīng)用推理規(guī)則進(jìn)行推理：全稱例化language(Y)program(Y)

假言推理language(C),language(Y)program(Y)

program(C)假言推理program(C),

program(X)like(wang,X)

like(wang,C)

王程喜歡C這門課。把一個(gè)真的謂詞公式中的任意的全稱量詞變量替換為定義域中的任意的適當(dāng)項(xiàng)。2023/8/845把已知事實(shí)及待求解問(wèn)題用謂詞公式表示如下：把45二、歸結(jié)(消解)原理簡(jiǎn)介

1965年Robinson發(fā)現(xiàn)的歸結(jié)原理(refutation)。是以邏輯演繹為基礎(chǔ)進(jìn)行邏輯推理。它的基本思想可用如下定理解釋：定理Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng)

(P)(~Q)是不可滿足的。

把已知條件表示謂詞公式，再化為一組子句；

欲證的目標(biāo)也化為一個(gè)子句的否定，

把目標(biāo)子句與條件子句合在一起推理，若能推出矛盾(空子句)，則可證明此目標(biāo)是成立的。2023/8/846二、歸結(jié)(消解)原理簡(jiǎn)介1965年Robinso46

已知兩子句C1=P

C1

和C2=~P

C2

，C1不等于C2，其中一個(gè)所含的

~P，剛好是另一個(gè)子句中P的否定，根據(jù)這兩個(gè)子句，推出一個(gè)新子句，即R(C1,C2)=C1

C2，稱作這兩個(gè)子句的歸結(jié)式。

P、~P為互補(bǔ)對(duì)。

實(shí)現(xiàn)歸結(jié)推理的關(guān)鍵步驟是置換合一與尋求子句集中的互補(bǔ)對(duì)。2023/8/847已知兩子句C1=PC1和C2=47歸結(jié)式

PQ~PQ歸結(jié)式

Q父輩1析取三段論

2合并3重言式4空子句(矛盾)5假言三段論P(yáng)~PQ(PQ)歸結(jié)式Q父輩PQ~P~Q歸結(jié)式Q~Q父輩PQ~P~Q

P

~PP~P歸結(jié)式NIL

父輩~PQ

(PQ)~QR

(QR)歸結(jié)式~PR

(PR)父輩2023/8/848歸結(jié)式PQ~PQ歸結(jié)式Q父輩1析取三48自動(dòng)歸結(jié)證明的過(guò)程：(1)否定G，得

~G；(2)

把~G添加到S中，得新集合{S,~G}；(3)

把新產(chǎn)生的集合{S,～G}化成子句集；(4)

重復(fù)歸結(jié)過(guò)程，推導(dǎo)出一個(gè)表示矛盾的空子句。2023/8/849自動(dòng)歸結(jié)證明的過(guò)程：(1)否定G，得~G；2023/7/349WFF化為子句的基本步驟重復(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)

移所有量詞到前部，形成前束范式

(X)p(X)(W)q(W)改為(X)(W)[p(X)q(W)]2023/8/850WFF化為子句的基本步驟重復(fù)運(yùn)用蘊(yùn)含等價(jià)式，消去蘊(yùn)含→20250消去存在量詞，形成對(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ù)2023/8/851消去存在量詞，形成對(duì)應(yīng)的S范式標(biāo)準(zhǔn)式 母式Skolem51例已知每個(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是Internet；

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))2023/8/852例已知每個(gè)使用Internet的人都想從網(wǎng)絡(luò)獲得信息，52

條件：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)[~(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)2023/8/853條件：W=(x)[(y)(U(x,y)∧53

(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è)子句：

~U(x，y)∨～I(xiàn)(y)∨(F(f(x))

~U(x，y)∨～I(xiàn)(y)∨E(x，f(x))2023/8/854(4)把母式化成合取范式前提W對(duì)應(yīng)54

結(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對(duì)應(yīng)子句集的三個(gè)子句：

~F(c)I(y)U(x，y)2023/8/855結(jié)論：G＝~(u)F(u)→(x)(y55對(duì)(1)施加置換

c／f(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(xiàn)(y)∨(F(f(x))~F(c)c／f(x)~U(x,y)∨~I(y)I(y)~U(x,y)U(x,y)NIL歸結(jié)反演樹(shù)2023/8/856(1)~U(x,y)∨~I(y)∨(F(f(x))~U56歸結(jié)策略歸結(jié)演繹推理實(shí)際上就是從子句集中不斷尋找可進(jìn)行歸結(jié)的子句對(duì)，并通過(guò)對(duì)這些子句對(duì)的歸結(jié)，最終得出一個(gè)空子句的過(guò)程。盲目地全面進(jìn)行歸結(jié)，產(chǎn)生許多無(wú)用的歸結(jié)式，嚴(yán)重的是會(huì)產(chǎn)生組合爆炸問(wèn)題。常用的歸結(jié)策略可分為兩大類:刪除策略——通過(guò)刪除某些無(wú)用的子句來(lái)縮小歸結(jié)范圍；限制策略——通過(guò)對(duì)參加歸結(jié)的子句進(jìn)行某些限制，來(lái)減少歸結(jié)的盲目性，以盡快得到空子句。2023/8/857歸結(jié)策略歸結(jié)演繹推理實(shí)際上就是從子句集中不斷57例等腰三角形ABC，AD為底邊的高，試證明BD=CD.證明：已知:AB=ACADBC

求證：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è)邊(角)等E(BD,CD),~E(BD,CD)直角三角形兩邊相等，第三遍也相等。ABCD2023/8/858例等腰三角形ABC，AD為底邊的高，試證明BD=CD.證58問(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))At(y,u)2023/8/859問(wèn)題求解例已知：張和李是同班同學(xué)。如果x和y是同班同學(xué)，59問(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/v}2023/8/860問(wèn)題求解（續(xù)）把目標(biāo)的否定用謂詞公式表示如下~(v)60WFF的基本等價(jià)式及推理規(guī)則現(xiàn)一并歸納于下：

1雙重否定律(否定之否定)～(～P)≡P2蘊(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))2023/8/861WFF的基本等價(jià)式及推理規(guī)則現(xiàn)一并歸納于下：2023/7/361WFF的基本等價(jià)式及推理規(guī)則（續(xù)）：8量詞轉(zhuǎn)換律～(x)P(x)≡(x)[～P(x)]～(x)Q(x)≡(x)[～Q(x)]9易名規(guī)則

(x)P(x)≡(y)P(y)(x)P(x)≡(y)P(y)

在一個(gè)量化的表達(dá)式中的約束變量是一類虛元，它可以用任何一個(gè)不在表達(dá)式中出現(xiàn)過(guò)的其它變量符號(hào)來(lái)代替。10量詞分配律

(x)[P(x)∨Q(x)]