離散數(shù)學(xué)課件[稻谷書(shū)苑]

1、第4章 一階邏輯基本概念 離散數(shù)學(xué)離散數(shù)學(xué) 2 本章說(shuō)明本章說(shuō)明 q本章的主要內(nèi)容本章的主要內(nèi)容 一階邏輯基本概念、命題符號(hào)化一階邏輯基本概念、命題符號(hào)化 一階邏輯公式、解釋及分類(lèi)一階邏輯公式、解釋及分類(lèi) q本章與后續(xù)各章的關(guān)系本章與后續(xù)各章的關(guān)系 克服命題邏輯的局限性克服命題邏輯的局限性 是第五章的先行準(zhǔn)備是第五章的先行準(zhǔn)備 3 引言引言 q 命題邏輯的局限性命題邏輯的局限性 在命題邏輯中，研究的基本單位是簡(jiǎn)單命題，對(duì)簡(jiǎn)單命在命題邏輯中，研究的基本單位是簡(jiǎn)單命題，對(duì)簡(jiǎn)單命 題不再進(jìn)行分解，并且不考慮命題之間的內(nèi)在聯(lián)系和數(shù)題不再進(jìn)行分解，并且不考慮命題之間的內(nèi)在聯(lián)系和數(shù) 量關(guān)系。量關(guān)系。 q

2、例如：例如： 所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是 要死的。要死的。 q 這個(gè)簡(jiǎn)單而有名的蘇格拉底三段論，卻無(wú)法用命題邏輯這個(gè)簡(jiǎn)單而有名的蘇格拉底三段論，卻無(wú)法用命題邏輯 予以證明。予以證明。 q 一階邏輯所研究的內(nèi)容一階邏輯所研究的內(nèi)容 為了克服命題邏輯的局限性，將簡(jiǎn)單命題再細(xì)分，分析為了克服命題邏輯的局限性，將簡(jiǎn)單命題再細(xì)分，分析 出個(gè)體詞、謂詞和量詞，以期達(dá)到出個(gè)體詞、謂詞和量詞，以期達(dá)到表達(dá)出個(gè)體與總體的表達(dá)出個(gè)體與總體的 內(nèi)在聯(lián)系和數(shù)量關(guān)系內(nèi)在聯(lián)系和數(shù)量關(guān)系。 4 本章內(nèi)容本章內(nèi)容 4.1 4.1 一階邏輯命題符號(hào)化一階邏輯

3、命題符號(hào)化 4.2 4.2 一階邏輯公式及解釋一階邏輯公式及解釋 本章小結(jié)本章小結(jié) 習(xí)題習(xí)題 作業(yè)作業(yè) 5 4.1一階邏輯命題符號(hào)化一階邏輯命題符號(hào)化 q一階邏輯命題符號(hào)化的三個(gè)基本要素一階邏輯命題符號(hào)化的三個(gè)基本要素 個(gè)體詞個(gè)體詞 謂詞謂詞 量詞量詞 q 6 個(gè)體詞及相關(guān)概念 q個(gè)體詞一般是充當(dāng)主語(yǔ)的名詞或代詞。個(gè)體詞一般是充當(dāng)主語(yǔ)的名詞或代詞。 說(shuō)說(shuō) 明明 q個(gè)體詞個(gè)體詞：指所研究對(duì)象中可以獨(dú)立存在的具體或抽：指所研究對(duì)象中可以獨(dú)立存在的具體或抽 象的客體。象的客體。 q舉例舉例 命題：電子計(jì)算機(jī)是科學(xué)技術(shù)的工具。命題：電子計(jì)算機(jī)是科學(xué)技術(shù)的工具。 個(gè)體詞：電子計(jì)算機(jī)。個(gè)體詞：電子計(jì)算機(jī)。

4、 命題：他是三好學(xué)生命題：他是三好學(xué)生。 個(gè)體詞：他。個(gè)體詞：他。 7 q 個(gè)體常項(xiàng)個(gè)體常項(xiàng)：表示具體或特定的客體的個(gè)體詞，用小寫(xiě)字母：表示具體或特定的客體的個(gè)體詞，用小寫(xiě)字母a a, , b b, ,c c，表示。表示。 q 個(gè)體變項(xiàng)個(gè)體變項(xiàng)：表示抽象或泛指的客體的個(gè)體詞，用：表示抽象或泛指的客體的個(gè)體詞，用x x, ,y y, ,z z, ,表表 示。示。 q 個(gè)體域（或稱(chēng)論域）個(gè)體域（或稱(chēng)論域）：指?jìng)€(gè)體變項(xiàng)的取值范圍。：指?jìng)€(gè)體變項(xiàng)的取值范圍。 可以是有窮集合，如可以是有窮集合，如 a a, , b b, , c c, 1, 2, 1, 2。 可以是無(wú)窮集合，如可以是無(wú)窮集合，如N N,

5、,Z Z, ,R R, ,。 q 全總個(gè)體域（全總個(gè)體域（universeuniverse）宇宙間一切事物組成宇宙間一切事物組成 。 個(gè)體詞及相關(guān)概念個(gè)體詞及相關(guān)概念 q本教材在論述或推理中，如果沒(méi)有指明所采本教材在論述或推理中，如果沒(méi)有指明所采 用的個(gè)體域，都是使用的全總個(gè)體域。用的個(gè)體域，都是使用的全總個(gè)體域。 說(shuō)說(shuō) 明明 8 謂詞及相關(guān)概念謂詞及相關(guān)概念 q 謂詞（謂詞（predicatepredicate）是用來(lái)刻畫(huà)個(gè)體詞性質(zhì)及個(gè)體詞之間相是用來(lái)刻畫(huà)個(gè)體詞性質(zhì)及個(gè)體詞之間相 互關(guān)系的詞?；リP(guān)系的詞。 (1)(1) 是無(wú)理數(shù)。是無(wú)理數(shù)。 是個(gè)體常項(xiàng)，是個(gè)體常項(xiàng)，“是無(wú)理數(shù)是無(wú)理數(shù)”是謂詞

6、，記為是謂詞，記為F F，命題符號(hào)命題符號(hào) 化為化為F(F( ) ) 。 (2) (2) x x是有理數(shù)。是有理數(shù)。 x x是個(gè)體變項(xiàng)，是個(gè)體變項(xiàng)，“是有理數(shù)是有理數(shù)”是謂詞，記為是謂詞，記為G G，命題符號(hào)命題符號(hào) 化為化為G(G(x x) )。 (3) (3) 小王與小李同歲。小王與小李同歲。 小王、小李都是個(gè)體常項(xiàng)，小王、小李都是個(gè)體常項(xiàng)，“與與同歲同歲”是謂詞，記為是謂詞，記為H H ，命題符號(hào)化為命題符號(hào)化為H(H(a,ba,b) ) ，其中，其中a a：小王，小王，b b：小李：小李。 (4) (4) x x與與y y具有關(guān)系具有關(guān)系L L。 x x，y y都是個(gè)體變項(xiàng)，謂詞為都是

7、個(gè)體變項(xiàng)，謂詞為L(zhǎng) L，命題符號(hào)化為命題符號(hào)化為L(zhǎng)(x,y)L(x,y)。 9 q 謂詞常項(xiàng)謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂詞。用大寫(xiě)字母表示。表示具體性質(zhì)或關(guān)系的謂詞。用大寫(xiě)字母表示。 如如(1)(1)、 (2)(2) 、(3)(3) 中謂詞中謂詞F F、G G、H H。 q 謂詞變項(xiàng)謂詞變項(xiàng)：表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞。用大寫(xiě)：表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞。用大寫(xiě) 字母表示。如字母表示。如(4)(4) 中謂詞中謂詞L L。 qn n( (n n 1)1)元謂詞元謂詞：P(xP(x1 1,x,x2 2, , ,x xn n) )表示含表示含n n個(gè)命題變項(xiàng)的個(gè)命題變項(xiàng)的n n元

8、謂詞元謂詞 。 n=1n=1時(shí)，一元謂詞時(shí)，一元謂詞表示表示x x1 1具有性質(zhì)具有性質(zhì)P P。 n2n2時(shí)，多元謂詞時(shí)，多元謂詞表示表示x x1 1,x,x2 2, , ,x xn n具有關(guān)系具有關(guān)系P P。 q0 0元謂詞元謂詞：不含個(gè)體變項(xiàng)的謂詞：不含個(gè)體變項(xiàng)的謂詞。如。如F(a)F(a)、G(a,b)G(a,b)、 P( P(a a1 1,a,a2 2, ,a,an n) )。 qn n元謂詞是命題嗎？元謂詞是命題嗎？ 不是，只有用謂詞常項(xiàng)取代不是，只有用謂詞常項(xiàng)取代P P，用個(gè)體常項(xiàng)取代用個(gè)體常項(xiàng)取代 x x1 1,x,x2 2, , ,x xn n時(shí)，才能使時(shí)，才能使n n元謂詞變

9、為命題。元謂詞變?yōu)槊}。 思思 考考 謂詞及相關(guān)概念謂詞及相關(guān)概念 10 例題例題 例例4.14.1 將下列命題在一階邏輯中用將下列命題在一階邏輯中用0 0元謂詞符號(hào)化，并討論真值。元謂詞符號(hào)化，并討論真值。 (1)(1)只有只有2 2是素?cái)?shù)，是素?cái)?shù)，4 4才是素?cái)?shù)。才是素?cái)?shù)。 (2)(2)如果如果5 5大于大于4 4，則，則4 4大于大于6. 6. 解：解： (1)(1)設(shè)一元謂詞設(shè)一元謂詞F(x):xF(x):x是素?cái)?shù)，是素?cái)?shù)，a:2a:2，b:4b:4。 命題符號(hào)化為命題符號(hào)化為0 0元謂詞的蘊(yùn)涵式元謂詞的蘊(yùn)涵式 F(b)F(a) F(b)F(a) 由于此蘊(yùn)涵前件為假，所以命題為真。由于

10、此蘊(yùn)涵前件為假，所以命題為真。 (2)(2)設(shè)二元謂詞設(shè)二元謂詞G(x,y):xG(x,y):x大于大于y y，a:4a:4，b:5b:5，c:6c:6。 命題符號(hào)化為命題符號(hào)化為0 0元謂詞的蘊(yùn)涵式元謂詞的蘊(yùn)涵式 G(b,a)G(a,c)G(b,a)G(a,c) 由于由于G(b,a)G(b,a)為真，而為真，而G(a,c)G(a,c)為假，所以命題為假。為假，所以命題為假。 11 例題例題 將命題將命題“這只大紅書(shū)柜擺滿(mǎn)了那些古書(shū)。這只大紅書(shū)柜擺滿(mǎn)了那些古書(shū)。”符號(hào)化符號(hào)化. . (1)(1)設(shè)設(shè) F(x,y)F(x,y)：x x擺滿(mǎn)了擺滿(mǎn)了y y，R(x)R(x)：x x是大紅書(shū)柜是大紅書(shū)

11、柜 Q(y)Q(y)：y y是古書(shū)，是古書(shū)，a a：這只，這只， b b：那些那些 符號(hào)化為：符號(hào)化為：R(a)Q(b)F(a,b) R(a)Q(b)F(a,b) (2)(2)設(shè)設(shè) A(x)A(x)：x x是書(shū)柜，是書(shū)柜，B(x)B(x)：x x是大的是大的 C(x)C(x)：x x是紅的，是紅的，D(y)D(y)：y y是古老的是古老的 E(y)E(y)： y y是圖書(shū)，是圖書(shū)，F(xiàn)(x,y)F(x,y)：x x擺滿(mǎn)了擺滿(mǎn)了y y a a：這只這只b b：那些那些 符號(hào)化為：符號(hào)化為：A(a)B(a)C(a)D(b)E(b)F(a,b) A(a)B(a)C(a)D(b)E(b)F(a,b) 1

12、2 量詞（量詞（quantifiersquantifiers）是表示個(gè)體常項(xiàng)或個(gè)體變項(xiàng)之間數(shù)量關(guān)是表示個(gè)體常項(xiàng)或個(gè)體變項(xiàng)之間數(shù)量關(guān) 系的詞。系的詞。 1 1. . 全稱(chēng)量詞全稱(chēng)量詞：符號(hào)化為符號(hào)化為“ ” q 日常生活和數(shù)學(xué)中所用的日常生活和數(shù)學(xué)中所用的“一切的一切的”、“所有的所有的”、“每一每一 個(gè)個(gè)”、“任意的任意的”、“凡凡”、“都都”等詞可統(tǒng)稱(chēng)為全稱(chēng)量詞等詞可統(tǒng)稱(chēng)為全稱(chēng)量詞 。 q x x表示個(gè)體域里的所有個(gè)體，表示個(gè)體域里的所有個(gè)體， xF(xxF(x) )表示個(gè)體域里所有個(gè)體表示個(gè)體域里所有個(gè)體 都有性質(zhì)都有性質(zhì)F F。 2 2. .存在量詞存在量詞：符號(hào)化為：符號(hào)化為“ ” q

13、 日常生活和數(shù)學(xué)中所用的日常生活和數(shù)學(xué)中所用的“存在存在”、“有一個(gè)有一個(gè)”、“有的有的” 、“至少有一個(gè)至少有一個(gè)”等詞統(tǒng)稱(chēng)為存在量詞。等詞統(tǒng)稱(chēng)為存在量詞。 q y y表示個(gè)體域里有的個(gè)體，表示個(gè)體域里有的個(gè)體， yG(yyG(y) )表示個(gè)體域里存在個(gè)體具表示個(gè)體域里存在個(gè)體具 有性質(zhì)有性質(zhì)G G等。等。 量詞及相關(guān)概念量詞及相關(guān)概念 13 例例4.24.2 在個(gè)體域分別限制為在個(gè)體域分別限制為( (a)a)和和( (b)b)條件時(shí)，將下面兩個(gè)條件時(shí)，將下面兩個(gè) 命題符號(hào)化命題符號(hào)化: : (1) (1) 凡人都呼吸。凡人都呼吸。 (2) (2) 有的人用左手寫(xiě)字。有的人用左手寫(xiě)字。 其中

14、其中:(:(a)a)個(gè)體域個(gè)體域D D1 1為人類(lèi)集合；為人類(lèi)集合； ( (b)b)個(gè)體域個(gè)體域D D2 2為全總個(gè)體域。為全總個(gè)體域。 一階邏輯命題符號(hào)化一階邏輯命題符號(hào)化 14 解解: (: (a)a)個(gè)體域?yàn)槿祟?lèi)集合。個(gè)體域?yàn)槿祟?lèi)集合。 令令F(x):xF(x):x呼吸。呼吸。G(x):xG(x):x用左手寫(xiě)字。用左手寫(xiě)字。 (1) (1) 在個(gè)體域中除了人外，再無(wú)別的東西，因而在個(gè)體域中除了人外，再無(wú)別的東西，因而“凡人都呼凡人都呼 吸吸”應(yīng)符號(hào)化為應(yīng)符號(hào)化為 xF(xxF(x) ) (2) (2) 在個(gè)體域中除了人外，再無(wú)別的東西，因而在個(gè)體域中除了人外，再無(wú)別的東西，因而“有的人用

15、有的人用 左手寫(xiě)字左手寫(xiě)字”符號(hào)化為符號(hào)化為 xG(xxG(x) ) 15 ( (b)b)個(gè)體域?yàn)槿倐€(gè)體域個(gè)體域?yàn)槿倐€(gè)體域。 即除人外，還有萬(wàn)物，所以必須考慮將人先分離出來(lái)。即除人外，還有萬(wàn)物，所以必須考慮將人先分離出來(lái)。 令令F(x):xF(x):x呼吸。呼吸。 G(x):xG(x):x用左手寫(xiě)字。用左手寫(xiě)字。 M(x):xM(x):x是人。是人。 (1) “(1) “凡人都呼吸凡人都呼吸”應(yīng)符號(hào)化為應(yīng)符號(hào)化為 x(M(x)x(M(x)F(x)F(x) (2) (2) “有的人用左手寫(xiě)字有的人用左手寫(xiě)字”符號(hào)化為符號(hào)化為 x(M(x)x(M(x)G(x)G(x) q在使用全總個(gè)體域時(shí)，要

16、將人從其他事物中區(qū)別出來(lái)，為此在使用全總個(gè)體域時(shí)，要將人從其他事物中區(qū)別出來(lái)，為此 引進(jìn)了謂詞引進(jìn)了謂詞M(x)M(x)，稱(chēng)為稱(chēng)為特性謂詞特性謂詞。 q同一命題在不同的個(gè)體域中符號(hào)化的形式可能不同。同一命題在不同的個(gè)體域中符號(hào)化的形式可能不同。 q思考：思考：在全總個(gè)體域中，能否將在全總個(gè)體域中，能否將(1)(1)符號(hào)化為符號(hào)化為 x(M(x)F(x)x(M(x)F(x)？ 能否將能否將(2)(2)符號(hào)化為符號(hào)化為 x(M(x)G(x)x(M(x)G(x)？ 結(jié)結(jié) 論論 16 例題例題 例例4.3 在個(gè)體域限制為在個(gè)體域限制為( (a)a)和和( (b)b)條件時(shí)，將下列命題符號(hào)化條件時(shí)，將下

17、列命題符號(hào)化: : (1) (1) 對(duì)于任意的對(duì)于任意的x x，均有均有x x2 2-3x+2=(x-1)(x-2)-3x+2=(x-1)(x-2)。 (2) (2) 存在存在x x，使得使得x+5=3x+5=3。 其中其中: (: (a)a)個(gè)體域個(gè)體域D D1 1=N(N=N(N為自然數(shù)集合為自然數(shù)集合) ) ( (b)b)個(gè)體域個(gè)體域D D2 2=R(R=R(R為實(shí)數(shù)集合為實(shí)數(shù)集合) ) ( (a)a)令令F(x): xF(x): x2 2-3x+2=(x-1)(x-2)-3x+2=(x-1)(x-2)，G(x): x+5=3G(x): x+5=3。 命題命題(1)(1)的符號(hào)化形式為的

18、符號(hào)化形式為 xF(xxF(x) ) （真命題）真命題） 命題命題(2)(2)的符號(hào)化形式為的符號(hào)化形式為 xG(xxG(x)（假命題）假命題） ( (b)b)在在D D2 2內(nèi)，內(nèi)，(1)(1)和和(2)(2)的符號(hào)化形式同的符號(hào)化形式同( (a)a)，皆為真命題。皆為真命題。 q在不同個(gè)體域內(nèi)，同一個(gè)命題的符號(hào)化形式可能不在不同個(gè)體域內(nèi)，同一個(gè)命題的符號(hào)化形式可能不 同，也可能相同。同，也可能相同。 q同一個(gè)命題，在不同個(gè)體域中的真值也可能不同。同一個(gè)命題，在不同個(gè)體域中的真值也可能不同。 說(shuō)說(shuō) 明明 17 例例4.44.4 將下列命題符號(hào)化，并討論真值。將下列命題符號(hào)化，并討論真值。 （

19、1 1）所有的人長(zhǎng)著黑頭發(fā)。）所有的人長(zhǎng)著黑頭發(fā)。 （2 2）有的人登上過(guò)月球。）有的人登上過(guò)月球。 （3 3）沒(méi)有人登上過(guò)木星。）沒(méi)有人登上過(guò)木星。 （4 4）在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。）在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。 分析：謂詞邏輯中命題的符號(hào)化，主要考慮：分析：謂詞邏輯中命題的符號(hào)化，主要考慮： (1)(1)非空個(gè)體域的選取。若是為了確定命題的真值，一般約非空個(gè)體域的選取。若是為了確定命題的真值，一般約 定在某個(gè)個(gè)體域上進(jìn)行，否則，在由一切事物構(gòu)成的全總定在某個(gè)個(gè)體域上進(jìn)行，否則，在由一切事物構(gòu)成的全總 個(gè)體域上考慮問(wèn)題時(shí)，需要增加一個(gè)指出個(gè)體變量變化范個(gè)體域上考慮問(wèn)題時(shí)，需要增

20、加一個(gè)指出個(gè)體變量變化范 圍的特性謂詞。圍的特性謂詞。 (2)(2)量詞的使用及作用范圍。量詞的使用及作用范圍。 (3)(3)正確地語(yǔ)義。正確地語(yǔ)義。 例題例題 18 例題例題 解：沒(méi)有提出個(gè)體域，所以認(rèn)為是全總個(gè)體域。解：沒(méi)有提出個(gè)體域，所以認(rèn)為是全總個(gè)體域。 （1 1）所有的人長(zhǎng)著黑頭發(fā)。）所有的人長(zhǎng)著黑頭發(fā)。 令令F(x):xF(x):x長(zhǎng)著黑頭發(fā)，長(zhǎng)著黑頭發(fā)， M(x):xM(x):x是人。命題符號(hào)化為是人。命題符號(hào)化為 x(M(x)x(M(x)F(x)F(x)。 命題真值為假。命題真值為假。 （2 2）有的人登上過(guò)月球。）有的人登上過(guò)月球。 令令G(x):xG(x):x登上過(guò)月球登上

21、過(guò)月球， M(x):xM(x):x是人。命題符號(hào)化為是人。命題符號(hào)化為 x(M(x)x(M(x)G(x)G(x)。 命題真值為真。命題真值為真。 19 例題例題 （3 3）沒(méi)有人登上過(guò)木星。）沒(méi)有人登上過(guò)木星。 令令H(x):xH(x):x登上過(guò)木星登上過(guò)木星， M(x):xM(x):x是人。命題符號(hào)化為是人。命題符號(hào)化為 x(M(x)x(M(x)H(x)H(x)。 命題真值為真。命題真值為真。 （4 4）在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。 令令F(x):xF(x):x是在美國(guó)留學(xué)的學(xué)生，是在美國(guó)留學(xué)的學(xué)生，G(x):xG(x):x是亞洲人。符號(hào)化是亞洲人。符號(hào)化

22、 x(F(x)G(x)x(F(x)G(x) 命題真值為真。命題真值為真。 20 例題例題 n n元謂詞的符號(hào)化元謂詞的符號(hào)化 例例4.54.5 將下列命題符號(hào)化將下列命題符號(hào)化 （1 1）兔子比烏龜跑得快。）兔子比烏龜跑得快。 （2 2）有的兔子比所有的烏龜跑得快。）有的兔子比所有的烏龜跑得快。 （3 3）并不是所有的兔子都比烏龜跑得快。）并不是所有的兔子都比烏龜跑得快。 （4 4）不存在跑得同樣快的兩只兔子。）不存在跑得同樣快的兩只兔子。 解解：令：令 F(x):xF(x):x是兔子，是兔子， G(y):yG(y):y是烏龜，是烏龜， H(x,y):xH(x,y):x比比y y跑得快，跑得快

23、， L(x,y):xL(x,y):x與與y y跑得同樣快。跑得同樣快。 （1 1） x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y) ) （2 2） x(F(x)x(F(x) y y( (G(y)G(y)H(x,y)H(x,y) （3 3） x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y) ) （4 4） x x y(F(x)y(F(x)F(y)F(y)L(x,y)L(x,y) ) 21 一階邏輯命題符號(hào)化時(shí)需要注意的事項(xiàng)一階邏輯命題符號(hào)化時(shí)需要注意的事項(xiàng) q 分析命題中表示性質(zhì)和關(guān)系的謂詞，分別符號(hào)為一元和分析命題中表示性質(zhì)和關(guān)系的謂詞，分別符

24、號(hào)為一元和n n（ n n 2 2）元謂詞。元謂詞。 q 根據(jù)命題的實(shí)際意義選用全稱(chēng)量詞或存在量詞。根據(jù)命題的實(shí)際意義選用全稱(chēng)量詞或存在量詞。 q 一般說(shuō)來(lái)，多個(gè)量詞出現(xiàn)時(shí)，它們的順序不能隨意調(diào)換。一般說(shuō)來(lái)，多個(gè)量詞出現(xiàn)時(shí)，它們的順序不能隨意調(diào)換。 例如，考慮個(gè)體域?yàn)閷?shí)數(shù)集，例如，考慮個(gè)體域?yàn)閷?shí)數(shù)集，H(xH(x，y)y)表示表示x+y=10 x+y=10， 則命題則命題“對(duì)于任意的對(duì)于任意的x x，都存在都存在y y，使得使得x+y=10”x+y=10”的符號(hào)化形的符號(hào)化形 式為式為 x x y yH(x,yH(x,y) )，為真命題。為真命題。 如果改變兩個(gè)量詞的順序，得如果改變兩個(gè)量詞的

25、順序，得 y y x xH(x,yH(x,y) )，為假命題。為假命題。 q 有些命題的符號(hào)化形式可不止一種。（例有些命題的符號(hào)化形式可不止一種。（例4.54.5之之(3)(3)） x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y) ) x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y) ) 22 4.24.2一階邏輯公式及解釋一階邏輯公式及解釋 q 同在命題邏輯中一樣，為在一階邏輯中進(jìn)行演算和推理，同在命題邏輯中一樣，為在一階邏輯中進(jìn)行演算和推理， 必須給出一階邏輯中公式的抽象定義，以及它們的分類(lèi)及必須給出一階邏輯中公式的抽象定義，以及它們的分類(lèi)及

26、 解釋。解釋。 q 一階語(yǔ)言一階語(yǔ)言是用于一階邏輯的形式語(yǔ)言，而一階邏輯就是建是用于一階邏輯的形式語(yǔ)言，而一階邏輯就是建 立在一階語(yǔ)言基礎(chǔ)上的邏輯體系，一階語(yǔ)言本身不具備任立在一階語(yǔ)言基礎(chǔ)上的邏輯體系，一階語(yǔ)言本身不具備任 何意義，但可以根據(jù)需要被解釋成具有某種含義何意義，但可以根據(jù)需要被解釋成具有某種含義。 q 一階語(yǔ)言的形式是多種多樣的，一階語(yǔ)言的形式是多種多樣的，本書(shū)給出的一階語(yǔ)言是便本書(shū)給出的一階語(yǔ)言是便 于將自然語(yǔ)言中的命題符號(hào)化的一階語(yǔ)言，記為于將自然語(yǔ)言中的命題符號(hào)化的一階語(yǔ)言，記為F F。 23 一階語(yǔ)言中的字母表一階語(yǔ)言中的字母表 定義定義4.1 4.1 一階語(yǔ)言一階語(yǔ)言F

27、F的的字母表字母表定義如下定義如下: : (1)(1)個(gè)體常項(xiàng)：個(gè)體常項(xiàng)：a , b , c , , ai , bi , ci , , i 1 (2)(2)個(gè)體變項(xiàng)：個(gè)體變項(xiàng)：x , y , z, , xi , yi , zi , , i 1 (3)(3)函數(shù)符號(hào)：函數(shù)符號(hào)：f , g , h , , fi , gi , hi , , i 1 (4)(4)謂詞符號(hào)：謂詞符號(hào)：F , G , H , , Fi , Gi , Hi , , i 1 (5)(5)量詞符號(hào)量詞符號(hào): : ， (6)(6)聯(lián)結(jié)詞符號(hào)聯(lián)結(jié)詞符號(hào):, :, (7)(7)括號(hào)與逗號(hào)括號(hào)與逗號(hào):(,),:(,),， 24 一階語(yǔ)

28、言中的項(xiàng)一階語(yǔ)言中的項(xiàng) 定義定義4.24.2 一階語(yǔ)言一階語(yǔ)言F F的的項(xiàng)項(xiàng)的定義如下的定義如下: : (1) (1) 個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng)項(xiàng)。 (2) (2) 若若 (x(x1 1,x,x2 2, , ,x xn n) )是任意的是任意的n n元函數(shù)，元函數(shù)，t t1 1,t,t2 2, , ,t tn n是任意是任意 的的n n個(gè)項(xiàng)，則個(gè)項(xiàng)，則 (t(t1 1,t,t2 2, , ,t tn n) )是是項(xiàng)項(xiàng)。 (3) (3) 所有的項(xiàng)都是有限次使用所有的項(xiàng)都是有限次使用(1)(1)，(2)(2)得到的。得到的。 25 一階語(yǔ)言中的原子公式一階語(yǔ)言中的原子公式 定義定

29、義4.34.3 設(shè)設(shè)R(xR(x1 1 ,x ,x2 , 2 , , ,x xn n) )是一階語(yǔ)言是一階語(yǔ)言F F的的任意任意n n元謂詞，元謂詞， t t1 1 ,t ,t2 2 , , , ,t tn n是一階語(yǔ)言是一階語(yǔ)言F F的任意的的任意的n n個(gè)項(xiàng)，則稱(chēng)個(gè)項(xiàng)，則稱(chēng) R(tR(t1 1 ,t ,t2 2 , , , ,t tn n) )是一階語(yǔ)言是一階語(yǔ)言F F的的原子公式原子公式。 例如例如：1 1元謂詞元謂詞F(x)F(x)，G(x)G(x)，2 2元謂詞元謂詞H(x,y)H(x,y)，L(x,y)L(x,y)等都等都 是原子公式。是原子公式。 26 一階語(yǔ)言一階語(yǔ)言F F的合

30、式公式的合式公式 定義定義4.4 4.4 一階語(yǔ)言一階語(yǔ)言F F的的合式公式合式公式定義如下定義如下: : (1) (1) 原子公式是合式公式。原子公式是合式公式。 (2) (2) 若若A A是合式公式，則是合式公式，則( (A)A)也是合式公式。也是合式公式。 (3) (3) 若若A A，B B是合式公式，則是合式公式，則( (A AB)B)，(A(AB)B)，(A(AB)B)，(A(AB)B) 也是合式公式。也是合式公式。 (4) (4) 若若A A是合式公式，則是合式公式，則 xAxA， xAxA也是合式公式。也是合式公式。 (5) (5) 只有有限次的應(yīng)用只有有限次的應(yīng)用(1)(1)(

31、4)(4)構(gòu)成的符號(hào)串才是合式公式。構(gòu)成的符號(hào)串才是合式公式。 一階語(yǔ)言一階語(yǔ)言F F的合式公式也稱(chēng)為的合式公式也稱(chēng)為謂詞公式謂詞公式，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng)公式公式。 qA A，B B代表任意公式，是元語(yǔ)言符號(hào)。代表任意公式，是元語(yǔ)言符號(hào)。 q下文的討論都是在一階語(yǔ)言下文的討論都是在一階語(yǔ)言F F中，因而不再提及中，因而不再提及。 說(shuō)說(shuō) 明明 27 自由出現(xiàn)與約束出現(xiàn)自由出現(xiàn)與約束出現(xiàn) 定義定義4.54.5 指導(dǎo)變?cè)⑤犛?、約束出現(xiàn)、自由出現(xiàn)指導(dǎo)變?cè)?、轄域、約束出現(xiàn)、自由出現(xiàn) q 在公式在公式 xAxA和和 xAxA中，稱(chēng)中，稱(chēng)x x為為指導(dǎo)變?cè)笇?dǎo)變?cè)?q 在公式在公式 xAxA和和 xAxA中，中

32、，A A為相應(yīng)量詞的為相應(yīng)量詞的轄域轄域。 q 在在 x x和和 x x的轄域中，的轄域中，x x的所有出現(xiàn)都稱(chēng)為的所有出現(xiàn)都稱(chēng)為約束出現(xiàn)約束出現(xiàn)。 q A A中不是約束出現(xiàn)的其他變項(xiàng)均稱(chēng)為是中不是約束出現(xiàn)的其他變項(xiàng)均稱(chēng)為是自由出現(xiàn)自由出現(xiàn)的。的。 28 例例4.64.6 指出下列各公式中的指導(dǎo)變?cè)?，各量詞的轄域，自由出指出下列各公式中的指導(dǎo)變?cè)?，各量詞的轄域，自由出 現(xiàn)以及約束出現(xiàn)的個(gè)體變項(xiàng)?，F(xiàn)以及約束出現(xiàn)的個(gè)體變項(xiàng)。 (1) (1) x x(F(F(x x,y)G(,y)G(x x,z),z) (2) (2) x x(F(F(x x)G(y)G(y) y y(H(x)L(x,(H(x)L(

33、x,y y,z) ,z) 例題例題 解答解答 (1) (1) x x是指導(dǎo)變?cè)?。量詞是指導(dǎo)變?cè)Ａ吭~ 的轄域的轄域A=(F(x,y)G(x,z)A=(F(x,y)G(x,z)。在在A A 中，中，x x的兩次出現(xiàn)均是約束出現(xiàn)。的兩次出現(xiàn)均是約束出現(xiàn)。y y和和z z均為自由出現(xiàn)。均為自由出現(xiàn)。 (2) (2) 前件上量詞前件上量詞 的指導(dǎo)變?cè)獮榈闹笇?dǎo)變?cè)獮閤 x，量詞量詞 的轄域的轄域 A=(F(x)G(y)A=(F(x)G(y)，x x在在A A中是約束出現(xiàn)的，中是約束出現(xiàn)的，y y在在A A中是自由中是自由 出現(xiàn)的。后件中量詞出現(xiàn)的。后件中量詞 的指導(dǎo)變?cè)獮榈闹笇?dǎo)變?cè)獮閥 y， 量詞量詞

34、的轄域?yàn)榈妮犛驗(yàn)?B=(H(x)L(x,y,z)B=(H(x)L(x,y,z)，y y在在B B中是約束出現(xiàn)的，中是約束出現(xiàn)的，x x、z z在在B B中中 均為自由出現(xiàn)的。均為自由出現(xiàn)的。 29 本書(shū)中的記法本書(shū)中的記法 q 用用A(xA(x1 1,x,x2 2, , ,x xn n) )表示含表示含x x1 1,x,x2 2, , ,x xn n自由出現(xiàn)的公式。自由出現(xiàn)的公式。 q 用用表示任意的量詞表示任意的量詞 或或 ，則則xx1 1A(xA(x1 1,x,x2 2, , ,x xn n) )是含是含 有有x x2 2,x,x3 3, , ,x xn n自由出現(xiàn)的公式，可記為自由出現(xiàn)的

35、公式，可記為A A1 1(x(x2 2,x,x3 3, , ,x xn n) )。 q 類(lèi)似的，類(lèi)似的，xx2 2xx1 1A(xA(x1 1,x,x2 2, , ,x xn n) )可記為可記為A A2 2(x(x3 3,x,x4 4, , ,x xn n) ) q xxn-1 n-1x xn-2 n-2x x1 1A(xA(x1 1,x,x2 2, , ,x xn n) )中只含有中只含有x xn n是自由出現(xiàn)是自由出現(xiàn) 的個(gè)體變項(xiàng)，可以記為的個(gè)體變項(xiàng)，可以記為A An-1 n-1(x (xn n) )。 q xxn nxx1 1A(xA(x1 1,x,x2 2, , ,x xn n) )

36、沒(méi)有自由出現(xiàn)的個(gè)體變項(xiàng)。沒(méi)有自由出現(xiàn)的個(gè)體變項(xiàng)。 舉例舉例 將例將例4.6(1)4.6(1)中的公式簡(jiǎn)記為中的公式簡(jiǎn)記為A(A(y y, ,z z) )，表明公式含有自由出現(xiàn)表明公式含有自由出現(xiàn) 的個(gè)體變項(xiàng)的個(gè)體變項(xiàng)y y，z z。而而 yA(y,yA(y,z z) )中只含有中只含有z z為自由出現(xiàn)的公為自由出現(xiàn)的公 式，式， z z yA(y,zyA(y,z) )中已經(jīng)沒(méi)有自由出現(xiàn)的個(gè)體變項(xiàng)了，中已經(jīng)沒(méi)有自由出現(xiàn)的個(gè)體變項(xiàng)了， 30 閉式閉式 定義定義4.64.6 設(shè)設(shè)A A是任意的公式，若是任意的公式，若A A中不含有自由出現(xiàn)的個(gè)體變中不含有自由出現(xiàn)的個(gè)體變 項(xiàng)，則稱(chēng)項(xiàng)，則稱(chēng)A A為為封

37、閉的公式封閉的公式，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng)閉式閉式。 例如：例如： x y(F(x) G(y)H(x , y) 為閉式，為閉式， x(F(x) G(x , y) 不是閉式不是閉式 。 一階公式的解釋一階公式的解釋 一階公式?jīng)]有確定的意義，一旦將其中的變項(xiàng)（項(xiàng)的變項(xiàng)、一階公式?jīng)]有確定的意義，一旦將其中的變項(xiàng)（項(xiàng)的變項(xiàng)、 謂詞變項(xiàng)）用指定的常項(xiàng)代替后，所得公式就具備一定的謂詞變項(xiàng)）用指定的常項(xiàng)代替后，所得公式就具備一定的 意義，有時(shí)就變成命題了。意義，有時(shí)就變成命題了。 31 例題例題4.74.7 例例4.74.7 將下列兩個(gè)公式中的變項(xiàng)指定成常項(xiàng)使其成為命題將下列兩個(gè)公式中的變項(xiàng)指定成常項(xiàng)使其成為命題: :

38、 (1)(1) x(F(x)x(F(x)G(x)G(x) (2)(2) x x y(F(x)y(F(x)F(y)F(y)G(x,y)G(x,y)H(f(x,y),g(x,y)H(f(x,y),g(x,y) (1)(1)指定個(gè)體變項(xiàng)的變化范圍，并且指定謂詞指定個(gè)體變項(xiàng)的變化范圍，并且指定謂詞F F，G G的含義，下的含義，下 面給出兩種指定法面給出兩種指定法: : ( (a)a)令個(gè)體域令個(gè)體域D D1 1為全總個(gè)體域，為全總個(gè)體域， F(x)F(x)為為x x是人，是人， G(x)G(x)為為x x是黃種人，是黃種人， 則命題為則命題為“所有人都是黃種人所有人都是黃種人”，這是假命題。，這是假

39、命題。 ( (b)b)令個(gè)體域令個(gè)體域D D2 2為實(shí)數(shù)集合為實(shí)數(shù)集合R R， F(x)F(x)為為x x是自然數(shù)，是自然數(shù)， G(x)G(x)為為x x是整數(shù)，是整數(shù)， 則命題為則命題為“自然數(shù)都是整數(shù)自然數(shù)都是整數(shù)”，這是真命題。，這是真命題。 32 例題例題4.74.7 (2)(2) x x y(F(x)y(F(x)F(y)F(y)G(x,y)G(x,y)H(f(x,y),g(x,y)H(f(x,y),g(x,y) 含有兩個(gè)含有兩個(gè)2 2元函數(shù)變項(xiàng)，兩個(gè)元函數(shù)變項(xiàng)，兩個(gè)1 1元謂詞變項(xiàng)，兩個(gè)元謂詞變項(xiàng)，兩個(gè)2 2元謂詞變?cè)^詞變 項(xiàng)。項(xiàng)。 指定個(gè)體域?yàn)槿倐€(gè)體域，指定個(gè)體域?yàn)槿倐€(gè)體域，

40、 F(x)F(x)為為x x是實(shí)數(shù)，是實(shí)數(shù)，G(x,y)G(x,y)為為xyxy， H(x,y)H(x,y)為為xyxy，f(x,y)=xf(x,y)=x2 2+y+y2 2， g(x,y)=2xyg(x,y)=2xy， 則表達(dá)的命題為則表達(dá)的命題為“對(duì)于任意的對(duì)于任意的x x，y y，若若x x與與y y都是實(shí)數(shù)，且都是實(shí)數(shù)，且 xyxy，則則x x2 2+y+y2 22xy”2xy”，這是真命題。這是真命題。 如果如果H(x,y)H(x,y)改為改為xyxy， 則所得命題為假命題。則所得命題為假命題。 33 一階公式的解釋一階公式的解釋 定義定義4.74.7 一階公式一階公式的的解釋解釋I

41、 I由下面由下面4 4部分組成部分組成: : ( (a)a)非空個(gè)體域非空個(gè)體域D DI I。 。 (b)D(b)DI I中一些特定元素的集合中一些特定元素的集合 。 ( (c)Dc)DI I上特定函數(shù)集合上特定函數(shù)集合 | |i, ni, n11。 (d)D(d)DI I上特定謂詞的集合上特定謂詞的集合 | |i, ni, n11。 12 , i a aa n i f n i F 34 q 為第為第i個(gè)個(gè)n元謂詞，如元謂詞，如i=2，n=3時(shí)，時(shí)， 表示第表示第2個(gè)個(gè)3 元謂詞，它可能以元謂詞，它可能以 (x,y,z)的形式出現(xiàn)在解釋中，公的形式出現(xiàn)在解釋中，公 式式A若出現(xiàn)若出現(xiàn)F2(x,

42、y,z)就解釋成就解釋成 (x,y,z)。 q 為第為第i個(gè)個(gè)n元函數(shù)。例如，元函數(shù)。例如，i=1，n=2時(shí)，時(shí)， 表示第一表示第一 個(gè)二元函數(shù)，它出現(xiàn)在解釋中，可能是個(gè)二元函數(shù)，它出現(xiàn)在解釋中，可能是 (x,y)=x2+y2， (x,y)=2xy等，一旦公式中出現(xiàn)等，一旦公式中出現(xiàn)f1(x,y)就解釋成就解釋成 (x,y)，出現(xiàn)出現(xiàn)g1(x,y)就解釋成就解釋成 (x,y)=2xy。 對(duì)解釋對(duì)解釋I I的幾點(diǎn)說(shuō)明的幾點(diǎn)說(shuō)明 q 被解釋的公式不一定全部包含解釋中的四部分。被解釋的公式不一定全部包含解釋中的四部分。 n i f 2 1 f 1 f 1 g 1 f 1 g n i F 3 2F 2

43、 F 2 F q 在解釋的公式在解釋的公式A A中的個(gè)體變項(xiàng)均取值于中的個(gè)體變項(xiàng)均取值于D DI I。 q 若若A A中含有個(gè)體常項(xiàng)中含有個(gè)體常項(xiàng)，就解釋成就解釋成 。 i a q 在解釋的定義中引進(jìn)了幾個(gè)元語(yǔ)言符號(hào)，如在解釋的定義中引進(jìn)了幾個(gè)元語(yǔ)言符號(hào)，如 i a n i f n i F 35 例例4.84.8 給定解釋給定解釋I I如下如下: : ( (a) a) 個(gè)體域個(gè)體域D=N(ND=N(N為自然數(shù)集合，即為自然數(shù)集合，即 N=0,1,2,N=0,1,2,) ) (b) =0 a (c) (x,y)=x+y, (x,y)=xy。fg (d) (x,y)為為x=y。 F 在在I下，下列

44、哪些公式為真下，下列哪些公式為真?哪些為假哪些為假?哪些的真值還不能確定哪些的真值還不能確定? 例題例題4.8 36 例題例題4.84.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) x y(F(f(x,a),y)F(f(y,a),x) (8) x y z F(f(x,y),z) (9) x F(f(x,x),g(x,x) 37 例題例題4.84.8 (1) (1) F(f(x,

45、y),g(x,y)F(f(x,y),g(x,y) 公式被解釋成公式被解釋成“x+y=xx+y=xy y”，這不是命題。這不是命題。 (2) (2) F(f(x,a),y)F(g(x,y),z)F(f(x,a),y)F(g(x,y),z) 公式被解釋成公式被解釋成“( (x+0=y)x+0=y)(x(xy=z)y=z)”，這也不是命題。這也不是命題。 (3) (3) F(g(x,y),g(y,z)F(g(x,y),g(y,z) 公式被解釋成公式被解釋成“x xy yy yz z”，同樣不是命題。同樣不是命題。 (4) (4) x F(g(x,y),z)x F(g(x,y),z) 公式被解釋成公式

46、被解釋成“ x(xx(xy=z)y=z)”，不是命題。不是命題。 38 例題例題4.84.8 (5) (5) x F(g(x,a),x)F(x,y)x F(g(x,a),x)F(x,y) 公式被解釋成公式被解釋成“ x(xx(x0=x)0=x)(x=y)(x=y)”，由于前件為假，所以由于前件為假，所以 被被 解釋的公式為真。解釋的公式為真。 (6) (6) x F(g(x,a),x)x F(g(x,a),x) 公式被解釋成公式被解釋成“ x(xx(x0=x)0=x)”，為假命題。為假命題。 (7) (7) x x y(F(f(x,a),y)F(f(y,a),x)y(F(f(x,a),y)F(

47、f(y,a),x) 公式被解釋成公式被解釋成“ x x y(x+0=y)y(x+0=y)(y+0=x)(y+0=x)”，為真命題。為真命題。 39 (8) (8) x x y y z F(f(x,y),z)z F(f(x,y),z) 公式被解釋成公式被解釋成“ x x y y z(x+y=z)z(x+y=z)”，這也為真命題。這也為真命題。 (9) (9) x F(f(x,x),g(x,x)x F(f(x,x),g(x,x) 公式被解釋成公式被解釋成“ x(x+x=xx(x+x=xx)x)”，為真命題。為真命題。 q閉式在給定的解釋中都變成了命題。如閉式在給定的解釋中都變成了命題。如(6)(6

48、) (8)(8)。 q不是閉式的公式在某些解釋下也可能變?yōu)槊}。如不是閉式的公式在某些解釋下也可能變?yōu)槊}。如(5)(5)。 結(jié)結(jié) 論論 例題例題4.84.8 定理定理4.14.1 封閉的公式在任何解釋下都變成命題。封閉的公式在任何解釋下都變成命題。 40 一階公式的分類(lèi)一階公式的分類(lèi) 定義定義4.8 4.8 永真式、永假式、可滿(mǎn)足式永真式、永假式、可滿(mǎn)足式 q 設(shè)設(shè)A A為一個(gè)公式，若為一個(gè)公式，若A A在任何解釋下均為真，則稱(chēng)在任何解釋下均為真，則稱(chēng)A A為為永真式永真式 ( (或稱(chēng)或稱(chēng)邏輯有效式邏輯有效式) )。 q 設(shè)設(shè)A A為一個(gè)公式，若為一個(gè)公式，若A A在任何解釋下均為假，則稱(chēng)在

49、任何解釋下均為假，則稱(chēng)A A為為矛盾式矛盾式 ( (或或永假式永假式) )。 q 設(shè)設(shè)A A為一個(gè)公式，若至少存在一個(gè)解釋使為一個(gè)公式，若至少存在一個(gè)解釋使A A為真，則稱(chēng)為真，則稱(chēng)A A為為可可 滿(mǎn)足式滿(mǎn)足式。 q 永真式一定是可滿(mǎn)足式，但可滿(mǎn)足式不一定是永真式。永真式一定是可滿(mǎn)足式，但可滿(mǎn)足式不一定是永真式。 q 在一階邏輯中，到目前為止，還沒(méi)有找到一種可行的算在一階邏輯中，到目前為止，還沒(méi)有找到一種可行的算 法，用來(lái)判斷任意一個(gè)公式是否是可滿(mǎn)足的，這與命題法，用來(lái)判斷任意一個(gè)公式是否是可滿(mǎn)足的，這與命題 邏輯的情況是完全不同的。邏輯的情況是完全不同的。 q 但對(duì)某些特殊的公式還是可以判斷

50、的。但對(duì)某些特殊的公式還是可以判斷的。 說(shuō)說(shuō) 明明 41 代換實(shí)例代換實(shí)例 定義定義4.9 4.9 設(shè)設(shè)A A0 0是含有命題變項(xiàng)是含有命題變項(xiàng)p p1 1,p,p2 2, , ,p pn n的命題公式，的命題公式， A A1 1,A,A2 2, ,A,An n是是n n個(gè)謂詞公式，用個(gè)謂詞公式，用A Ai i(1(1i in)n)處處代替處處代替A A0 0 中的中的p pi i，所得公式所得公式A A稱(chēng)為稱(chēng)為A A0 0的的代換實(shí)例代換實(shí)例。 例如例如，F(xiàn)(x)F(x)G(x), G(x), xF(x)xF(x)yG(yyG(y) )等都是等都是p pq q的代換的代換 實(shí)例，而實(shí)例，而

51、x(F(x)x(F(x)G(x)G(x)等不是等不是p pq q的代換實(shí)例。的代換實(shí)例。 定理定理4.24.2 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí) 例都是矛盾式。例都是矛盾式。 42 例例4.9 4.9 判斷下列公式中，哪些是永真式，哪些是矛盾式？判斷下列公式中，哪些是永真式，哪些是矛盾式？ （1 1） x x( (F F( (x x) )G G( (x x) （2 2） x x( (F F( (x x) ) G G( (x x) （3 3） xFxF( (x x) )( ( x x yGyG( (x x, ,y y) )xFxF( (x x)

52、 （4 4） ( ( xFxF( (x x) )yGyG( (y y)yGyG( (y y) ) 解解: (1) : (1) x x( (F F( (x x) )G G( (x x) 解釋解釋1 1：個(gè)體域?yàn)閷?shí)數(shù)集合：個(gè)體域?yàn)閷?shí)數(shù)集合R R，F(xiàn)(x)F(x)：x x是整數(shù)，是整數(shù)，G(x)G(x)：x x是有理是有理 數(shù)，因此公式真值為真。數(shù)，因此公式真值為真。 解釋解釋2 2：個(gè)體域?yàn)閷?shí)數(shù)集合：個(gè)體域?yàn)閷?shí)數(shù)集合R R，F(xiàn)(x)F(x)：x x是無(wú)理數(shù)，是無(wú)理數(shù)，G(x)G(x)：x x能表能表 示成分?jǐn)?shù)，因此公式真值為假。示成分?jǐn)?shù)，因此公式真值為假。 所以公式為非永真式的可滿(mǎn)足式。所以公式為

53、非永真式的可滿(mǎn)足式。 例題例題4.94.9 43 例題例題4.94.9 （2 2） x x( (F F( (x x) ) G G( (x x) 公式為非永真式的可滿(mǎn)足式。公式為非永真式的可滿(mǎn)足式。 （3 3） xFxF( (x x) )( ( x x yGyG( (x x, ,y y) )xFxF( (x x) 為為p p( (q qp p) )（重言式）的代換實(shí)例，故為永真式。重言式）的代換實(shí)例，故為永真式。 （4 4） ( ( xFxF( (x x) )yGyG( (y y)yGyG( (y y) ) 為為 ( (p pq q) ) q q（矛盾式）的代換實(shí)例，故為永假式。矛盾式）的代換實(shí)

54、例，故為永假式。 44 例題例題 例例4.104.10 判斷下列公式的類(lèi)型。判斷下列公式的類(lèi)型。 (1) (1) xF(xxF(x) ) xF(xxF(x) ) (2) (2) x x yF(x,yyF(x,y) ) x x yF(x,yyF(x,y) ) (3) (3) x(F(x)G(x) x(F(x)G(x) yG(yyG(y) ) 解解 記記(1)(1)，(2)(2)，(3)(3)中的公式分別為中的公式分別為A,B,CA,B,C。 (1)(1)設(shè)設(shè)I I為任意一個(gè)解釋?zhuān)瑐€(gè)體域?yàn)闉槿我庖粋€(gè)解釋?zhuān)瑐€(gè)體域?yàn)镈 D。 若存在若存在x x0 0D D，使得使得F(xF(x0 0) )為假，則為假

55、，則 xF(xxF(x) )為假，所以為假，所以A A的前的前 件為假，故件為假，故A A為真。為真。 若對(duì)于任意若對(duì)于任意x xD D，F(xiàn)(x)F(x)均為真，則均為真，則 xF(x)xF(x)， xF(xxF(x) )都為真都為真 ，從而，從而A A為真。為真。 所以在所以在I I下下A A為真。由為真。由I I的任意性可知，的任意性可知，A A是永真式。是永真式。 45 例題例題 (2) (2) x x yF(x,yyF(x,y) ) x x yF(x,yyF(x,y) ) 取解釋取解釋I I：個(gè)體域?yàn)樽匀粩?shù)集合個(gè)體域?yàn)樽匀粩?shù)集合N N，F(xiàn)(x,y)F(x,y)為為x xy y。 在在I

56、 I下下B B的前件與后件均為真，所以的前件與后件均為真，所以B B為真。這說(shuō)明為真。這說(shuō)明B B不是矛盾不是矛盾 式。（式。（ 在在 x x yF(x,yyF(x,y) )中，中，x x0 0 ） 再取再取II：個(gè)體域仍然為個(gè)體域仍然為N N，F(xiàn)(x,y)F(x,y)為為x=yx=y。 在在II下，下，B B的前件真而后件假，所以的前件真而后件假，所以B B為假。這說(shuō)明為假。這說(shuō)明B B不是永不是永 真式。真式。 故故B B是非永真式的可滿(mǎn)足式。是非永真式的可滿(mǎn)足式。 (3) (3) x(F(x)G(x) x(F(x)G(x) yG(yyG(y) ) C C也是非永真式的可滿(mǎn)足式。也是非永真

57、式的可滿(mǎn)足式。 小節(jié)結(jié)束小節(jié)結(jié)束 46 本章主要內(nèi)容本章主要內(nèi)容 q 個(gè)體詞個(gè)體詞 個(gè)體常項(xiàng)個(gè)體常項(xiàng) 個(gè)體變項(xiàng)個(gè)體變項(xiàng) 個(gè)體域個(gè)體域 全總個(gè)體域全總個(gè)體域 q 謂詞謂詞 謂詞常項(xiàng)謂詞常項(xiàng) 謂詞變項(xiàng)謂詞變項(xiàng) n(n1)n(n1)元謂詞元謂詞 特性謂詞特性謂詞 q 量詞量詞 全稱(chēng)量詞全稱(chēng)量詞 存在量詞存在量詞 47 本章主要內(nèi)容本章主要內(nèi)容 q 一階邏輯中命題符號(hào)化一階邏輯中命題符號(hào)化 q 一階邏輯公式一階邏輯公式 原子公式原子公式 合式公式（或公式）合式公式（或公式） 閉式閉式 q 解釋解釋 q 一階邏輯公式的分類(lèi)一階邏輯公式的分類(lèi) 邏輯有效式（或永真式）邏輯有效式（或永真式） 矛盾式（或永假式

58、）矛盾式（或永假式） 可滿(mǎn)足式可滿(mǎn)足式 48 本章學(xué)習(xí)要求本章學(xué)習(xí)要求 q 要求準(zhǔn)確地將給出的命題符號(hào)化：要求準(zhǔn)確地將給出的命題符號(hào)化： 當(dāng)給定個(gè)體域時(shí)，在給定個(gè)體域內(nèi)將命題符號(hào)化。當(dāng)給定個(gè)體域時(shí)，在給定個(gè)體域內(nèi)將命題符號(hào)化。 當(dāng)沒(méi)給定個(gè)體域時(shí)，應(yīng)在全總個(gè)體域內(nèi)符號(hào)化。當(dāng)沒(méi)給定個(gè)體域時(shí)，應(yīng)在全總個(gè)體域內(nèi)符號(hào)化。 在符號(hào)化時(shí)，當(dāng)引入特性時(shí)，注意全稱(chēng)量詞與蘊(yùn)含聯(lián)結(jié)詞的在符號(hào)化時(shí)，當(dāng)引入特性時(shí)，注意全稱(chēng)量詞與蘊(yùn)含聯(lián)結(jié)詞的 搭配，存在量詞與合取聯(lián)結(jié)詞的搭配。搭配，存在量詞與合取聯(lián)結(jié)詞的搭配。 q 深刻理解邏輯有效式、矛盾式、可滿(mǎn)足式的概念。深刻理解邏輯有效式、矛盾式、可滿(mǎn)足式的概念。 q 記住閉式的性

59、質(zhì)：在任何解釋下均為命題。記住閉式的性質(zhì)：在任何解釋下均為命題。 q 對(duì)給定的解釋?zhuān)瑫?huì)判別公式的真值或不能確定真值。對(duì)給定的解釋?zhuān)瑫?huì)判別公式的真值或不能確定真值。 小節(jié)結(jié)束小節(jié)結(jié)束 49 習(xí)題選講習(xí)題選講命題符號(hào)化命題符號(hào)化 1. 1. 在一階邏輯中將下列命題符號(hào)化。在一階邏輯中將下列命題符號(hào)化。 （1 1） 每個(gè)人都有心臟。每個(gè)人都有心臟。 （2 2） 有的狗會(huì)飛。有的狗會(huì)飛。 （3 3） 沒(méi)有不犯錯(cuò)誤的人。沒(méi)有不犯錯(cuò)誤的人。 （4 4） 發(fā)光的不都是金子。發(fā)光的不都是金子。 （5 5） 一切人都不一樣高。一切人都不一樣高。 （6 6） 并不是所有的汽車(chē)都比火車(chē)快。并不是所有的汽車(chē)都比火車(chē)快

60、。 （7 7） 沒(méi)有一個(gè)自然數(shù)大于等于任何自然數(shù)。沒(méi)有一個(gè)自然數(shù)大于等于任何自然數(shù)。 （8 8） 有唯一的偶素?cái)?shù)。有唯一的偶素?cái)?shù)。 （9 9） 不管黑貓白貓，抓住老鼠就是好貓。不管黑貓白貓，抓住老鼠就是好貓。 （1010）對(duì)平面上任意兩點(diǎn)，有且僅有一條直線通過(guò)這兩點(diǎn)。）對(duì)平面上任意兩點(diǎn)，有且僅有一條直線通過(guò)這兩點(diǎn)。 50 習(xí)題選講習(xí)題選講命題符號(hào)化命題符號(hào)化 解：由于沒(méi)指出個(gè)體域，故用全總個(gè)體域解：由于沒(méi)指出個(gè)體域，故用全總個(gè)體域 （1 1）每個(gè)人都有心臟。）每個(gè)人都有心臟。 本命題的含義：對(duì)于每一個(gè)本命題的含義：對(duì)于每一個(gè)x x，如果如果x x是人，則是人，則x x有心臟。有心臟。 因而應(yīng)首