離散第二章謂詞邏輯1st

1、2/44離散數(shù)學(xué)第二章 謂詞邏輯3/44謂詞邏輯的引入在命題邏輯中，試進(jìn)行下列推理:“蘇格拉底三段論”：凡人都是要死的， P蘇格拉底是人， Q所以蘇格拉底是要死的。R(PQ)R命題邏輯中，命題被當(dāng)作一個(gè)基本的，不可分割的單位，只研究由原子命題和聯(lián)接詞所組成的復(fù)合命題，沒有研究命題內(nèi)部的內(nèi)部結(jié)構(gòu)以及 命題之間的內(nèi)在關(guān)系。4/44類似的還有很多，例如：所有的人都要呼吸，李華是人，所以李華要呼吸。所有的正整數(shù)都大于0，3是正整數(shù)，所以3大于0。本章介紹的謂詞邏輯，對原子命題的成份、結(jié)構(gòu)和原子命題間的共同特性等作了進(jìn)一步分析。引入了個(gè)體詞、謂詞、量詞、謂詞公式等概念，在此基礎(chǔ)上研究謂詞公式間的等值關(guān)系

2、和蘊(yùn)含關(guān)系，并且對命題邏輯中的推理規(guī)則進(jìn)行擴(kuò)充和進(jìn)行謂詞演繹。4/9本章內(nèi)容謂詞、個(gè)體、量詞合式謂詞公式自由變元和約束變元含有量詞的等價(jià)式和永真蘊(yùn)含式謂詞邏輯中的推理理論前束范式、斯柯林范式5/442.1基本概念和表示原子命題被分解為謂詞和個(gè)體兩部分。個(gè)體：可以獨(dú)立存在的事物 。老師，計(jì)算機(jī)，證書，道德，智商等。謂詞：用來刻劃個(gè)體的性質(zhì)或個(gè)體之間關(guān)系的詞稱為謂詞，刻劃一個(gè)個(gè)體性質(zhì)的詞稱為一元謂詞；刻劃n個(gè)個(gè)體之間關(guān)系的詞稱為n元謂詞。 6/44謂詞和個(gè)體例：（1）李明是學(xué)生；（2）張亮比陳華高；（3）陳華坐在張亮與李明之間。個(gè)體：李明，張亮，陳華謂詞：是學(xué)生； 比高； 坐在 和之間一元謂詞：

3、是學(xué)生二元謂詞： 比高三元謂詞： 坐在 和之間7/44謂詞和個(gè)體（1）李明是學(xué)生；（2）張亮比陳華高；（3）陳華坐在張亮與李明之間。一般用大寫的英文字母表示謂詞，而用小寫的英文字母表示個(gè)體。上述命題可分別表示為Q(a),P(b,c),R(c,b,a)一般地，由n個(gè)個(gè)體和n元謂詞所組成的命題可表示為F（a1,a2, ,an）,其中F表示n元謂詞, a1,a2, ,an 分別表示n個(gè)個(gè)體。注意：a1,a2, ,an的排列次序是重要的。 8/44謂詞和個(gè)體對于F（a1,a2, ,an），如果括號內(nèi)的個(gè)體是抽象的可變化的，那么F（a1,a2, ,an）稱為n元原子謂詞公式或n元命題函數(shù)。注意：命題的n

4、元謂詞表示形式和n元命題函數(shù)不同?a:張明。命題函數(shù)：P(x) x是學(xué)生。謂詞表示形式:P(a) 張明是學(xué)生。9/44個(gè)體域個(gè)體域可以是有限的，也可以是無限的。所有個(gè)體域的總和叫作全總個(gè)體域。以某個(gè)個(gè)體域?yàn)樽兓秶淖冊袀€(gè)體變元。個(gè)體域的變換范圍影響到謂詞公式的真假R(x)：x是大連理工大學(xué)軟件學(xué)院的學(xué)生如果x的討論范圍是大工軟件學(xué)院某個(gè)班級的學(xué)生如果x的討論范圍是某個(gè)幼兒園里的小朋友如果x的討論范圍是大連的所有市民任何個(gè)體的變化都有一個(gè)范圍，這個(gè)變化范圍稱為個(gè)體域(或論域)。永真永假可滿足10/44謂詞的階在謂詞P(x1,x2,xn)中，如果個(gè)體變元是一些簡單的事物，那么P為一階謂詞；若個(gè)

5、體變元中有一些是一階謂詞，那么P為二階謂詞；二階以上遞推。本門課程僅研究一階謂詞11/44量詞使用前面介紹的謂詞和個(gè)體變元，還不足以描述自然界的所有命題。例：描述命題“所有的正整數(shù)都大于0”以及命題“有些正整數(shù)是素?cái)?shù)”。量詞的引入：量詞指在命題里表示數(shù)量的詞。12/44全稱量詞符號“(x)P(x) ”表示命題：“對于個(gè)體域中所有個(gè)體x，謂詞P(x)均為T”。其中“(x)”叫作全稱量詞，讀作“對于所有的x”。謂詞P(x)稱為全稱量詞的轄域或作用范圍。 例如： 所有的人都是要死的 令D(x)：x 是要死的。則命題可表示為 x D(x)取個(gè)體域?yàn)槿w人的集合，是真命題。所有的正整數(shù)都是素?cái)?shù)；令 P(

6、x)：x 是素?cái)?shù)則命題可表示成 x P(x)取個(gè)體域?yàn)檎麛?shù)集，是假命題。13/44存在量詞符號“( x)P(x) ”表示命題：“在個(gè)體域中存在某些個(gè)體使謂詞P(x)為T”其中“( x)”叫作存在量詞，讀作“存在x”。謂詞P(x)稱為存在量詞的轄域或作用范圍。 例如： 有些正整數(shù)是素?cái)?shù)；令 P(x)：x 是素?cái)?shù)則命題可表示成 x P(x)取個(gè)體域?yàn)檎麛?shù)集，是真命題。13/44存在唯一量詞 !符號“(! x)P(x) ”表示命題：“在個(gè)體域中存在唯一的一個(gè)個(gè)體使謂詞P(x)為T”其中“(! x)”叫作存在唯一量詞，讀作“恰有一個(gè)x”。謂詞P(x)稱為存在唯一量詞的轄域或作用范圍。 例如： 存在

7、唯一的質(zhì)數(shù)是偶數(shù)；令 P(x)：x 是偶數(shù)則命題可表示成 ! x P(x)取個(gè)體域?yàn)橘|(zhì)數(shù)集合，是真命題。14/44量詞量詞本身不是一個(gè)獨(dú)立的邏輯概念，可以用,聯(lián)結(jié)詞取代。設(shè)個(gè)體域 S: S= a1,a2,an ,謂詞可以表示成以下形式： (x)A(x)A(a1) A(a2) A(an) ( x)A(x)A(a1) A(a2) A(an) ( !x)A(x) ( x)(A(x) (y)(A(y) x=y)由量詞確定的命題真值與個(gè)體域有關(guān)。令 P(x)：x 是素?cái)?shù)則 x P(x)，如果取個(gè)體域?yàn)樗財(cái)?shù)集，為真；如果個(gè)體域?yàn)檎麛?shù)集，為假。15/44量詞為了方便起見，個(gè)體域一律用全總個(gè)體域，每個(gè)個(gè)體變元

8、的真正變化范圍則用一個(gè)特性謂詞來刻劃。 注意：對于全稱量詞應(yīng)使用單條件邏輯聯(lián)結(jié)詞；對于存在量詞應(yīng)使用邏輯聯(lián)結(jié)詞合取。 R(x): x是自然數(shù)；P(x): x大于0. (x)(R(x)P(x) ( x)(R(x) P(x)以后不加強(qiáng)調(diào)個(gè)體域均指全總個(gè)體域16/44量詞全稱量詞和存在量詞不僅可以單獨(dú)出現(xiàn)，還可以組合形式出現(xiàn)。對于二元謂詞P(x,y)，可能有以下幾種量化的可能： 17/44組合量詞的含義設(shè)A(x,y)表示x,y同姓， x的個(gè)體域是1班同學(xué)，y的個(gè)體域是2班同學(xué)。(x) (y)A(x,y) ：1班任何一個(gè)同學(xué)與2班的所有同學(xué)同姓；(y) (x) A(x,y) ：2班任何一個(gè)同學(xué)與1班的

9、所有同學(xué)同姓； (x) ( y)A(x,y) ：對1班的任意一個(gè)同學(xué)，2班都有人跟他同姓； ( y) (x)A(x,y) ：存在一個(gè)2班同學(xué)和1班的所有同學(xué)同姓。翻譯時(shí)從左向右18/44合式謂詞公式若P為不能再分解的n元謂詞變元，x1, x2,xn是個(gè)體變元，則稱P(x1, x2,xn)為原子公式或原子謂詞公式。當(dāng)n=0時(shí)， P表示命題變元即原子命題公式。所以，命題邏輯實(shí)際上是謂詞邏輯的特例。 由原子謂詞公式出發(fā)，通過命題聯(lián)結(jié)詞，可以組成復(fù)合謂詞公式，叫分子謂詞公式。19/44合式謂詞公式定義：（1）原子謂詞公式是合式的公式；（2）若A是合式的公式，則 A也是合式的公式；（3）若A和B都是合式

10、的公式，則A B, A B, A B,A B 也都是合式的公式；（4） 如果A是合式的公式，x是任意變元，且A中無(x)或( x)出現(xiàn)，則(x)A(x)和( x)A(x)都是合式的公式；（5）當(dāng)且僅當(dāng)有限次使用規(guī)則（1）（4）由邏輯聯(lián)結(jié)詞、圓括號構(gòu)成的有意義的字符串是合式的公式。20/44自由變元和約束變元在謂詞公式中，如果有形如(x)A(x)或者( x)A(x) ，則稱它們是x的約束部分。每個(gè)量詞后面的最短公式，稱為量詞的轄域。約束變元：一個(gè)變元若出現(xiàn)在包含這個(gè)變元的量詞(全稱量詞或存在量詞)的轄域之內(nèi)，則該變元稱為約束變元，其出現(xiàn)稱為約束出現(xiàn)。 自由變元：變元的非約束出現(xiàn)叫作自由出現(xiàn)，該變

11、元叫作自由變元。 21/44自由變元和約束變元例：說明以下各式量詞的轄域與變元的約束情況。22/44自由變元和約束變元從約束變元的概念可知，謂詞P(x)的量化，就是從變元x的整個(gè)個(gè)體域著眼，對性質(zhì)P(x)所作的一個(gè)全稱判斷或特稱判斷。其結(jié)果是將謂詞變成一個(gè)命題。因此，(x) 和( x) 可以看成消元運(yùn)算。對n元謂詞P(x1, x2,xn)量化后，假設(shè)有k個(gè)自由變元，則降為k元謂詞。二元謂詞一元謂詞23/44自由變元和約束變元一般情況下給定一個(gè)謂詞公式A(x)，僅表明在該公式中只有一個(gè)自由變元，但并不限制在該公式中還存在若干約束變元。 以下各式都可以寫成A(x)：24/44謂詞公式的解釋在命題邏

12、輯中對一個(gè)公式的解釋，是對每個(gè)命題變元進(jìn)行取值指派，如果公式有n個(gè)變元，則有2n種解釋。謂詞公式的解釋，涉及到命題變元、謂詞變元、個(gè)體變元、符號函數(shù)真值表法不可行25/44謂詞公式的解釋定義：設(shè)A的個(gè)體域是D，如果用一組謂詞常量、命題常量和A中的個(gè)體及函數(shù)符號（將它們簡記為I）代換公式A中相應(yīng)的變元，則該公式A轉(zhuǎn)化成一個(gè)命題，可以確定其真值（記作P）。稱I為公式A在D中的解釋（或指派），稱P為公式A關(guān)于解釋I的真值。永真永假可滿足 26/44謂詞公式的解釋給定兩個(gè)謂詞公式A和B，D是它們共同的個(gè)體域，若AB在D中是永真式，則稱遍及D有AB ；若D是全總個(gè)體域，則稱AB;若AB且B A，則稱AB

13、 。命題邏輯中的恒等式和永真蘊(yùn)含式全部可以推廣到謂詞邏輯中。27/44含有量詞的等價(jià)式和永真蘊(yùn)含式量詞轉(zhuǎn)換律例：設(shè)P(x)：x今天來上課。 選修史老師離散數(shù)學(xué)的全體同學(xué)。 (x)(P(x) ：所有同學(xué)今天都來上課了。 (x)(P(x) ：不是所有人今天都來上課了。( x) P (x) ：今天有人沒有來上課。 (x)(P(x) ( x) P (x) ( x) P (x) ：有人今天來上課了。 ( x) P (x) ：沒有人今天來上課。 (x)(P(x) ：所有的人今天都沒有來上課。 (x)(P(x) (x) P (x) 28/44量詞轉(zhuǎn)換律 （其中A(x)是任意的公式） 證明 設(shè)個(gè)體域 ,則29

14、/44量詞轄域擴(kuò)張及收縮律證明：僅對第一個(gè)式子證明，其余類推。30/44量詞分配律全稱量詞對滿足分配律，存在量詞對滿足分配律。證明：僅證明第一個(gè)式子。31/44量詞分配律全稱量詞對，存在量詞對 不滿足分配律。例：個(gè)體域是人的集合。 A(x)：x是女人。 B(x)：x是男人。 (x)( A(x) B (x)為真； (x) A(x) (x) B (x) 為假。 ( x)( A(x) B (x)為假. ( x) A(x) ( x) B (x)為真。 僅滿足：為正確理解上面第二式。設(shè)A(x) :x會用左手拿筷子吃飯B(x): x會用右手拿筷子吃飯32/44重要等價(jià)式和永真蘊(yùn)含式33/44重要等價(jià)式和永

15、真蘊(yùn)含式34/44重要等價(jià)式和永真蘊(yùn)含式35/44量詞交換式36/44記憶規(guī)律37/44謂詞公式的翻譯38/44謂詞公式的翻譯任何整數(shù)都是實(shí)數(shù)。P(x)：x是整數(shù)；Q(x)：x是實(shí)數(shù)。 符號化為：沒有不犯錯(cuò)誤的人。P(x)：x是人；Q(x)：x犯錯(cuò)誤。符號化為：或符號化為：39/44謂詞公式的翻譯有一個(gè)大于10的偶數(shù)。P(x)：x10；Q(x)：x是偶數(shù)。 符號化為：每個(gè)學(xué)生都要鍛煉身體。P(x)：x是學(xué)生；Q(x)：x鍛煉身體。符號化為：不能符號化為：40/44有的獅子不愛喝咖啡。P(x)：x是獅子；Q(x)：x愛喝咖啡。 符號化為：不能符號化為：41/44謂詞公式的翻譯不管黑貓白貓，抓住老鼠就是好貓。P(x)：x是黑貓。Q(x)：x