又稱之為謂詞合式公式-合肥工業(yè)大學(xué)

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室1/113高級(jí)人工智能邏輯、推理與知識(shí)

王浩2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室1/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室2/117命題邏輯一階邏輯(一階謂詞演算）其他邏輯系統(tǒng)約束推理定性推理基于范例的推理知識(shí)及其表示2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室2/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室3/117命題邏輯什么是邏輯？簡(jiǎn)單地說(shuō)，邏輯就是人們用以處理問(wèn)題而抽象的一種思維規(guī)則或計(jì)算方法。命題邏輯的關(guān)系表達(dá)直觀、生動(dòng)而簡(jiǎn)潔，它是一階邏輯發(fā)展的前導(dǎo)和基礎(chǔ)。把命題邏輯加以簡(jiǎn)單的形式化，就能擴(kuò)展應(yīng)用于一階邏輯推理中。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室3/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室4/117命題邏輯1.命題和個(gè)體

設(shè)有如下符號(hào)命名的語(yǔ)句：

①X：愛因斯坦是一位偉人。②Y：海水是甜的。③W：3+4=9上述X、Y、Z都是陳述性語(yǔ)句，分別具有肯定(True)或否定(False)意義的真值，我們把它們都稱之為命題。其中，諸如“愛因斯坦”，“海水”，數(shù)字“3”、“4”等，它們是命題中的行為中心對(duì)象，又稱為個(gè)體。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室4/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室5/117命題邏輯

定義3.1

命題(Proposition)，即具有真(T)假(F)意義的陳述性語(yǔ)句。注意：

⑴命題一定是陳述性語(yǔ)句；如上述X、Y、W等。例如，下面句子是陳述性語(yǔ)句嗎？①請(qǐng)勿吸煙。②昨晚你看足球聯(lián)賽了嗎？③西湖好美呵?、泼}既可用自然語(yǔ)言(包括中、外文)形式表示，也可用大寫的英文字符或字符串來(lái)命名。⑶命題反映了人腦進(jìn)行思維的一種判斷，可見命題表達(dá)自身就含有智能特性。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室5/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室6/117命題邏輯（1）個(gè)體是命題中的中心對(duì)象，通常由名詞構(gòu)成。個(gè)體可以是具體的人物、物體、一組數(shù)字、地名等，也可以是某個(gè)抽象的概念。例如，機(jī)器人、海棠花、理想、快樂(lè)、智能等均可作為個(gè)體。（2）個(gè)體的取值范圍稱為個(gè)體域。個(gè)體域可以是有限的，也可以是無(wú)限的。定義3.2

所謂個(gè)體，是指可以獨(dú)立存在的某個(gè)事物。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室6/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室7/117命題邏輯2.謂詞及變?cè)?/p>

為了對(duì)許多具有進(jìn)步影響人物都使用形同X命題方式贊揚(yáng)之，可使用一種類同數(shù)學(xué)函數(shù)的形式語(yǔ)言——用含有變量字符或字符串的謂詞來(lái)定義：表達(dá)為英文字符串形式：

GIANT(x).其被賦予的漢語(yǔ)解釋是：

x是一位偉人。

把GIANT(x)稱為謂詞（Predicate），其中GIANT()是謂詞名；括號(hào)中的參量x叫做謂詞的變?cè)?，又稱之為項(xiàng)(item)。GIANT(?)

謂詞名謂詞變?cè)?024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室7/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室8/117命題邏輯

這種由定義的謂詞名、變?cè)?，共同?gòu)成了具有陳述性表達(dá)的形式化語(yǔ)句，稱為謂詞。一個(gè)謂詞可以有n（其中n=0,1,2,……）個(gè)變?cè)?，并稱之為n元謂詞。在謂詞中，謂詞名表達(dá)了語(yǔ)句中除主語(yǔ)個(gè)體之外的其余部分，常采用自然語(yǔ)言的謂語(yǔ)動(dòng)作詞根來(lái)表達(dá)；謂詞的變?cè)稍谙鄳?yīng)個(gè)體域集合中取值任意一個(gè)元素。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室8/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室9/117命題邏輯例3.1

假如定義英文字符串“OCITY(x)

”

設(shè)其含意為：x是一座歷史名城。

解：這里x可以取值“西安”——

真值為T；x取值“深圳”真值為F。若取值“北京”則為T、“華盛頓”——T、“野玫瑰”——F、“機(jī)器人”為F等。由上例可見，當(dāng)使用特定的個(gè)體常量取代了謂詞中的變?cè)?，該謂詞就轉(zhuǎn)換成為一個(gè)命題；反之，如果把命題中有獨(dú)立結(jié)構(gòu)的個(gè)體常量替換成變?cè)獏⒘?，則又可把命題轉(zhuǎn)換成為一個(gè)具有謂詞結(jié)構(gòu)的表達(dá)式了。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室9/112024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室10/117命題邏輯3.謂詞的元和謂詞的階

定義3.3

謂詞中包含個(gè)體或變?cè)臄?shù)目，稱為謂詞的元或謂詞的目。例3.2

比較下列謂詞或謂詞形式的命題：①LIKE(john，mary)；②ROBOT(john)；③ROBOT(mary)；

④ADDQ(x，y，z)。試解釋具體含義，并指出它們各是幾元謂詞。解：上述謂詞①②③意即“機(jī)器人約翰喜歡瑪麗”；②和③都只有一個(gè)個(gè)體，稱為一元謂詞；相應(yīng)①則稱為二元謂詞；④表示為表達(dá)式“x+y=z”，其中包含有3個(gè)變?cè)?，故稱為三元謂詞。依此類推，可推出關(guān)于n元謂詞的概念。

順便指出：在多元謂詞中，變?cè)呐判蚝苤匾?，一旦確定，就不可隨意交換。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室10/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室11/117命題邏輯定義3.4

謂詞表達(dá)形式中所包容相疊加的含義層次數(shù)數(shù)目，稱為謂詞的階。例2-3

為了說(shuō)明謂詞的階，我們來(lái)比較下列謂詞形式的命題：①LIFELESS(outer-stars)；外星球沒(méi)有智能生命。②INCORRECT(lifeless(outer-stars))；說(shuō)“外星球沒(méi)有智能生命”是不確切的。解：在上述謂詞形式的命題中，謂詞①只有一層含義，稱為一階謂詞；謂詞②在前一層含義基礎(chǔ)上，又增加了一層新意，共有二層含義。故把謂詞②稱為二階謂詞。依此類推，可推出關(guān)于n階謂詞的概念。注意：在謂詞邏輯演算中，最重要的有三大類：即：命題邏輯演算、一階謂詞邏輯演算和二階謂詞演算。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室11/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室12/117命題邏輯4.命題與謂詞邏輯的關(guān)系命題邏輯表示比較簡(jiǎn)單，只能表達(dá)具體固定的情況，命題是謂詞邏輯特殊事例的生動(dòng)描述，謂詞邏輯可以靈活表現(xiàn)多種或變化的情況；謂詞表達(dá)是命題邏輯的抽象與推廣?？偟目磥?lái)，命題和謂詞的知識(shí)表示形式可以相互轉(zhuǎn)換，而謂詞比命題有更強(qiáng)的表達(dá)能力。

顯而易見，謂詞是一種描述個(gè)體群之間的相互關(guān)系、性質(zhì)及其邏輯結(jié)構(gòu)的數(shù)學(xué)表示。人們把采用這種表示的運(yùn)算，又稱為謂詞邏輯。比較起來(lái)：命題邏輯演算太簡(jiǎn)單，只能解決具體容易的問(wèn)題；二階謂詞演算又太復(fù)雜，以至迄今為止，尚未找到最根本有效的算法。

因此，在人工智能中，目前使用最多的還是一階謂詞邏輯演算。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室12/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室13/117一階邏輯命題或謂詞邏輯推理演算，主要可利用連接詞和量詞，把單個(gè)的謂詞組合成為謂詞公式來(lái)完成?；诿}和謂詞邏輯可相互轉(zhuǎn)換的特性，這里約定：對(duì)命題和謂詞邏輯的相關(guān)公式表達(dá)、相關(guān)定理、定律的論證和推導(dǎo)等，不再加以嚴(yán)格區(qū)別。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室13/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室14/117一階邏輯1.連接詞(Connectives)

連接詞共有五個(gè)：⑴符號(hào)“?”稱為“否定”(Negation)或補(bǔ)，表示“非”的連接關(guān)系。即當(dāng)命題P為真時(shí)，則?P

為假；反之，當(dāng)命題P為假，則?P

為真。⑵符號(hào)“∧”稱為“合取”(Conjunction)，表示“與”(AND)或“同時(shí)”的關(guān)系。例如，P∧Q，讀作“P與Q”。⑶符號(hào)“∨”稱為“析取”(Disjunction)，它表示“或”(OR)的連接關(guān)系。例如，P∨Q，讀作“P或Q”。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室14/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室15/117一階邏輯⑷符號(hào)“→”稱為“條件”(Conditional)或者“蘊(yùn)涵”(Implication)，它表示“如果……，則……”的定義關(guān)系。例如，在P→Q的表達(dá)式中，表示了“如果P，則Q”的條件推導(dǎo)關(guān)系。這里，又稱P為前件，表示條件的前提，稱Q為后件，表示邏輯結(jié)論。條件表達(dá)式有一個(gè)重要特性：當(dāng)前件P=F時(shí)，無(wú)論后件Q為何值(T或者F)，條件式P→Q真值總是為T；當(dāng)前件P=T時(shí)，條件式P→Q的真值總是與后件Q真值相同。⑸符號(hào)“

”稱為“雙條件”(Biconditional)或者等價(jià)(Equivalence)

連接關(guān)系。例如，表達(dá)式P

Q，讀作“P當(dāng)且僅當(dāng)Q”?；蛘哒f(shuō)它表示的含義為：P為真，當(dāng)且僅當(dāng)Q為真。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室15/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室16/117一階邏輯

PQ

?P

P∨Q

P∧Q

P→Q

P

Q

FF

T

F

F

T

T

FT

T

T

F

T

F

TF

F

T

F

F

F

TT

F

T

T

T

T表3.1連接詞定義真值表

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室16/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室17/117一階邏輯

2.

量詞(Quantifiers)

量詞，表示了個(gè)體與個(gè)體域之間的包含關(guān)系。

⑴全稱量詞(UniversalQuantifier)：用字符“

x”表達(dá)，表示了該量詞作用的轄域?yàn)閭€(gè)體域中“所有的個(gè)體x”或“每一個(gè)體x都”要遵從所約定的謂詞關(guān)系。例3.4

(

x)(現(xiàn)代理工科大學(xué)生(x)→學(xué)習(xí)計(jì)算機(jī)應(yīng)用基礎(chǔ)(x))；解：該謂詞邏輯表達(dá)的含義是：“所有現(xiàn)代理工科的大學(xué)生x，都必須學(xué)習(xí)計(jì)算機(jī)應(yīng)用基礎(chǔ)課程”。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室17/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室18/117一階邏輯

2.

量詞(Quantifiers)

⑵存在量詞(ExistentialQuantifier)：用字符“彐x”表達(dá)，表示了該量詞要求“存在于個(gè)體域中的某些個(gè)體x”或“某個(gè)個(gè)體x”，要服從所約定的謂詞關(guān)系。例3.5

(

x)(彐y)(CLASSMATE(x,y)∧COLLEGEOFCOMPUTER(x)；解：該謂詞邏輯表達(dá)的意思是：在所有的計(jì)算機(jī)學(xué)院學(xué)生中，相對(duì)于每一位同學(xué)x，必然存在一個(gè)個(gè)體y，y同學(xué)與x滿足同班同學(xué)的關(guān)系。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室18/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室19/117一階邏輯

3.命題公式及其描述舉例：⑴小張既聰明，又勤奮，所以他的學(xué)習(xí)成績(jī)一直很好。P：小張聰明Q：小張勤奮R：小張學(xué)習(xí)成績(jī)一直很好⑵小王總是在圖書館看書，除非他病了或圖書館不開門。P：小王病了Q：圖書館開門R：小王在圖書館看書得到：（P∧Q）→R得到：?

（P∨?

Q）

R2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室19/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室20/117一階邏輯⑴若張先生是小張的父親，則小張是王太太的兒子。解：先設(shè)定謂詞，再設(shè)定變?cè)?，并將變?cè)猿Ａ浚眠B接詞運(yùn)算符連接并加以描述：設(shè)定謂詞：FATHER(x,y)：x是y的父親

SON(y,w)：y是w的兒子

常量：z表示張先生；mz表示小張；wtt——王太太則可描述為：FATHER(z,mz)→SON(mz,wtt)（2）若x是小張的父親，且y是小張的兄弟，則x也是y的父親。解：設(shè)定謂詞：FATHER(x,y)：x是y的父親

BROTHER(y,w)：y是w的兄弟

常量：mz表示小張則可描述為：FATHER(x,mz)∧BROTHER(y,mz)→FATHER(x,y)4.謂詞公式及其描述舉例：2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室20/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室21/117一階邏輯（3）*在那遙遠(yuǎn)的地方，有位好姑娘，人們走過(guò)她的身旁，都要回頭留戀地張望。解：(彐x){好姑娘(x)∧居住的地方(z，x)∧遙遠(yuǎn)的(z)∧(

y)[人(y)∧行走經(jīng)過(guò)(y,z)→回頭留戀地張望(y)]}2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室21/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室22/117一階邏輯5.謂詞公式概念使用連接詞和量詞，把若干謂詞連接組合在一起，就得到了謂詞邏輯公式(PLF：PredicateLogicFormula)的表達(dá)。定義3.5

僅能表達(dá)單一意義且不可再細(xì)劃分的簡(jiǎn)單命題稱為原子命題。例如，一階零元(目)命題、一階一元命題、一階二元命題等都是原子命題。定義3.6

用連接詞或者量詞把若干原子命題聯(lián)結(jié)組合在一起，就得到了命題公式(PF：PropositionFormula)，又稱之為命題合式公式。定義3.7

采用參量變?cè)獊?lái)替代命題合式公式中的常量，就得到了原子謂詞公式，又稱之為謂詞合式公式（PWFF：PredicateWell-FormedFormula），簡(jiǎn)稱合式公式或WFF。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室22/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室23/117一階邏輯謂詞合式公式及其生成規(guī)則的定理。

定理3.1

謂詞合式公式可依照下述遞歸(Recursion)過(guò)程得到：①原子公式是謂詞合式公式；②若A是謂詞合式公式，x是A中的任一個(gè)變?cè)?，則?A,(

x)A和(彐x)A也都是合式公式；③若A、B都是謂詞合式公式，則?A,?B,A∧B,A∨B,A→B,A

B也都是合式公式；④若有限次使用上述各步生成的公式，仍是合式公式。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室23/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室24/117一階邏輯注意：為了使合式公式WFF在連接和運(yùn)算中表達(dá)簡(jiǎn)潔一致，對(duì)WFF還有如下規(guī)定：⑴WFF最外層括號(hào)可以省略；⑵括號(hào)內(nèi)連接符運(yùn)算優(yōu)先，連接符運(yùn)算優(yōu)先次序?yàn)?∧∨→

；⑶同級(jí)連接符的運(yùn)算按照排列順序進(jìn)行。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室24/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室25/117一階邏輯

6.謂詞公式的解釋首先以個(gè)體域中任意常量來(lái)替換謂詞公式中的變?cè)?，使謂詞公式轉(zhuǎn)換為一組確定的命題公式；隨后賦予各命題邏輯以真值，就得到了對(duì)應(yīng)于該謂詞公式的某個(gè)含義的解釋。

由于存在多種組合情況，則一個(gè)謂詞公式可有許多個(gè)解釋。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室25/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室26/117一階邏輯下面是關(guān)于謂詞公式解釋的定義。定義3.8

設(shè)D為謂詞合式公式PWFF的個(gè)體域，按照如下規(guī)定對(duì)PWFF中的各參量賦值：①為每個(gè)個(gè)體常量指派D中的一個(gè)元素；②為每個(gè)n元函數(shù)指派一個(gè)從Dn到D的映像，其中

Dn={(x1,x2,…,xn)/x1,…,xn∈D}③為每個(gè)n元謂詞指派一個(gè)從Dn到真值{F,T}的映像。則稱這些指派為公式P在D上的一個(gè)解釋。若某個(gè)解釋I使PWFF為真(T)，則稱I是該公式的一個(gè)正模型，簡(jiǎn)稱模型；反之，若某個(gè)解釋I，使PWFF為假(F)，則稱I是該公式的一個(gè)反模型。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室26/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室27/117一階邏輯7.謂詞公式的永真性判定

人們?nèi)舭严胍瓿傻闹悄苋蝿?wù)表示為一個(gè)謂詞公式，從而把問(wèn)題的求解轉(zhuǎn)化為求解該公式的真值問(wèn)題：

如果某公式的真值總為T，則稱它是永真的；否則，就稱其為非永真或?yàn)榧佟?024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室27/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室28/117一階邏輯例3.6：

（1）若OCITY(x)

表示其含意為：x是一座歷史名城。其中，

x∈{西安，洛陽(yáng)，深圳，劉平，雪花，華盛頓，墨水，開封，…}那么，x的哪些取值的真值為T？哪些取值的真值又為F？它的哪些解釋是一個(gè)正模型？而哪些解釋又是反模型？（2）若WHITE(w)

表示其含意為：w是白的。其中，w

∈{煤球，雪花，大海，劉平，面粉，墨水，玫瑰花，…}

那么，w的哪些取值其真值為T？哪些取值的真值又為F？它的哪些解釋為正模型？而哪些解釋又屬于反模型？（3）若有公式OCITY(x)∨WHITE(w)

，其取值和解釋又如何呢？（4）若有公式OCITY(x)∧WHITE(w)

，其取值和解釋又如何呢？2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室28/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室29/117一階邏輯謂詞公式是否為永真的定義：

定義3.9

如果謂詞公式P對(duì)個(gè)體域D上的任何一個(gè)解釋都取得真值T，則稱P在D上是永真的；如果P在每個(gè)非空個(gè)體域上都是永真的，則稱P永真。

定義3.10

對(duì)于謂詞公式P，若至少存在一個(gè)解釋，使得謂詞公式P在此解釋下的真值為T，則稱公式P是兼容的或可滿足的；反之，如果存在一個(gè)解釋集(Set)，使得謂詞公式P在其中的任何解釋下的真值都為F，則稱公式P對(duì)該解釋集是不兼容的或不可滿足的。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室29/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室30/117一階邏輯判斷謂詞公式是否為永真的定理：

定理3.2

如果謂詞合式公式WFF對(duì)于個(gè)體域中的任何一個(gè)解釋I都有

(

I)WFF（I）=T成立，則該公式WFF是一個(gè)永真公式。

類同上述，可否引入關(guān)于“永假的”、“非永真的”、“非永假的”概念與定義，并得出關(guān)于謂詞公式永真性問(wèn)題的若干定理呢？

永假公式——定理3.3

如果謂詞合式公式WFF對(duì)于個(gè)體域中的任何一個(gè)解釋I都有

(

I)WFF（I）=F成立，則該公式WFF是一個(gè)永假公式。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室30/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室31/117一階邏輯

非永真公式——定理3.4

如果謂詞合式公式WFF在個(gè)體域中存在解釋I，使得

(彐I)WFF（I）=F

成立，則該公式WFF是一個(gè)非永真公式；并且該解釋I是此公式的一個(gè)反模型。

非永假公式——定理3.5

如果謂詞合式公式WFF在個(gè)體域中存在解釋I，使得

(彐I)WFF（I）=T成立，則該公式WFF是一個(gè)非永假公式；并且該解釋I是此公式的一個(gè)模型。由定義3.10可知，非永假公式可叫做是兼容的或可滿足的，而永假公式又稱為不可滿足的或不兼容的。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室31/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室32/117一階邏輯常用的謂詞邏輯演算律主要有兩大類：一類是邏輯等價(jià)律，另一類是邏輯蘊(yùn)涵律。下面分別加以介紹。

8.謂詞邏輯等價(jià)律

定義3.11

設(shè)P與Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域，若P與Q對(duì)于D上的任何一個(gè)解釋都有相同的真值，則稱公式P和Q在D上是邏輯等價(jià)的，記為P

Q

；如果D是任意個(gè)體域，則稱公式P和Q是邏輯等價(jià)的，記作P

Q。D2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室32/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室33/117謂詞邏輯等價(jià)律(一)E1??PP雙重否定律E2P∧PP吸收律㈠（又稱等冪律）E3P∨PPE4P∧QQ∧P交換律

E5

P∨QQ∨PE6

(P∧Q)∧RP∧(Q∧R)結(jié)合律

E7

(P∨Q)∨RP∨(Q∨R)E8P∧(Q∨R)(P∧Q)∨(P∧R)分配律

E9P∨(Q∧R)(P∨Q)∧(P∨R)一階邏輯2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室33/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室34/117謂詞邏輯等價(jià)律(二)E10P∧(P∨Q)P吸收律㈡E11P∨(P∧Q)PE12?(P∧Q)?P∨?Q德·摩根定律E13?(P∨Q)?P∧?QE14P→Q?P∨Q

蘊(yùn)涵化歸律E15P

Q(P→Q)∧(Q→P)等價(jià)律E16P∧TP謂詞與真值演算律E17P∧FFE18P∨TTE19P∨FP一階邏輯2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室34/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室35/117謂詞邏輯等價(jià)律(三)E20P∧?PF補(bǔ)余律E21

P∨?PTE22P→(Q→R)P∧Q→R輸出律E23(P→Q)∧(P→?Q)?P

歸謬律E24P→Q?Q→?P

逆反律E25

(

x)AA（A中不含x）E26

(

x)AAE27(

x)(P(x)∧Q(x))(

x)P(x)∧(x)Q(x)量詞分配律E28(

x)(P(x)∨Q(x))(

x)P(x)∨(

x)Q(x)E29?(

x)P(x)(

x)?P(x)

量詞轉(zhuǎn)換律E30?(

x)P(x)(

x)?P(x)一階邏輯2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室35/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室36/117謂詞邏輯等價(jià)律(四)E31(

x)P(x)∧A

(

x)(P(x)∧A)

量詞轄域擴(kuò)張、收縮律E32(

x)P(x)∨A

(

x)(P(x)∨A)

（A中不含x）E33(

x)P(x)∧A

(

x)(P(x)∧A)

（A中不含x）E34

(

x)P(x)∨A

(

x)(P(x)∨A)（A中不含x）E35

(

x)(

y)P(x,y)

(

y)(

x)P(x,y)量詞交換律E36

(

x)(

y)P(x,y)

(

y)(

x)P(x,y)E37

(

x)P(x)→A

(

x)(P(x)→A)量詞轉(zhuǎn)換及擴(kuò)張、收縮律E38

(

x)P(x)→A

(

x)(P(x)→A)（A中不含x）E39A→(

x)P(x)

(

x)(A→P(x))E40A→(

x)P(x)

(

x)(A→P(x))E41P∨﹁Q

R

P

Q∨R復(fù)合化歸律E42P

Q∨R

P∧Q

RE43P

(Q

R)

P∧Q

RE44(P

Q)

R

(

P

R)∧(Q

R)

(P∨R)∧(Q

R)一階邏輯2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室36/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室37/117一階邏輯

9.謂詞邏輯蘊(yùn)涵律

定義3.12

在謂詞公式P與Q中，若P→Q是永真的，則稱P永真蘊(yùn)涵Q；并稱P為前提，Q為P的邏輯結(jié)論，記作P

Q。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室37/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室38/117謂詞邏輯蘊(yùn)涵律I1P

P∨Q；Q

P∨Q；Q

P

Q附加律

I2P∧Q

P；

P∧Q

Q化簡(jiǎn)律I3P，P→Q

Q假言推理I4(P→Q)∧?Q

?P

拒取式推理I5

?P

，P∨Q

Q析取三段論推理I6(P→Q)∧(Q→R)

P→R假言三段論推理I7P→Q

(Q→R)→(P→R)I8(P→Q)∧(R→S)

P∧R→Q∧SI9(P

Q)∧(Q

S)

P

RI10

P∨Q，P→Q，Q→R

R二難推理I11

(

x)P(x)

P(y)

全稱固化律(y為個(gè)體域中的個(gè)體常量)I12

(

x)P(x)

P(y)

存在固化律一階邏輯2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室38/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室39/11710.幾條重要的推理規(guī)則⑴P規(guī)則：在進(jìn)行推理的任何步驟上，都可以引入前提P。⑵T規(guī)則：在進(jìn)行推理時(shí)，若同時(shí)有一個(gè)或多個(gè)謂詞公式永真(T)蘊(yùn)含公式S，則可把S引入推理過(guò)程中。⑶CP規(guī)則：若從公式C和前提集合P能推出S來(lái)，則由P可推出：P→S。一階邏輯2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室39/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室40/117⑷反證法規(guī)則：P

Q，當(dāng)且僅當(dāng)P∧?Q

F。即要證明Q成為P的邏輯結(jié)論，其充要條件是后一式必須成立。由反證法規(guī)則推廣之，可得到如下定理：定理3.6Q為P1，P2，……，PN的邏輯結(jié)論，當(dāng)且僅當(dāng)（P1∧P2∧…∧PN∧?Q

F

順便指出，這是一條使用了反證法的定理，也是迄今實(shí)現(xiàn)機(jī)器定理證明一種較為可靠的傳統(tǒng)途徑。

一階邏輯2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室40/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室41/117其他邏輯系統(tǒng)

——“非二值”邏輯

正如計(jì)算機(jī)中使用“0”和“1”兩個(gè)代碼來(lái)解釋世界一樣，人們?cè)诨诜?hào)的命題與謂詞邏輯中，試圖只使用“F”和“T”二個(gè)真值來(lái)描述智能特性。因此，人們把這種邏輯描述，又常稱之為二值邏輯或標(biāo)準(zhǔn)邏輯。但是，發(fā)展中的世界，事物運(yùn)動(dòng)變化，氣象萬(wàn)千，是否“非真即假”二值邏輯就能全部包容呢？事實(shí)上，在“T”和“F”兩極之間，世界萬(wàn)物還有著無(wú)限精彩表現(xiàn)。由于這些邏輯的特性往往都不是二值的，故統(tǒng)稱其為多值邏輯，或稱為“非二值”邏輯。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室41/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室42/117其他邏輯系統(tǒng)

——“非二值”邏輯

人們從實(shí)際應(yīng)用出發(fā)已經(jīng)發(fā)明和建立了許多適用于不同目的的邏輯系統(tǒng)：(1)為了表示關(guān)于認(rèn)知的有關(guān)概念，如相信、知道、愿望、意圖、目標(biāo)、承諾等等，人們引進(jìn)了刻劃各種認(rèn)知概念的模態(tài)邏輯；(2)為了刻劃智能系統(tǒng)中的時(shí)間因素，人們?cè)谶壿嬒到y(tǒng)中引進(jìn)時(shí)間的概念，提出了各種時(shí)序邏輯；(3)為了描述各種不確定的和不精確的概念，人們引進(jìn)了所謂模糊邏輯；模糊邏輯是直接建立在自然語(yǔ)言上的邏輯系統(tǒng)，與其它邏輯系統(tǒng)相比較，它考慮了更多的自然語(yǔ)言的成分。按照其創(chuàng)始人Zadeh的說(shuō)法就是詞語(yǔ)上的計(jì)算，表示為一個(gè)公式，即

fuzzylogic＝computingwithwords；

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室42/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室43/117其他邏輯系統(tǒng)

——“非二值”邏輯

(4)行為或者動(dòng)作的概念在智能系統(tǒng)中是一個(gè)關(guān)鍵的概念。動(dòng)作的概念與一般邏輯中的靜態(tài)的概念很不相同，它是一個(gè)動(dòng)態(tài)的概念，動(dòng)作的發(fā)生影響著智能系統(tǒng)的性質(zhì)。為了刻劃動(dòng)作的概念，人們引進(jìn)了一些新的邏輯體系來(lái)刻劃它。(5)人類在決策時(shí)，對(duì)于各種方案和目標(biāo)有一定的偏好和選擇。這時(shí)“偏愛”就成為了一個(gè)基本的概念。為了表述和模擬人類在決策時(shí)的選擇的規(guī)律和行為，對(duì)于“偏愛”這個(gè)詞的研究就是不可避免的。于是，基于管理科學(xué)的所謂的偏愛邏輯被提出并加以研究。(6)時(shí)間是智能系統(tǒng)中最重要的幾個(gè)概念之一。人類使用各類副詞來(lái)對(duì)時(shí)間概念加以描述。例如，“一會(huì)兒”“相當(dāng)長(zhǎng)”“斷斷續(xù)續(xù)地”“偶爾”等等，含有這些詞的句子顯然是很難用經(jīng)典的時(shí)序邏輯來(lái)刻劃的，于是有人引進(jìn)了一種邏輯系統(tǒng)專門刻劃這類句子。其基本思想是利用數(shù)學(xué)中積分的思想，通過(guò)對(duì)時(shí)間的某種像積分那樣的表示和運(yùn)算來(lái)形式化這些句子2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室43/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室44/117其他邏輯系統(tǒng)

——邏輯程序設(shè)計(jì)

Prolog程序就是一種邏輯程序，它是一種交互式的描述性語(yǔ)言，第一個(gè)正式版本是1970年代法國(guó)Marseilles大學(xué)的AlainColmerauer作為PROgramminginLOGic的工具開發(fā)出來(lái)的。只要給定所需的事實(shí)和規(guī)則，Prolog使用演繹推理方法就可對(duì)問(wèn)題進(jìn)行求解。Prolog特點(diǎn)：

（1）Prolog是數(shù)據(jù)和程序的統(tǒng)一。Prolog提供了一種一致的數(shù)據(jù)結(jié)構(gòu)：項(xiàng)。所有數(shù)據(jù)和程序都是由項(xiàng)構(gòu)造而成的。在智能程序中常需要將一段程序的輸出數(shù)據(jù)作為新產(chǎn)生的程序來(lái)執(zhí)行，因此人工智能語(yǔ)言應(yīng)具有數(shù)據(jù)和程序結(jié)構(gòu)一致的特性。

（2）Prolog能夠自動(dòng)實(shí)現(xiàn)模式匹配和回溯。這些是人工智能系統(tǒng)中最常用的、最基本的操作。

（3）Prolog具有遞歸的特點(diǎn)，它反映在Prolog程序和數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)中。由于這一特性，一個(gè)大的數(shù)據(jù)結(jié)構(gòu)常?？梢杂靡粋€(gè)小的程序來(lái)處理。一般情況下，對(duì)一個(gè)應(yīng)用來(lái)說(shuō)，用Prolog語(yǔ)言寫的程序長(zhǎng)度是用C++語(yǔ)言寫的程序長(zhǎng)度的十分只一。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室44/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室45/117其他邏輯系統(tǒng)

——邏輯程序設(shè)計(jì)

Horn子句一個(gè)子句由兩部分組成：頭部和體。IF-THEN規(guī)則的結(jié)論稱為頭部，前提部分稱為體。

定義3.13Horn子句是頭部最多包含一個(gè)文字（命題或謂詞）的子句。Horn子句在Prolog中有三種表示形式：（1）無(wú)條件子句（事實(shí)）：A.（2）條件子句(規(guī)則)：A:-B1,…,Bn.（3）目標(biāo)子句(問(wèn)題)：?-B1,…,Bn.上述三種Horn子句均具有明顯的非形式語(yǔ)義：（1）無(wú)條件子句A：表示對(duì)變量的任何賦值，A均為真。（2）條件子句A:-B1,…,Bn：表示對(duì)變量的任何賦值，如果B1,…,Bn均為真，則A為真。（3）目標(biāo)子句?-B1,…,Bn：其邏輯形式為?x1…xn(?B1∨…∨?Bn)，等價(jià)于??x1…xn(B1∧…∧Bn)。它視作推理的目標(biāo)。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室45/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室46/117其他邏輯系統(tǒng)

——邏輯程序設(shè)計(jì)定義3.14

邏輯程序就是由Horn子句構(gòu)成的程序。在邏輯程序中，頭部具有相同謂詞符的那些子句稱為該謂詞的定義。例如下面兩個(gè)謂詞邏輯句子，每個(gè)句子都只有一個(gè)頭。

Father(X,Y):-Child(Y,X),Male(X).Son(Y,X):-Child(Y,X),Male(Y).上述兩個(gè)子句都是Horn子句，它們構(gòu)成一個(gè)邏輯程序。假設(shè)還有下面三個(gè)事實(shí)子句：

Child(xiao-li,lao-li).Male(xiao-li).Male(lao-li).如果把上述規(guī)則和事實(shí)加入Prolog中，編譯執(zhí)行后，給出下面的查詢，則有：（1）目標(biāo)：?-Father(X,Y).

則會(huì)得到：Father(lao-li,xiao-li).

（2）目標(biāo)：?-Son(Y,X).

則會(huì)得到：Son(xiao-li,lao-li).2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室46/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室47/117其他邏輯系統(tǒng)

——非單調(diào)邏輯單調(diào)邏輯在現(xiàn)有知識(shí)的基礎(chǔ)上，通過(guò)嚴(yán)密的邏輯論證和推理獲得的新知識(shí)必須與已有的知識(shí)相一致。具體地說(shuō)，設(shè)有知識(shí)系統(tǒng)A，如果已知A蘊(yùn)涵著知識(shí)B，即A→B，則可推理得出知識(shí)B。在此過(guò)程中，嚴(yán)格要求B必須遵從知識(shí)系統(tǒng)A。單調(diào)邏輯的推理規(guī)則是單調(diào)的。設(shè)Γ表示推理規(guī)則集，則單調(diào)邏輯的語(yǔ)言Th(Γ)={A|?！鶤}具有如下單調(diào)性：

(1)Γ∈Th(Γ)(2)如果Γ1?Γ2，則Th(Γ1)?Th(Γ2)(3)Th(Th(Γ))=Th(Γ)(冪等性)其中(3)又稱為不動(dòng)點(diǎn)(fixedpoint)。單調(diào)推理規(guī)則的顯著特性之一就是它的語(yǔ)言是封閉的最小不動(dòng)點(diǎn)，亦即Th(Γ1)=∩{s|Γ1→S且Th(S)=Γ2}。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室47/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室48/117其他邏輯系統(tǒng)

——非單調(diào)邏輯非單調(diào)推理推理系統(tǒng)的定理集合并不隨推理過(guò)程的進(jìn)行而單調(diào)地增大，新推出的定理很可能會(huì)否定、改變?cè)瓉?lái)的一些定理，使得原來(lái)能夠解釋的某些現(xiàn)象變得不能解釋了。假如把人們?cè)诓煌J(rèn)識(shí)階段的知識(shí)用集合F來(lái)表示，則這樣的集合是時(shí)間t的函數(shù)F(t)。每個(gè)集合F(t)表示人們?cè)跁r(shí)刻t的知識(shí)總和，則這些集合不是單調(diào)增大的。形式地說(shuō)，如果t1<t2，則F(t1)?F(t2)并不成立。然而人們的知識(shí)卻一直在不斷增長(zhǎng)。導(dǎo)致這一現(xiàn)象的根本原因就是人們推理時(shí)所依據(jù)的知識(shí)具有不完全性。非單調(diào)邏輯是處理不完全知識(shí)的工具。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室48/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室49/117其他邏輯系統(tǒng)

——非單調(diào)邏輯非單調(diào)推理三個(gè)主要流派：

McCarthy提出的限制理論：當(dāng)且僅當(dāng)沒(méi)有事實(shí)證明S在更大的范圍成立時(shí)，S只在指定的范圍成立；Reiter的缺省邏輯：“S在缺省的條件下成立”是指“當(dāng)且僅當(dāng)沒(méi)有事實(shí)證明S不成立時(shí)S是成立的”；Moore的自認(rèn)知邏輯：“如果我知道S，并且我不知道有其他任何事實(shí)與S矛盾，則S是成立的”。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室49/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室50/117其他邏輯系統(tǒng)

——非單調(diào)邏輯

對(duì)邏輯進(jìn)行擴(kuò)展，將非單調(diào)推理形式化，稱為非單調(diào)邏輯。

語(yǔ)言方面的擴(kuò)充是指增強(qiáng)其表達(dá)能力；

語(yǔ)義方面的擴(kuò)充是指對(duì)真值的真假兩種情況進(jìn)行修正；一是對(duì)推理模式的擴(kuò)展，這涉及非單調(diào)推理的過(guò)程化方面，稱為非單調(diào)系統(tǒng)。非單調(diào)邏輯大致分為兩類：一類基于最小化語(yǔ)義，稱為最小化非單調(diào)邏輯；另一類基于定點(diǎn)定義，稱為定點(diǎn)非單調(diào)邏輯。

最小化非單調(diào)邏輯可以分為基于最小化模型和基于最小化知識(shí)模型。前者主要有封閉世界假設(shè)、McCarthy的限制邏輯（circumscription）等，后者包括Konolige的忽略邏輯（ignorance）等。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室50/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室51/117其他邏輯系統(tǒng)

——非單調(diào)邏輯定點(diǎn)非單調(diào)邏輯可以分為缺省邏輯(default)和自認(rèn)知邏輯(autoepistemic)。McDermott和Doyle提出的非單調(diào)模態(tài)邏輯NML旨在研究非單調(diào)邏輯的一般基礎(chǔ),是一種一般缺省邏輯。非單調(diào)系統(tǒng)的實(shí)現(xiàn)，可以通過(guò)對(duì)矛盾的檢測(cè)進(jìn)行真值的修正來(lái)維護(hù)相容性，可稱為真值維護(hù)系統(tǒng)，包括Doyle提出的真值維護(hù)系統(tǒng)TMS，Dekleer提出的基于假設(shè)的真值維護(hù)系統(tǒng)ATMS等等。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室51/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室52/117其他邏輯系統(tǒng)

——封閉世界假設(shè)封閉世界假設(shè)（ClosedWorldAssumption—CWA）是一種對(duì)由一組基本信念集合KB定義的理論T(KB)進(jìn)行完備化的方法。一個(gè)理論T(KB)是完備的，是說(shuō)其包含（顯式或隱含）了每一個(gè)基原子公式或該公式否定。CWA的基本思想是：如果無(wú)法證明P，則就認(rèn)為它是否定的。即：如果從知識(shí)庫(kù)中無(wú)法證明P或者?P，則就向KB中增加?P。這就是說(shuō)你假定知道所有有關(guān)世界的事情（即世界是封閉的）。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室52/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室53/117其他邏輯系統(tǒng)

——封閉世界假設(shè)CWA的最大用處是完備化數(shù)據(jù)庫(kù)系統(tǒng)。例如，我們可以設(shè)計(jì)一個(gè)關(guān)于國(guó)家鄰接的數(shù)據(jù)庫(kù)Neighbor(x,y)?；贑WA，凡是未在該數(shù)據(jù)庫(kù)中說(shuō)明是鄰接的國(guó)家都是不鄰接的。假定KB：Neighbor(China,Russia).Neighbor(China,Mongolia).?x?y(Neighbor(x,y)?Neighbor(y,x))則T(KB)是不完全的，因?yàn)闊o(wú)論是Neighbor(Russia,Mongolia)還是?Neighbor(Russia,Mongolia)都不在KB中。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室53/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室54/117其他邏輯系統(tǒng)

——封閉世界假設(shè)

CWA對(duì)理論的完備化是僅僅通過(guò)向基本信念集合KB中增加基原子公式的取反來(lái)實(shí)現(xiàn)的。換言之，若一個(gè)基原子公式不能經(jīng)由邏輯推理從基本信念集KB導(dǎo)出，就將其取反作為KB的擴(kuò)充。顯然，CWA是非單調(diào)的，因?yàn)橐坏┮院笥行碌幕庸郊舆M(jìn)KB，則為完備T（KB）而生成的擴(kuò)充集就必須收縮（刪除該基原子公式的否定）。例如對(duì)于國(guó)家相鄰問(wèn)題，可以向KB中增加?Neighbor(Russia,Mongolia)實(shí)現(xiàn)完備化。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室54/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室55/117其他邏輯系統(tǒng)

——情景演算

情景演算是分析處理和研究涉及動(dòng)作和進(jìn)化問(wèn)題的最常用的形式工具。

多類邏輯（LR）：建立在對(duì)情景演算的直觀理解的意義上，把情景演算的概念和方法在這種特殊的多類一階邏輯的框架之內(nèi)進(jìn)行描述，以便為有關(guān)的研究提供一個(gè)堅(jiān)實(shí)的系統(tǒng)的理論基礎(chǔ)。把情景演算集成在一個(gè)多類邏輯框架里，這一做法的核心是：為了刻劃一個(gè)動(dòng)作，只需要描述動(dòng)作發(fā)生的條件和動(dòng)作發(fā)生以后對(duì)其環(huán)境所產(chǎn)生的效果這兩件事。為此，在邏輯框架LR中引入了“動(dòng)作”，“狀態(tài)”和“一般對(duì)象”這三種個(gè)體類型，然后通過(guò)一系列的邏輯句子來(lái)表述這三種對(duì)象的最一般關(guān)系以及動(dòng)作發(fā)生的前提和后果。每個(gè)這樣的句子集被稱為一個(gè)基本的動(dòng)作理論。從純粹邏輯學(xué)的觀點(diǎn)看，所謂的“動(dòng)作的基本理論”就是在特定的多類邏輯中的普通邏輯學(xué)意義下的一個(gè)理論。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室55/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室56/117其他邏輯系統(tǒng)

——情景演算LR被定義成一種多類邏輯，在其形式語(yǔ)言?中引入了三種關(guān)于個(gè)體的類型，即狀態(tài)類型s、對(duì)象類型o和動(dòng)作類型a。一個(gè)類型為s的常量符號(hào)S0（表示起始狀態(tài)）；一個(gè)類型為<a,s；s>的二元函數(shù)符號(hào)do（描述一個(gè)動(dòng)作的發(fā)生使得狀態(tài)從一個(gè)變成另外一個(gè)）；一個(gè)類型為<a,s>的二元關(guān)系符號(hào)Poss（表示一個(gè)動(dòng)作在一個(gè)狀態(tài)之下是可能發(fā)生的）；一個(gè)類型為<s,s>的二元關(guān)系符號(hào)<（表示狀態(tài)之間的先后關(guān)系）。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室56/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室57/117其他邏輯系統(tǒng)

——?jiǎng)討B(tài)描述邏輯DDL

描述邏輯是一種基于對(duì)象的知識(shí)表示的形式化，也叫概念表示語(yǔ)言或術(shù)語(yǔ)邏輯。它是一階邏輯的一個(gè)可判定的子集，具有合適定義的語(yǔ)義，并且具有很強(qiáng)的表達(dá)能力。一個(gè)描述邏輯系統(tǒng)包含四個(gè)基本組成部分：表示概念和關(guān)系的構(gòu)造集；TBox包含斷言；ABox實(shí)例斷言；TBox和ABox上的推理機(jī)制。一個(gè)描述邏輯系統(tǒng)的表示能力和推理能力取決于對(duì)以上幾個(gè)要素的選擇以及不同的假設(shè)。描述邏輯中有兩個(gè)基本元素：

概念解釋為一個(gè)領(lǐng)域的子集；

關(guān)系則表示在領(lǐng)域中個(gè)體之間所具有的相互關(guān)系，是在領(lǐng)域集合上的一種二元關(guān)系。動(dòng)態(tài)描述邏輯是在傳統(tǒng)描述邏輯的基礎(chǔ)上擴(kuò)充得到的。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室57/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室58/117約束推理約束通常是指一個(gè)包含若干變量的關(guān)系表達(dá)式，用以表示這些變量所必須滿足的條件。

約束滿足問(wèn)題(ConstraintSatisfactionProblem,簡(jiǎn)稱CSP)一組變量與一組變量間的約束。一般而言，變量表示領(lǐng)域參數(shù)，每個(gè)變量都有一個(gè)固定的值域。一個(gè)變量的值域可能是有限的，例如一個(gè)布爾變量的值域包含兩個(gè)值；也可能是離散無(wú)限的，如整數(shù)域；也可能是連續(xù)的，如實(shí)數(shù)域。約束可用于描述領(lǐng)域?qū)ο蟮男再|(zhì)、相互關(guān)系、任務(wù)要求、目標(biāo)等。

約束滿足問(wèn)題的目標(biāo)就是找到所有變量的一個(gè)（或多個(gè)）賦值，使所有約束都得到滿足。約束滿足問(wèn)題在一般情形下是一個(gè)NP問(wèn)題，所以必須使用各種策略與啟發(fā)式信息。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室58/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室59/117約束推理約束表示易于理解、編碼及有效實(shí)現(xiàn)，它具有以下優(yōu)點(diǎn):(1)約束表示允許以說(shuō)明性的方式來(lái)表達(dá)領(lǐng)域知識(shí)，表達(dá)能力較強(qiáng)，應(yīng)用程序只需指定問(wèn)題的目標(biāo)條件及數(shù)據(jù)間的相互關(guān)系。因而具有邏輯表示的類似性質(zhì)。

(2)約束表示允許變量的域包含任意多個(gè)值，而不像命題只取真假二值。所以它保存了問(wèn)題的一些結(jié)構(gòu)信息，如變量域的大小、變量間的相關(guān)性等，從而為問(wèn)題求解提供啟發(fā)式信息。(3)易于并行實(shí)現(xiàn)。因?yàn)榧s束網(wǎng)絡(luò)上的信息傳播可以認(rèn)為是同時(shí)的。(4)適合于遞增型系統(tǒng)。約束可以遞增式地加入到約束網(wǎng)絡(luò)。(5)易于與領(lǐng)域相關(guān)的問(wèn)題求解模型相銜接。各種數(shù)學(xué)規(guī)劃技術(shù)，方程求解技術(shù)等,都可以自然地嵌入約束系統(tǒng)。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室59/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室60/117約束推理

根據(jù)聯(lián)系于約束網(wǎng)絡(luò)節(jié)點(diǎn)上的數(shù)據(jù)類型，可以將約束推理分為以下幾種：

(1)

關(guān)系推理：推理過(guò)程中推出的新的約束關(guān)系,并將其加到約束網(wǎng)絡(luò)中。Kuiper的ENV系統(tǒng)、Simmon的QuantityLattice系統(tǒng)，及Brooks的CMS系統(tǒng),都屬于關(guān)系推理。

(2)標(biāo)記推理：每個(gè)節(jié)點(diǎn)標(biāo)注以可能值的集合，在傳播過(guò)程中約束用于限制這些集合。

(3)值推理：節(jié)點(diǎn)標(biāo)記以常量值。約束用已標(biāo)記節(jié)點(diǎn)的值求出標(biāo)記節(jié)點(diǎn)的值。SKETCHPAD及THINGLAB都使用值推理。

(4)表達(dá)式推理：是值推理的推廣，其中節(jié)點(diǎn)可能標(biāo)以關(guān)于其它節(jié)點(diǎn)的表達(dá)式。當(dāng)一個(gè)節(jié)點(diǎn)標(biāo)記以不同的表達(dá)式時(shí),應(yīng)使其等同起來(lái),并求解結(jié)果方程。CONSTRAINTS就使用這種推理。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室60/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室61/117約束推理

約束分類,按復(fù)雜性的次序列舉如下：一元謂詞。序關(guān)系語(yǔ)言，只包含偏序關(guān)系或?qū)嵶兞可系拇笮￡P(guān)系。形如“x-y>c”或“x-y≥c”的方程。單位系數(shù)的線性方程與不等式，即所有的系數(shù)為-1,0,1。任意系數(shù)的線性方程與不等式。約束的布爾組合。代數(shù)與三角方程。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室61/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室62/117約束推理

約束推理的研究：

約束搜索

主要研究有限域上的約束滿足。大體包括下列方法：回溯法。約束傳播。智能回溯與真值維護(hù)?？勺兇涡蚶尽＞植啃拚?。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室62/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室63/117約束推理約束語(yǔ)言

CONSTRAINTS：是一個(gè)面向電路描述的約束表示語(yǔ)言。使用了符號(hào)處理技術(shù)來(lái)求解數(shù)學(xué)方程，系統(tǒng)采用表達(dá)式推理與值推理，并實(shí)現(xiàn)相關(guān)制導(dǎo)的回溯。

Bertrand：Bertrand是由Leler開發(fā)的基于增強(qiáng)型項(xiàng)重寫技術(shù)的系統(tǒng)，是在項(xiàng)重寫系統(tǒng)的基礎(chǔ)上加上賦值功能與類型機(jī)制。能夠解決實(shí)數(shù)與有理數(shù)上的線性方程。

約束邏輯程序設(shè)計(jì)語(yǔ)言CHIP：是在Prolog的基礎(chǔ)上引入約束傳播機(jī)制，以提高搜索效率，增強(qiáng)表達(dá)能力。通過(guò)提供幾種新的計(jì)算域而增強(qiáng)邏輯程序設(shè)計(jì)的能力。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室63/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室64/117約束推理約束語(yǔ)言約束層次與HCLP：

將需要盡可能滿足的“軟約束”分成若干優(yōu)先等級(jí)，這種表示就稱為約束層次。Borning設(shè)計(jì)的HCLP語(yǔ)言將約束層次嵌入Prolog之中，使整個(gè)約束層次系統(tǒng)完全建立在說(shuō)明性表示基礎(chǔ)之上。面向?qū)ο蠹s束語(yǔ)言COPS

：中科院計(jì)算所研制，將說(shuō)明性約束表達(dá)與類型層次結(jié)合起來(lái)，具有如約束傳播、面向目標(biāo)和數(shù)據(jù)驅(qū)動(dòng)的問(wèn)題求解、有限步的回溯、對(duì)象分層中的繼承等特點(diǎn)。ILOG

：ILOG公司的ILOGSolver使用建模語(yǔ)言來(lái)表示約束問(wèn)題。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室64/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室65/117定性推理

定性推理(qualitativereasoning)是從物理系統(tǒng)、生命系統(tǒng)的結(jié)構(gòu)描述出發(fā),導(dǎo)出行為描述,以便預(yù)測(cè)系統(tǒng)的行為并給出原因解釋。定性推理采用系統(tǒng)部件間的局部結(jié)構(gòu)規(guī)則來(lái)解釋系統(tǒng)行為,即部件狀態(tài)的變化行為只與直接相鄰的部件有關(guān)。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室65/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室66/117定性推理定性推理理論起源

對(duì)物理現(xiàn)象的研究,早期的工作常常是針對(duì)一物理過(guò)程如動(dòng)力學(xué)、流體力學(xué)、熱流等問(wèn)題來(lái)討論的。1952年，Simmons提出定性分析的因果關(guān)系。1977年，Rieger發(fā)表了因果仿真的論文。1984年，“ArtificialIntelligence”雜志第24卷出版了定性推理專輯，刊載了deKleer,Forbus和Kuipers對(duì)定性推理奠基性的文章，這標(biāo)志著定性推理開始走向成熟。1986年，Iwasaki和Simmons發(fā)表了“CausalityinDeviceBehavior”的文章。1993年,“ArtificialIntelligence”雜志第59卷又發(fā)表了一組文章，回顧十年前這幾位定性推理奠基人所做的工作。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室66/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室67/117定性推理對(duì)物理系統(tǒng)不同的結(jié)構(gòu)描述,便提出了不同的定性推理方法。常用的三種方法：deKleer的定性模型方法：deKleer的定性模型方法所涉及的物理系統(tǒng)是由管子、閥門、容器等裝置組成,約束條件(定性方程)反映在這些裝置的連接處,依定性方程給出定性解釋。

Forbus的定性進(jìn)程方法中，一個(gè)物理系統(tǒng)的變化是由進(jìn)程引起的，一個(gè)物理過(guò)程由一些進(jìn)程來(lái)描述。Kuipers定性仿真法直接用部件的參量作為狀態(tài)變量來(lái)描述物理結(jié)構(gòu)，定性約束直接由物理規(guī)律得到，把一個(gè)參量隨時(shí)間的變化視作定性的狀態(tài)序列，求解算法是從初始狀態(tài)出發(fā)，生成各種可能的后續(xù)狀態(tài)，進(jìn)而通過(guò)一致性過(guò)濾，重復(fù)這過(guò)程直到?jīng)]有新狀態(tài)出現(xiàn)。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室67/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室68/117定性推理一般分析運(yùn)動(dòng)系統(tǒng)行為的標(biāo)準(zhǔn)過(guò)程可分為三個(gè)步驟：

(1)決定描述對(duì)象系統(tǒng)特征的量。

(2)用方程式表示量之間的相互關(guān)系。

(3)分析方程式，得到數(shù)值解。這類運(yùn)動(dòng)系統(tǒng)行為的問(wèn)題用計(jì)算機(jī)進(jìn)行求解時(shí)，將面臨如下三個(gè)問(wèn)題：

(1)步驟(1)(2)需要相當(dāng)多的知識(shí)，并且要有相應(yīng)的算法。

(2)有的場(chǎng)合對(duì)象系統(tǒng)的性質(zhì)很難用數(shù)學(xué)式子表示。

(3)步驟(3)得到了數(shù)值解，但是對(duì)象系統(tǒng)的行為并不直觀明了。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室68/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室69/117定性推理為了解決第二、第三個(gè)問(wèn)題，定性推理一般采用下列分析步驟：

(1)結(jié)構(gòu)認(rèn)識(shí)：將對(duì)象系統(tǒng)分解成部件的組合。

(2)因果分析：當(dāng)輸入值變化時(shí)，分析對(duì)象系統(tǒng)中怎樣傳播。

(3)行為推理：輸入值隨著時(shí)間變化，分析對(duì)象系統(tǒng)的內(nèi)部狀態(tài)怎樣變化。

(4)功能說(shuō)明：行為推理的結(jié)果表明對(duì)象系統(tǒng)的行為，由此可以說(shuō)明對(duì)象系統(tǒng)的功能。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室69/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室70/117定性推理定性推理的觀點(diǎn)大體上可這樣來(lái)理解:忽略被描述對(duì)象的次要因素,掌握主要因素簡(jiǎn)化問(wèn)題的描述。

將隨時(shí)間t連續(xù)變化的參量x(t)的值域離散化為定性值集合,通常變量x的定性值[x]定義為

-當(dāng)X<0

[x]=0當(dāng)X=0+當(dāng)X>0

依物理規(guī)律將微分方程轉(zhuǎn)換成定性(代數(shù))方程,或直接依物理規(guī)律建立定性模擬或給出定性進(jìn)程描述。

最后給出定性解釋

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室70/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室71/117基于范例的推理

基于范例推理

(Case-BasedReasoning,簡(jiǎn)稱CBR)：把當(dāng)前所面臨的問(wèn)題或情況稱為目標(biāo)范例(targetcase)，而把記憶的問(wèn)題或情況稱為源范例(basecase)?；诜独评砭褪怯赡繕?biāo)范例的提示而獲得記憶中的源范例，并由源范例來(lái)指導(dǎo)目標(biāo)范例求解的一種策略。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室71/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室72/117基于范例的推理

范例（case）：范例是一段帶有上下文信息的知識(shí)，該知識(shí)表達(dá)了推理機(jī)在達(dá)到其目標(biāo)的過(guò)程中能起關(guān)鍵作用的經(jīng)驗(yàn)范例應(yīng)具有特性：范例表示了與某個(gè)上下文有關(guān)的具體知識(shí)，這種知識(shí)具有可操作性。范例可以是各式各樣的，可有不同的形狀和粒度，可涵蓋或大或小的時(shí)間片，可帶有問(wèn)題的解答或動(dòng)作執(zhí)行后的效應(yīng)。范例記錄了有用的經(jīng)驗(yàn)，這種經(jīng)驗(yàn)?zāi)軒椭评頇C(jī)在未來(lái)更容易地達(dá)到目標(biāo)，或提醒推理機(jī)失敗發(fā)生的可能性有多大等等。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室72/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室73/117基于范例的推理基于范例推理對(duì)人工智能的貢獻(xiàn)：(1)知識(shí)獲?。哼@是基于知識(shí)的系統(tǒng)的瓶頸問(wèn)題。開發(fā)基于規(guī)則的知識(shí)系統(tǒng)時(shí)，獲取規(guī)則或模型是最繁瑣的一件事務(wù)，需要領(lǐng)域?qū)＜液椭R(shí)工程師的密切合作；有的領(lǐng)域甚至很難找到適合的規(guī)則。

(2)知識(shí)維護(hù)：隨著系統(tǒng)的運(yùn)行，知識(shí)系統(tǒng)常常出現(xiàn)初始的知識(shí)不完整而需要更新，新的知識(shí)可能會(huì)與原有知識(shí)產(chǎn)生沖突，導(dǎo)致非常大的系統(tǒng)變動(dòng)。基于范例推理則不存在這些問(wèn)題。(3)改進(jìn)問(wèn)題求解效率：基于范例推理通過(guò)復(fù)用過(guò)去的解答，無(wú)需象常規(guī)推理那樣從頭做起。特別是，由于記錄了過(guò)去求解時(shí)的失敗或成功信息，使得求解新問(wèn)題時(shí)可避開錯(cuò)誤的途徑。2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室73/12024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室74/117基于范例的推理

(4)改進(jìn)問(wèn)題求解質(zhì)量：過(guò)去求解失敗的經(jīng)歷可以指導(dǎo)當(dāng)前求解時(shí)避開失敗。(5)提高用戶接受度：用戶如果能清楚知道系統(tǒng)得出的結(jié)論是合理地推出的，他才相信該結(jié)論。基于范例推理的根據(jù)則是歷史事實(shí)，事實(shí)勝于雄辯，因此對(duì)用戶有說(shuō)服力。

2024/4/2合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室74/12024/4/2合肥工業(yè)大學(xué)人工智能與