人工智能第三章

1、人工智能第三章第1頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題命題：能判斷真假（不是既真又假）的陳述句。簡單陳述句描述事實(shí)、事物的狀態(tài)、關(guān)系等性質(zhì)。例如：1 1+1=22 雪是黑色的。3 北京是中國的首都。4 到冥王星去渡假。命題通常用字母p ,q ,a ,b 表示； 判斷一個句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現(xiàn)在是假，隨著人類科學(xué)的發(fā)展，有可能變成真，但不管怎樣，真值是唯一的。因此，以上4個例子都是命題。而例如： 1 快點(diǎn)走吧！ 2 到那去？ 3 x+y10等等句子，都不是命題。第2頁，共80頁，2022年，5

2、月20日，10點(diǎn)59分，星期日命題邏輯公式 定義： 原子命題：不能再分解的命題稱為原子命題。 合式公式：原子命題是合式公式，連接詞聯(lián)結(jié)的合式公式的組合也是合 式公式（ 命題公式）。常用的聯(lián)結(jié)詞：合取式：p與q，記做p q析取式： p或q，記做p q蘊(yùn)含式： 如果p則q，記做p q等價式：p當(dāng)且僅當(dāng)q，記做p q否定：p 、 最優(yōu)先，其次為、，再次為， 第3頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式。如：設(shè)“下雨”為p，“騎車上班”為q，1“只要不下雨，我騎自行車上班”。p 是 q的充分條件，因而，可得命題公式： p q2“只有不下雨，我才

3、騎自行車上班”。p 是 q的必要條件，因而，可得命題公式：q p 第4頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題表示公式（2）事件化為命題公式的步驟：（）分析簡單命題，將其符號化；（）使用適當(dāng)?shù)穆?lián)結(jié)詞把簡單命題連接起來。例如：1 “如果我進(jìn)城我就去看你，除非我很累。”設(shè)：p，我進(jìn)城，q，去看你，r，我很累。則有命題公式：r (p q)。2“應(yīng)屆高中生，得過數(shù)學(xué)或物理競賽的一等 獎，保送上北京大學(xué)?！?設(shè)：p，應(yīng)屆高中生，q，保送上北京大學(xué)上學(xué)， r，是得過數(shù)學(xué)一等獎。t，是得過物理一等獎。 則有命題公式公式：p ( r t ) q。 第5頁，共80頁，2022年，5月20日

4、，10點(diǎn)59分，星期日命題公式的解釋定義：設(shè)為一個命題公式，p1,p2,pn是出現(xiàn)在中的全部原子命題，給原子命題各指定一個真值（或者），稱為對的一個賦值或解釋。若的值為真，則稱為成真賦值。若的值為假，則稱為成假賦值。第6頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日公式邏輯真值表第7頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯基礎(chǔ)基本等值式交換率：pq q p ； p q q p 結(jié)合率： (pq) r p(q r); (p q) r p (q r)分配率： p(q r) (pq)(p r) ；p (q r) (p q) (p r) 雙重否定率： p p 等冪

5、率： p pp ， p p p 等價等值式： p q ( p q )(q p )等價否定式： p q p q 第8頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯基礎(chǔ)摩根率: (pq) p q ； (p q) p q 吸收率: p(pq ) p ； p (pq ) p 同一律: p0 p ； p1 p 蘊(yùn)含等值式:p q pq 假言易位式: p q p q 歸謬式: (p q ) (p q ) p 排中律： pp ；矛盾律： pp 零率：p ； p 第9頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日范式：公式的標(biāo)準(zhǔn)型式。定義：設(shè)A為一個公式若A無成假賦值，則稱A為

6、重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個成真賦值，則稱A為可滿足的；簡單合取式：有限個原子命題或其否定構(gòu)成合取式。簡單析取式：有限個原子命題或其否定構(gòu)成析取式。析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。范式的性質(zhì)：析取范式是矛盾式，當(dāng)且僅當(dāng)每個簡單合取式是矛盾式。合取范式是永真式，當(dāng)且僅當(dāng)每個簡單析取式是永真式。第10頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日范式的轉(zhuǎn)化存在定理：任何命題公式都存在著與之等值的析取范式和合取范式。求合取范式的步驟：（）消去多余的，以及聯(lián)結(jié)詞（）去掉否定符號（）利用分配率例

7、：3.1,3.23.1.3命題邏輯的意義把自然語言轉(zhuǎn)化為形式語言，以利于計算機(jī)能夠處理。第11頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日例3.2：求的（）合取范式解： （） （） （） （）（）（） （）（）第12頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯的推理規(guī)則（自然演繹推理）邏輯結(jié)論：對于，如果永真，則稱是的邏輯結(jié)論，即推出的結(jié)論正確，為真則為真，記為=。常用的推理定律（永真式）： ，附加：=（）簡化： （）= 假言推理：（）=拒取式：（）=析取三段論：（）=假言三段論： （）（）=（）等價三段論： （）（）=（）構(gòu)造性二難：（）（）（） ）=（）

8、第13頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日常用的推理規(guī)則：（）前提引入規(guī)則（）結(jié)論引入規(guī)則（）置換規(guī)則：等價的可以置換例.4：證明：如果今天是下雨天，則要帶傘或帶雨衣。如果走路上班，則不帶雨衣。今天下雨，走路上班，所以帶雨傘。解：把題目用命題公式表示：今天下雨p，帶傘q，帶雨衣r，走路上班s前提： p（q r）， s r， p， s要證的結(jié)論： q證明： p（q r） p前提引入（q r）假言推理 s s r前提引入 r假言推理 q析取三段論第14頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯的歸結(jié)法歸謬法：命題： A1、A2、A3 和 B求證： A1

9、A2A3成立，則B成立，即：A1A2A3 B為永真 A1A2A3 B 等價于(A1A2A3)B 等價于(A1A2A3)B) 等價于(A1A2A3)B) 永真 即證明 (A1A2A3)B) 永假反證法：證明A1A2A3B 是矛盾式 （永假式） 第15頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日例：前提： p（rs）q)， p， s要證的結(jié)論： q證明： p（rs）q) p前提引入 （rs）q 假言推理 q 引入否定結(jié)論 （rs） 拒取式 s前提引入 s簡化 s s 合取 永假矛盾。第16頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)原理由由1965年提出。與演繹法(

10、deductive inference)完全不同，新的邏輯演算(inductive inference)算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。 語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。 而歸結(jié)方法是自動推理、自動推導(dǎo)證明用的。（“數(shù)學(xué)定理機(jī)器證明”）第17頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯的歸結(jié)法子句集子句：子句是文字的集合，各個文字之間被析取分隔。文字：原子命題或否定被稱為文字。合取范式：命題、命題或的與， 如：P（ PQ

11、）（ PQ）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：P（ PQ）（ PQ） 子句集 S：S = P, PQ, PQ 第18頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)式設(shè)C1, C2是子句集中的兩個子句，如果C1中的文字L1與C2中文字L2互補(bǔ)，則可以從C1和 C2中分別消去文字L1和文字L2，并將中余下的部分按析取關(guān)系構(gòu)成一個新子句C12，這個過程就叫歸結(jié)。如子句：C1=PQ, C2=PW ， 歸結(jié)式： C12 = WQ 性質(zhì)：歸結(jié)式 C12 是親本子句C1和 C2邏輯結(jié)論。C1C2 C12 ，注意：反之不一定成立。 第19頁，共80頁，2022年，5月

12、20日，10點(diǎn)59分，星期日命題邏輯的歸結(jié)法歸結(jié)過程 將命題寫成合取范式求出子句集對子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句 ，S是不可滿足的（矛盾），原命題成立。 （證明完畢）謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。 第20頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯歸結(jié)例題（1）例題，已知：(P Q) 求證： (Q P)證明： （1）根據(jù)歸結(jié)原理，將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式：(P Q) (Q P)（2）分別將公式前項(xiàng)化為合取范式：P Q P Q結(jié)論求后的后項(xiàng)化為合取范式：(Q P) (QP) Q P兩項(xiàng)合并后化為合取范式：（

13、P Q）Q P （3）則子句集為： PQ，Q，P第21頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯歸結(jié)例題（2）子句集為： PQ，Q，P（4）對子句集中的子句進(jìn)行歸結(jié)可得：1. PQ2. Q3. P4. Q，（1，3歸結(jié)）5. ，（2，4歸結(jié)）由上可得原公式成立。第22頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日3.2謂詞歸結(jié)原理基礎(chǔ)一階邏輯基本概念個體詞：表示主語的詞(客體、具體事物或抽象的概念）謂詞：刻畫個體性質(zhì)或個體之間關(guān)系的詞量詞：表示數(shù)量的詞第23頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞歸結(jié)原理基礎(chǔ)小王是個工程師。8是個自然數(shù)

14、。我去買花。小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個體詞，而“是個工程師”、“是個自然數(shù)”、“去買”、“是朋友”都是謂詞。顯然前兩個謂詞表示的是事物的性質(zhì)，第三個謂詞“去買”表示的一個動作也表示了主、賓兩個個體詞的關(guān)系，最后一個謂詞“是朋友”表示兩個個體詞之間的關(guān)系。第24頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞歸結(jié)原理基礎(chǔ)個體常量：a,b,c個體變量：x,y,z謂詞符號：P,Q,R謂詞：由謂詞符號和個體（項(xiàng)）組成。例P(x,y)一階謂詞：謂詞中不含有謂詞。n元謂詞：就是有n個項(xiàng)。量詞符號： ,第25頁，共80頁，20

15、22年，5月20日，10點(diǎn)59分，星期日例如：（1）所有的人都是要死的。 （2） 有的人活到一百歲以上。在個體域D為人類集合時，可符號化為：（1）xP(x)，其中P(x)表示x是要死的。（2）x Q(x), 其中Q(x)表示x活到一百歲以上。在個體域D是全總個體域時，引入特殊謂詞R(x)表示x是人，可符號化為：（1）x（R(x) P(x)）, 其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x) Q(x)），其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。 第26頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日一階謂詞邏輯1謂詞公式原子公式：單個謂詞就是原子公

16、式。謂詞公式：簡單說就是由原子公式、連接詞、否定符號以及量詞構(gòu)成的式子。指導(dǎo)變量：量詞后面的變量稱為指導(dǎo)變量。x 、y轄域：就是量詞管轄的區(qū)域。約束出現(xiàn)：在轄域內(nèi)，受量詞約束的變量是約束出現(xiàn)。自由出現(xiàn)：在轄域內(nèi)，不受量詞約束的變量是約束出現(xiàn)。換名規(guī)則：將量詞轄域中某個約束出現(xiàn)的個體變量改成在此轄域中未出現(xiàn)過的個體變量符號。xP(x,y)R(x,y) 第27頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日替換規(guī)則：對某個自由變量用與原公式中所有個體變量符號不同的變量去替代，且處處替代。 xP(x,y)R(x,y)替換xP(x,z)R(x,z)2.謂詞公式的解釋 對謂詞公式的各變量常量去

17、替代，就構(gòu)成了一個謂詞公式的解釋。 當(dāng)存在解釋能使謂詞公式為真時，則稱這個解釋滿足謂詞公式。 這個解釋就是這個謂詞公式的模型。 兩個謂詞公式等價，當(dāng)且僅當(dāng)所有的解釋下兩個謂詞公式的值是相同的。 永真式 不可滿足式 歸結(jié)原理就是對謂詞公式的正確性證明轉(zhuǎn)化為不可滿足性證明。第28頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞演算與推理1.謂詞演算公式量詞否定等值式：( x ） M（x） （ y ） M（y） ( x ） M（x） （ y ） M（y）量詞分配等值式：( x ）( P（x） Q（x）) ( x ） P（x） ( x ） Q（x）( x ）( P（x） Q（x）) (

18、x ） P（x） ( x ） Q（x）消去量詞等值式：設(shè)個體域?yàn)橛懈F集合（a1, a2, an）( x ） P（x） P（ a1 ） P（ a2 ） P（ an ）( x ）P（x） P（ a1 ） P（ a2 ） P（ an ）第29頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日約束變量換名規(guī)則：(Qx)P(x) (Qy)P(y) (Qx)P(x,z) (Qy)P(y,z)量詞轄域收縮與擴(kuò)張等值式：( x ）( P（x） Q) ( x ） P（x） Q( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）(Q P

19、（x） ) Q ( x ） P（x） ( x ）( P（x） Q) ( x ） P（x） Q( x ）( P（x） Q) ( x ） P（x） Q ( x ）( P（x） Q) ( x ） P（x） Q ( x ）(Q P（x） ) Q ( x ） P（x）第30頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日前束范式定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。 第31頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日即： 把所有的量詞都提到前面去，然后消掉所有量詞(Q1x1)(Q2x2)(Qnxn)

20、M(x1,x2,xn)例第32頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞推理要運(yùn)用與命題邏輯相同的推理規(guī)則和量詞的消去和引入。任意量詞可以消去，用變量或常量表示，存在量詞可以用常量表示。對于任意量詞，為自由變量，為不在中約束出現(xiàn)的個體變量時：（）=（）為常量（）=（）對于存在量詞， （）=（）對于變量引入量詞：（）=（）要求在（）中自由出現(xiàn)，且為真，不在（）中約束出現(xiàn)。（）=（）要求是特定常量，取代的不能在（）中出現(xiàn)。第33頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日例3.10 20世紀(jì)年代的漫畫都是日本漫畫家創(chuàng)作的，這幅漫畫是世紀(jì)年代的作品，因此這幅漫畫是日

21、本漫畫家的作品。解：設(shè)(x)：是20世紀(jì)年代的漫畫Q():日本漫畫家的作品a: 一幅漫畫 前提 x(x) Q(x) ,P(a)結(jié)論 Q(a) 證明 x(x) Q(x) P(a) (a) Q(a) Q(a) 第34頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞知識表示知識：是人們在認(rèn)識、改造世界中經(jīng)驗(yàn)的總結(jié)或者實(shí)事的描述。使用邏輯法表示知識，將自然語言描述的知識，通過謂詞、函數(shù)加以描述，獲得邏輯謂詞公式，進(jìn)而利用計算機(jī)進(jìn)行處理。例：校長與小李打網(wǎng)球?？梢员硎緸椋憾x：Play(x ,y,z)表示，和打這種球Play(zhang ,li,tennis) 清華是個大學(xué)定義：Univ(

22、x)表示是大學(xué) Univ(qinghua)第35頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日常用的可以用蘊(yùn)含代表規(guī)則：人人都受法律管制： Human(x)Lawed(x) 如果犯罪則被懲罰 Commit(x)Punished(x)（Human(x)Lawed(x)） （Commit(x)Punished(x)）應(yīng)用謂詞表示知識應(yīng)用廣泛：（）易于用數(shù)據(jù)庫存貯知識（）謂詞具有完備邏輯推理方法（）表達(dá)的知識具有科學(xué)嚴(yán)密性（）邏輯推理具有知識的一致性第36頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日.3謂詞邏輯歸結(jié)原理歸結(jié)原理命題： A1、A2、A3 和 B求證： A1A2

23、A3成立，則B成立，反證法：證明A1A2A3B 是矛盾式 （永假式）3.3.2Skolem 標(biāo)準(zhǔn)形1.前束范式2. Skolem 標(biāo)準(zhǔn)形 消去前束范式中的所有量詞的公式第37頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日量詞消去原則：消去存在量詞“”，略去全程量詞“”。注意：左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)；如沒有，改寫成為常量。第38頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞歸結(jié)子句形( Skolem 標(biāo)準(zhǔn)形)Skolem定理：謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。 SKOLEM標(biāo)準(zhǔn)形定義：消去量詞后的

24、謂詞公式。注意：謂詞公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。 第39頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞歸結(jié)子句形( Skolem 標(biāo)準(zhǔn)形)例:將下式化為Skolem標(biāo)準(zhǔn)形：(x)(y)P(a, x, y) (x)(y)Q(y, b)R(x)解：第一步，消去號，得：(x)(y)P(a, x, y) (x) (y)Q(y, b)R(x)第二步，深入到量詞內(nèi)部，得：(x)(y)P(a, x, y) (x) (y)Q(y, b)R(x)第三步，變元易名，得(x)(y)P(a, x, y) (u) ( v)(Q(v, b) R(u)第四步，存在量詞左移，直至所有的量詞移到前面

25、，得： (x) (y) (u) ( v)P(a, x, y) (Q(v, b) R(u)由此得到前述范式第40頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞歸結(jié)子句形( Skolem 標(biāo)準(zhǔn)形)第五步，消去“”（存在量詞），略去“”全稱量詞消去(y)，因?yàn)樗筮呏挥?x)，所以使用x的函數(shù)f(x)代替之，這樣得到：(x)(z)( P(a, x, f(x) Q(z, b)R(x)消去(z)，同理使用g(x)代替之，這樣得到：(x) ( P(a, x, f(x) Q(g(x), b)R(x)則，略去全稱變量，原式的Skolem標(biāo)準(zhǔn)形為： P(a, x, f(x) Q(g(x), b)

26、R(x) 第41頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日子句集子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集S的求取： G SKOLEM標(biāo)準(zhǔn)形 消去存在變量 以“，”取代“”，并表示為集合形式 。第42頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日謂詞歸結(jié)子句形 G是不可滿足的 S是不可滿足的G與S不等價，但在不可滿足得意義下是一致的。 定理：若G是給定的公式，而S是相應(yīng)的子句集，則G是不可滿足的 S是不可滿足的。 注意：G真不一定S真，而S真必有G真。即： S = G第43頁，共80頁，2022年，5月20日，10點(diǎn)59分，

27、星期日謂詞歸結(jié)子句形G = G1 G2 G3 Gn 的子句形G的字句集可以分解成幾個單獨(dú)處理。 有 SG = S1 U S2 U S3 U U Sn則SG 與 S1 U S2 U S3 U U Sn在不可滿足得意義上是一致的。即SG 不可滿足 S1 U S2 U S3 U U Sn不可滿足第44頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日求取子句集例(1)例：對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？求：用一階邏輯表示這個問題，并建立子句集。解：這里我們首先引入謂詞：P(x, y) 表示x是y的父親

28、Q(x, y) 表示x是y的祖父ANS(x) 表示問題的解答第45頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日求取子句集例(2)對于第一個條件，“如果x是y 的父親， y又是z 的父親，則x是z 的祖父”，一階邏輯表達(dá)式如下：A1：(x)(y)(z)(P(x, y)P(y, z)Q(x, z)S A1：P(x ,y)P(y, z)Q(x, z)對于第二個條件：“每個人都有父親”，一階邏輯表達(dá)式：A2：(y)(x)P(x, y)S A2：P(f(y), y)對于結(jié)論：某個人是它的祖父B：(x)(y)Q(x, y)否定后得到子句： （ (x)(y)Q(x, y)） ANS(x)SB：

29、Q(x, y)ANS(x)則得到的相應(yīng)的子句集為： S A1，S A2，SB 第46頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)原理歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數(shù)，所以要考慮合一和置換。 第47頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日置換與合一置換：可以簡單的理解為是在一個謂詞公式中用置換項(xiàng)去置換變量。定義：置換是形如t1/x1, t2/x2, , tn/xn的有限集合。其中，x1, x2, , xn是互不相同的變量，t1, t2, , tn是不同于xi的項(xiàng)（常量、變量、函數(shù)）；ti/xi表示用ti置換xi

30、，并且要求ti與xi不能相同，而且xi不能循環(huán)地出現(xiàn)在另一個ti中。例如a/x，c/y，f(b)/z是一個置換。g(y)/x，f(x)/y不是一個置換， 第48頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日置換的合成設(shè)t1/x1, t2/x2, , tn/xn， u1/y1, u2/y2, , un/yn，是兩個置換。 則與的合成也是一個置換，記作。它是從集合t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , un/yn 中刪去以下兩種元素： 當(dāng)ti=xi時，刪去ti/xi (i = 1, 2, , n); 當(dāng)yix1,x2, , xn時，刪去uj/yj

31、(j = 1, 2, , m)最后剩下的元素所構(gòu)成的集合。 合成即是對ti先做置換然后再做置換，置換xi第49頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日置換的合成例：設(shè)：f(y)/x, z/y，a/x, b/y, y/z，求與的合成。解：先求出集合f(b/y)/x, (y/z)/y, a/x, b/y, y/zf(b)/x, y/y, a/x, b/y, y/z其中，f(b)/x中的f(b)是置換作用于f(y)的結(jié)果；y/y中的y是置換作用于z的結(jié)果。在該集合中，y/y滿足定義中的條件i，需要刪除；a/x，b/y滿足定義中的條件ii，也需要刪除。最后得f(b)/x，y/z第50

32、頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日合一合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞公式一致”。定義：設(shè)有公式集FF1，F(xiàn)2，F(xiàn)n，若存在一個置換，可使F1F2= Fn，則稱是F的一個合一。同時稱F1，F(xiàn)2，. ，F(xiàn)n是可合一的。例：設(shè)有公式集FP(x, y, f(y), P(a,g(x),z)，則a/x, g(a)/y, f(g(a)/z是它的一個合一。注意：一般說來，一個公式集的合一不是唯一的。 第51頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日最一般合一： 設(shè)是謂詞公式集F，如果對F的任意一個合一都存在一個置換使得=，則稱是一個最一般的合一mg

33、u.最一般合一求取方法：逐一比較找出不一致，并做合一置換算法：對于F1和F2令W=F1,F2令k=0，W0=W, 0=如果Wk已合一，停止,k=mgu ,，否則找不一致集Dk若Dk中存在元素vk和tk，其中vk不出現(xiàn)于tk中，轉(zhuǎn)，否則不可合一令k+1=ktk/vk, Wk+1=Wktk/tk =Wk+1k=k+1轉(zhuǎn)?？勺C明若F1和F2可合一，算法必停于第52頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日例3.16：W=P(a,x,f(g(y),P(z,f(a),f(u), F1= P(a,x,f(g(y), F2=P(z,f(a),f(u),求： F1和F2的最一般合一第53頁，共

34、80頁，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)式要考慮變量的置換和合一歸結(jié)式：對兩個無公共變量的字句 對于子句C1L1和C2L2，如果L1與L2可合一，且s是其合一者，則(C1C2)s是其歸結(jié)式。其中L1、L2是單文字。事實(shí)上L1、L2中有一個含有否定符，所以對另一個加上否定符后，才能判斷它們是否可合一。 例（1）P(x) Q(x,y)與P(a) R(b,z)（2）P(x,y) Q(x) R(x)與P(a,z) Q(b)第54頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)式歸結(jié)的注意事項(xiàng)：謂詞的一致性，P()與Q()， 不可以常量的一致性，P(a, )與P(b,.)，

35、 不可以 變量，P(a, .)與P(x, )， 可以變量與函數(shù)，P(a, x, .)與P(x, f(x), )，不可以；是不能同時消去兩個互補(bǔ)對，PQ與PQ的空，不可以先進(jìn)行內(nèi)部簡化（置換、合并） 第55頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)的過程寫出謂詞關(guān)系公式 用反演法寫出謂詞表達(dá)式 SKOLEM標(biāo)準(zhǔn)形 子句集S 對S中可歸結(jié)的子句做歸結(jié) 歸結(jié)式仍放入S中，反復(fù)歸結(jié)過程 得到空子句 得證第56頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日子句集的化簡 在謂詞邏輯中，任何一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集。其化簡步驟如下： (1)

36、 消去連接詞“”和“” 反復(fù)使用如下等價公式： PQ PQ PQ (PQ)(PQ)即可消去謂詞公式中的連接詞“”和“”。 例如公式 (x)(y)P(x,y) (y)(Q(x,y)R(x,y)經(jīng)等價變化后為 (x)(y)P(x,y) (y)(Q(x,y)R(x,y)第57頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日2. 子句集的化簡(2) 減少否定符號的轄域反復(fù)使用雙重否定率 (P) P摩根定律 (PQ) PQ (PQ) PQ量詞轉(zhuǎn)換率 (x)P(x) (x) P(x) (x)P(x) (x)P(x)將每個否定符號“”移到僅靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。 例

37、如，上式經(jīng)等價變換后為 (x)(y)P(x，y)(y)( Q(x，y) R(x，y)第58頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日子句集的化簡 (3) 對變元標(biāo)準(zhǔn)化 在一個量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn)過的任意變元代替，使不同量詞約束的變元有不同的名字。 例如，上式經(jīng)變換后為 (x)(y)P(x，y)(z)( Q(x，z) R(x，z) (4) 化為前束范式 化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。由于第(3)步已對變元進(jìn)行了標(biāo)準(zhǔn)化，每個量詞都有自己的變元，這就消除了任何由變元引起沖突的可能，因此這種

38、移動是可行的。 例如，上式化為前束范式后為 (x)(y) (z)(P(x，y)( Q(x，z) R(x，z)第59頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日2. 子句集的化簡 (5) 消去存在量詞 消去存在量詞時，需要區(qū)分以下兩種情況： 若存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞），只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。 若存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如 (x1)(xn) (y)P(x1，x2 , xn ,y)則需要用Skolem函數(shù)f(x1，x2 , xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。 例如

39、，上步所得公式中存在量詞(y)和(z)都位于(x)的轄域內(nèi)，因此都需要用Skolem函數(shù)來替換。設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后的式子為 (x)(P(x,f(x)(Q(x,g(x)R(x,g(x)第60頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日2. 子句集的化簡 (6) 化為Skolem標(biāo)準(zhǔn)形 Skolem標(biāo)準(zhǔn)形的一般形式為 (x1)(xn) M(x1,x2,xn)其中， M(x1,x2,xn)是Skolem標(biāo)準(zhǔn)形的母式，它由子句的合取所構(gòu)成。 把謂詞公式化為Skolem標(biāo)準(zhǔn)形需要使用以下等價關(guān)系 P(QR) (PQ)(PR)例如，前面的公式化為

40、Skolem標(biāo)準(zhǔn)形后為 (x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x) (7) 消去全稱量詞 由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設(shè)其變元是被全稱量詞量化的。 例如，上式消去全稱量詞后為 (P(x,f(x)Q(x,g(x) (P(x,f(x)R(x,g(x)第61頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日2. 子句集的化簡 (8) 消去合取詞 在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個元素都是一個子句。 例如，上式的子句集中包含以下兩個子句 P

41、(x,f(x)Q(x,g(x) P(x,f(x)R(x,g(x) (9) 更換變量名稱 對子句集中的某些變量重新命名，使任意兩個子句中不出現(xiàn)相同的變量名。由于每一個子句都對應(yīng)著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實(shí)際上不存在任何關(guān)系。這樣，更換變量名是不會影響公式的真值的。 例如，對前面的公式，可把第二個子句集中的變元名x更換為y，得到如下子句集 P(x,f(x)Q(x,g(x) P(y,f(y)R(y,g(y)第62頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日對于證明問題 設(shè)F為前提的公式集，Q為目標(biāo)公式集，用歸結(jié)反演證明的步驟：

42、 （1）否定Q，得到Q （2）把Q加入到公式集F，得到F， Q稱為S （3）對S進(jìn)行歸結(jié)，歸結(jié)到空子句為止。第63頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日例：求證:G是F1和F2的邏輯推論 F1：F2: G: 證明： 化為子句集P(a) (1) R(y)L(a,y) (2) P(x) Q(y) L(x,y) (3) R(b) (4) Q(b) (5) (2)(4)歸結(jié) L(a,b) (6) (1)(3)歸結(jié) Q(y) L(a,y) (7) (5)(7) L(a,b) (8)(6)(8) NIL 證畢。第64頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日例題“快樂學(xué)

43、生”問題假設(shè)任何通過計算機(jī)考試并獲獎的人都是快樂的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有的考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎。求證：張是快樂的。解：先將問題用謂詞表示如下：R1:“任何通過計算機(jī)考試并獲獎的人都是快樂的”(x)(Pass(x, computer)Win(x, prize)Happy(x)R2:“任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有考試”(x)(y)(Study(x)Lucky(x)Pass(x, y)R3:“張不肯學(xué)習(xí)但他是幸運(yùn)的”Study(zhang)Lucky(zhang)R4:“任何幸運(yùn)的人都能獲獎”(x)(Luck(x)Win(x,prize)結(jié)論：“張是

44、快樂的”的否定Happy(zhang)第65頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日例題“快樂學(xué)生”問題由R1及邏輯轉(zhuǎn)換公式:PWH = （PW） H ，可得 (1)Pass(x, computer)Win(x, prize)Happy(x)由R2： (2)Study(y)Pass(y,z) (3)Lucky(u)Pass(u,v)由R3： (4)Study(zhang) (5)Lucky(zhang)由R4： (6)Lucky(w)Win(w，prize)由結(jié)論：(7)Happy(zhang)（結(jié)論的否定）(8)Pass(w, computer)Happy(w)Luck(w

45、) (1)(6)，w/x(9)Pass(zhang, computer)Lucky(zhang) (8)(7)，zhang/w(10)Pass(zhang, computer) (9)(5)(11)Lucky(zhang) (10)(3)，zhang/u, computer/v(12) (11)(5)第66頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日對于用歸結(jié)原理求取問題答案步驟：（1）把已知化為謂詞公式并轉(zhuǎn)化成子句集S(2) 把待求解的問題用謂詞公式表示，并否定之，然后和謂詞ANSWER(x)構(gòu)成析取式，x代表問題的答案。（3）把第二步的析取式和S合并，構(gòu)成S(4) 對S進(jìn)行歸

46、結(jié)（5）若歸結(jié)出ANSWER(x)，并且在x已經(jīng)被替代， 被替代就是答案。第67頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日已知：F1: 李(li)先生是小趙(zhao)的老師； F2:小趙(zhao) 與小劉(liu)是同班同學(xué)； F3: 如果x與y是同班同學(xué)，則x的老師也是y的老師。 定義的謂詞如下： T(x，y)：表示x是y的老師； C(x，y)：表示x與y是同班同學(xué)； 求：小劉的老師是誰？解：把已知前提及待求解的問題表示成謂詞公式： 第68頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日把上述公式化為子句集：（1）（2）（3）（4）應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)：（5）

47、（1）和（3）歸結(jié) （4）和（5）歸結(jié)（2）和（6）歸結(jié)得知小劉的老師是李老師。第69頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日第70頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)原理歸結(jié)法的實(shí)質(zhì)：歸結(jié)法是僅有一條推理規(guī)則的推理方法。 歸結(jié)的過程是一個語義樹倒塌的過程。 歸結(jié)法的問題子句中有等號或不等號時，完備性不成立。 Herbrand定理的不實(shí)用性引出了可實(shí)用的歸結(jié)法。第71頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)過程的控制策略要解決的問題：歸結(jié)方法的知識爆炸?？刂撇呗缘哪康臍w結(jié)點(diǎn)盡量少控制策略的原則給出控制策略，以使僅對選擇合適的子句間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)?；蛘哒f，少做些歸結(jié)仍能導(dǎo)出空子句。第72頁，共80頁，2022年，5月20日，10點(diǎn)59分，星期日控制策略的方法(1)刪除策略完備名詞解釋：歸類：設(shè)有兩個子句C和D，若有置換使得C D成立，則稱子句C把子句D歸類。由于小的可以代表大的，所以小的吃掉大的了。若對S使用歸結(jié)推理過程中，當(dāng)歸結(jié)式Cj是重言式（永真式）和Cj被S中子句和子句集的歸結(jié)式Ci(ij)所歸類時，便將Cj刪除。這樣的推理過程便稱做使用了刪除策略的歸結(jié)過