一階謂詞原理.ppt

1、一階謂詞邏輯,CH4 一階邏輯基本概念 CH5 一階邏輯等值演算與推理,13:26,2,內(nèi)容要點：,置換規(guī)則,13:26,3,1.命題的表達,例1.1：凡偶數(shù)都能被2整除， 6是偶數(shù)。 所以，6能被2整除 將它們命題符號化： p：凡偶數(shù)都能被2整除 q： 6是偶數(shù) r： 6能被2整除 則推理的形式結(jié)構(gòu)符號化為： (p q) r,由于上式不是重言式，所以不能由它判斷推理的正確性。為了克服命題邏輯的局限性，就應(yīng)該將簡單命題再細分，分析出個體詞、謂詞和量詞，以期達到表達出個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系，這就是謂詞邏輯。,13:26,4,(1)是自然數(shù)。 (2) 21世紀末，人類將住在月球。 (3)

2、x+y=y+x (4) 只有x能被2整除， x才能被4整除。,A.個體詞,x,y的取值范圍：復(fù)數(shù)域 a的取值范圍：整數(shù)域,是指所研究對象中可以獨立存在的具體的或抽象的客體。,表示具體或特定的客體的個體詞稱作個體常項；常用a,b,c,表示。,表示抽象或泛指的客體的個體詞稱作個體變項；常用x,y,z,表示。,全總個體域：由宇宙間一切事物組成的域為全總個體域。,13:26,5,a.小陳是大學生 b.小張生于蘇州 c. 8=3*2 x是大學生 小陳-個體；是大學生-謂詞： 是大學生刻劃了x 的性質(zhì) x生于y 生于-謂詞：刻劃了x和y的關(guān)系,x=y*z .=.-謂詞：刻劃了x，y，z三 元的關(guān)系,一、謂

3、詞和個體,B. 謂詞,13:26,6,B. 謂詞,(1)是自然數(shù)。 (2) 21世紀末，人類將住在月球。 (3) x 與 y 具有關(guān)系L (4) 只有x能被2整除， x才能被4整除。,謂詞：用來刻劃個體詞性質(zhì)及個體詞之間相互關(guān)系的詞,13:26,7,一般的 用F(a)表示個體常項a具有性質(zhì)F（F是謂詞常項或謂詞變項）， 用F(x)表示個體變項x具有性質(zhì)F。 而用F(a, b)表示個體常項a, b具有關(guān)系F， 用F(x, y) 表示個體變項x, y具有關(guān)系F。,定義：一個大寫英文字母后邊有括號，括號內(nèi)是若干個客體變元，用以表示客體的屬性或者客體之間的關(guān)系，稱之為謂詞。如果括號內(nèi)有n個客體變元，稱

4、該謂詞為n元謂詞。,13:26,8,例如 S(x):表示x是大學生。 一元謂詞 G(x,y)：表示 xy。 二元謂詞 B(x,y,z)：表示x在y與z之間。三元謂詞 一般地 P(x1,x2,xn) 是n元謂詞。,0元謂詞：有時將不帶個體變項的謂詞稱為0元謂詞，例如上面提到的F(a)，H(a, b)，P( a1, a2, ,an )等都是0元謂詞，當F, H, P為謂詞常項時，0元謂詞為命題。這樣，命題邏輯中的命題均可表示成0元謂詞，因而可以將命題看成是特殊的謂詞。,13:26,9,(1) 2是素數(shù)且是偶數(shù) (2) 如果2大于3，則2大于4 解：(1)設(shè)一元謂詞F(x)：x是素數(shù)；一元謂詞G(x

5、)：x是偶數(shù)；a：2。 則(1)中命題符號化為0元謂詞的合取式：F(a) G(a)。 (2) 設(shè)二元謂詞L(x, y)：x大于y；a：2；b：3；c：4. L(a,b), L(a,c)是兩個0元謂詞，把(2)中命題符號化為L(a,b) L(a,c),例題：將下列命題用0元謂詞符號化，并討論它們的真值。,13:26,10,x讀作對任意x xP(x)表示對一切x,P(x)為真 xP(x)表示 并非對任意x, P(x)是真,(1)全稱量詞x,C.量詞,13:26,11,x讀作至少有一x，存在一x x P(x)表示 存在一x，使P(x) 為真 x P(x)表示 并非存在一個x，使 P(x)為真,(2)

6、存在量詞x,C.量詞,13:26,12,在P(x)，P(x,y)前加上x或x，稱變元x被存在量化或 全稱量化。,將謂詞F(x)變成命題有兩種方法。 a.將x取定值 例：F(x)表示x是質(zhì)數(shù)，那么F(4)是命題（假） b.將謂詞量化 例：1). xF(x) F(x)：任意的x是質(zhì)數(shù) 2). y(yy+1) 3). y(yy+1),量詞的作用,C.量詞,13:26,13,(1) 分析命題中表示性質(zhì)和關(guān)系的謂詞，分別符號化為一元和n（n 2）元謂詞。 (2) 根據(jù)命題的實際意義選用全稱量詞或存在量詞。 (3) 在不同的個體域中，命題符號化的形式可能不一樣。如果事先沒有給出個體域，都應(yīng)以全總個體域為個

7、體域。 (4)多個量詞同時出現(xiàn)時，不能隨意顛倒它們的順序，顛倒后會改變原命題的含義。,在使用量詞時，應(yīng)注意以下幾點：,13:26,14,(5) 當個體域為有限集時，如D=a1, a2, , an，由量詞的意義可以看出，對于任意的謂詞A(x)，都有 x A(x) A(a1) A(a2) A(an) x A(x) A(a1) A(a2) A(an) 這實際上是將謂詞邏輯中命題公式轉(zhuǎn)化為命題邏輯中的命題公式問題。,13:26,15,1.設(shè)個體域為D=0,1,2,10,將下列命題符號化： (1)D中所有元素都是整數(shù)； (2)D中有的元素是偶數(shù)； (3)D中所有的偶數(shù)都能被2整除； (4)D中有的偶數(shù)是

8、4的倍數(shù)。,D.舉例,xF(x), 其中F(x)：x是整數(shù),xG(x), 其中G(x)：x是偶數(shù),x(G(x) H(x), 其中G(x):x是偶數(shù); H(x):x能被2整除,x(G(x)R(x), 其中G(x):x是偶數(shù); R(x):x是4的倍數(shù),13:26,16,2.設(shè)個體域為D=x|x為人，將下列命題符號化： (1)人都生活在地球上； (2)有的人長著黑頭發(fā)； (3)中國人都用筷子吃飯； (4)有的中國人不住在中國；,D.舉例,xF(x), 其中F(x)：x生活在地球上,xG(x), 其中G(x)：x長著黑頭發(fā),x(H(x) I(x), 其中H(x): x是中國人；I(x)：x用筷子吃飯,

9、x(H(x)R(x), 其中H(x): x是中國人；R(x): x住在中國,13:26,17,D.舉例,3. 用量詞、謂詞來表述命題。 (1)凡是人都是要死的。 (2) 某些實數(shù)是有理數(shù)。 ,x(F(x)H(x), 其中F(x): x是人；H(x):是要死的；,x(G(x)Q(x), 其中G(x): x是實數(shù)；H(x):是有理數(shù)；,4. 在個體域限制為（a）和（b）條件時，將下列命題符號化： （1）對于任意的x，均有x23x2(x1)(x-2) （2） 存在x，使得x53 其中： （a）個體域D1N（N為自然數(shù)集合） （b）個體域D2R（R為實數(shù)集合） 解：(a) 令F(x)：x23x2(x1

10、)(x-2)，G(x)： x53。命題（1）的符號化形式為 x F(x) (*) 命題（2）的符號化形式為 x G(x) (*) 顯然（1）為真命題，而（2）為假命題。 (b) 在D2內(nèi)，（1）與（2）的符號化形式還是(*)和(*)式，（1）仍然為真命題，而此時（2）也為真命題。,13:26,19,謂詞邏輯中命題符號化一般遵循的原則：,(1)名詞：專有名詞多譯為個體常元，如“地球”等；普通名詞一般譯為謂詞，如“自然數(shù)”；,(2)代詞：無論是人稱代詞，如“你”，“我”，“他”等，還是指示代詞，如“這個”，“那個”等多譯為個體常元；,(3)形容詞：多譯為謂詞；,(4)動詞：多譯為謂詞；,(5)數(shù)量

11、詞：表示全體概念的數(shù)量詞，如“每個”、“任何”、“所有”等譯為全稱量詞，表示部分概念的數(shù)量詞，如“有”、“存在”、“若干”、“有些”等，譯為存在量詞；,(6)副詞和前置詞與其它詞類合并，不再進行單獨分析；,(7)連詞一般譯為邏輯聯(lián)結(jié)詞。,13:26,20,定義：不出現(xiàn)命題聯(lián)結(jié)詞和量詞的謂詞命名式 P(X1, X2Xn)稱為謂詞演算的原子公式。,A.原子公式,2.謂詞合式公式,前面例子中的1元謂詞F(x)，G(x)，2元謂詞H(x,y)，L(x,y) 等都是原子公式。,13:26,21,謂詞合式公式簡稱謂詞公式 定義: 1) 原子公式是謂詞合式公式 2)若A， B是謂詞合式公式，則,(A)，(A

12、B)，(AB)，(AB)，(AB)， (XA)和(XA)是謂詞合式公式,3)只有有限次應(yīng)用步驟1)和2)構(gòu)成的公式才是謂詞合式公式,注：由定義知，命題公式也是謂詞公式 例：XR(X) ( XR(X) ) (XR(X) XS(X) ) ( XR(X) XS(X) ) A(BC) 命題公式均是謂詞公式,B.謂詞合式公式,13:26,22,定義:量詞的轄域是鄰接量詞之后的最小子公式，故除非轄域是個原子公式，否則應(yīng)在該子公式的兩端有括號。 例：XP(X)Q(X) X的轄域是P(X) X(P(X,Y)Q(X，Y) ) P(Y,Z) X的轄域是P(X，Y)Q(X，Y),(1)量詞的轄域,C.自由變元與約束

13、變元,13:26,23,定義：在量詞X，X轄域內(nèi)變元X的一切出現(xiàn)叫約束出現(xiàn)，稱 這樣的X為約束變元。,變元的非約束出現(xiàn)稱為自由出現(xiàn),稱這樣的變元為自由變元。,例：指出下列謂詞公式中的自由變元和約束變元，并指明量詞的轄域 X(P(X) R(X) )XP(X) Q(X) 解：表達式中的X(P(X)R(X)中X的轄域是 P(X) R(X),其中的X是約束出現(xiàn) Q(X)中的X是自由變元,13:26,24,例：指出下列謂詞公式中的自由變元和約束變元。 并指明量詞的轄域 (2) X(P(X，Y)YR(X，Y) ) 解：其中的P(X，Y)中的Y是自由變元，X是約束變元， R(X，Y)中的X，Y是約束變元。,

14、注：在一個公式中，一個變元既可以約束出現(xiàn)，又可以 自由出現(xiàn)。為避免混淆可用改名規(guī)則對變元改名。,13:26,25,(1)若要改名，則該變元在量詞及該量詞的轄域中的所有 出現(xiàn)須一起更改。,(2)改名時所選用變元必須是量詞轄域內(nèi)未出現(xiàn)的，最好 是公式中未出現(xiàn)的。,注：對自由變元換名，可稱為代入,D. 約束變元改名規(guī)則,13:26,26,例1：X(P(X，Y)YR(X，Y) ) 可改為 X(P(X，Y)ZR(X，Z) ) 例2：XP(X) Q(X) 可改為YP(Y) Q(X) 例3：X(A(X)B(X，Y)C(X)D(W) 可改為： X(A(X)B(X，Y) )C(Z) D(W) 注意： Z(A(Z

15、)B(Z，Y) ) C(X) D(W)不可改為： Y(A(Y)B(Y，Y) ) C(X) D(W),13:26,27,E.閉公式,定義：設(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 y L(x,y,z)都不是閉式。 要想使含有r(r1)個自由出現(xiàn)個體變項的公式變成閉式，至少要加上r個量詞,13:26,28,例題：在一階邏輯中將簡單的數(shù)學命題符號化,1.設(shè)個體域為整數(shù)集合Z，將下列問題符號化： (1)對于任意的x和y，存在著z，使得x+y=z;

16、 (2)存在著x，對于任意的y和z，均有y-z=x是不成立的。 (3)設(shè)y=f(x)在x=x0處連續(xù)，將下面命題符號化。任給Z0 ，存在d 0,使得當|x-x0| d 時，均有|f(x)-f(x0)|Z.,xyz(x+y=z),(xyz(x2+y2=z2),Z0d0(|x-x0| d |f(x)-f(x0)|Z),13:26,29,謂詞公式的解釋：,定義 一個解釋I由下面4部分組成： （1）非空個體域D； （2）D中一些特定元素的集合 （3）D上特定函數(shù)集合 （4）D上特定謂詞的集合,在I 下，下列哪些公式為真？哪些為假？哪些的真值還不能確定？,(1) F(f(x,y),g(x,y),在I下，

17、被解釋成 “x+y=xy”, 這不是命題,(2) F(f(x,a),y)F(g(x,y),z),在I下，被解釋成 “(x+0=y)(xy=z)”, 這不是命題,(3) F(g(x,y), g(y,z),在I下，被解釋成 “xyyz”, 這不是命題,(4) xF(g(x,y),z),在I下，被解釋成 “x( xyz)”, 這不是命題,(5) xF(g(x,a),x)F(x,y),在I下，被解釋成 “x( x0=x) (x=y)”, 由于蘊含式前件為假，所以被解釋的公式為真。,(6) xF(g(x,a),x),在I下，被解釋成 “x( x0=x)”, 這不是命題,(7) xy F(f(x,a),y

18、) F(f(y,a),x),在I下，被解釋成 “xy( x+0=y) (y+0=x)”, 這是真命題,(8) xyz F(f(x,y),z),在I下，被解釋成 “xyz(x+y=z)”, 這是真命題,(9) x F(f(x,x),g(x,x),在I下，被解釋成 “x(x+x=xx)”, 這是真命題,解 為方便起見，用A，B，C分別記(1)，(2)，(3)中的公式。 (1)取解釋I1:個體域為實數(shù)集合R，F(xiàn)(x):x是整數(shù)，G(x):x是有理數(shù)。在I1下A為真，因而A不是矛盾式。取解釋I2:個體域仍然為R，F(xiàn)(x):x是無理數(shù)，G(x):x能表示成分數(shù)。在I2下A為假，所以A不是永真式。故A是非永真式的可滿足式。 (2)易知B是命題公式p(qp)的代換實例，而該命題公式是重言式，所以B是永真式。 (3)C是命題公式(pq)q的代換實例，而該命題公式是矛盾式，所以C是矛盾式。,13:26,32,注：,在證明一個謂詞公式既不是永真式也不是矛盾式時，可以為公