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