1、第4章 一階邏輯基本概念離 散 數(shù) 學(xué)本章說(shuō)明本章的主要內(nèi)容一階邏輯基本概念、命題符號(hào)化一階邏輯公式、解釋及分類本章與后續(xù)各章的關(guān)系克服命題邏輯的局限性是第五章的先行準(zhǔn)備 引言 例如(著名的蘇格拉底三段論) （1）所有的人都是要死的； （2）蘇格拉底是人。 （3）蘇格拉底是要死的。 命題邏輯能夠解決的問(wèn)題是有局限性的。只能進(jìn)行命題間關(guān)系的推理，無(wú)法解決與命題的結(jié)構(gòu)和成分有關(guān)的推理問(wèn)題。蘇格拉底三段論 P：所有的人都是要死的； Q：蘇格拉底是人。 R：蘇格拉底是要死的。 可見，P，Q，R為不同的命題，無(wú)法體現(xiàn)三者相互之間的聯(lián)系。問(wèn)題在于這類推理中，各命題之間的邏輯關(guān)系不是體現(xiàn)在原子命題之間，而是

2、體現(xiàn)在構(gòu)成原子命題的內(nèi)部成分之間。對(duì)此，命題邏輯將無(wú)能為力。本章內(nèi)容 一階邏輯命題符號(hào)化1一階邏輯公式及其解釋2 本章學(xué)習(xí)要求 重點(diǎn)掌握了解11 謂詞邏輯符號(hào)化及真值2 謂詞公式的有效性和基本等價(jià)公式3謂詞公式及其解釋 21 謂詞公式的解釋和真值2 自由變?cè)图s束變?cè)话阏莆找浑A邏輯命題符號(hào)化一階邏輯命題符號(hào)化的三個(gè)基本要素個(gè)體詞謂詞量詞個(gè)體詞及相關(guān)概念個(gè)體詞一般是充當(dāng)主語(yǔ)的名詞或代詞。說(shuō)明個(gè)體詞：指所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體。舉例命題：電子計(jì)算機(jī)是科學(xué)技術(shù)的工具。個(gè)體詞：電子計(jì)算機(jī)。命題：他是三好學(xué)生。個(gè)體詞：他。個(gè)體常項(xiàng)：表示具體或特定的客體的個(gè)體詞，用小寫字母a, b,c

3、，表示。個(gè)體變項(xiàng)：表示抽象或泛指的客體的個(gè)體詞，用x,y,z,表示。個(gè)體域（或稱論域）：指?jìng)€(gè)體變項(xiàng)的取值范圍?？梢允怯懈F集合，如a, b, c, 1, 2?？梢允菬o(wú)窮集合，如N,Z,R,。全總個(gè)體域（universe）宇宙間一切事物組成 。個(gè)體詞及相關(guān)概念本教材在論述或推理中，如果沒(méi)有指明所采用的個(gè)體域，都是使用的全總個(gè)體域。說(shuō)明謂詞及相關(guān)概念謂詞（predicate）是用來(lái)刻畫個(gè)體詞性質(zhì)及個(gè)體詞之間相互關(guān)系的詞。(1) 是無(wú)理數(shù)。是個(gè)體常項(xiàng)，“是無(wú)理數(shù)”是謂詞，記為F，命題符號(hào)化為F() 。(2) x是有理數(shù)。x是個(gè)體變項(xiàng)，“是有理數(shù)”是謂詞，記為G，命題符號(hào)化為G(x)。(3) 小王與小李

4、同歲。小王、小李都是個(gè)體常項(xiàng)，“與同歲”是謂詞，記為H，命題符號(hào)化為H(a,b) ，其中a：小王，b：小李。(4) x與y具有關(guān)系L。x，y都是個(gè)體變項(xiàng)，謂詞為L(zhǎng)，命題符號(hào)化為L(zhǎng)(x,y)。謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂詞。用大寫字母表示。如(1)、 (2) 、(3) 中謂詞F、G、H。謂詞變項(xiàng)：表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞。用大寫字母表示。如(4) 中謂詞L。n(n1)元謂詞：P(x1,x2,xn)表示含n個(gè)命題變項(xiàng)的n元謂詞。n=1時(shí)，一元謂詞表示x1具有性質(zhì)P。n2時(shí)，多元謂詞表示x1,x2,xn具有關(guān)系P。0元謂詞：不含個(gè)體變項(xiàng)的謂詞。如F(a)、G(a,b)、 P(a1,a2

5、,an)。 n元謂詞是命題嗎？不是，只有用謂詞常項(xiàng)取代P，用個(gè)體常項(xiàng)取代x1,x2,xn時(shí)，才能使n元謂詞變?yōu)槊}。思考謂詞及相關(guān)概念更一般地 P(x)：x是電子科技大學(xué)的學(xué)生。x：個(gè)體詞P：謂詞P(x):命題函數(shù)P(x)結(jié)論 謂詞中個(gè)體詞的順序是十分重要的，不能隨意變更。如命題F(b, c)為“真”，但命題F(c, b)為“假”；一元謂詞用以描述某一個(gè)個(gè)體的某種特性，而n元謂詞則用以描述n個(gè)個(gè)體之間的關(guān)系。0元謂詞(不含個(gè)體詞的)實(shí)際上就是一般的命題；結(jié)論（續(xù)）具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者不是命題，它的真值是不確定的。如上例中S(a)是有真

6、值的，但S(x)卻沒(méi)有真值；一個(gè)n元謂詞不是一個(gè)命題，但將n元謂詞中的個(gè)體變?cè)加脗€(gè)體域中具體的個(gè)體取代后，就成為一個(gè)命題。而且，個(gè)體變?cè)诓煌膫€(gè)體域中取不同的值對(duì)是否成為命題及命題的真值有很大的影響。 例題 將下列命題在一階邏輯中用0元謂詞符號(hào)化，并討論真值。(1)只有2是素?cái)?shù)，4才是素?cái)?shù)。 (2)如果5大于4，則4大于6. 解：(1)設(shè)一元謂詞F(x):x是素?cái)?shù)，a:2，b:4。 命題符號(hào)化為0元謂詞的蘊(yùn)涵式 F(b)F(a) 由于此蘊(yùn)涵前件為假，所以命題為真。 (2)設(shè)二元謂詞G(x,y):x大于y，a:4，b:5，c:6。 命題符號(hào)化為0元謂詞的蘊(yùn)涵式 G(b,a)G(a,c) 由于

7、G(b,a)為真，而G(a,c)為假，所以命題為假。 例題將命題“這只大紅書柜擺滿了那些古書?！狈?hào)化.(1)設(shè)F(x,y)：x擺滿了y，R(x)：x是大紅書柜Q(y)：y是古書，a：這只，b：那些 符號(hào)化為：R(a)Q(b)F(a,b) (2)設(shè)A(x)：x是書柜，B(x)：x是大的 C(x)：x是紅的，D(y)：y是古老的E(y)： y是圖書，F(xiàn)(x,y)：x擺滿了ya：這只b：那些 符號(hào)化為：A(a)B(a)C(a)D(b)E(b)F(a,b) 量詞（quantifiers）是表示個(gè)體常項(xiàng)或個(gè)體變項(xiàng)之間數(shù)量關(guān)系的詞。1. 全稱量詞：符號(hào)化為“”日常生活和數(shù)學(xué)中所用的“一切的”、“所有的”

8、、“每一個(gè)”、“任意的”、“凡”、“都”等詞可統(tǒng)稱為全稱量詞。x表示個(gè)體域里的所有個(gè)體，xF(x)表示個(gè)體域里所有個(gè)體都有性質(zhì)F。2.存在量詞：符號(hào)化為“”日常生活和數(shù)學(xué)中所用的“存在”、“有一個(gè)”、“有的”、“至少有一個(gè)”等詞統(tǒng)稱為存在量詞。y表示個(gè)體域里有的個(gè)體，yG(y)表示個(gè)體域里存在個(gè)體具有性質(zhì)G等。 量詞及相關(guān)概念不便之處從書寫上十分不便，總要特別注明個(gè)體域；在同一個(gè)比較復(fù)雜的句子中，對(duì)于不同命題函數(shù)中的個(gè)體可能屬于不同的個(gè)體域，此時(shí)無(wú)法清晰表達(dá)； 如例 (所有的老虎都要吃人；)和(有一些人登上過(guò)月球；)的合取 x人x老虎(x)P(x)(x)R(x)不便之處(續(xù))若個(gè)體域的注明不清

9、楚，將造成無(wú)法確定其真值。即對(duì)于同一個(gè)n元謂詞，不同的個(gè)體域有可能帶來(lái)不同的真值。 例如 對(duì)于語(yǔ)句“(x)(x+6 = 5)”可表示為：“有一些x，使得x+6 = 5”。該語(yǔ)句在下面兩種個(gè)體域下有不同的真值： （a）在實(shí)數(shù)范圍內(nèi)時(shí)，確有x=-1使得x+6 = 5，因此，(x)(x+6 = 5)為“真”； （b）在正整數(shù)范圍內(nèi)時(shí)，則找不到任何x，使得x+6=5為“真”，所以，(x)(x+6=5)為“假”。 不便之處的根源對(duì)了，都是因?yàn)樾枰貏e標(biāo)注每個(gè)謂詞的個(gè)體域所致！全總個(gè)體域特性謂詞新的問(wèn)題出現(xiàn)了，U(x)如何與(x)P(x)結(jié)合才符合邏輯呢？U(x)：x是老虎x老虎謂詞邏輯符號(hào)化的兩條規(guī)則

10、統(tǒng)一個(gè)體域?yàn)槿倐€(gè)體域，而對(duì)每一個(gè)句子中個(gè)體變量的變化范圍用一元特性謂詞刻劃之。這種特性謂詞在加入到命題函數(shù)中時(shí)必定遵循如下原則：（1）對(duì)于全稱量詞(x)，刻劃其對(duì)應(yīng)個(gè)體域的特性謂詞作為蘊(yùn)涵式之前件加入。（2）對(duì)于存在量詞(x)，刻劃其對(duì)應(yīng)個(gè)體域的特性謂詞作為合取式之合取項(xiàng)加入。 在個(gè)體域分別限制為(a)和(b)條件時(shí)，將下面兩個(gè)命題符號(hào)化: (1) 凡人都呼吸。 (2) 有的人用左手寫字。 其中:(a)個(gè)體域D1為人類集合； (b)個(gè)體域D2為全總個(gè)體域。 一階邏輯命題符號(hào)化解: (a)個(gè)體域?yàn)槿祟惣稀?令F(x):x呼吸。G(x):x用左手寫字。(1) 在個(gè)體域中除了人外，再無(wú)別的東西，

11、因而“凡人都呼吸”應(yīng)符號(hào)化為 xF(x) (2) 在個(gè)體域中除了人外，再無(wú)別的東西，因而“有的人用左手寫字”符號(hào)化為 xG(x) (b)個(gè)體域?yàn)槿倐€(gè)體域。 即除人外，還有萬(wàn)物，所以必須考慮將人先分離出來(lái)。 令F(x):x呼吸。 G(x):x用左手寫字。 M(x):x是人。 (1) “凡人都呼吸”應(yīng)符號(hào)化為 x(M(x)F(x) (2) “有的人用左手寫字”符號(hào)化為 x(M(x)G(x) 在使用全總個(gè)體域時(shí)，要將人從其他事物中區(qū)別出來(lái)，為此引進(jìn)了謂詞M(x)，稱為特性謂詞。同一命題在不同的個(gè)體域中符號(hào)化的形式可能不同。思考：在全總個(gè)體域中，能否將(1)符號(hào)化為x(M(x)F(x)？ 能否將(2

12、)符號(hào)化為x(M(x)G(x)？ 結(jié)論例題 在個(gè)體域限制為(a)和(b)條件時(shí)，將下列命題符號(hào)化:(1) 對(duì)于任意的x，均有x2-3x+2=(x-1)(x-2)。(2) 存在x，使得x+5=3。其中: (a)個(gè)體域D1=N(N為自然數(shù)集合)(b)個(gè)體域D2=R(R為實(shí)數(shù)集合)(a)令F(x): x2-3x+2=(x-1)(x-2)，G(x): x+5=3。命題(1)的符號(hào)化形式為xF(x)（真命題）命題(2)的符號(hào)化形式為xG(x)（假命題）(b)在D2內(nèi)，(1)和(2)的符號(hào)化形式同(a)，皆為真命題。在不同個(gè)體域內(nèi)，同一個(gè)命題的符號(hào)化形式可能不同，也可能相同。同一個(gè)命題，在不同個(gè)體域中的真

13、值也可能不同。說(shuō)明 將下列命題符號(hào)化，并討論真值。（1）所有的人長(zhǎng)著黑頭發(fā)。（2）有的人登上過(guò)月球。（3）沒(méi)有人登上過(guò)木星。（4）在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。分析：謂詞邏輯中命題的符號(hào)化，主要考慮：(1)非空個(gè)體域的選取。若是為了確定命題的真值，一般約定在某個(gè)個(gè)體域上進(jìn)行，否則，在由一切事物構(gòu)成的全總個(gè)體域上考慮問(wèn)題時(shí)，需要增加一個(gè)指出個(gè)體變量變化范圍的特性謂詞。 (2)量詞的使用及作用范圍。 (3)正確地語(yǔ)義。例題例題解：沒(méi)有提出個(gè)體域，所以認(rèn)為是全總個(gè)體域。（1）所有的人長(zhǎng)著黑頭發(fā)。 令F(x):x長(zhǎng)著黑頭發(fā)， M(x):x是人。命題符號(hào)化為 x(M(x)F(x)。 命題真值為假。（2

14、）有的人登上過(guò)月球。 令G(x):x登上過(guò)月球， M(x):x是人。命題符號(hào)化為 x(M(x)G(x)。 命題真值為真。例題（3）沒(méi)有人登上過(guò)木星。 令H(x):x登上過(guò)木星， M(x):x是人。命題符號(hào)化為 x(M(x)H(x)。 命題真值為真。（4）在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。令F(x):x是在美國(guó)留學(xué)的學(xué)生，G(x):x是亞洲人。符號(hào)化x(F(x)G(x) 命題真值為真。 謂詞翻譯難點(diǎn) 一元謂詞用以描述某一個(gè)個(gè)體的某種特性，而n元謂詞則用以描述的n個(gè)個(gè)體之間關(guān)系；如有多個(gè)量詞，則讀的順序按從左到右的順序；另外，量詞對(duì)變?cè)募s束，往往與量詞的次序有關(guān)，不同的量詞次序，可以產(chǎn)生不同的真值

15、，此時(shí)對(duì)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能隨意顛倒它們的順序，顛倒后會(huì)改變?cè)械暮x。謂詞翻譯難點(diǎn)（續(xù)）根據(jù)命題的實(shí)際意義，選用全稱量詞或存在量詞。全稱量詞加入時(shí)，其刻劃個(gè)體域的特性謂詞將以蘊(yùn)涵的前件加入，存在量詞加入時(shí)，其刻劃個(gè)體域的特性謂詞將以合取項(xiàng)加入；有些命題在進(jìn)行符號(hào)化時(shí)，由于語(yǔ)言敘述不同，可能翻譯不同，但它們表示的意思是相同的，即句子符號(hào)化形式可不止一種。例題 n元謂詞的符號(hào)化 將下列命題符號(hào)化（1）兔子比烏龜跑得快。（2）有的兔子比所有的烏龜跑得快。（3）并不是所有的兔子都比烏龜跑得快。（4）不存在跑得同樣快的兩只兔子。解：令 F(x):x是兔子， G(y):y是烏龜， H(x,y):x比

16、y跑得快， L(x,y):x與y跑得同樣快。（1）xy(F(x)G(y)H(x,y)（2） x(F(x)y(G(y)H(x,y)（3） xy(F(x)G(y)H(x,y)（4） xy(F(x)F(y)L(x,y)一階邏輯命題符號(hào)化時(shí)需要注意的事項(xiàng)分析命題中表示性質(zhì)和關(guān)系的謂詞，分別符號(hào)為一元和n（ n2）元謂詞。根據(jù)命題的實(shí)際意義選用全稱量詞或存在量詞。一般說(shuō)來(lái)，多個(gè)量詞出現(xiàn)時(shí)，它們的順序不能隨意調(diào)換。例如，考慮個(gè)體域?yàn)閷?shí)數(shù)集，H(x，y)表示x+y=10，則命題“對(duì)于任意的x，都存在y，使得x+y=10”的符號(hào)化形式為xyH(x,y)，為真命題。如果改變兩個(gè)量詞的順序，得yxH(x,y)，為

17、假命題。有些命題的符號(hào)化形式可不止一種。（例4.5之(3)）xy(F(x)G(y)H(x,y)xy(F(x)G(y)H(x,y)同在命題邏輯中一樣，為在一階邏輯中進(jìn)行演算和推理，必須給出一階邏輯中公式的抽象定義，以及它們的分類及解釋。一階語(yǔ)言是用于一階邏輯的形式語(yǔ)言，而一階邏輯就是建立在一階語(yǔ)言基礎(chǔ)上的邏輯體系，一階語(yǔ)言本身不具備任何意義，但可以根據(jù)需要被解釋成具有某種含義。一階語(yǔ)言的形式是多種多樣的，本書給出的一階語(yǔ)言是便于將自然語(yǔ)言中的命題符號(hào)化的一階語(yǔ)言，記為F。一階語(yǔ)言中的字母表 一階語(yǔ)言F的字母表定義如下:(1)個(gè)體常項(xiàng)：a , b , c , , ai , bi , ci , ,

18、i 1(2)個(gè)體變項(xiàng)：x , y , z, , xi , yi , zi , , i 1 (3)函數(shù)符號(hào)：f , g , h , , fi , gi , hi , , i 1(4)謂詞符號(hào)：F , G , H , , Fi , Gi , Hi , , i 1(5)量詞符號(hào): ，(6)聯(lián)結(jié)詞符號(hào):, (7)括號(hào)與逗號(hào):(,),，一階語(yǔ)言L (續(xù))定義 L 的項(xiàng)的定義如下：(1) 個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng).(2) 若(x1, x2, , xn)是任意的n元函數(shù)，t1,t2,tn是任意 的n個(gè)項(xiàng)，則(t1, t2, , tn) 是項(xiàng).(3) 所有的項(xiàng)都是有限次使用 (1), (2) 得到的.定義 設(shè)R

19、(x1, x2, , xn)是L 的任意n元謂詞，t1,t2, tn是L 的任意n個(gè)項(xiàng)，則稱R(t1, t2, , tn)是原子公式一階語(yǔ)言L (續(xù))定義 L 的合式公式定義如下：(1) 原子公式是合式公式 (2) 若A是合式公式, 則 (A)也是合式公式(3) 若A, B是合式公式, 則(AB), (AB), (AB), (AB)也 是合式公式(4) 若A是合式公式, 則xA, xA也是合式公式(5) 只有有限次地應(yīng)用(1)(4)形成的符號(hào)串才是合式公式.合式公式又稱謂詞公式, 簡(jiǎn)稱公式量詞的轄域定義 在公式xA和xA中, 稱x為指導(dǎo)變?cè)? A為相應(yīng)量詞的轄域. 在x和x的轄域中, x的所有

20、出現(xiàn)稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項(xiàng)稱為自由出現(xiàn)例6 公式 x(F(x,y)yG(x,y,z) x的轄域:(F(x,y)yG(x,y,z)， 指導(dǎo)變?cè)獮閤 y的轄域:G(x,y,z)， 指導(dǎo)變?cè)獮閥 x的兩次出現(xiàn)均為約束出現(xiàn) y的第一次出現(xiàn)為自由出現(xiàn), 第二次出現(xiàn)為約束出現(xiàn)z為自由出現(xiàn). 謂詞合式公式難點(diǎn)3命題邏輯與謂詞邏輯中的公式及其解釋的不同1掌握并能夠靈活運(yùn)用謂詞，個(gè)體詞和量詞；2注意量詞的作用域。通過(guò)緊跟量詞后面的是否為括號(hào)進(jìn)行判定； 指出下列各公式中的指導(dǎo)變?cè)髁吭~的轄域，自由出現(xiàn)以及約束出現(xiàn)的個(gè)體變項(xiàng)。(1) x(F(x,y)G(x,z)(2) x(F(x)G(y)y(H

21、(x)L(x,y,z) 例題解答(1) x是指導(dǎo)變?cè)Ａ吭~的轄域A=(F(x,y)G(x,z)。在A中，x的兩次出現(xiàn)均是約束出現(xiàn)。y和z均為自由出現(xiàn)。(2) 前件上量詞的指導(dǎo)變?cè)獮閤，量詞的轄域A=(F(x)G(y)，x在A中是約束出現(xiàn)的，y在A中是自由出現(xiàn)的。后件中量詞的指導(dǎo)變?cè)獮閥， 量詞的轄域?yàn)锽=(H(x)L(x,y,z)，y在B中是約束出現(xiàn)的，x、z在B中均為自由出現(xiàn)的。例確定以下公式各量詞的轄域以及各個(gè)體變量為自由變?cè)€是約束變?cè)?。?）(x)(P(x)(y)R(x, y)；（2）(x)P(x)Q(x, y)；（3）(x)(y)(P(x, y)Q(y, z) (x)R(x,y)；（

22、4）(x)(P(x)R(x)(y)Q(x, y)。變?cè)煜?）(x)(P(x)R(x)(y)Q(x, y)約束變?cè)杂勺冊(cè)?在一個(gè)公式中，某一個(gè)變?cè)某霈F(xiàn)即可以是自由的，又可以是約束的，如(4)中的x。為了使得我們的研究更方便，而不致引起混淆，同時(shí)為了使其式子給大家以一目了然的結(jié)果，對(duì)于表示不同意思的個(gè)體變?cè)?，我們總是以不同的變量符?hào)來(lái)表示之。 本書中的記法用A(x1,x2,xn)表示含x1,x2,xn自由出現(xiàn)的公式。用表示任意的量詞或，則x1A(x1,x2,xn)是含有x2,x3,xn自由出現(xiàn)的公式，可記為A1(x2,x3,xn)。類似的，x2x1A(x1,x2,xn)可記為A2(x3,x

23、4,xn)xn-1xn-2x1A(x1,x2,xn)中只含有xn是自由出現(xiàn)的個(gè)體變項(xiàng)，可以記為An-1(xn)。xnx1A(x1,x2,xn)沒(méi)有自由出現(xiàn)的個(gè)體變項(xiàng)。 閉式: 不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式.例題 將下列兩個(gè)公式中的變項(xiàng)指定成常項(xiàng)使其成為命題:(1)x(F(x)G(x)(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y)(1)指定個(gè)體變項(xiàng)的變化范圍，并且指定謂詞F，G的含義，下面給出兩種指定法: (a)令個(gè)體域D1為全總個(gè)體域，F(xiàn)(x)為x是人，G(x)為x是黃種人，則命題為“所有人都是黃種人”，這是假命題。 (b)令個(gè)體域D2為實(shí)數(shù)集合R，F(xiàn)(x)為x是自然數(shù)

24、，G(x)為x是整數(shù)，則命題為“自然數(shù)都是整數(shù)”，這是真命題。例題(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y)含有兩個(gè)2元函數(shù)變項(xiàng)，兩個(gè)1元謂詞變項(xiàng)，兩個(gè)2元謂詞變項(xiàng)。指定個(gè)體域?yàn)槿倐€(gè)體域，F(xiàn)(x)為x是實(shí)數(shù)，G(x,y)為xy，H(x,y)為xy，f(x,y)=x2+y2，g(x,y)=2xy，則表達(dá)的命題為“對(duì)于任意的x，y，若x與y都是實(shí)數(shù)，且xy，則x2+y22xy”，這是真命題。如果H(x,y)改為xy，則所得命題為假命題。解釋定義 設(shè)一階語(yǔ)言L 的個(gè)體常項(xiàng)集ai| i1, 函數(shù)符號(hào)集fi| i1, 謂詞符號(hào)集Fi| i1, L 的解釋I由下面4部分組成:

25、(1) 非空個(gè)體域DI(2) 對(duì)每一個(gè)個(gè)體常項(xiàng)ai, DI, 稱作ai在I中的解釋(3) 對(duì)每一個(gè)函數(shù)符號(hào)fi, 設(shè)其為m元的, 是DI上的m元函數(shù), 稱作fi在I中的解釋(4) 對(duì)每一個(gè)謂詞符號(hào)Fi, 設(shè)其為n元的, 是一個(gè)n元謂詞, 稱作Fi在I中的解釋 為第i個(gè)n元謂詞，如i=2，n=3時(shí)， 表示第2個(gè)3元謂詞，它可能以 (x,y,z)的形式出現(xiàn)在解釋中，公式A若出現(xiàn)F2(x,y,z)就解釋成 (x,y,z)。 為第i個(gè)n元函數(shù)。例如，i=1，n=2時(shí)， 表示第一個(gè)二元函數(shù)，它出現(xiàn)在解釋中，可能是 (x,y)=x2+y2， (x,y)=2xy等，一旦公式中出現(xiàn)f1(x,y)就解釋成 (x

26、,y)，出現(xiàn)g1(x,y)就解釋成 (x,y)=2xy。對(duì)解釋I的幾點(diǎn)說(shuō)明被解釋的公式不一定全部包含解釋中的四部分。在解釋的公式A中的個(gè)體變項(xiàng)均取值于DI。若A中含有個(gè)體常項(xiàng)，就解釋成 。在解釋的定義中引進(jìn)了幾個(gè)元語(yǔ)言符號(hào)，如 給定解釋I如下: (a) 個(gè)體域D=N(N為自然數(shù)集合，即 N=0,1,2,) (b) =0(c) (x,y)=x+y, (x,y)=xy。(d) (x,y)為x=y。在I下，下列哪些公式為真?哪些為假?哪些的真值還不能確定?例題(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

27、(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) 例題(1) F(f(x,y),g(x,y) 公式被解釋成“x+y=xy”，這不是命題。(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)”，不是命

28、題。例題(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=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)”，為真命題。閉式在給定的解釋中都變成了命題。如(6)(8)。不是閉式的公式在某些解釋下也可能

29、變?yōu)槊}。如(5)。結(jié)論例題 封閉的公式在任何解釋下都變成命題。 一階公式的分類定義4.8 永真式、永假式、可滿足式設(shè)A為一個(gè)公式，若A在任何解釋下均為真，則稱A為永真式(或稱邏輯有效式)。設(shè)A為一個(gè)公式，若A在任何解釋下均為假，則稱A為矛盾式(或永假式)。設(shè)A為一個(gè)公式，若至少存在一個(gè)解釋使A為真，則稱A為可滿足式。 永真式一定是可滿足式，但可滿足式不一定是永真式。在一階邏輯中，到目前為止，還沒(méi)有找到一種可行的算法，用來(lái)判斷任意一個(gè)公式是否是可滿足的，這與命題邏輯的情況是完全不同的。但對(duì)某些特殊的公式還是可以判斷的。說(shuō)明代換實(shí)例定義4.9 設(shè)A0是含有命題變項(xiàng)p1,p2,pn的命題公式，A1

30、,A2,An是n個(gè)謂詞公式，用Ai(1in)處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例。例如，F(xiàn)(x)G(x), xF(x)yG(y)等都是pq的代換實(shí)例，而x(F(x)G(x)等不是pq的代換實(shí)例。 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式。例4.9 判斷下列公式中，哪些是永真式，哪些是矛盾式？（1）x(F(x)G(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：個(gè)體域?yàn)閷?shí)數(shù)集合R，F(xiàn)(x)：x是整數(shù)，G(x)：x是有理數(shù)，因此公式真值為真。 解釋2：個(gè)體域?yàn)閷?shí)數(shù)

31、集合R，F(xiàn)(x)：x是無(wú)理數(shù)，G(x)：x能表示成分?jǐn)?shù)，因此公式真值為假。 所以公式為非永真式的可滿足式。例題例題（2）x(F(x)G(x) 公式為非永真式的可滿足式。（3）xF(x)(xyG(x,y)xF(x) 為p(qp)（重言式）的代換實(shí)例，故為永真式。（4）(xF(x)yG(y)yG(y) 為(pq)q（矛盾式）的代換實(shí)例，故為永假式。例題 判斷下列公式的類型。(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為任意一個(gè)解釋，個(gè)體域?yàn)镈。若存在x0D，使得F(

32、x0)為假，則xF(x)為假，所以A的前件為假，故A為真。若對(duì)于任意xD，F(xiàn)(x)均為真，則xF(x)，xF(x)都為真，從而A為真。所以在I下A為真。由I的任意性可知，A是永真式。 例題(2) xyF(x,y) xyF(x,y)取解釋I：個(gè)體域?yàn)樽匀粩?shù)集合N，F(xiàn)(x,y)為xy。在I下B的前件與后件均為真，所以B為真。這說(shuō)明B不是矛盾式。（ 在xyF(x,y)中，x0 ）再取I：個(gè)體域仍然為N，F(xiàn)(x,y)為x=y。在I下，B的前件真而后件假，所以B為假。這說(shuō)明B不是永真式。故B是非永真式的可滿足式。 (3) x(F(x)G(x) yG(y) C也是非永真式的可滿足式。 謂詞合式公式的應(yīng)用利

33、用謂詞之間的等價(jià)關(guān)系證明下列公式之間的關(guān)系：(x)P(x)Q(x)=(y)( P(y)Q(x) 證明 (x)P(x)Q(x) = (x)P(x)Q(x) = (x)P(x)Q(x) = (y)P(y)Q(x) = (y)(P(y)Q(x) = (y)(P(y)Q(x)例判斷(x)P(x)Q(x)(x)P(x)(x)Q(x)是否為一個(gè)有效公式。 解 設(shè)個(gè)體域D=2, 4, 6, 8， P(x)：x能被2整除；Q(x)：x能被4整除?？芍?x)P(x) 真值為真，(x)Q(x) 真值為假。1）自由變?cè)獂=4 原式真值=（1Q(4)（10）=0 故 (x)P(x)Q(4)(x)P(x)(x)Q(x)

34、的真值為假。所以原式不是有效公式。例（續(xù)） 2）自由變?cè)獂=6原式真值 =（1 Q(6)）（10）= 1 故(x)P(x)Q(6)(x)P(x)(x)Q(x)的真值為真。 綜上所述，個(gè)體域中有些個(gè)體使原式的真值為真，有些個(gè)體使原式的真值為假，因此，該公式只能是一個(gè)可滿足公式。小節(jié)結(jié)束本章主要內(nèi)容個(gè)體詞個(gè)體常項(xiàng)個(gè)體變項(xiàng)個(gè)體域全總個(gè)體域謂詞謂詞常項(xiàng)謂詞變項(xiàng)n(n1)元謂詞特性謂詞量詞全稱量詞存在量詞本章主要內(nèi)容一階邏輯中命題符號(hào)化一階邏輯公式原子公式合式公式（或公式）閉式解釋一階邏輯公式的分類邏輯有效式（或永真式）矛盾式（或永假式）可滿足式本章學(xué)習(xí)要求要求準(zhǔn)確地將給出的命題符號(hào)化：當(dāng)給定個(gè)體域時(shí)，

35、在給定個(gè)體域內(nèi)將命題符號(hào)化。當(dāng)沒(méi)給定個(gè)體域時(shí)，應(yīng)在全總個(gè)體域內(nèi)符號(hào)化。在符號(hào)化時(shí)，當(dāng)引入特性時(shí)，注意全稱量詞與蘊(yùn)含聯(lián)結(jié)詞的搭配，存在量詞與合取聯(lián)結(jié)詞的搭配。深刻理解邏輯有效式、矛盾式、可滿足式的概念。記住閉式的性質(zhì)：在任何解釋下均為命題。對(duì)給定的解釋，會(huì)判別公式的真值或不能確定真值。小節(jié)結(jié)束習(xí)題選講命題符號(hào)化1. 在一階邏輯中將下列命題符號(hào)化。（1） 每個(gè)人都有心臟。（2） 有的狗會(huì)飛。（3） 沒(méi)有不犯錯(cuò)誤的人。（4） 發(fā)光的不都是金子。（5） 一切人都不一樣高。（6） 并不是所有的汽車都比火車快。（7） 沒(méi)有一個(gè)自然數(shù)大于等于任何自然數(shù)。（8） 有唯一的偶素?cái)?shù)。（9） 不管黑貓白貓，抓住老鼠

36、就是好貓。（10）對(duì)平面上任意兩點(diǎn)，有且僅有一條直線通過(guò)這兩點(diǎn)。習(xí)題選講命題符號(hào)化解：由于沒(méi)指出個(gè)體域，故用全總個(gè)體域（1）每個(gè)人都有心臟。本命題的含義：對(duì)于每一個(gè)x，如果x是人，則x有心臟。因而應(yīng)首先從宇宙間的一切事物中，將人分離出來(lái)，這就必須引入特性謂詞。 令M(x):x是人，H(x):x有心臟。 命題符號(hào)化為： x(M(x)H(x)如果將其中的改為，即x(P(x)H(x)，它表示的意思是：“對(duì)于每個(gè)x，x是人且x有心臟”。這是一個(gè)假命題，而“每個(gè)人都有心臟”是真命題。這說(shuō)明將命題“每個(gè)人都有心臟”符號(hào)化為(x)(P(x)H(x)是錯(cuò)誤的。 習(xí)題選講命題符號(hào)化（2）有的狗會(huì)飛。 命題的意思

37、是：存在一個(gè)x，使得x是狗，并且x會(huì)飛。 設(shè)D(x)：x是狗，F(xiàn)(x)：x會(huì)飛。命題符號(hào)化為：x(D(x)F(x)如果將其中的改為，即x(D(x)F(x)，如果用a表示某只貓，則D(a)為假，因而，D(a)F(a)為真，所以x(D(x)F(x)為真，而“有的狗會(huì)飛”為假，這說(shuō)明將“有的狗會(huì)飛”符號(hào)化為(x)(D(x)F(x)是錯(cuò)誤的。 習(xí)題選講命題符號(hào)化（3）沒(méi)有不犯錯(cuò)誤的人。 命題的意思是： 存在不犯錯(cuò)誤的人是不可能的。 只要是人，必然犯錯(cuò)誤。 設(shè) M(x): x是人，F(xiàn)(x):x犯錯(cuò)誤命題符號(hào)化為 x(M(x)F(x) x(M(x)F(x)習(xí)題選講命題符號(hào)化（4）發(fā)光的不都是金子。 命題的意思是： 不是發(fā)光的東西都是金子。 存在著發(fā)光的東西不是金子。 設(shè) L(x)：x是發(fā)光的東西，G(x)：x是金子。 命題符號(hào)化為 x(L(x)G(x) x(L(x)G(x) （5）一切人都不一樣高。 設(shè) F(x):x是人, H(x,y), x與y相同, L(x,y): x與y一樣高，命題符號(hào)化為 x(F(x)y(F(y)H(x