哈工大人工智能課件chpt3124

人工智能原理

第3章

邏輯系統(tǒng)

1第一頁，共一百二十五頁。

本章內(nèi)容

3.1命題邏輯和一階謂詞邏輯

3.2邏輯系統(tǒng)的語法和語義

3.3邏輯推理舉例

3.4邏輯智能體的推理策略

參考書目

附錄形式系統(tǒng)簡介第3章邏輯系統(tǒng)2第二頁，共一百二十五頁。經(jīng)典數(shù)理邏輯AI研究內(nèi)容之一是推理，即研究怎樣使計(jì)算機(jī)獲得自動(dòng)推理的能力數(shù)理邏輯用數(shù)學(xué)方法研究各種推理中的邏輯問題，以推理本身作為研究對象AI要使用邏輯推理，就必然涉及數(shù)理邏輯/數(shù)理邏輯的經(jīng)典部分—經(jīng)典的命題邏輯和一階謂詞邏輯，同時(shí)作為人工智能的知識(shí)表示方法和推理方法而存在；因此數(shù)理邏輯是人工智能的一個(gè)基礎(chǔ)第3章邏輯系統(tǒng)3第三頁，共一百二十五頁。邏輯智能體基于知識(shí)的智能體的核心部件是知識(shí)庫，當(dāng)這些知識(shí)以邏輯形式表示并進(jìn)行相應(yīng)的推理時(shí)，就是邏輯智能體知識(shí)表示：命題邏輯、一階謂詞邏輯推理(一階謂詞邏輯)—主要有3類推理算法：前向鏈接和演繹系統(tǒng)、反向鏈接和邏輯程序設(shè)計(jì)(本章)、歸結(jié)反演和定理證明系統(tǒng)(第4章)采用命題和謂詞演算進(jìn)行推理的系統(tǒng)(如演繹系統(tǒng))是一種典型的邏輯智能體第3章邏輯系統(tǒng)4第四頁，共一百二十五頁。3.1命題邏輯和一階謂詞邏輯

命題、真值、原子公式、合式公式

謂詞、論域、個(gè)體

量詞、變量、函數(shù)

一階語言、一階語言的項(xiàng)第3章邏輯系統(tǒng)5第五頁，共一百二十五頁。命題命題：描述客觀世界的可區(qū)分真假的陳述句,即一個(gè)判斷（經(jīng)典二值邏輯：非真即假）是命題的例子：2+2=4/二月份有30天/2002年威海有地震/北京是中國首都不是命題的例子：快點(diǎn)走吧/張三比李四聰明/公共汽車內(nèi)非常擁擠（各人認(rèn)識(shí)不同）第3章邏輯系統(tǒng)6第六頁，共一百二十五頁。命題變量與真值命題變量（變元）：一個(gè)命題用符號表示，稱為命題符號當(dāng)命題符號代表任一個(gè)命題時(shí)，即為命題變量真值：真或假–一個(gè)命題或命題變量具有真值真值連接詞（5個(gè)）：否定/合取/析取/蘊(yùn)涵/等價(jià)真值函數(shù)：真值聯(lián)結(jié)詞可以視為一元或二元映射(真值函數(shù))，￢是從{T,F}到{T,F}，其余是{T,F}2到{T,F}的映射/其函數(shù)定義由真值表確定第3章邏輯系統(tǒng)7第七頁，共一百二十五頁。簡單命題與復(fù)合命題簡單命題：一個(gè)被視為整體的、具有真或假的命題是簡單命題復(fù)合命題：使用聯(lián)結(jié)詞將簡單命題聯(lián)結(jié)起來的命題是復(fù)合命題第3章邏輯系統(tǒng)8第八頁，共一百二十五頁。命題邏輯基礎(chǔ)定義：合取式：p與q，記做p∧q

析取式：p或q，記做p∨q

蘊(yùn)含式：如果p則q，記做p→q

等價(jià)式：p當(dāng)且僅當(dāng)q，記做pq

第3章邏輯系統(tǒng)9第九頁，共一百二十五頁。命題邏輯基礎(chǔ)定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個(gè)成真賦值，則稱A為可滿足的；…………析取范式：僅由有限個(gè)簡單合取式組成的析取式合取范式：僅由有限個(gè)簡單析取式組成的合取式

第3章邏輯系統(tǒng)10第十頁，共一百二十五頁。命題邏輯基礎(chǔ)基本等值式（24個(gè)）交換律：p∨qq∨p

p∧qq∧p結(jié)合律：(p∨q)∨rp∨(q∨r);

(p∧q)∧rp∧(q∧r)

分配律：p∨(q∧r)(p∨q)∧(p∨r)；

p∧(q∨r)(p∧q)∨(p∧r)

第3章邏輯系統(tǒng)11第十一頁，共一百二十五頁。命題邏輯基礎(chǔ)基本等值式（24個(gè)）摩根律:～(p∨q)～p∧～q；

～(p∧q)～p∨～q吸收律:p∨(p∧q)p；

p∧(p∨q)p同一律:p∨0p；

p∧1p蘊(yùn)含等值式：p→q

～p∨q

假言易位式:p→q～p→～q

第3章邏輯系統(tǒng)12第十二頁，共一百二十五頁。命題語言與原子公式命題邏輯：研究復(fù)合命題之間的推導(dǎo)關(guān)系命題語言：是命題邏輯使用的形式語言，是符號的集合,用Lp表示

包括：命題符號、連接詞、左右括號原子公式：命題語言中的一個(gè)表達(dá)式是原子公式，當(dāng)且僅當(dāng)它是一個(gè)命題符號/原子公式也稱為文字(包括正文字和負(fù)文字)第3章邏輯系統(tǒng)13第十三頁，共一百二十五頁。命題邏輯的合式公式合式公式(well-formedformula)，簡稱公式，記作wff：一個(gè)表達(dá)式是一個(gè)公式，當(dāng)且僅當(dāng)它能通過有限次地使用下述步驟生成：(1)原子公式是公式；(2)如果A是公式，則(￢A)是公式；(3)如果A、B均為公式，則A*B是公式，其中*表示∧∨→≡中的任意一個(gè)公式的形成規(guī)則命題邏輯的主要研究對象是公式第3章邏輯系統(tǒng)14第十四頁，共一百二十五頁。例子將陳述句轉(zhuǎn)化成命題公式。如：設(shè)“下雨”為p，“騎車上班”為q1“只要不下雨，我就騎車上班”。~p是q的充分條件，因而可得命題公式：~pq2“只有不下雨，我才騎車上班”。~p是q的必要條件，因而可得命題公式：q

~p15第十五頁，共一百二十五頁。例子1“如果我進(jìn)城我就去看你，除非我很累”設(shè)：p,我進(jìn)城，q，去看你，r，我很累，則有命題公式：~r(pq)2”應(yīng)屆高中生，得過數(shù)學(xué)或物理競賽的一等獎(jiǎng)，保送上大學(xué)“設(shè)：p，應(yīng)屆高中生；q,保送上大學(xué)；r,得過數(shù)學(xué)競賽的一等獎(jiǎng)；t,得過物理競賽的一等獎(jiǎng)。則有命題公式：p∧(r∨t)q

16第十六頁，共一百二十五頁。命題邏輯的特點(diǎn)命題邏輯：使用陳述性、上下文無關(guān)、無歧義性、合成性的形式語言陳述性—使用符號描述(語句形式)顯式地表示知識(shí)(相對于過程性—將需要的知識(shí)直接編寫為程序代碼)上下文無關(guān)—其含義不因環(huán)境而改變無歧義性—含義唯一合成性—語句的含義是其各部分含義的一個(gè)函數(shù)(也是一種唯一性)第3章邏輯系統(tǒng)17第十七頁，共一百二十五頁。一階謂詞邏輯從命題到一階謂詞：命題內(nèi)部邏輯結(jié)構(gòu)的分解對判斷的分解，把判斷中的具體內(nèi)容抽出，稱為個(gè)體；剩下的判斷即為謂詞謂詞可看作是從個(gè)體域或個(gè)體域的笛卡兒乘積到真值集合{T/F}的映射典型的推理例子：(1)凡人皆有死；(2)蘇格拉底是人；(3)蘇格拉底有死。（三段論式）M(x)D(x),M(s)├D(s)第3章邏輯系統(tǒng)18第十八頁，共一百二十五頁。例子小王是個(gè)工程師8是個(gè)自然數(shù)我去買花小麗和小華是朋友其中，“小王”、“工程師”、“8”、“我”、“花”、“小麗”、“小華”都是個(gè)體，而“是個(gè)工程師”、“是個(gè)自然數(shù)”、“去買花”、“是朋友”都是謂詞。顯然前兩個(gè)謂詞表示的是事物的性質(zhì)，第三個(gè)謂詞表示的是一個(gè)動(dòng)作，也表示了主、賓兩個(gè)個(gè)體的關(guān)系，最后一個(gè)謂詞“是朋友”表示兩個(gè)個(gè)體之間的關(guān)系。19第十九頁，共一百二十五頁。論域與個(gè)體論域和個(gè)體：在一階邏輯中，被研究對象構(gòu)成的非空集稱為論域；論域中的每個(gè)元素稱為個(gè)體論域例子：前面例子中的論域是“人”/所有的有理數(shù)都是實(shí)數(shù)：其論域?yàn)橛欣頂?shù)一階邏輯還研究個(gè)體之間的關(guān)系（或個(gè)體的性質(zhì)）及作用于個(gè)體的函數(shù)論域/個(gè)體/個(gè)體間關(guān)系/作用于個(gè)體函數(shù)這4個(gè)成分構(gòu)成了一階邏輯的結(jié)構(gòu)第3章邏輯系統(tǒng)20第二十頁，共一百二十五頁。謂詞謂詞（關(guān)系）：一階形式語言中用于指稱論域中個(gè)體的性質(zhì)或者個(gè)體之間關(guān)系的形式符號（大寫字母表示）給定了論域，就確定了謂詞的真假值一元謂詞：個(gè)體的性質(zhì)；二元謂詞(多元謂詞)：個(gè)體的關(guān)系個(gè)體的位置—空位，具體化—構(gòu)成意義完整的語句空位的數(shù)目—謂詞的元數(shù)→幾元謂詞第3章邏輯系統(tǒng)21第二十一頁，共一百二十五頁。變量與量詞變量(變元)：表示論域內(nèi)的任意一個(gè)個(gè)體/常量(常元)，表示確定的個(gè)體量詞與變量：量詞用來表示謂詞的判斷特性全稱量詞：對所有的xxP(x)存在量詞：存在xxP(x)約束變量：、中x的變量，量詞所管轄的公式如P(x)稱為量詞轄域自由變量：不在量詞轄域內(nèi)的變量為自由變量第3章邏輯系統(tǒng)22第二十二頁，共一百二十五頁。約束變量和自由變量區(qū)別：自由變量可代入常量，約束變量不行，因?yàn)閍P(a)無意義；約束變量可改名，自由變量不行帶有全稱變量x的命題表示為一階公式時(shí)，其表示形式為x(P(x)→…)，帶有存在變量x的命題則表示形式為x(P(x)∧…)例子：所有有理數(shù)都是實(shí)數(shù)x(P(x)→R(x))，有些人身高超過2米x(M(x)∧G(x))上述使用方式不可改變，否則造成邏輯錯(cuò)誤第3章邏輯系統(tǒng)23第二十三頁，共一百二十五頁。函數(shù)函數(shù)：表示個(gè)體之間的運(yùn)算，可作用于一個(gè)或數(shù)個(gè)個(gè)體（用小寫字母）給定一個(gè)或若干個(gè)體（對象），產(chǎn)生一個(gè)新的個(gè)體（對象）/函數(shù)的元數(shù)例子：x的父親father(張三)兩數(shù)之和仍是一個(gè)數(shù)add(e1,e2)第3章邏輯系統(tǒng)24第二十四頁，共一百二十五頁。函數(shù)與謂詞的區(qū)別謂詞和函數(shù)的區(qū)別：謂詞代表語句，結(jié)果是關(guān)系（具有真假值）；函數(shù)代表關(guān)系運(yùn)算，結(jié)果是一個(gè)新個(gè)體例子：謂詞SUM(e1,e2,e3)說明e1、e2、e3之間的關(guān)系是e1與e2的和是e3，函數(shù)add(e1,e2)說明e1與e2相加的結(jié)果仍是一個(gè)數(shù)第3章邏輯系統(tǒng)25第二十五頁，共一百二十五頁。一階語言(1)一階語言L：是一階邏輯使用的形式語言，可以和任何結(jié)構(gòu)（論域）沒有聯(lián)系，也可以與某個(gè)結(jié)構(gòu)有聯(lián)系與結(jié)構(gòu)沒有聯(lián)系的一階語言由8類符號組成：(1)無限序列的個(gè)體符號（個(gè)體常量）(2)無限序列的謂詞符號，有確定的元數(shù)n≥1有一個(gè)特殊的謂詞符號稱為相等符號（等式），記為=。L可含或不含=，如果含有，即稱為含=的一階邏輯第3章邏輯系統(tǒng)26第二十六頁，共一百二十五頁。一階語言(2)(3)無限序列的函數(shù)符號，有確定的元數(shù)m≥1(4)無限序列的自由變量：用u/v/w等表示自由變量(5)無限序列的約束變量：用x/y/z等表示約束變量(6)聯(lián)結(jié)詞：￢∧∨→≡(7)量詞：、(8)標(biāo)點(diǎn)：左右括號、逗號(),一階邏輯：描述對象和關(guān)系的陳述性、合成性的形式語言第3章邏輯系統(tǒng)27第二十七頁，共一百二十五頁。一階語言的項(xiàng)和公式L的項(xiàng)：一階語言中的一個(gè)符號是項(xiàng)t，當(dāng)且僅當(dāng)它能通過有限次使用下述步驟生成：

(1)個(gè)體常量、自由變量是項(xiàng)； (2)如果t1…tn是項(xiàng)，且f是n元函數(shù)，則f(t1…tn)是項(xiàng)L的原子公式：一階語言中的一個(gè)表達(dá)式是一個(gè)原子公式，當(dāng)且僅當(dāng)它有如下2種形式：

(1)F(t1…tn)，F(xiàn)是n元謂詞，t1…tn是項(xiàng)； (2)=(t1,t2)或t1=t2，t1、t2是項(xiàng)第3章邏輯系統(tǒng)28第二十八頁，共一百二十五頁。一階語言的公式(1)L的公式：一階語言中的一個(gè)表達(dá)式是一個(gè)公式，當(dāng)且僅當(dāng)它能通過有限次使用下述步驟生成：(1)原子公式是公式；(2)如果A是公式，則(￢A)是公式；(3)如果A、B均為公式，則A*B是公式，其中*表示∧∨→≡中的任意一個(gè)(4)如果A(u)是公式，且x不在A(u)中出現(xiàn)，則xA(x)、xA(x)都是公式第3章邏輯系統(tǒng)29第二十九頁，共一百二十五頁。一階語言的公式(2)一階謂詞公式的例子數(shù)學(xué)命題的表示：5只被1和5整除設(shè)Q(x,y)表示x被y整除，N(x)表示x是自然數(shù)

x(Q(5,x)→N(5)∨N(1))自然語言語句的表示：他不能在所有時(shí)刻欺騙所有人設(shè)F(x)表示“x是人”/G(x)“x是一個(gè)時(shí)刻”/H(x,y)“他能在y時(shí)刻欺騙x” ?xy(F(x)∧G(y)→H(x,y))或者 xy(?H(x,y)∧F(x)∧G(y))

第3章邏輯系統(tǒng)30第三十頁，共一百二十五頁。一階語言的公式(3)一階謂詞公式的例子1所有人都是要死的2有的人活到一百歲以上在個(gè)體域D為人類集合時(shí)，可符號化為： 1xP(x),其中P(x)表示x是要死的 2xQ(x),其中Q(x)表示x活到一百歲以上在個(gè)體域D是全總個(gè)體域時(shí)，引入特殊謂詞R(x)表示x是人，可符號化為 1x（R(x)P(x)) 2x(R(x)∧Q(x))第3章邏輯系統(tǒng)31第三十一頁，共一百二十五頁。3.3邏輯推理舉例

wumpus世界

第3章邏輯系統(tǒng)32第三十二頁，共一百二十五頁。wumpus世界(1)Wumpus是一個(gè)早期電腦游戲中的怪物Agent感知：陷阱旁邊有微風(fēng)breeze怪獸旁邊有惡臭stench金子閃閃發(fā)光glitter感覺墻的反彈陷阱和怪物的位置隨機(jī)生成第3章邏輯系統(tǒng)stenchBreezePitWumpus(Monster)BreezeStenchGoldPitBreezestenchBreezeAgentBreezePitBreeze33第三十三頁，共一百二十五頁。wumpus世界(2)Wumpus世界搜索圖示—感知用5元組表示

[感知wumpus,感知微風(fēng),感知金光,感知墻,感知wumpus被殺死] A=Agent B=Breeze G=Glitter,Gold OK=safesquare P=Pit S=Stench V=visited W=wumpus N=None1,42,43,44,41,32,33,34,31,2OK2,23,24,21,1

AOK2,1OK3,14,1第3章邏輯系統(tǒng)1,42,43,44,41,32,33,34,31,2OK2,2P?3,24,21,1VOK2,1ABOK3,1P?4,1(a)[N,N,N,N,N] (b)[N,B,N,N,N]34第三十四頁，共一百二十五頁。wumpus世界(3)1,42,43,44,41,3W!2,33,34,31,2ASOK2,2OK3,24,21,1VOK2,1BVOK3,1P!4,1第3章邏輯系統(tǒng)1,42,4P？3,44,41,3W!2,3ABSG3,3P？4,31,2S

VOK2,2VOK3,24,21,1VOK2,1BVOK3,1P!4,1A=Agent B=Breeze G=Glitter,Gold OK=safesquareP=Pit S=Stench V=visited W=wumpus N=None(c)[S,N,N,N,N] (d)[S,B,G,N,N]35第三十五頁，共一百二十五頁。wumpus世界中的命題和推理規(guī)則一個(gè)簡單的知識(shí)庫：只考慮陷阱的情況Pi,j=T—[i,j]中有陷阱，記為Pi,jBi,j=T—[i,j]中有微風(fēng)，記為Bi,j規(guī)則如下：R1 P1,1R2 B1,1P1,2P2,1R3 B2,1P1,1P2,2P3,1R4 B1,1R5 B2,1第3章邏輯系統(tǒng)36第三十六頁，共一百二十五頁。命題邏輯的推理模式分離規(guī)則與消去邏輯等價(jià)(雙向蘊(yùn)涵消去)第3章邏輯系統(tǒng)37第三十七頁，共一百二十五頁。wumpus世界的推理例子用R1~R5規(guī)則和推理模式證明：[1,2]和[2,1]中沒有陷阱，即P1,2和P2,1證明：從R2開始R6 (B1,1(P1,2∨P2,1))∧((P1,2∨P2,1)B1,1) R2雙向蘊(yùn)涵消去R7 (P1,2∨P2,1)B1,1 R6與消去R8 ?B1,1?(P1,2∨P2,1) 逆否命題邏輯等價(jià)R9 ?(P1,2∨P2,1) R4/R8分離規(guī)則R10(結(jié)果) ?P1,2∧?P2,1 迪摩根定律第3章邏輯系統(tǒng)38第三十八頁，共一百二十五頁。3.4邏輯智能體的推理策略

邏輯智能體構(gòu)造

Horn子句

置換與合一

前向鏈接算法/后向鏈接算法第3章邏輯系統(tǒng)39第三十九頁，共一百二十五頁。邏輯智能體的構(gòu)造(1)以一階謂詞演算為核心的邏輯系統(tǒng)是典型的邏輯智能體系統(tǒng)的基礎(chǔ)是一階語言，由此構(gòu)造知識(shí)庫

一般構(gòu)造知識(shí)庫(知識(shí)工程)的過程包括：確定任務(wù)收集相關(guān)知識(shí)確定謂詞、函數(shù)和常量詞匯表第3章邏輯系統(tǒng)40第四十頁，共一百二十五頁。邏輯智能體的構(gòu)造(2)對領(lǐng)域(論域)的通用知識(shí)進(jìn)行編碼對特定問題實(shí)例的描述進(jìn)行編碼查詢提交、推理、給出答案調(diào)試知識(shí)庫如果采用一階語言的特殊形式—確定子句Horn子句，可獲得高效推理第3章邏輯系統(tǒng)41第四十一頁，共一百二十五頁。Horn子句Horn子句(HornClause)：是一類至多只有一個(gè)正文字的子句(子句=文字的析取式)例子:?A∨?B∨C(注意：這是一般公式AB→C的變形)Horn子句稱為確定子句,其中正文字稱為子句的頭,負(fù)文字構(gòu)成子句的體第3章邏輯系統(tǒng)42第四十二頁，共一百二十五頁。Horn子句的性質(zhì)只有一個(gè)正文字的約束具有重要意義:每個(gè)Horn子句實(shí)際上都是一個(gè)蘊(yùn)涵式的變形,實(shí)際知識(shí)庫中常常使用這樣易懂的形式

Horn子句的推理可以使用前向鏈接和后向鏈接算法用Horn子句判定蘊(yùn)涵所需時(shí)間與數(shù)據(jù)庫成線性關(guān)系最重要的是最后一個(gè)性質(zhì)第3章邏輯系統(tǒng)43第四十三頁，共一百二十五頁。推理策略簡要介紹2種推理算法—簡單的前向鏈接算法和簡單的后向鏈接算法,結(jié)合一個(gè)例子說明算法的應(yīng)用一階推理規(guī)則—一般化分離規(guī)則(GeneralizedModusPonens)對于原子語句pi,pi’,q,存在置換,使得(pi)=(pi’),對所有i都成立,則第3章邏輯系統(tǒng)44第四十四頁，共一百二十五頁。置換與合一置換(或代換)：設(shè)x1～xn是n個(gè)變量，且各不相同，t1～tn是n個(gè)項(xiàng)(常量、變量、函數(shù))，ti≠xi，則有限序列{t1/x1,t2/x2…tn/xn}稱為一個(gè)置換置換乘積(合成)：設(shè)和是2個(gè)置換，則先后作用于公式或項(xiàng)，稱為置換乘積，用表示。通過相關(guān)的置換,使不同的一階公式成為一樣的，這個(gè)過程稱為合一第3章邏輯系統(tǒng)45第四十五頁，共一百二十五頁。合一置換合一置換：設(shè)有一組謂詞公式{E1～Ek}和置換，使E1=E2=…=Ek,則稱為合一置換，E1～Ek稱為可合一的/合一置換也叫通代最一般合一置換(最廣通代)：如果和都是公式組{E1～Ek}的合一置換，且有置換存在，使得=，則稱為公式組{E1～Ek}的最一般合一置換，記為mgu(mostgeneralunification)第3章邏輯系統(tǒng)46第四十六頁，共一百二十五頁。置換與合一的例子有子句xKing(x)∧Greedy(x)→Evil(x)King(John)Greedy(John)則做置換={x/John},用一般化分離規(guī)則可得:q=Evil(John)第3章邏輯系統(tǒng)47第四十七頁，共一百二十五頁。合一結(jié)果對于合一UNIFY,合一的結(jié)果是一個(gè)置換,如:UNIFY(Know(John,x),Know(John,Jane))={x/Jane}UNIFY(Know(John,x),Know(y,Mary))={x/Mary,y/John}但是UNIFY(K(John,x),K(x,Jane))=FAIL,原因是x不能同時(shí)選取2個(gè)值詳細(xì)的合一算法將在第4章介紹第3章邏輯系統(tǒng)48第四十八頁，共一百二十五頁。用于邏輯推理的例子問題描述:美國法律規(guī)定：美國人(American)賣武器(weapon)給敵對國家(hostile)是犯罪的(criminal).美國的敵國Nono有一些導(dǎo)彈(missile)，所有這些導(dǎo)彈是West上校賣給他們的，而West上校是一個(gè)美國人證明：West是犯罪的第3章邏輯系統(tǒng)49第四十九頁，共一百二十五頁。問題用一階子句表示(1)用確定子句表示上述內(nèi)容美國人賣武器給敵對國家是犯罪的American(x)∧Weapon(y)∧Sell(x,y,z)∧Hostile(z)→Criminal(x) [1]Nono有一些導(dǎo)彈xOwn(Nono,x)∧Missile(x) 消去其中的存在量詞，引入新常量，得到2個(gè)原子公式(正文字)Own(Nono,M1) [4]Missile(M1) [5]第3章邏輯系統(tǒng)50第五十頁，共一百二十五頁。問題用一階子句表示(2)所有該國導(dǎo)彈都是West上校出售的Missile(y)∧Own(Nono,y)→Sell(West,y,Nono)[2]導(dǎo)彈是武器Missile(y)→Weapon(y) [3]其它陳述：美國人West American(West) [6]敵國Nono Hostile(Nono) [7]上述描述放入知識(shí)庫：[1]~[3]為確定子句(上述原始形式均可以化為原子的析取且只有一個(gè)正文字)，[4]~[7]為正文字第3章邏輯系統(tǒng)51第五十一頁，共一百二十五頁。前向鏈接算法的說明(1)前向鏈接算法的推理過程：從已知事實(shí)(知識(shí)庫中的原子公式)開始，依次對知識(shí)庫中的規(guī)則(以確定子句的形式出現(xiàn))進(jìn)行置換，檢查規(guī)則前提部分的文字是否全部與知識(shí)庫中的事實(shí)相匹配如果是匹配的，則把該條規(guī)則已經(jīng)做過置換的結(jié)論部分添加到知識(shí)庫中，如果這個(gè)結(jié)論和查詢(既需要推導(dǎo)出的結(jié)論)一致，則推理結(jié)束，獲得證明第3章邏輯系統(tǒng)52第五十二頁，共一百二十五頁。前向鏈接算法的說明(2)重復(fù)上述過程，直到獲得證明；或者再?zèng)]有新的事實(shí)(推出的結(jié)論)加入，則此時(shí)推理以證明失敗結(jié)束約束：要求每次加入知識(shí)庫的結(jié)論都是全新的，而不是已知事實(shí)的重命名(即謂詞相同只是變量名不同)第3章邏輯系統(tǒng)53第五十三頁，共一百二十五頁。簡單的前向鏈接算法FunctionFC(KB,α)ReturnasubstitutionorFALSE Inputs:KB,asetoffirst-orderdefiniteclauses/,thequery=anatom localvariables:new,thenewrulesinferredoneachiteration repeatuntilnewisempty

new←{} foreachruler(intheformofdefineclause)inKBdo

foreachsuchthat(p1∧…∧pn)=(p1’∧…∧pn’) get(q)=q’ ifq’isnew(satisfiedtheconstraint) thendoaddq’tonew ←UNIFY(q’,)

Ifisnotfailthenreturn addnewtoKB returnfalse第3章邏輯系統(tǒng)54第五十四頁，共一百二十五頁。前向鏈接算法例子(1)第3章邏輯系統(tǒng)使用前向鏈接算法對前面的例子進(jìn)行推理用知識(shí)庫中的事實(shí)(即[4]~[7])依次對知識(shí)庫中的各個(gè)子句進(jìn)行置換操作并用推理規(guī)則獲得新的文字第一次循環(huán)體執(zhí)行：子句[1]前提部分未獲滿足(為什么？)子句[2]—使用置換{x/M1},則可得 Sell(West,M1,Nono) [8]子句[3]—使用置換{x/M1}，則可得Weapon(M1) [9]American(x)∧Weapon(y)∧Sell(x,y,z)∧Hostile(z)→Criminal(x)[1]Missile(y)∧Own(Nono,y)→Sell(West,y,Nono)[2]Missile(y)→Weapon(y) [3]Own(Nono,M1) [4]Missile(M1)[5]American(West) [6]Hostile(Nono) [7]55第五十五頁，共一百二十五頁。前向鏈接算法例子(2)第3章邏輯系統(tǒng)此時(shí)new中為[8][9]，為原知識(shí)庫所未有，將它們添加到知識(shí)庫中第二次循環(huán)體執(zhí)行：再次循環(huán)時(shí)new首先清空子句[1]—置換{x/West,y/M1,z/Nono} 得到Criminal(West) [10]添加到new中，與查詢進(jìn)行合一測試，一致則返回/算法結(jié)束56第五十六頁，共一百二十五頁。前向鏈接生成的證明樹第3章邏輯系統(tǒng)Criminal(West)Weapon(M1)Sells(West,M1,Nono)Hostile(Nono)American(West)Missile(M1)Owns(Nono,M1)Enemy(Nono,America)57第五十七頁，共一百二十五頁。反向鏈接算法的說明(1)算法的推理過程是：選取棧當(dāng)中的第一個(gè)目標(biāo)，在知識(shí)庫中尋找子句的頭(即結(jié)論部分)能與目標(biāo)合一的每個(gè)子句每個(gè)這樣的子句創(chuàng)建了一個(gè)遞歸調(diào)用過程，在這個(gè)遞歸調(diào)用過程中子句的前提(子句的體)被加入到目標(biāo)棧當(dāng)中當(dāng)棧中所有目標(biāo)都得到匹配，則當(dāng)前的證明分支是成功的注意：事實(shí)是指有頭沒有體的子句(正文字)第3章邏輯系統(tǒng)58第五十八頁，共一百二十五頁。反向鏈接算法的說明(2)原始查詢(既要證明的結(jié)論)以目標(biāo)列表的形式出現(xiàn)，開始時(shí)列表中只有一個(gè)元素列表的操作相當(dāng)于棧，是一個(gè)遞歸過程(如下)即深度優(yōu)先的搜索過程推理過程是從結(jié)論(子句的頭)開始，找到匹配的頭就擴(kuò)展這個(gè)頭所在的規(guī)則體；擴(kuò)展部分又作為頭繼續(xù)擴(kuò)展，直到全部原子均與事實(shí)相匹配比較：正向=事實(shí)結(jié)論/反向=結(jié)論事實(shí)第3章邏輯系統(tǒng)59第五十九頁，共一百二十五頁。簡單的反向鏈接算法FunctionBC(KB,goals,)returnsasetofsubstitutions

Inputs:KB,goals=alistofconjunctsformingaquery(alreadyapplied),=thecurrentsubstitution(initial={})

localvariables:answers=asetofsubstitutions(initial={})

ifgoalsisemptythenreturn{} q’=(FIRST(goals)) (初始為空，遞歸以后不空) foreachruler(intheformofdefineclause)inKBand ’=UNIFY(q,q’)succeeds new_goal={p1’,…,pn’}asREST(goals) answers=BC(KB,new_goal,’))∪answers returnanswers第3章邏輯系統(tǒng)60第六十頁，共一百二十五頁。反向鏈接算法的說明(3)在算法中answers作為存放置換的數(shù)據(jù)結(jié)構(gòu)，返回一系列置換操作，這些操作說明了反向鏈接算法獲取證明的過程在算法中包括了置換的合成’(或者寫為Compose(’,))，其效果就是依次進(jìn)行每個(gè)置換第3章邏輯系統(tǒng)61第六十一頁，共一百二十五頁。反向鏈接算法的說明(4)第一次應(yīng)用算法，對于待證明的目標(biāo)來說，本身就是一個(gè)正文字，此時(shí)要用這個(gè)文字中的常量對合適的規(guī)則(子句的頭與該文字匹配)進(jìn)行置換這個(gè)置換通過遞歸調(diào)用帶入下一次置換，就得到了合成置換在本例中有：初始{x/West} 遞歸{x/West,y/M1} 遞歸{x/West,y/M1,z/Nono}第3章邏輯系統(tǒng)62第六十二頁，共一百二十五頁。反向鏈接算法例子(1)反向鏈接算法推理過程目標(biāo)Criminal(West)分解為公式[1]前提部分的4個(gè)文字，即American(West),Weapon(y),Sell(West,y,z),Hostile(z)—置換={x/West}American(West)和事實(shí)相匹配需要遞歸匹配：Weapon(y),Sell(West,y,z),Hostile(z)Weapon(y)遞歸調(diào)用前={x/West}，進(jìn)入第一次遞歸產(chǎn)生Missile(M1)，此時(shí)置換{y/M1}匹配，遞歸返回復(fù)合={x/West,y/M1}第3章邏輯系統(tǒng)63第六十三頁，共一百二十五頁。反向鏈接算法例子(2)再次遞歸調(diào)用Sell(West,M1,z)—得到置換={z/Nono}，遞歸返回復(fù)合置換{x/West,y/M1,z/Nono}在置換過程中每個(gè)變量只能置換一個(gè)常量作為約束，減少置換的不定性此時(shí)子目標(biāo)全部匹配，再無新的子目標(biāo)生成，返回置換集合結(jié)束第3章邏輯系統(tǒng)64第六十四頁，共一百二十五頁。反向鏈接生成的證明樹第3章邏輯系統(tǒng)Criminal(West)American(West)Weapon(y)Sells(West,M1,z)Hostile(Nono)Missile(y)Missile(M1)Owns(Nono,M1)Enemy(Nono,Amerca){}z/Nono{}{}{}{y/M1}65第六十五頁，共一百二十五頁。正向鏈接和反向鏈接前向鏈接算法特點(diǎn)：數(shù)據(jù)驅(qū)動(dòng)/是可靠的和完備的后向鏈接算法特點(diǎn)：目標(biāo)驅(qū)動(dòng)/是可靠的但不是完備的(書中p220/p224)可以從“是否能找到問題的解”角度考慮不完備性后向鏈接算法根據(jù)目標(biāo)來進(jìn)行相關(guān)事實(shí)的匹配，對于大規(guī)模的知識(shí)庫來說有助于減小搜索空間第3章邏輯系統(tǒng)66第六十六頁，共一百二十五頁。3.2邏輯系統(tǒng)的語法和語義

邏輯系統(tǒng)的語法

邏輯系統(tǒng)的語義

語法和語義之間的關(guān)系第3章邏輯系統(tǒng)67第六十七頁，共一百二十五頁。邏輯系統(tǒng)邏輯系統(tǒng)(亦稱形式系統(tǒng)FormalSystem)由5個(gè)部分組成：符號表—非空集合，即邏輯(形式)語言—如一階語言項(xiàng)和變量—

上全體符號的集合*的子集公式FORMULA—*的子集|公式和項(xiàng)的交集為空公理AXIOM—公式FORMULA上的子集推理規(guī)則RULE—公式上的n元關(guān)系集合、項(xiàng)TERM、FORMULA稱為FS的組成部分/AXIOM、RULE稱為FS的推演部分第3章邏輯系統(tǒng)68第六十八頁，共一百二十五頁。語法和形式推演邏輯系統(tǒng)除符號表以外的部分構(gòu)成了邏輯系統(tǒng)的語法形式推演：定義了公式之間的形式可推演性關(guān)系，它涉及公式的語法結(jié)構(gòu)，其正確性能夠機(jī)械地證明用記號├表示形式可推演關(guān)系，讀作“推出”用├A表示A是由形式可推演的（或形式可證明的），其中是前提，A是結(jié)論第3章邏輯系統(tǒng)69第六十九頁，共一百二十五頁。命題邏輯的語義與可滿足性研究命題邏輯的語義，即研究公式(公式集)的真假賦值問題真假賦值：真假賦值是以所有命題符號的集合為定義域、以真假值{1,0}為值域的函數(shù)。真假賦值v給公式A指派的值記作Av可滿足性：是可滿足的，當(dāng)且僅當(dāng)有真假賦值v，使得v=1。此時(shí)稱v滿足。第3章邏輯系統(tǒng)70第七十頁，共一百二十五頁?？蓾M足性的可滿足性蘊(yùn)涵了中所有公式的可滿足性，但反過來不成立。因?yàn)檫@要求同一個(gè)真假賦值滿足所有的公式(并非所有可滿足的公式使用同一個(gè)賦值)重言式和矛盾式A是重言式(永真式)，當(dāng)且僅當(dāng)對于任意的真假賦值v，Av=1A是矛盾式(永假式)，當(dāng)且僅當(dāng)對于任意的真假賦值v，Av=0第3章邏輯系統(tǒng)71第七十一頁，共一百二十五頁。邏輯推論可推導(dǎo)關(guān)系：研究前提的真是否蘊(yùn)涵結(jié)論的真引入語義以后對公式進(jìn)行真假賦值；如果對任意的真假賦值，都有上述關(guān)系，則說明前提和結(jié)論之間存在一種邏輯推論關(guān)系(或稱邏輯蘊(yùn)涵)第3章邏輯系統(tǒng)72第七十二頁，共一百二十五頁。命題邏輯的邏輯推論邏輯推論：設(shè)、A分別是命題邏輯中的公式集合和公式,A是的邏輯推論，記為|=A，當(dāng)且僅當(dāng)對于任意真假賦值v，v=1蘊(yùn)涵Av=1。|=可讀作“邏輯地蘊(yùn)涵”，|=是前提和結(jié)論A之間的關(guān)系邏輯推論的證明要證明|=A時(shí)，即要證明對于任何真假賦值v，如果v=1則Av=1(通常使用反證法)第3章邏輯系統(tǒng)73第七十三頁，共一百二十五頁。一階語言的語義一階語言的語義：一階語言的解釋包括一個(gè)論域和一個(gè)函數(shù)函數(shù)把一階語言中的個(gè)體符號映射到論域中的個(gè)體n元關(guān)系符號(即謂詞)映射到論域上的n元關(guān)系m元函數(shù)符號映射到論域上的m元全函數(shù)以上組成了該論域中對一階語言的解釋第3章邏輯系統(tǒng)74第七十四頁，共一百二十五頁。一階語言的賦值賦值：一階語言L的賦值v包括一個(gè)論域D和一個(gè)函數(shù)(記作v)L中所有個(gè)體符號a為定義域，其賦值v(a)或av

關(guān)系符號F的賦值v(F)或Fv

函數(shù)符號f的賦值v(f)或fv自由變量符號u的賦值v(u)或uv則有 (1)av,uv∈D (2)FvDn (3)fv:Dm→D第3章邏輯系統(tǒng)75第七十五頁，共一百二十五頁。一階邏輯的邏輯推論公式的真假值：一階語言的公式在以D為論域的賦值之下，其真假值可以遞歸定義一階邏輯的邏輯推論：設(shè)、A分別是一階語言的公式集和公式，A是的邏輯推論，記作|=A，當(dāng)且僅當(dāng)對于任何賦值v，v=1蘊(yùn)涵Av=1一階邏輯的邏輯推論證明方法類似于命題邏輯，常用反證法。但對于否證邏輯推論，則需要構(gòu)造賦值所需的論域。確定論域時(shí)，關(guān)鍵在于論域的大小第3章邏輯系統(tǒng)76第七十六頁，共一百二十五頁。邏輯系統(tǒng)的整體特征在經(jīng)典邏輯的形式系統(tǒng)中，形式推演是語法概念，邏輯推論是語義概念形式系統(tǒng)的整體特征：是在形式系統(tǒng)引入語義以后，研究對于任何一階語言的公式集和公式A在何種賦值的條件下，其結(jié)果是否為真—即研究形式推演與邏輯推論之間的關(guān)系即語法和語義之間的關(guān)系賦值的條件：給定某個(gè)賦值—可滿足性給定任意賦值—有效性第3章邏輯系統(tǒng)77第七十七頁，共一百二十五頁。可滿足性與有效性(1)不加證明地給出有關(guān)定義和定理可滿足性—一階邏輯公式集合是可滿足的，當(dāng)且僅當(dāng)有(以某個(gè)不空集為論域)賦值v，使得v=1/當(dāng)v=1時(shí)，稱v滿足反過來，不可滿足性就是對任意論域上的任意賦值都有v=0第3章邏輯系統(tǒng)78第七十八頁，共一百二十五頁。可滿足性與有效性(2)有效性：一階邏輯公式A是有效的，當(dāng)且僅當(dāng)對于(以任何不空集為論域)任何賦值v，Av=1/有效性也稱為普遍有效性/教科書中稱為合法性第3章邏輯系統(tǒng)79第七十九頁，共一百二十五頁。可滿足性與有效性(3)(關(guān)于命題的)定理:(1)A是可滿足的，當(dāng)且僅當(dāng)?A是不有效的；(2)A是有效的，當(dāng)且僅當(dāng)?A是不可滿足的。(關(guān)于一階的)定理:(1)A(u1,…,un)是可滿足的，當(dāng)且僅當(dāng)x1...xnA(x1,…,xn)是可滿足的(2)A(u1,…,un)是有效的，當(dāng)且僅當(dāng)x1...xnA(x1,…,xn)是有效的第3章邏輯系統(tǒng)80第八十頁，共一百二十五頁?？煽啃远ɡ砼c完備性定理對于任何一階語言的公式集和公式A，├A|=A表示：凡是形式可推演性所反映的前提和結(jié)論之間的關(guān)系，在非形式的推理中都是成立的，即形式可推演性對于反映非形式的推理是可靠的，此即可靠性定理(或者稱合理性)|=A├

A表示：凡是在非形式推理中成立的前提和結(jié)論之間的關(guān)系，形式可推演性都是能夠反映的，即形式可推演性在反映非形式推理時(shí)沒有遺漏，此即完備性定理第3章邏輯系統(tǒng)81第八十一頁，共一百二十五頁。作業(yè)1掃雷游戲，和wumpus世界有著密切的聯(lián)系，N個(gè)方格的矩形網(wǎng)絡(luò)，M個(gè)隨機(jī)分布的地雷。通過在每個(gè)已經(jīng)探尋過的方格內(nèi)顯示直接以及對交相鄰的地雷數(shù)量來指示地雷的存在，目標(biāo)是探尋每個(gè)沒有地雷的方格。（1）Xi,j為真當(dāng)且僅當(dāng)方格[i,j]中包含地雷，用一個(gè)包括Xi,j命題的一些邏輯組合的語句表示[i,j]周圍恰好有1顆地雷的斷言。（2）如何構(gòu)造一個(gè)合取范式語句，并根據(jù)（1）把你的斷言推廣為：n個(gè)相鄰的方格中有k個(gè)方格包含地雷。82第八十二頁，共一百二十五頁。參考書目StuartRussell/PeterNorvig:AIMA第7章/第8章/第9章陸汝鈐編著:人工智能(上冊)第1章陸鐘萬，面向計(jì)算機(jī)科學(xué)的數(shù)理邏輯，科學(xué)出版社，1998年1月第1版朱梧[木賈]、肖奚安，數(shù)理邏輯引論，南京大學(xué)出版社，1995年5月第1版王元元，計(jì)算機(jī)科學(xué)中的邏輯學(xué)，科學(xué)出版社，1989年9月第1版第3章邏輯系統(tǒng)83第八十三頁，共一百二十五頁。附錄形式系統(tǒng)簡介

F1形式系統(tǒng)和形式推演

F2形式系統(tǒng)的語義

F3形式系統(tǒng)的整體特征第3章邏輯系統(tǒng)84第八十四頁，共一百二十五頁。F1形式系統(tǒng)定義和形式推演第3章邏輯系統(tǒng)85第八十五頁，共一百二十五頁。形式系統(tǒng)定義(1)邏輯的形式系統(tǒng)的定義–一個(gè)形式系統(tǒng)FormalSystem由5個(gè)部分組成：(1)符號表，非空集合，即形式語言(如Lp和L)；(2)上全體符號的集合*的一個(gè)子集TERM，其元素稱為FS的項(xiàng)；TERM有子集VARIABLE，其元素稱為變量；(3)*的一個(gè)子集FORMULA，其元素稱為FS的公式；FORMULA有子集ATOM，其元素稱為原子公式；TERMFORMULA=；第3章邏輯系統(tǒng)86第八十六頁，共一百二十五頁。形式系統(tǒng)定義(2)(4)FORMULA的一個(gè)子集AXIOM，其元素稱為FS的公理；(5)FORMULA上的n元關(guān)系集合RULE，其元素稱為FS的推理規(guī)則。其中、TERM、FORMULA稱為FS的組成部分，AXIOM、RULE稱為FS的推演部分公理推演系統(tǒng)包括AXIOM，而自然推演系統(tǒng)只包括推理規(guī)則第3章邏輯系統(tǒng)87第八十七頁，共一百二十五頁。對象語言和元語言(1)對象語言和元語言：作為被研究對象的語言稱為對象語言，用以研究對象語言的語言稱為元語言例子：用漢語研究英語語法，則英語是對象語言，漢語是元語言數(shù)理邏輯中的形式系統(tǒng)各有其自身的形式語言如Lp和L，這些是被研究的對象，因而是對象語言；但為了研究這些形式系統(tǒng)，又必須使用某種語言，那么這種語言便是元語言第3章邏輯系統(tǒng)88第八十八頁，共一百二十五頁。對象語言和元語言(2)如：“鳥正在飛翔”—描述—對象語言；“命題‘鳥正在飛翔’真”—對上句的評論—元語言。形式系統(tǒng)的對象語言，其中的符號既是對客觀對象的抽象，用于研究客觀對象;同時(shí)又是一種符號客體，是被研究的對象第3章邏輯系統(tǒng)89第八十九頁，共一百二十五頁。對象語言和元語言(3)形式系統(tǒng)的元語言包括：對形式系統(tǒng)中組成成分的稱謂—項(xiàng)、公式、公理等邏輯術(shù)語—如果-那么、當(dāng)且僅當(dāng)、存在、所有等對形式系統(tǒng)性質(zhì)（整體特征）的描述—如一致性、完備性、可判定性等，該部分最重要元語言中使用的符號：自然語言（如漢語）和一些被引進(jìn)的符號，如：├、|=等未經(jīng)解釋的形式語言可以沒有含義，但元語言必須有其具體含義。第3章邏輯系統(tǒng)90第九十頁，共一百二十五頁。元理論元理論是關(guān)于形式系統(tǒng)的理論，包括三部分內(nèi)容：關(guān)于形式系統(tǒng)語法(syntax)的研究，不涉及具體意義的符號體系，研究符號串的推演，即形式推演；關(guān)于形式系統(tǒng)語義(semantics)的研究，研究形式系統(tǒng)在被作出各種解釋時(shí)的性質(zhì)；關(guān)于形式系統(tǒng)語法和語義關(guān)系的研究，特別是形式系統(tǒng)的性質(zhì)，如：合理性、完備性等。第3章邏輯系統(tǒng)91第九十一頁，共一百二十五頁。形式推演形式推演：定義了公式之間的形式可推演性關(guān)系，它涉及公式的語法結(jié)構(gòu)，其正確性能夠機(jī)械地證明用記號├表示形式可推演關(guān)系，讀作“推出”用├A表示A是由形式可推演的（或形式可證明的），其中是前提，A是結(jié)論記號├不是形式語言中的符號，├A也不是形式語言中的公式，而是元語言中的命題第3章邏輯系統(tǒng)92第九十二頁，共一百二十五頁。常用推演規(guī)則(1)形式推演由形式推演的規(guī)則定義命題邏輯中有一些常用的推演規(guī)則(規(guī)則模式)肯定前提 ifA∈then├A (∈)增加前提 if├Athen,‘├A(+)自反 A├A (Ref)傳遞 if├‘├Athen├A()第3章邏輯系統(tǒng)93第九十三頁，共一百二十五頁。常用推演規(guī)則(2)￢消去(反證律) if,￢A├B&,￢A├￢B then├A (￢-)￢引入(歸謬律) if,A├B&,A├￢B then├￢A (￢+)→消去 if├A→B,├A then├B (→-)→引入if,A├B then├A→B (→+)第3章邏輯系統(tǒng)94第九十四頁，共一百二十五頁。常用推演規(guī)則(3)∧消去if├A∧Bthen├A,├B (∧-)∧引入 if├A,├Bthen├A∧B (∧+)∨消去if,A├C&,B├Cthen,A∨B├C(∨-)∨引入if├A

then├A∨B,├B∨A (∨+)第3章邏輯系統(tǒng)95第九十五頁，共一百二十五頁。常用推演規(guī)則(2)≡消去if├A≡B,├Athen├Bif├A≡B,├Bthen├A (≡－)≡引入if,A├B&,B├A then├A≡B (≡+)通過連接詞的增減或變形，實(shí)現(xiàn)公式的變換常用A→BAB第3章邏輯系統(tǒng)96第九十六頁，共一百二十五頁。形式可推演性(1)(命題邏輯)形式可推演性：在命題邏輯中，A是由可形式推演的(或形式可證明的)，記為├A，當(dāng)且僅當(dāng)├A能通過有限次應(yīng)用命題邏輯的形式推演規(guī)則生成即├A成立，當(dāng)且僅當(dāng)存在有限序列使得1├A1，2├A2，…，n├An

中的每一項(xiàng)均由某個(gè)形式推導(dǎo)規(guī)則生成,且n├An

就是├A即n=,An=A第3章邏輯系統(tǒng)97第九十七頁，共一百二十五頁。形式可推演性(2)用

A表示├A不成立用A|-|B表示左右兩邊的公式可以互相推出，稱其為語法等值公式或等值公式建立在上述形式推演規(guī)則基礎(chǔ)上的形式推演系統(tǒng)稱為自然推演(演繹)系統(tǒng)第3章邏輯系統(tǒng)98第九十八頁，共一百二十五頁。形式可推演性(3)命題邏輯中的形式推演規(guī)則都包括在一階邏輯當(dāng)中，但是其中出現(xiàn)的公式是一階語言中的公式，另外增加了關(guān)于量詞的規(guī)則(一階邏輯)形式可推演性：在一階邏輯中，A是由可形式推演的(或形式可證明的)，記為├A，當(dāng)且僅當(dāng)├A能通過有限次應(yīng)用一階邏輯的形式推演規(guī)則生成形式推演的例子可以參考本章后面列出的3本關(guān)于邏輯的教科書第3章邏輯系統(tǒng)99第九十九頁，共一百二十五頁。F2形式系統(tǒng)的語義第3章邏輯系統(tǒng)100第一百頁，共一百二十五頁。形式系統(tǒng)的語義(1)語義即對形式語言進(jìn)行解釋研究可推導(dǎo)性即形式推演(├)時(shí)不考慮作為前提和結(jié)論的命題的內(nèi)容，只考慮命題真假并由此確定前提的真是否蘊(yùn)涵結(jié)論的真，即前提和結(jié)論之間是否有可推導(dǎo)關(guān)系(語法)研究形式系統(tǒng)的語義時(shí)，對形式系統(tǒng)賦予研究對象的集合即論域；用論域中的個(gè)體對象、對象之上的運(yùn)算(函數(shù))、對象之間的關(guān)系(謂詞)去解釋形式系統(tǒng)中的符號，稱作指稱denote指稱語義學(xué)第3章邏輯系統(tǒng)101第一百零一頁，共一百二十五頁。形式系統(tǒng)的語義(2)賦予形式系統(tǒng)的論域及解釋稱為形式系統(tǒng)的語義結(jié)構(gòu)，簡稱結(jié)構(gòu)(structure)/結(jié)構(gòu)及其在該結(jié)構(gòu)下公式所取真值的規(guī)定，稱為形式系統(tǒng)的指稱語義(denotationalsemantics)第3章邏輯系統(tǒng)102第一百零二頁，共一百二十五頁。命題邏輯的可滿足性研究命題邏輯的語義，即研究公式(公式集)的真假賦值問題真假賦值：真假賦值是以所有命題符號的集合為定義域，以真假值{1,0}為值域的函數(shù)。真假賦值v給公式A指派的值記作Av可滿足性：是可滿足的，當(dāng)且僅當(dāng)有真假賦值v，使得v=1。此時(shí)稱v滿足。第3章邏輯系統(tǒng)103第一百零三頁，共一百二十五頁。可滿足性的可滿足性蘊(yùn)涵了中所有公式的可滿足性，但反過來不成立。因?yàn)檫@要求同一個(gè)真假賦值滿足所有的公式(并非所有可滿足的公式使用同一個(gè)賦值)重言式和矛盾式A是重言式(永真式)，當(dāng)且僅當(dāng)對于任意的真假賦值v，Av=1A是矛盾式(永假式)，當(dāng)且僅當(dāng)對于任意的真假賦值v，Av=0第3章邏輯系統(tǒng)104第一百零四頁，共一百二十五頁。真假判斷與邏輯推論一個(gè)命題公式是重言式或者是矛盾式或者兩者都不是，需要進(jìn)行判定。判定方法可通過構(gòu)造真假值表方法或采用樹形分支的方法來判定可推導(dǎo)關(guān)系研究前提的真是否蘊(yùn)涵結(jié)論的真，引入語義以后對公式進(jìn)行真假賦值；如果對任意的真假賦值，都有上述關(guān)系，則說明前提和結(jié)論之間存在一種邏輯推論關(guān)系(或稱邏輯蘊(yùn)涵)。此時(shí)對關(guān)系陳述得也更精確第3章邏輯系統(tǒng)105第一百零五頁，共一百二十五頁。命題邏輯的邏輯推論邏輯推論：設(shè)、A分別是命題邏輯中的公式集合和公式,A是的邏輯推論，記為A，當(dāng)且僅當(dāng)對于任意真假賦值v，v=1蘊(yùn)涵Av=1。|=可讀作“邏輯地蘊(yùn)涵”，|=是前提和結(jié)論A之間的關(guān)系,但不是命題語言中的符號，|=A是元語言中的命題第3章邏輯系統(tǒng)106第一百零六頁，共一百二十五頁。邏輯推論的證明邏輯推論的證明要證明|=A時(shí)，即要證明對于任何真假賦值v，如果v=1則Av=1但任意的真假賦值難于驗(yàn)證故使用反證法，假設(shè)|≠A，即存在一個(gè)真假賦值v，使得v=1且Av=0，由此而產(chǎn)生矛盾，即肯定了|=A第3章邏輯系統(tǒng)107第一百零七頁，共一百二十五頁。一階語言的語義(1)一階語言的語義：一階語言的解釋包括一個(gè)論域和一個(gè)函數(shù)，函數(shù)把一階語言中的個(gè)體符號、n元關(guān)系符號(即謂詞)、m元函數(shù)符號分別映射到論域中的個(gè)體、論域上的n元關(guān)系和m元全函數(shù)，是在這個(gè)論域中對一階語言的解釋第3章邏輯系統(tǒng)108第一百零八頁，共一百二十五頁。一階語言的語義(2)如果n元關(guān)系符號和m元函數(shù)中不含自由變量，其項(xiàng)為論域中的個(gè)體ai，則原子公式F(t1,…,tn)被解釋為：a1,…,an有R關(guān)系；項(xiàng)f(t1,…,tn)被解釋為論域中的個(gè)體f(a1,…,an)對于含有自由變量的函數(shù)(項(xiàng))和公式，則分別被解釋為論域上的m元函數(shù)和n元命題函數(shù)，它們經(jīng)過解釋，再給其中的自由變量符號指派論域中的某些個(gè)體，就得到論域中個(gè)體作為其值、真或假的命題作為其真假值第3章邏輯系統(tǒng)109第一百零九頁，共一百二十五頁。一階語言的賦值(1)賦值：一階語言L的賦值v包括一個(gè)論域和一個(gè)函數(shù)，記作v，以L中所有個(gè)體符號a、關(guān)系符號F、函數(shù)符號f和自由變量符號u構(gòu)成的集合為定義域，且分別把v(a)、v(F)、v(f)、v(u)寫作av、Fv、fv、uv，則有 (1)av,uv∈D (2)FvDn (3)fv:Dm→D第3章邏輯系統(tǒng)110第一百一十頁，共一百二十五頁。一階語言的賦值(2)項(xiàng)的值：在以D為論域的賦值v之下的項(xiàng)的值遞歸定義如下：

(1)av,uv∈D (2)f(t1,…,tn)v=fv(t1v,…,tnv)對于一階語言的項(xiàng)t，設(shè)v是以D為論域的賦值，則tv∈D第3章邏輯系統(tǒng)111第一百一十一頁，共一百二十五頁。一階邏輯的邏輯推論公式的真假值：一階語言的公式在以D為論域的賦值之下，其真假值可以遞歸定義一階邏輯的邏輯推論:與命題邏輯相同，只是這里不使用真假賦值，而用賦值邏輯推論：設(shè)、A分別是一階語言的公式集和公式，A是的邏輯推論，記作|=A，當(dāng)且僅當(dāng)對于任何賦值v，v=1蘊(yùn)涵Av=1第3章邏輯系統(tǒng)112第一百一十二頁，共一百二十五頁。邏輯推論的證明方法一階邏輯的邏輯推論證明方法類似于命題邏輯，常用反證法。但對于否證邏輯推論，則