8一階邏輯-概念公式4-14-1

1、例：第四章 一階邏輯基本概念 4.1 一階邏輯的符號化 一、命題的分解 命題(陳述句） 主語 和 謂語 個體 和 謂詞 分解為： 對象 及 對象的性質(zhì)、特征及關(guān)系 來討論命題邏輯所不能反映的命題的內(nèi)在聯(lián)系及其微觀結(jié)構(gòu)二、謂詞 1.個體 個體詞是指所研究對象中可以獨立存在的具體的或抽象的客體 1）一般用小寫字母表示：x,y,z,s,t . 2）個體常元和個體變元 具體的個體或 a,b,c。 個體變元x,y,z.變元 3）個體域（個體的取值范圍） 全總個體域12謂詞：謂詞是用來刻劃個體詞性質(zhì)及個體詞之間相互關(guān)系的詞 1) 謂詞一般用大寫字母表示：F、H、L、G 2)謂詞所關(guān)聯(lián)個體的個數(shù) 謂詞所關(guān)聯(lián)

2、的個體個數(shù)是一個稱該謂詞為一元謂詞F(x)、G(x) F(x)：x是人 G(x)：x是整數(shù) D(x):x是要死的 謂詞所關(guān)聯(lián)的個體個數(shù)是兩個稱該謂詞為二元謂詞L(x,y) L(x,y)：x y H(x,y):x比y跑的快 謂詞所關(guān)聯(lián)的個體個數(shù)是三個稱該謂詞為三元謂詞H(x,y,z) H(x,y,z)：x位于y與z之間 n元謂詞T（x1,x2.xn） 前面的命題由于不包含個體變元0元謂詞 3）命題函數(shù) 謂詞中的個體是具體的客體謂詞為命題（具有真值） 謂詞中的個體是泛指的任何客體謂詞為命題函數(shù)（不是命題） （不具有真值） 其真值由給定的客體所確定2 F(x）：x 是無理數(shù) G（x）：x是有理數(shù) 那

3、么 F（2）為真 , F（2）為假， G（e ）為假、G（4） 為真 L（x,y）: x與y是同學(xué), L（小王，小李）具有真值 L（x，y）不具有真值,為命題函數(shù) H（x,y,z）: x位于y、z之間， H（北京，鄭州，廣州）為假 H（鄭州，北京，廣州）為真 若4大于3且3大于2 ，則4大于2 設(shè)謂詞：L（x,y）: x大于y, 可符號化為：L（x,y）L（y,z）L（x,z）為命題函數(shù) 而 L（4,3）L（3,2）L（4,2）是真命題有的謂詞雖然含有任意個體，但也具有一定的邏輯真值： 任何數(shù)如果是整數(shù)則一定都是偶數(shù)是假命題符號化命題只有2是素數(shù)，4才是素數(shù)F(x):x是素數(shù) a:2 b:4

4、F(b) F(a) 真如果5大于4，則4大于6 L（5,4） L（4,6）假3僅有個體與謂詞還不能準(zhǔn)確表示一些邏輯問題 如：N（x）：x是整數(shù)， O（x）:x是偶數(shù) 所有的整數(shù)是偶數(shù)可符號化為 N（x） O（x） 肯定為假 其否定應(yīng)為真. 但 （N（x）O（x）等值于 N（x）O（x） 即： 所有的整數(shù)且不是偶數(shù)也為假 主要原因是：沒有體現(xiàn)整體和個別的關(guān)系 所以在描述時必須引入反映數(shù)量關(guān)系的詞3. 量詞 1）全稱量詞 表示日常生活和數(shù)學(xué)中常用的“一切的”，“所有的”，“每一個”、 “任意的”，“凡”，“都”等詞可統(tǒng)稱為全稱量詞 用xf(x)，yG(y)等分別表示個體域里所有個體都有性質(zhì)F和都有

5、性質(zhì)G 4 2) 存在量詞- 表示日常生活和數(shù)學(xué)中常用的“存在”，“有一個”，“有的”，“至少有一個”等詞統(tǒng)稱為存在量詞. 并用x，y等表示個體域里有的個體，而用xF(x)，yG(y)等分別表示在個體域里存在個體具有性質(zhì)F和存在個體具有性質(zhì)G等 4.一階邏輯的符號化 要理解自然語言的真實含義，體會出整體和存在的意思 1）謂詞的設(shè)定 2）量詞的選定 例： 3）個體域的選取，在未特別說明情況下一般是指全總個體域但對于描述的具體具體要選用適當(dāng)?shù)奶匦灾^詞來進行限定：特性謂詞：確定個體對象、性質(zhì)的謂詞（一般為一元謂詞） F(x)：x是人 R(x)：x是實數(shù) H(x)：x是貓 等54) 從邏輯上一般用全稱

6、量詞及蘊涵連接詞來表示“所有x具有性質(zhì)B”的情況 5) 從邏輯上一般用存在量詞及合取連接詞來表示“某些x具有性質(zhì)B”的情況(6)“對于D中所有x，y而言，若x有性質(zhì)F，y有性質(zhì)G，則x與y就有關(guān)系H”，則符號化為 : xy(F(x) G(y) H(x，y) 例：貓必捉鼠 再看(7)“對于D中所有x而言，若x有性質(zhì)F，就存在y有性質(zhì)G，使得x與y有關(guān)系H”，符號化為: x(F(x) y(G(y) H(x，y) 例： 不存在最大的整數(shù)6 (8)“存在著D中x有性質(zhì)F，并且對D中所有的y而言，如果y有性質(zhì)G，則x與y就有關(guān)系H”， 符號化為: x(F(x) y(G(y) H(x，y) 例：存在最大的

7、整數(shù)在使用量詞時要注意：1、在不同的個體域，謂詞的符號化形式可能不同，而且其真值也可能不同。2、對于未指出個體域時，均認(rèn)為是全總個體域3、多個量詞出現(xiàn)時不能隨意交換它們的位置，否則會得到錯誤的結(jié)論。作業(yè)： 習(xí)題四 1（奇數(shù)）、2、4（奇數(shù)）、5（奇數(shù)）轉(zhuǎn)一階公式71、無法判斷一些簡單而常見的推理考慮下面的推理： 著名的“蘇格拉底(Socrates，古希臘哲學(xué)家，公元前470399)論證”就是如此：p: “所有的人總是要死的。 q: 因為蘇格拉底是人。 r: 所以蘇格拉底總是要死的?！睉{直覺就能知道這個結(jié)論是真的，但是借助于命題演算的推理理論，卻不能推導(dǎo)出這個結(jié)論來。 即公式 (pq) r 并不

8、是重言式2、無法了解 命題 的結(jié)構(gòu) 和內(nèi)在聯(lián)系(1)張華是個勞動英雄。(2)李明是個勞動英雄。 兩個命題具有共同的性質(zhì)（內(nèi)在聯(lián)系） （3）x是個勞動英雄 (4)小王與小劉同學(xué) 張華與李明是同學(xué) 兩個命題具有共同的性質(zhì)（內(nèi)在聯(lián)系：x與y是同學(xué) ）命題邏輯將命題看成一個整體，不能研究它的內(nèi)部結(jié)構(gòu)。 命題(陳述句） 主語 和 謂語 將命題的分解開 個體 和 謂詞返回8返回凡人都呼吸（個體域為人的集合）F(x): x呼吸 x F(x)x F(x) 沒有不呼吸的人沒有不怕死的人M(x):x是人； F(x): x不怕死 x（M(x) F(x)x(M(x) F(x) 凡人都怕死例： 人總是要死的（隱含著所有

9、人的意思）設(shè)謂詞：M(x)：x是人 D（x）:x是要死的 個體域為全總 x ( M（x）D（x）) 例：在美國留學(xué)的人未必都是亞洲人 有的人登上過月球 在北京工作的并非都是北京人 沒有人登上過木星 凡偶數(shù)都能被2整除 6是偶數(shù)， 所以6能被2整除。9對于出現(xiàn)多個變元的情況： 令F(X)：X是兔子，G(y)：y是烏龜 H(x，y)：x比y跑得快，L(x，y)：x與y跑得同樣快(1)兔子比烏龜跑得快(2)有的兔子比所有的烏龜跑得快(3)并不是所有的兔子都比烏龜跑得快(4)不存在跑得同樣快的兩只兔子 這4個命題分別符號化為 xy( F(X)G(y) H(x,y) ) X(F(X) y(G(y)H(x

10、，y) xy(F(x)G(y)H(x，y) xy(F(x)F(y)L(x，y) 任何兩個兔子跑的不同樣快 返回10 4.2 一階邏輯公式及解釋一、一階語言F定義（字母表） (1)個體常項：a,b,c,d，a1,a2，ai i1 (2)個體變項：x，y，z，xi，yi，zi， i1 (3)函數(shù)符號：f，g，h，fi，gi，hi， i1 (4)謂詞符號：F，G，H，F(xiàn)i，Gi，Hi， i1 (5)量詞符號：， (6)聯(lián)結(jié)詞符號：，1. F 下的合式公式定義如下： (1)原子公式是合式公式 (2)若A是合式公式，則(A)也是合式公式 (3)若A，B是合式公式，則(AB)，(A B)，(AB)， (A

11、 B)也是合式公式 (4)若A是合式公式，則xA，xA也是合式公式 (5)只有有限次地應(yīng)用(1)(4)構(gòu)成的符號串才是合式公式 合式公式也稱為謂詞公式，簡稱公式112、量詞的轄域:量詞所界定的子公式3、自由變項和約束變項： 在公式xA和xA中，稱x為指導(dǎo)變元，A為相應(yīng)量詞的轄域 在x和X的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)， A中不是約束出現(xiàn)的其他變項均稱為是自由出現(xiàn)的 例 考察下面謂詞公式 (1)(x)P(x，y) P(x，y)中的y為自由變項，x為約束的 (2)(x)(P(x)(y)R(x，y) x,y均為約束變元 (3)(x)(P(x)R(y)(y)(F(x)Q(y) P(x)中的x為約

12、束的， R(y)中的y為自由變元 F(x)Q(y) 中的x為自由的，y為約束的 公式中的x與y均為雙重身份（即自由又約束） (4)(x)P(x)Q(x) (5) x y( R(x,y)L(y,z) )x H(x,y) 12 二、公式的解釋（相當(dāng)于命題公式的賦值） 按合式公式的形成規(guī)則形成的符號串是F中的公式，這種公式?jīng)]有確定意義一旦將其中的變項(項的變項，謂詞變項等)用指定的常項代替后，所得公式就具備一定意義，有時就變成命題了 一個解釋不外乎指定個體域、個體域中一些特定的元素、特定的函數(shù)和謂詞等部分1、公式的解釋 1）定義：F的解釋I的內(nèi)容一般由下面4部分組成： (a)指定非空個體域DI （個

13、體域的取值范圍） (b)指定DI中一些特定元素(常量)的集合a1,a2，ai (c)給定DI上特定函數(shù)集合fi | i 1 具體的函數(shù) (d)給定DI上特定謂詞的集合 Hi | i1 具體的謂詞 在解釋I下的公式A中的個體變項均取值于DI 被解釋I下的公式不一定全部包含解釋中的四部分4、閉式定義 設(shè)A是公式，若A中不含自由出現(xiàn)的個體變項則稱A為封閉的公式，簡稱閉式13 閉式在給定的解釋中都變成了命題(具有真值）結(jié)論： 定理41 封閉的公式在任何解釋下都變成命題 如：謂詞公式) x)(F(x) G(x) 是閉式 F(x):x是人 G (x):x是黃種人 上式為假 F(x):x是人 G (x):x

14、是要死的 上式為真 F(x):x是自然數(shù) G (x):x是整數(shù) 上式為真 注： 對于不是閉式的謂詞公式則不能成為任何命題是命題函數(shù)確定謂詞公式的真值：1) F(f(x,y),g(x,y) 2) F(f(x,a),y)F(g(x,y),z)3)x F(g(x,y), z) 4)x(F(g(x,a),x)F(x,y) )5)xy(F(f(x,a),y) F(f(y,a),x) ) 6)xyz F(f(x,y),z) 例：給定解釋I 1）個體域DI為自然數(shù)集合 2） a=0 3)函數(shù) f(x,y)=x+y, g(x,y)=xy 4)謂詞 F(x,y): x=y14確定謂詞公式的真值：1) F(f(x

15、,a1),g(x,a1) 2) xy F( f(x,y),g(x,y) )3) x y F(f(x,y),g(x,y) ) 4)y( F(y,a0)x(F( f(x,y),g(x,y) ) )5)yx( F(x,y) F(f(x,y),x) ) 6) F(f(x,y),g(x,y) 7) x ( F(x,a0) F( f(x,y),g(x,y) ) )例：給定解釋I 1）個體域為整數(shù)集合Z 2） Z上的特定元素 a0=0，a1=1; 3)Z上的特定函數(shù) f(x,y)=x-y, g(x,y)=x+y； 4)Z上的特定謂詞 F(x,y): x y;1) (x - 1 ) (x+1 ) 不是閉式 ，

16、但在此解釋下是命題 T 2) xy( (x-y) (x+y) ) F3) x y ( (x-y) (x+y) ) T4)y( (y0)x( (x-y) (x+y) ) ) ) T5)yx( (x y) ( (x-y) x ) ) F6) ( (x-y) (x+y) ) 不是閉式 7) x ( (x0) ( (x-y) (x+y) ) ) 不是閉式 15注：1有的公式在具體的解釋中真值確定，即變成了命題有的公式在某些解釋中真值仍然不能確定，因而仍然不是命題。2閉式在任何解釋中都成為命題不太嚴(yán)謹(jǐn)?shù)卣f，由于在閉式中，每個個體變項都受量詞的約束，因而在具體解釋中總表達一個意義確定的語句，即一個真命題或

17、一個假命題3不是閉式的公式在某一解釋中，可能成為命題，也可能不能成為命題。6.謂詞公式的分類定義： 設(shè)A為一公式，若A在任何解釋下均為真，則稱A為永真式(或稱邏輯有效式)若A在任何解釋下均為假，則稱A為矛盾式(或永假式)若至少存在一個解釋使A為真，則稱A是可滿足式 注：在一階邏輯中，由于公式的復(fù)雜性和解釋的多樣性，到目前為止，還沒有找到一種可行的算法，對某些特殊的公式還是可以判斷的。 可以利用一些特殊方法來進行判斷：16 7. 代入實例 定義 設(shè)A0是含命題變項p1，p2，pn的命題公式，A1，A2，An是 n個謂詞公式，用Ai(1in)處處代替A0中的pi所得公式A稱為A0的代換實例 如：x

18、F(x) x G(x) A(x) B(x) 都是p q的代入實例 x( F(x) G(x) 是否是p q的代入實例？定理42 重言式的代換實例都是永真式，矛盾式的代換實例都是矛盾式 這樣由命題邏輯的許多重言式可得到謂詞公式相應(yīng)的重言式 （只要能確定是那個重言式的代換實例）看謂詞公式：（(x)p(x) (y)q(y) ） (x)p(x) (y)q(y) 而 ( p q ) p q 是永真式 注意它們之間的關(guān)系從命題公式中的永真式（矛盾式）來得到判別17判斷下列公式中，哪些是永真式，哪些是矛盾式? （通過找到代入實例） (1) xF(x)(xyG(x，y)xF(x)因為可設(shè) p: x F(x) q : xy G(x,y) 原式可表示為 p(q p) p (qp) 1 q 1 是命題公式 p (q p)的代換實例，而該命題公式是重言式，所以該式是永真式 (2) (xF(x)yG(y)yC(y) 該式是命題公式 (p q )q 的代換實例， 而該命題公式是矛盾式，所以該式是矛盾式 可通過否定是重言式和矛盾式得到公式為可滿足式x(F(x) G(x) 取解釋I：個體域為實數(shù)集合R，F(xiàn)(x)：x是整數(shù)，G(x)：x是有理數(shù) 在I下該式為真，因而該式不是矛盾式 取解釋2：個體域仍為R，F(xiàn)(x)：x是無理數(shù)，G(X)：x能表示成分?jǐn)?shù) 在2下該式為假