-第四章推理技術(shù)-謂詞邏輯課件

第四章推理技術(shù)

4.1一階謂詞邏輯推理4.2歸結(jié)演繹推理第四章推理技術(shù)4.1一階謂詞邏輯推理推理技術(shù)概述推理是人類求解問題的主要思維方法，即按照某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過程。按思維方式可分演繹推理、歸納推理、類比推理等。邏輯推理：按邏輯規(guī)則進(jìn)行的推理。分為：

經(jīng)典邏輯推理

:主要指命題邏輯和一階謂詞邏輯推理，也稱精確推理或確定性推理；

非經(jīng)典邏輯推理：主要指除經(jīng)典邏輯之外，按多值邏輯、模糊邏輯、概率邏輯等的推理，也稱為非精確推理或非確定性推理。推理技術(shù)概述推理是人類求解問題的主要思維方法，即按照某種策略邏輯推理舉例

經(jīng)典推理：蘇格拉底之死

如何判別謊言？

ABC三人都喜歡說謊話，偶爾也說真話。某天，A指責(zé)B說謊話，B指責(zé)C說謊話，C說AB兩人都在說謊話。問誰(shuí)在說謊？

邏輯推理舉例有幾條瘋狗？

村里有50戶人家，每家都養(yǎng)了一條狗?，F(xiàn)發(fā)現(xiàn)村子里面出現(xiàn)了n只瘋狗，村里規(guī)定，誰(shuí)要是發(fā)現(xiàn)了自己的狗是瘋狗，就要將自己的狗槍斃。但問題是，村子里面的人只能看出別人家的狗是不是瘋狗，而不能看出自己的狗是不是瘋的，如果看出別人家的狗是瘋狗，也不能告訴別人。于是大家開始觀察，第一天晚上，沒有槍聲，第二天晚上，沒有槍聲，第三天晚上，槍聲響起（具體幾槍不清楚），問村子里有幾只瘋狗？只有晚上才能看出病狗，并且一天晚上只能看一次。有幾條瘋狗？村里有50戶人家，每愛因斯坦的世界難題（1）愛因斯坦在20世紀(jì)初出一個(gè)謎語(yǔ)。他說世界上有98％的人答不出來。1、在一條街上，有5座房子，噴了5種顏色；2、每個(gè)房里住著不同國(guó)籍的人；3、每個(gè)人喝不同的飲料，抽不同品牌的香煙，養(yǎng)不同的寵物。

問題是：誰(shuí)養(yǎng)魚？

愛因斯坦的世界難題（1）愛因斯坦在20世紀(jì)初出一個(gè)謎語(yǔ)。他說愛因斯坦的世界難題（2）條件是：1、英國(guó)人住紅色房子； 2、瑞典人養(yǎng)狗；3、丹麥人喝茶； 4、綠色房子在白色房子左面；5、綠色房子主人喝咖啡；6、抽PallMall香煙的人養(yǎng)鳥；7、黃色房子主人抽Dunhill香煙；8、住在中間房子的人喝牛奶；9、挪威人住第一間房； 10、抽Blends香煙的人住在養(yǎng)貓的人隔壁11、養(yǎng)馬的人住抽Dunhill香煙的人隔壁；12、抽BlueMaster的人喝??；13、德國(guó)人抽Prince香煙； 14、挪威人住藍(lán)色房子隔壁；15、抽Blends香煙的人有一個(gè)喝水的鄰居。愛因斯坦的世界難題（2）條件是：邏輯學(xué)與計(jì)算機(jī)科學(xué)邏輯學(xué)：研究思維規(guī)律的科學(xué)計(jì)算機(jī)科學(xué)：模擬人腦行為和功能（思維）的科學(xué)思維：大腦、邏輯、語(yǔ)言、計(jì)算機(jī)邏輯是知識(shí)表示和推理的重要形式和工具邏輯學(xué)與計(jì)算機(jī)科學(xué)邏輯學(xué)：研究思維規(guī)律的科學(xué)8邏輯的歷史Aristotle——邏輯學(xué)Leibnitz——數(shù)理邏輯：邏輯+數(shù)學(xué)GottlobFrege(1848-1925)——一階謂詞演算系統(tǒng)邏輯是探索、闡述和確立有效推理原則的學(xué)科，最早由古希臘學(xué)者亞里士多德創(chuàng)建的。用數(shù)學(xué)的方法研究關(guān)于推理、證明等問題的學(xué)科就叫做數(shù)理邏輯。也叫做符號(hào)邏輯。20世紀(jì)30年代，數(shù)理邏輯廣泛發(fā)展，成為數(shù)學(xué)和計(jì)算機(jī)科學(xué)基礎(chǔ)。8邏輯的歷史Aristotle——邏輯學(xué)邏輯系統(tǒng)一個(gè)邏輯系統(tǒng)是定義語(yǔ)言和它的含義的方法。邏輯系統(tǒng)中的一個(gè)邏輯理論是該邏輯的語(yǔ)言的一個(gè)語(yǔ)句集合，它包括：邏輯符號(hào)集合：在所有該邏輯的邏輯理論中均出現(xiàn)的符號(hào)；非邏輯符號(hào)集合：不同的邏輯理論中出現(xiàn)的不同的符號(hào)；語(yǔ)句規(guī)則：定義什么樣的符號(hào)串是有意義的；證明：什么樣的符號(hào)串是一個(gè)合理的證明；語(yǔ)義規(guī)則：定義符號(hào)串的語(yǔ)義。邏輯系統(tǒng)一個(gè)邏輯系統(tǒng)是定義語(yǔ)言和它的含義的方法。邏輯程序語(yǔ)言邏輯符號(hào)保留字或者符號(hào)非邏輯符號(hào)用戶自定義的符號(hào)(變量名，函數(shù)名等)語(yǔ)句規(guī)則構(gòu)造一個(gè)程序的語(yǔ)句規(guī)則語(yǔ)義規(guī)則定義程序做什么的語(yǔ)句規(guī)則推理規(guī)則、公理和證明沒有邏輯與程序語(yǔ)言的對(duì)比邏輯程序語(yǔ)言邏輯符號(hào)保留字或者符號(hào)非邏輯符號(hào)用戶自定義的符號(hào)1.3命題邏輯命題：可以確定其真假的陳述句。Bolle提出了布爾代數(shù)。語(yǔ)言:原子Q、否定?、吸取V、合取、蘊(yùn)含、等價(jià)<->公式：AV?B，(AB,A)=>?

1.3命題邏輯命題：可以確定其真假的陳述句。Bolle提出-第四章推理技術(shù)-謂詞邏輯課件-第四章推理技術(shù)-謂詞邏輯課件

公司招聘工作人員，有M,N,Q三人應(yīng)聘，經(jīng)面試后，公司表示如下想法：（1）三人中至少錄取一人;（2）如果錄取M,則一定錄取N；（3）如果錄取N,則一定錄取Q。結(jié)果如何？公司招聘工作人員，有M,N,Q三人應(yīng)聘，經(jīng)面試1.4謂詞邏輯(一階邏輯)謂詞邏輯是一種形式語(yǔ)言，具有嚴(yán)密的理論體系，也是一種常用的知識(shí)表示方法。語(yǔ)言:

?，，，，(，)；常元，變?cè)?，函詞，謂詞；公式City（北京）City（上海）Age（張三，23）(x)(y)(z)(F(x,y)F(y,z)GF(x,z)）1.4謂詞邏輯(一階邏輯)謂詞邏輯是一種形式語(yǔ)言，具有嚴(yán)密謂詞邏輯中的形式演繹推理將自然語(yǔ)言中的陳述語(yǔ)句利用謂詞公式表示利用邏輯等價(jià)式將謂詞公式進(jìn)行變換利用邏輯蘊(yùn)含式推出結(jié)論符號(hào)化過程公式變形推理過程謂詞邏輯中的形式演繹推理將自然語(yǔ)言中的陳述語(yǔ)句利用邏輯等價(jià)式表4.1常用邏輯等價(jià)式表4.1常用邏輯等價(jià)式-第四章推理技術(shù)-謂詞邏輯課件-第四章推理技術(shù)-謂詞邏輯課件-第四章推理技術(shù)-謂詞邏輯課件表4.2常用邏輯蘊(yùn)含式表4.2常用邏輯蘊(yùn)含式-第四章推理技術(shù)-謂詞邏輯課件

設(shè)有前提：

(1)凡是大學(xué)生都學(xué)過計(jì)算機(jī)；

(2)小王是大學(xué)生。試問：小王學(xué)過計(jì)算機(jī)嗎？解令S(x)：x是大學(xué)生;M(x)：x學(xué)過計(jì)算機(jī);a：小王。則上面的兩個(gè)命題可用謂詞公式表示為

(1)x(S(x)→M(x))(2)S(a)例設(shè)有前提：例

下面我們進(jìn)行形式推理：

(1)x(S(x)→M(x))［前提］

(2)S(a)→M(a)［(1),US］

(3)S(a)［前提］

(4)M(a)［(2),(3),I3］得結(jié)果：M(a)，即“小王學(xué)過計(jì)算機(jī)”。

這種推理過程完全是一種符號(hào)變換過程，很類似于人們用自然語(yǔ)言推理的思維過程，因而稱為自然演繹推理下面我們進(jìn)行形式推理：這種推理過程完全是一種符號(hào)變換過程

在語(yǔ)法上，如果存在一個(gè)從假設(shè)到的證明，則記為

?，稱由可推導(dǎo)出的，或可證明的。如果在沒有任何假設(shè)下是可推導(dǎo)出的，則記為?，稱為可證明的。稱一個(gè)假設(shè)是不協(xié)調(diào)的，如果存在一個(gè)語(yǔ)句使得和的否定均可由推導(dǎo)得出。稱一個(gè)邏輯系統(tǒng)是一致的，或相容的(consistent)，如果不存在邏輯系統(tǒng)的公式A，使得?A與??A同時(shí)成立。證明(語(yǔ)法)在語(yǔ)法上，如果存在一個(gè)從假設(shè)到的證明，證

語(yǔ)言的解釋是在某個(gè)論域(domain)中定義非邏輯符號(hào)。語(yǔ)句的語(yǔ)義是在解釋下定義出語(yǔ)言L的真假值。如果I是L的一個(gè)解釋，且在I中為真，則記為I

?

，稱作I滿足，或者I是的一個(gè)模型。類似地，給定一個(gè)語(yǔ)句和一個(gè)語(yǔ)句，如果對(duì)每個(gè)解釋I

，有I

?

蘊(yùn)含I

?

，換言之，如果I是的一個(gè)模型則I也是的一個(gè)模型，則記為

?，我們稱為的一個(gè)邏輯結(jié)果。解釋(語(yǔ)義)語(yǔ)言的解釋是在某個(gè)論域(domain)中定義非邏輯解可靠性(reliable)語(yǔ)法->語(yǔ)義一個(gè)邏輯是可靠的，如果它的證明保持真假值，即在任何解釋I下，如果I是的模型，且可由推導(dǎo)出，則I也是的一個(gè)模型。即，一個(gè)邏輯是可靠的，如果對(duì)任何語(yǔ)句集合和語(yǔ)句，

?蘊(yùn)涵

??？煽啃院屯陚湫酝陚湫?complete)語(yǔ)義->語(yǔ)法一個(gè)邏輯是完備的，如果任何永真語(yǔ)句是可證的。即，對(duì)任何語(yǔ)句集合和語(yǔ)句，

?蘊(yùn)涵

?。如果一個(gè)邏輯是完備的，則該邏輯的證明系統(tǒng)已強(qiáng)到可以推出任何永真式。G?del完備性定理：一階邏輯是完備的可靠性(reliable)語(yǔ)法->語(yǔ)義可靠性和完備性可判定的一個(gè)邏輯稱為是可判定的(decidable)，如果存在一個(gè)算法對(duì)邏輯中的任一公式A，可確定?

A是否成立。否則，稱為是不可判定的(undecidable)

。如果上述算法雖不一定存在，卻有一個(gè)過程，可對(duì)該系統(tǒng)的定理做出肯定的判斷，但對(duì)非定理的公式過程未必終止，因而未必能作出判斷。這時(shí)稱邏輯是半可判定的?？膳卸ㄐ砸浑A邏輯是不可判定的，但它是半可判定的?？膳卸ǖ目膳卸ㄐ砸浑A邏輯是不可判定的，但它是半可判定的。

現(xiàn)代邏輯學(xué)與計(jì)算機(jī)科學(xué)、計(jì)算語(yǔ)言學(xué)和人工智能的關(guān)系表邏輯自然語(yǔ)程序人工邏輯指令與直數(shù)據(jù)庫(kù)復(fù)雜性智能體未來展望言處理控制智能編程陳式語(yǔ)言理論理論理論時(shí)序邏輯√√√√√√√√廣泛應(yīng)用模態(tài)邏輯√√√√√√√√非常活躍算法證明√√√√√√√√非單調(diào)推理√√√√√√√意義重大概率和模糊√√√√√√√目前主流直覺主義邏輯√√√√√√√√主要替代者高階邏輯，λ-演算√√√√√√更具中心作用經(jīng)典邏輯片斷√√√√√√前景誘人資源和子結(jié)構(gòu)邏輯√√√√纖維化和組合邏輯√√√√√√可自我指稱謬誤理論在適當(dāng)語(yǔ)境邏輯動(dòng)力學(xué)√√動(dòng)態(tài)邏輯觀論辯理論游戲√前景光明對(duì)象層次/元層次√√總起中心作用機(jī)制:溯因缺省相干√√邏輯的一部分與神經(jīng)網(wǎng)絡(luò)的聯(lián)系極重要，剛開始時(shí)間-行動(dòng)-修正模型√√一類新模型加標(biāo)演繹系統(tǒng)√√√√√邏輯學(xué)的統(tǒng)一框架

4.2歸結(jié)演繹推理

歸結(jié)演繹推理是基于一種稱為歸結(jié)原理(亦稱消解原理

principleofresolution)的推理規(guī)則的推理方法。歸結(jié)原理是由魯濱遜(J.A.Robinson)于1965年首先提出。它是謂詞邏輯的一個(gè)相當(dāng)有效的機(jī)械化推理方法。歸結(jié)原理的出現(xiàn)，被認(rèn)為是自動(dòng)推理，特別是定理機(jī)器證明領(lǐng)域的重大突破。從理論上解決了定理證明問題。

4.2歸結(jié)演繹推理

歸結(jié)演繹推理是基于一種稱有關(guān)歸結(jié)演繹推理的定義文字子句空子句子句集Skolem函數(shù)Skolem常量互補(bǔ)文字歸結(jié)，又稱消解(resolution)有關(guān)歸結(jié)演繹推理的定義文字

定義1原子謂詞公式及其否定稱為文字，若干個(gè)文字的一個(gè)析取式稱為一個(gè)子句不含任何文字的子句稱為空子句（真值為假），記為NIL。

例如下面的析取式都是子句

P∨Q∨乛RP(x,y)∨乛Q(x)定義1原子謂詞公式及其否定稱為文字，

定義2對(duì)一個(gè)謂詞公式G，通過以下步驟所得的子句集合S，稱為G的子句集。

(1)消去蘊(yùn)含詞→和等值詞←→。可使用邏輯等價(jià)式:①A→B乛A∨B②A←→B(乛A∨B)∧(乛B∨A)(2)縮小否定詞的作用范圍，直到其僅作用于原子公式?？墒褂眠壿嫷葍r(jià)式:①乛(乛A)A②乛(A∧B)乛A∨乛B將一個(gè)謂詞公式轉(zhuǎn)換為子句集定義2對(duì)一個(gè)謂詞公式G，通過以下步③乛(A∨B)乛A∧乛B④乛xP(x)x乛P(x)⑤乛xP(x)x乛P(x)(3)適當(dāng)改名，使量詞間不含同名自由變?cè)图s束變?cè)?/p>

(4)消去存在量詞。消去存在量詞時(shí)，同時(shí)還要進(jìn)行變?cè)鎿Q。變?cè)鎿Q分兩種情況：①若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的函數(shù)稱為Skolem函數(shù)；

②若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的常量符號(hào)稱為Skolem常量。③乛(A∨B)乛A∧乛B②若該存在量詞不在任何全稱xyP(x,y)根據(jù)步驟4轉(zhuǎn)換為xP(x,g(x))這里y=g(x)為Skolem函數(shù)。

xP(x)根據(jù)步驟4轉(zhuǎn)換為P(a),

這里a為Skolem常量

Skolem函數(shù)舉例xyP(x,y)根據(jù)步驟(5)消去所有全稱量詞。

(6)化公式為合取范式?？墒褂眠壿嫷葍r(jià)式:①A∨(B∧C)(A∨B)∧(A∨C)②(A∧B)∨C(A∨C)∧(B∨C)(7)適當(dāng)改名，使子句間無同名變?cè)?/p>

(8)消去合取詞∧，以子句為元素組成一個(gè)集合S。

(5)消去所有全稱量詞。

(A

B)(CD)

1.消去

(A

B)(CD)

轉(zhuǎn)換子句集舉例

(AB)(CD)

轉(zhuǎn)換子句集舉例

(A

B)(CD)

1.消去

(A

B)(CD)

2.縮減作用范圍

(AB)(CD)

轉(zhuǎn)換子句集舉例

(AB)(CD)

轉(zhuǎn)換子句集舉例

(A

B)(CD)

1.消去

(A

B)(CD)

2.縮減作用范圍

(AB)(CD)

3.化公式為合取范式

(A(CD))(B(CD)) (AC)(AD)(BC)(BD)轉(zhuǎn)換子句集舉例

(AB)(CD)

轉(zhuǎn)換子句集舉例

(A

B)(CD)

1.消去

(A

B)(CD)

2.縮減作用范圍

(AB)(CD)

3.化公式為合取范式

(A(CD))(B(CD)) (AC)(AD)(BC)(BD)子句集: {AC,AD,BC,BD}謂詞公式轉(zhuǎn)換子句集舉例

(AB)(CD)

謂詞公式轉(zhuǎn)換子句集定義3：若P是原子謂詞公式，則P與乛P為互補(bǔ)文字定義4：設(shè)C1與C2是子句集中的任意兩個(gè)基子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么C1和C2中分別消去L1和L2，并將兩個(gè)子句余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱此過程為歸結(jié)，又稱消解（resolution）。稱C12為基子句C1和C2的歸結(jié)式。稱C1和C2為C12的親本子句。例3.9設(shè)C1=乛P∨Q∨R,C2=乛Q∨S,于是C1,C2的歸結(jié)式為乛P∨R∨S歸結(jié)（消解）定義定義3：若P是原子謂詞公式，則P與乛P為互補(bǔ)文字定義4：設(shè)C子句集的特點(diǎn)由謂詞公式轉(zhuǎn)化為子句集的過程中可以看出，在子句集中子句之間是合取關(guān)系。其中只要有一個(gè)子句不可滿足(真值為假），則子句集就不可滿足。若一個(gè)子句集中包含空子句，則這個(gè)子句集一定是不可滿足的。子句集的特點(diǎn)由歸結(jié)原理可知：如果兩個(gè)互否的單元子句進(jìn)行歸結(jié)，則歸結(jié)式為空子句即:

L

?L=□同時(shí)，L

?L=F(假）因此□F因此，可以通過推導(dǎo)空子句來做間接證明。

一旦推出了空子句，就說明子句集S是不可滿足的由歸結(jié)原理可知：因此，可以通過推導(dǎo)空子句來做間接證明。歸結(jié)反演證明步驟第一步：化子句集（1）將定理證明的前提謂詞公式轉(zhuǎn)換為子句集F(2)將要求證明的目標(biāo)表示成謂詞公式G(目標(biāo)公式）（3）將目標(biāo)公式的否定式乛G轉(zhuǎn)化成子句的形式，并加入到子句集F,得到子句集S。第二步：歸結(jié)反演應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)的歸結(jié)式都并入到S中。如此反復(fù)進(jìn)行，若歸結(jié)得到一個(gè)空子句NIL，則停止歸結(jié)，此時(shí)證明了G為真。歸結(jié)反演證明步驟第一步：化子句集歸結(jié)原理證明定理思路

用歸結(jié)原理證明定理有些類似于“反證法”的思想。反證法：首先假定要證明的結(jié)論不成立然后通過推導(dǎo)出與已知條件存在矛盾反證出結(jié)論成立。

歸結(jié)法：首先對(duì)結(jié)論求反，然后將已知條件和結(jié)論的否定合在一起用子句集表達(dá)。如果該子句集存在矛盾，則證明了結(jié)論的正確性。歸結(jié)原理證明定理思路用歸結(jié)原理證明定理有些類2．命題邏輯的歸結(jié)

命題邏輯，簡(jiǎn)單的說，就是不含有變量的邏輯。

歸結(jié)式：對(duì)任意兩個(gè)子句C1和C2，若C1中有一個(gè)文字L1，而C2中有一個(gè)與L1成互補(bǔ)的文字L2，則分別從C1、C2中刪去L1和L2，并將其剩余部分組成新的析取式C12，則稱這個(gè)新子句為歸結(jié)式或預(yù)解式。2．命題邏輯的歸結(jié)命題邏輯，簡(jiǎn)單的說，就是不含有變量命題邏輯的歸結(jié)過程

命題邏輯中，若給定公理集F和命題P，則歸結(jié)證明過程可歸納如下：

①把F轉(zhuǎn)化成子句集表示，得子句集S0；

②把命題P的否定式~P也轉(zhuǎn)化成子句集表示，并將其加到S0中，得S＝S0∪{S~p}；

③對(duì)子句集S反復(fù)應(yīng)用歸結(jié)推理規(guī)則，直至導(dǎo)出含有空子句的擴(kuò)大子句集為止。即出現(xiàn)歸結(jié)式為空子句的情況時(shí)，表明已找到了矛盾，證明過程結(jié)束。

命題邏輯的歸結(jié)過程命題邏輯中，若給定公理集F和命題P，則例證明子句集{P∨乛Q,乛P,Q}是不可滿足的。證(1)P∨乛Q(2)乛P(3)Q(4)乛Q由(1),(2)(5)□由(3),(4)基于命題邏輯的歸結(jié)舉例例證明子句集{P∨乛Q,乛P,Q}是不可滿足的?；诿}P∨乛Q乛P乛QQ□P∨乛Q乛P乛QQ□

例用歸結(jié)原理證明R是

P,(P∧Q)→R,(S∨U)→Q,U的邏輯結(jié)果。證明步驟第一步將問題轉(zhuǎn)換為子句集。我們先把諸前提條件化為子句形式，再把結(jié)論R的非乛R也化為子句，由所有子句得到子句集S例用歸結(jié)原理證明R是將P,(P∧Q)→R,(S∨U)→Q,U化為子句集形式：(P∧Q)→R乛(P∧Q)∨R(乛P∨乛Q)∨R乛P∨乛Q∨R(S∨U)→Q(1)乛(S∨U)∨Q(2)(乛S∧乛U)∨Q(3)(乛S∨Q)∧(乛U∨Q)子句集：{P,乛P∨乛Q∨R,乛S∨Q,乛U∨Q,U,乛R}將P,(P∧Q)→R,(S∨U)→Q,U化為子第二步：然后對(duì)該子句集S進(jìn)行歸結(jié)。如果從子句集S最后歸結(jié)出空子句，則子句集S不可滿足，從而間接證明R是真。第二步：然后對(duì)該子句集S進(jìn)行歸結(jié)。P乛P∨乛Q∨R乛S∨Q乛U∨QU乛R乛P∨乛Q(2)和（6）乛Q(1)和（7）乛U(4)和(8)□(5)和(9)子句集P子句集圖3―1例3.12歸結(jié)演繹樹圖3―1例3.12歸結(jié)演繹樹

在一階謂詞邏輯中應(yīng)用消解原理，不像命題邏輯中那樣簡(jiǎn)單，因?yàn)橹^詞邏輯中謂詞具有常量、變量和函數(shù)等變?cè)拇嬖?，這就使尋找含互否文字的子句對(duì)的操作變得復(fù)雜。例如：

C1=P(x)∨Q(x)C2=乛P(a)∨R(y)

直接比較，似乎兩者中不含互否文字，但如果我們用a替換C1中的x，則得到

C1′=P(a)∨Q(a)C2′=乛P(a)∨R(y)于是根據(jù)命題邏輯中的消解原理，得C1′和C2′的消解式：

C3′=Q(a)∨R(y)謂詞邏輯的歸結(jié)在一階謂詞邏輯中應(yīng)用消解原理，不像命題邏輯中那樣合一（Unify）

在謂詞邏輯的歸結(jié)過程中，尋找項(xiàng)之間合適的變量置換使表達(dá)式一致是一個(gè)很重要的過程，這個(gè)過程稱為合一。

合一（Unify）在謂詞邏輯的歸結(jié)過程中，尋找項(xiàng)

定義6一個(gè)替換(Substitution)是形如

mgu=｛t1/x1,t2/x2,…,tn/xn｝的有限集合，其中t1,t2,…,tn是項(xiàng)，稱為替換的分子；

x1,x2,…,xn是互不相同的個(gè)體變?cè)Q為替換的分母；替換(Substitution)定義6一個(gè)替換(Substitution)是形如替C1=P(x)∨Q(x)C2=乛P(a)∨R(y)做替換：mgu={a/x}C1′=P(a)∨Q(a)C2′=乛P(a)∨R(y)于是根據(jù)命題邏輯中的消解原理，得C1′和C2′的消解式：

C3′=Q(a)∨R(y)C1=P(x)∨Q(x)例3.21求證G是A1和A2的邏輯結(jié)果。A1:x(P(x)→(Q(x)∧R(x)))A2:x(P(x)∧S(x))G:x(S(x)∧R(x))

證我們用反證法，即證明A1∧A2∧乛G不可滿足。首先求得子句集S：例3.21求證G是A1和A2的邏輯結(jié)果。(1)乛P(x)∨Q(x)(2)乛P(y)∨R(y)(3)P(a)(4)S(a)(5)乛S(z)∨乛R(z)(乛G)然后應(yīng)用消解原理，得(6)R(a)［(2),(3),mgu=｛a/y｝］(7)乛R(a)［(4),(5),mgu=｛a/z｝］(8)□［(6),(7)］所以S是不可滿足的，從而G是A1和A2的邏輯結(jié)果。

(A1)(A2)S(1)乛P(x)∨Q(x)(A1)(A2)S例設(shè)已知：(1)能閱讀者是識(shí)字的；(2)海豚不識(shí)字；(3)有些海豚是很聰明的。試證明：有些聰明并不能閱讀。證首先，定義如下謂詞：R(x)：x能閱讀。L(x)：x識(shí)字。I(x)：x是聰明的。D(x)：x是海豚。例設(shè)已知：然后把上述各語(yǔ)句翻譯為謂詞公式：(1)x(R(x)→L(x))(2)x(D(x)→乛L(x))已知條件(3)x(D(x)∧I(x))(4)x(I(x)∧乛R(x))需證結(jié)論然后把上述各語(yǔ)句翻譯為謂詞公式：求題設(shè)與結(jié)論否定的子句集，得(1)乛R(x)∨L(x)(2)乛D(y)∨乛L(y)(3)D(a)(4)I(a)(5)乛I(z)∨R(z)歸結(jié)得(6)R(a)(5)，(4)，{a/z}(7)L(a)(6)，(1)，{a/x}(8)乛D(a)(7),(2),{a/y}(9)□(8),(3)這個(gè)歸結(jié)過程的演繹樹如圖3―2所示。

求題設(shè)與結(jié)論否定的子句集，得

圖3-2例3.22歸結(jié)演繹樹圖3-2例3.22歸結(jié)演繹樹練習(xí)1證明子句集{P∨乛Q,乛P,Q}是不可滿足的。練習(xí)2某公司招聘工作人員，有A,B,C三人應(yīng)聘，經(jīng)面試后，公司表示如下想法：（1）三人中至少錄取一人（2）如果錄取A而不錄取B,則一定錄取C（3）如果錄取B,則一定錄取C試用歸結(jié)原理求證：公司一定錄取C-第四章推理技術(shù)-謂詞邏輯課件第一步：將問題用謂詞公式表示前提：（1）三人中至少錄取一人：A∨B∨C

（2）如果錄取A而不錄取B,則一定錄取C：

(A∧乛B)→C（3）如果錄取B,則一定錄取C

：B→C結(jié)論：公司一定錄取CC第一步：將問題用謂詞公式表示前提：（1）三人中至少錄取一人第二步：將謂詞公式轉(zhuǎn)化為子句集，并將結(jié)論的否定化為子句，也加入子句集（1）A∨B∨C（2）(A∧乛B)→C

乛(A∧乛B)∨C

乛A∨B∨C(3)B→C

乛B∨C(4)乛C子句集：{A∨B∨C，乛A∨B∨C，乛B∨C，乛C}第二步：將謂詞公式轉(zhuǎn)化為子句集，并將結(jié)論的否定化為子句，也加第三步證明子句集是不可滿足的（1）A∨B∨C（2）乛A∨B∨C(3)乛B∨C(4)乛C(5)B∨C由（1）（2）

(6)C由(5)(3)(7)□由（4）（6）第三步證明子句集是不可滿足的（1）A∨B∨C課堂練習(xí)問題1：設(shè)已知公理集為

P…（1）

（P∧Q）→R……（2）

（S∨T）→Q……（3）

T…（4）

求證R。

課堂練習(xí)問題1：設(shè)已知公理集為

P…（1）

（

由（1）有子句集{P}；

由（2）有：

（P∧Q）→R

＝>～(P∧Q)∨R

＝>(～P∨～Q∨R)

得子句集：{～P∨～Q∨R}

由（3）有：

(S∨T)→Q

＝>～(S∨T)∨Q

＝>(～S∧～T)∨Q

＝>(～S∨Q)∧(～T∨Q)

得子句集：{～S∨Q,～T∨Q}

由（4）有子句集：(T)。

由結(jié)論的否定得子句集：{～R}

將以上子句集并在一起有總的子句集：

{P，~P∨~Q∨R，~S∨Q，~T∨Q，T，~R}由（1）有子句集{P}；

由（2）有：

（P∧命題邏輯的歸結(jié)演繹樹命題邏輯的歸結(jié)演繹樹一個(gè)經(jīng)典的歸結(jié)問題例“快樂學(xué)生”問題假設(shè)：任何通過計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎(jiǎng)。求證：張是快樂的。解：先定義謂詞：

Pass(x,y)x可以通過y考試

Win(x,prize)x能獲得獎(jiǎng)勵(lì)

Study(x)x肯學(xué)習(xí)

Happy(x)x是快樂的

Lucky(x)x是幸運(yùn)的一個(gè)經(jīng)典的歸結(jié)問題例“快樂學(xué)生”問題再將問題用謂詞表示如下：“任何通過計(jì)算機(jī)考試并獎(jiǎng)的人都是快樂的”

(?x)(Pass(x,computer)∧Win(x,prize)→Happy(x))“任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有考試”

(?x)(?y)(Study(x)∨Lucky(x)→Pass(x,y))“張不肯學(xué)習(xí)但他是幸運(yùn)的”

﹁Study(zhang)∧Lucky(zhang)“任何幸運(yùn)的人都能獲獎(jiǎng)”

(?x)(Lucky(x)→Win(x,prize))

結(jié)論“張是快樂的”的否定

﹁Happy(zhang)再將問題用謂詞表示如下：將上述謂詞公式轉(zhuǎn)化為子句集如下：

(1)﹁Pass(x,computer)∨﹁Win(x,prize)∨Happy(x)(2)﹁Study(y)∨Pass(y,z)(3)﹁Lucky(u)∨Pass(u,v)(4)﹁Study(zhang)(5)Lucky(zhang)(6)﹁Lucky(w)∨Win(w,prize)(7)﹁Happy(zhang)(結(jié)論的否定)將上述謂詞公式轉(zhuǎn)化為子句集如下：

﹁Exciting(Liming)﹁Happy(z)∨Exciting(z)﹁Happy(Liming)Happy(x))∨﹁Smart(x)∨Happy(x)Poor(Liming)∨﹁Smart(Liming)﹁Read(y)∨Smart(y)Poor(Liming)∨﹁Read(Liming)﹁Poor(Liming)﹁Read(Liming)Read(Liming)NIL{Liming/z}{Liming/x}{Liming/y}﹁Exciting(Liming)﹁Happy(z)∨Ex歸結(jié)演繹推理的歸結(jié)策略

廣度優(yōu)先是一種窮盡子句比較的復(fù)雜搜索方法。設(shè)初始子句集為S0，廣度優(yōu)先策略的歸結(jié)過程可描述如下：

(1)從S0出發(fā)，對(duì)S0中的全部子句作所有可能的歸結(jié)，得到第一層歸結(jié)式，把這些歸結(jié)式的集合記為S1;(2)用S0中的子句與S1中的子句進(jìn)行所有可能的歸結(jié)，得到第二層歸結(jié)式，把這些歸結(jié)式的集合記為S2;(3)用S0和S1中的子句與S2中的子句進(jìn)行所有可能的歸結(jié)，得到第三層歸結(jié)式，把這些歸結(jié)式的集合記為S3;

如此繼續(xù)，知道得出空子句或不能再繼續(xù)歸結(jié)為止。例設(shè)有如下子句集：

S={﹁I(x)∨R(x),I(a),﹁R(y)∨L(y),﹁L(a)}用寬度優(yōu)先策略證明S為不可滿足。寬度優(yōu)先策略的歸結(jié)樹如下：歸結(jié)演繹推理的歸結(jié)策略廣度優(yōu)先是一種窮盡子句比較的

歸結(jié)演繹推理的歸結(jié)策略

1.廣度優(yōu)先策略（2/3）﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁I(x)∨L(x)﹁R(a)L(a)L(a)﹁I(a)﹁I(a)NILSS1S2歸結(jié)演繹推理的歸結(jié)策略

1.廣度優(yōu)先策略（2/3）﹁I(歸結(jié)演繹推理的歸結(jié)策略

1.廣度優(yōu)先策略（3/3）

從這個(gè)例子可以看出，寬度優(yōu)先策略歸結(jié)出了許多無用的子句，既浪費(fèi)事間，又浪費(fèi)空間。但是，這種策略由一個(gè)有趣的特性，就是當(dāng)問題有解時(shí)保證能找到最短歸結(jié)路徑。因此，它是一種完備的歸結(jié)策略。寬度優(yōu)先對(duì)大問題的歸結(jié)容易產(chǎn)生組合爆炸，但對(duì)小問題卻仍是一種比較好的歸結(jié)策略。歸結(jié)演繹推理的歸結(jié)策略

1.廣度優(yōu)先策略（3/3）歸結(jié)演繹推理的歸結(jié)策略

2.支持集策略（1/3）

支持集策略是沃斯(Wos)等人在1965年提出的一種歸結(jié)策略。它要求每一次參加歸結(jié)的兩個(gè)親本子句中，至少應(yīng)該有一個(gè)是由目標(biāo)公式的否定所得到的子句或它們的后裔?？梢宰C明支持集策略是完備的，即當(dāng)子句集為不可滿足時(shí)，則由支持集策略一定能夠歸結(jié)出一個(gè)空子句。也可以把支持集策略看成是在寬度優(yōu)先策略中引入了某種限制條件，這種限制條件代表一種啟發(fā)信息，因而有較高的效率

例設(shè)有如下子句集：

S={﹁I(x)∨R(x),I(a),﹁R(y)∨L(y),﹁L(a)}其中，﹁I(x)∨R(x)為目標(biāo)公式的否定。用支持集策略證明S為不可滿足。歸結(jié)演繹推理的歸結(jié)策略

2.支持集策略（1/3）歸結(jié)演繹推理的歸結(jié)策略

2.支持集策略（2/3）﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁I(x)∨L(x)L(a)L(a)﹁I(a)NIL歸結(jié)演繹推理的歸結(jié)策略

2.支持集策略（2/3）﹁I(x)歸結(jié)演繹推理的歸結(jié)策略

2.支持集策略（3/3）

從上述歸結(jié)過程可以看出，各級(jí)歸結(jié)式數(shù)目要比寬度優(yōu)先策略生成的少，但在第二級(jí)還沒有空子句。就是說這種策略限制了子句集元素的劇增，但會(huì)增加空子句所在的深度。此外，支持集策略具有逆向推理的含義，由于進(jìn)行歸結(jié)的親本子句中至少有一個(gè)與目標(biāo)子句有關(guān)，因此推理過程可以看作是沿目標(biāo)、子目標(biāo)的方向前進(jìn)的。

歸結(jié)演繹推理的歸結(jié)策略

2.支持集策略（3/3）歸結(jié)演繹推理的歸結(jié)策略

3.刪除策略（2/2）重言式刪除法如果一個(gè)子句中包含有互補(bǔ)的文字對(duì)，則稱該子句為重言式。例如

P(x)∨﹁P(x),P(x)∨Q(x)∨﹁P(x)都是重言式，不管P(x)的真值為真還是為假，P(x)∨﹁P(x)和P(x)∨Q(x)∨﹁P(x)都均為真。重言式是真值為真的子句。對(duì)一個(gè)子句集來說，不管是增加還是刪除一個(gè)真值為真的子句，都不會(huì)影響該子句集的不可滿足性。因此，可從子句集中刪去重言式。歸結(jié)演繹推理的歸結(jié)策略

3.刪除策略（2/2）重言式刪除法歸結(jié)演繹推理的歸結(jié)策略

4.單文字子句策略（1/2）

如果一個(gè)子句只包含一個(gè)文字，則稱此子句為單文字子句。單文字子句策略是對(duì)支持集策略的進(jìn)一步改進(jìn)，它要求每次參加歸結(jié)的兩個(gè)親本子句中至少有一個(gè)子句是單文字子句。例設(shè)有如下子句集：

S={﹁I(x)∨R(x),I(a),﹁R(y)∨L(y),﹁L(a)}用單文字子句策略證明S為不可滿足。采用單文字子句策略，歸結(jié)式包含的文字?jǐn)?shù)將少于其親本子句中的文字?jǐn)?shù)，這將有利于向空子句的方向發(fā)展，因此會(huì)有較高的歸結(jié)效率。但這種策略是不完備的，即當(dāng)子句集為不可滿足時(shí)，用這種策略不一定能歸結(jié)出空子句。歸結(jié)演繹推理的歸結(jié)策略

4.單文字子句策略（1/2）歸結(jié)演繹推理的歸結(jié)策略

4.單文字子句策略（2/2）﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁R(a)NIL歸結(jié)演繹推理的歸結(jié)策略

4.單文字子句策略（2/2）﹁I(歸結(jié)演繹推理的歸結(jié)策略

5.線形輸入策略（1/2）

這種策略要求每次參加歸結(jié)的兩個(gè)親本子句中，至少應(yīng)該有一個(gè)是初始子句集中的子句。所謂初始子句集是指開始?xì)w結(jié)時(shí)所使用的子句集。

例設(shè)有如下子句集：

S={﹁I(x)∨R(x),I(a),﹁R(y)∨L(y),﹁L(a)}用線性輸入策略證明S為不可滿足。線性輸入策略可限制生成歸結(jié)式的數(shù)目，具有簡(jiǎn)單和高效的優(yōu)點(diǎn)。但是，這種策略也是一種不完備的策略。例如，子句集

S={Q(u)∨P(a),﹁Q(w)∨P(w),﹁Q(x)∨﹁P(x),Q(y)∨﹁P(y)}

從S出發(fā)很容易找到一棵歸結(jié)反演樹，但卻不存在線性輸入策略的歸結(jié)反演樹。

歸結(jié)演繹推理的歸結(jié)策略

5.線形輸入策略（1/2）歸結(jié)演繹推理的歸結(jié)策略

5.線形輸入策略（2/2）﹁I(x)∨R(x)I(a)﹁R(y)∨L(y)﹁L(a)R(a)﹁I(x)∨L(x)﹁R(a)﹁I(a)L(a)L(a)﹁I(a)NIL歸結(jié)演繹推理的歸結(jié)策略

5.線形輸入策略（2/2）﹁I(x歸結(jié)演繹推理的歸結(jié)策略

6.祖先過濾策略（1/2）

這種策略與線性輸入策略有點(diǎn)相似，但是，放寬了對(duì)子句的限制。每次參加歸結(jié)的兩個(gè)親本子句，只要滿足以下兩個(gè)條件中的任意一個(gè)就可進(jìn)行歸結(jié)：

(1)兩個(gè)親本子句中至少有一個(gè)是初始子句集中的子句。

(2)如果兩個(gè)親本子句都不是初始子句集中的子句，則一個(gè)子句應(yīng)該是另一個(gè)子句的先輩子句。所謂一個(gè)子句(例如C1)是另一個(gè)子句(例如C2)的先輩子句是指C2是由C1與別的子句歸結(jié)后得到的歸結(jié)式。

例設(shè)有如下子句集：

S={﹁Q(x)∨﹁P(x),Q(y)∨﹁P(y)，﹁Q(w)∨P(w),Q(a)∨P(a)}用祖先過濾策略證明S為不可滿足。

可以證明祖先過濾策略也是完備的。上面分別討論了幾種基本的歸結(jié)策略，但在實(shí)際應(yīng)用中，還可以把幾種策略結(jié)合起來使用?？傊谶x擇歸結(jié)反演策略時(shí)，主要應(yīng)考慮其完備性和效率問題。歸結(jié)演繹推理的歸結(jié)策略

6.祖先過濾策略（1/2）歸結(jié)演繹推理的歸結(jié)策略

6.祖先過濾策略（2/2）﹁Q(x)∨﹁P(x)Q(y)∨﹁P(y)﹁P(x)﹁Q(w)∨P(w)﹁Q(w)Q(a)∨P(a)P(a)NIL歸結(jié)演繹推理的歸結(jié)策略

6.祖先過濾策略（2/2）﹁Q(x

作業(yè)1判斷以下子句是否為不可滿足

{P(x)∨Q(x)∨R(x),﹁P(y)∨R(y),﹁Q(a),﹁R(b)}

2證明G是F的邏輯結(jié)論

F:(?x)(?y)(P(f(x))∧(Q(f(y)))G:P(f(a))∧P(y)∧Q(y)3公司招聘工作人員，有M,N,Q三人應(yīng)聘，經(jīng)面試后，公司表示如下想法：（1）三人中至少錄取一人;（2）如果錄取M,則一定錄取N；（3）如果錄取N,則一定錄取Q。試用歸結(jié)反演方法求證：公司一定錄取Q。4設(shè)謂詞S(p,q)表示“p為q刮胡子”。假設(shè)論域?yàn)槿恕＃?)請(qǐng)用謂詞語(yǔ)句描述“有一個(gè)人P只為每個(gè)不給自己刮胡子的人刮胡子”。（2）將（1）中語(yǔ)句轉(zhuǎn)換為子句形式。（3）用歸結(jié)法證明（2）本身不一致（或不可滿足)。作業(yè)1判斷以下子句是否為不可滿足第四章推理技術(shù)

4.1一階謂詞邏輯推理4.2歸結(jié)演繹推理第四章推理技術(shù)4.1一階謂詞邏輯推理推理技術(shù)概述推理是人類求解問題的主要思維方法，即按照某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過程。按思維方式可分演繹推理、歸納推理、類比推理等。邏輯推理：按邏輯規(guī)則進(jìn)行的推理。分為：

經(jīng)典邏輯推理

:主要指命題邏輯和一階謂詞邏輯推理，也稱精確推理或確定性推理；

非經(jīng)典邏輯推理：主要指除經(jīng)典邏輯之外，按多值邏輯、模糊邏輯、概率邏輯等的推理，也稱為非精確推理或非確定性推理。推理技術(shù)概述推理是人類求解問題的主要思維方法，即按照某種策略邏輯推理舉例

經(jīng)典推理：蘇格拉底之死

如何判別謊言？

ABC三人都喜歡說謊話，偶爾也說真話。某天，A指責(zé)B說謊話，B指責(zé)C說謊話，C說AB兩人都在說謊話。問誰(shuí)在說謊？

邏輯推理舉例有幾條瘋狗？

村里有50戶人家，每家都養(yǎng)了一條狗。現(xiàn)發(fā)現(xiàn)村子里面出現(xiàn)了n只瘋狗，村里規(guī)定，誰(shuí)要是發(fā)現(xiàn)了自己的狗是瘋狗，就要將自己的狗槍斃。但問題是，村子里面的人只能看出別人家的狗是不是瘋狗，而不能看出自己的狗是不是瘋的，如果看出別人家的狗是瘋狗，也不能告訴別人。于是大家開始觀察，第一天晚上，沒有槍聲，第二天晚上，沒有槍聲，第三天晚上，槍聲響起（具體幾槍不清楚），問村子里有幾只瘋狗？只有晚上才能看出病狗，并且一天晚上只能看一次。有幾條瘋狗？村里有50戶人家，每愛因斯坦的世界難題（1）愛因斯坦在20世紀(jì)初出一個(gè)謎語(yǔ)。他說世界上有98％的人答不出來。1、在一條街上，有5座房子，噴了5種顏色；2、每個(gè)房里住著不同國(guó)籍的人；3、每個(gè)人喝不同的飲料，抽不同品牌的香煙，養(yǎng)不同的寵物。

問題是：誰(shuí)養(yǎng)魚？

愛因斯坦的世界難題（1）愛因斯坦在20世紀(jì)初出一個(gè)謎語(yǔ)。他說愛因斯坦的世界難題（2）條件是：1、英國(guó)人住紅色房子； 2、瑞典人養(yǎng)狗；3、丹麥人喝茶； 4、綠色房子在白色房子左面；5、綠色房子主人喝咖啡；6、抽PallMall香煙的人養(yǎng)鳥；7、黃色房子主人抽Dunhill香煙；8、住在中間房子的人喝牛奶；9、挪威人住第一間房； 10、抽Blends香煙的人住在養(yǎng)貓的人隔壁11、養(yǎng)馬的人住抽Dunhill香煙的人隔壁；12、抽BlueMaster的人喝??；13、德國(guó)人抽Prince香煙； 14、挪威人住藍(lán)色房子隔壁；15、抽Blends香煙的人有一個(gè)喝水的鄰居。愛因斯坦的世界難題（2）條件是：邏輯學(xué)與計(jì)算機(jī)科學(xué)邏輯學(xué)：研究思維規(guī)律的科學(xué)計(jì)算機(jī)科學(xué)：模擬人腦行為和功能（思維）的科學(xué)思維：大腦、邏輯、語(yǔ)言、計(jì)算機(jī)邏輯是知識(shí)表示和推理的重要形式和工具邏輯學(xué)與計(jì)算機(jī)科學(xué)邏輯學(xué)：研究思維規(guī)律的科學(xué)97邏輯的歷史Aristotle——邏輯學(xué)Leibnitz——數(shù)理邏輯：邏輯+數(shù)學(xué)GottlobFrege(1848-1925)——一階謂詞演算系統(tǒng)邏輯是探索、闡述和確立有效推理原則的學(xué)科，最早由古希臘學(xué)者亞里士多德創(chuàng)建的。用數(shù)學(xué)的方法研究關(guān)于推理、證明等問題的學(xué)科就叫做數(shù)理邏輯。也叫做符號(hào)邏輯。20世紀(jì)30年代，數(shù)理邏輯廣泛發(fā)展，成為數(shù)學(xué)和計(jì)算機(jī)科學(xué)基礎(chǔ)。8邏輯的歷史Aristotle——邏輯學(xué)邏輯系統(tǒng)一個(gè)邏輯系統(tǒng)是定義語(yǔ)言和它的含義的方法。邏輯系統(tǒng)中的一個(gè)邏輯理論是該邏輯的語(yǔ)言的一個(gè)語(yǔ)句集合，它包括：邏輯符號(hào)集合：在所有該邏輯的邏輯理論中均出現(xiàn)的符號(hào)；非邏輯符號(hào)集合：不同的邏輯理論中出現(xiàn)的不同的符號(hào)；語(yǔ)句規(guī)則：定義什么樣的符號(hào)串是有意義的；證明：什么樣的符號(hào)串是一個(gè)合理的證明；語(yǔ)義規(guī)則：定義符號(hào)串的語(yǔ)義。邏輯系統(tǒng)一個(gè)邏輯系統(tǒng)是定義語(yǔ)言和它的含義的方法。邏輯程序語(yǔ)言邏輯符號(hào)保留字或者符號(hào)非邏輯符號(hào)用戶自定義的符號(hào)(變量名，函數(shù)名等)語(yǔ)句規(guī)則構(gòu)造一個(gè)程序的語(yǔ)句規(guī)則語(yǔ)義規(guī)則定義程序做什么的語(yǔ)句規(guī)則推理規(guī)則、公理和證明沒有邏輯與程序語(yǔ)言的對(duì)比邏輯程序語(yǔ)言邏輯符號(hào)保留字或者符號(hào)非邏輯符號(hào)用戶自定義的符號(hào)1.3命題邏輯命題：可以確定其真假的陳述句。Bolle提出了布爾代數(shù)。語(yǔ)言:原子Q、否定?、吸取V、合取、蘊(yùn)含、等價(jià)<->公式：AV?B，(AB,A)=>?

1.3命題邏輯命題：可以確定其真假的陳述句。Bolle提出-第四章推理技術(shù)-謂詞邏輯課件-第四章推理技術(shù)-謂詞邏輯課件

公司招聘工作人員，有M,N,Q三人應(yīng)聘，經(jīng)面試后，公司表示如下想法：（1）三人中至少錄取一人;（2）如果錄取M,則一定錄取N；（3）如果錄取N,則一定錄取Q。結(jié)果如何？公司招聘工作人員，有M,N,Q三人應(yīng)聘，經(jīng)面試1.4謂詞邏輯(一階邏輯)謂詞邏輯是一種形式語(yǔ)言，具有嚴(yán)密的理論體系，也是一種常用的知識(shí)表示方法。語(yǔ)言:

?，，，，(，)；常元，變?cè)?，函詞，謂詞；公式City（北京）City（上海）Age（張三，23）(x)(y)(z)(F(x,y)F(y,z)GF(x,z)）1.4謂詞邏輯(一階邏輯)謂詞邏輯是一種形式語(yǔ)言，具有嚴(yán)密謂詞邏輯中的形式演繹推理將自然語(yǔ)言中的陳述語(yǔ)句利用謂詞公式表示利用邏輯等價(jià)式將謂詞公式進(jìn)行變換利用邏輯蘊(yùn)含式推出結(jié)論符號(hào)化過程公式變形推理過程謂詞邏輯中的形式演繹推理將自然語(yǔ)言中的陳述語(yǔ)句利用邏輯等價(jià)式表4.1常用邏輯等價(jià)式表4.1常用邏輯等價(jià)式-第四章推理技術(shù)-謂詞邏輯課件-第四章推理技術(shù)-謂詞邏輯課件-第四章推理技術(shù)-謂詞邏輯課件表4.2常用邏輯蘊(yùn)含式表4.2常用邏輯蘊(yùn)含式-第四章推理技術(shù)-謂詞邏輯課件

設(shè)有前提：

(1)凡是大學(xué)生都學(xué)過計(jì)算機(jī)；

(2)小王是大學(xué)生。試問：小王學(xué)過計(jì)算機(jī)嗎？解令S(x)：x是大學(xué)生;M(x)：x學(xué)過計(jì)算機(jī);a：小王。則上面的兩個(gè)命題可用謂詞公式表示為

(1)x(S(x)→M(x))(2)S(a)例設(shè)有前提：例

下面我們進(jìn)行形式推理：

(1)x(S(x)→M(x))［前提］

(2)S(a)→M(a)［(1),US］

(3)S(a)［前提］

(4)M(a)［(2),(3),I3］得結(jié)果：M(a)，即“小王學(xué)過計(jì)算機(jī)”。

這種推理過程完全是一種符號(hào)變換過程，很類似于人們用自然語(yǔ)言推理的思維過程，因而稱為自然演繹推理下面我們進(jìn)行形式推理：這種推理過程完全是一種符號(hào)變換過程

在語(yǔ)法上，如果存在一個(gè)從假設(shè)到的證明，則記為

?，稱由可推導(dǎo)出的，或可證明的。如果在沒有任何假設(shè)下是可推導(dǎo)出的，則記為?，稱為可證明的。稱一個(gè)假設(shè)是不協(xié)調(diào)的，如果存在一個(gè)語(yǔ)句使得和的否定均可由推導(dǎo)得出。稱一個(gè)邏輯系統(tǒng)是一致的，或相容的(consistent)，如果不存在邏輯系統(tǒng)的公式A，使得?A與??A同時(shí)成立。證明(語(yǔ)法)在語(yǔ)法上，如果存在一個(gè)從假設(shè)到的證明，證

語(yǔ)言的解釋是在某個(gè)論域(domain)中定義非邏輯符號(hào)。語(yǔ)句的語(yǔ)義是在解釋下定義出語(yǔ)言L的真假值。如果I是L的一個(gè)解釋，且在I中為真，則記為I

?

，稱作I滿足，或者I是的一個(gè)模型。類似地，給定一個(gè)語(yǔ)句和一個(gè)語(yǔ)句，如果對(duì)每個(gè)解釋I

，有I

?

蘊(yùn)含I

?

，換言之，如果I是的一個(gè)模型則I也是的一個(gè)模型，則記為

?，我們稱為的一個(gè)邏輯結(jié)果。解釋(語(yǔ)義)語(yǔ)言的解釋是在某個(gè)論域(domain)中定義非邏輯解可靠性(reliable)語(yǔ)法->語(yǔ)義一個(gè)邏輯是可靠的，如果它的證明保持真假值，即在任何解釋I下，如果I是的模型，且可由推導(dǎo)出，則I也是的一個(gè)模型。即，一個(gè)邏輯是可靠的，如果對(duì)任何語(yǔ)句集合和語(yǔ)句，

?蘊(yùn)涵

?。可靠性和完備性完備性(complete)語(yǔ)義->語(yǔ)法一個(gè)邏輯是完備的，如果任何永真語(yǔ)句是可證的。即，對(duì)任何語(yǔ)句集合和語(yǔ)句，

?蘊(yùn)涵

?。如果一個(gè)邏輯是完備的，則該邏輯的證明系統(tǒng)已強(qiáng)到可以推出任何永真式。G?del完備性定理：一階邏輯是完備的可靠性(reliable)語(yǔ)法->語(yǔ)義可靠性和完備性可判定的一個(gè)邏輯稱為是可判定的(decidable)，如果存在一個(gè)算法對(duì)邏輯中的任一公式A，可確定?

A是否成立。否則，稱為是不可判定的(undecidable)

。如果上述算法雖不一定存在，卻有一個(gè)過程，可對(duì)該系統(tǒng)的定理做出肯定的判斷，但對(duì)非定理的公式過程未必終止，因而未必能作出判斷。這時(shí)稱邏輯是半可判定的。可判定性一階邏輯是不可判定的，但它是半可判定的。可判定的可判定性一階邏輯是不可判定的，但它是半可判定的。

現(xiàn)代邏輯學(xué)與計(jì)算機(jī)科學(xué)、計(jì)算語(yǔ)言學(xué)和人工智能的關(guān)系表邏輯自然語(yǔ)程序人工邏輯指令與直數(shù)據(jù)庫(kù)復(fù)雜性智能體未來展望言處理控制智能編程陳式語(yǔ)言理論理論理論時(shí)序邏輯√√√√√√√√廣泛應(yīng)用模態(tài)邏輯√√√√√√√√非?；钴S算法證明√√√√√√√√非單調(diào)推理√√√√√√√意義重大概率和模糊√√√√√√√目前主流直覺主義邏輯√√√√√√√√主要替代者高階邏輯，λ-演算√√√√√√更具中心作用經(jīng)典邏輯片斷√√√√√√前景誘人資源和子結(jié)構(gòu)邏輯√√√√纖維化和組合邏輯√√√√√√可自我指稱謬誤理論在適當(dāng)語(yǔ)境邏輯動(dòng)力學(xué)√√動(dòng)態(tài)邏輯觀論辯理論游戲√前景光明對(duì)象層次/元層次√√總起中心作用機(jī)制:溯因缺省相干√√邏輯的一部分與神經(jīng)網(wǎng)絡(luò)的聯(lián)系極重要，剛開始時(shí)間-行動(dòng)-修正模型√√一類新模型加標(biāo)演繹系統(tǒng)√√√√√邏輯學(xué)的統(tǒng)一框架

4.2歸結(jié)演繹推理

歸結(jié)演繹推理是基于一種稱為歸結(jié)原理(亦稱消解原理

principleofresolution)的推理規(guī)則的推理方法。歸結(jié)原理是由魯濱遜(J.A.Robinson)于1965年首先提出。它是謂詞邏輯的一個(gè)相當(dāng)有效的機(jī)械化推理方法。歸結(jié)原理的出現(xiàn)，被認(rèn)為是自動(dòng)推理，特別是定理機(jī)器證明領(lǐng)域的重大突破。從理論上解決了定理證明問題。

4.2歸結(jié)演繹推理

歸結(jié)演繹推理是基于一種稱有關(guān)歸結(jié)演繹推理的定義文字子句空子句子句集Skolem函數(shù)Skolem常量互補(bǔ)文字歸結(jié)，又稱消解(resolution)有關(guān)歸結(jié)演繹推理的定義文字

定義1原子謂詞公式及其否定稱為文字，若干個(gè)文字的一個(gè)析取式稱為一個(gè)子句不含任何文字的子句稱為空子句（真值為假），記為NIL。

例如下面的析取式都是子句

P∨Q∨乛RP(x,y)∨乛Q(x)定義1原子謂詞公式及其否定稱為文字，

定義2對(duì)一個(gè)謂詞公式G，通過以下步驟所得的子句集合S，稱為G的子句集。

(1)消去蘊(yùn)含詞→和等值詞←→?？墒褂眠壿嫷葍r(jià)式:①A→B乛A∨B②A←→B(乛A∨B)∧(乛B∨A)(2)縮小否定詞的作用范圍，直到其僅作用于原子公式?？墒褂眠壿嫷葍r(jià)式:①乛(乛A)A②乛(A∧B)乛A∨乛B將一個(gè)謂詞公式轉(zhuǎn)換為子句集定義2對(duì)一個(gè)謂詞公式G，通過以下步③乛(A∨B)乛A∧乛B④乛xP(x)x乛P(x)⑤乛xP(x)x乛P(x)(3)適當(dāng)改名，使量詞間不含同名自由變?cè)图s束變?cè)?/p>

(4)消去存在量詞。消去存在量詞時(shí)，同時(shí)還要進(jìn)行變?cè)鎿Q。變?cè)鎿Q分兩種情況：①若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的函數(shù)稱為Skolem函數(shù)；

②若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的常量符號(hào)稱為Skolem常量。③乛(A∨B)乛A∧乛B②若該存在量詞不在任何全稱xyP(x,y)根據(jù)步驟4轉(zhuǎn)換