人工智能第三章

1、人工智能第三章第1頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日命題命題：能判斷真假（不是既真又假）的陳述句。簡(jiǎn)單陳述句描述事實(shí)、事物的狀態(tài)、關(guān)系等性質(zhì)。例如：1 1+1=22 雪是黑色的。3 北京是中國(guó)的首都。4 到冥王星去渡假。命題通常用字母p ,q ,a ,b 表示； 判斷一個(gè)句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現(xiàn)在是假，隨著人類科學(xué)的發(fā)展，有可能變成真，但不管怎樣，真值是唯一的。因此，以上4個(gè)例子都是命題。而例如： 1 快點(diǎn)走吧！ 2 到那去？ 3 x+y10等等句子，都不是命題。第2頁(yè)，共80頁(yè)，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等價(jià)式：p當(dāng)且僅當(dāng)q，記做p q否定：p 、 最優(yōu)先，其次為、，再次為， 第3頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式。如：設(shè)“下雨”為p，“騎車上班”為q，1“只要不下雨，我騎自行車上班”。p 是 q的充分條件，因而，可得命題公式： p q2“只有不下雨，我才

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

4、，10點(diǎn)59分，星期日命題公式的解釋定義：設(shè)為一個(gè)命題公式，p1,p2,pn是出現(xiàn)在中的全部原子命題，給原子命題各指定一個(gè)真值（或者），稱為對(duì)的一個(gè)賦值或解釋。若的值為真，則稱為成真賦值。若的值為假，則稱為成假賦值。第6頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日公式邏輯真值表第7頁(yè)，共80頁(yè)，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 等價(jià)等值式： p q ( p q )(q p )等價(jià)否定式： p q p q 第8頁(yè)，共80頁(yè)，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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日范式：公式的標(biāo)準(zhǔn)型式。定義：設(shè)A為一個(gè)公式若A無(wú)成假賦值，則稱A為

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

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

8、第13頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日常用的推理規(guī)則：（）前提引入規(guī)則（）結(jié)論引入規(guī)則（）置換規(guī)則：等價(jià)的可以置換例.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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯的歸結(jié)法歸謬法：命題： A1、A2、A3 和 B求證： A1

9、A2A3成立，則B成立，即：A1A2A3 B為永真 A1A2A3 B 等價(jià)于(A1A2A3)B 等價(jià)于(A1A2A3)B) 等價(jià)于(A1A2A3)B) 永真 即證明 (A1A2A3)B) 永假反證法：證明A1A2A3B 是矛盾式 （永假式） 第15頁(yè)，共80頁(yè)，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簡(jiǎn)化 s s 合取 永假矛盾。第16頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)原理由由1965年提出。與演繹法(

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

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

12、20日，10點(diǎn)59分，星期日命題邏輯的歸結(jié)法歸結(jié)過(guò)程 將命題寫成合取范式求出子句集對(duì)子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句 ，S是不可滿足的（矛盾），原命題成立。 （證明完畢）謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過(guò)程一樣。 第20頁(yè)，共80頁(yè)，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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日命題邏輯歸結(jié)例題（2）子句集為： PQ，Q，P（4）對(duì)子句集中的子句進(jìn)行歸結(jié)可得：1. PQ2. Q3. P4. Q，（1，3歸結(jié)）5. ，（2，4歸結(jié)）由上可得原公式成立。第22頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日3.2謂詞歸結(jié)原理基礎(chǔ)一階邏輯基本概念個(gè)體詞：表示主語(yǔ)的詞(客體、具體事物或抽象的概念）謂詞：刻畫個(gè)體性質(zhì)或個(gè)體之間關(guān)系的詞量詞：表示數(shù)量的詞第23頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日謂詞歸結(jié)原理基礎(chǔ)小王是個(gè)工程師。8是個(gè)自然數(shù)

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

15、22年，5月20日，10點(diǎn)59分，星期日例如：（1）所有的人都是要死的。 （2） 有的人活到一百歲以上。在個(gè)體域D為人類集合時(shí)，可符號(hào)化為：（1）xP(x)，其中P(x)表示x是要死的。（2）x Q(x), 其中Q(x)表示x活到一百歲以上。在個(gè)體域D是全總個(gè)體域時(shí)，引入特殊謂詞R(x)表示x是人，可符號(hào)化為：（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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日一階謂詞邏輯1謂詞公式原子公式：?jiǎn)蝹€(gè)謂詞就是原子公

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

17、替代，就構(gòu)成了一個(gè)謂詞公式的解釋。 當(dāng)存在解釋能使謂詞公式為真時(shí)，則稱這個(gè)解釋滿足謂詞公式。 這個(gè)解釋就是這個(gè)謂詞公式的模型。 兩個(gè)謂詞公式等價(jià)，當(dāng)且僅當(dāng)所有的解釋下兩個(gè)謂詞公式的值是相同的。 永真式 不可滿足式 歸結(jié)原理就是對(duì)謂詞公式的正確性證明轉(zhuǎn)化為不可滿足性證明。第28頁(yè)，共80頁(yè)，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è)個(gè)體域?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頁(yè)，共80頁(yè)，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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日前束范式定義：說(shuō)公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。 第31頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日即： 把所有的量詞都提到前面去，然后消掉所有量詞(Q1x1)(Q2x2)(Qnxn)

20、M(x1,x2,xn)例第32頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日謂詞推理要運(yùn)用與命題邏輯相同的推理規(guī)則和量詞的消去和引入。任意量詞可以消去，用變量或常量表示，存在量詞可以用常量表示。對(duì)于任意量詞，為自由變量，為不在中約束出現(xiàn)的個(gè)體變量時(shí)：（）=（）為常量（）=（）對(duì)于存在量詞， （）=（）對(duì)于變量引入量詞：（）=（）要求在（）中自由出現(xiàn)，且為真，不在（）中約束出現(xiàn)。（）=（）要求是特定常量，取代的不能在（）中出現(xiàn)。第33頁(yè)，共80頁(yè)，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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日謂詞知識(shí)表示知識(shí)：是人們?cè)谡J(rèn)識(shí)、改造世界中經(jīng)驗(yàn)的總結(jié)或者實(shí)事的描述。使用邏輯法表示知識(shí)，將自然語(yǔ)言描述的知識(shí)，通過(guò)謂詞、函數(shù)加以描述，獲得邏輯謂詞公式，進(jìn)而利用計(jì)算機(jī)進(jìn)行處理。例：校長(zhǎng)與小李打網(wǎng)球。可以表示為：定義：Play(x ,y,z)表示，和打這種球Play(zhang ,li,tennis) 清華是個(gè)大學(xué)定義：Univ(

22、x)表示是大學(xué) Univ(qinghua)第35頁(yè)，共80頁(yè)，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)用謂詞表示知識(shí)應(yīng)用廣泛：（）易于用數(shù)據(jù)庫(kù)存貯知識(shí)（）謂詞具有完備邏輯推理方法（）表達(dá)的知識(shí)具有科學(xué)嚴(yán)密性（）邏輯推理具有知識(shí)的一致性第36頁(yè)，共80頁(yè)，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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日量詞消去原則：消去存在量詞“”，略去全程量詞“”。注意：左邊有全程量詞的存在量詞，消去時(shí)該變量改寫成為全程量詞的函數(shù)；如沒(méi)有，改寫成為常量。第38頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日謂詞歸結(jié)子句形( Skolem 標(biāo)準(zhǔn)形)Skolem定理：謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。 SKOLEM標(biāo)準(zhǔn)形定義：消去量詞后的

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

27、星期日謂詞歸結(jié)子句形G = G1 G2 G3 Gn 的子句形G的字句集可以分解成幾個(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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日求取子句集例(1)例：對(duì)所有的x,y,z來(lái)說(shuō)，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個(gè)人都有父親，試問(wèn)對(duì)某個(gè)人來(lái)說(shuō)誰(shuí)是它的祖父？求：用一階邏輯表示這個(gè)問(wèn)題，并建立子句集。解：這里我們首先引入謂詞：P(x, y) 表示x是y的父親

28、Q(x, y) 表示x是y的祖父ANS(x) 表示問(wèn)題的解答第45頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日求取子句集例(2)對(duì)于第一個(gè)條件，“如果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)對(duì)于第二個(gè)條件：“每個(gè)人都有父親”，一階邏輯表達(dá)式：A2：(y)(x)P(x, y)S A2：P(f(y), y)對(duì)于結(jié)論：某個(gè)人是它的祖父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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)原理歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數(shù)，所以要考慮合一和置換。 第47頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日置換與合一置換：可以簡(jiǎn)單的理解為是在一個(gè)謂詞公式中用置換項(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)在另一個(gè)ti中。例如a/x，c/y，f(b)/z是一個(gè)置換。g(y)/x，f(x)/y不是一個(gè)置換， 第48頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日置換的合成設(shè)t1/x1, t2/x2, , tn/xn， u1/y1, u2/y2, , un/yn，是兩個(gè)置換。 則與的合成也是一個(gè)置換，記作。它是從集合t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, , un/yn 中刪去以下兩種元素： 當(dāng)ti=xi時(shí)，刪去ti/xi (i = 1, 2, , n); 當(dāng)yix1,x2, , xn時(shí)，刪去uj/yj

31、(j = 1, 2, , m)最后剩下的元素所構(gòu)成的集合。 合成即是對(duì)ti先做置換然后再做置換，置換xi第49頁(yè)，共80頁(yè)，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，需要?jiǎng)h除；a/x，b/y滿足定義中的條件ii，也需要?jiǎng)h除。最后得f(b)/x，y/z第50

32、頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日合一合一可以簡(jiǎn)單地理解為“尋找相對(duì)變量的置換，使兩個(gè)謂詞公式一致”。定義：設(shè)有公式集FF1，F(xiàn)2，F(xiàn)n，若存在一個(gè)置換，可使F1F2= Fn，則稱是F的一個(gè)合一。同時(shí)稱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是它的一個(gè)合一。注意：一般說(shuō)來(lái)，一個(gè)公式集的合一不是唯一的。 第51頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日最一般合一： 設(shè)是謂詞公式集F，如果對(duì)F的任意一個(gè)合一都存在一個(gè)置換使得=，則稱是一個(gè)最一般的合一mg

33、u.最一般合一求取方法：逐一比較找出不一致，并做合一置換算法：對(duì)于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頁(yè)，共80頁(yè)，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頁(yè)，共

34、80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)式要考慮變量的置換和合一歸結(jié)式：對(duì)兩個(gè)無(wú)公共變量的字句 對(duì)于子句C1L1和C2L2，如果L1與L2可合一，且s是其合一者，則(C1C2)s是其歸結(jié)式。其中L1、L2是單文字。事實(shí)上L1、L2中有一個(gè)含有否定符，所以對(duì)另一個(gè)加上否定符后，才能判斷它們是否可合一。 例（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頁(yè)，共80頁(yè)，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), )，不可以；是不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，PQ與PQ的空，不可以先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并） 第55頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)的過(guò)程寫出謂詞關(guān)系公式 用反演法寫出謂詞表達(dá)式 SKOLEM標(biāo)準(zhǔn)形 子句集S 對(duì)S中可歸結(jié)的子句做歸結(jié) 歸結(jié)式仍放入S中，反復(fù)歸結(jié)過(guò)程 得到空子句 得證第56頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日子句集的化簡(jiǎn) 在謂詞邏輯中，任何一個(gè)謂詞公式都可以通過(guò)應(yīng)用等價(jià)關(guān)系及推理規(guī)則化成相應(yīng)的子句集。其化簡(jiǎn)步驟如下： (1)

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

37、如，上式經(jīng)等價(jià)變換后為 (x)(y)P(x，y)(y)( Q(x，y) R(x，y)第58頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日子句集的化簡(jiǎn) (3) 對(duì)變?cè)獦?biāo)準(zhǔn)化 在一個(gè)量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變?cè)坑昧硗庖粋€(gè)沒(méi)有出現(xiàn)過(guò)的任意變?cè)妫共煌吭~約束的變?cè)胁煌拿帧?例如，上式經(jīng)變換后為 (x)(y)P(x，y)(z)( Q(x，z) R(x，z) (4) 化為前束范式 化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動(dòng)時(shí)不能改變其相對(duì)順序。由于第(3)步已對(duì)變?cè)M(jìn)行了標(biāo)準(zhǔn)化，每個(gè)量詞都有自己的變?cè)?，這就消除了任何由變?cè)饹_突的可能，因此這種

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

39、，上步所得公式中存在量詞(y)和(z)都位于(x)的轄域內(nèi)，因此都需要用Skolem函數(shù)來(lái)替換。設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后的式子為 (x)(P(x,f(x)(Q(x,g(x)R(x,g(x)第60頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日2. 子句集的化簡(jiǎn) (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)形需要使用以下等價(jià)關(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) 消去全稱量詞 由于母式中的全部變?cè)苋Q量詞的約束，并且全稱量詞的次序已無(wú)關(guān)緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設(shè)其變?cè)潜蝗Q量詞量化的。 例如，上式消去全稱量詞后為 (P(x,f(x)Q(x,g(x) (P(x,f(x)R(x,g(x)第61頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日2. 子句集的化簡(jiǎn) (8) 消去合取詞 在母式中消去所有合取詞，把母式用子句集的形式表示出來(lái)。其中，子句集中的每一個(gè)元素都是一個(gè)子句。 例如，上式的子句集中包含以下兩個(gè)子句 P

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

42、 （1）否定Q，得到Q （2）把Q加入到公式集F，得到F， Q稱為S （3）對(duì)S進(jìn)行歸結(jié)，歸結(jié)到空子句為止。第63頁(yè)，共80頁(yè)，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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日例題“快樂(lè)學(xué)

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

44、快樂(lè)的”的否定Happy(zhang)第65頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日例題“快樂(lè)學(xué)生”問(wèn)題由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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日對(duì)于用歸結(jié)原理求取問(wèn)題答案步驟：（1）把已知化為謂詞公式并轉(zhuǎn)化成子句集S(2) 把待求解的問(wèn)題用謂詞公式表示，并否定之，然后和謂詞ANSWER(x)構(gòu)成析取式，x代表問(wèn)題的答案。（3）把第二步的析取式和S合并，構(gòu)成S(4) 對(duì)S進(jìn)行歸

46、結(jié)（5）若歸結(jié)出ANSWER(x)，并且在x已經(jīng)被替代， 被替代就是答案。第67頁(yè)，共80頁(yè)，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é)； 求：小劉的老師是誰(shuí)？解：把已知前提及待求解的問(wèn)題表示成謂詞公式： 第68頁(yè)，共80頁(yè)，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頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日第70頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)原理歸結(jié)法的實(shí)質(zhì)：歸結(jié)法是僅有一條推理規(guī)則的推理方法。 歸結(jié)的過(guò)程是一個(gè)語(yǔ)義樹(shù)倒塌的過(guò)程。 歸結(jié)法的問(wèn)題子句中有等號(hào)或不等號(hào)時(shí)，完備性不成立。 Herbrand定理的不實(shí)用性引出了可實(shí)用的歸結(jié)法。第71頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日歸結(jié)過(guò)程的控制策略要解決的問(wèn)題：歸結(jié)方法的知識(shí)爆炸。控制策略的目的歸結(jié)點(diǎn)盡量少控制策略的原則給出控制策略，以使僅對(duì)選擇合適的子句間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)?；蛘哒f(shuō)，少做些歸結(jié)仍能導(dǎo)出空子句。第72頁(yè)，共80頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日控制策略的方法(1)刪除策略完備名詞解釋：歸類：設(shè)有兩個(gè)子句C和D，若有置換使得C D成立，則稱子句C把子句D歸類。由于小的可以代表大的，所以小的吃掉大的了。若對(duì)S使用歸結(jié)推理過(guò)程中，當(dāng)歸結(jié)式Cj是重言式（永真式）和Cj被S中子句和子句集的歸結(jié)式Ci(ij)所歸類時(shí)，便將Cj刪除。這樣的推理過(guò)程便稱做使用了刪除策略的歸結(jié)過(guò)