10謂詞邏輯.ppt

第二章謂詞邏輯 第十講 原因是三個(gè)原子命題不能把第1個(gè)命題和第2命題的共同屬性 人 表示出來(lái) 這就是命題邏輯的局限性 為了解決這個(gè)問(wèn)題需要引入謂詞邏輯的有關(guān)概念 蘇格拉底是人 所有 人 具有的共同屬性 死亡 他也應(yīng)該有 但在命題邏輯中無(wú)法實(shí)現(xiàn) 2 1謂詞邏輯的基本概念2 1 1謂詞及其表示命題是一個(gè)有唯一真值的陳述句 陳述句主要由主語(yǔ) 謂語(yǔ) 賓語(yǔ)和補(bǔ)語(yǔ)組成 其中主語(yǔ) 謂語(yǔ)是句子的主要成份 主語(yǔ)是謂語(yǔ)描述的對(duì)象 稱(chēng)為個(gè)體或客體 謂語(yǔ)用于描述主語(yǔ)的性質(zhì)和關(guān)系 是陳述句的主體部分 1 不管白貓黑貓 抓住老鼠就是好貓 2 鄭州在北京和廣州之間 3 王語(yǔ)嫣和慕容復(fù)是表兄妹 定義2 1可以獨(dú)立存在的具體或抽象的客體稱(chēng)為個(gè)體詞 定義2 2在謂詞邏輯中 刻劃個(gè)體性質(zhì)和相互之間的關(guān)系的詞稱(chēng)為謂詞 例2 1 張三是大學(xué)生 李四是大學(xué)生 我們用大寫(xiě)字母S表示 是大學(xué)生 用小寫(xiě)字母a b分別表示 張三 和 李四 上述兩個(gè)命題可表示為 S a 張三是大學(xué)生 S b 李四是大學(xué)生 謂詞可分為一元謂詞和多元謂詞 在命題中若謂詞只聯(lián)系一個(gè)客體 則稱(chēng)之為一元謂詞 一元謂詞表示客體的屬性 若謂詞聯(lián)系著n個(gè)客體 則稱(chēng)之為n元謂詞 多元謂詞表示客體之間的聯(lián)系 例2 2 1 冰比水密度小 2 4大于3解 用D表示 比 密度小 G表示 大于 則上述謂詞命題可以表示為 D 冰 水 和G 4 3 不難發(fā)現(xiàn) 在多元謂詞中 個(gè)體在謂詞中出現(xiàn)的次序不是任意的 它將直接影響謂詞命題的真值 在多元謂詞公式中 個(gè)體在謂詞公式出現(xiàn)的次序一旦約定就不能更改 如果更改便變成不同的命題 其真值也發(fā)生變化 如上例中改為D 水 冰 和G 3 4 變成命題 水比冰密度小 和 3大于4 其真值都為假 2 1 常元與變?cè)谥^詞邏輯中 表示特定個(gè)體的詞稱(chēng)為個(gè)體常元 個(gè)體常元可以是代表個(gè)體的標(biāo)識(shí)符 也可以直接引用個(gè)體的名稱(chēng) 如上述例2 1中a代表 張三 b代表 李四 在例2 2中直接使用個(gè)體的名稱(chēng) 如 水 冰 等 在謂詞邏輯中 用來(lái)表示抽象或泛指的個(gè)體的詞稱(chēng)為個(gè)體變?cè)?其標(biāo)識(shí)符常用小寫(xiě)字母x y z 表示 例如用 x 表示x是素?cái)?shù) Q x 表示x是有理數(shù) x 和Q x 不是命題 只有用具體的個(gè)體取代其中的個(gè)體變?cè)蟛攀敲} 才有真值 2 2命題函數(shù)及量化2 2 1命題函數(shù) 函項(xiàng) 單獨(dú)的謂詞不是命題 在謂詞后面的括號(hào)中填上代表個(gè)體的標(biāo)識(shí)符所得的式子稱(chēng)為謂詞填式 如果在謂詞填式的括號(hào)中填入的是個(gè)體常元 則該謂詞填式是一個(gè)命題 在謂詞填式的括號(hào)中填入的是個(gè)體變?cè)?則稱(chēng)該謂詞填式為命題函數(shù) 定義2 3由一個(gè)謂詞和一些個(gè)體變?cè)M成的表達(dá)式稱(chēng)為原子 簡(jiǎn)單 命題函數(shù) 用邏輯聯(lián)結(jié)詞把一個(gè)或多個(gè)原子命題函數(shù)連接而成的表達(dá)式稱(chēng)為復(fù)合命題函數(shù) 如上述所舉例子中S x D x y G x y 都是簡(jiǎn)單命題函數(shù) 其中x y為個(gè)體變?cè)?把不含個(gè)體變?cè)拿}函數(shù)稱(chēng)為0元謂詞 例如 上述的D 冰 水 和G 4 3 等都是0元謂詞 0元謂詞本身就是命題 命題邏輯中的原子命題都可以用0元謂詞表示 因此 可以將命題邏輯看成是謂詞邏輯的特殊情況 值得注意的是 在謂詞演算中邏輯聯(lián)結(jié)詞的含義與命題演算中完全相同 且命題演算中的公式在謂詞演算中完全適用 例2 3將下列命題符號(hào)化 1 存在既是素?cái)?shù)又是偶數(shù)的數(shù) 解 令 F x x是素?cái)?shù) G x x是偶數(shù) 則命題符號(hào)化為 F x G x 2 只有努力學(xué)習(xí)才能取得好成績(jī) 解 令 G x x想取得好成績(jī) H x x努力學(xué)習(xí) 則命題符號(hào)化為 3 在實(shí)數(shù)域中 若x比y大 y比大z 則x比z大 解 設(shè)x y z是實(shí)數(shù) 令 P x y x比y大 則命題符號(hào)化為 P x y P y z P x z 定義2 4個(gè)體變?cè)恼撌龇秶Q(chēng)為個(gè)體域 或論域 各種個(gè)體域綜合在一起作為論述范圍稱(chēng)為全總個(gè)體域 個(gè)體域和全總個(gè)體域是相對(duì)的 它根據(jù)你討論的問(wèn)題而定 同時(shí)它可以是有限的 也可以是無(wú)限的 2 2 2個(gè)體域 2 2 3量化用具體個(gè)體的名稱(chēng)取代個(gè)體變?cè)?使命題函數(shù)成為命題的過(guò)程稱(chēng)為代換 通過(guò)代換而得到的命題稱(chēng)為命題函數(shù)的代換實(shí)例 由代換實(shí)例得到的命題是個(gè)別命題 除代換外 我們還可以采用量化的辦法來(lái)確定命題 采用量化確定的命題是一個(gè)命題集合 所謂量化是指出個(gè)體變?cè)趥€(gè)體域中的取值方式 在謂詞邏輯中 個(gè)體域中個(gè)體變?cè)娜≈捣绞匠Ｓ玫挠幸韵聝煞N 1 全稱(chēng)量詞如果命題函數(shù)個(gè)體變?cè)趥€(gè)體域中的取值方式是考慮論域中的所有個(gè)體 則這種量化稱(chēng)為全稱(chēng)量化 如日常語(yǔ)言中的 所有的 任意的 每一個(gè) 等詞 我們把 所有的 的英語(yǔ)短語(yǔ) ForAll 中的 All 的第一個(gè)字母 A 倒寫(xiě)為 作為全稱(chēng)量詞符號(hào) x 表示個(gè)體域中的所有個(gè)體 其中的 x 稱(chēng)為指導(dǎo)變?cè)?例如 xP x 就表示個(gè)體域中的所有個(gè)體都具有性質(zhì)P 例如 設(shè)論域?yàn)槿祟?lèi)H x 表示x是要呼吸的 則 xH x 表示 所有人都是要呼吸的 例如 所有的自然數(shù)都是實(shí)數(shù) N x x是自然數(shù) R x x是實(shí)數(shù) 則原命題可以表示為 2 存在量詞如果命題函數(shù)個(gè)體變?cè)趥€(gè)體域中的取值方式是考慮個(gè)體域中的部分個(gè)體 則稱(chēng)為存在量化 它對(duì)應(yīng)日常語(yǔ)言中的 存在著 有的 至少有一個(gè) 有一些 等詞 英語(yǔ)短語(yǔ)表示為 ThereExist 我們用 Exist 的第一個(gè)字母E的反寫(xiě)為 作為存在量詞符號(hào) x 表示論域中存在某些個(gè)體 其中的 x 稱(chēng)為指導(dǎo)變?cè)?例如 xP x 表示論域中存在個(gè)體具有性質(zhì)P 例如 設(shè)論域?yàn)槿祟?lèi)S x 表示x吸煙 則 xS x 表示有人吸煙 例如 有的學(xué)生在看書(shū) S x 表示x是學(xué)生 B y 表示y是書(shū)籍 R x y 表示x正在看y 則原命題表示為 P x 是不能確定真值的命題函數(shù) 其中的x是個(gè)體變?cè)?而 xP x 和 xP x 都是可以確定真值的命題 其中的x再不起變?cè)淖饔?已經(jīng)受到量詞 x x的限制 個(gè)體變?cè)艿搅吭~限制的過(guò)程稱(chēng)之為量化 說(shuō)明 xP x 和 xP x 與P x 有著本質(zhì)的區(qū)別 2 2 4特性謂詞命題函數(shù)的量化與個(gè)體域有關(guān) 個(gè)體域的指定不但影響命題的表達(dá)形式 而且影響命題的真值 為了描述方便 將所討論的命題函數(shù)的個(gè)體域統(tǒng)一使用全總個(gè)體域 使用全總個(gè)體域后 對(duì)于每個(gè)個(gè)體變?cè)娜≈捣秶仨氂每虅潅€(gè)體特性的謂詞加以限制 定義2 5在全總個(gè)體域中 表示具體個(gè)體域的謂詞稱(chēng)為特性謂詞 例如 所有人是要死的 1 論域?yàn)槿祟?lèi) D x 表示x是要死的 符號(hào)化為 xD x 2 論域是全總個(gè)體域 使用全總個(gè)體域 就必須使用特性謂詞來(lái)限制個(gè)體的取值范圍 H x 表示x是人類(lèi) 特性謂詞 符號(hào)化為 值得注意的是 在全稱(chēng)量化中 特性謂詞常作為條件命題的前件 例如 有人吸煙 1 論域?yàn)槿祟?lèi) S x 表示x吸煙 符號(hào)化為 2 論域?yàn)槿倐€(gè)體域 此時(shí)就必須使用特性謂詞來(lái)限制個(gè)體的取值范圍 H x 表示x是人類(lèi)符號(hào)化為 例如 存在既是偶數(shù)又是素?cái)?shù)的有理數(shù) 論域?yàn)槿倐€(gè)體域 Q x 表示x是有理數(shù) E x 表示x是偶數(shù) P x 表示x是素?cái)?shù) 原命題符號(hào)化為 值得注意的是 在存在量化中 特性謂詞常作為合取項(xiàng) 2 2 5量化與代換實(shí)例當(dāng)個(gè)體域?yàn)橛邢藜蠒r(shí) 例如個(gè)體域?yàn)橛邢藜?a1 a2 a3 an 由量詞的定義可以知道 對(duì)于任意謂詞都有 2 1 2 2 這就是量詞的消去規(guī)則 它可以將帶量詞的謂詞公式轉(zhuǎn)化成謂詞公式的代換實(shí)例 這一點(diǎn)非常重要 在謂詞邏輯的等價(jià)公式證明中常采用這個(gè)規(guī)則 2 3謂詞合適公式與翻譯2 3 1謂詞合適公式在命題邏輯中引入了命題公式的概念 它是由命題常元 命題變?cè)?命題聯(lián)結(jié)詞和圓括號(hào)按照一定的規(guī)律所組成的符號(hào)串 謂詞邏輯是命題邏輯的進(jìn)一步拓展 在謂詞邏輯中 也需要引入原子謂詞公式和謂詞合適公式 Wellformformula簡(jiǎn)稱(chēng)謂詞公式 的概念 定義2 7原子謂詞公式定義如下 1 一個(gè)命題是原子謂詞公式 2 一個(gè)命題變?cè)窃又^詞公式 3 由n個(gè)個(gè)體變?cè)皀元謂詞所組成的命題函數(shù)也是一個(gè)原子謂詞公式 原子謂詞公式簡(jiǎn)稱(chēng)為原子公式 定義2 8謂詞公式定義如下 1 一個(gè)原子公式是一個(gè)謂詞公式 2 若A是謂詞公式 則 A也是謂詞公式 3 若A B是謂詞公式 則 A B A B A B A B 也是謂詞公式 4 若A是謂詞公式 x是A中的個(gè)體變?cè)?則 xA x xA x 也是謂詞公式 只有有限次地運(yùn)用規(guī)則 1 2 3 4 所得到的符號(hào)串才是謂詞公式 注意 謂詞公式中的某些圓括號(hào)也可以省略 其規(guī)定與命題公式相同 但量詞后的圓括號(hào)不能省略 因?yàn)樗P(guān)系到量詞的作用范圍 2 3 2謂詞公式的翻譯與命題公式的翻譯類(lèi)似 謂詞公式的翻譯同樣有兩個(gè)方面 一是將自然語(yǔ)言描述的命題符號(hào)化 也稱(chēng)形式化 二是將形式化的謂詞公式翻譯成自然語(yǔ)言描述的命題 在公式翻譯過(guò)程中 除注意聯(lián)結(jié)詞的選擇外 還必須注意量詞的選擇 一 將自然語(yǔ)言描述的謂詞公式形式化例2 4每個(gè)人都會(huì)犯錯(cuò)誤解 該命題可以說(shuō)成 對(duì)于所有的x 如果x是人 則x會(huì)犯錯(cuò)誤 設(shè)H x x是人 M x x會(huì)犯錯(cuò)誤 則命題可表示為 例2 5并非所有實(shí)數(shù)都是有理數(shù)解 該命題可以說(shuō)成 所有實(shí)數(shù)都是有理數(shù)是不對(duì)的 設(shè)R x x是實(shí)數(shù) Q x x是有理數(shù) 則命題可表示為 例2 6盡管有的人聰明 但不是所有的人都聰明解 該命題是由兩個(gè)并列的句子組成 即由兩個(gè)合取項(xiàng)組成 第一個(gè)合取項(xiàng)為 存在聰明的人 第二個(gè)合取項(xiàng)是 不是所有的人都是聰明人 設(shè)H x x是人 C x x聰明 則命題可表示為 例2 7李濤無(wú)書(shū)不讀 解 該命題即是說(shuō) 李濤所有的書(shū)都讀 設(shè)P x x是書(shū) Q y x y讀x a 李濤 則命題可表示為 例2 8有人無(wú)書(shū)不讀 解 該命題可解釋為存在這樣的人 這種人所有書(shū)都讀 H y y是人 P x