第四章謂詞邏輯的基本概念

1、第四章 謂詞邏輯的基本概念l在命題邏輯中，是把簡(jiǎn)單命題作為基在命題邏輯中，是把簡(jiǎn)單命題作為基本單元或說作為原子來看待的，不再本單元或說作為原子來看待的，不再對(duì)簡(jiǎn)單命題的內(nèi)部結(jié)構(gòu)進(jìn)行分析對(duì)簡(jiǎn)單命題的內(nèi)部結(jié)構(gòu)進(jìn)行分析l謂詞邏輯引入謂詞和量詞對(duì)簡(jiǎn)單命題謂詞邏輯引入謂詞和量詞對(duì)簡(jiǎn)單命題做了進(jìn)一步剖析。做了進(jìn)一步剖析。l約定以小寫字母表示約定以小寫字母表示命題、函數(shù)命題、函數(shù)，而，而以大寫字母來表示以大寫字母來表示謂詞謂詞l所介紹的內(nèi)容限于一階謂詞邏輯或稱所介紹的內(nèi)容限于一階謂詞邏輯或稱狹謂詞邏輯狹謂詞邏輯4.1 謂詞和個(gè)體詞4ll 謂詞的描述性定義l例例 張三是學(xué)生李四是學(xué)生張三是學(xué)生李四是學(xué)生1.1

2、.在命題邏輯里，這是兩個(gè)不同的命題，在命題邏輯里，這是兩個(gè)不同的命題， 只能分別以兩個(gè)不同的符號(hào)表示只能分別以兩個(gè)不同的符號(hào)表示2.2.然而然而它們都有主詞和謂詞它們都有主詞和謂詞。主詞。主詞“張三張三”、“李四李四”不同不同謂詞謂詞“是學(xué)生是學(xué)生”是是相同相同的若以大寫符號(hào)的若以大寫符號(hào)P P表示表示“是學(xué)生是學(xué)生”，便可，便可把這兩個(gè)命題分別寫成把這兩個(gè)命題分別寫成P(P(張三張三) ) 和和P(P(李李四四) )3.3.自然一般地可引入變量自然一般地可引入變量x x來表示主詞，來表示主詞，于是符號(hào)于是符號(hào)P(xP(x) )就表示就表示“x x是學(xué)生是學(xué)生”通常通常把把P(xP(x) )稱

3、作謂詞稱作謂詞一元謂詞描述性定義：一元謂詞描述性定義：在一個(gè)命題里，在一個(gè)命題里，如果主詞只有一個(gè)，這時(shí)表示該主詞如果主詞只有一個(gè)，這時(shí)表示該主詞性質(zhì)或?qū)傩缘脑~便稱作謂詞這是一性質(zhì)或?qū)傩缘脑~便稱作謂詞這是一元元( (目目) )謂詞，以謂詞，以P(x)P(x)，Q(x)Q(x)，表表示示多元謂詞描述性定義：多元謂詞描述性定義：在一個(gè)命題里，在一個(gè)命題里，如果主詞多于一個(gè)，那么表示這幾個(gè)如果主詞多于一個(gè)，那么表示這幾個(gè)主詞間的關(guān)系的詞稱作謂詞這是多主詞間的關(guān)系的詞稱作謂詞這是多元謂詞，以元謂詞，以P(xP(x，y)y)，Q(xQ(x，y)y)，R(xR(x，y y，z)z)，表示表示n如如“張三和

4、李四是兄弟張三和李四是兄弟”其中其中“是兄弟是兄弟”是是謂詞謂詞“5 5大于大于3”3”其中其中“大于大于”是謂詞是謂詞“張三比李四高張三比李四高”其中其中“比比高高”是謂是謂詞詞“天津位于北京的東南天津位于北京的東南”其中其中“位于位于東南東南”是謂詞是謂詞“A A在在B B上上”其中其中“在在上上”是謂詞是謂詞4.1.2 4.1.2 個(gè)體詞個(gè)體詞 l 個(gè)體詞個(gè)體詞( (主詞主詞) ): :個(gè)體常項(xiàng)、個(gè)體變項(xiàng)個(gè)體常項(xiàng)、個(gè)體變項(xiàng)l 謂詞謂詞: :謂詞常項(xiàng)、謂詞變項(xiàng)謂詞常項(xiàng)、謂詞變項(xiàng)l 個(gè)體詞的變化范圍個(gè)體詞的變化范圍：個(gè)體域：個(gè)體域( (論域論域) )。約定謂詞邏。約定謂詞邏輯的個(gè)體域除明確指

5、明外，都認(rèn)為是包括一切事輯的個(gè)體域除明確指明外，都認(rèn)為是包括一切事物的一個(gè)最廣的集合以物的一個(gè)最廣的集合以D D表示表示l 謂詞的變化范圍謂詞的變化范圍: :不做特別聲明時(shí)，指一切關(guān)系不做特別聲明時(shí)，指一切關(guān)系或一切性質(zhì)的集合或一切性質(zhì)的集合l 同一謂詞在不同論域下的描述形式可能不同，所同一謂詞在不同論域下的描述形式可能不同，所取的真假值也可能不同取的真假值也可能不同4.1.3 4.1.3 謂詞的抽象定義謂詞的抽象定義 l 將謂詞視作為一個(gè)個(gè)體的性質(zhì)或多個(gè)個(gè)體間的將謂詞視作為一個(gè)個(gè)體的性質(zhì)或多個(gè)個(gè)體間的關(guān)系還可進(jìn)一步關(guān)系還可進(jìn)一步抽象地定義抽象地定義: :謂詞是給定的個(gè)體域到集合謂詞是給定的個(gè)

6、體域到集合T T，F(xiàn) F上的一個(gè)上的一個(gè)映射映射l 還需說明，一般地說謂詞還需說明，一般地說謂詞P(X)P(X)，Q(xQ(x，y)y)是命是命題形式而不是命題題形式而不是命題不可能直接確定取真還是不可能直接確定取真還是取假，僅當(dāng)謂詞變項(xiàng)取定為某個(gè)謂詞常項(xiàng)，并取假，僅當(dāng)謂詞變項(xiàng)取定為某個(gè)謂詞常項(xiàng)，并且個(gè)體詞取定為個(gè)體常項(xiàng)時(shí)，命題形式才化為且個(gè)體詞取定為個(gè)體常項(xiàng)時(shí)，命題形式才化為命題命題4.1.4 4.1.4 謂詞邏輯與命題邏輯謂詞邏輯與命題邏輯l 可認(rèn)為謂詞邏輯是命題邏輯的推廣可認(rèn)為謂詞邏輯是命題邏輯的推廣因?yàn)槿我幻驗(yàn)槿我幻}都可通過引入具有相應(yīng)含義的謂詞題都可通過引入具有相應(yīng)含義的謂詞(

7、(個(gè)體詞視為個(gè)體詞視為常項(xiàng)常項(xiàng)) )來表示，或認(rèn)為一個(gè)命題是沒有個(gè)體變?cè)膩肀硎?，或認(rèn)為一個(gè)命題是沒有個(gè)體變?cè)牧阍^詞零元謂詞l 命題邏輯中的很多概念。規(guī)則都可推廣到謂詞邏命題邏輯中的很多概念。規(guī)則都可推廣到謂詞邏輯中延用，如輯中延用，如聯(lián)結(jié)詞可照搬到謂詞邏輯聯(lián)結(jié)詞可照搬到謂詞邏輯，無需再，無需再做說明，有的等值式推理式也可移植到謂詞邏輯做說明，有的等值式推理式也可移植到謂詞邏輯4.2 4.2 函數(shù)和量詞函數(shù)和量詞4.2.1 4.2.1 函數(shù)函數(shù)l 約定函數(shù)符號(hào)用小寫字母表示，如約定函數(shù)符號(hào)用小寫字母表示，如f f，g g，fatherfather，l 函數(shù)可以嵌入在謂詞中，但不能單獨(dú)使用函

8、數(shù)可以嵌入在謂詞中，但不能單獨(dú)使用如如函數(shù)函數(shù)father(x)father(x)表示表示x x的父親，若謂詞的父親，若謂詞P(x)P(x)表表示示x x是教師，則是教師，則P(father(x)P(father(x)就表示就表示x x的父親是的父親是教師當(dāng)教師當(dāng)x x的取值確定后，的取值確定后，P(father(x)P(father(x)的值或的值或?yàn)檎婊驗(yàn)榧贋檎婊驗(yàn)榧儆秩缬秩纭皬埲母赣H和母親是夫妻張三的父親和母親是夫妻”可描述成可描述成MARRIED(father(MARRIED(father(張三張三) )，mother(mother(張三張三)其中謂其中謂詞詞MARRIED(xMAR

9、RIED(x，y)y)表示表示x x和和y y是夫妻，而是夫妻，而father(x)father(x)，mother(x)mother(x)是函數(shù)是函數(shù)4.2.2 4.2.2 量詞量詞全稱量詞全稱量詞l 例子：例子：“凡事物都是運(yùn)動(dòng)的凡事物都是運(yùn)動(dòng)的”。這命題中的。這命題中的“凡凡” ” 是表示個(gè)體變?cè)獢?shù)量的詞，是表示個(gè)體變?cè)獢?shù)量的詞，“凡凡”的等義詞有的等義詞有“所有的所有的”、“切的切的”、“任任個(gè)個(gè)”、“每一每一個(gè)個(gè)”，它是全稱量詞。，它是全稱量詞。l 符號(hào)符號(hào): :( ( x x) )讀作所有的讀作所有的x x或任一或任一x x，一切，一切x x而而 就就稱為全稱量詞，它所約束的個(gè)體是

10、稱為全稱量詞，它所約束的個(gè)體是x xl 定義：定義：命題命題( ( x x)P(x)P(x)當(dāng)且僅當(dāng)對(duì)論域中的所有當(dāng)且僅當(dāng)對(duì)論域中的所有x x來說，來說，P(x)P(x)均為真時(shí)方為真這就是全稱量詞的均為真時(shí)方為真這就是全稱量詞的定義定義( ( x x)P(x)P(x)也寫為也寫為( ( x x)(P(x)(P(x)注意注意( ( x x)(P(x)(P(x) Q(x)Q(x) ( ( x x)P(x)P(x) Q(x)Q(x)量詞的運(yùn)算優(yōu)先級(jí)高于邏輯聯(lián)結(jié)詞量詞的運(yùn)算優(yōu)先級(jí)高于邏輯聯(lián)結(jié)詞l 性質(zhì)性質(zhì): :( ( x x)P(x)P(x)F F成立，當(dāng)且僅當(dāng)有一個(gè)成立，當(dāng)且僅當(dāng)有一個(gè)x x0 0

11、 D D ，使使P(xP(x0 0 D D) )F F存在量詞存在量詞 例子：例子：“有的事物是動(dòng)物有的事物是動(dòng)物”。這命題中。這命題中“有的有的”就是就是表示個(gè)體變?cè)獢?shù)量的詞，表示個(gè)體變?cè)獢?shù)量的詞，“有的有的”的等義詞有的等義詞有“存在存在一個(gè)一個(gè)”、“有一個(gè)有一個(gè)”、“有些有些”它是存在量詞。它是存在量詞。 符號(hào)符號(hào): :( ( x x) )讀作至少有一個(gè)讀作至少有一個(gè)x x或存在或存在個(gè)個(gè)x x或有某些或有某些x x而而 就是對(duì)個(gè)體詞起約束作用的存在量詞，所約就是對(duì)個(gè)體詞起約束作用的存在量詞，所約束的變?cè)鞘淖冊(cè)莤.x.l 定義：定義：命題命題( ( x x)Q(x)Q(x)當(dāng)且僅當(dāng)

12、在論域中至少有一個(gè)當(dāng)且僅當(dāng)在論域中至少有一個(gè)x x0 0，Q ( xQ ( x0 0) ) 為 真 時(shí) 方 為 真 這 就 是 存 在 量 詞 的 定為 真 時(shí) 方 為 真 這 就 是 存 在 量 詞 的 定義義( ( x x)Q(x)Q(x)也寫為也寫為( ( x x)(Q(x)(Q(x)注意注意( ( x x)(P(x)(P(x) Q(x)Q(x) ( ( x x)P(x)P(x) Q(x)Q(x)l 性質(zhì)性質(zhì): :( ( x x)Q(x)Q(x)F F當(dāng)且僅當(dāng)對(duì)所有的當(dāng)且僅當(dāng)對(duì)所有的x x D D都有都有Q(x)Q(x)F F4.2.2 4.2.2 約束變?cè)妥杂勺冊(cè)s束變?cè)妥杂勺冊(cè)?

13、. 約束變?cè)c自由變?cè)s束變?cè)c自由變?cè)猯 在一個(gè)含有量詞的命題形式里，區(qū)分個(gè)體詞在一個(gè)含有量詞的命題形式里，區(qū)分個(gè)體詞受量詞的約束還是不受量詞的約束是重要受量詞的約束還是不受量詞的約束是重要的的l 若若P(x)P(x)表示表示x x是有理數(shù)，這時(shí)的變?cè)怯欣頂?shù)，這時(shí)的變?cè)獂 x不受任不受任何量詞約束，便稱是何量詞約束，便稱是自由的自由的而而( ( x)P(x)x)P(x)中中的的兩處出現(xiàn)的兩處出現(xiàn)的變?cè)冊(cè)獂 x都受量詞都受量詞 的約束，便稱的約束，便稱作作約束變?cè)s束變?cè)?，受約束的變?cè)卜Q被量詞量化，受約束的變?cè)卜Q被量詞量化了的變?cè)说淖冊(cè)猯 例：命題形式例：命題形式( ( x)P(x)

14、x)P(x) Q(y)Q(y)中，變?cè)校冊(cè)獂 x是約是約束的，而變?cè)模冊(cè)獃 y是自由的是自由的2. 2. 量詞的轄域量詞的轄域l 量詞所約束的命題范圍稱為量詞的轄域如量詞所約束的命題范圍稱為量詞的轄域如x的轄域y)是y)P(x,(y)的轄域，y)是(y)中，P(x,y)P(x,x)(x)的轄域。y)是(y)中，R(x,x)R(x,(3. 3. 變?cè)酌?guī)則變?cè)酌?guī)則( ( x x)P(x)= )P(x)= ( ( y y)P(y)P(y)4.3 4.3 合式公式合式公式l 目的：目的：像命題邏輯一樣，需限定所討論的命題形像命題邏輯一樣，需限定所討論的命題形式的范圍，由于謂詞邏輯里

15、引入了個(gè)體詞、量詞，式的范圍，由于謂詞邏輯里引入了個(gè)體詞、量詞，從而帶來了復(fù)雜性從而帶來了復(fù)雜性l 一階而不是高階謂詞邏輯：一階而不是高階謂詞邏輯：限定量詞僅作用于個(gè)限定量詞僅作用于個(gè)體變?cè)?，不允許量詞作用于命題變項(xiàng)和謂詞變項(xiàng)，體變?cè)?，不允許量詞作用于命題變項(xiàng)和謂詞變項(xiàng)，也不討論謂詞的謂詞也不討論謂詞的謂詞不考慮下述公式不考慮下述公式( p)(Q(x)p)量詞作用于命題量詞作用于命題p( Q)(Q(x) P(x)量詞作用于謂詞量詞作用于謂詞Q(x)合式公式新定義合式公式新定義基本基本( (納入謂詞納入謂詞( (函數(shù)可嵌入函數(shù)可嵌入)：(1)(1)命題常項(xiàng)、命題命題常項(xiàng)、命題變項(xiàng)和變項(xiàng)和原子謂詞

16、公式原子謂詞公式( (不含聯(lián)結(jié)詞的謂詞不含聯(lián)結(jié)詞的謂詞) )都是合都是合式公式式公式( (函數(shù)嵌入？函數(shù)嵌入？) )聯(lián)結(jié)詞：聯(lián)結(jié)詞：(2)(2)如果如果A A是合式公式，則是合式公式，則A A也是合式公也是合式公式式聯(lián)結(jié)詞：聯(lián)結(jié)詞：(3)(3)如果如果A A，B B是合式公式，而無變?cè)呛鲜焦?，而無變?cè)獂 x在在A A，B B的一個(gè)中是約束的而在另一個(gè)中是自由的，則的一個(gè)中是約束的而在另一個(gè)中是自由的，則(AB)(AB)，(AB)(AB)，(A(AB)B)，(A (A B)B)也是合式公也是合式公式式( (最外層括號(hào)可省略最外層括號(hào)可省略) )量詞：量詞：(4)(4)如果如果A A是合式公式

17、，而是合式公式，而x x在在A A中是自由變?cè)惺亲杂勺冊(cè)?，則則( ( x)Ax)A，( ( x)Ax)A也是合式公式也是合式公式協(xié)調(diào)：協(xié)調(diào)：(5)(5)只有有限次應(yīng)用以上只有有限次應(yīng)用以上4 4條構(gòu)成的符號(hào)串才條構(gòu)成的符號(hào)串才是合式公式是合式公式判斷一個(gè)公式是否為合式公式判斷一個(gè)公式是否為合式公式合式公式：合式公式： p, p, P(x,y)P(x,y)Q(y), (Q(y), ( x)(A(x)x)(A(x)B(x),B(x),( ( x)(A(x)x)(A(x)( ( y)B(x,y)y)B(x,y)非合式公式：非合式公式：( ( x)F(x)G(x),x)F(x)G(x),違反第三條

18、違反第三條( ( x)(x)( x)F(x),x)F(x),違反第四條違反第四條( ( x)P(y)x)P(y)違反第四條違反第四條4.4 4.4 自然語句的形式化自然語句的形式化使用謂詞邏輯描述以自然語句表達(dá)的問題，使用謂詞邏輯描述以自然語句表達(dá)的問題，首先要將問題分解成一些原子謂詞，引入謂首先要將問題分解成一些原子謂詞，引入謂詞符號(hào)，進(jìn)而使用量詞、函數(shù)、聯(lián)結(jié)詞來構(gòu)詞符號(hào)，進(jìn)而使用量詞、函數(shù)、聯(lián)結(jié)詞來構(gòu)成合式公式。成合式公式。一、四個(gè)典型例子4.4.1 “所有的有理數(shù)都是實(shí)數(shù)”的形式化l 若以若以P(x)P(x)表示表示x x是有理數(shù)，是有理數(shù)，Q(x)Q(x)表示表示x x是實(shí)數(shù)，是實(shí)數(shù)，

19、這句話的形式描述應(yīng)為這句話的形式描述應(yīng)為( ( x)(P(x)x)(P(x)Q(x)Q(x)l “所有的所有的都是都是”，這類語句的形式描，這類語句的形式描述只能使用述只能使用而不能使用而不能使用. 當(dāng)當(dāng)P(x)P(x)與與Q(x)Q(x)為為此例中的謂詞常項(xiàng)時(shí)，上式真值與論域無關(guān)。此例中的謂詞常項(xiàng)時(shí)，上式真值與論域無關(guān)。4.4.2 “有的實(shí)數(shù)是有理數(shù)”的形式化l 以以P(x)P(x)表表x x是有理數(shù)，是有理數(shù)，Q(x)Q(x)表示表示x x是實(shí)數(shù)，這句是實(shí)數(shù)，這句話的形式描述應(yīng)為話的形式描述應(yīng)為( ( x)(P(x)Q(x)x)(P(x)Q(x)l 這類語句的形式描述只能使用這類語句的形式

20、描述只能使用而不能使用而不能使用. .按通常認(rèn)識(shí)，按通常認(rèn)識(shí)，其真值與論域有關(guān)。其真值與論域有關(guān)。設(shè)論域設(shè)論域D D1 1=e=e，張三，桌子，張三，桌子 ，則上述命題為假。僅當(dāng)則上述命題為假。僅當(dāng)D D1 1中中有有理數(shù)時(shí)上述命題方為真有有理數(shù)時(shí)上述命題方為真4.4.3 “沒有無理數(shù)是有理數(shù)”的形式化l 若以若以A(x)A(x)表示表示x是無理數(shù)，是無理數(shù)， B(x)B(x)表示表示x是有理是有理數(shù)，這句話的形式描述為數(shù)，這句話的形式描述為 ( ( x)(A(x)B(x) (x)(A(x)B(x) (比照比照4.4.2)4.4.2)l 由摩根律，上式等價(jià)于由摩根律，上式等價(jià)于( (比照比照4

21、.4.1)4.4.1)()()()()()(xAxBxxBxAx證明證明( (注意論域相同注意論域相同) ) ( ( x)(A(x)B(xx)(A(x)B(x)= = ( ( x)(x)( A(x)A(x)B(xB(x)= = ( ( x)(A(x)x)(A(x)B(xB(x)= (= ( x)(B(x)x)(B(x)A(xA(x)4.4.4 “有的實(shí)數(shù)不是有理數(shù)”的形式化l 若以若以A(x)A(x)表示表示x x是實(shí)數(shù)，是實(shí)數(shù)，B(x)B(x)表示表示x x是有理數(shù)，是有理數(shù)，那么這句話可形式描述為那么這句話可形式描述為)()()(xBxAx二、二、4.4.5 4.4.5 自然數(shù)集的三條公理

22、的形式描述自然數(shù)集的三條公理的形式描述l 論域是自然數(shù)集論域是自然數(shù)集，來形式化語句，來形式化語句(1)(1)對(duì)每個(gè)數(shù)，有且僅有一個(gè)相繼后元，對(duì)每個(gè)數(shù)，有且僅有一個(gè)相繼后元，(2)(2)沒有這樣的數(shù)，沒有這樣的數(shù)，O O是其相繼后元是其相繼后元(3)(3)對(duì)除對(duì)除O O而外的數(shù)，有且僅有一個(gè)相繼前元而外的數(shù)，有且僅有一個(gè)相繼前元( (可將可將這三句話作為建立自然數(shù)集合的公理這三句話作為建立自然數(shù)集合的公理) )l 準(zhǔn)備工作準(zhǔn)備工作: :引入謂詞引入謂詞E(x,y)E(x,y)表示表示x xy y，引入函數(shù)引入函數(shù)f(x)f(x)表示個(gè)體表示個(gè)體x x的相繼后元，即的相繼后元，即f(x)=x+1

23、f(x)=x+1引入函引入函數(shù)數(shù)g(x)g(x)表示個(gè)體表示個(gè)體x x的相繼前元，即的相繼前元，即g(x)g(x)x-1.x-1.n對(duì)語句對(duì)語句1 1需注意需注意存在性和唯一性的描述存在性和唯一性的描述: :即對(duì)每個(gè)即對(duì)每個(gè)x x都存在都存在y y，y y是是x x的相繼后元的相繼后元; ;且對(duì)且對(duì)任一任一z z，如果它也是，如果它也是x x的相繼后元，那么的相繼后元，那么y y，z z必相等必相等),()(,()()(,()()(zyExfzEzxfyEyxl語句語句2 2的描述是簡(jiǎn)單的，可寫成的描述是簡(jiǎn)單的，可寫成 對(duì)語句對(duì)語句3 3需注意的是對(duì)需注意的是對(duì)“除除0 0而外而外”的描的描述

24、，可理解為如果述，可理解為如果x x00則則的形式，的形式，于是語句于是語句3 3可描述為可描述為)(, 0()(xfEx),()(,()()(,()() 0 ,()(zyExgzEzxgyEyxEx三、三、4.4.6 4.4.6 三例不等三例不等)()()()()()()(xBxxAxxBxAx)()()()()()()(xBxxAxxBxAx)()()()()()()(xBxxAxxBxAx四、三個(gè)有趣的例子四、三個(gè)有趣的例子4.4.7 4.4.7 積木世界的形式描述積木世界的形式描述如圖所示三塊積木如圖所示三塊積木A A，B B，C C放在桌子上放在桌子上相對(duì)位置可如下描述：相對(duì)位置可如

25、下描述：ON(CON(C，A) A) 表示表示C C在在A A上，上，ONTABLE(A) ONTABLE(A) 表示表示A A在桌子上在桌子上ONTABLE(B) ONTABLE(B) 表示表示B B在桌子上，在桌子上，CLEAR(C) CLEAR(C) 表示表示C C上無積木塊上無積木塊CLEAR(B) CLEAR(B) 表示表示B B上無積木塊上無積木塊表示，對(duì)任一表示，對(duì)任一x x，如果，如果x x上無積木，那么沒有上無積木，那么沒有y y在在x x上，這表明了謂詞上，這表明了謂詞CLEARCLEAR，ONON的關(guān)系的關(guān)系),()()()(xyONyxCLEARx4.4.8 4.4.8

26、 一段話的形式描述一段話的形式描述l “張三在計(jì)算機(jī)系工作，李四是計(jì)算機(jī)系的領(lǐng)張三在計(jì)算機(jī)系工作，李四是計(jì)算機(jī)系的領(lǐng)導(dǎo)人員如果導(dǎo)人員如果y y在計(jì)算機(jī)系工作，而在計(jì)算機(jī)系工作，而z z是計(jì)算機(jī)是計(jì)算機(jī)系的領(lǐng)導(dǎo)，那么系的領(lǐng)導(dǎo)，那么z z是是y y的上級(jí)的上級(jí)”這段話的形式描這段話的形式描述為述為WORKS-IN(WORKS-IN(計(jì)算機(jī)系，張三計(jì)算機(jī)系，張三) )MANAGER(MANAGER(計(jì)算機(jī)系，李四計(jì)算機(jī)系，李四) ),(),(),(zyOFBOSSzMANAGERyINWORKS計(jì)算機(jī)系計(jì)算機(jī)系4.4.9 4.4.9 “函數(shù)函數(shù)f(x)f(x)在在aa，bb上的點(diǎn)上的點(diǎn)x x。處連續(xù)

27、。處連續(xù)”的形式描的形式描述述)| |) )f(xf(x|f(x)|f(x)| |x xx xx)(|x)(|( (0 0)()( (0 0)()( (0 00 0五、五、4.4.10 4.4.10 對(duì)謂詞變?cè)啻瘟炕姆治鰧?duì)謂詞變?cè)啻瘟炕姆治鲈O(shè)設(shè)P(xP(x，y)y)是二元謂詞，對(duì)兩個(gè)變?cè)牧炕傻檬嵌^詞，對(duì)兩個(gè)變?cè)牧炕傻? 4種形式種形式(1)注意注意 x x和和 y y可交換可交換(2)注意注意 x x和和 y y不可交換，不可交換，且且y y是是x x的函數(shù)的函數(shù)),()(),()(yxPyxyxPyx),()(),()(yxPyxyxPyx(3)注意注意 x x和和 y

28、y不可交換不可交換(4)注意注意 x x和和 y y可交換可交換),()(),()(yxPyxyxPyx),()(),()(yxPyxyxPyx自然語言形式化小結(jié)l這一節(jié)介紹了一些具體語句的形式化，都這一節(jié)介紹了一些具體語句的形式化，都具有一般性，特別是對(duì)具有一般性，特別是對(duì)“所有的所有的都都是是”，“有的有的是是”的形式描述的形式描述是最基本的格式是最基本的格式4.5 4.5 有限域下公式有限域下公式 的表示法的表示法l 今將論域限定為有限集，為方便又不失一般性，今將論域限定為有限集，為方便又不失一般性，用用1，2，k來代表，這時(shí)來重新認(rèn)識(shí)一下來代表，這時(shí)來重新認(rèn)識(shí)一下全稱量詞和存在量詞全稱

29、量詞和存在量詞)()(),()(xPxxPx4.5.1 4.5.1 論域?yàn)橛邢抻驎r(shí)的公式表示法論域?yàn)橛邢抻驎r(shí)的公式表示法)()2() 1 ()()()()2() 1 ()()(kPPPxPxkPPPxPx l 全稱量詞是合取詞的推廣全稱量詞是合取詞的推廣有限域下，就化成有限域下，就化成了由合取詞描述的命題邏輯的公式了由合取詞描述的命題邏輯的公式在任意域在任意域下，全稱量詞的作用下，全稱量詞的作用“相當(dāng)于相當(dāng)于”無限個(gè)合取詞的無限個(gè)合取詞的作用作用l 同樣，同樣，存在量詞乃是析取詞的推廣存在量詞乃是析取詞的推廣有限域下有限域下就化成了由析取詞描述的命題邏輯的公式就化成了由析取詞描述的命題邏輯的公

30、式在在任意域下，存在量詞的作用任意域下，存在量詞的作用“相當(dāng)于相當(dāng)于”無限個(gè)析無限個(gè)析取詞的作用取詞的作用l 在無窮集在無窮集11，2 2，k k， 上上都是沒有定義的，不是合式公式因此一都是沒有定義的，不是合式公式因此一般地說，謂詞邏輯的公式不能轉(zhuǎn)換為命題般地說，謂詞邏輯的公式不能轉(zhuǎn)換為命題邏輯公式邏輯公式 P(k)P(2)P(1)P(k)P(2)P(1)4.5.2 4.5.2 在域在域11，22上多次量化公式上多次量化公式)2 , 2() 1 , 2()2 , 1 () 1 , 1 (), 2()(), 1 ()(),()()2 , 2() 1 , 2()2 , 1 () 1 , 1 ()

31、, 2()(), 1 ()(),()()2 , 2() 1 , 2()2 , 1 () 1 , 1 (), 2()(), 1 ()(),()()2 , 2() 1 , 2()2 , 1 () 1 , 1 (), 2()(), 1 ()(),()(PPPPyPyyPyyxPyxPPPPyPyyPyyxPyxPPPPyPyyPyyxPyxPPPPyPyyPyyxPyx),()(),()(yxPxyyxPyx注意上式右側(cè)含意：注意上式右側(cè)含意：x x是是y y的函數(shù)的函數(shù)4.5.3 4.5.3 域域11，22上謂詞公式的解釋上謂詞公式的解釋l 在已知的論域下，需對(duì)公式中所含的在已知的論域下，需對(duì)公式

32、中所含的命題變命題變項(xiàng)、自由個(gè)體變項(xiàng)、謂詞變項(xiàng)以及函數(shù)項(xiàng)、自由個(gè)體變項(xiàng)、謂詞變項(xiàng)以及函數(shù)給出給出一個(gè)具體的設(shè)定才構(gòu)成該公式的一個(gè)具體的設(shè)定才構(gòu)成該公式的一個(gè)解釋一個(gè)解釋I I，在在I I下該公式有確定的真值。下面在論域下該公式有確定的真值。下面在論域11，22上討論。上討論。例例1 1：需設(shè)定謂詞變項(xiàng)：需設(shè)定謂詞變項(xiàng)例例2 2：需設(shè)定謂詞變項(xiàng)：需設(shè)定謂詞變項(xiàng)例例3 3：需設(shè)定謂詞變項(xiàng)、函數(shù)、自由：需設(shè)定謂詞變項(xiàng)、函數(shù)、自由個(gè)體變項(xiàng)個(gè)體變項(xiàng)l不難看出，在不難看出，在般的論域般的論域D D上，一個(gè)謂上，一個(gè)謂詞公式解釋的個(gè)數(shù)是無限的，而且每個(gè)詞公式解釋的個(gè)數(shù)是無限的，而且每個(gè)解釋本身需設(shè)定的內(nèi)容也可理解為是無解釋本身需設(shè)定的內(nèi)容也可理解為是無限的，包括對(duì)限的，包括對(duì)P(1)P(1)，P(2),P(2),，f(1)f(1)，f(2)f(2)，的設(shè)定，的設(shè)定，4.6 4.6 公式的普遍有效性和判定問題公式的普遍有效性和判定問題l謂詞邏輯公式也可分為三類，一是普遍有謂詞邏輯公式也可分為三類，一是普遍有效公式、一是可滿足公式、一是不可滿足效公式、一是可滿足公式、一是不可滿足公式公式論域確定之后，論域確定之后，判別一個(gè)公式的普判