階邏輯基本概念(調(diào)整).ppt

1、第4章 一階邏輯基本概念,離 散 數(shù) 學(xué),1.1階邏輯的基本概念 2.1階邏輯命題符號化 3.1階邏輯的公式、解釋、分類,1.明確一階邏輯的相關(guān)概念 2.熟練將一階邏輯命題符號化 3.掌握1階邏輯公式的解釋,一階邏輯命題的符號化,1階邏輯公式的解釋,基本問題：,基本要求：,教學(xué)重點：,教學(xué)重點：,第4章 一階邏輯基本概念,本章說明,本章與后續(xù)各章的關(guān)系 克服命題邏輯的局限性 是第五章的先行準(zhǔn)備,引言,問題：命題邏輯的局限性 在命題邏輯中，研究的基本單位是簡單命題， 對簡單命題不再進行分解，并且不考慮命題 之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系。 例如：所有的人都是要死的，蘇格拉底是人，所以 蘇格拉底是要死的

2、。 這是著名的蘇格拉底三段論，但卻無法用命題邏輯予以證明。,蘇格拉底；著名的古希臘的思想家、哲 學(xué)家、教育家.學(xué)生柏拉圖柏、拉圖的學(xué) 生亞里士多德-“古希臘三賢”，更被后人 廣泛認為是西方哲學(xué)的奠基者。,引言,一階邏輯所研究的內(nèi)容： 為了克服命題邏輯的局限性，將簡單命題再細分，分析出個體詞、謂詞和量詞，以期達到表達出個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系。,第一節(jié) 一階邏輯命題符號化,一階邏輯命題符號化的三個基本要素,謂詞 謂詞 謂詞常項 謂詞變項 特性謂詞,量詞 存在量詞 全稱量詞,個體詞 個體詞 個體常項 個體變項 個體域（論域） 全總個體域,基本概念,1.個體詞（個體）：指所研究對象中可以獨立存

3、在的具 體或抽象的客體（名詞或代詞充當(dāng)） 例如： 命題：電子計算機是科學(xué)技術(shù)的工具。個體詞：電子計算機。 命題：他是三好學(xué)生。個體詞：他。,（1）個體常項：具體的事物，用a, b,c，表示 （2）個體變項：抽象的事物，用x,y,z,表示。 （3）個體域（或稱論域）：個體變項的取值范圍。 有限個體域，如a, b, c, 1, 2。 無限個體域，如N,Z,R,。 全總個體域，宇宙間一切事物組成 。,基本概念,本教材在論述或推理中，如果沒有指明所采用的個體域，都是使用的全總個體域。,說明,基本概念,2.謂詞：表示個體詞性質(zhì)或相互之間關(guān)系的詞 例如：(1) 是無理數(shù) 是個體常項，“是無理數(shù)”是謂詞，記

4、為F，命題符號化 為F() 。 (2) x是有理數(shù) x是個體變項，“是有理數(shù)”是謂詞，記為G，命題符號化 為G(x)。 (3) 小王與小李同歲 小王、小李都是個體常項，“與同歲”是謂詞，記為H， 命題符號化為H(a,b) ，其中a：小王，b：小李。 (4) x與y具有關(guān)系L x，y都是個體變項，謂詞為L，命題符號化為L(x,y)。,（1）謂詞常項：表示具體的性質(zhì)或關(guān)系的謂詞。 F：。是人，F(xiàn)（a）:a是人 （2）謂詞變項：表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞。 F：。具有性質(zhì)F，F(xiàn)（x）: x具有性質(zhì)F （3）n(n1)元謂詞： n=1時，一元謂詞表示事物的性質(zhì)。 n2時，多元謂詞表示事物之間的

5、。 L(x，y)：x和y具有性質(zhì)L （4）0元謂詞：不含個體變項的謂詞。 如F(a)、G(a,b)、P(a1,a2,an)。,基本概念,n元謂詞是命題嗎？ 0元謂詞是命題嗎？ 兩者有什么區(qū)別？,思考,3.量詞：是表示個體常項或個體變項之間數(shù)量關(guān)系的詞。 （1）全稱量詞：符號化為“”， x 日常生活和數(shù)學(xué)中所用的“一切的”、“所有的”、“每一個”、“任意的”、“凡”、“都”等詞可統(tǒng)稱為全稱量詞。 x表示個體域里的所有個體，xF(x)表示個體域里所有個體都有性質(zhì)F。 （2）存在量詞：符號化為“” ，y 日常生活和數(shù)學(xué)中所用的“存在”、“有一個”、“有的”、“至少有一個”等詞統(tǒng)稱為存在量詞。 y表示

6、個體域里有的個體，yG(y)表示個體域里存在個體具有性質(zhì)G等。,基本概念,例4.1： 在個體域分別限制為(a)和(b)條件時，將下面兩 個命題符號化: (1) 凡人都呼吸。 (2) 有的人用左手寫字。 其中:(a)個體域D1為人類集合； (b)個體域D2為全總個體域。,一階邏輯命題符號化,x,x,解：(a)個體域為人類集合,令F(x):x呼吸。G(x):x用左手寫字,(1)在個體域中除了人外，再無別的東西，因而“凡人都呼吸” 應(yīng)符號化為,F(x),(2)在個體域中除了人外，再無別的東西，因而“有的人用左 手寫字”符號化為：,G(x),一階邏輯命題符號化,(b)個體域為全總個體域,即除人外，還有

7、萬物，所以必須考慮將人先分離出來,令F(x):x呼吸。 G(x):x用左手寫字。 M(x):x是人,(1) “凡人都呼吸”應(yīng)符號化為,(M(x)F(x),x,(2) “有的人用左手寫字”符號化為,(M(x)G(x),x,2.同一命題在不同的個體域中符號化的形式可能不同。,思考：在全總個體域中， 能否將(1)符號化為x(M(x)F(x)？ 能否將(2)符號化為x(M(x)G(x)？,注意：,1.在使用全總個體域時，要將人從其他事物中區(qū)別出來， 為此引進了謂詞M(x)，稱為特性謂詞,例4.2： 在個體域限制為(a)和(b)條件時，將下列命題符號化: (1) 對于任意的x，均有x2-3x+2=(x-

8、1)(x-2)。 (2) 存在x，使得x+5=3。 其中: (a)個體域D1=N(N為自然數(shù)集合) (b)個體域D2=R(R為實數(shù)集合) (a)令F(x): x2-3x+2=(x-1)(x-2)，G(x): x+5=3。 命題(1)的符號化形式為x F(x) （真命題） 命題(2)的符號化形式為x G(x) （假命題） (b)在D2內(nèi)，(1)和(2)的符號化形式同(a)，皆為真命題。,一階邏輯命題符號化,說明,1.在不同個體域內(nèi)，同一個命題的符號化形式可能不同，也可能相同。,2.同一個命題，在不同個體域中的真值也可能不同。,例4.3 ：將下列命題符號化，并討論真值。 （1）所有的人長著黑頭發(fā)。

9、 （2）有的人登上過月球。 （3）沒有人登上過木星。 （4）在美國留學(xué)的學(xué)生未必都是亞洲人。,例題,謂詞邏輯中命題的符號化，主要考慮以下問題： 非空個體域的選取 量詞的使用及作用范圍 正確地語義,1.全稱量詞的選取注 意和蘊含式的結(jié)合。 2.存在量詞的選取注意 和合取式的結(jié)合。,1.若是為了確定命題的真值，一 般約定在某個個體域上進行。 2.在由一切事物構(gòu)成的全總個體 域上考慮問題時，需要增加一 個指出個體變量變化范圍的特 性謂詞。,特別提醒,解：沒有提出個體域，所以認為是全總個體域,（1）所有的人長著黑頭發(fā)。,令F(x):x長著黑頭發(fā)， M(x):x是人。 命題符號化為,M(x),F(x),

10、),(,x,命題真值為假,（2）有的人登上過月球。,令G(x):x登上過月球， M(x):x是人。 命題符號化為：,(M(x)G(x)。,x,命題真值為真。,例題,（3）沒有人登上過木星,令H(x):x登上過木星， M(x):x是人,命題符號化為：,(M(x)H(x),x,命題真值為真,（4）在美國留學(xué)的學(xué)生未必都是亞洲人,令F(x):x是在美國留學(xué)的學(xué)生，G(x):x是亞洲人,命題符號化為：,(F(x)G(x),x,命題真值為真,例題,一階邏輯命題符號化時需要注意的事項,1.分析命題中表示性質(zhì)和關(guān)系的謂詞， 分別符號為一元和n（ n2）元謂詞。 2.根據(jù)命題的實際意義選用全稱量詞或存在量詞。

11、 3.一般說來，多個量詞出現(xiàn)時，它們的順序不能隨意調(diào)換。 例如：考慮個體域為實數(shù)集，H(x，y)表示x+y=10， 則命題“對于任意的x，都存在y，使得x+y=10”的符號化 形式為xyH(x,y) 真命題。 如果改變兩個量詞的順序，得yxH(x,y) 假命題。,第二節(jié) 一階邏輯公式及解釋,同在命題邏輯中一樣，為在一階邏輯中進行演算和推理，必須給出一階邏輯中公式的抽象定義，以及它們的分類及解釋。,一階語言F的字母表,定義4.1 ：一階語言F的字母表定義如下: (1)個體常項：a , b , c , , ai , bi , ci , , i 1 (2)個體變項：x , y , z, , xi ,

12、 yi , zi , , i 1 (3)函數(shù)符號：f , g , h , , fi , gi , hi , , i 1 (4)謂詞符號：F , G , H , , Fi , Gi , Hi , , i 1 (5)量詞符號: ， (6)聯(lián)結(jié)詞符號:, (7)括號與逗號:(,),，,一階語言：是用于一階邏輯的形式語言。,一階語言F的項,定義4.2： 一階語言F的項的定義如下: (1) 個體常項和個體變項是項。 (2) 若(x1,x2,xn)是任意的n元函數(shù)，t1,t2,tn是任意的n個項，則(t1,t2,tn)是項。 (3) 所有的項都是有限次使用(1)，(2)得到的。,一階語言F的原子公式,定義

13、4.3:(一階語言F的原子公式) 設(shè)R(x1 ,x2 , ,xn)是一階語言F的任意n元謂 詞， t1 ,t2 , ,tn是一階語言F的任意的n個 項，則稱R(t1 ,t2 , ,tn)是一階語言F的原子公式。 例如：1元謂詞F(x)，G(x)，2元謂詞H(x,y)，L(x,y)等都 是原子公式。,一階語言F的合式公式,定義4.4 一階語言F的合式公式定義如下: (1) 原子公式是合式公式。 (2) 若A是合式公式，則(A)也是合式公式。 (3) 若A，B是合式公式，則(AB)，(AB)，(AB)，(AB) 也是合式公式。 (4) 若A是合式公式，則xA，xA也是合式公式。 (5) 只有有限次

14、的應(yīng)用(1)(4)構(gòu)成的符號串才是合式公式。 一階語言F的合式公式也稱為謂詞公式，簡稱公式。,A，B代表任意公式，是元語言符號。 下文的討論都是在一階語言F中，因而不再提及。,說明,自由出現(xiàn)與約束出現(xiàn),定義4.5： 指導(dǎo)變元-在公式xA和xA中，稱x為指導(dǎo)變元。 轄域-在公式xA和xA中，A為相應(yīng)量詞的轄域。 約束出現(xiàn)-在x和x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)。 自由出現(xiàn)-A中不是約束出現(xiàn)的其他變項均稱為是自由出現(xiàn)的。,例4.6 指出下列各公式中的指導(dǎo)變元，各量詞的轄域，自由出 現(xiàn)以及約束出現(xiàn)的個體變項。 (1) x(F(x,y)G(x,z) (2) x(F(x)G(y)y(H(x)L(x

15、,y,z),例題,解答,(1) x是指導(dǎo)變元。量詞的轄域A=(F(x,y)G(x,z)。在A中，x的兩次出現(xiàn)均是約束出現(xiàn)。y和z均為自由出現(xiàn)。 (2) 前件上量詞的指導(dǎo)變元為x，量詞的轄域A=(F(x)G(y)，x在A中是約束出現(xiàn)的，y在A中是自由出現(xiàn)的。后件中量詞的指導(dǎo)變元為y， 量詞的轄域為B=(H(x)L(x,y,z)，y在B中是約束出現(xiàn)的，x、z在B中均為自由出現(xiàn)的。,閉式,定義4.6： 設(shè)A是任意的公式，若A中不含有自由出現(xiàn)的個體 變項，則稱A為封閉的公式，簡稱閉式。 例如： xy(F(x)G(y)H(x , y) 為閉式， x(F(x)G(x , y) 不是閉式 。,一階公式的解釋

16、 一階公式?jīng)]有確定的意義，一旦將其中的變項（項的變項、謂詞變項）用指定的常項代替后，所得公式就具備一定的意義，有時就變成命題了。,例題4.7,例4.7： 將下列兩個公式中的變項指定成常項使其成為命題: (1)x(F(x)G(x)(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y) (1)指定個體變項的變化范圍，并且指定謂詞F，G的含義， 下面給出兩種指定法: (a)令個體域D1為全總個體域，F(xiàn)(x)為x是人，G(x)為x是黃種人， 則命題為“所有人都是黃種人”，這是假命題。 (b)令個體域D2為實數(shù)集合R，F(xiàn)(x)為x是自然數(shù)，G(x)為x是整數(shù)， 則命題為“自然數(shù)都是整數(shù)”

17、，這是真命題。,例題4.7,(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y) 含有兩個2元函數(shù)變項，兩個1元謂詞變項，兩個2元謂詞變項。 指定個體域為全總個體域，F(xiàn)(x)為x是實數(shù)，G(x,y)為xy，H(x,y)為xy，f(x,y)=x2+y2，g(x,y)=2xy， 則表達的命題為“對于任意的x，y，若x與y都是實數(shù)，且xy，則x2+y22xy”，這是真命題。 如果H(x,y)改為xy， 則所得命題為假命題。,例4.8 給定解釋I如下: (a) 個體域D=N(N為自然數(shù)集合，即 N=0,1,2,),(b) =0,(c) (x,y)=x+y, (x,y)=xy。,(d)

18、 (x,y)為x=y。,在I下，下列哪些公式為真?哪些為假?哪些的真值還不能確定?,例題4.8,例題4.8,(1) F(f(x,y),g(x,y) (2) F(f(x,a),y)F(g(x,y),z) (3) F(g(x,y),g(y,z) (4) x F(g(x,y),z) (5) x F(g(x,a),x)F(x,y) (6) x F(g(x,a),x) (7) xy(F(f(x,a),y)F(f(y,a),x) (8) xyz F(f(x,y),z) (9) x F(f(x,x),g(x,x),例題4.8,(1) F(f(x,y),g(x,y) 公式被解釋成“x+y=xy”，這不是命題。

19、 (2) F(f(x,a),y)F(g(x,y),z) 公式被解釋成“(x+0=y)(xy=z)”，這也不是命題。 (3) F(g(x,y),g(y,z) 公式被解釋成“xyyz”，同樣不是命題。 (4) x F(g(x,y),z) 公式被解釋成“x(xy=z)”，不是命題。,例題4.8,(5) x F(g(x,a),x)F(x,y) 公式被解釋成“x(x0=x)(x=y)”，由于前件為假，所以被 解釋的公式為真。 (6) x F(g(x,a),x) 公式被解釋成“x(x0=x)”，為假命題。 (7) xy(F(f(x,a),y)F(f(y,a),x) 公式被解釋成“xy(x+0=y)(y+0

20、=x)”，為真命題。,(8) xyz F(f(x,y),z) 公式被解釋成“xyz(x+y=z)”，這也為真命題。 (9) x F(f(x,x),g(x,x) 公式被解釋成“x(x+x=xx)”，為真命題。,例題4.8,定理4.1 封閉的公式在任何解釋下都變成命題。,一階公式的分類,定義4.8： 、 永真式：設(shè)A為一個公式，若A在任何解釋下均為真，則稱A為 永真式(或稱邏輯有效式)。 永假式：設(shè)A為一個公式，若A在任何解釋下均為假，則稱A為 矛盾式(或永假式)。 可滿足式：設(shè)A為一個公式，若至少存在一個解釋使A為真， 則稱A為可滿足式。,永真式一定是可滿足式，但可滿足式不一定是永真式。 在一階

21、邏輯中，到目前為止，還沒有找到一種可行的算法，用來判斷任意一個公式是否是可滿足的，這與命題邏輯的情況是完全不同的。 但對某些特殊的公式還是可以判斷的。,說明,代換實例,定義4.9： 設(shè)A0是含有命題變項p1,p2,pn的命題公式， A1,A2,An是n個謂詞公式，用Ai(1in)處處 代替A0中的pi，所得公式A稱為A0的代換實例。,例如，F(xiàn)(x)G(x), xF(x)yG(y)等都是pq的代換實例，而x(F(x)G(x)等不是pq的代換實例。,定理4.2：重言式的代換實例都是永真式，矛盾式的代換 實例都是矛盾式。,例4.9 判斷下列公式中，哪些是永真式，哪些是矛盾式？ （1）x(F(x)G(

22、x) （2）x(F(x)G(x) （3）xF(x)(xyG(x,y)xF(x) （4）(xF(x)yG(y)yG(y) 解: (1) x(F(x)G(x) 解釋1：個體域為實數(shù)集合R，F(xiàn)(x)：x是整數(shù)，G(x)：x是有理數(shù)，因此公式真值為真。 解釋2：個體域為實數(shù)集合R，F(xiàn)(x)：x是無理數(shù)，G(x)：x能表示成分數(shù)，因此公式真值為假。 所以公式為非永真式的可滿足式。,例題4.9,例題4.9,（2）x(F(x)G(x) 公式為非永真式的可滿足式。 （3）xF(x)(xyG(x,y)xF(x) 為p(qp)（重言式）的代換實例，故為永真式。 （4）(xF(x)yG(y)yG(y) 為(pq)q

23、（矛盾式）的代換實例，故為永假式。,例題,例4.10 判斷下列公式的類型。(1) xF(x) xF(x)(2) xyF(x,y) xyF(x,y)(3) x(F(x)G(x) yG(y) 解 記(1)，(2)，(3)中的公式分別為A,B,C。 (1)設(shè)I為任意一個解釋，個體域為D。 若存在x0D，使得F(x0)為假，則xF(x)為假，所以A的前件為假，故A為真。 若對于任意xD，F(xiàn)(x)均為真，則xF(x)，xF(x)都為真，從而A為真。 所以在I下A為真。由I的任意性可知，A是永真式。,例題,(2) xyF(x,y) xyF(x,y) 取解釋I：個體域為自然數(shù)集合N，F(xiàn)(x,y)為xy。 在I下B的前件與后件均為真，所以B為真。這說明B不是矛盾式。（ 在xyF(x,y)中，x0 ） 再取I：個體域仍然為N，F(xiàn)(x,y)為x=y。 在I下，B的前件真而后件假，所以B為假。這說明B不是永真式。 故B是非永真式的可滿足式。 (3) x(F(x)G(x) yG(y) C也是非永真式的可滿足式。,小節(jié)結(jié)束,本章主要內(nèi)容,個體詞個體常項個體變項個體域全總個體域 謂詞謂詞常項謂詞變項n(n1)元謂詞特性謂詞 量詞全稱量詞存在量詞,本章主要內(nèi)容,一階邏輯中命題符號化 一階邏輯公式原子公