第4章一階邏輯基本概念離散數(shù)學

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

2、體現(xiàn)在構成原子命題的內(nèi)部成分之間。對此，命題邏輯將無能為力。本章內(nèi)容 一階邏輯命題符號化1一階邏輯公式及其解釋2 本章學習要求 重點掌握了解11 謂詞邏輯符號化及真值2 謂詞公式的有效性和基本等價公式3謂詞公式及其解釋 21 謂詞公式的解釋和真值2 自由變元和約束變元一般掌握一階邏輯命題符號化一階邏輯命題符號化的三個基本要素個體詞謂詞量詞個體詞及相關概念個體詞一般是充當主語的名詞或代詞。說明個體詞：指所研究對象中可以獨立存在的具體或抽象的客體。舉例命題：電子計算機是科學技術的工具。個體詞：電子計算機。命題：他是三好學生。個體詞：他。個體常項：表示具體或特定的客體的個體詞，用小寫字母a, b,c

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

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

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

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

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

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

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

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

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

12、)符號化為x(M(x)G(x)？ 結論例題 在個體域限制為(a)和(b)條件時，將下列命題符號化:(1) 對于任意的x，均有x2-3x+2=(x-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)的符號化形式為xF(x)（真命題）命題(2)的符號化形式為xG(x)（假命題）(b)在D2內(nèi)，(1)和(2)的符號化形式同(a)，皆為真命題。在不同個體域內(nèi)，同一個命題的符號化形式可能不同，也可能相同。同一個命題，在不同個體域中的真

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

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

15、，此時對多個量詞同時出現(xiàn)時，不能隨意顛倒它們的順序，顛倒后會改變原有的含義。謂詞翻譯難點（續(xù)）根據(jù)命題的實際意義，選用全稱量詞或存在量詞。全稱量詞加入時，其刻劃個體域的特性謂詞將以蘊涵的前件加入，存在量詞加入時，其刻劃個體域的特性謂詞將以合取項加入；有些命題在進行符號化時，由于語言敘述不同，可能翻譯不同，但它們表示的意思是相同的，即句子符號化形式可不止一種。例題 n元謂詞的符號化 將下列命題符號化（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)一階邏輯命題符號化時需要注意的事項分析命題中表示性質和關系的謂詞，分別符號為一元和n（ n2）元謂詞。根據(jù)命題的實際意義選用全稱量詞或存在量詞。一般說來，多個量詞出現(xiàn)時，它們的順序不能隨意調(diào)換。例如，考慮個體域為實數(shù)集，H(x，y)表示x+y=10，則命題“對于任意的x，都存在y，使得x+y=10”的符號化形式為xyH(x,y)，為真命題。如果改變兩個量詞的順序，得yxH(x,y)，為

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

18、i 1(2)個體變項：x , y , z, , xi , 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)結詞符號:, (7)括號與逗號:(,),，一階語言L (續(xù))定義 L 的項的定義如下：(1) 個體常項和個體變項是項.(2) 若(x1, x2, , xn)是任意的n元函數(shù)，t1,t2,tn是任意 的n個項，則(t1, t2, , tn) 是項.(3) 所有的項都是有限次使用 (1), (2) 得到的.定義 設R

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

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

21、(x)L(x,y,z) 例題解答(1) x是指導變元。量詞的轄域A=(F(x,y)G(x,z)。在A中，x的兩次出現(xiàn)均是約束出現(xiàn)。y和z均為自由出現(xiàn)。(2) 前件上量詞的指導變元為x，量詞的轄域A=(F(x)G(y)，x在A中是約束出現(xiàn)的，y在A中是自由出現(xiàn)的。后件中量詞的指導變元為y， 量詞的轄域為B=(H(x)L(x,y,z)，y在B中是約束出現(xiàn)的，x、z在B中均為自由出現(xiàn)的。例確定以下公式各量詞的轄域以及各個體變量為自由變元還是約束變元。（1）(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)。變元混淆（4）(x)(P(x)R(x)(y)Q(x, y)約束變元自由變元 在一個公式中，某一個變元的出現(xiàn)即可以是自由的，又可以是約束的，如(4)中的x。為了使得我們的研究更方便，而不致引起混淆，同時為了使其式子給大家以一目了然的結果，對于表示不同意思的個體變元，我們總是以不同的變量符號來表示之。 本書中的記法用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)的個體變項，可以記為An-1(xn)。xnx1A(x1,x2,xn)沒有自由出現(xiàn)的個體變項。 閉式: 不含自由出現(xiàn)的個體變項的公式.例題 將下列兩個公式中的變項指定成常項使其成為命題:(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ù)

24、，G(x)為x是整數(shù)，則命題為“自然數(shù)都是整數(shù)”，這是真命題。例題(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，則所得命題為假命題。解釋定義 設一階語言L 的個體常項集ai| i1, 函數(shù)符號集fi| i1, 謂詞符號集Fi| i1, L 的解釋I由下面4部分組成:

25、(1) 非空個體域DI(2) 對每一個個體常項ai, DI, 稱作ai在I中的解釋(3) 對每一個函數(shù)符號fi, 設其為m元的, 是DI上的m元函數(shù), 稱作fi在I中的解釋(4) 對每一個謂詞符號Fi, 設其為n元的, 是一個n元謂詞, 稱作Fi在I中的解釋 為第i個n元謂詞，如i=2，n=3時， 表示第2個3元謂詞，它可能以 (x,y,z)的形式出現(xiàn)在解釋中，公式A若出現(xiàn)F2(x,y,z)就解釋成 (x,y,z)。 為第i個n元函數(shù)。例如，i=1，n=2時， 表示第一個二元函數(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。對解釋I的幾點說明被解釋的公式不一定全部包含解釋中的四部分。在解釋的公式A中的個體變項均取值于DI。若A中含有個體常項，就解釋成 。在解釋的定義中引進了幾個元語言符號，如 給定解釋I如下: (a) 個體域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)。結論例題 封閉的公式在任何解釋下都變成命題。 一階公式的分類定義4.8 永真式、永假式、可滿足式設A為一個公式，若A在任何解釋下均為真，則稱A為永真式(或稱邏輯有效式)。設A為一個公式，若A在任何解釋下均為假，則稱A為矛盾式(或永假式)。設A為一個公式，若至少存在一個解釋使A為真，則稱A為可滿足式。 永真式一定是可滿足式，但可滿足式不一定是永真式。在一階邏輯中，到目前為止，還沒有找到一種可行的算法，用來判斷任意一個公式是否是可滿足的，這與命題邏輯的情況是完全不同的。但對某些特殊的公式還是可以判斷的。說明代換實例定義4.9 設A0是含有命題變項p1,p2,pn的命題公式，A1

30、,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.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：個體域為實數(shù)集合R，F(xiàn)(x)：x是整數(shù)，G(x)：x是有理數(shù)，因此公式真值為真。 解釋2：個體域為實數(shù)

31、集合R，F(xiàn)(x)：x是無理數(shù)，G(x)：x能表示成分數(shù)，因此公式真值為假。 所以公式為非永真式的可滿足式。例題例題（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（矛盾式）的代換實例，故為永假式。例題 判斷下列公式的類型。(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)設I為任意一個解釋，個體域為D。若存在x0D，使得F(

32、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也是非永真式的可滿足式。 謂詞合式公式的應用利

33、用謂詞之間的等價關系證明下列公式之間的關系：(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)是否為一個有效公式。 解 設個體域D=2, 4, 6, 8， P(x)：x能被2整除；Q(x)：x能被4整除。可知(x)P(x) 真值為真，(x)Q(x) 真值為假。1）自由變元x=4 原式真值=（1Q(4)（10）=0 故 (x)P(x)Q(4)(x)P(x)(x)Q(x)

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

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

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

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