第十九章謂詞邏輯PPT課件

1、第十九章第十九章 謂詞邏輯謂詞邏輯1 謂詞代數(shù)謂詞代數(shù)一、項與原子公式一、項與原子公式一數(shù)一數(shù)的的平方平方與與一數(shù)一數(shù)的的平方根平方根之之和和大于大于0”。命題涉及命題涉及3個個體對象個個體對象:兩個不確定數(shù)，兩個不確定數(shù)，x1,x2一個常數(shù)一個常數(shù)0，用，用c1表示；表示；涉及涉及3個函數(shù)，兩個一元運算個函數(shù)，兩個一元運算(即平方與平方根即平方與平方根)，分別記為，分別記為f1(1),f1(2)，求和運算則是二元運算，用求和運算則是二元運算，用f2(1)表示；表示；最后，還有一個關于數(shù)的二元關系最后，還有一個關于數(shù)的二元關系“大于大于”，用，用R2(1)表示。表示。命題表示成命題表示成R2(

2、1)(f2(1)(f1(1)(x1),f1(2)(x2),c1)。這個命題是否正確，取決于對這個命題是否正確，取決于對x1,x2所作的賦值。所作的賦值。若若x1,x2都是非負實數(shù)且至少有一個不為都是非負實數(shù)且至少有一個不為0，則命題正確，則命題正確若若x1,x2都為都為0，則命題不正確。，則命題不正確。通過分解命題可以發(fā)現(xiàn)，命題的內(nèi)部結通過分解命題可以發(fā)現(xiàn)，命題的內(nèi)部結構包含了下述內(nèi)容：構包含了下述內(nèi)容：(1)一些個體對象及對它們進行的某些運一些個體對象及對它們進行的某些運算；算；(2)關于這些對象的一個關系。關于這些對象的一個關系。定義定義19.1:由表示某種不確定的可列個個由表示某種不確定

3、的可列個個體對象全體所組成的集合稱為體對象全體所組成的集合稱為個體變元個體變元集集，記為，記為X=x1,xn,，這里這里xi稱為稱為個個體變元體變元，用來表示不確定的個體對象。，用來表示不確定的個體對象。由表示某種確定的個體對象全體所組成由表示某種確定的個體對象全體所組成的集合稱為的集合稱為個體常元集個體常元集，它是可列集或，它是可列集或有 限 集 ， 也 可 以 是 空 集 ， 記 為有 限 集 ， 也 可 以 是 空 集 ， 記 為 C = c1,cn,，這里這里ci稱為稱為個體常元個體常元，用，用來表示某個確定的個體對象。來表示某個確定的個體對象。對于類型對于類型T(1)=1nnT,這里

4、這里Tn=fni|ar(fni)=n，并且并且|Tn|0(故故|T(1)|0),由定理由定理19.1，可構，可構造造XC上的自由上的自由T(1)-代數(shù)代數(shù)I。當當T(1)=時，時，I=XC；當當T(1)，I=0nnI, 其中其中I0=XC(這是因為這是因為T0=)，I1=(f1i,xj)|f1i T1,xj X(f1i,cj)|f1i T1,cj C (f2i,xj,xk)|f2i T2,xj,xk X (f2i,xj,ck)|f2i T2,xj X,ck C (f2i,cj,xk)|f2i T2,xk X,cj C (f2i,cj,ck)|f2i T2,cj,ck C (fki,y1,y2,

5、yk)|fki Tk,yi XC隨著隨著n的增大的增大In將更為復雜。將更為復雜。在在I上定義運算上定義運算fki:IkI，使得使得fki(a1,ak)=(fki,a1,ak)，這里這里aj I (j=1,k)，即即fki為為I上的第上的第i個個k元運元運算。算。定義定義19.2:XC上的自由上的自由T(1)-代數(shù)代數(shù)I稱為稱為項項集集，I中的每個元素稱為中的每個元素稱為項項，不含個體變，不含個體變元的項稱為元的項稱為閉項閉項，I上的代數(shù)運算上的代數(shù)運算fni稱為稱為第第i個個n元函數(shù)詞元函數(shù)詞。如果。如果XC,T(1)可列，可列，項集項集I也是可列集。也是可列集。例：設例：設C=,T=(f1

6、1,f21|ar(f11)=1, ar(f21)=2,求求I0，I1，I2，定義定義19.3:設關系集設關系集R=0nnRRn表示某個對象表示某個對象集上的所有集上的所有n元關系，即元關系，即Rn =Rni|ar(Rni)=n定義定義19.4:對任意的對任意的Rni Rn R，稱稱I上的上的n元關元關系系Rni(t1, ,tn)為為I上的上的原子公式原子公式(特別地，特別地，R0i就是原子命題公式就是原子命題公式),這里這里t1, ,tn I,Rni稱為第稱為第i個個n元謂詞?；陉P系集元謂詞。基于關系集R的所有的所有I上的原子公上的原子公式全體稱為式全體稱為I的的原子公式集原子公式集，記為，

7、記為Y。原子公式集原子公式集Y是可列集。是可列集。C=, T(1)=,R=R0(這里這里R0為為0元關系集元關系集)時，原子公時，原子公式就是命題邏輯中的命題變元即原子命題。式就是命題邏輯中的命題變元即原子命題。二、謂詞代數(shù)二、謂詞代數(shù)例：設例：設A=1,100，對于命題對于命題“A中所中所有數(shù)都大于有數(shù)都大于0”.ci表示數(shù)字表示數(shù)字i，R2i表示二元關系表示二元關系“大于大于”，命題形式化地表示為：命題形式化地表示為：R2i(c1,0) R2i(c100,0)。當當A為正實數(shù)集時，就不能用上述方式表為正實數(shù)集時，就不能用上述方式表示。為此引進記號示。為此引進記號 xR2i(x,0)來表示上

8、面來表示上面的命題。這里的命題。這里 x稱為全稱量詞。稱為全稱量詞。注意注意: x中的中的x只是虛設的，只是虛設的， xR2i(x,0)并并不依賴于不依賴于x，事實上也可用事實上也可用 yR2i(y,0)表示表示上述命題。上述命題。對于命題對于命題“對所有的對所有的x，使得有使得有p(x)就必有就必有q(x)”，可表示為可表示為 x (p(x)q(x)。設設A=-2,-1,0,1,2,對于命題對于命題“在在A中必存在中必存在大于大于0的數(shù)的數(shù)”，令令ci表示數(shù)字表示數(shù)字i，R2(1)表示二元關系表示二元關系“大大于于”，則命題可形式化地表示為：，則命題可形式化地表示為：R2(1)(c-2,0)

9、 R2(1)(c-1,0) R2(1)(c0,0) R2(1)(c1,0) R2(1)(c2,0)。當當A為實數(shù)集時，就不能用上述方式表示為實數(shù)集時，就不能用上述方式表示引進記號引進記號 xR2(1)(x,0)來表示上面的命題。來表示上面的命題。這里這里 x稱為存在量詞。要注意的是，在稱為存在量詞。要注意的是，在 x中的中的x只是虛設的，只是虛設的， xR2(1)(x,0)并不依并不依賴于賴于x，事實上也可用事實上也可用 yR2(1)(y,0)表示上表示上述命題。述命題。存在量詞與全稱量詞有聯(lián)系。存在量詞與全稱量詞有聯(lián)系。對命題對命題“不存在不存在x具有性質具有性質p”，可表示為可表示為 (

10、xp(x)，也可表示為也可表示為 x( p(x)。因此因此 x和和x 有相同的含義，所以在有相同的含義，所以在構造模型時，就不需要包括存在量詞，構造模型時，就不需要包括存在量詞，而只要定義而只要定義 x=x 。謂詞代數(shù)建立在原子公式集謂詞代數(shù)建立在原子公式集Y上，并且謂上，并且謂詞代數(shù)詞代數(shù)P(Y)除了必須是除了必須是 F, -代數(shù)外，代數(shù)外，還必須使個體變元集還必須使個體變元集X中的每個個體變元中的每個個體變元x，都有函數(shù)都有函數(shù) x:P(Y)P(Y)。定義定義19.5:原子公式集原子公式集(作為生成元集作為生成元集) Y=Rn(t1, ,tn)|Rn R,ti I, 1 i n上關于上關于

11、類型類型F, x|x X的自由代數(shù)稱為的自由代數(shù)稱為謂詞代謂詞代數(shù)數(shù)，記為，記為P(Y)，P(Y)中的元素稱為中的元素稱為謂詞合謂詞合式公式式公式，因此，因此P(Y)也稱為也稱為謂詞公式集謂詞公式集。這。這里里F是是0元運算，元運算，為二元運算，而為二元運算，而 x則是則是一元運算。一元運算。與命題代數(shù)類似，可利用與命題代數(shù)類似，可利用F，和和 x來來定義一元運算定義一元運算 和和 x以及其它二元運算以及其它二元運算 , , ，現(xiàn)定義如下：，現(xiàn)定義如下：)()()(p)(p)(ppdefpqqpqpqqpqqpxxFdefdefdefdef定義定義19.6:在謂詞合式公式在謂詞合式公式q= x

12、p(這里這里 表表示示 或或 )中，稱中，稱p為為 x的的轄域轄域。p中中x的出的出現(xiàn)稱為現(xiàn)稱為x在在q中的中的約束出現(xiàn)約束出現(xiàn)。p中不是約束中不是約束出現(xiàn)的其它變元的出現(xiàn)稱為變元在出現(xiàn)的其它變元的出現(xiàn)稱為變元在q中的中的自由出現(xiàn)自由出現(xiàn)。如果變元。如果變元x在在q中約束出現(xiàn)，中約束出現(xiàn)，則稱則稱x是是q中的中的約束變元約束變元。如果變元。如果變元x在在q中自由出現(xiàn)，則稱中自由出現(xiàn)，則稱x是是q中的中的自由變元自由變元。 q中自由出現(xiàn)的個體變元全體構成的集合中自由出現(xiàn)的個體變元全體構成的集合用用var(q)表示，若表示，若var(q)=，則稱則稱q為為閉閉式式，此時，此時q中無自由變元。中無自

13、由變元。x可能既是自由變元可能既是自由變元，又是約束變元。，又是約束變元。對于對于A P(Y)，A中所有公式的自由變元中所有公式的自由變元全體構成的集合用全體構成的集合用var(A)來表示。來表示。例例:指出下列謂詞公式中，量詞的轄域，指出下列謂詞公式中，量詞的轄域，個體變元的自由出現(xiàn)和約束出現(xiàn)：個體變元的自由出現(xiàn)和約束出現(xiàn)：(1) x(R11(x) yR21(x,y)(2) x( xR11(x)R21(x,y)R22(x,y)解解:在在(1)中中,量詞量詞 y的轄域是的轄域是R21(x,y)，量量詞詞 x的轄域是的轄域是R11(x) yR21(x,y)，x的兩的兩次出現(xiàn)都是約束出現(xiàn)，次出現(xiàn)都

14、是約束出現(xiàn)，y也是約束出現(xiàn)的，也是約束出現(xiàn)的，x和和y都是約束變元都是約束變元,是是閉式閉式(2) x( xR11(x)R21(x,y)R22(x,y)在在(2)中，中， x的轄域是的轄域是R11(x)， x的轄域的轄域是是 xR11(x)R21(x,y)。定義定義19.7:設設p(x)是是P(Y)中謂詞合式公式，中謂詞合式公式，x是其自由變元之一，是其自由變元之一，t(z)是項，是項，z 代表代表t中的任一個個體變元。當中的任一個個體變元。當x不出現(xiàn)在不出現(xiàn)在p的的 z的轄域內(nèi)，則稱的轄域內(nèi)，則稱t對于對于p中的中的x是是自由的自由的，否則就稱否則就稱t對于對于p中的中的x是是不自由的不自由

15、的。當當t代入代入p(x)中的中的x而得而得p(t(z)時，時，z應是應是p的自由變元，但如果的自由變元，但如果x出現(xiàn)在出現(xiàn)在p的的 z的轄的轄域內(nèi)，域內(nèi)，z就成為就成為p(t(z)中的約束變元中的約束變元這時這時t對于對于p中的中的x是不自由的，變元的性是不自由的，變元的性質就完全不同了質就完全不同了,這在語義解釋時即可發(fā)這在語義解釋時即可發(fā)現(xiàn)。現(xiàn)。例例:在在 x1R21(x1,x2) x3R22(x3,x1)中，項中，項f21(x1,x3)對自由變元對自由變元x1,x2都是不自由的；都是不自由的；項項f22(x2,x3)對自由變元對自由變元x1是不自由的，對自是不自由的，對自由變元由變元x

16、2是自由的；是自由的；項項x2對自由變元對自由變元x1是自由的，項是自由的，項x1對自由變對自由變元元x2則是不自由的。則是不自由的。約定約定:用用p(x)或或p表示表示P(Y)中的元素中的元素(即謂詞合即謂詞合式公式式公式)p(x)并不意味著并不意味著x在在p(x)中是自由出現(xiàn)的，中是自由出現(xiàn)的，x可可以不自由出現(xiàn)，甚至不出現(xiàn)。以不自由出現(xiàn)，甚至不出現(xiàn)。用用p(t)表示由項表示由項t去替換去替換p(x)中所有自由出現(xiàn)的中所有自由出現(xiàn)的x所得到的結果。所得到的結果。例：例：p(x2)= x1R21(x1,x2) x3R22(x3,x1)p(f22(x2,x3)= x1R21(x1, f22(x2,x3) x3R22(x3,x1)p(x1)= x1R21(x1,x2) x3R22(x3,x1)p(f11(x2)= x1R