02離散數(shù)學(xué)課件資料

1、在命題邏輯中，命題是命題演算的基本在命題邏輯中，命題是命題演算的基本單位，不關(guān)心每個簡單命題反映的具體內(nèi)容，單位，不關(guān)心每個簡單命題反映的具體內(nèi)容，沒有進(jìn)一步研究命題的內(nèi)部結(jié)構(gòu)，因而在實沒有進(jìn)一步研究命題的內(nèi)部結(jié)構(gòu)，因而在實際應(yīng)用中存在很多缺陷。際應(yīng)用中存在很多缺陷。著名的蘇格拉底三段論著名的蘇格拉底三段論: :“所有的人都是要死的所有的人都是要死的, ,蘇格拉底是人蘇格拉底是人, ,所以是蘇所以是蘇格拉底是要死的。格拉底是要死的。” p: : 所有的人是要死的所有的人是要死的; ; q: : 蘇格拉底是人蘇格拉底是人; ; r: : 蘇格拉底是要死的蘇格拉底是要死的. . 由上述文字構(gòu)造的命

2、題邏輯推理結(jié)構(gòu)為由上述文字構(gòu)造的命題邏輯推理結(jié)構(gòu)為: : (p q) r 可知可知: : (p q) r不是一個重言式不是一個重言式, ,因此因此, ,按命題邏輯按命題邏輯的方法的方法, ,無法證明上述問題無法證明上述問題. .為了在命題演算中，反映命題的內(nèi)在聯(lián)系，為了在命題演算中，反映命題的內(nèi)在聯(lián)系，常常要將簡單命題分解成常常要將簡單命題分解成個體詞個體詞、謂詞謂詞、量詞量詞等，并對它們的形式結(jié)構(gòu)及邏輯關(guān)系加以研究，總等，并對它們的形式結(jié)構(gòu)及邏輯關(guān)系加以研究，總結(jié)出正確的推理形式和規(guī)則，這就是本章一階邏輯結(jié)出正確的推理形式和規(guī)則，這就是本章一階邏輯要研究的內(nèi)容。要研究的內(nèi)容。2022-2-1

3、3離散數(shù)學(xué)4個體詞個體詞：可以獨立存在的客體，既可以是抽象的概念，：可以獨立存在的客體，既可以是抽象的概念，也可以是具體的事物。也可以是具體的事物。謂謂 詞詞：用來刻劃個體詞的：用來刻劃個體詞的性質(zhì)性質(zhì)或個體詞之間或個體詞之間關(guān)系關(guān)系的。的。2如：李明、自然數(shù)、如：李明、自然數(shù)、2如：如：(1)(1)是無理數(shù)是無理數(shù)(性質(zhì)性質(zhì))(2) 小李小李比比小趙小趙高高2 2厘米厘米(關(guān)系關(guān)系)簡單命題總可以被分解成簡單命題總可以被分解成個體詞個體詞和和謂詞謂詞兩部分。兩部分。個體常項：指個體常項：指具體具體或或特定特定的個體的詞，用小寫字的個體的詞，用小寫字母母a, b, c,，表示。表示。個體變項：

4、表示個體變項：表示抽象抽象的或的或泛指泛指的個體的詞，用的個體的詞，用x, y, z,，表示。表示。個體域：個體變項的取值范圍。個體域：個體變項的取值范圍。 全總個體域：當(dāng)無特殊聲明時全總個體域：當(dāng)無特殊聲明時, ,表示宇宙間的一切表示宇宙間的一切 事物組成的個體域，又稱事物組成的個體域，又稱全總域全總域。謂詞常項謂詞常項：表示具體性質(zhì)或關(guān)系的謂詞，用大寫：表示具體性質(zhì)或關(guān)系的謂詞，用大寫英文字母英文字母F，G，表示。表示。謂詞變項謂詞變項：表示抽象的或泛指的性質(zhì)或關(guān)系的謂：表示抽象的或泛指的性質(zhì)或關(guān)系的謂詞，也用大寫字母詞，也用大寫字母F，G，表示。表示。一般根據(jù)上、下文區(qū)分常項與變項。一般

5、根據(jù)上、下文區(qū)分常項與變項。個體變項個體變項x具有性質(zhì)具有性質(zhì)F：記作記作F(x)個體變項個體變項x、y具有關(guān)系具有關(guān)系L：記作記作L(x,y)2(1)是無理數(shù)是無理數(shù)(性質(zhì)性質(zhì))(2) 小李小李比比小趙小趙高高2厘米厘米(關(guān)系關(guān)系)設(shè)設(shè)F(x) : x 是無理數(shù)是無理數(shù), ， 2:a設(shè)設(shè)H(x, y) : x 比比 y 高高2厘米厘米a : 小李，小李， b : 小趙小趙則則(2)可表示為可表示為： H(a, b) (不是不是H(b, a)將下列兩命題符號化：將下列兩命題符號化：則則(1)可表示為可表示為F(a) 解：解：解：解：元數(shù)：在謂詞中所包含的元數(shù)：在謂詞中所包含的個體詞個體詞( (

6、變項變項) )數(shù)數(shù)。 n元謂詞：元謂詞：含含n( (n 1)1)個個體詞的謂詞，可個個體詞的謂詞，可用用D(x1, x2,，xn) )表示。表示。 一元謂詞表性質(zhì)；一元謂詞表性質(zhì)；二元或更多元謂詞表示關(guān)系。二元或更多元謂詞表示關(guān)系。 0 0元謂詞：元謂詞：不含不含個體變項個體變項的謂詞的謂詞 。如：如：a為為2，b為為3，L(a，b)是是0元謂詞。元謂詞。例例1.1.將下列命題用將下列命題用0 0元謂詞符號化元謂詞符號化(1) 2是素數(shù)且是偶數(shù)是素數(shù)且是偶數(shù) ；(2) 如果如果2 2大于大于3 3，則，則2 2大于大于4 4 ；(3) 如果張明比李民高，李民比趙亮高，如果張明比李民高，李民比趙

7、亮高，則張明比趙亮高則張明比趙亮高 ；設(shè)設(shè)F(x) ： x是素數(shù)是素數(shù)，G( (x) )：x是偶數(shù)是偶數(shù)， a：2 2，則，則(1) 符號化為符號化為F(a) G(a) (0(0元謂詞元謂詞)引入二元謂詞：引入二元謂詞：L(x, y)：x比比y大大 a: :2 2，b: :3 3，c: :4 4， (2) 符號化為符號化為L(a,b) L(a, c)引入二元謂詞：引入二元謂詞：H(x, y)：x比比y高高 a: :張張, ,b: :李李, ,c: :趙趙, , (3) 符號化為符號化為(H(a,b) H(H(b, ,c c)H(a, c)(1) (1) 所有的人都是要死的所有的人都是要死的;

8、;(2) (2) 有些人活百歲以上有些人活百歲以上; ;考慮以下形式命題的符號化考慮以下形式命題的符號化: :量量 詞詞表示數(shù)量的詞，分表示數(shù)量的詞，分全稱量詞全稱量詞與與存在量詞存在量詞。 ：一切、所有的、任意一切、所有的、任意的；的； ：存在著、有一個、至少有一個；存在著、有一個、至少有一個； x：個體域中所有個體；個體域中所有個體； x：個體域中個體域中存在存在某個個體；某個個體； xF(x)：個體域中所有個體具有性質(zhì)個體域中所有個體具有性質(zhì)F F； xF(x)：個體域中存在著某個個體具有性質(zhì)個體域中存在著某個個體具有性質(zhì)F F。將命題將命題 “所有的人都是要死的所有的人都是要死的”符號

9、化符號化 ( (個體域為人類集合個體域為人類集合） 符號化為：符號化為： xF(x) 其中其中F(x)表示：表示：x是要死的。是要死的。將命題將命題 “有的人活百歲以上有的人活百歲以上”符號化符號化 ( (個體域為人類集合個體域為人類集合） 符號化為：符號化為： xF(x) 其中其中F(x)表示：表示：x活百歲以上?；畎贇q以上。特性謂詞特性謂詞：在全總個體域的情況下，為了：在全總個體域的情況下，為了指定指定某個某個個體變項的范圍，引入特性謂詞。個體變項的范圍，引入特性謂詞。將命題將命題( (公式公式) )“所有的人都是要死的所有的人都是要死的”符號符號化化 M(x)：x是人是人 ( (特性謂詞

10、特性謂詞) )F(x)：x是要死的是要死的命題命題( (公式公式) )符號化為：符號化為： x(M(x)F(x)分析一下：分析一下： 它與它與 xF(x)有什么區(qū)別？有什么區(qū)別？ 有了個體詞、謂詞、量詞等概念，我們就可有了個體詞、謂詞、量詞等概念，我們就可以更細(xì)致地刻劃命題公式。以更細(xì)致地刻劃命題公式。將命題將命題( (公式公式) )“有些人活百歲以上有些人活百歲以上”符號化符號化 M(x)：x是人是人( (特性謂詞特性謂詞) )F(x)：x活百歲以上活百歲以上命題命題( (公式公式) )符號化為：符號化為： x(M(x) F(x)分析一下：分析一下： 它與它與 xF(x)有什么區(qū)別？有什么區(qū)

11、別？ 使用量詞時使用量詞時, , 應(yīng)該注意以下幾點應(yīng)該注意以下幾點: :1 .在不同的個體域中，命題符號化的形式可能不一樣在不同的個體域中，命題符號化的形式可能不一樣;2. 如沒有事先給出個體域如沒有事先給出個體域,都應(yīng)以全總個體域為個體域。都應(yīng)以全總個體域為個體域。 3. 在引入特性謂詞后，引入全稱量詞與存在量詞符號化在引入特性謂詞后，引入全稱量詞與存在量詞符號化的形式是不同的的形式是不同的;4.當(dāng)個體域為有限集時，如當(dāng)個體域為有限集時，如D=a1,a2,a3,an,對于任意對于任意的謂詞的謂詞A(x)，都有，都有 (1) xA(x) A(a1) A(a2) . A(an) (2) xA(x

12、)A(a1) A(a2) A(an) 5. .多個量詞同時出現(xiàn)時，不能隨意顛倒順序多個量詞同時出現(xiàn)時，不能隨意顛倒順序; ; x y H(x，y) , 其中其中H(x，y) : x+y=5 量詞顛倒順序成立嗎量詞顛倒順序成立嗎? ?例例: : 對于任意的對于任意的x, , 存在存在y, ,使得使得x+y=5, , 取個體域為實數(shù)集合取個體域為實數(shù)集合, ,該如何符號化該如何符號化? ?在謂詞邏輯中將下列命題符號化在謂詞邏輯中將下列命題符號化(1) (1) 對所有的對所有的x，均有均有x21=(x+1)(x1) ( (個體域為自然數(shù)集個體域為自然數(shù)集) ) (2) (2) 存在存在x, ,使得使

13、得x+5=2 ( (個體域為自然數(shù)集個體域為自然數(shù)集) ) (4) (4) 存在著偶素數(shù)存在著偶素數(shù)(5) (5) 沒有不犯錯誤的人沒有不犯錯誤的人(3) (3) 凡偶數(shù)均能被凡偶數(shù)均能被2 2整除整除(6) (6) 在北京工作的人未必都是北京人在北京工作的人未必都是北京人(7) (7) 一切人都不一樣高一切人都不一樣高(8) (8) 每個自然數(shù)都有后繼數(shù)每個自然數(shù)都有后繼數(shù)(9) (9) 有的自然數(shù)無先驅(qū)數(shù)有的自然數(shù)無先驅(qū)數(shù)(10) (10) 有的有理數(shù)是整數(shù)有的有理數(shù)是整數(shù) ( (個體域為實數(shù)集個體域為實數(shù)集) )(11) 每個人都有一些缺點。每個人都有一些缺點。符號化方法符號化方法1、

14、找到所有的個體詞找到所有的個體詞; ;2 2、 是否要引入特性謂詞是否要引入特性謂詞; ;3 3、 描述個體詞性質(zhì)：性質(zhì)謂詞描述個體詞性質(zhì)：性質(zhì)謂詞( (一元一元);); 描述個體詞關(guān)系：關(guān)系謂詞描述個體詞關(guān)系：關(guān)系謂詞( (二元二元););4 4、 按原命題的實際意義進(jìn)行刻劃。按原命題的實際意義進(jìn)行刻劃。設(shè)設(shè)F(x) ：x滿足滿足x21=(x+1)(x 1) (1)符號化符號化： xF(x)(1) 對所有的對所有的x，均有均有x2 1=(x+1)(x1) ( (個體域為自然數(shù)集個體域為自然數(shù)集) ) (2) 存在存在 x,使得使得x +5=2 ( (個體域為自然數(shù)集個體域為自然數(shù)集) ) 設(shè)

15、設(shè)G(x) ：x滿足滿足x +5=2(2)符號化符號化： xG(x)要引入特性謂詞要引入特性謂詞： F(x) ： x是偶數(shù)是偶數(shù)G(x) ： x能被能被2 2整除整除F(x) ： x是偶數(shù)是偶數(shù) G(x) ： x是素數(shù)是素數(shù) 符號化：符號化： x(F(x) G(x)符號化符號化： x(F(x)G(x)(4) 存在著偶素數(shù)存在著偶素數(shù)(3) 凡偶數(shù)均能被凡偶數(shù)均能被2 2整除整除特性謂詞特性謂詞M(x)：x是人是人F(x) ： x是在北京工作的人是在北京工作的人，G(x) ：x是北京人是北京人F(x)：x犯錯誤犯錯誤符號化：符號化： x(M(x) F(x)或或 x(M(x) F(x)符號化：符號

16、化： x(F(x) G(x)(5) (5) 沒有不犯錯誤的人沒有不犯錯誤的人(6) 在北京工作的人未必都是北京人在北京工作的人未必都是北京人或：或： x(F(x) G(x)M(x) ： x是人是人, L(x，y) ： x與與y一樣高一樣高 H(x，y)：x與與y是同一個人是同一個人 符號化：符號化： x y(M(x) M(y) H(x，y) L(x,y)(7) 7) 一切人都不一樣高一切人都不一樣高(8) 每個自然數(shù)都有后繼數(shù)每個自然數(shù)都有后繼數(shù)F(x)：x自然數(shù)自然數(shù) H(x，y)：y是是x的后繼數(shù)的后繼數(shù)符號化：符號化： x(F(x) y (F(y) H(x，y)或：或： x y(M(x)

17、 M(y) H(x，y) L(x,y)或：或： x(F(x) y (F(y) H(x，y)F(x)：x是自然數(shù)是自然數(shù) ，H(x，y)：y是是x的先驅(qū)數(shù)的先驅(qū)數(shù)符號化：符號化： x(F(x) y(F(y) H(x，y) F(x)：x是有理數(shù)是有理數(shù)，G(x)：x是整數(shù)是整數(shù)符號化符號化： x(F(x) G(x)(9) 9) 有的自然數(shù)無先驅(qū)數(shù)有的自然數(shù)無先驅(qū)數(shù)(10) 有的有理數(shù)是整數(shù)有的有理數(shù)是整數(shù) ( (個體域為實數(shù)集個體域為實數(shù)集) )或：或： x(F(x) y(F(y) H(x，y)F(x,y)：x都有都有y，M(x)：x是人，是人，G(y)：y是缺點是缺點或或： ( x)( y)(M

18、(x)(G(y) F(x,y)符號化符號化： ( x) (M(x)( y) (G(y) F(x,y)(11) 每個人都有一些缺點。每個人都有一些缺點。謂詞演算中的合式公式：謂詞演算中的合式公式：原子公式：不出現(xiàn)原子公式：不出現(xiàn)命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞和和量詞量詞的命題的命題 函數(shù)函數(shù)P(x1, x2, xn) ， 其中其中x1，x2，xn為個體變項或常項。為個體變項或常項。(1) (1) 原子謂詞公式是合式公式；原子謂詞公式是合式公式；(2) (2) 若若A A是合式公式，則是合式公式，則 A也是；也是；一、一階邏輯合式一、一階邏輯合式( (謂詞謂詞) )公式的概念公式的概念(3)(3)若若A和和

19、B是合式公式，則是合式公式，則(A B),(A B)，(AB)和和(A B)也是也是 ；(4)(4)如果如果A是合式公式，是合式公式，x是是A中出現(xiàn)的個體變項，中出現(xiàn)的個體變項，則則 ( x)A和和( x)A是合式公式是合式公式 ；(5)(5)只有有限次地應(yīng)用規(guī)則只有有限次地應(yīng)用規(guī)則(1)(1)、(2)(2)、(3)(3)、(4)(4)所所得到的公式才是合式公式得到的公式才是合式公式。 謂詞合式公式即按規(guī)則謂詞合式公式即按規(guī)則(1)(1)、(2)(2)、(3)(3)、(4)(4)、(5)(5)由原子公式、聯(lián)結(jié)詞、量詞及括號組成的字符串，由原子公式、聯(lián)結(jié)詞、量詞及括號組成的字符串，但最外層括號可

20、以省略。但最外層括號可以省略。 指導(dǎo)變元及作用域指導(dǎo)變元及作用域 在謂詞公式中，形如在謂詞公式中，形如( x)P(x)或或( x)P(x)的的部分，叫做部分，叫做公式的約束部分公式的約束部分。 量詞量詞 ， 后面的后面的x叫做量詞的叫做量詞的作用變元，或作用變元，或指導(dǎo)變元指導(dǎo)變元，P(x)叫做叫做量詞的作用域量詞的作用域。 在作用域中，在作用域中，x的一切出現(xiàn)為的一切出現(xiàn)為約束出現(xiàn)約束出現(xiàn)，非，非約束出現(xiàn)的其它變元叫約束出現(xiàn)的其它變元叫自由出現(xiàn)變元自由出現(xiàn)變元。在謂詞公式中，我們還用到以下概念。在謂詞公式中，我們還用到以下概念。二、謂詞公式的改寫二、謂詞公式的改寫( y)R(x, y)中，指

21、導(dǎo)變元是中，指導(dǎo)變元是y， 的作用域為的作用域為R(x, y)，其中其中y是約束出現(xiàn)，是約束出現(xiàn)，x是自由出現(xiàn)的。是自由出現(xiàn)的。 (1) ( x)(P(x)( y)R (x,y) ；在整個合式公式中，在整個合式公式中，x是作用變元是作用變元( (指導(dǎo)變元指導(dǎo)變元),), 的作用域的作用域(P(x)( y)R(x, y)，x, y 都是約束出現(xiàn)的，都是約束出現(xiàn)的，x約束出現(xiàn)約束出現(xiàn)2 2次，次，y約束出現(xiàn)約束出現(xiàn)1 1次。次。. . 指出下列合式公式中的指導(dǎo)變元，量詞的作指出下列合式公式中的指導(dǎo)變元，量詞的作用域及變元約束的情況。用域及變元約束的情況。(2) ( x) ( y) (P(x, y)

22、 Q(y, z) ( x) R(x, y)在在( x)R(x, y)中中，x是指導(dǎo)變元，是指導(dǎo)變元， 的作用域為的作用域為R(x, y)，其中其中x約束約束出現(xiàn)出現(xiàn)1 1次，次，y自由出現(xiàn)自由出現(xiàn)1 1次。在整個合式公式中，次。在整個合式公式中，x約束出現(xiàn)約束出現(xiàn)2 2次，次，y約束出現(xiàn)約束出現(xiàn)2 2次，自由出現(xiàn)次，自由出現(xiàn)1 1次次，z自由出現(xiàn)自由出現(xiàn)1 1次。次。( x)( y)(P(x, y) Q(y, z)，x,y是作用變元，兩是作用變元，兩個量詞個量詞 的作用域都是的作用域都是(P(x,y) Q(y,z)，其中其中x, , y均為約束出現(xiàn)，均為約束出現(xiàn)，x約束出現(xiàn)約束出現(xiàn)1 1次，次

23、，y約束出現(xiàn)約束出現(xiàn)2 2次，次，z為自由出現(xiàn)為自由出現(xiàn)1 1次。次。( x)Q(x, z)中中x是作用變元，是作用變元， 的轄域為的轄域為Q(x，z)，其中其中 x 約束出現(xiàn)，約束出現(xiàn)，z自由出現(xiàn)；自由出現(xiàn)；(3) ( x)(P(x) ( x)Q(x, z)( y)R(x, y) Q(x, y) ； ( y)R(x, y)中，中，y是是作用變元，作用變元， 的轄域為的轄域為R(x, y)，其中其中y約束出現(xiàn)，約束出現(xiàn)，x自自由出現(xiàn)；由出現(xiàn)；在在( x)(P(x) ( x) Q(x,z)( y)R(x, y) 中，中，作用變元為作用變元為x， 的作用域為的作用域為(P(x) ( x)Q(x,

24、z) ( y)R(x, y), 但但Q(x, z)中的中的x不是不是 的作用變元，的作用變元，x, y均為約束出現(xiàn)，均為約束出現(xiàn)，z自由出現(xiàn)；自由出現(xiàn)； Q(x, y)中，中，x, y為自由變元。為自由變元。在整個公式中，在整個公式中，x約束出現(xiàn)約束出現(xiàn)3 3次，自由出現(xiàn)次，自由出現(xiàn)1 1次次，y約束出現(xiàn)約束出現(xiàn)1 1次，自由出現(xiàn)次，自由出現(xiàn)1 1次次，z自由出現(xiàn)自由出現(xiàn)1 1次。次。1. 1. 換名規(guī)則換名規(guī)則：2 2. . 代替規(guī)則代替規(guī)則將量詞作用域中出現(xiàn)的某個將量詞作用域中出現(xiàn)的某個約束出現(xiàn)約束出現(xiàn)的個體變項的個體變項及對應(yīng)的指導(dǎo)變項改成另一個作用域中沒有出現(xiàn)及對應(yīng)的指導(dǎo)變項改成另一個

25、作用域中沒有出現(xiàn)過的個體變項符號，公式的其余部分不變。過的個體變項符號，公式的其余部分不變。 考慮到謂詞公式中，有的個體變項既可以約束出考慮到謂詞公式中，有的個體變項既可以約束出現(xiàn)，又可以自由出現(xiàn)，為避免這種雙重性可能引起的現(xiàn)，又可以自由出現(xiàn)，為避免這種雙重性可能引起的混淆，我們要將謂詞公式進(jìn)行改寫，改寫規(guī)則如下混淆，我們要將謂詞公式進(jìn)行改寫，改寫規(guī)則如下：對某對某自由出現(xiàn)自由出現(xiàn)的個體變項用與原公式中所有個體的個體變項用與原公式中所有個體變項符號不同的變項符號去代替，且處處代替。變項符號不同的變項符號去代替，且處處代替。(1) (x)(P(x)(y)R (x,y) ；(2) ( x)( y)

26、(P(x,y) Q(y,z) ( x)P(x,y) ；(3) ( x)(P(x) ( x)Q(x,z)( y)R(x,y) Q(x,y) ； 換名規(guī)則與代替規(guī)則可避免有的個體變項既換名規(guī)則與代替規(guī)則可避免有的個體變項既可以約束出現(xiàn)，又可以自由出現(xiàn)?？梢约s束出現(xiàn)，又可以自由出現(xiàn)。例例4.4.試對下列公式換名或代替。試對下列公式換名或代替。第一步換名第一步換名: :( x)( y)(P(x,y) Q(y,z) ( u)R(u,y) ；第二步代替第二步代替: :( x)( y)(P(x,y) Q(y,z) ( u)R(u, v) ；第一步換名第一步換名: :( x)(P(x) ( u)Q(u,z)(

27、 y)R(x,y) Q(x,y)第二步代替第二步代替: :( x)(P(x) ( u)Q(u,z)( y)R(x,y) Q(s, t)(2) ( x)( y)(P(x,y) Q(y,z) ( x)R(x,y) ；(3) ( x)(P(x) ( x)Q(x,z)( y)R(x,y) Q(x,y) ；解：解：(1) ( x)(P(x)( y)R (x,y) ；不用改寫；不用改寫求下列謂詞公式的真值：求下列謂詞公式的真值：( x)(P(x)Q(x)，其中其中P(x)：x = 1，Q(x)：x = 2，且個體域且個體域 E = 1，2； 當(dāng)個體域是有限集時，如當(dāng)個體域是有限集時，如D =a1,a2,a

28、n( x)A(x)A(a1) A(a2) A(an)則：則：( x)A(x)A(a1) A(a2) A(an)從而謂詞公式的真值等價于命題公式的真值。從而謂詞公式的真值等價于命題公式的真值。解題思想解題思想解：解： ( x)(P(x)Q(x)(P(1)Q(1) (P(2)Q(2)(10 0) (01 1) 0謂詞合式公式的解釋謂詞合式公式的解釋 ( (或指派或指派) ) 一個一階邏輯合式公式中往往含有個體變項、一個一階邏輯合式公式中往往含有個體變項、謂詞變項等，一組使合式公式成為具有確定真值謂詞變項等，一組使合式公式成為具有確定真值的常項（的常項（個體個體常項、常項、謂詞謂詞常項等）就構(gòu)成了一

29、個常項等）就構(gòu)成了一個公式的公式的解釋解釋。例例6 6：給定解釋給定解釋I如下：如下： DI=2，3；DI中中特定的元素特定的元素a=2; 函數(shù)函數(shù)f(x)為為f(2)=3，f(3)=2； 謂詞謂詞F(x)為為F(2)=0，F(xiàn)(3)=1; G(x,y)為為G(i，j)=1 ，i, j=2,3; L(x,y)為為L(2,2)= L(3,3)=1; L(2,3)= L(3,2)=0.確定下列謂詞公式的真值。確定下列謂詞公式的真值。（1）x(F(x) G (x,a) (F(2) G (2,2) (F(3) G (3,2) (0 1) (1 1) 0（2）x(F(f(x) G (x, f(x) (F(

30、f(2) G (2, f(2) (F(f(3) G (3, f(3) (F(3)G (2,3)(F(2)G(3, 2) (11) (01) 1（3）xy L(x,y) x(L(x,2)L(x,3) (L(2,2)L(2,3) (L(3,2)L(3,3) (10) (01) 1永真式永真式( (邏輯有效式）：邏輯有效式）：任一組解釋皆使公式真值為任一組解釋皆使公式真值為1 1永假式：永假式： (?)(?)可滿足式：可滿足式： (?)(?) 沒有一個可行的算法來判斷一階邏輯公式的類型，沒有一個可行的算法來判斷一階邏輯公式的類型，只能對某些只能對某些特殊的特殊的公式進(jìn)行判斷公式進(jìn)行判斷。一、謂詞演算

31、中常見等值式：一、謂詞演算中常見等值式：(I) (I) 命題公式的推廣命題公式的推廣 2424個常用的命題演算等值式及其代換可推廣個常用的命題演算等值式及其代換可推廣到謂詞演算中使用到謂詞演算中使用, ,如如2. ( x)P(x) ( y)R(x,y) ( ( x)P(x) ( y)R(x, y)3. ( x)H(x,y) ( x)H(x,y)F 1. ( x)(P(x)Q(x)( x)( P(x) Q(x)() 量詞否定等值式量詞否定等值式 ( (量詞轉(zhuǎn)換律量詞轉(zhuǎn)換律) ) ( x)P(x) ( x) P(x) ( x)P(x) ( x) P(x)實例：實例：“不是所有人今天都來上課不是所有

32、人今天都來上課” “存在一些人今天沒來上課存在一些人今天沒來上課” “沒有一個人今天來上課沒有一個人今天來上課” “所有的人今天都沒來上課所有的人今天都沒來上課” 。一、謂詞演算中常見等值式：一、謂詞演算中常見等值式：() 量詞作用域的擴(kuò)張與收縮等值式量詞作用域的擴(kuò)張與收縮等值式 xA(x) Bx(A(x) B) xA(x) Bx(A(x) B)* xA(x)B x(A(x)B)B xA(x) x(BA(x) xA(x) Bx(A(x) B) xA(x) Bx(A(x) B)* xA(x)B x(A(x)B)B xA(x) x(BA(x)注意記住注意記住( (* *) )，且各等價式中的，且各

33、等價式中的B B可含其他非指導(dǎo)變元?？珊渌侵笇?dǎo)變元。() 量詞分配等價式量詞分配等價式( x)(A(x) B(x)( x)A(x) ( x)B(x)( 對對 的分配的分配)( x)(A(x) B(x)( x)A(x) ( x)B(x) ( 對對 的分配的分配)注意：注意： 對對 ， 對對 不存在分配等價式。不存在分配等價式。( x)(A(x) B(x)( x)A(x) ( x)B(x)( x)(A(x) B(x)( x)A(x) ( x)B(x)一、謂詞演算中常見等值式：一、謂詞演算中常見等值式：() 多個量詞的使用多個量詞的使用( x)( y)A(x,y)( y)( x)A(x,y)(

34、x)( y)A(x,y) ( y)( x)A(x,y)注意：注意： 其他情況下量詞換序后一般不等價。其他情況下量詞換序后一般不等價。一、謂詞演算中常見等值式：一、謂詞演算中常見等值式：前束范式前束范式：一個合式謂詞公式，它的所有量詞均：一個合式謂詞公式，它的所有量詞均 非否定非否定地出現(xiàn)在公式的最前面，且它們的地出現(xiàn)在公式的最前面，且它們的作用域一直延伸到公式的末尾。作用域一直延伸到公式的末尾。如：如： ( x)( y)( z)(P(x) F(y,z) Q(y,z)二、二、常見等值式的應(yīng)用常見等值式的應(yīng)用( (前束范式前束范式) )借助于常見等價式，我們仿照命題公式可以化成標(biāo)借助于常見等價式，

35、我們仿照命題公式可以化成標(biāo)準(zhǔn)形式，也想把謂詞公式化成標(biāo)準(zhǔn)形式。準(zhǔn)形式，也想把謂詞公式化成標(biāo)準(zhǔn)形式。例例7. 將合式公式將合式公式( x)P(x) ( y)R(y)( x)F(x)化為前束范式：化為前束范式：任一合式公式表示成前束范式可按如下步驟進(jìn)行：任一合式公式表示成前束范式可按如下步驟進(jìn)行：(1) ) 消去公式中出現(xiàn)的多余量詞；消去公式中出現(xiàn)的多余量詞；解題思想解題思想二、二、常見等值式的應(yīng)用常見等值式的應(yīng)用( (前束范式前束范式) )(2) 利用雙重否定定律、德利用雙重否定定律、德 摩根律及量詞轉(zhuǎn)換律摩根律及量詞轉(zhuǎn)換律將公式中的否定字符深入到謂詞字母前將公式中的否定字符深入到謂詞字母前(

36、(否定符否定符緊貼緊貼) )；(3) 利用換名和代換規(guī)則使所有約束變元均不相同利用換名和代換規(guī)則使所有約束變元均不相同, ,并且使自由變元也與約束變元不同并且使自由變元也與約束變元不同( (更名更名) )；(4) 利用量詞作用域的擴(kuò)張和收縮律，擴(kuò)大量詞的利用量詞作用域的擴(kuò)張和收縮律，擴(kuò)大量詞的作用域至整個公式作用域至整個公式( (擴(kuò)域擴(kuò)域) )。二、二、常見等值式的應(yīng)用常見等值式的應(yīng)用( (前束范式前束范式) ) ( xP(x) yR(y) xF(x) ( xP(x) yR(y) zF(z)(1) 更換變元符號更換變元符號 x y z(P(x) R(y) F(z)(2) 擴(kuò)大作用域擴(kuò)大作用域二

37、、常見等值式的應(yīng)用二、常見等值式的應(yīng)用( (前束范式前束范式) ) 求下列合式公式的前束范式求下列合式公式的前束范式(1) ( x)P(x) ( x)Q(x) ( x)P(x) ( x)Q(x) ( x)P(x) ( x) Q(x) ( x)(P(x) Q(x)二、常見等值式的應(yīng)用二、常見等值式的應(yīng)用( (前束范式前束范式) ) 求下列合式公式的前束范式求下列合式公式的前束范式(2) ( x)P(x) ( x)Q(x) ( x)P(x) ( x)Q(x) ( x)P(x) ( x) Q(x) ( x)P(x) ( y) Q(y) ( x)( y)(P(x)Q(y)二、常見等值式的應(yīng)用二、常見等

38、值式的應(yīng)用( (前束范式前束范式) )(3) ( x)P(x)( x)Q(x) ( x)P(x)( y)Q(y) ( x)( y)(P(x)Q(y)二、常見等值式的應(yīng)用二、常見等值式的應(yīng)用(前束范式前束范式)(4) ( x)P(x)( x)Q(x) ( x)P(x)( y)Q(y) ( x)( y)(P(x)Q(y) 求下列合式公式的前束范式求下列合式公式的前束范式 求下列合式公式的前束范式求下列合式公式的前束范式(5) ( xF(x，y) yG(y) xH(x，y)二、二、常見等值式的應(yīng)用常見等值式的應(yīng)用( (前束范式前束范式) )( xF(x，z) yG(y) xH(x，z)( xF(x，

39、z) yG(y) uH(u，z) x y( (F(x，z)G(y) uH(u，z) x y u(F(x，z)G(y)H(u，z)前束合取范式：前束合取范式：前束范式前束范式( x)P(x)的命題公式部分即的命題公式部分即P(x)為合為合取范式。取范式。前束析取范式：前束析取范式：前束范式前束范式( x)P(x)的命題公式部分即的命題公式部分即P(x)為析為析取范式。取范式。二、常見等值式的應(yīng)用二、常見等值式的應(yīng)用旅游審美文化 7陸游；沈園 城上斜陽畫角哀，沈園非復(fù)舊池臺。 傷心橋下春波綠，曾是驚鴻照影來。 柴埠溪；情人巖 , 如笛卡兒所說 :“同一件事情可以使這批人高興的要跳舞 ,卻使另一批人傷心的要流淚?！?如菊花 中國與西方山水審美觀的差異是十分明顯的。在人與自然的關(guān)系方面，中國哲學(xué)主張中國哲學(xué)主張“天人合一天人合一”，“物我一物我一體體”，而西方哲學(xué)則主張?zhí)烊藢αⅲ镂覍α?。，而西方哲學(xué)則主張?zhí)烊藢α?，物我對立。這種哲學(xué)觀念的差異，必然導(dǎo)致山水審美觀的分岐。一）、中國人特別關(guān)注山水景觀所附載的人文美一）、中國人特別關(guān)注山水景觀所附載的人文美 ;而西方則而西方則關(guān)注山水景觀本身的自然美關(guān)注山水景觀本身的自然美 滕王閣序 “落霞與孤鶩齊飛 ,秋水共