離散數(shù)學(xué)第三章 謂詞演算基礎(chǔ)-函數(shù)與量詞

《離散數(shù)學(xué)第三章 謂詞演算基礎(chǔ)-函數(shù)與量詞》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第三章 謂詞演算基礎(chǔ)-函數(shù)與量詞（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第三章 謂詞演算基礎(chǔ)3.1 謂詞與個體謂詞與個體3.2 函數(shù)與量詞函數(shù)與量詞 3.2.1 函數(shù)項函數(shù)項 3.2.2 量詞量詞3.3 自由變元和約束變元自由變元和約束變元 3.4 永真性和可滿足性永真性和可滿足性3.5 唯一性量詞與摹狀詞唯一性量詞與摹狀詞復(fù)習(xí)：復(fù)習(xí)：項的概念項的概念例例 考察謂詞考察謂詞 WRITE(x,y)表示表示x 寫了寫了y 的謂詞填式：的謂詞填式：uWRITE(Shakespeare，Hamlet)uWRITE(Shakespeare，y)u莎士比亞的兒子寫了哈姆雷特莎士比亞的兒子寫了哈姆雷特 WRITE(son(Shakespeare)，Hamlet)變量符號函數(shù)！實

2、體函數(shù)項函數(shù)項以個體為定義域、以個體為值域的函數(shù)。以個體為定義域、以個體為值域的函數(shù)。約定用約定用f，g，h等表示抽象的函數(shù)項。等表示抽象的函數(shù)項。項：包括實體、變量符號和函數(shù)符號等項：包括實體、變量符號和函數(shù)符號等,是構(gòu)成原子公式的一部分是構(gòu)成原子公式的一部分 (原子公式的定義詳見原子公式的定義詳見3.3第第28頁第頁第-5行行)例例 Johns mother is married to his father解：解：記記 M(e1，e2)表示表示e1 is married to e2；f(e)表示表示e的的father；m(e)表示表示e的的mother。則原話可以翻譯為：則原話可以翻譯為：

3、M(m(John)，f(John)量詞量詞l計算機學(xué)院學(xué)生都是江蘇人。計算機學(xué)院學(xué)生都是江蘇人。l計算機學(xué)院學(xué)生有江蘇人。計算機學(xué)院學(xué)生有江蘇人。l計算機學(xué)院教師都有學(xué)士學(xué)位。計算機學(xué)院教師都有學(xué)士學(xué)位。l計算機學(xué)院有些教師沒有學(xué)士學(xué)位。計算機學(xué)院有些教師沒有學(xué)士學(xué)位。所有人所有人有一些有一些計算機系人（包括教師與學(xué)生）計算機系人（包括教師與學(xué)生）全總個體域、全總個體域、量詞量詞(1)約定變量符號即個體變元約定變量符號即個體變元x取值于全總個體域取值于全總個體域U；(2)用謂詞來限定用謂詞來限定x的取值范圍；的取值范圍；(3)引進引進 全稱量詞全稱量詞 x 表示表示“所有的所有的x”、“一切一

4、切x”等，等，存在量詞存在量詞 x 表示表示“存在一些存在一些x”、“有一些有一些x”等概念；等概念；(4)規(guī)定一般情況下規(guī)定一般情況下緊跟在全稱量詞緊跟在全稱量詞 x之后的主聯(lián)結(jié)詞為之后的主聯(lián)結(jié)詞為“”，緊跟在存在量詞緊跟在存在量詞 x之后的主聯(lián)結(jié)詞為之后的主聯(lián)結(jié)詞為“”。試譯：試譯：計算機學(xué)院的有些老師是青年教師。計算機學(xué)院的有些老師是青年教師。解：解：設(shè)設(shè) C(e)表示表示e為計算機學(xué)院的人；為計算機學(xué)院的人；T(e)表示表示e為教師為教師;Y(e)表示表示e為青年為青年.則原句譯為：則原句譯為：x(C(x)T(x)Y(x)此例中：此例中：x就取值于全總個體域就取值于全總個體域U，謂詞謂

5、詞C(e)限定限定x取值范圍。取值范圍。例例1 某些人對某些食物過敏。某些人對某些食物過敏。解：設(shè)解：設(shè) A(e)表示表示e為人；為人；B(e)表示表示e為食物；為食物；C(e1，e2)表示表示e1對對e2過敏。過敏。則原句譯為：則原句譯為：x(A(x)y(B(y)C(x，y)例2 金子閃光，但閃光的并非全是金子。金子閃光，但閃光的并非全是金子。解：設(shè)解：設(shè) G(e)表示表示e為金子；為金子；S(e)表示表示e閃光。閃光。則原句譯為：則原句譯為：x(G(x)S(x)x(S(x)G(x)或或 x(G(x)S(x)x(S(x)G(x)例3 If a program can not be told

6、a fact，then it can not learn that fact.解：設(shè)解：設(shè) P(e)表示表示e為為program;F(e)表示表示e為為fact;T(e1，e2)表示表示e1 can be told e2;L(e1，e2)表示表示e1 can learn e2;則原句譯為：則原句譯為：x y(P(x)F(y)T(x，y)L(x，y)例例4 并非并非“人不為己，天誅地滅人不為己，天誅地滅”。解：設(shè)解：設(shè)P(e)表示表示e為人；為人；A(e1，e2)表示表示e1為為e2；B(e1，e2)表示表示e1誅誅e2；C(e1，e2)表示表示e1滅滅e2；a表示天；表示天；b表示地；表示地；

7、則原句譯為：則原句譯為：x(P(x)A(x,x)(B(a,x)C(b,x)例5 任何人均會犯錯誤。任何人均會犯錯誤。解：設(shè)解：設(shè) P(e)表示表示e為人；為人；M(e)表示表示e為錯誤；為錯誤；D(e1，e2)表示表示e1犯犯e2。則原句譯為：則原句譯為：x(P(x)y(M(y)D(x，y)例例6 己所不欲勿施于人。己所不欲勿施于人。解：設(shè)解：設(shè) P(e)表示表示e為人；為人；T(e)表示表示e為東西；為東西；W(e1，e2)表示表示e1要要e2；S(e1，e2，e3)表示表示e1施施e2給給e3。則原句譯為：則原句譯為：x y(P(x)T(y)W(x,y)z(P(z)S(x,y,z)例例 所

8、有的正數(shù)均可開方。所有的正數(shù)均可開方。解：解：(i)若個體域為全體正實數(shù)若個體域為全體正實數(shù)R+，S(X)：X可以開方，可以開方，則命題符號化為：則命題符號化為：xS(x)(ii)若個體域為全體實數(shù)集若個體域為全體實數(shù)集R，G(x，y)：xy，則命題符號化為：則命題符號化為：x(G(x，0)S(x)(iii)若若D為全總個體域為全總個體域,R(x):x是實數(shù)，則符號化為：是實數(shù)，則符號化為：x(R(x)G(x，0)S(x)例例 沒有最大的自然數(shù)沒有最大的自然數(shù)。解：這句話可以理解為解：這句話可以理解為“對所有對所有x，若，若x是自然是自然數(shù)，則存在數(shù)，則存在y，y也是自然數(shù)，且也是自然數(shù)，且y

9、x”。引入引入N(x):x是自然數(shù)，是自然數(shù)，G(x,y):xy,則符號化為：則符號化為：x(N(x)y(N(y)G(y,x)也可以理解為也可以理解為“下句話是不對的下句話是不對的存在一存在一個個x，x是自然數(shù)且對一切自然數(shù)是自然數(shù)且對一切自然數(shù)y，x均大均大于于y”，符號化為，符號化為x(N(x)y(N(y)G(x,y)設(shè)設(shè)B(x):x是最大的，是最大的，N(x):x是自然數(shù)。是自然數(shù)。則命題可以表示為：則命題可以表示為：x(B(x)N(x)第三章 謂詞演算基礎(chǔ)3.1 謂詞與個體謂詞與個體3.2 函數(shù)與量詞函數(shù)與量詞 3.2.1 函數(shù)項函數(shù)項 3.2.2 量詞量詞3.3 自由變元和約束變元自由變元和約束變元 3.4 永真性和可滿足性永真性和可滿足性3.5 唯一性量詞與摹狀詞唯一性量詞與摹狀詞