lecture6一階邏輯基本概念.ppt

在命題邏輯中，命題是最基本的單位，對(duì)簡(jiǎn)單命題不再進(jìn)行分解，并且不考慮命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系。因而命題邏輯具有很大的局限性，甚至無(wú)法判斷一些簡(jiǎn)單而常見(jiàn)的推理?？紤]下面的推理:,所有的人都是要死的； 蘇格拉底是人。 所以，蘇格拉底是要死的。,這個(gè)蘇格拉底三段論是我們公認(rèn)的真命題，但是在命題邏輯中卻無(wú)法判斷它的正確性。因?yàn)樵诿}邏輯中只能將推理中出現(xiàn)的三個(gè)簡(jiǎn)單命題依次符號(hào)化為p，q，r，將推理的形式結(jié)構(gòu)符號(hào)化為,(pq)r,由于上式不是重言式，所以不能由它判斷推理的正確性。,個(gè)體詞，謂詞和量詞是一階邏輯命題符號(hào)化的三個(gè)基本要素。下面討論這三個(gè)要素。,個(gè)體詞是指所研究對(duì)象中可以獨(dú)立存在的具體的或抽象的客體。例如，小王，小李，中國(guó)，3等都可以作為個(gè)體詞。將表示具體或特定的客體的個(gè)體詞稱(chēng)作個(gè)體常項(xiàng)，一般用小寫(xiě)英文字母a，b，c表示；而將表示抽象或泛指的個(gè)體詞稱(chēng)為個(gè)體變項(xiàng)，常用x，y，z表示。稱(chēng)個(gè)體變項(xiàng)的取值范圍為個(gè)體域(或稱(chēng)論域)。個(gè)體域可以是有窮集合，例如，1，2，3，a，b，c，d，a，b，c，x，y，z，；也可以是無(wú)窮集合，例如，自然數(shù)集合N=0，1，2，實(shí)數(shù)集合R=x|x是實(shí)數(shù)。有一個(gè)特殊的個(gè)體域，它是由宇宙間一切事物組成的，稱(chēng)它為全總個(gè)體域。本書(shū)在論述或推理中如沒(méi)有指明所采用的個(gè)體域，都是使用全總個(gè)體域。,謂詞是用來(lái)刻畫(huà)個(gè)體詞性質(zhì)及個(gè)體詞之間相互關(guān)系的詞。,同個(gè)體詞一樣，謂詞也有常項(xiàng)和變項(xiàng)之分。表示具體性質(zhì)或關(guān)系的謂詞稱(chēng)為謂詞常項(xiàng)，表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞稱(chēng)為謂詞變項(xiàng)。無(wú)論是謂詞常項(xiàng)或變項(xiàng)都用大寫(xiě)英文字母F，G，H，表示，可根據(jù)上下文區(qū)分。,是無(wú)理數(shù)。,是個(gè)體常項(xiàng)，“是無(wú)理數(shù)”是謂詞，記為F，并用F( )表示該命題。,用P(x1,x2,xn)表示含n(n1)個(gè)命題變項(xiàng)的n元謂詞。 問(wèn)：它是不是命題？,要想使它成為命題，必須用謂詞常項(xiàng)取代P，用個(gè)體常項(xiàng)a1,a2,an取代x1,x2,xn，得P(a1,a2,an)是命題。,有了個(gè)體詞和謂詞之后，有些命題還是不能準(zhǔn)確的符號(hào)化，原因是還缺少表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞。稱(chēng)表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞為量詞。量詞可分兩種:,日常生活和數(shù)學(xué)中所用的“一切的”，“所有的”，“每一個(gè)”，“任意的”，“凡”，“都”等詞可統(tǒng)稱(chēng)為全稱(chēng)量詞，將它們符號(hào)化為“”。并用x，y等表示個(gè)體域里的所有個(gè)體，而用xF(x)，yG(y)等分別表示個(gè)體域里所有個(gè)體都有性質(zhì)F和都有性質(zhì)G。,日常生活和數(shù)學(xué)中所用的“存在”，“有一個(gè)”，“有的”，“至少有一個(gè)”等詞統(tǒng)稱(chēng)為存在量詞，將它們都符號(hào)化為“”。并用x，y等表示個(gè)體域里有的個(gè)體，而用xF(x)，yG(y)等分別表示個(gè)體域里存在個(gè)體具有性質(zhì)F和存在個(gè)體具有性質(zhì)G等。,例4.2 在個(gè)體域分別限制為(a)和(b)條件時(shí)，將下面兩個(gè)命題符號(hào)化: (1) 凡人都呼吸。 (2) 有的人用左手寫(xiě)字。,其中:(a)個(gè)體域D1為人類(lèi)集合； (b)個(gè)體域D2為全總個(gè)體域。,解 (a)令F(x):x呼吸。G(x):x用左手寫(xiě)字。 (1) 在D1中除了人外，再無(wú)別的東西，因而“凡人都呼吸”應(yīng)符號(hào)化為 xF(x) (4.1),(2) 在D1中的有些個(gè)體(人)用左手寫(xiě)字，因而“有的人用左手寫(xiě)字”符號(hào)化為 xG(x) (4.2),(b) D2中除了有人外，還有萬(wàn)物，因而在(1)，(2)符號(hào)化時(shí)，必須考慮將人分離出來(lái)。令M(x):x是人。在D2中，(1)，(2)可以分別重述如下: (1)對(duì)于宇宙間一切事物而言，如果事物是人，則他要呼吸。 (2)在宇宙間存在著用左手寫(xiě)字的人。,于是(1)，(2)的符號(hào)化形式分別為 x(M(x)F(x) (4.3) 和 x(M(x)G(x) (4.4) 其中F(x)與G(x)的含義同(a)中。,命題(1)，(2)在不同的個(gè)體域D1和D2中符號(hào)化的形式不一樣。主要區(qū)別在于，在使用個(gè)體域D2時(shí)，要將人與其他事物區(qū)分開(kāi)來(lái)。為此引進(jìn)了謂詞M(x)，像這樣的謂詞稱(chēng)為特性謂詞。在命題符號(hào)化時(shí)一定要正確使用特性謂詞。,問(wèn): (a)能否將(1)符號(hào)化為x(M(x)F(x)？ (b)能否將(2)符號(hào)化為x(M(x)G(x)？,問(wèn)： 1. 在不同個(gè)體域內(nèi)，同一個(gè)命題的符號(hào)化形式可能不同，也可能相同。 2. 同一個(gè)命題，在不同個(gè)體域中的真值也可能不同。,注意,1. 一般說(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) (4.17) 所給命題顯然為真命題。但是如果改變兩個(gè)量詞的順序，得 yxH(x,y) (4.18) (4.18)已經(jīng)不表示原命題，而且它所表示的命題是假命題。,2. 有些命題的符號(hào)化形式可不止一種。,由于引進(jìn)了個(gè)體詞，謂詞和量詞的概念，現(xiàn)在可以將本章開(kāi)始時(shí)討論的推理在一階邏輯中符號(hào)化為如下形式: x(F(x)G(x)F(a)G(a) (4.21) 其中，F(xiàn)(x):x是人，G(x):x是要死的，a:蘇格拉底.,定義4.5 在公式xA和xA中，稱(chēng)x為指導(dǎo)變?cè)?，A為相應(yīng)量詞的轄域。在x和x的轄域中，x的所有出現(xiàn)都稱(chēng)為約束出現(xiàn)。A中不是約束出現(xiàn)的其他變項(xiàng)均稱(chēng)為是自由出現(xiàn)的。,定義4.6 設(shè)A是任意的公式，若A中不含有自由出現(xiàn)的個(gè)體變項(xiàng)，則稱(chēng)A為封閉的公式，簡(jiǎn)稱(chēng)閉式。,例4.7 將下列兩個(gè)公式中的變項(xiàng)指定成常項(xiàng)使其成為命題: (1)x(F(x)G(x) (4.25),解 (1)指定個(gè)體變項(xiàng)的變化范圍，并且指定謂詞F，G的含義，下面給出兩種指定法:,(a)令個(gè)體域D1為全總個(gè)體域，F(xiàn)(x)為x是人，G(x)為x是黃種人，則(4.25)表達(dá)的命題為“所有人都是黃種人”，這是假命題。,(b)令個(gè)體域D2為實(shí)數(shù)集合R，F(xiàn)(x)為x是自然數(shù)，G(x)為x是整數(shù)，則(4.25)表達(dá)的命題為“自然數(shù)都是整數(shù)”，這是真命題。,我們還可以給出其他各種不同指定，使(4.25)表達(dá)各種不同形式的命題。,定義4.8 設(shè)A為一個(gè)公式，若A在任何解釋下均為真，則稱(chēng)A為永真式(或稱(chēng)邏輯有效式)。若A在任何解釋下均為假，則稱(chēng)A為矛盾式(或永假式)。若至少存在一個(gè)解釋使A為真，則稱(chēng)A為可滿足式。,定義4.9 設(shè)A0是含有命題變項(xiàng)p1,p2,pn的命題公式，A1,A2,An是n個(gè)謂詞公式，