L4謂詞邏輯1 離散數(shù)學(xué)

謂詞邏輯一1L4謂詞邏輯1離散數(shù)學(xué)主要內(nèi)容謂詞與量詞謂詞公式等值演算范式謂詞邏輯推理歸結(jié)法推理2L4謂詞邏輯1離散數(shù)學(xué)謂詞邏輯與命題邏輯的區(qū)別命題邏輯:簡(jiǎn)單命題是分析的基本單元,不再對(duì)簡(jiǎn)單命題的內(nèi)部結(jié)構(gòu)進(jìn)行分析.例如a:“柏拉圖是人”和b:“亞里士多德是人”是兩個(gè)相互獨(dú)立的命題,看不出a和b有什么聯(lián)系.謂詞邏輯(predicatelogic):深入到簡(jiǎn)單命題的內(nèi)部進(jìn)行更精細(xì)的分析,即其主謂結(jié)構(gòu).例如用謂詞Man(x)表示“x是人”,則上述命題a和b可表示為Man(Plato)和Man(Aristotle).這樣能看出兩命題有聯(lián)系.3L4謂詞邏輯1離散數(shù)學(xué)對(duì)命題的進(jìn)一步分析日常語(yǔ)言的陳述句包含主語(yǔ)和謂語(yǔ).例如:“亞里士多德是人”,主語(yǔ)(“亞里士多德”)是述說(shuō)的對(duì)象,謂語(yǔ)(“是人”)描述主語(yǔ)的屬性或關(guān)系.謂詞邏輯用個(gè)體詞描述對(duì)象,用謂詞表達(dá)謂語(yǔ):如Man(Aristotle),Man(Plato).又如:“人是動(dòng)物”,主語(yǔ)“人”就不適合看成個(gè)體了,因?yàn)椤叭恕笔穷惛拍?適合理解成:“對(duì)任何個(gè)體x:若x是人,則x是動(dòng)物”.所以這個(gè)命題涉及兩個(gè)謂詞Man()和Animal()間的蘊(yùn)涵.4L4謂詞邏輯1離散數(shù)學(xué)為什么需要謂詞邏輯?可描述更豐富的推理形式.例如下面這個(gè)推理用命題邏輯無(wú)法描述.人皆有死.

a蘇格拉底是人.

b蘇格拉底會(huì)死.

c用謂詞邏輯可以很好地描述.我們介紹的是一階謂詞邏輯(FOL),它基本上覆蓋了人們?cè)跀?shù)學(xué)和日常生活中用到的推理.5L4謂詞邏輯1離散數(shù)學(xué)個(gè)體個(gè)體(individual)是指獨(dú)立存在的客體,可以是具體事物,也可以是抽象概念.個(gè)體常元:確定的個(gè)體,如Socrates,Plato.個(gè)體變?cè)?不確定的個(gè)體.所有個(gè)體構(gòu)成論域(domainofdiscourse).也叫個(gè)體域.不特別指明的話,論域囊括一切事物.當(dāng)討論真假性時(shí),往往指明特定論域.論域是所有個(gè)體變?cè)淖兓秶?6L4謂詞邏輯1離散數(shù)學(xué)謂詞謂詞(predicate)描述個(gè)體的屬性以及個(gè)體之間的關(guān)系.例如:柏拉圖是人.Man(Plato)亞當(dāng)喜歡夏娃.Likes(Adam,Eve)A在B和C之間.Between(A,B,C)7L4謂詞邏輯1離散數(shù)學(xué)謂詞的變目個(gè)數(shù)用一元謂詞描述個(gè)體的屬性.如前面的Man(x)用多元謂詞描述個(gè)體間的關(guān)系.關(guān)于n個(gè)個(gè)體的謂詞稱為n元謂詞.如前面的二元謂詞Likes(x,y)有0元謂詞?命題可視為0元謂詞!是獨(dú)立于任何個(gè)體變?cè)年愂鼍?故謂詞邏輯是命題邏輯的推廣.Arity/Adicitynullary/medadicunary/monadicbinary/dyadicternary/triadicn-arymultary/polyadic8L4謂詞邏輯1離散數(shù)學(xué)謂詞是命題函數(shù)一元謂詞P可視為從個(gè)體域D到集合{1,0}上的映射: P:D{1,0}n元謂詞也是一樣: P:Dn

{1,0}注意:P(x)是命題形式但不是命題,因?yàn)槠湔嬷挡淮_定.僅當(dāng)x取定為個(gè)體常元時(shí),P(x)才成為命題.9L4謂詞邏輯1離散數(shù)學(xué)個(gè)體函數(shù)個(gè)體函數(shù)是將個(gè)體映射到個(gè)體的函數(shù)

f:Dn

D不同于謂詞(將個(gè)體映射到真假值).個(gè)體函數(shù)可當(dāng)作個(gè)體使用,但不能單獨(dú)使用例如:若函數(shù)father(x)表示x的父親,謂詞P(x)表示x是教師,則P(father(x))就表示x的父親是教師.10L4謂詞邏輯1離散數(shù)學(xué)量詞量詞(quantifier)用來(lái)對(duì)論域中參與判斷的個(gè)體數(shù)量進(jìn)行約束.常用兩個(gè)量詞(全稱量詞):表示所有個(gè)體都參與判斷(存在量詞):表示存在某個(gè)個(gè)體參與判斷11L4謂詞邏輯1離散數(shù)學(xué)全稱量詞全稱量詞表達(dá)“對(duì)所有個(gè)體都…..”“所有”是對(duì)個(gè)體數(shù)量的一種約束.與此同義的還有“凡是”,“一切”,“任一”,“每個(gè)”等.基本形式為 (x)P(x)(x)P(x)為真iff

對(duì)論域中所有個(gè)體x,P(x)都為真P也可以是n元謂詞,如(x)P(x,y,z)量詞(x)后面也可以是任意公式(見后)12L4謂詞邏輯1離散數(shù)學(xué)存在量詞存在量詞表達(dá)“存在個(gè)體使得……”.“存在”也是對(duì)個(gè)體數(shù)量的一種約束,即至少有一個(gè).與此同義的還有“有”,“某個(gè)”,“某些”等.基本形式為 (x)P(x)(x)P(x)為真iff

論域中至少存在一個(gè)個(gè)體x0使P(x0)為真P也可以是n元謂詞,如(x)P(x,y,z)量詞(x)后面可以是任意公式(見后)13L4謂詞邏輯1離散數(shù)學(xué)有限論域下的量詞此前我們約定論域是包含一切事物的集合.論域的無(wú)限性給公式真值的討論帶來(lái)了復(fù)雜性.若論域是有限的,假設(shè)用{1,2,…,k}表示.則(x)P(x)=P(1)P(2)…P(k)(x)P(x)=P(1)P(2)…P(k)謂詞公式轉(zhuǎn)化成了命題公式LuChaojun,SJTU1414L4謂詞邏輯1離散數(shù)學(xué)LuChaojun,SJTU主要內(nèi)容謂詞與量詞謂詞公式等值演算范式謂詞邏輯推理歸結(jié)法推理15L4謂詞邏輯1離散數(shù)學(xué)一階謂詞邏輯一階(first-order)謂詞邏輯:量詞僅作用于個(gè)體變?cè)?簡(jiǎn)稱一階邏輯,記作FOL意即:一階邏輯只研究刻畫個(gè)體的謂詞,而二階邏輯則可刻畫謂詞的謂詞.符號(hào)約定個(gè)體常元:a,b,c,…個(gè)體變?cè)?x,y,z,…命題變?cè)?p,q,r,…函數(shù):f,g,h,…謂詞:P,Q,R,…量詞:,聯(lián)結(jié)詞:,,,,輔助符號(hào):“(”,“)”,“,”16L4謂詞邏輯1離散數(shù)學(xué)項(xiàng)謂詞邏輯的項(xiàng)遞歸定義如下:(1)個(gè)體常元和個(gè)體變?cè)琼?xiàng);(2)若f是n元個(gè)體函數(shù),t1,…,tn是n個(gè)項(xiàng),則f(t1,…,tn)是項(xiàng);(3)所有項(xiàng)都是通過(guò)有限次使用(1)(2)而生成.17L4謂詞邏輯1離散數(shù)學(xué)合式公式謂詞邏輯的wff遞歸定義如下:(0)命題變?cè)莣ff;(1)若P是n元謂詞,t1,…,tn是n個(gè)項(xiàng),則P(t1,…,tn)是wff.此類wff稱為原子公式;(2)若A,B是wff,則(A),

(AB),(AB),(AB),(AB)也是wff;(3)若A是wff,而x是A中的個(gè)體變?cè)?則(x)A,(x)A也是wff;(4)所有wff都是通過(guò)有限次使用(1)(2)(3)而生成.注wff簡(jiǎn)稱公式.常用符號(hào)A,B,C,…表示公式.—這是元語(yǔ)言符號(hào)!約定公式的最外層括號(hào)省略.18L4謂詞邏輯1離散數(shù)學(xué)例:合式公式合式公式:p(P(x,y))Q(x,y)(x)(P(x)Q(x))(x)(P(x)(y)Q(x,y))非合式公式(?):(x)((x)P(x))(x)P(y)19L4謂詞邏輯1離散數(shù)學(xué)約束變?cè)妥杂勺冊(cè)还街行稳?x)A或(x)A的部分稱為對(duì)x的約束部分(這里A是公式部分),稱A為量詞的轄域,稱x為約束變?cè)?稱x在(x)A或(x)A中的出現(xiàn)為約束出現(xiàn).若x在公式中的某個(gè)出現(xiàn)不處于x或x的轄域中,則稱x的這個(gè)出現(xiàn)為自由出現(xiàn),x是自由變?cè)?沒有自由變?cè)墓椒Q為閉公式.LuChaojun,SJTU2020L4謂詞邏輯1離散數(shù)學(xué)約束變?cè)妥杂勺冊(cè)?續(xù))在公式中x可能出現(xiàn)多次,可能既有約束出現(xiàn)又有自由出現(xiàn).例如:(x)P(x)Q(x)中,變?cè)獂的前兩個(gè)出現(xiàn)是約束出現(xiàn),第三個(gè)出現(xiàn)是自由出現(xiàn).約束變?cè)拿植恢匾?后文有約束變?cè)?guī)則).因此上面的公式與(y)P(y)Q(x)等值.包含自由變?cè)墓揭话悴荒苡?jì)算出真值,必須對(duì)自由變?cè)鞒鼋忉?賦值)后才可.而約束變?cè)獎(jiǎng)t無(wú)需解釋.21L4謂詞邏輯1離散數(shù)學(xué)自然語(yǔ)句表示為謂詞公式使用FOL表示自然語(yǔ)句,首先分解出謂詞,進(jìn)而使用量詞、函數(shù)、聯(lián)結(jié)詞來(lái)構(gòu)成合式公式.22L4謂詞邏輯1離散數(shù)學(xué)例:自然語(yǔ)句形式表示(1)所有有理數(shù)都是實(shí)數(shù).(x)(Rational(x)Real(x))(2)有些實(shí)數(shù)是有理數(shù).(x)(Real(x)Rational(x))(3)沒有無(wú)理數(shù)是有理數(shù)./無(wú)理數(shù)都不是有理數(shù).(x)(Irrational(x)Rational(x))(x)(Irrational(x)Rational(x))注:公式的真假依賴于論域.23L4謂詞邏輯1離散數(shù)學(xué)例:自然語(yǔ)句形式表示(續(xù))(4)設(shè)論域是自然數(shù)集:令Eq(x,y)表示=,s(x)表示x的后繼x+1,p(x)表示x的前驅(qū)x-1.i.對(duì)每個(gè)數(shù),有且僅有一個(gè)后繼(x)(y)(Eq(y,s(x))(z)(Eq(z,s(x))Eq(y,z)))ii.沒有這樣的數(shù),0是其后繼(x)(Eq(0,s(x)))iii.除0之外的數(shù),有且僅有一個(gè)前驅(qū)(x)(Eq(x,0)(y)(Eq(y,p(x))(z)(Eq(z,p(x))Eq(y,z))))24L4謂詞邏輯1離散數(shù)學(xué)例:自然語(yǔ)句形式表示(續(xù))(5)積木世界的形式描述桌上有三塊積木A,B,C.其相對(duì)位置可描述為:On(C,A)OnTable(A)OnTable(B)Clear(C)Clear(B)則“若x上方空,則不存在y在x上”可表示為 (x)(Clear(x)(y)On(y,x))25L4謂詞邏輯1離散數(shù)學(xué)例:自然語(yǔ)句形式表示(續(xù))(6)“函數(shù)f(x)在[a,b]上的點(diǎn)x0處連續(xù)”的-定義.()(

>0()(>0 (x)(|x-x0|<|f(x)–f(x0)|<

)))26L4謂詞邏輯1離散數(shù)學(xué)例:自然語(yǔ)句形式表示(續(xù))(7)多次量化:如對(duì)P(x,y)有四種多次量化情形:(x)((y)P(x,y))=(x)(y)P(x,y)=(y)(x)P(x,y)人人愛人人=人人被人人愛(x)((y)P(x,y))=(x)(y)P(x,y)≠(y)(x)P(x,y)人人都有所愛之人≠有人被人人愛(x)((y)P(x,y))=(x)(y)P(x,y)≠(y)(x)P(x,y)某人愛人人≠人人都有人愛(x)((y)P(x,y))=(x)(y)P(x,y)=(y)(x)P(x,y)某人愛某人=某人被某人愛27L4謂詞邏輯1離散數(shù)學(xué)謂詞公式的解釋謂詞公式的真假與論域、自由個(gè)體變?cè)?、命題變?cè)⒅^詞和函數(shù)有關(guān).對(duì)謂詞公式的解釋I包括五個(gè)部分:非空論域D對(duì)命題變?cè)概蔀閧0,1}對(duì)個(gè)體常元和(自由)個(gè)體變?cè)概蔀镈中元素對(duì)謂詞指派為D上的謂詞(關(guān)系)對(duì)函數(shù)指派為D上的函數(shù)公式A在解釋I下是一個(gè)命題AI,即有確定的真值.稱AI的真值為A在解釋I下的真值.28L4謂詞邏輯1離散數(shù)學(xué)例:謂詞公式的解釋考慮對(duì)(x)(P(x)Q(f(x),a))的解釋I:

論域D指派為{1,2};

個(gè)體常元a指派為1;

f指派為D上函數(shù)fI:fI(1)=2,fI(2)=1.

P指派為D上一元關(guān)系PI

={<2>} Q指派為D上二元關(guān)系QI

={<1,1>,<1,2>,<2,2>}此外,若x指派為1:PI(1)QI(fI(1),1)=T若x指派為2:PI(2)QI(fI(2),1)=T所以(x