謂詞邏輯與歸結(jié)原理-2015

謂詞邏輯與歸結(jié)原理華北電力大學(xué)計(jì)算機(jī)系2/5/20231第三章謂詞邏輯與歸結(jié)原理歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)過(guò)程的控制策略Herbrand定理2/5/20232華北電力大學(xué)歸結(jié)推理命題邏輯謂詞邏輯Skolem標(biāo)準(zhǔn)型、子句集基本概念謂詞邏輯歸結(jié)原理合一和置換、控制策略數(shù)理邏輯命題邏輯歸結(jié)Herbrand定理內(nèi)容框架2/5/20233華北電力大學(xué)第三章謂詞邏輯與歸結(jié)原理歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)過(guò)程的控制策略2/5/20234華北電力大學(xué)概述-推理技術(shù)推理按照某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過(guò)程。推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)醫(yī)療診斷專家系統(tǒng)知識(shí)庫(kù)中存儲(chǔ)經(jīng)驗(yàn)及醫(yī)學(xué)常識(shí)數(shù)據(jù)庫(kù)中存放病人的癥狀、化驗(yàn)結(jié)果等初始事實(shí)利用知識(shí)庫(kù)中的知識(shí)及一定的控制策略，為病人診治疾病、開出醫(yī)療處方就是推理過(guò)程2/5/20235華北電力大學(xué)概述推理的分類演繹推理、歸納推理、默認(rèn)推理

確定性推理、不精確推理

單調(diào)推理、非單調(diào)推理

啟發(fā)式推理、非啟發(fā)式推理

2/5/20236華北電力大學(xué)概述從推出新判斷的途徑分演繹、歸納和默認(rèn)推理演繹推理從全稱判斷推出特稱判斷或單稱判斷的過(guò)程，即從一般到個(gè)別的推理演繹推理中最常用的形式是三段論法（大前提和小前提，及結(jié)論）例如：所有的推理系統(tǒng)都是智能系統(tǒng)——一般的知識(shí)專家系統(tǒng)是推理系統(tǒng)——個(gè)體的判斷所以，專家系統(tǒng)是智能系統(tǒng)——新判斷

沒(méi)有增加新的知識(shí)2/5/20237華北電力大學(xué)概述-演繹推理、歸納推理和默認(rèn)推理歸納推理從足夠多的事例中歸納出一般性結(jié)論的推理過(guò)程，是一種從個(gè)別到一般的推理過(guò)程常用的歸納推理有簡(jiǎn)單枚舉法和類比法枚舉法歸納推理是由已觀察到的事物都有某屬性，而沒(méi)有觀察到相反的事例，從而推出某類事物都有某屬性，推理過(guò)程為：

S1是P S2是P …

Sn

是P(S1,S2,…Sn

是S類中的個(gè)別事物，在枚舉中兼容)

S都是P

2/5/20238華北電力大學(xué)概述-演繹推理、歸納推理和默認(rèn)推理歸納推理之枚舉法枚舉法歸納推理分完全歸納推理與不完全歸納推理完全歸納推理在進(jìn)行歸納時(shí)考察了相應(yīng)事物的全部對(duì)象，并根據(jù)這些對(duì)象是否都具有某種屬性，從而推出這個(gè)事物是否具有這個(gè)屬性完全歸納推理是必然性推理

不完全歸納推理只考察了相應(yīng)事物的部分對(duì)象，就得出了結(jié)論不完全推理得出的結(jié)論不具有必然性，屬于非必然性推理2/5/20239華北電力大學(xué)概述-演繹推理、歸納推理和默認(rèn)推理歸納推理之類比法在兩個(gè)或兩類事物在許多屬性上都相同的基礎(chǔ)上，推出它們?cè)谄渌鼘傩陨弦蚕嗤?，這就是類比法歸納推理類比法歸納可形式化地表示為：

A具有屬性a,b,c,d,e B具有屬性a,b,c,d,

B也具有屬性e類比法的可靠程度決定于兩個(gè)或兩類事物的相同屬性與推出的那個(gè)屬性之間的相關(guān)程度，相關(guān)程度越高，則類比法的可靠性就越高歸納推理增加了知識(shí)（在機(jī)器學(xué)習(xí)部分稱為歸納學(xué)習(xí)）

2/5/202310華北電力大學(xué)概述-演繹推理、歸納推理和默認(rèn)推理默認(rèn)推理又稱為缺省推理，是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理如：在條件A已成立的情況下，如果沒(méi)有足夠的證據(jù)能證明條件B不成立，則就默認(rèn)B是成立的，并在此默認(rèn)的前提下進(jìn)行推理，推導(dǎo)出某個(gè)結(jié)論知識(shí)不完全的情況下也能進(jìn)行推理如果到某一時(shí)刻發(fā)現(xiàn)原先所作的默認(rèn)不正確，則要撤消所作的默認(rèn)以及由此默認(rèn)推出的所有結(jié)論，重新按新情況進(jìn)行推理

2/5/202311華北電力大學(xué)概述按推理時(shí)所用的知識(shí)的確定性分確定性推理推理中所用的知識(shí)都是精確的歸結(jié)反演、基于規(guī)則的演繹系統(tǒng)等都是確定性推理不精確推理基于不確定的推理規(guī)則進(jìn)行，形成的結(jié)論也是不確定的專家系統(tǒng)中主要使用的是不精確推理2/5/202312華北電力大學(xué)概述按推出的結(jié)論是否單調(diào)增加，或推出的結(jié)論是否越來(lái)越接近最終目標(biāo)分：?jiǎn)握{(diào)推理在推理過(guò)程中隨著推理的向前推進(jìn)及新知識(shí)的加入，推出的結(jié)論呈單調(diào)增加的趨勢(shì)，并且越來(lái)越接近最終目標(biāo)非單調(diào)推理在推理過(guò)程中隨著推理的向前推進(jìn)及新知識(shí)的加入，不僅沒(méi)有加強(qiáng)已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始一般非單調(diào)推理是在知識(shí)不完全的情況下進(jìn)行的2/5/202313華北電力大學(xué)概述按推理中是否運(yùn)用與問(wèn)題有關(guān)的啟發(fā)性知識(shí)分啟發(fā)式推理推理過(guò)程中，運(yùn)用與問(wèn)題有關(guān)的啟發(fā)性知識(shí)，以加快推理過(guò)程，提高搜索效率A*、AO*等算法就屬于此類推理非啟發(fā)式推理推理過(guò)程中，不運(yùn)用啟發(fā)性知識(shí)，只按照一般的控制邏輯進(jìn)行推理這種方法缺乏對(duì)求解問(wèn)題的針對(duì)性，所以推理效率較低，容易出現(xiàn)“組合爆炸”問(wèn)題，如寬度優(yōu)先搜索法2/5/202314華北電力大學(xué)概述推理的控制策略

主要是指推理方向的選擇、推理時(shí)所用的搜索策略及沖突解決策略等一般推理的控制策略與知識(shí)表達(dá)方法有關(guān)推理方向推理方向用于確定推理的驅(qū)動(dòng)方式根據(jù)推理方向的不同，可將推理分為正向推理、反向推理和正反向混合推理無(wú)論按哪種方式進(jìn)行推理，一般都要求系統(tǒng)具有一個(gè)存放知識(shí)的知識(shí)庫(kù)（KB）、一個(gè)存放初始事實(shí)和中間結(jié)果的數(shù)據(jù)庫(kù)（DB）和一個(gè)用于推理的推理機(jī)2/5/202315華北電力大學(xué)概述-推理的控制策略推理方向正向推理（事實(shí)驅(qū)動(dòng)推理）是由已知事實(shí)出發(fā)向結(jié)論方向的推理開始DB中是否包含問(wèn)題的解？將用戶提供的新事實(shí)加入DB中KB中是否有可適用的知識(shí)？把KB中所有適用的規(guī)則加入到RS中RS為空？按一定的沖突解決策略從RS中選擇一條規(guī)則進(jìn)行推理將推理結(jié)論加入DB中成功，退出用戶可是否補(bǔ)充新事實(shí)？失敗，退出將初始事實(shí)加入數(shù)據(jù)庫(kù)DB中是否否是否是否2/5/202316華北電力大學(xué)概述-推理的控制策略推理方向反向推理——以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的一種推理，又稱為目標(biāo)驅(qū)動(dòng)推理或逆向推理在KB中找出所有能導(dǎo)出該假設(shè)的規(guī)則，形成適用規(guī)則集RS該假設(shè)是否是事實(shí)？該假設(shè)在數(shù)據(jù)庫(kù)DB？從RS中選擇一條規(guī)則，并將該規(guī)則的一個(gè)條件作為新的假設(shè)目標(biāo)該假設(shè)成立有假設(shè)？退出詢問(wèn)用戶有事實(shí)？該假設(shè)成立，并將此假設(shè)作為事實(shí)存入DB提出假設(shè)開始是否是否否是是否2/5/202317華北電力大學(xué)概述-推理的控制策略推理方向正反混合推理是開始進(jìn)行正向推理需要反向推理？以正向推理所得結(jié)果作為假設(shè)進(jìn)行反向推理還需要正向推理嗎？輸出結(jié)果退出否是否2/5/202318華北電力大學(xué)概述-推理的控制策略搜索策略推理時(shí)，要反復(fù)用到知識(shí)庫(kù)中的規(guī)則，而知識(shí)庫(kù)中的規(guī)則又很多，這樣就存在著如何在知識(shí)庫(kù)中尋找可用規(guī)則的問(wèn)題為有效控制規(guī)則的選取，可以采用各種搜索策略常用搜索策略：狀態(tài)空間搜索（寬度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索等）啟發(fā)式搜索等（第三章）2/5/202319華北電力大學(xué)概述-推理的控制策略沖突解決策略

推理過(guò)程中，系統(tǒng)要不斷地用數(shù)據(jù)庫(kù)中的事實(shí)與知識(shí)庫(kù)中的規(guī)則進(jìn)行匹配，當(dāng)有一個(gè)以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫(kù)相匹配時(shí)，就需要有一種策略來(lái)決定首先使用哪一條規(guī)則，這就是沖突解決策略沖突解決策略實(shí)際上就是確定規(guī)則的啟用順序

2/5/202320華北電力大學(xué)概述-推理的控制策略推理的控制策略

沖突解決策略

(1)

專一性排序 如果某一規(guī)則的條件部分規(guī)定的情況比另一規(guī)則的條件部分所規(guī)定的情況更專門，則這條規(guī)則具有較高的優(yōu)先級(jí)

例，有如下規(guī)則： 規(guī)則1：IFAANDBANDCTHENE； 規(guī)則2：IFAANDBANDCANDDTHENF； 數(shù)據(jù)庫(kù)中A、B、C、D均為真，這時(shí)規(guī)則1和規(guī)則2都與數(shù)據(jù)庫(kù)相匹配，但因?yàn)橐?guī)則2的條件部分包括了更多的限制，所以具有較高的優(yōu)先級(jí)

本策略是優(yōu)先使用針對(duì)性較強(qiáng)的產(chǎn)生式規(guī)則

2/5/202321華北電力大學(xué)概述-推理的控制策略推理的控制策略

3．沖突解決策略

(2)

規(guī)則排序 規(guī)則編排的順序就表示了啟用的優(yōu)先級(jí)

(3)

數(shù)據(jù)排序 數(shù)據(jù)排序就是把規(guī)則條件部分的所有條件排序，按優(yōu)先級(jí)次序編排，發(fā)生沖突時(shí)，首先使用在條件部分包含較高優(yōu)先級(jí)數(shù)據(jù)的規(guī)則

(4)

就近排序 把最近使用的規(guī)則放在最優(yōu)先的位置。如果某一規(guī)則經(jīng)常使用，則傾向于更多地使用這條規(guī)則

(5)

上下文限制 上下文限制就是把產(chǎn)生式規(guī)則按它們所描述的上下文分組，在某種上下文條件下，只能從與其相對(duì)應(yīng)的那組規(guī)則中選擇可應(yīng)用的規(guī)則2/5/202322華北電力大學(xué)概述-推理的控制策略推理的控制策略

3．沖突解決策略

(6)

按匹配度排序

在不精確匹配中，為了確定兩個(gè)知識(shí)模式是否可以進(jìn)行匹配，需要計(jì)算這兩個(gè)模式的相似程度，當(dāng)其相似度達(dá)到某個(gè)預(yù)先規(guī)定的值時(shí)，就認(rèn)為它們是可匹配的。若有幾條規(guī)則均可匹配成功，則可根據(jù)它們的匹配度來(lái)決定哪一個(gè)產(chǎn)生式規(guī)則可優(yōu)先被應(yīng)用

(7)按條件個(gè)數(shù)排序

如果有多條產(chǎn)生式規(guī)則生成的結(jié)論相同，則要求條件少的產(chǎn)生式規(guī)則被優(yōu)先應(yīng)用，因?yàn)橐髼l件少的規(guī)則匹配時(shí)花費(fèi)的時(shí)間較少不同的系統(tǒng)，可使用上述這些策略的不同組合2/5/202323華北電力大學(xué)概述歸結(jié)原理由J.A.Robinson于1965年提出定理證明的實(shí)質(zhì)就是要對(duì)給出的（已知的）前提和結(jié)論，證明此前提推導(dǎo)出該結(jié)論這一事實(shí)是永恒的真理這是非常困難的，幾乎是不可實(shí)現(xiàn)的要證明在一個(gè)論域上一個(gè)事件是永真的：就要證明在該域中的每一個(gè)點(diǎn)上該事實(shí)都成立論域是不可數(shù)時(shí)，該問(wèn)題不可能解決即使可數(shù)，如果該論域是無(wú)限的，問(wèn)題也無(wú)法簡(jiǎn)單地解決2/5/202324華北電力大學(xué)概述理論基礎(chǔ)：Herbrand采用了反證法的思想，將永真性的證明問(wèn)題轉(zhuǎn)化成為不可滿足性的證明問(wèn)題實(shí)現(xiàn)方法：Robinson的歸結(jié)原理使得自動(dòng)定理證明得以實(shí)現(xiàn)歸結(jié)推理方法在人工智能推理方法中有著很重要的歷史地位，是機(jī)器定理證明的主要方法2/5/202325華北電力大學(xué)歸結(jié)法的特點(diǎn)歸結(jié)法是一階邏輯中，至今為止的最有效的半可判定的算法。也是最適合計(jì)算機(jī)進(jìn)行推理的邏輯演算方法半可判定一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定（證明其為永真式）當(dāng)不知道該公式是否為恒真時(shí)，使用歸結(jié)原理不能得到任何結(jié)論2/5/202326華北電力大學(xué)歸結(jié)法基本原理采用反證法(反演推理方法)將待證明的表達(dá)式（定理）轉(zhuǎn)換成為邏輯公式（謂詞公式）然后再進(jìn)行歸結(jié)歸結(jié)能夠順利完成，則證明原公式（定理）是正確的2/5/202327華北電力大學(xué)歸結(jié)法基本原理—例例：由命題邏輯描述的命題：A1、A2、A3和B，要求證明：如果A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B是重言式（永真式）歸結(jié)法的思路A1ΛA2ΛA3→B是重言式等價(jià)于A1ΛA2ΛA3Λ～B是矛盾式，也就是永假式反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）2/5/202328華北電力大學(xué)歸結(jié)法和其它推理方法的比較語(yǔ)義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等知識(shí)表示方法的推理都是以邏輯推理方法為前提的也就是說(shuō)如果有了規(guī)則和已知條件，就能夠依據(jù)一定的規(guī)則和公理順藤摸瓜找到結(jié)果歸結(jié)方法是在一個(gè)規(guī)則指導(dǎo)下，進(jìn)行自動(dòng)推導(dǎo)。多用于計(jì)算機(jī)自動(dòng)推理、自動(dòng)推導(dǎo)證明注意：只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問(wèn)題2/5/202329華北電力大學(xué)第三章謂詞邏輯與歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)過(guò)程的控制策略Herbrand定理2/5/202330華北電力大學(xué)第三章謂詞邏輯與歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)過(guò)程的控制策略Herbrand定理2/5/202331華北電力大學(xué)命題描述事實(shí)、事物的狀態(tài)、關(guān)系等性質(zhì)的文字串，取值為真或假（表示是否成立）的句子稱作命題命題：非真即假的簡(jiǎn)單陳述句能判斷真假陳述句命題用小寫字母p、q、r、s等表示2/5/202332華北電力大學(xué)命題例命題：能判斷真假（不是既真又假）的陳述句

簡(jiǎn)單陳述句描述事實(shí)、事物的狀態(tài)、關(guān)系等性質(zhì)例如：1．

1+1=2 2．

雪是黑色的。

3．

北京是中國(guó)的首都。

4．

到冥王星去渡假。

判斷一個(gè)句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上4個(gè)例子都是命題。例如：1．

快點(diǎn)走吧！

2．

到哪兒去？

3．

x+y>10

都不是命題。2/5/202333華北電力大學(xué)命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式。如：設(shè)“下雨”為p，“騎車上班”為q，1．“只要不下雨，我騎自行車上班”?！玴

是q的充分條件，因而，可得命題公式：～p→q2．“只有不下雨，我才騎自行車上班”。～p

是q的必要條件，因而，可得命題公式：q→～p2/5/202334華北電力大學(xué)命題表示公式（2）例如：1．

“如果我進(jìn)城我就去看你，除非我很累。” 設(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。

2/5/202335華北電力大學(xué)命題邏輯基礎(chǔ)—數(shù)理邏輯的基本定義命題邏輯基礎(chǔ)：定義：合取式：p與q，記做p∧

q析取式：

p或q，記做p∨

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

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

q

。。。。。。歸結(jié)法的基礎(chǔ)2/5/202336華北電力大學(xué)命題邏輯基礎(chǔ)—數(shù)理邏輯的基本定義定義：若A無(wú)成假賦值，則稱A為重言式或永真式若A無(wú)成真賦值，則稱A為矛盾式或永假式若A至少有一個(gè)成真賦值，則稱A為可滿足的析取范式：僅由有限個(gè)簡(jiǎn)單合取式組成的析取式合取范式：僅由有限個(gè)簡(jiǎn)單析取式組成的合取式2/5/202337華北電力大學(xué)命題邏輯基礎(chǔ)—基本等值式(1)基本等值式24個(gè)交換率：p∨q

<=>q

∨p

；

p∧q<=>q∧

p

結(jié)合率：(p∨q)∨

r<=>p∨(q

∨r); (p∧q)∧

r<=>p∧(q∧r)分配率：p∨(q

∧

r)<=>(p∨q)∧(p∨r)

；

p∧(q∨

r)<=>(p∧q)∨(p∧r)2/5/202338華北電力大學(xué)命題邏輯基礎(chǔ)—基本等值式(2)摩根率:～

(p∨q)

<=>～

p∧

～

q

；

～

(p∧

q)

<=>～

p∨

～

q

吸收率:p∨(p

∧

q)<=>p

；

p∧(p∨q

)<=>p

同一律:p∨0

<=>p

；

p∧1

<=>p

蘊(yùn)含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q雙重否定律p

<=>～

～

p零率律p∨0

<=>p;p∧1

<=>p2/5/202339華北電力大學(xué)命題邏輯基礎(chǔ)-合取范式范式：公式的標(biāo)準(zhǔn)形式合取范式：?jiǎn)卧泳洹卧泳涞幕颍ā牛┑呐c（∧）如：P∧（P∨Q）∧（～P∨Q）求合取范式的步驟求合取范式的基本原則利用∨對(duì)∧例：求取P∧(Q→R)→S的合取范式1.消去對(duì)于{→，∨，∧}來(lái)說(shuō)冗余的連接詞2.內(nèi)移或消去否定號(hào)3.利用分配律2/5/202340華北電力大學(xué)命題邏輯基礎(chǔ)-合取范式解：P∧(Q→R)→S

=～（P∧(～Q∨R)∨S

=～P∨～(～Q∨R)∨S

=～P∨(～～Q∧～R)∨S

=～P∨(Q∧～R)∨S

=～P∨S∨(Q∧～R)

=(～P∨S∨Q)∧(～P∨S∨～R)注意：將原有的命題公式整理、轉(zhuǎn)換成為各個(gè)“或”語(yǔ)句的“與”，不然后續(xù)推導(dǎo)沒(méi)有意義轉(zhuǎn)換是基于數(shù)理邏輯的基本等值公式進(jìn)行的，“或”轉(zhuǎn)換到“與”中2/5/202341華北電力大學(xué)命題邏輯的推理規(guī)則邏輯結(jié)論（有效結(jié)論）：A→B如A→B為重言式（永真式），則稱A推結(jié)論B的推理正確。B是A的邏輯結(jié)論稱A→B為由前件A推結(jié)論B的推理的形式結(jié)構(gòu)可采用真值表法、等值演算法等證明邏輯結(jié)論邏輯結(jié)論也稱為假言推理或演繹推理重言式表示為AB2/5/202342華北電力大學(xué)命題邏輯的推理規(guī)則——常用的推理定律附加：A（A∨B）簡(jiǎn)化：（A∧B）A假言推理：（（A→B）∧A）B拒取式：（（A→B）∧～B）～A析取三段論：（（A∨B）∧～A）B假言三段論：（（A→B）∧（B→C））A→C等價(jià)三段論：（（AB）∧（BC））AC構(gòu)造性二難：（（A→B）∧（C→D）∧（A∨C））（B∨D）2/5/202343華北電力大學(xué)命題邏輯的推理規(guī)則——常用的推理規(guī)則前提引入規(guī)則：在證明的任何步驟上，都可以引入前提結(jié)論引入規(guī)則：在證明的任何步驟上，所證明的結(jié)論都可以作為后續(xù)證明的前提置換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題都可以用與之等值的命題公式置換例如，可以用～p∨q置換p→q2/5/202344華北電力大學(xué)命題邏輯的演繹推理-例1例3.3：構(gòu)造下列推理的證明。前提p∨q，p→～r，s→t，～s→r，～t結(jié)論q證明：

①s→t

前提引入 ②～t 前提引入 ③～s ①②拒取規(guī)則 ④～s→r

前提引入 ⑤r ③④假言推理 ⑥p→～r 前提引入 ⑦～p ⑤⑥拒取規(guī)則 ⑧p∨q

前提引入 ⑨q ⑦⑧析取三段論2/5/202345華北電力大學(xué)命題邏輯的演繹推理-例2例3.4寫出對(duì)應(yīng)下面推理的證明。如果今天是下雨天，則要帶雨傘或帶雨衣。如果走路上班，則不帶雨衣。今天下雨，走路上班，所以帶傘。解：p：今天下雨。q：帶傘。r：帶雨衣。s：走路上班。前提：p→（q∨r），s→～r，p，s結(jié)論：q證明：

①p→（q∨r） 前提引入 ②p 前提引入 ③q∨r ①②假言推理 ④s→~r

前提引入 ⑤s 前提引入 ⑥～r ④⑤假言推理 ⑦q ③⑥析取三段論2/5/202346華北電力大學(xué)命題邏輯的歸結(jié)演繹推理：從一系列前提得出結(jié)論上兩個(gè)例子歸結(jié)方法：新推理方法理論基礎(chǔ)是Herbrand定理將待證邏輯公式的結(jié)論，通過(guò)等值公式轉(zhuǎn)換成附加前提，再證明該邏輯公式不可滿足A1ΛA2ΛA3→B是重言式證明A1ΛA2ΛA3Λ～B不可滿足建立在子句集基礎(chǔ)上2/5/202347華北電力大學(xué)命題邏輯基礎(chǔ)-子句集命題公式的子句集S是合取范式形式下的子命題（元素）的集合子句集是合取范式中各個(gè)合取分量的集合生成子句集的過(guò)程可以簡(jiǎn)單地理解為將命題公式的合取范式中的與符號(hào)“∧”，置換為逗號(hào)“，”上例的合取范式：(～P∨S∨Q)∧(～P∨S∨～R)其子句集為S={～P∨S∨Q,～P∨S∨～R}命題公式：P∧（P∨Q）∧（～P∨Q）其子句集S：S={P,P∨Q,～P∨Q}2/5/202348華北電力大學(xué)命題邏輯的歸結(jié)—合取范式和子句集合取范式：命題、命題或的與，如：

P∧（P∨Q）∧（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：P∧（P∨Q）∧（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}2/5/202349華北電力大學(xué)命題邏輯的歸結(jié)法——?dú)w結(jié)式歸結(jié)式——?dú)w結(jié)法的核心設(shè)C1和C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個(gè)新子句C12，則稱這一個(gè)過(guò)程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句消去互補(bǔ)文字，用析取連接剩余部分例如：有子句：C1＝P∨C1'

，C2＝～P∨C2'

，存在互補(bǔ)對(duì)P和～P，則可得歸結(jié)式：C12=C1'∨C2'2/5/202350華北電力大學(xué)命題邏輯的歸結(jié)法——?dú)w結(jié)式性質(zhì)歸結(jié)式性質(zhì)：歸結(jié)式C12是親本子句C1和C2的邏輯結(jié)論C1ΛC2→C12任一使C1,C2

為真的解釋I下必有歸結(jié)式C12為真注意：C1ΛC2→C12，反之不一定成立。C1＝P∨C1'

，C2＝～P∨C2'

，C12=C1'∨C2'因?yàn)榇嬖谝粋€(gè)使C1'∨C2'為真的解釋I，不妨設(shè)C1'為真，C2'為假。若P為真，則～P∨C2'就為假了。因此反之不一定成立2/5/202351華北電力大學(xué)命題邏輯的歸結(jié)法——?dú)w結(jié)過(guò)程

建立待歸結(jié)命題公式：根據(jù)反證法將所求證的問(wèn)題轉(zhuǎn)化成為命題公式，求證其是矛盾式（永假式）求取合取范式建立子句集歸結(jié)對(duì)子句集中的子句使用歸結(jié)規(guī)則歸結(jié)式作為新子句加入子句集參加歸結(jié)歸結(jié)式為空子句□為止(說(shuō)明子句集不可滿足，即定理成立)。歸結(jié)完畢 謂詞歸結(jié)：除有量詞和函數(shù)以外，其余和命題歸結(jié)一樣2/5/202352華北電力大學(xué)命題邏輯歸結(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)＝～(Q∨～P)＝～Q∧P

兩項(xiàng)合并后化為合取范式： （～P∨Q）∧～Q∧P（3）則子句集為：

{～P∨Q，～Q，P}2/5/202353華北電力大學(xué)命題邏輯歸結(jié)例題（2）

子句集為： {～P∨Q，～Q，P}（4）對(duì)子句集中的子句進(jìn)行歸結(jié)可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3歸結(jié)）5.

， （2，4歸結(jié)）

由上可得原公式成立。2/5/202354華北電力大學(xué)第三章謂詞邏輯與歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)過(guò)程的控制策略Herbrand定理2/5/202355華北電力大學(xué)第三章謂詞邏輯與歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)過(guò)程的控制策略Herbrand定理2/5/202356華北電力大學(xué)謂詞邏輯歸結(jié)基礎(chǔ)—基本概念一階邏輯邏輯的基本定義基本概念個(gè)體詞：表示主語(yǔ)的詞個(gè)體常量：具體的或特定的個(gè)體個(gè)體變量：抽象的或泛指的個(gè)體謂詞：刻畫個(gè)體性質(zhì)或個(gè)體之間關(guān)系的詞謂詞常量：具體性質(zhì)或關(guān)系的謂詞謂詞變量：抽象或泛指的謂詞量詞：表示數(shù)量的詞量詞符號(hào)：全稱、存在量詞2/5/202357華北電力大學(xué)謂詞邏輯歸結(jié)基礎(chǔ)—基本概念-例小王是個(gè)工程師。8是個(gè)自然數(shù)。我去買花。小麗和小華是朋友。個(gè)體詞：“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”謂詞：“是個(gè)工程師”、“是個(gè)自然數(shù)”、“去買”、“是朋友”都是謂詞前兩個(gè)謂詞表示的是事物的性質(zhì)第三個(gè)謂詞“去買”表示的一個(gè)動(dòng)作也表示了主、賓兩個(gè)個(gè)體詞的關(guān)系最后一個(gè)謂詞“是朋友”表示兩個(gè)個(gè)體詞之間的關(guān)系2/5/202358華北電力大學(xué)謂詞邏輯歸結(jié)基礎(chǔ)—基本概念一階邏輯邏輯：以謂詞的形式來(lái)表示動(dòng)作的主體、客體公式及其解釋個(gè)體常量：a,b,c個(gè)體變量：x,y,z謂詞常量：P,Q,R謂詞變量：P(x),Q(x,y),R(x,b)量詞符號(hào)：

,,xP(x),xP(x)2/5/202359華北電力大學(xué)謂詞邏輯歸結(jié)基礎(chǔ)—基本概念原子公式：設(shè)P(x1,x2,…,xn)是任意n元謂詞，t1，t2，……，tn是項(xiàng)，則P(t1,t2,…,tn)為原子公式謂詞公式：原子公式是謂詞公式若A是謂詞公式，則(～A)也是謂詞公式若A、B是謂詞公式，則(A∧B)、(A∨B)、(A→B)、(A?B)也是謂詞公式若A是謂詞公式，則xA

,xA也是謂詞公式只有有限次的應(yīng)用①~④構(gòu)成的符號(hào)串才是謂詞公式2/5/202360華北電力大學(xué)謂詞邏輯歸結(jié)基礎(chǔ)—基本概念指導(dǎo)變量：xA,xA中的x為指導(dǎo)變量轄域：xA,xA中的A成為相應(yīng)量詞的轄域約束出現(xiàn)：在轄域（A）中，x的所有出現(xiàn)稱為約束出現(xiàn)自由出現(xiàn)：在轄域（A）中，不是約束出現(xiàn)的其他變量的出現(xiàn)，稱為自由出現(xiàn)2/5/202361華北電力大學(xué)謂詞邏輯歸結(jié)基礎(chǔ)—基本概念-例例如：（1）所有的人都是要死的。（2）

有的人活到一百歲以上。在個(gè)體域D為人類集合時(shí)，可符號(hào)化為：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(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活到一百歲以上。2/5/202362華北電力大學(xué)謂詞邏輯歸結(jié)基礎(chǔ)——謂詞公式等值式量詞否定等值式：～(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）)<=>(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

）2/5/202363華北電力大學(xué)謂詞邏輯歸結(jié)基礎(chǔ)——謂詞公式等值式量詞轄域收縮與擴(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（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）2/5/202364華北電力大學(xué)Skolem

標(biāo)準(zhǔn)型——前束范式SKolem標(biāo)準(zhǔn)型是在前束范式的基礎(chǔ)上進(jìn)行變量映射的前束范式定義：說(shuō)公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)將量詞提到公式最前端時(shí)存在約束變量換名問(wèn)題。要嚴(yán)守約束變?cè)膿Q名規(guī)則(Qx)M（x）（Qy

）M（y）(Qx)M（x,z）（Qy

）M（y,z）

例題Qi：量詞，M：母式2/5/202365華北電力大學(xué)例(w)P(w)→((x)((y)((z)(P(x,y,z)→(u)R(x,y,z,u)))))(w)~P(w)∨(x)((y)((z)(～P(x,y,z)∨(u)R(x,y,z,u))))(w)(x)(y)(z)(u)(~P(w)∨～P(x,y,z)∨R(x,y,z,u))2/5/202366華北電力大學(xué)Skolem

標(biāo)準(zhǔn)型前束范式中消去所有的量詞，則稱這種形式的謂詞公式為Skolem標(biāo)準(zhǔn)型Skolem標(biāo)準(zhǔn)型必須滿足合取范式的條件任何一個(gè)謂詞公式都可以化成與之對(duì)應(yīng)的Skolem標(biāo)準(zhǔn)型。但Skolem標(biāo)準(zhǔn)型不唯一2/5/202367華北電力大學(xué)Skolem

標(biāo)準(zhǔn)型——轉(zhuǎn)化過(guò)程將謂詞公式G轉(zhuǎn)換成為前束范式消去量詞量詞消去原則：消去存在量詞“”如果存在量詞左邊沒(méi)有任何全稱量詞，則只將其改寫成為常量（a,b等）如果是左邊有全稱量詞的存在量詞，消去時(shí)該變量改寫成為全稱量詞的函數(shù)(f(x),g(y)等)略去全稱量詞“”，簡(jiǎn)單地省略掉該量詞2/5/202368華北電力大學(xué)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)))=(x)(y)P(a,x,y)∧(x)((y)～Q(y,b)∧～R(x))第三步，任意量詞左移，利用分配律，得到

(x)((y)P(a,x,y)∧(y)(～Q(y,b)∧～R(x)))第四步，變?cè)酌?，存在量詞左移，直至所有的量詞移到前面，得：

(x)((y)P(a,x,y)∧(y)(～Q(y,b)∧～R(x)))=(x)((y)P(a,x,y)∧(z)(～Q(z,b)∧～R(x)))=(x)(y)(z)(P(a,x,y)∧(～Q(z,b)∧～R(x))

由此得到前述范式2/5/202369華北電力大學(xué)Skolem

標(biāo)準(zhǔn)型——例上頁(yè)：(x)(y)(z)(P(a,x,y)∧(～Q(z,b)∧～R(x))第五步，消去“”，略去“” 消去(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)∧～R(x)

例2：

((x)p(x)∨(x)Q(x))→(x)(p(x)∨Q(x))2/5/202370華北電力大學(xué)Skolem定理SKOLEM標(biāo)準(zhǔn)型定義： 消去量詞后的前束范式Skolem定理：

謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一注意：

謂詞公式G的SKOLEM標(biāo)準(zhǔn)型同G并不等值例如有謂詞公式G=(x)p(x)，其skolem標(biāo)準(zhǔn)型G’=P(a)

解釋I：個(gè)體域DI={0,1},常數(shù)a=0，謂詞P(x)為P(0)=F，P(1)=T，則在解釋I下G=T,G’=F2/5/202371華北電力大學(xué)子句集——定義子句與子句集文字：不含任何連接詞的謂詞公式子句：一些文字的析取（謂詞的和）空子句：不含任何文字的子句，子句集：所有子句的集合對(duì)于任一個(gè)公式G，都可以通過(guò)Skolem標(biāo)準(zhǔn)型，標(biāo)準(zhǔn)化建立起一個(gè)子句集與之相對(duì)應(yīng)2/5/202372華北電力大學(xué)子句集——求取步驟子句集S的求?。和ㄟ^(guò)Skolem標(biāo)準(zhǔn)型求取

G→前束范式 →消去量詞生成Skolem標(biāo)準(zhǔn)型→將Skolem標(biāo)準(zhǔn)型中的子句提出，表示為集合形式，即以“，”取代∧”，并表示為集合形式注意Skolem標(biāo)準(zhǔn)型必須滿足合取范式的條件2/5/202373華北電力大學(xué)子句集與謂詞公式的不可滿足性G是不可滿足的<=>S是不可滿足的G與S不等價(jià)，但在不可滿足的意義下是一致的

定理3.1： 若G是給定的公式，而S是相應(yīng)的子句集，則G是不可滿足的，當(dāng)且僅當(dāng)S是不可滿足的。

注意：G真不一定S真，而S真必有G真 即：S=>G2/5/202374華北電力大學(xué)子句集與謂詞公式的不可滿足性

——定理3.1的推廣謂詞公式G=G1ΛG2ΛG3Λ…ΛGn，G的子句集S的求取可以分解成幾個(gè)部分單獨(dú)處理。如果Gi的子句集為Si，則有：

S'=S1∪S2∪S3∪…∪Sn。雖然G的子句集不為S'，但是可以證明：

SG與S'

在不可滿足的意義上是一致的。即SG不可滿足

S1∪S2∪S3∪…∪Sn不可滿足2/5/202375華北電力大學(xué)求取子句集例(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的父親

Q(x,y)表示x是y的祖父

ANS(x)表示問(wèn)題的解答2/5/202376華北電力大學(xué)求取子句集例(2)對(duì)于第一個(gè)條件，“如果x是y的父親，y又是z的父親，則x是z的祖父”，一階邏輯表達(dá)式如下：

A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)對(duì)于第二個(gè)條件：“每個(gè)人都有父親”，一階邏輯表達(dá)式：

A2：(y)(x)P(x,y) SA2：P(f(y),y)對(duì)于結(jié)論：某個(gè)人是他的祖父

B：(x)(y)Q(x,y)

否定后得到子句：～((x)(y)Q(x,y))∨ANS(x) S～B：～Q(x,y)∨ANS(x)則得到的相應(yīng)的子句集為：{SA1，SA2，S～B}2/5/202377華北電力大學(xué)第三章謂詞邏輯與歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)過(guò)程的控制策略Herbrand定理2/5/202378華北電力大學(xué)第三章謂詞邏輯與歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)過(guò)程的控制策略Herbrand定理2/5/202379華北電力大學(xué)歸結(jié)原理歸結(jié)原理正確性的根本在于，如果在子句集中找到矛盾可以肯定命題是不可滿足的（不真）方法：和命題邏輯一樣但由于有函數(shù)，所以要考慮合一和置換

2/5/202380華北電力大學(xué)置換置換：在一個(gè)謂詞公式中用置換項(xiàng)去置換變量定義： 置換是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的變量，t1,t2,…,tn是不同于xi的項(xiàng)（常量、變量、函數(shù)）；ti/xi表示用ti置換xi，并且要求ti與xi不能相同，而且xi不能循環(huán)地出現(xiàn)在另一個(gè)ti中。例如

{a/x，c/y，f(b)/z}是一個(gè)置換

{g(y)/x，f(x)/y}不是一個(gè)置換2/5/202381華北電力大學(xué)置換定義：設(shè)是一個(gè)置換，E是一個(gè)表達(dá)式，把對(duì)E施行置換，即把E中出現(xiàn)的個(gè)體變?cè)獂i用ti替換，記為E例：={a/x,f(b)/y,c/z},G=P(x,y,z),求G

G=P(a,f(b),c)2/5/202382華北電力大學(xué)置換的合成

設(shè)＝{t1/x1,t2/x2,…,tn/xn}， ＝{u1/y1,u2/y2,…,um/ym}，是兩個(gè)置換。則與的合成也是一個(gè)置換，記作·。它是從集合

{t1·/x1,t2·/x2,…,tn·/xn,u1/y1,u2/y2,…,um/ym}

中刪去以下兩種元素：當(dāng)ti=xi時(shí)，刪去ti/xi(i=1,2,…,n)

當(dāng)yi{x1,x2,…,xn}時(shí)，刪去uj/yj

(j=1,2,…,m)

最后剩下的元素所構(gòu)成的集合合成即是對(duì)ti先做置換然后再做置換，置換xi2/5/202383華北電力大學(xué)置換的合成例：設(shè)：＝{f(y)/x,z/y}，＝{a/x,b/y,y/z}，求與的合成解：先求出集合

{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(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}2/5/202384華北電力大學(xué)合一合一可以簡(jiǎn)單地理解為“尋找相對(duì)變量的置換，使兩個(gè)謂詞公式一致”定義：設(shè)有公式集F＝{F1，F(xiàn)2，…，F(xiàn)n}，若存在一個(gè)置換，可使F1＝F2＝…=Fn，則稱是F的一個(gè)合一。同時(shí)稱F1，F(xiàn)2，...，F(xiàn)n是可合一的2/5/202385華北電力大學(xué)合一——例子例： 設(shè)有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，則＝{a/x,g(a)/y,f(g(a))/z}是它的一個(gè)合一。注意：一般說(shuō)來(lái)，一個(gè)公式集的合一不是唯一的2/5/202386華北電力大學(xué)最一般合一定義：最一般合一設(shè)σ是公式集F的一個(gè)合一，如果對(duì)F的任意一個(gè)合一θ都存在一個(gè)置換λ，使得θ＝σ·λ，則稱σ是一個(gè)最一般合一（MostGeneralUnifier，簡(jiǎn)記為mgu）2/5/202387華北電力大學(xué)最一般合一一個(gè)公式集的最一般合一是唯一的若用最一般合一去置換那些可合一的謂詞公式，可使它們變成完全一致的謂詞公式（——用途）mgu的求取方法對(duì)于給定謂詞公式F1和F2，采用逐一比較找出不一致，并作出相應(yīng)的合一置換，可求得mgu2/5/202388華北電力大學(xué)mgu求取方法令w={F1,F2}令k=0，w0=w，σ0=ε如果wk已合一，停止，σk=mgu，否則，找不一致集Dk若Dk中存在元素vk和tk，其中vk不出現(xiàn)于tk中，轉(zhuǎn)5，否則，不可合一令σk+1=σk{tk/vk},wk+1=wk{tk/vk}=wσk+1k=k+1,轉(zhuǎn)3若F1和F2可合一，算法必停止與32/5/202389華北電力大學(xué)mgu的例子例：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的最一般合一。2/5/202390華北電力大學(xué)mgu的例子2/5/202391華北電力大學(xué)mgu的例子2/5/202392華北電力大學(xué)歸結(jié)式和命題邏輯一樣消去互補(bǔ)對(duì)，但要考慮變量的合一與置換設(shè)C1、C2是兩個(gè)無(wú)公共變量的子句，L1和L2分別是C1和C2的文字，如果L1、～L2有最一般合一σ，則

R=（C1

σ-{L1σ}）∪（C2

σ-{L2σ}）稱作子句C1、C2的一個(gè)二元?dú)w結(jié)式，而L1和L2為被歸結(jié)的文字例子2/5/202393華北電力大學(xué)P(x)∨Q(x,y)與~P(a)∨R(b,z)的歸結(jié)式

Q(a,y)∨R(b,z)σ={a/x}

P(x,y)∨Q(x)∨R(x)與~P(a,z)∨~Q(b)的歸結(jié)式

Q(a)∨R(a)∨~Q(b)σ={a/x,y/z}

P(b,y)∨R(b)∨~P(a,z)σ={b/x}歸結(jié)式-例2/5/202394華北電力大學(xué)歸結(jié)原理——?dú)w結(jié)的注意事項(xiàng)謂詞的一致性，P()與～Q()，不可以常量的一致性，P(a,…)與～

P(b,….)，不可以；變量，P(a,….)與～P(x,…)，可以變量與函數(shù)，

P(x,x,….)與～P(x,f(x),…)，不可以；

P(x,x,….)與～P(x,f(y),…)，可以；不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，P∨Q與～P∨～Q得空，不可以先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并）

例子2/5/202395華北電力大學(xué)歸結(jié)原理——?dú)w結(jié)的過(guò)程歸結(jié)的過(guò)程寫出謂詞關(guān)系公式→用反演法寫出謂詞表達(dá)式→SKOLEM標(biāo)準(zhǔn)型→子句集S→對(duì)S中可歸結(jié)的子句做歸結(jié)→歸結(jié)式仍放入S中，反復(fù)歸結(jié)過(guò)程→得到空子句→

?得證2/5/202396華北電力大學(xué)例題“快樂(lè)學(xué)生”問(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é)論：“張是快樂(lè)的”的否定～Happy(zhang)2/5/202397華北電力大學(xué)例題“快樂(lè)學(xué)生”問(wèn)題由R1及邏輯轉(zhuǎn)換公式:P∧W→H=～（P∧W）∨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)∨～Lucky(w)(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)

2/5/202398華北電力大學(xué)例題某些患者喜歡所有醫(yī)生，沒(méi)有患者喜歡庸醫(yī)，所以沒(méi)有醫(yī)生是庸醫(yī)。2/5/202399華北電力大學(xué)第三章謂詞邏輯與歸結(jié)原理概述命題邏輯的歸結(jié)法謂詞邏輯歸結(jié)基礎(chǔ)歸結(jié)原理歸結(jié)