《離散數(shù)學(xué)第三章謂詞演算基礎(chǔ)-謂詞與個(gè)體.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第三章謂詞演算基礎(chǔ)-謂詞與個(gè)體.ppt（32頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、目錄（ 數(shù)理邏輯） 第一章 命題演算基礎(chǔ) （ 6學(xué)時(shí)） 第二章 命題演算的推理理論（ 4學(xué)時(shí)） 第三章 謂詞演算基礎(chǔ)（ 5學(xué)時(shí)） 第四章 謂詞演算的推理理論（ 5學(xué)時(shí)） 第五章 遞歸函數(shù)論（ 4學(xué)時(shí)） 第三章 謂詞演算基礎(chǔ) 在命題演算中，把不可剖開(kāi)或分解為更簡(jiǎn)單命 題的原子命題作為基本單元。 將對(duì)原子命題內(nèi)部結(jié)構(gòu)進(jìn)一步剖析，分解為 個(gè)體 謂詞 蘇格拉底三段論 P：凡人要死 Q：蘇格拉底是人 R：蘇格拉底要死 此三段論表示為 : (PQ)R 此三段論是正確的，但 PQR卻不是重言式， 這就是命題邏輯的局限性。 三段論 P: 計(jì)算機(jī)學(xué)院學(xué)生學(xué)習(xí)離散數(shù)學(xué) Q: 王明是計(jì)算機(jī)學(xué)院學(xué)生 R: 王明學(xué)習(xí)離
2、散數(shù)學(xué) (PQ)R 該推理是正確的，但 PQR卻不是重言式， 第三章 謂詞演算基礎(chǔ) 3.1 謂詞與個(gè)體 3.1.1 個(gè)體 3.1.2 謂詞 3.2 函數(shù)與量詞 3.3 自由變?cè)图s束變?cè)?3.4 永真性和可滿足性 3.5 唯一性量詞與摹狀詞 3.1.1 個(gè)體 (1)個(gè)體 ：個(gè)體是指具有獨(dú)立意義、獨(dú)立存在的東西。 也稱為常個(gè)體或?qū)嶓w。 用 a、 b、 c 等表示。 (2)個(gè)體域 ：由個(gè)體組成的集合稱為個(gè)體域。 個(gè)體域常用 I、 J、 K 等表示。 (3)全總個(gè)體域 ： 所有個(gè)體不管是何種類型的個(gè)體綜合在一起組成的 個(gè)體域稱為全總個(gè)體域。用 U表示。 個(gè)體變?cè)?、?xiàng) (4)個(gè)體變?cè)?：以個(gè)體域 I為
3、 變域 的變?cè)Q為個(gè)體域 I 上的個(gè)體變?cè)?用 x、 y、 z、 等表示。 (5)項(xiàng) ： 包括實(shí)體、變量符號(hào)和函數(shù)符號(hào)等 , 是構(gòu)成原子公式的一部分 (原子公式的定義詳見(jiàn)第 28頁(yè)第 -5行 ) 特定個(gè)體 a、泛指?jìng)€(gè)體 x、 個(gè)體的函數(shù) f(x) 第三章 謂詞演算基礎(chǔ) 3.1 謂詞與個(gè)體 3.1.1 個(gè)體 3.1.2 謂詞 3.2 函數(shù)與量詞 3.3 自由變?cè)图s束變?cè)?3.4 永真性和可滿足性 3.5 唯一性量詞與摹狀詞 一、有關(guān)概念 把語(yǔ)句中表示 個(gè)體性質(zhì)和關(guān)系的語(yǔ)言成分（通常是謂語(yǔ)） 稱為 謂詞 （ predicate）。 謂詞是指?jìng)€(gè)體所具 有的性質(zhì)或若干個(gè) 體之間的關(guān)系。 例 (謂詞
4、：表示個(gè)體性質(zhì)或個(gè)體間關(guān)系 ) “蘇格拉底是人”中的 “ 是人” 。 “蘇格拉底是要死的”中的 “ 是要死的” 。 “張三生于北京”中的 “ 生于 ” 。 “ 3+2=5”中的 “ +=” 。 謂詞的元數(shù) 謂詞所攜空位的數(shù)目 謂詞攜有可以放置個(gè)體的空位，當(dāng)空位上填 入個(gè)體后便產(chǎn)生一個(gè)關(guān)于這些個(gè)體的語(yǔ)句， 它斷言個(gè)體具有謂詞所表示的性質(zhì)和關(guān)系。 例 (一元謂詞、二元謂詞、三元謂詞 ) “蘇格拉底是人”中的 “ 是人” 。 “蘇格拉底是要死的”中的 “ 是要死的” 。 “張三生于北京”中的 “ 生于 ” 。 “ 3+2=5”中的 “ +=” 。 謂詞命名式 : 攜有空位的大寫(xiě)字母 M（）表示“ 是
5、人”。 D（）表示“ 是要死的”。 B（ ，）表示“ 生于 ”。 ADD（ ， ， ）表示“ +=”。 可讀性差！ 可用變?cè)獊?lái)代替空位。因此，上述謂詞可以表 示為： M(x)， D(x)， B(x,y)， ADD(x, y, z) 謂詞填式 謂詞的空位上填入個(gè)體后所產(chǎn)生的語(yǔ)句 。 例如： M（ 蘇格拉底 ）表示“ 蘇格拉底 是人”。 D（ 蘇格拉底 ）表示“ 蘇格拉底 是要死的”。 B（張三，北京）表示“張三生于北京”。 ADD（ 3， 2， 5）表示“ 3+2=5”。 單個(gè)謂詞不構(gòu)成完整的意思，只有當(dāng)謂詞填 以個(gè)體后才能夠構(gòu)成完整的意義。 謂詞命名式與謂詞填式 同形，但它們表示不同的意義。
6、例如， M(x)作為命名式時(shí)，它只是 M()的另一寫(xiě)法 ，與 x無(wú)關(guān)，改為 M(y)意義照舊； M(x)作為填式時(shí)，它表示“ x是人”，改為 M(y)后其意義“ y是人。 謂詞：從個(gè)體域到真值集的映射 當(dāng)謂詞填式中所填個(gè)體都是常元時(shí)，它是一 個(gè)命題，因而有確定的真值。 例如： M（ 蘇格拉底 ）為真， M（孔子）為真， M（孫悟空）為假， M（北京）為假。 一元謂詞的數(shù)目與個(gè)體域的大小有關(guān)。 謂詞：從個(gè)體域到真值集的映射 例如： D（ 蘇格拉底 ）為真， D（孫悟空）為假， B（ 蘇格拉底 ，希臘）為真 B（ 蘇格拉底 ，中國(guó)）為假， ADD（ 1， 1， 2）為真， ADD（ 3， 2， 5
7、）為真， ADD（ 3， 2， 6）為假。 謂詞變?cè)?以謂詞組成的集合為變域的變?cè)Q為謂詞變?cè)?已經(jīng)描述過(guò) : 大寫(xiě)字母 A、 B、 C等表示特定的謂詞， 小寫(xiě)字母 a、 b、 c表示特定的個(gè)體或?qū)嶓w。 現(xiàn)在約定用 大寫(xiě)字母 X、 Y、 Z等表示謂詞變?cè)?小寫(xiě)字母 x、 y、 z等表示個(gè)體變?cè)?二、謂詞語(yǔ)句的符號(hào)化 動(dòng)詞 、 系動(dòng)詞 、 形容詞、 集合名詞 均可以表達(dá)成謂詞。 例 1 我送他這本書(shū)。 解：令 A(e1， e2， e3)表示“ e1送 e3給 e2”； B(e)表示“ e為書(shū)”； a表示“我”； b表示“他”； c表示“這”； 則原句譯為： A(a， b， c) B(c)
8、例 2 這只大紅書(shū)柜擺滿了那些古書(shū)。 解：令 A(e1， e2)表示“ e1擺滿了 e2； B(e)表示“ e為大的”； C(e)表示“ e為紅的”； D(e)表示“ e為書(shū)柜”； E(e)表示“ e為古書(shū)”； a表示“這只”； b表示“那些”； 則原句譯為： A(a， b) B(a) C(a) D(a) E(b) 例 Shakespeare wrote “Hamlet”。 解： 令 WRITE(x, y)表示 x寫(xiě)了 y。 則原語(yǔ)句可以符號(hào)化為： WRITE(Shakespeare， Hamlet) 此表達(dá)式表示 常謂詞 WRITE與兩個(gè)實(shí)體 Shakespeare和 Hamlet之間的關(guān)系
9、。 特定的謂詞 基于個(gè)體變?cè)系闹^詞 進(jìn)一步考察： WRITE(x， y) 其中 x,y為變量符號(hào)項(xiàng)。 此式表示 x和 y的關(guān)系是 WRITE，即作者 x寫(xiě)了書(shū) y。 此時(shí) x可在個(gè)體域 I (表示作者的集合 )上變化； y可在個(gè)體域 J (表示書(shū)名的集合 )上變化。 謂詞變?cè)?一般地，考察 A(x， y) 其中 x,y為變量符號(hào)項(xiàng)、 A為謂詞變?cè)?此式表示 x和 y具有關(guān)系 A。 注意： x， y， A分別在三個(gè)域上變化。 謂詞變?cè)亩x 以某個(gè)個(gè)體域 I為定義域、以真假為值 域的謂詞稱作 個(gè)體域 I上 的 謂詞 。 以某個(gè)個(gè)體域 I上的謂詞為 變域 的變?cè)?稱作 個(gè)體域 I上的 謂詞變?cè)?/p>
10、 。 個(gè)體域 a上的一元謂詞 單個(gè)體的一元謂詞 A(e)如下圖所示 : e A1 A2 a T F 一元謂詞共有兩個(gè)。 個(gè)體域 a， b上的一元謂詞 兩個(gè)個(gè)體的一元謂詞 A(e)如下圖所示 : e A1 A2 A3 A4 a T F T F b T T F F 兩個(gè)個(gè)體的 一元謂詞共有 22=4個(gè)。 個(gè)體域 a， b， c上的一元謂詞 三個(gè)個(gè)體的一元謂詞 A(e)如下圖所示 : e A1 A2 A3 A4 A5 A6 A7 A8 a T F T T F T F F b T T F T F F T F c T T T F T F F F 三個(gè)個(gè)體的 一元謂詞共有 23=8個(gè)。 個(gè)體域 a上的二元
11、謂詞 單個(gè)體的二元謂詞 A(e1， e2)如下圖所示 : e1 e2 A1 A2 a a T F 單 個(gè)體的二 元謂詞有 2個(gè)。 個(gè)體域 a， b上的二元謂詞 兩個(gè)個(gè)體的二元謂詞 A(e1， e2)如下圖所示 : 兩個(gè)個(gè)體的 二元謂詞 A(e1， e2)共有 24=16個(gè)。 e1 e2 A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 a a T F T T T F F F T T T T F F F F a b T T F T T F T T F F T F T F F F b a T T T F T T F T F T F F F T F F b b T T T T F T T F T F F F F F T F 謂詞數(shù)目 不難驗(yàn)證， h個(gè)個(gè)體組成的個(gè)體域 I上的一元謂 詞有 2h個(gè)，二元謂詞共有 2h2個(gè)， m元謂詞共有 2hm個(gè)。 謂詞數(shù)目 一元謂詞 二元謂詞 三元謂詞 m元謂詞 2個(gè)個(gè)體 4 16 256 22m 3個(gè)個(gè)體 8 512 134217728 23m h個(gè)個(gè)體 2h 2h2 2h3 2hm 第三章 謂詞演算基礎(chǔ) 3.1 謂詞與個(gè)體 3.1.1 個(gè)體 3.1.2 謂詞 3.2 函數(shù)與量詞 3.3 自由變?cè)图s束變?cè)?3.4 永真性和可滿足性 3.5 唯一性量詞與摹狀詞
離散數(shù)學(xué)第三章謂詞演算基礎(chǔ)-謂詞與個(gè)體.ppt
