一階謂詞原理.ppt

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

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

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

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

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

6、存在量詞x,C.量詞,13:26,12,在P(x)，P(x,y)前加上x或x，稱變?cè)獂被存在量化或 全稱量化。,將謂詞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)系的謂詞，分別符號(hào)化為一元和n（n 2）元謂詞。 (2) 根據(jù)命題的實(shí)際意義選用全稱量詞或存在量詞。 (3) 在不同的個(gè)體域中，命題符號(hào)化的形式可能不一樣。如果事先沒(méi)有給出個(gè)體域，都應(yīng)以全總個(gè)體域?yàn)閭€(gè)

7、體域。 (4)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能隨意顛倒它們的順序，顛倒后會(huì)改變?cè)}的含義。,在使用量詞時(shí)，應(yīng)注意以下幾點(diǎn)：,13:26,14,(5) 當(dāng)個(gè)體域?yàn)橛邢藜瘯r(shí)，如D=a1, a2, , an，由量詞的意義可以看出，對(duì)于任意的謂詞A(x)，都有 x A(x) A(a1) A(a2) A(an) x A(x) A(a1) A(a2) A(an) 這實(shí)際上是將謂詞邏輯中命題公式轉(zhuǎn)化為命題邏輯中的命題公式問(wèn)題。,13:26,15,1.設(shè)個(gè)體域?yàn)镈=0,1,2,10,將下列命題符號(hào)化： (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è)個(gè)體域?yàn)镈=x|x為人，將下列命題符號(hào)化： (1)人都生活在地球上； (2)有的人長(zhǎng)著黑頭發(fā)； (3)中國(guó)人都用筷子吃飯； (4)有的中國(guó)人不住在中國(guó)；,D.舉例,xF(x), 其中F(x)：x生活在地球上,xG(x), 其中G(x)：x長(zhǎng)著黑頭發(fā),x(H(x) I(x), 其中H(x): x是中國(guó)人；I(x)：x用筷子吃飯,

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

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

11、詞：表示全體概念的數(shù)量詞，如“每個(gè)”、“任何”、“所有”等譯為全稱量詞，表示部分概念的數(shù)量詞，如“有”、“存在”、“若干”、“有些”等，譯為存在量詞；,(6)副詞和前置詞與其它詞類合并，不再進(jìn)行單獨(dú)分析；,(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,謂詞合式公式簡(jiǎn)稱謂詞公式 定義: 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,定義:量詞的轄域是鄰接量詞之后的最小子公式，故除非轄域是個(gè)原子公式，否則應(yīng)在該子公式的兩端有括號(hào)。 例：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.自由變?cè)c約束

13、變?cè)?13:26,23,定義：在量詞X，X轄域內(nèi)變?cè)猉的一切出現(xiàn)叫約束出現(xiàn)，稱 這樣的X為約束變?cè)?變?cè)姆羌s束出現(xiàn)稱為自由出現(xiàn),稱這樣的變?cè)獮樽杂勺冊(cè)?例：指出下列謂詞公式中的自由變?cè)图s束變?cè)?，并指明量詞的轄域 X(P(X) R(X) )XP(X) Q(X) 解：表達(dá)式中的X(P(X)R(X)中X的轄域是 P(X) R(X),其中的X是約束出現(xiàn) Q(X)中的X是自由變?cè)?13:26,24,例：指出下列謂詞公式中的自由變?cè)图s束變?cè)?并指明量詞的轄域 (2) X(P(X，Y)YR(X，Y) ) 解：其中的P(X，Y)中的Y是自由變?cè)琗是約束變?cè)?R(X，Y)中的X，Y是約束變?cè)?

14、注：在一個(gè)公式中，一個(gè)變?cè)瓤梢约s束出現(xiàn)，又可以 自由出現(xiàn)。為避免混淆可用改名規(guī)則對(duì)變?cè)拿?13:26,25,(1)若要改名，則該變?cè)诹吭~及該量詞的轄域中的所有 出現(xiàn)須一起更改。,(2)改名時(shí)所選用變?cè)仨毷橇吭~轄域內(nèi)未出現(xiàn)的，最好 是公式中未出現(xiàn)的。,注：對(duì)自由變?cè)獡Q名，可稱為代入,D. 約束變?cè)拿?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)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡(jiǎn)稱閉式。 例如，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)個(gè)自由出現(xiàn)個(gè)體變項(xiàng)的公式變成閉式，至少要加上r個(gè)量詞,13:26,28,例題：在一階邏輯中將簡(jiǎn)單的數(shù)學(xué)命題符號(hào)化,1.設(shè)個(gè)體域?yàn)檎麛?shù)集合Z，將下列問(wèn)題符號(hào)化： (1)對(duì)于任意的x和y，存在著z，使得x+y=z;

16、 (2)存在著x，對(duì)于任意的y和z，均有y-z=x是不成立的。 (3)設(shè)y=f(x)在x=x0處連續(xù)，將下面命題符號(hào)化。任給Z0 ，存在d 0,使得當(dāng)|x-x0| d 時(shí)，均有|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,謂詞公式的解釋：,定義 一個(gè)解釋I由下面4部分組成： （1）非空個(gè)體域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)”, 由于蘊(yùn)含式前件為假，所以被解釋的公式為真。,(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:個(gè)體域?yàn)閷?shí)數(shù)集合R，F(xiàn)(x):x是整數(shù)，G(x):x是有理數(shù)。在I1下A為真，因而A不是矛盾式。取解釋I2:個(gè)體域仍然為R，F(xiàn)(x):x是無(wú)理數(shù)，G(x):x能表示成分?jǐn)?shù)。在I2下A為假，所以A不是永真式。故A是非永真式的可滿足式。 (2)易知B是命題公式p(qp)的代換實(shí)例，而該命題公式是重言式，所以B是永真式。 (3)C是命題公式(pq)q的代換實(shí)例，而該命題公式是矛盾式，所以C是矛盾式。,13:26,32,注：,在證明一個(gè)謂詞公式既不是永真式也不是矛盾式時(shí)，可以為公