離散數(shù)學及其應用課件：一階邏輯

一階邏輯2.1一階邏輯的基本概念2.2

一階邏輯公式與解釋2.3一階邏輯等值演算2.4一階邏輯公式范式2.5一階邏輯推理理論2.6數(shù)理邏輯與專家系統(tǒng)

2.1一階邏輯的基本概念

2.1.1個體和謂詞任何一個陳述句(原子命題)都是由主語和謂語兩部分組成的。主語是被描述的對象,稱為個體,它可以是一個具體的事物,也可以是一個抽象的概念。例如,鮮花、蜜蜂、小明、整數(shù)、好人主義思想、命題等都可以作為個體。謂語部分用于描述對象的屬性或?qū)ο笾g的關(guān)系,稱為謂詞。

個體又分為個體常元(項)和個體變元(項)。個體常元是指確定的具體的個體,通常用a,b,c等小寫字母表示。個體變元泛指不確定的個體,通常用x,y,z等小寫字母表示。如上例中的“小花”和“直線A和直線B”是個體常元,而“x”是個體變元。個體變元的取值范圍稱為個體域(或論域),個體域可以是有限事物的集合,也可以是無限事物的集合,例如{1,2,3}、26個英文字母、自然數(shù),都可以作為個體域。所有非空對象的集合稱為全總個體域。

謂詞通常用大寫字母F,G,H,…表示。一個單獨的謂詞是沒有意義的,通常用F(x)的形式表示某個體變元x具有某種屬性。如若x是個體,P表示“是素數(shù)”,則P(x)表示“x是素數(shù)”。又如“小花是三好學生”可表示為F(a),其中a為小花,F表示“是三好學生”。

謂詞中可以有多個個體變元或個體常元,個體之間用“,”分割,且它們之間的順序不能任意顛倒,例如M(Alice,Ann)表示“Alice是Ann的媽媽”。

定義2.1含有n個有序個體變元x1,…,xn的謂詞P稱為n元謂詞,表示為P(x1,…,xn)。它是以特定個體域為定義域,以{0,1}為值域的n元函數(shù),稱為命題函數(shù)。

n元謂詞中個體變元的個數(shù)稱為元數(shù),不帶個體變元的謂詞稱為0元謂詞。

命題函數(shù)的真假值是不確定的,只有當謂詞中的個體變元賦以確定值后,謂詞的真值才能確定?？紤]謂詞P(x,y,z)表示“x-y=z”,若指定x=3,則P(3,y,z)表示“3-y=z”,記作P1(y,z);若進一步指定y=2,則P(3,2,z)表示“3-2=z”,記作P2(z);若再進一步指定z=1,則P(3,2,1)表示“3-2=1”,記作P3。很顯然,

P(x,y,z)、P1(y,z)、P2(z)分別是3元、2元、1元謂詞,它們的真值都是不確定的;P3是0元謂詞,其真值為0,即0元謂詞是命題。

一階邏輯中,常用函數(shù)表示個體之間的關(guān)系,用f,g,h等小寫字母表示。如若Q(x,y)表示“x大于y”,f(x)=x+1,則Q(f(x),x)表示“x+1大于x”。

注意謂詞與函數(shù)之間的區(qū)別是:謂詞是從個體域到{0,1}的映射,其個體變元用常量代入后是命題,其值為0或者1;函數(shù)是從個體域到個體域(即函數(shù)的值域)的映射,個體經(jīng)函數(shù)映射后仍然是個體。

例2.1用0元謂詞將下面命題符號化。

(1)李明既學過英語,也學過日語。

(2)如果2是奇數(shù),3就是奇數(shù)。

(3)王珊不是學生。

(4)張強和張虎一樣高。

例2.2-令L(x,y)表示“x<y”,討論L(2,3)和L(5,1)的真值。

解

L(2,3)表示“2<3”,所以L(2,3)的真值為1。

L(5,1)表示“5<1”,所以L(5,1)的真值為0。

2.1.2-量詞

1.全稱量詞

自然語言中表示“所有的”、“全部的”、“任意的”、“都”、“一切的”、“每一個”等詞稱為全稱量詞,用“?”表示。?xP(x)表示x取其論域中所有值都使得謂詞P為真,并讀作“對一切x,P(x)是真”,稱x被全稱量化。

例如,對任何實數(shù)都有x<x+1,可以表示為?x(x<x+1),很顯然這個命題為真。

2.存在量詞

自然語言中表示“至少有一個”、“有的”、“差不多”、“有些”等詞稱為存在量詞,用“?”表示。?xP(x)表示在x的論域中至少有一個值使得謂詞P(x)為真,并讀作:“存在一個x,使得P(x)為真”,稱x被存在量化。

例如,存在實數(shù)y,使得y=3,可以表示?y(y=3),很顯然這個命題為真,即?y(y=3)為真。

3.命題函數(shù)變命題的途徑

例2.3令P(x)表示x>0,論域為整數(shù)Z,討論?xP(x)和?xP(x)的真值。

解根據(jù)題意,?xP(x)表示“對任意整數(shù)x,x都大于0”,由于除了正整數(shù)以外,還存在負整數(shù),所以?xP(x)為假;?xP(x)表示“在整數(shù)集中存在x,x大于0”,同理可知?xP(x)為真。

在上述例題中,P(x)的真值是不確定的,它不是命題,只是一個命題函數(shù),但經(jīng)過量化后的?xP(x)和?xP(x)變成了命題。前面我們討論過,當給一個命題變元x取一個確定的值a時,命題函數(shù)可以變?yōu)槊}。由此可見,命題函數(shù)不是命題,但在給個體變元指定確定的值或者對個體變元進行量化后,它可以變成命題。

需要注意的是,量化后所得命題的真值與論域有關(guān),即隨論域不同真值可能不同。如上例中,如果將論域改為正整數(shù)Z+,則?xP(x)為真。

2.1.3一階邏輯的翻譯(符號化)

把一個自然語言敘述的陳述句或者一個數(shù)學命題用一階邏輯符號表示出來的過程稱為一階邏輯翻譯或符號化。一階邏輯中把命題邏輯中的每個原子命題分解成了個體和謂詞,

如果涉及到部分和全體的概念,則需要引入量詞。在實際應用中,還需要考慮個體域,個體域的不同不僅僅影響命題的真值,還影響命題的符號化形式?？紤]下面兩個命題的符號化:

(1)所有人都是要死的。

(2)有的人愛吃糖。

令D(x)表示“x是要死的”;E(x)表示“x愛吃糖”。

當論域為全人類時,“所有的人都是要死的”符號為?xD(x);“有的人愛吃糖”符號為?xE(x)。

當不指定論域時,默認為全總個體域,?xD(x)就不能再解釋為“所有的人都是要死的”,只能解釋為“所有的事物(或?qū)ο?都是要死的”,?xE(x)也會得到同樣的解釋。為此,需要引入一個新的謂詞,將研究的對象(這里指人)從全總個體域中分離出來,這個謂詞稱為特性謂詞。

一階邏輯符號化的一般步驟如下:

(1)正確理解給定命題,必要時可適當加以改述,使其中的各原子命題之間的關(guān)系更清晰;

(2)把每個原子命題分解成個體和謂詞,涉及到部分和全體時,需要找出適當量詞,確定論域,當給定的論域大于研究問題的范圍時,引入特性謂詞,將每個原子命題進行符號化;

(3)用適當?shù)穆?lián)結(jié)詞將各原子命題連接起來。

2.2

一階邏輯公式與解釋

2.2.1一階邏輯合式公式通過前面的學習可以發(fā)現(xiàn),一個命題通常被分解為個體和謂詞兩部分,為了解決部分和全體的概念引入了量詞。

下面我們逐一梳理一下一階邏輯表達式中的常用符號:

(1)個體常元符號:a,b,c,…,ai,bi,ci,…(i≥1);

(2)個體變元符號:x,y,z,…,xi,yi,zi,…(i≥1);

(3)謂詞符號:F,G,H,…,Fi,Gi,Hi,…(i≥1)

(4)量詞符號:?,?;

(5)聯(lián)結(jié)詞符號:,∧,∨,→,?;

(6)括號和逗號:(,),,;

(7)函數(shù)符號:f,g,h,…,fi,gi,hi,…(i≥1)。

定義2.2

把不含有聯(lián)結(jié)詞和量詞的n元謂詞稱為原子公式,一階邏輯合式公式的遞歸定義如下:

(1)單個原子公式是合式公式;

(2)若A是合式公式,x是個體,則?xA、?xA也是合式公式;

(3)若A和B是合式公式,則A、A∧B、A∨B、A→B、A?B也是合式公式;

(4)有限次的應用(1)~(3)生成的公式是一階邏輯合式公式,也稱為謂詞公式,簡稱為公式。

2.2.2

自由變元與約束變元

定義2.3如果一個公式有形如?xA和?xA的子公式,則x為指導變元,A為相應量詞的轄域,在轄域A中x的出現(xiàn)稱約束出現(xiàn),不是約束出現(xiàn)的變元稱為自由出現(xiàn);公式中約束出現(xiàn)的個體變元是約束變元,自由出現(xiàn)的個體變元是自由變元。

確定一個量詞轄域就是要找出位于該量詞之后的相鄰接的子公式,具體地講:①若量詞后有括號,則括號內(nèi)的子公式就是該量詞的轄域;②若量詞后無括號,則與量詞鄰接的

子公式為該量詞的轄域。

在一個公式中,允許一個變元既是自由變元又是約束變元,如上例中的x。為了避免概念上的混淆,可以通過修改約束變元名或者自由變元名的方法,使得一個變元在一個公式中呈現(xiàn)一種出現(xiàn)方式,即改名規(guī)則和代替規(guī)則。

改名規(guī)則對公式中的約束變元符號采用如下規(guī)則更改:

(1)對某約束變元改名時,更改該指導變元及其在轄域中的所有約束出現(xiàn),其余部分不變。

(2)改名時所選用的個體變元符號必須是公式中未出現(xiàn)過的符號。

代替規(guī)則對公式中的自由變元符號采用如下規(guī)則更改:

(1)對某自由變元改名時,更改該自由變元在公式中的所有自由出現(xiàn),其余部分不變。

(2)代替時所選用的個體變元符號必須是公式中未出現(xiàn)過的符號。

例如,對公式?y(P(x,y)∧?x(F(x)→?zQ(x,z))),可以采用改名規(guī)則和代替規(guī)則兩種方法消除x既自由出現(xiàn)又約束出現(xiàn)的現(xiàn)象。

改名后的公式:?y(P(x,y)∧?u(F(u)→?zQ(u,z)))

代替后的公式:?y(P(w,y)∧?x(F(x)→?zQ(x,z)))

定義2.4設(shè)A為任意謂詞公式,若A中無自由出現(xiàn)的個體變元,則稱A是封閉的合式公式,簡稱閉式。

例如,?x(F(x)→G(x))和?x?y(F(x)∨G(x,y))是閉式。但?x(F(x)→G(x,y))和?z?yL(x,y,z)不是閉式。

閉式中不存在自由變元,也就是說閉式中所有變元都是被量化的,因此,閉式一定是非真即假的命題。

2.2.3一階邏輯公式的解釋

一個合式公式包含個體常元、個體變元、函數(shù)變項、謂詞變項等,由這些符號組成的公式是沒有任何意義,即公式的真值不能確定。只有對各種變項指定一個有確定意義的值,才能確定公式的真值。

定義2.5給一個合式公式G中的一些符號指定的一組有確定意義的常量,包括非空個體域、個體域上的特定個體、特定函數(shù)和謂詞,稱為該公式的解釋,也稱為指派或賦值,通常用I表示。若在解釋I下公式G的真值為真,則稱I為G的成真解釋或成真賦值;若在解釋I下公式G的真值為假,則稱I為G的成假解釋或成假賦值。

定義2.6設(shè)A為一階邏輯公式,如果A在任意解釋下均為真,則稱A為永真式,也稱邏輯有效式;如果A在任意解釋下均為假,則稱A為永假式,也稱為矛盾式;如果至少存在一個解釋使得A為真,則稱A為可滿足式。

定義2.7設(shè)A*是含命題變元p1,p2,…,pn

的命題公式,A1,A2,…,An是n個謂詞公式,用Ai(1≤i≤n)替換A*中的所有pi,所得公式A稱為A*的代換實例。

2.3一階邏輯等值演算

2.3.1一階邏輯等值式類似于命題邏輯,下面給出一階邏輯等值式的定義。定義2.8任意給定兩個謂詞公式A和B,如果它們的等價式A?B為重言式,則稱謂詞公式A與B是邏輯等值的,簡稱為等值式,記作A?B。

定理2.1設(shè)A、B、C為任意謂詞公式,則有:

(1)A?A。

(2)若A?B則B?A。

(3)若A?B且B?C則A?C。

根據(jù)上一節(jié)內(nèi)容可知,命題公式中永真式的代換實例在謂詞公式中也是永真式,因此,命題邏輯中的24個等值式的代換實例在一階邏輯中仍然是等值式。

例如,?xF(x)→G(x)??xF(x)∨G(x)。

除此之外,一階邏輯中還有一些關(guān)于量詞的等值式。

1.量詞消去等值式

若論域為有限集合{a1,a2,…,an},根據(jù)?xP(x)的語義“對論域中的一切x,P(x)均為真”,可得P(a1),P(a2),…,P(an)均為真;同理,根據(jù)?xP(x)的語義“在論域中至少有一個值,使得P為真”,但不能確定是哪個值,或者是a1,或者是a2,…,或者是

an,因此有如下等值式成立:

2.量詞否定等值式

(1)?xA(x)??x

A(x)

(2)?xA(x)??x

A(x)

這一組等值式給出了全稱量詞和存在量詞之間的轉(zhuǎn)換規(guī)則。例如,設(shè)A(x)表示x選修了離散數(shù)學,則?xA(x)表示不是所有人都選離散數(shù)學,?xA(x)表示有些人沒有選修離散數(shù)學,這兩句話在意義上是相同的,所以(1)式成立。同理,可以說明公式(2)成立。

3.量詞轄域的收縮和擴張等值式

其中,A(x)是含有自由變元x的任意謂詞,B為不含自由變元x的任意謂詞。

4.量詞分配等值式

(1)?x(A(x)∧B(x))??xA(x)∧?xB(x)

(2)?x(A(x)∨B(x))??xA(x)∨?xB(x)

其中,A(x)和B(x)都是含有自由變元x的任意謂詞。

這組等值式說明全稱量詞對合取聯(lián)結(jié)詞滿足分配律,存在量詞對析取聯(lián)結(jié)詞滿足分配律。

5.多量詞交換等值式

(1)?x?yA(x,y)??y?xA(x,y)

(2)?x?yA(x,y)??y?xA(x,y)

通過這組等值式可知,兩個連續(xù)出現(xiàn)的相同量詞的先后順序是無關(guān)的。

2.3.2

一階邏輯等值演算

定理2.2

設(shè)f(A)是一個含有子公式A的謂詞公式,f(B)是用公式B置換了f(A)中的子公式A后得到的公式,如果A?B,那么f(A)?f(B)。

置換規(guī)則是一種等值演算的方法,即等值演算的每一步都是用與原公式中的子公式(可以是公式本身)邏輯等價的等值式置換該子公式,從而得到新的等值式。除此之外,還需要用量詞改名規(guī)則和代替規(guī)則,消除一個變元既自由出現(xiàn)又約束出現(xiàn)或一個變元在多個不同量詞轄域中約束出現(xiàn)的現(xiàn)象。

定理2.3設(shè)A是任意謂詞公式,若A*是對公式A中約束變元改名或?qū)ψ杂勺冊婧蟮玫降墓?則A?A*。

這個定理的正確性很顯然,因為,某公式中存在一個變元既約束出現(xiàn)又自由出現(xiàn),則說明這個以兩種不同形式出現(xiàn)的變元代表著不同的個體,只不過這兩個不同個體使用了相同的名字,正像現(xiàn)實生活中兩個不同的人取了同一個名字一樣。

2.4一階邏輯公式范式

2.4.1前束范式定義2.9形如Q1x1Q2x2…QnxnA的謂詞公式稱為前束范式,其中Qi(i≤n)為?或?,A為不含量詞的謂詞公式。

定理2.4任何謂詞公式都有與之等值的前束范式。

任何一個謂詞公式,可以用如下方法將其轉(zhuǎn)化為前束范式形式。

(1)使用量詞否定等值式將否定聯(lián)結(jié)詞移到量詞之后謂詞變元之前;

(2)若一個變元出現(xiàn)在不同的量詞轄域中或者一個變元既約束出現(xiàn)又自由出現(xiàn),則使用改名規(guī)則、代替規(guī)則使所有變元均呈現(xiàn)出一種出現(xiàn)形式;

(3)使用量詞轄域收縮或擴張等值式、量詞分配等值式將量詞轄域擴大到整個公式。

2.4.2

斯科倫范式

定義2.10形如?1x1?2x2…?nxnB的前束范式,若B為合取范式,則?1x1?2x2…?nxnB是斯科倫(Skolem)范式。

定理2.5若前束范式B是公式A的斯科倫范式,則A是可滿足的當且僅當B是可滿足的。

注意在前束范式中,存在量詞越靠前,越容易消去存在量詞。因此,求給定公式的前束范式時總是先擴展存在量詞的轄域,再擴展全稱量詞的轄域,使得公式中的存在量詞盡可能排在前面。

2.5一階邏輯推理理論

2.5.1一階邏輯推理的基本概念1.永真蘊涵式定義2.11設(shè)A和B是任意兩個謂詞公式,若它們的蘊涵式A→B為永真式,則稱A永真蘊涵B,記作A?B,稱A?B為永真蘊涵式。

定理2.6設(shè)A和B為任意兩個謂詞公式,A?B當且僅當A?B且B?A。

在命題邏輯中,基本永真蘊涵式的代換實例在一階邏輯中仍然是永真蘊涵式。此外,一階邏輯還有兩組永真蘊涵式,即量詞分配永真蘊涵式和多量詞交換永真蘊涵式。

(1)量詞分配永真蘊涵式。

①?xA(x)∨?xB(x)??x(A(x)∨B(x))

②?x(A(x)∧B(x))??xA(x)∧?xB(x)

(2)多量詞交換永真蘊涵式。

從2.3節(jié),我們知道兩個連續(xù)出現(xiàn)的相同量詞,其先后次序是無關(guān)的。但不同量詞之間的先后順序不能隨意調(diào)動,其關(guān)系可以用下面的永真蘊涵式描述:

?x?yA(x,y)??y?xA(x,y)

?x?yA(x,y)成立的含義是:在論域中至少有一個值x,使得y取任意值時A(x,y)都為真,那么,不論y取何值都能找到一個x使得A(x,y)為真,即?y?xA(x,y)為真。反之不真。

2.前提和結(jié)論

定義2.12

給定一組假設(shè)H1,H2,…,Hn和一個結(jié)論C,只需考察如下永真蘊涵式是否成立:

若該永真蘊涵式成立,則稱從謂詞公式H1∧H2∧…∧Hn推出C的推理是正確的(或有效的),稱H1,H2,…,Hn

為推理的前提,C為由這些前提推出的有效結(jié)論,也稱為邏輯結(jié)論;否則,推理不成立,稱C是H1,H2,…,Hn的謬誤結(jié)論。

一般將永真蘊涵式稱為推理定律,一階邏輯的推理定律的來源有如下幾種:

(1)命題邏輯中的推理定律在一階邏輯中的代換實例;

(2)每個等值式(包括一階邏輯等值式和命題邏輯等值式的代換實例)產(chǎn)生兩條推理定律;

(3)一階邏輯中的關(guān)于量詞分配和多量詞交換的永真蘊涵式。

2.5.2

一階邏輯的推理規(guī)則

1.全稱量詞消去規(guī)則(UI)

這個規(guī)則表明,若個體域中所有個體x都具有性質(zhì)A,則任意個體常元c或變量y也具有性質(zhì)A,即A(c)或A(y)成立,其中,c是在A(x)中沒有出現(xiàn)的個體常元,y是在A(x)中不約束出現(xiàn)的個體變元。

2.全稱量詞引入規(guī)則(UG)

這個規(guī)則的含義是,若個體域中任意一個體變元y都具有性質(zhì)A,則個體域中所有個體變元x都具有性質(zhì)A,其中,取代y的x一定是在A(y)中不約束出現(xiàn)過的個體變元。

3.存在量詞消去規(guī)則(EI)

這個規(guī)則表明,當個體域中存在某個個體x具有性質(zhì)A時,若c是使得A(c)成立的常量,則可以將存在量詞消去。其中,c是沒有在A(x)中出現(xiàn)過的特定常元。使用這個規(guī)則時,一定要注意,c必須是具有性質(zhì)A的特定個體常元,否則,不能用此規(guī)則。

4.存在量詞引入規(guī)則(EG)

這個規(guī)則的含義是,若個體域中某個特定個體c具有性質(zhì)A,則可以對變元x存在量化,即?xA(x)為真。其中,取代c的x一定是沒有在A(c)中出現(xiàn)過的個體變元。

一階邏輯推理的一般方法如下:

(1)使用P規(guī)則或CP規(guī)則引入帶量詞的前提或附加前提;

(2)用UI或EI消除前提中的量詞;

(3)使用命題演算的各種規(guī)則與辦法完成推導;

(4)使用UG或EG添加量詞,使結(jié)論呈量化形式。

2.