人工智能邏輯-智能科學(xué)課件

人工智能邏輯

2023/1/5史忠植邏輯基礎(chǔ)1史忠植中國(guó)科學(xué)院計(jì)算技術(shù)研究所高級(jí)人工智能第二章人工智能邏輯

2022/12/27史忠植邏輯基礎(chǔ)1史忠植主要內(nèi)容邏輯簡(jiǎn)介邏輯程序設(shè)計(jì)非單調(diào)邏輯默認(rèn)邏輯限定邏輯真值維護(hù)系統(tǒng)情景演算動(dòng)態(tài)描述邏輯2023/1/5史忠植邏輯基礎(chǔ)2主要內(nèi)容邏輯簡(jiǎn)介2022/12/27史忠植邏輯基礎(chǔ)2邏輯簡(jiǎn)介邏輯的歷史邏輯系統(tǒng)命題邏輯謂詞邏輯2023/1/5史忠植邏輯基礎(chǔ)3邏輯簡(jiǎn)介邏輯的歷史2022/12/27史忠植邏輯基礎(chǔ)3邏輯的歷史Aristotle——邏輯學(xué)Leibnitz——數(shù)理邏輯GottlobFrege(1848-1925)——一階謂詞演算系統(tǒng),《符號(hào)論》20世紀(jì)30年代，數(shù)理邏輯廣泛發(fā)展2023/1/5史忠植邏輯基礎(chǔ)4邏輯的歷史Aristotle——邏輯學(xué)2022/12/27史邏輯系統(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ǔ)義。2023/1/5史忠植邏輯基礎(chǔ)5邏輯系統(tǒng)一個(gè)邏輯系統(tǒng)是定義語(yǔ)言和它的含義的方法。20222023/1/5史忠植邏輯基礎(chǔ)6邏輯程序語(yǔ)言邏輯符號(hào)保留字或者符號(hào)非邏輯符號(hào)用戶(hù)自定義的符號(hào)(變量名，函數(shù)名等)語(yǔ)句規(guī)則構(gòu)造一個(gè)程序的語(yǔ)句規(guī)則語(yǔ)義規(guī)則定義程序做什么的語(yǔ)句規(guī)則推理規(guī)則、公理和證明沒(méi)有邏輯與程序語(yǔ)言的對(duì)比2022/12/27史忠植邏輯基礎(chǔ)6邏輯程序語(yǔ)言邏輯符號(hào)2023/1/5史忠植邏輯基礎(chǔ)7

一個(gè)證明是一個(gè)語(yǔ)法結(jié)構(gòu)，它由符號(hào)串根據(jù)一定的規(guī)則組成。它包括假設(shè)和結(jié)論。在公理化邏輯中，邏輯給出一個(gè)邏輯公理和推理規(guī)則的集合。推理規(guī)則是可以從一個(gè)語(yǔ)句的集合得到另一語(yǔ)句的集合。

公理化邏輯中的證明就是一個(gè)語(yǔ)句序列，使得其中的每個(gè)語(yǔ)句要么是邏輯公理，要么是一個(gè)假設(shè)，要么是由前面的語(yǔ)句通過(guò)推理規(guī)則得到的。證明2022/12/27史忠植邏輯基礎(chǔ)7一個(gè)證2023/1/5史忠植邏輯基礎(chǔ)8

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

?，稱(chēng)由可推導(dǎo)出的，或可證明的。如果在沒(méi)有任何假設(shè)下是可推導(dǎo)出的，則記為?，稱(chēng)為可證明的。稱(chēng)一個(gè)假設(shè)是不協(xié)調(diào)的，如果存在一個(gè)語(yǔ)句使得和的否定均可由推導(dǎo)得出。稱(chēng)一個(gè)邏輯系統(tǒng)是一致的，或相容的(consistent)，如果不存在邏輯系統(tǒng)的公式A，使得?A與??A同時(shí)成立。證明(語(yǔ)法)2022/12/27史忠植邏輯基礎(chǔ)8在語(yǔ)法2023/1/5史忠植邏輯基礎(chǔ)9

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

?

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

，有I

?

蘊(yùn)含I

?

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

?，我們稱(chēng)為的一個(gè)邏輯結(jié)果。解釋(語(yǔ)義)2022/12/27史忠植邏輯基礎(chǔ)9語(yǔ)言的解釋是2023/1/5史忠植邏輯基礎(chǔ)10可靠性(reliable)一個(gè)邏輯是可靠的，如果它的證明保持真假值，即在任何解釋I下，如果I是的模型，且可由推導(dǎo)出，則I也是的一個(gè)模型。即，一個(gè)邏輯是可靠的，如果對(duì)任何語(yǔ)句集合和語(yǔ)句，

?蘊(yùn)涵

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

?蘊(yùn)涵

?。如果一個(gè)邏輯是完備的，則該邏輯的證明系統(tǒng)已強(qiáng)到可以推出任何永真式。G?del完備性定理：一階邏輯是完備的2022/12/27史忠植邏輯基礎(chǔ)10可靠性(relia2023/1/5史忠植邏輯基礎(chǔ)11可判定的一個(gè)邏輯稱(chēng)為是可判定的(decidable)，如果存在一個(gè)算法對(duì)邏輯中的任一公式A，可確定?

A是否成立。否則，稱(chēng)為是不可判定的(undecidable)。如果上述算法雖不一定存在，卻有一個(gè)過(guò)程，可對(duì)該系統(tǒng)的定理做出肯定的判斷，但對(duì)非定理的公式過(guò)程未必終止，因而未必能作出判斷。這時(shí)稱(chēng)邏輯是半可判定的?？膳卸ㄐ砸浑A邏輯是不可判定的，但它是半可判定的。2022/12/27史忠植邏輯基礎(chǔ)11可判定的可判定性一

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

命題邏輯命題是可以確定其真假的陳述句。Bolle提出了布爾代數(shù)。語(yǔ)言:

?，； 公式，原子公式公理模式:

◆(A

(B

A))

◆((A

(B

C))((A

B)(A

C)))

◆(((?A))(?B)(B

A))推理規(guī)則:分離規(guī)則(modusponens，MP規(guī)則)2023/1/5史忠植邏輯基礎(chǔ)13命題邏輯命題是可以確定其真假的陳述句。2022/12/27史謂詞邏輯(一階邏輯)Frege謂詞演算語(yǔ)言:

?，，，，(，)；常元，變?cè)?，函詞，謂詞；公式公理模式:

◆(A

(B

A))

◆((A

(B

C))((A

B)(A

C)))

◆(((?A)(?B))(B

A))

◆vAAtv(t對(duì)A中變?cè)獀可代入)

◆v(AB)(vAvB)

◆AvA(v在A中無(wú)自由出現(xiàn))推理規(guī)則:分離規(guī)則2023/1/5史忠植邏輯基礎(chǔ)14謂詞邏輯(一階邏輯)Frege謂詞演算2022/12/27史謂詞邏輯與命題邏輯的區(qū)別2023/1/5史忠植邏輯基礎(chǔ)15謂詞邏輯給出了原子語(yǔ)句的內(nèi)部結(jié)構(gòu)，將原子公式看作是事物直接的關(guān)系；它引入了“推廣”(泛化)，加強(qiáng)了邏輯的表示能力和推理能力。這樣，我們可以說(shuō)某種性質(zhì)對(duì)某個(gè)對(duì)象是成立的，或?qū)λ械膶?duì)象成立，或不對(duì)任何對(duì)象成立。謂詞邏輯與命題邏輯的區(qū)別2022/12/27史忠植邏輯基邏輯程序設(shè)計(jì)歸結(jié)原理(消解原理)Horn邏輯Prolog邏輯程序設(shè)計(jì)語(yǔ)言2023/1/5史忠植邏輯基礎(chǔ)16邏輯程序設(shè)計(jì)歸結(jié)原理(消解原理)2022/12/27史忠植歸結(jié)原理例：

C1=?P∨Q∨R C2=P∨Q則C1與C2歸結(jié)后的結(jié)果為：Q∨R若子句集S能導(dǎo)出空子句?(有否證)，則稱(chēng)S是不可滿(mǎn)足的。反證法：S?AiffS?A

??2023/1/5史忠植邏輯基礎(chǔ)17歸結(jié)原理例：2022/12/27史忠植邏輯基礎(chǔ)17Horn邏輯文字：原子公式(正文字)或原子公式的否定(負(fù)文字)。P,Q,?R子句：若干文字的析取。?P∨Q∨RHorn子句：子句L1∨L2∨…∨Ln中如果至多只含一個(gè)正文字，那么該子句稱(chēng)為Horn子句。Horn子句P∨?Q1∨?Q2∨…∨?Qn通常表示為：PQ1,Q2,…,Qn2023/1/5史忠植邏輯基礎(chǔ)18Horn邏輯文字：原子公式(正文字)或原子公式的否定(負(fù)文字Horn子句的類(lèi)型2023/1/5史忠植邏輯基礎(chǔ)19

◆過(guò)程：PQ1,Q2,…,Qn

◆事實(shí)：

P

◆目標(biāo)：Q1,Q2,…,Qn

◆空子句：?例:

◆過(guò)程：AT(dog,x)

AT(Zhang,x)

◆事實(shí)：AT(Zhang,train)

◆目標(biāo)：AT(dog,train)

首先目標(biāo)中過(guò)程調(diào)用AT(dog,train)與過(guò)程名AT(dog,x)匹配，合一為{train/x}，調(diào)用過(guò)程AT(Zhang,x)，從而產(chǎn)生新目標(biāo)

AT(Zhang,train)，與事實(shí)匹配，產(chǎn)生目標(biāo)?。因而調(diào)用成功，輸出“是”。Horn子句的類(lèi)型2022/12/27史忠植邏輯基礎(chǔ)19

PrologProlog(Programminginlogic)語(yǔ)言是以Horn子句邏輯為基礎(chǔ)的高級(jí)程序設(shè)計(jì)語(yǔ)言。1972年，法國(guó)馬賽大學(xué)的Alain.Colmerauer提出了Prolog的雛型。1975年，Prolog被用于問(wèn)題求解系統(tǒng)。此后，它在許多領(lǐng)域獲得了應(yīng)用，如關(guān)系數(shù)據(jù)庫(kù)、定理證明、智能問(wèn)題求解、計(jì)算機(jī)輔助設(shè)計(jì)、規(guī)劃生成等領(lǐng)域。2023/1/5史忠植邏輯基礎(chǔ)20PrologProlog(ProgramminginlProlog的構(gòu)成事實(shí)：關(guān)于對(duì)象性質(zhì)和關(guān)系的事實(shí)語(yǔ)句；student(john)，married(tom,mary)規(guī)則：關(guān)于對(duì)象性質(zhì)和關(guān)系的定義規(guī)則語(yǔ)句；它與事實(shí)的不同在于，規(guī)則所定義的性質(zhì)、關(guān)系依賴(lài)與其它的性質(zhì)和關(guān)系，因此規(guī)則呈蘊(yùn)涵語(yǔ)句形式。

B:—

A “如果A則B”bird(x):—animal(x)，has(x,feather)問(wèn)題：關(guān)于對(duì)象性質(zhì)或關(guān)系的詢(xún)問(wèn)。

?—student(john)

?—married(mary，x)2023/1/5史忠植邏輯基礎(chǔ)21Prolog的構(gòu)成事實(shí)：關(guān)于對(duì)象性質(zhì)和關(guān)系的事實(shí)語(yǔ)句；2022023/1/5史忠植邏輯基礎(chǔ)22Prolog的執(zhí)行方式搜索：在程序中自上而下地搜索事實(shí)和規(guī)則；匹配：將目標(biāo)中的項(xiàng)與事實(shí)和規(guī)則進(jìn)行匹配；回溯：當(dāng)目標(biāo)中一項(xiàng)失敗時(shí)，如果目標(biāo)中有已經(jīng)成功的的項(xiàng)(應(yīng)在失敗項(xiàng)的左邊)，那末就重新調(diào)用這些成功項(xiàng)中最右邊的一個(gè)，謀求新的成功。2022/12/27史忠植邏輯基礎(chǔ)22Prolog的執(zhí)行2023/1/5史忠植邏輯基礎(chǔ)23Prolog語(yǔ)言的基本文法Prolog語(yǔ)言的最基本語(yǔ)言成分是項(xiàng)(term)，一個(gè)項(xiàng)或者是常量，或者是變量，或者是一個(gè)結(jié)構(gòu)。常量：是指對(duì)象和對(duì)象之間的特定關(guān)系的名；

整數(shù)，如0，22，1586等；

原子，如John，student，likes，sister-of變量：表示任意的對(duì)象，它與FOL中的變?cè)嗤?/p>

Prolog中變量可以用大寫(xiě)字母，下劃線(xiàn)，以及由它們開(kāi)頭的字母串。如X,Y,Answer,_value等。結(jié)構(gòu)：是常量和變量的序列，它由一個(gè)函子(函詞或謂詞)和該函子的自變量所組成。如：likes(john,X) married(mary,jack)2022/12/27史忠植邏輯基礎(chǔ)23Prolog語(yǔ)言的例子2023/1/5史忠植邏輯基礎(chǔ)24(1)likes(bell,sports)(2)likes(mary,smith)(3)likes(mary,sports)(4)likes(jones,smith)(5)friend(john,X):—likes(X,sports),likes(X,smith)(規(guī)則)(6)?—friends(john,Y) (問(wèn)題)(事實(shí))(7)?—likes(X,sports),likes(X,smith)(8)?—likes(bell,smith) (bell/X)(7)?—likes(X,sports),likes(X,smith)(8)?—likes(mary,smith) (mary/X)Y=mary，John與Mary是朋友例子2022/12/27史忠植邏輯基礎(chǔ)24(事實(shí))(7)2023/1/5史忠植邏輯基礎(chǔ)25Prolog的基本特點(diǎn)Horn子句邏輯是Prolog的基礎(chǔ)。Prolog既是一種邏輯程序設(shè)計(jì)語(yǔ)言，又是一個(gè)邏輯系統(tǒng)。Prolog是一種描述性語(yǔ)言，它是一種面向問(wèn)題的語(yǔ)言，你只需要告訴它要做什么，即給出問(wèn)題的形式描述，而不需要知道應(yīng)該如何做。Prolog完全依靠匹配、回溯來(lái)進(jìn)行搜索。Prolog的求解過(guò)程是一個(gè)尋求否證的消解過(guò)程。Prolog也使用元語(yǔ)言種的謂詞，有很強(qiáng)的描述能力。Prolog采用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)——項(xiàng)，它包含控制成分，且有專(zhuān)門(mén)進(jìn)行數(shù)值計(jì)算和符號(hào)處理的模塊。2022/12/27史忠植邏輯基礎(chǔ)25Prolog的基本非單調(diào)邏輯單調(diào)邏輯非單調(diào)邏輯區(qū)別2023/1/5史忠植邏輯基礎(chǔ)26非單調(diào)邏輯單調(diào)邏輯2022/12/27史忠植邏輯基礎(chǔ)26單調(diào)邏輯在現(xiàn)有知識(shí)的基礎(chǔ)上，通過(guò)嚴(yán)密的邏輯論證和推理獲得的新知識(shí)必須與已有的知識(shí)相一致。A，AB

B推理系統(tǒng)的定理集合隨著推理過(guò)程的進(jìn)行而單調(diào)地增大。單調(diào)性：

(1)∈

Th() (2)若1?

2，則Th(1)?Th(2) (3)Th(Th())＝Th() (不動(dòng)點(diǎn))2023/1/5史忠植邏輯基礎(chǔ)27單調(diào)邏輯在現(xiàn)有知識(shí)的基礎(chǔ)上，通過(guò)嚴(yán)密的邏輯論證和推理獲得的新2023/1/5史忠植邏輯基礎(chǔ)28非單調(diào)邏輯推理系統(tǒng)的定理集合并不隨著推理過(guò)程的進(jìn)行而單調(diào)地增大，新推出的定理很可能會(huì)否定、改變?cè)瓉?lái)的一些定理，使得原來(lái)能夠解釋的某些現(xiàn)象變得不能解釋了。新規(guī)則：

(4)

??P (不動(dòng)點(diǎn))2022/12/27史忠植邏輯基礎(chǔ)28非單調(diào)邏輯推理系統(tǒng)默認(rèn)邏輯1980年，Reiter提出了默認(rèn)邏輯(DefaultLogic)。

“一般情況下鳥(niǎo)是會(huì)飛的”

“鴕鳥(niǎo)不會(huì)飛”

“企鵝不會(huì)飛”2023/1/5史忠植邏輯基礎(chǔ)29默認(rèn)邏輯1980年，Reiter提出了默認(rèn)邏輯(Defaul2023/1/5史忠植邏輯基礎(chǔ)30默認(rèn)規(guī)則一個(gè)默認(rèn)規(guī)則是如下形式的規(guī)則：

(x):稱(chēng)為前提條件

i(x):稱(chēng)為默認(rèn)條件，或檢驗(yàn)條件

(x):稱(chēng)為結(jié)論為簡(jiǎn)便，通常情況下可以省略檢驗(yàn)條件中的M。規(guī)則的使用：如果規(guī)則的前提條件滿(mǎn)足，且現(xiàn)有的知識(shí)導(dǎo)不出檢驗(yàn)條件的否定?i(x)，則可以得出結(jié)論成立。2022/12/27史忠植邏輯基礎(chǔ)30默認(rèn)規(guī)則一個(gè)默2023/1/5史忠植邏輯基礎(chǔ)31默認(rèn)理論一個(gè)默認(rèn)理論由兩個(gè)部分組成，即默認(rèn)規(guī)則集D和公式集W，一般用二元組來(lái)表示

＝<D,W>若D中的規(guī)則是閉規(guī)則時(shí)，則為閉默認(rèn)理論。定義：設(shè)＝<D,W>為一閉默認(rèn)理論，為關(guān)于D的一個(gè)算子，作用于任意的命題集合S，而其值為滿(mǎn)足下列三個(gè)性質(zhì)的最小命題集合(S)：

(1)W

(S) (2)Th((S))=(S)，其中Th((S))={A|(S)?

A} (3)如果D中有規(guī)則 ，且∈(S)，?1,…,?m?

S，那么∈(S)2022/12/27史忠植邏輯基礎(chǔ)31默認(rèn)理論一個(gè)默2023/1/5史忠植邏輯基礎(chǔ)32默認(rèn)理論的擴(kuò)充定義：對(duì)命題集合E，如果(E)=E，則E稱(chēng)為關(guān)于D的算子的不動(dòng)點(diǎn)(fixpoint)。此時(shí)稱(chēng)E為默認(rèn)理論＝<D,W>的一個(gè)擴(kuò)充(extension)。例1：設(shè)D

＝{ }，W

＝，計(jì)算默認(rèn)理論＝<D,W>的擴(kuò)充。＝<D,W>有唯一的擴(kuò)充E

＝Th({?B,?F})。2022/12/27史忠植邏輯基礎(chǔ)32默認(rèn)理論的擴(kuò)充定義默認(rèn)理論的擴(kuò)充2023/1/5史忠植邏輯基礎(chǔ)33例2：設(shè)D

＝{ }，W

＝{B,CF∨A,A∧C

?E}，計(jì)算默認(rèn)理論＝<D,W>的擴(kuò)充。＝<D,W>有三個(gè)擴(kuò)充E1

＝Th(W{A,C})E2

＝Th(W{A,E})E3

＝Th(W{C,E,G})默認(rèn)理論的擴(kuò)充2022/12/27史忠植邏輯基礎(chǔ)33例22023/1/5史忠植邏輯基礎(chǔ)34限定推理1980年，McCarthy提出了一種非單調(diào)的推理——限定推理(Circumscription)?；舅枷耄簭哪承┦聦?shí)A出發(fā)能夠推出具有某一性質(zhì)的P的對(duì)象就是滿(mǎn)足性質(zhì)P的全部對(duì)象。只有當(dāng)發(fā)現(xiàn)其它對(duì)象也具有該性質(zhì)時(shí)，才修改這種看法。2022/12/27史忠植邏輯基礎(chǔ)34限定推理1980年限定邏輯2023/1/5史忠植邏輯基礎(chǔ)35

限定邏輯CIRC是一種極小化邏輯。下面，從一個(gè)基于極小模型定義的命題限定出發(fā)，給出限定的基本定義,進(jìn)而給出一階限定的基本結(jié)果，并將它推廣。定義2.1設(shè)L0是一個(gè)命題語(yǔ)言，p1,p2是在命題語(yǔ)言L(fǎng)0

中的兩個(gè)賦值。稱(chēng)p1小于p2

，記為p1p2,當(dāng)且僅當(dāng)對(duì)任一命題變?cè)獂,如果p1(x)=l,則p2(x)=l。限定邏輯2022/12/27史忠植邏輯基礎(chǔ)35限限定邏輯2023/1/5史忠植邏輯基礎(chǔ)36

定義2.2設(shè)A

是一個(gè)公式，稱(chēng)A的一個(gè)賦值p是極小的，當(dāng)且僅當(dāng)不存在A的其它賦值p'使得p'p。顯然,是一個(gè)偏序關(guān)系。p1

p2表示p1包含的真命題比p2

少。極小賦值包含的真命題極小。定義2.3極小后承M。設(shè)A,B是兩個(gè)公式，A

M

B

當(dāng)且僅當(dāng)B在所有A

的極小模型中都為真。極小模型是非單調(diào)的，它以命題的極小化作為優(yōu)先模型的準(zhǔn)則。限定邏輯2022/12/27史忠植邏輯基礎(chǔ)36定限定邏輯2023/1/5史忠植邏輯基礎(chǔ)37

定義2.4設(shè)A是一個(gè)包含命題集P={p1,p2,...,pn}的公式，一個(gè)A的賦值p稱(chēng)為

Z-極小賦值，當(dāng)且僅當(dāng)不存在A的其它賦值p‘使得pp’,定義如下：設(shè)p1,p2

是兩個(gè)賦值，p1

Z-p2

當(dāng)且僅當(dāng)對(duì)任一zZ,

若p1

(Z)=l,則p2

(Z)=l。

限定邏輯2022/12/27史忠植邏輯基礎(chǔ)37定限定邏輯2023/1/5史忠植邏輯基礎(chǔ)38

定義2.5命題限定P

或CIRC(A,P)。設(shè)A是一個(gè)包含命題集的公式，是一個(gè)公式，A

P

當(dāng)且僅當(dāng)

在所有A的

p-

極小賦值中都為真。

定理2.1Ap當(dāng)且僅當(dāng)A

P

限定邏輯2022/12/27史忠植邏輯基礎(chǔ)38定義限定邏輯2023/1/5史忠植邏輯基礎(chǔ)39

定義2.6令L是一個(gè)一階語(yǔ)言，T是一個(gè)L的公式，它包含謂詞元組集。設(shè)M[T]和M*[T]是公式T的兩個(gè)模型。定義M*[T]優(yōu)先于M[T],

記為M*[T]

M[T]，當(dāng)且僅當(dāng)

(1)M和M*有相同的對(duì)象域，

(2)除外，公式T中所有的其它關(guān)系和函數(shù)常數(shù)在M和M*都有相同的解釋?zhuān)?/p>

(3)在M*中的外延是在M中的子集。限定邏輯2022/12/27史忠植邏輯基礎(chǔ)39定義限定邏輯2023/1/5史忠植邏輯基礎(chǔ)40

一個(gè)理論T的模型M稱(chēng)為優(yōu)先的，當(dāng)且僅當(dāng)不存在T的其它模型M'使得M'

M。定義2.7Mm是的最小模型，當(dāng)且僅當(dāng)

MMm,M=Mm

限定邏輯2022/12/27史忠植邏輯基礎(chǔ)40限定邏輯2023/1/5史忠植邏輯基礎(chǔ)41

例如設(shè)論域D={1,2}T=xy(P(y)Q(x,y))=[(P(1)Q(1,1))(P(2)Q(1,2))][(P(1)Q(2,1))(P(2)Q(2,2))]M:P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)TTFTFTM*:P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)FTFTFT

限定邏輯2022/12/27史忠植邏輯基礎(chǔ)41例如2023/1/5史忠植邏輯基礎(chǔ)42真值維護(hù)系統(tǒng)TMS1979年，Doyle提出了一種非單調(diào)推理系統(tǒng)——真值維護(hù)系統(tǒng)(TruthMaintenanceSystem)真值維護(hù)系統(tǒng)是大型推理系統(tǒng)的的一個(gè)子系統(tǒng)，實(shí)現(xiàn)知識(shí)庫(kù)中信念(belief)的修改與維護(hù)。其基本問(wèn)題有：必須在不完全的、有限的信息基礎(chǔ)上作出假設(shè)的決策，使得該假設(shè)成為知識(shí)庫(kù)的信念；當(dāng)這些決策的結(jié)論被以后的事實(shí)證明為錯(cuò)誤時(shí)，如何對(duì)其信念進(jìn)行修正。2022/12/27史忠植邏輯基礎(chǔ)42真值維護(hù)系統(tǒng)TMS2023/1/5史忠植邏輯基礎(chǔ)43基本數(shù)據(jù)結(jié)構(gòu):

結(jié)點(diǎn)：表示信念

理由：表示信念的原因信念既包括已知的知識(shí)，也包括假設(shè)的知識(shí)?；静僮鳎?/p>

新結(jié)點(diǎn)的形成——將信念賦予該結(jié)點(diǎn)；

新理由的加入——把某個(gè)信念與該結(jié)點(diǎn)聯(lián)接起來(lái)實(shí)現(xiàn)過(guò)程： 默認(rèn)假設(shè)的形成； 相關(guān)性回溯過(guò)程。真值維護(hù)系統(tǒng)TMS2022/12/27史忠植邏輯基礎(chǔ)43基本數(shù)據(jù)結(jié)構(gòu):基本2023/1/5史忠植邏輯基礎(chǔ)44信念知識(shí)表示每一個(gè)命題或規(guī)則均稱(chēng)為結(jié)點(diǎn)，它分為兩類(lèi)：

IN-結(jié)點(diǎn)：相信為真

OUT-結(jié)點(diǎn)：不相信為真，或無(wú)理由相信為真， 或當(dāng)前沒(méi)有任何有效的理由。每個(gè)結(jié)點(diǎn)附有理由表，表示具體結(jié)點(diǎn)的有效性：

支持表SL：所在結(jié)點(diǎn)的信念的原因，理由；

條件證明CP：出現(xiàn)矛盾的原因。2022/12/27史忠植邏輯基礎(chǔ)44信念知識(shí)表示每一個(gè)2023/1/5史忠植邏輯基礎(chǔ)45(SL(<IN-結(jié)點(diǎn)表>)(<OUT-結(jié)點(diǎn)表>))IN-結(jié)點(diǎn)表中的IN-結(jié)點(diǎn)表示知識(shí)庫(kù)中的已知知識(shí);OUT-結(jié)點(diǎn)表中的OUT-結(jié)點(diǎn)表示這些結(jié)點(diǎn)的否定。例1:(1)現(xiàn)在是夏天 (SL()())(2)天氣很潮濕 (SL(1)())結(jié)點(diǎn)(1)不依賴(lài)于任何別的結(jié)點(diǎn)中的當(dāng)前信念或默認(rèn)信念,因而這種結(jié)點(diǎn)稱(chēng)為前提;結(jié)點(diǎn)(2)則依賴(lài)于當(dāng)前結(jié)點(diǎn)(1)的信念.所以，與一階邏輯不同的是,TMS可以撤消前提,并可以對(duì)知識(shí)庫(kù)作適當(dāng)修改.（1）支持表SL信念知識(shí)表示2022/12/27史忠植邏輯基礎(chǔ)45(SL(<IN-結(jié)2023/1/5史忠植邏輯基礎(chǔ)46例2:

(1)現(xiàn)在是夏天 (SL()()) (2)天氣很潮濕 (SL(1)(3)) (3)天氣很干燥若結(jié)點(diǎn)(1)是IN,結(jié)點(diǎn)(3)是OUT,則結(jié)點(diǎn)(2)才為IN.若在某個(gè)時(shí)刻出現(xiàn)結(jié)點(diǎn)(3)的證據(jù),則結(jié)點(diǎn)(2)就變?yōu)镺UT,因?yàn)樗辉儆幸粋€(gè)有效的證實(shí).象結(jié)點(diǎn)(2)這樣的結(jié)點(diǎn)稱(chēng)為假設(shè),它與非空的OUT結(jié)點(diǎn)表的SL證實(shí)有關(guān).OUT結(jié)點(diǎn)(3)是結(jié)點(diǎn)(2)的證實(shí)的一部分.但如果結(jié)點(diǎn)(3)不存在,就不能這樣表示了.在TMS中,它僅利用證實(shí)來(lái)維持一個(gè)相容的信念數(shù)據(jù)庫(kù),而它本身并不產(chǎn)生證實(shí).信念知識(shí)表示2022/12/27史忠植邏輯基礎(chǔ)46例2:信念知識(shí)表示2023/1/5史忠植邏輯基礎(chǔ)47(CP<結(jié)論><IN-假設(shè)><OUT-假設(shè)>)如果結(jié)論結(jié)點(diǎn)為IN-結(jié)點(diǎn),以及下列條件成立: (1)IN假設(shè)中的每個(gè)結(jié)點(diǎn)都是IN-結(jié)點(diǎn); (2)OUT-假設(shè)中的每個(gè)結(jié)點(diǎn)都是OUT-結(jié)點(diǎn).那么條件證明CP是有效的.一般說(shuō)來(lái),OUT-假設(shè)總是空集.TMS要求假設(shè)集劃分成兩個(gè)不相交的子集,分別為不導(dǎo)致矛盾的假設(shè)和導(dǎo)致矛盾的假設(shè).通常只要在IN-假設(shè)中的結(jié)點(diǎn)為IN,OUT-假設(shè)中的結(jié)點(diǎn)為OUT,則結(jié)論結(jié)點(diǎn)為IN.（2）條件證明CP信念知識(shí)表示2022/12/27史忠植邏輯基礎(chǔ)47(CP<結(jié)論>2023/1/5史忠植邏輯基礎(chǔ)48默認(rèn)假設(shè)

令{F1,F2,…,Fn}表示所有可能的侯選的默認(rèn)假設(shè)結(jié)點(diǎn)集,G表示選擇默認(rèn)假設(shè)的原因的結(jié)點(diǎn),即由G引起在{F1,…,Fn}中進(jìn)行默認(rèn)選擇.這樣我們結(jié)合結(jié)點(diǎn)Node(Fi)以如下理由:(SL(G)(F1,…,Fi-1

,Fi+1,…,Fn))而選取Fi為默認(rèn)假設(shè).如果不存在任何其它關(guān)于如何進(jìn)行選擇的信息，則可以認(rèn)為除Fi之外其它任何時(shí)候選都不是可信的．這樣Fi為IN,其它Fj(ij)均為OUT.但如果接收到一個(gè)有效的理由支持某個(gè)其它的侯選Fj,則Fj就為IN,而導(dǎo)致Fi的假設(shè)失敗而變?yōu)镺UT.2022/12/27史忠植邏輯基礎(chǔ)48默認(rèn)假設(shè)令{F2023/1/5史忠植邏輯基礎(chǔ)49相關(guān)回溯當(dāng)知識(shí)庫(kù)中出現(xiàn)不一致時(shí),TMS將尋找并刪除已做的一個(gè)不正確的默認(rèn)邏輯,恢復(fù)一致性.它包括三個(gè)步驟: (1)從產(chǎn)生的矛盾結(jié)點(diǎn)開(kāi)始,回溯跟蹤該矛盾結(jié)點(diǎn)的理由充足的支持以尋找矛盾的假設(shè)集,并從中去掉至少一個(gè)假設(shè)信念以消除矛盾. (2)構(gòu)造一個(gè)結(jié)點(diǎn)記錄矛盾產(chǎn)生的原因. (3)從S中選取假設(shè)A(即不合理假設(shè)),并證實(shí)列在其理由充足的支持條件中的一個(gè)OUT-結(jié)點(diǎn).2022/12/27史忠植邏輯基礎(chǔ)49相關(guān)回溯當(dāng)知識(shí)2023/1/5史忠植邏輯基礎(chǔ)50

(4)矛盾 (SL(1,3)()) (周三14:00沒(méi)有空會(huì)議室)例3:

(1)會(huì)議日期為星期三 (SL()(2)) (2)會(huì)議日期不應(yīng)是星期三

(3)會(huì)議時(shí)間為14:00 (SL(32,40,61)())

(5)不相容 (CP4(1,3)())

(2)會(huì)議日期不應(yīng)是星期三 (SL(5)())結(jié)點(diǎn)(2)與結(jié)點(diǎn)(5)為IN,就引起結(jié)點(diǎn)(1)為OUT,因?yàn)榻Y(jié)點(diǎn)(1)的證實(shí)依賴(lài)于結(jié)點(diǎn)(2)是OUT.結(jié)點(diǎn)(4)現(xiàn)在也變成OUT.進(jìn)而矛盾就消除了.相關(guān)回溯2022/12/27史忠植邏輯基礎(chǔ)50 (4)矛盾 2023/1/5史忠植邏輯基礎(chǔ)51情景演算

情景演算是一種一階邏輯語(yǔ)言，主要是用來(lái)表示動(dòng)態(tài)變化的世界的。世界的所有變化過(guò)程都是“動(dòng)作”的結(jié)果。一個(gè)可能世界歷史可以簡(jiǎn)單表示為動(dòng)作的序列，它是通過(guò)稱(chēng)之為情景的一階項(xiàng)所表示的。

常量S0表示初始情景，即動(dòng)作還沒(méi)有發(fā)生時(shí)的情景。

do(,s)表示在情景s中執(zhí)行動(dòng)作之后的后繼情景。

do(put(A,B),s)表示當(dāng)世界狀態(tài)為s時(shí)，將A放到B上的結(jié)果這種情景。

do(putdown(A)),do(walk(L)),do(pickup(A))是一種表示世界歷史由動(dòng)作序列[pickup(A),walk(L),

putdown(A)]所組成的，它們按照從右到左的方式組織。

2022/12/27史忠植邏輯基礎(chǔ)51情景演算情2023/1/5史忠植邏輯基礎(chǔ)52定義1定義Lsitcalc語(yǔ)言的動(dòng)作理論D為如下形式：D=∑?Dss?Dap

?Duna?DSo

其中：

∑：基礎(chǔ)的、針對(duì)情景演算的獨(dú)立于領(lǐng)域的公理。

Dap：動(dòng)作前提條件公理；

Dss：后續(xù)狀態(tài)公理；

Duna：針對(duì)原子動(dòng)作的唯一命名公理；

DSo：描述初始情形的公理。

情景演算2022/12/27史忠植邏輯基礎(chǔ)52定義1定義Lsi2023/1/5史忠植邏輯基礎(chǔ)53

基于情景演算的一些基本理論和方法，我們利用它們來(lái)刻畫(huà)主體的復(fù)雜動(dòng)作和過(guò)程，將主體的各個(gè)部件加以描述。

<1>原子動(dòng)作Do(a,s,s)Poss(a[s],s)∧s=do(a[s],s)

<2>檢驗(yàn)動(dòng)作Do(φ?,s,s)φ[s]∧s=s

<3>順序動(dòng)作Do([δ1,δ2],s,s)(?s*).Do([δ1],s,s*)∧Do([δ2],s*,s)def＝def＝def＝情景演算2022/12/27史忠植邏輯基礎(chǔ)53 基于情景演算2023/1/5史忠植邏輯基礎(chǔ)54<4>兩個(gè)動(dòng)作的不確定選擇Do((δ1|δ2),s,s)(?s*).Do(δ1,s,s)∨Do(δ2,s,s)def＝<5>動(dòng)作參數(shù)的不確定選擇Do((πx)δ(x),s,s)(?x).Do(δ(x),s,s)

def＝<6>不確定反復(fù)Do(δ*,s,s) (?P).{(?s1)P(s1,s1)∧(?s1,s2,s3) [P(s1,s2)∧Do(δ,s2,s3)?P(s1,s3)]} ?P(s,s)def＝情景演算2022/12/27史忠植邏輯基礎(chǔ)54<4>兩個(gè)動(dòng)作的2023/1/5史忠植邏輯基礎(chǔ)55動(dòng)作理論與情景演算的研究◆MaCarthy針對(duì)動(dòng)態(tài)領(lǐng)域中的問(wèn)題求解和邏輯程序設(shè)計(jì)提出了情景演算。◆

Reiter，F(xiàn)angzhenLin，Pirria，Lifschitz等人主要將情景演算進(jìn)行了一些擴(kuò)充，對(duì)狀態(tài)約束、動(dòng)作理論、動(dòng)態(tài)關(guān)系等方面進(jìn)行了深入的研究，并以數(shù)據(jù)庫(kù)、機(jī)器人等動(dòng)態(tài)領(lǐng)域?yàn)楸尘埃隽艘恍┻壿嫵绦蛟O(shè)計(jì)以及應(yīng)用等研究。

◆

Levesque和Reiter提出了一種新的動(dòng)態(tài)邏輯設(shè)計(jì)語(yǔ)言

Golog/ConGolog◆Baral等人重點(diǎn)對(duì)狀態(tài)的描述、動(dòng)作的表示與推理以及動(dòng)態(tài)領(lǐng)域中的知識(shí)表示等方面做了一些工作，提出了一種邏輯程序設(shè)計(jì)語(yǔ)言

A-Prolog，

2022/12/27史忠植邏輯基礎(chǔ)55動(dòng)作理論與情景演算2023/1/5史忠植高級(jí)人工智能56描述邏輯

DescriptionLogics◆

什么是描述邏輯？◆為什么用描述邏輯？◆描述邏輯的研究進(jìn)展◆描述邏輯的體系結(jié)構(gòu)◆描述邏輯的構(gòu)造算子◆描述邏輯的推理問(wèn)題◆我們的工作2022/12/27史忠植高級(jí)人工智能56描述邏輯2023/1/5史忠植高級(jí)人工智能57什么是描述邏輯(DL)？

一種基于對(duì)象的知識(shí)表示的形式化，也叫概念表示語(yǔ)言或術(shù)語(yǔ)邏輯。建立在概念和關(guān)系(Role)之上

－概念解釋為對(duì)象的集合 －關(guān)系解釋為對(duì)象之間的二元關(guān)系源于語(yǔ)義網(wǎng)絡(luò)和KL-ONE是一階邏輯FOL的一個(gè)可判定的子集具有合適定義的語(yǔ)義(基于邏輯)2022/12/27史忠植高級(jí)人工智能57什么是描述邏輯2023/1/5史忠植高級(jí)人工智能58描述邏輯的特點(diǎn)◆是以往表示工具的邏輯重構(gòu)和統(tǒng)一形式化 －

框架系統(tǒng)

(Frame-basedsystems)

－

語(yǔ)義網(wǎng)絡(luò)

(SemanticNetworks)

－

面向?qū)ο蟊硎?/p>

(OOrepresentation)

－

語(yǔ)義數(shù)據(jù)模型

(Semanticdatamodels)

－

類(lèi)型系統(tǒng)

(Typesystems)

－

特征邏輯

(FeatureLogics)◆

具有很強(qiáng)的表達(dá)能力◆是可判定的，總能保證推理算法終止2022/12/27史忠植高級(jí)人工智能58描述邏輯的特點(diǎn)2023/1/5史忠植高級(jí)人工智能59描述邏輯的應(yīng)用

◆概念建?！舨樵?xún)優(yōu)化和視圖維護(hù)◆自然語(yǔ)言語(yǔ)義◆智能信息集成◆信息存取和智能接口◆工程的形式化規(guī)范◆術(shù)語(yǔ)學(xué)和本體論◆規(guī)劃◆…2022/12/27史忠植高級(jí)人工智能59描述邏輯的應(yīng)用2023/1/5史忠植高級(jí)人工智能60為什么用描述邏輯？若直接使用一階邏輯，而不附加任何約束，則：◆知識(shí)的結(jié)構(gòu)將被破壞，這樣就不能用來(lái)驅(qū)動(dòng)推理◆對(duì)獲得可判定性和有效的推理問(wèn)題來(lái)說(shuō)，其表達(dá)能力太高，（也許是太抽象了）◆對(duì)興趣表達(dá)，但仍然可判定的理論，其推理能力太低。DL的重要特征是：◆很強(qiáng)的表達(dá)能力；◆可判定性，它能保證推理算法總能停止，并返回正確的結(jié)果。2022/12/27史忠植高級(jí)人工智能60為什么用描述邏2023/1/5史忠植高級(jí)人工智能61在眾多知識(shí)表示的形式化方法中，描述邏輯在十多年來(lái)受到人們的特別關(guān)注，主要原因在于以下三點(diǎn):◆它們有清晰的模型-理論機(jī)制;◆它們很適合于通過(guò)概念分類(lèi)學(xué)來(lái)表示應(yīng)用領(lǐng)域；◆它們提供了很用的推理服務(wù)。它們可以被認(rèn)為是從基于框架的表示形式化向著精確的語(yǔ)義特征方向發(fā)展。此外，描述邏輯將分類(lèi)學(xué)中表示和推理（專(zhuān)業(yè)推理）與在分類(lèi)學(xué)中項(xiàng)的事實(shí)或?qū)嵗谋硎竞屯评恚〝嘌酝评恚﹨^(qū)別開(kāi)來(lái)。為什么用描述邏輯？2022/12/27史忠植高級(jí)人工智能61在眾多知識(shí)表示描述邏輯的研究進(jìn)展2023/1/5史忠植高級(jí)人工智能62◆描述邏輯的基礎(chǔ)研究 研究描述邏輯的構(gòu)造算子、表示和推理的基本問(wèn)題，如可滿(mǎn)足性、包含檢測(cè)、一致性、可判定性等。 一般都在最基本的ALC的基礎(chǔ)上在擴(kuò)展一些構(gòu)造算子，如數(shù)量約束、逆關(guān)系、特征函數(shù)、關(guān)系的復(fù)合等。

TBox和Abox上的推理問(wèn)題、包含檢測(cè)算法等。

Schmidt-Schaub

和Smolka首先建立了基于描述邏輯ALC的Tableau算法，該算法能在多項(xiàng)式時(shí)間內(nèi)判斷描述邏輯ALC概念的可滿(mǎn)足性問(wèn)題。描述邏輯的研究進(jìn)展2022/12/27史忠植高級(jí)人工智能描述邏輯的擴(kuò)展研究2023/1/5史忠植高級(jí)人工智能63

A.Artale和E.Franconi(1998)提出了一個(gè)知識(shí)表示系統(tǒng)，用時(shí)間約束的方法將狀態(tài)、動(dòng)作和規(guī)劃的表示統(tǒng)一起來(lái)。 為了能讓描述邏輯處理模態(tài)詞，F(xiàn).Baader將模態(tài)操作引入描述邏輯，證明了該描述邏輯公式的可滿(mǎn)足性問(wèn)題是可判定的。

Wolter等對(duì)具有模態(tài)算子的描述邏輯進(jìn)行了深入系統(tǒng)的調(diào)查分析，并證明在恒定的領(lǐng)域假設(shè)下多種認(rèn)知和時(shí)序描述邏輯是可判定的。

另外如時(shí)序擴(kuò)展(Artale,Wolter)、模糊擴(kuò)展(Straccia)等。描述邏輯的擴(kuò)展研究2022/12/27史忠植高級(jí)人工智能2023/1/5史忠植高級(jí)人工智能64描述邏輯在許多領(lǐng)域中被作為知識(shí)表示的工具，如 信息系統(tǒng)（Catarci,1993） 數(shù)據(jù)庫(kù)（Borgida,1995;Bergamaschi1992;Sheth,1993） 軟件工程(Devambu,1991)

網(wǎng)絡(luò)智能訪(fǎng)問(wèn)（Levy，

1996；

Blanco，1994） 規(guī)劃（Seida,1992）等

Horrocks對(duì)表達(dá)能力較強(qiáng)的描述邏輯進(jìn)行了研究，并建立了一些邏輯框架和系統(tǒng)，如FaCT，SHIQ等。他和DieterFensel等人將描述邏輯、語(yǔ)義網(wǎng)和DAML結(jié)合起來(lái)，提出了DAML+OIL，其中以描述邏輯作為核心的表示和推理基礎(chǔ)。并在XML及其RDF上面進(jìn)行了擴(kuò)展，用描述邏輯來(lái)研究語(yǔ)義網(wǎng)絡(luò)和本體論。描述邏輯的應(yīng)用研究2022/12/27史忠植高級(jí)人工智能64描述邏輯在許多研究背景語(yǔ)義Web[Bemers-Lee1998,2006]

描述邏輯：OWL的邏輯基礎(chǔ)[Horrocks2003]特點(diǎn)：描述能力+可判定；有效的判定算法和推理機(jī)制。局限：不能處理動(dòng)態(tài)領(lǐng)域中與動(dòng)作相關(guān)的知識(shí)。OWLLiteOWLDLOWLFullSHIF(D)SHOIN(D)不可判定研究背景語(yǔ)義Web[Bemers-Lee1998,22023/1/5史忠植高級(jí)人工智能66描述邏輯的體系結(jié)構(gòu)一個(gè)描述邏輯系統(tǒng)包含四個(gè)基本組成部分：1）表示概念和關(guān)系（Role）的構(gòu)造集2）Tbox——關(guān)于概念術(shù)語(yǔ)的斷言3）Abox——關(guān)于個(gè)體的斷言4）Tbox和Abox上的推理機(jī)制。

2022/12/27史忠植高級(jí)人工智能66描述邏輯的體系2023/1/5史忠植高級(jí)人工智能67◆概念

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

例子：所有在校學(xué)習(xí)的人員的集合構(gòu)成“學(xué)生”概念 又如：孩子，已婚的，哺乳動(dòng)物等概念{x|Student(x)}，{x|Married(x)}◆

關(guān)系(Roles)——屬性(二元謂詞，關(guān)系)例子：朋友，愛(ài)人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}DL的基本元素——概念和關(guān)系2022/12/27史忠植高級(jí)人工智能67◆概念——2023/1/5史忠植高級(jí)人工智能68知識(shí)庫(kù)TBox(模式)Man?Human?MaleHappy-father?Human?

?Has-child.Female?

…Abox(數(shù)據(jù))John:Happy-father<John,Mary>:Has-child推理系統(tǒng)接口2022/12/27史忠植高級(jí)人工智能68TBox(模式TBox語(yǔ)言2023/1/5史忠植高級(jí)人工智能69TBox語(yǔ)言是描述領(lǐng)域結(jié)構(gòu)的公理的集合定義:引入概念的名稱(chēng)A?

C,A

?

CFather?

Man?

?

has-child.HumanHuman?

Animal?

Biped包含：聲明包含關(guān)系的公理C

?

D

(C?

D

C

?

D

，D

?

C)?

has-degree.Masters?

?

has-degree.Bachelors一個(gè)解釋I滿(mǎn)足：C?

D

iffCI

=DI C?

D

iffCI

?

DI一個(gè)解釋I滿(mǎn)足TBoxT

iff它滿(mǎn)足T中的每個(gè)公理(I?T)TBox語(yǔ)言2022/12/27史忠植高級(jí)人工智能69T2023/1/5史忠植高級(jí)人工智能70◆概念斷言

——表示一個(gè)對(duì)象是否屬于某個(gè)概念

a:C例如：Tom是個(gè)學(xué)生，表示為

Tom

:Student 或者 Student(Tom)

John

:Man?

?

has-child.Female◆關(guān)系斷言

——表示兩個(gè)對(duì)象是否滿(mǎn)足一定的關(guān)系

<a,b>:R例如：John有個(gè)孩子叫Mary

<John,

Mary>

:has-childABox語(yǔ)言是描述具體情形的公理的集合ABox語(yǔ)言2022/12/27史忠植高級(jí)人工智能70◆概念斷言語(yǔ)義解釋2023/1/5史忠植高級(jí)人工智能71一個(gè)解釋I滿(mǎn)足：a:

C

iffaI

∈

CI

<a,b>:R

iff<aI,bI>

∈RI一個(gè)解釋I滿(mǎn)足ABoxA

iff它滿(mǎn)足A中的每個(gè)公理記為：I?A一個(gè)解釋I滿(mǎn)足知識(shí)庫(kù)=<T,A

>

iff它滿(mǎn)足T和A

記為：I?語(yǔ)義解釋2022/12/27史忠植高級(jí)人工智能71一個(gè)解2023/1/5史忠植高級(jí)人工智能72

語(yǔ)法和語(yǔ)義構(gòu)造算子語(yǔ)法語(yǔ)義例子原子概念A(yù)AI?△IHuman原子關(guān)系RRI?△I△Ihas-child對(duì)概念C,D和關(guān)系(role)R合取C?DCI∩DIHuman?Male析取C?DCI?

DIDoctor?Lawyer非?C△I\C?Male存在量詞?

R.C{x|?y.<x,y>∈

RI∧y∈CI}?

has-child.Male全稱(chēng)量詞?R.C{x|?y.<x,y>∈

RI

y∈CI}?

has-child.Doctor2022/12/27史忠植高級(jí)人工智能72語(yǔ)法和語(yǔ)義構(gòu)2023/1/5史忠植高級(jí)人工智能73一般地，描述邏輯依據(jù)提供的構(gòu)造算子，在簡(jiǎn)單的概念和關(guān)系上構(gòu)造出復(fù)雜的概念和關(guān)系。通常DL至少包含以下算子： ◆合取(?)，吸取(?)，非(?) ◆量詞約束：存在量詞(?)，全稱(chēng)量詞(?)最基本的DL稱(chēng)之為ALC例如，ALC中概念Happy-father定義為：

Man?

?

has-child.Male

?

?

has-child.Female

?

?has-child.(Doctor?

Lawyer)DL中的構(gòu)造算子2022/12/27史忠植高級(jí)人工智能73一般地，描述邏2023/1/5史忠植高級(jí)人工智能74構(gòu)造算子語(yǔ)法語(yǔ)義例子數(shù)量約束≥nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≥n}≥3

has-child.Male≤nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≤n}≤3

has-child.Male逆R-{<y,x>|<x,y>∈

RI}has-child-傳遞閉包R*(RI)*has-child*DL中的其它算子topT△IMale?

?MaleBottomMan?

?Man另外，有兩個(gè)類(lèi)似于FOL中的全集(true)和空集(false)的算子2022/12/27史忠植高級(jí)人工智能74構(gòu)造算子語(yǔ)法語(yǔ)2023/1/5史忠植高級(jí)人工智能75DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不同表達(dá)能力的描述邏輯，其復(fù)雜性問(wèn)題也不盡相同。例如，在ALC的基礎(chǔ)上添加逆(-)算子，則構(gòu)成ALCI若再加上數(shù)量約束算子(≥n,≤n)，則構(gòu)成ALCIQ。若在描述邏輯中添加時(shí)序算子，則構(gòu)成為時(shí)序描述邏輯(TemporalDescriptionLogic)，例如，可以添加：

Until算子U：C

U

D Since算子S：CSD還可以加入其它算子，如模態(tài)算子□，

，○等。2022/12/27史忠植高級(jí)人工智能75DL中添加算子2023/1/5史忠植高級(jí)人工智能76描述邏輯中的推理1)

一致性（協(xié)調(diào)性consistency）2)可滿(mǎn)足性(satisfiability)3)包含檢測(cè)（subsumption）4)實(shí)例檢測(cè)

(instancechecking)5)Tableaux算法6）可判定性7）計(jì)算復(fù)雜性2022/12/27史忠植高級(jí)人工智能76描述邏輯中的推2023/1/5史忠植高級(jí)人工智能77一致性檢測(cè)(Consistency)◆知識(shí)庫(kù)<T,A>是協(xié)調(diào)的嗎？ 即檢測(cè)是否有<T,A>的模型(解釋)I？◆C關(guān)于TboxT是協(xié)調(diào)的嗎？

即檢測(cè)是否有T的模型I使得C

≠

？2022/12/27史忠植高級(jí)人工智能77一致性檢測(cè)(C2023/1/5史忠植高級(jí)人工智能78概念可滿(mǎn)足性(Satisfiablity)

對(duì)一個(gè)概念C，如果存在一個(gè)解釋I使得CI是非空的，則稱(chēng)概念C是可滿(mǎn)足的，否則是不可滿(mǎn)足的。

檢驗(yàn)一個(gè)概念的可滿(mǎn)足性，實(shí)際上就是看是否有解釋使得這個(gè)概念成立。例如：概念Male?

Female，即需要檢測(cè)是否有性別既是男的又是女的這樣的人。若確實(shí)是沒(méi)有這種兩性人，則我們斷言，這個(gè)概念是不可滿(mǎn)足的。又如概念：student?worker，它是可滿(mǎn)足的。即代表那些在職學(xué)生的集合。定理：概念C是可滿(mǎn)足的，當(dāng)且僅當(dāng)C不包含于。

2022/12/27史忠植高級(jí)人工智能78概念可滿(mǎn)足性(2023/1/5史忠植高級(jí)人工智能79◆在知識(shí)庫(kù)中檢測(cè)：

C?

D？ 即檢測(cè)CI

?

DI是否在所有的解釋中成立？概念包含(Subsumption)例如：

bird?animal computer?equipment◆在Tbox中檢測(cè)：

C?

D？ 即檢測(cè)CI

?

DI是否在TboxT的所有解釋中成立？2022/12/27史忠植高級(jí)人工智能79◆在知識(shí)庫(kù)中檢2023/1/5史忠植高級(jí)人工智能80C?

Diff

C?

?D是不可滿(mǎn)足的。C?T

Diff

C?

?D關(guān)于T是不可滿(mǎn)足的。C關(guān)于T是一致的iffC?T

A?

?A包含與可滿(mǎn)足性的關(guān)系?DDCC?

?D＝

2022/12/27史忠植高級(jí)人工智能80C?D2023/1/5史忠植高級(jí)人工智能81實(shí)例檢測(cè)(Instancechecking)概念的實(shí)例：

Student(John)，或者表示為John:Student關(guān)系的實(shí)例：

Father(John,Mary) 實(shí)例檢索：檢索屬于某個(gè)概念的所有實(shí)例的集合2022/12/27史忠植高級(jí)人工智能81實(shí)例檢測(cè)(In2023/1/5史忠植高級(jí)人工智能82可滿(mǎn)足性檢測(cè)算法——Tableaux算法1)

?規(guī)則:S→?{

x:C1,x:C2}?S，若x:C1?

C2在S中，且x:C1和x:C2不在S中同時(shí)出現(xiàn)。2)?規(guī)則:S→?

{x:D}?S，若x:C1?C2在S中，x:C1和x:C2都不在S中，且D=C1或者D=C2。3)?規(guī)則:S→?

{xP1y,…,xPky,y:C}?S，若x:?R.C在S中，R=P1?…?Pk，沒(méi)有z使得xRz在S中成立，且z:C在S中，y為一個(gè)新變量。4)?規(guī)則:S→?{y:C}?S，若x:?R.C在S中，xRy在S中成立，且y:C不在S中。

2022/12/27史忠植高級(jí)人工智能82可滿(mǎn)足性檢測(cè)算檢測(cè)概念的可滿(mǎn)足性2023/1/5史忠植高級(jí)人工智能83例子：檢測(cè)概念的可滿(mǎn)足性：(?has-child.Male)?(?has-child.?Male)，其檢測(cè)過(guò)程為：((?has-child.Male)?(?has-child.?Male))(x)(?has-child.Male)(x) ?規(guī)則(?has-child.?Male)(x) ?規(guī)則has-child(x,y) ?規(guī)則?Male(y) ?規(guī)則Male(y) ?規(guī)則

矛盾所以這個(gè)概念是不可滿(mǎn)足的。檢測(cè)概念的可滿(mǎn)足性2022/12/27史忠植高級(jí)人工智能2023/1/5史忠植高級(jí)人工智能84可判定性描述邏輯中的可滿(mǎn)足性問(wèn)題是可判定的。其它推理問(wèn)題基本上可以歸結(jié)為可滿(mǎn)足性問(wèn)題。2022/12/27史忠植高級(jí)人工智能84可判定性描述邏2023/1/5史忠植高級(jí)人工智能85計(jì)算復(fù)雜性描述邏輯中的推理問(wèn)題其計(jì)算復(fù)雜性一般是多項(xiàng)式時(shí)間的。但通常由于構(gòu)造的不同，其復(fù)雜性也有一定的差異。2022/12/27史忠植高級(jí)人工智能85計(jì)算復(fù)雜性2023/1/5史忠植高級(jí)人工智能86帶缺省的描述邏輯◆帶缺省的描述邏輯定義

一個(gè)缺省規(guī)則是形如這樣的表達(dá)式，其中C、D、E為概念名，x是一個(gè)變?cè)?。C(x)稱(chēng)為前提條件，D(x)稱(chēng)為檢驗(yàn)條件(缺省)，E(x)稱(chēng)為缺省的結(jié)論。定義1.2

一個(gè)知識(shí)庫(kù)是一個(gè)三元組<T,A,D>，其中T為T(mén)box，A為Abox，D為缺省規(guī)則集。2022/12/27史忠植高級(jí)人工智能86帶缺省的描述邏2023/1/5史忠植高級(jí)人工智能87動(dòng)態(tài)描述邏輯

描述邏輯最開(kāi)始只是用來(lái)表示靜態(tài)知識(shí)的。為了考慮在時(shí)間上的變化，或者在一定動(dòng)作下的變化，以及保持其語(yǔ)言的相對(duì)簡(jiǎn)單性，很自然地我們需要通過(guò)相應(yīng)的模態(tài)算子來(lái)擴(kuò)展它，以保留其命題模態(tài)狀態(tài)。提出動(dòng)態(tài)描述邏輯，描述動(dòng)態(tài)知識(shí)以及行為,進(jìn)行推理。描述邏輯動(dòng)態(tài)邏輯＋動(dòng)態(tài)行為動(dòng)態(tài)描述邏輯2022/12/27史忠植高級(jí)人工智能87動(dòng)態(tài)描述邏輯動(dòng)態(tài)描述邏輯推理機(jī)動(dòng)態(tài)描述邏輯推理機(jī)2023/1/5史忠植高級(jí)人工智能89描述邏輯與語(yǔ)義Web有何區(qū)別與聯(lián)系？思考描述邏輯與Prolog有何區(qū)別與聯(lián)系？描述邏輯可以在哪些方面進(jìn)行擴(kuò)展與完善？2022/12/27史忠植高級(jí)人工智能89描述邏輯與語(yǔ)義參考文獻(xiàn)史忠植，《高級(jí)人工智能》，科學(xué)出版社，2011。陸鐘萬(wàn)，《面向計(jì)算機(jī)科學(xué)的數(shù)理邏輯》，科學(xué)出版社，2000。王元元，《計(jì)算機(jī)科學(xué)中的邏輯學(xué)》，科學(xué)出版社，1989。2023/1/5史忠植邏輯基礎(chǔ)90參考文獻(xiàn)史忠植，《高級(jí)人工智能》，科學(xué)出版社，2011。202023/1/5史忠植高級(jí)人工智能91參考文獻(xiàn)/http://www.cs.man.ac.uk/~horrocks/Slides/index.htmlhttp://www.cs.man.ac.uk/~franconi/dl/course/史忠植董明楷蔣運(yùn)承張海俊.語(yǔ)義Web的邏輯基礎(chǔ).中國(guó)科學(xué)E輯信息科學(xué)2004,34(10):1123-1138LiangChang,ZhongzhiShi,TianlongGu,LingzhongZhao:AFamilyofDynamicDescriptionLogicsforRepresentingandReasoningAboutActions.J.Autom.Reasoning49(1):1-52(2012).

2022/12/27史忠植高級(jí)人工智能91參考文獻(xiàn)htt2023/1/5史忠植智能科學(xué)92

ThankYouQuestion!/2022/12/27史忠植智能科學(xué)92人工智能邏輯

2023/1/5史忠植邏輯基礎(chǔ)93史忠植中國(guó)科學(xué)院計(jì)算技術(shù)研究所高級(jí)人工智能第二章人工智能邏輯

2022/12/27史忠植邏輯基礎(chǔ)1史忠植主要內(nèi)容邏輯簡(jiǎn)介邏輯程序設(shè)計(jì)非單調(diào)邏輯默認(rèn)邏輯限定邏輯真值維護(hù)系統(tǒng)情景演算動(dòng)態(tài)描述邏輯2023/1/5史忠植邏輯基礎(chǔ)94主要內(nèi)容邏輯簡(jiǎn)介2022/12/27史忠植邏輯基礎(chǔ)2邏輯簡(jiǎn)介邏輯的歷史邏輯系統(tǒng)命題邏輯謂詞邏輯2023/1/5史忠植邏輯基礎(chǔ)95邏輯簡(jiǎn)介邏輯的歷史2022/12/27史忠植邏輯基礎(chǔ)3邏輯的歷史Aristotle——邏輯學(xué)Leibnitz——數(shù)理邏輯GottlobFrege(1848-1925)——一階謂詞演算系統(tǒng),《符號(hào)論》20世紀(jì)30年代，數(shù)理邏輯廣泛發(fā)展2023/1/5史忠植邏輯基礎(chǔ)96邏輯的歷史Aristotle——邏輯學(xué)2022/12/27史邏輯系統(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ǔ)義。2023/1/5史忠植邏輯基礎(chǔ)97邏輯系統(tǒng)一個(gè)邏輯系統(tǒng)是定義語(yǔ)言和它的含義的方法。20222023/1/5史忠植邏輯基礎(chǔ)98邏輯程序語(yǔ)言邏輯符號(hào)保留字或者符號(hào)非邏輯符號(hào)用戶(hù)自定義的符號(hào)(變量名，函數(shù)名等)語(yǔ)句規(guī)則構(gòu)造一個(gè)程序的語(yǔ)句規(guī)則語(yǔ)義規(guī)則定義程序做什么的語(yǔ)句規(guī)則推理規(guī)則、公理和證明沒(méi)有邏輯與程序語(yǔ)言的對(duì)比2022/12/27史忠植邏