離散數(shù)學(xué)22命題函數(shù)與量詞

1、1第二章謂詞邏輯2-2 命題函數(shù)與量詞授課人：李朔email:2一、命題函數(shù)與命題邏輯中命題常量和命題變?cè)母拍铑愃?，代表個(gè)體的個(gè)體標(biāo)識(shí)符也可以表示客體（個(gè)體常量）客體（個(gè)體常量）或客體變?cè)▊€(gè)體變?cè)┛腕w變?cè)▊€(gè)體變?cè)﹏表示具體或特定個(gè)體的標(biāo)識(shí)符稱作個(gè)體常元個(gè)體常元，一般用小寫英文字母a、b、c、或這些英文字母帶下標(biāo)表示。n將表示任意個(gè)體或泛指某類個(gè)體的標(biāo)識(shí)符稱為個(gè)體變?cè)獋€(gè)體變?cè)?，常表示為x、y、z、等或這些英文字母帶下標(biāo)。3一、命題函數(shù)設(shè)h是謂詞“能到達(dá)山頂”ni表示客體李四、t表示老虎，c表示汽車nh(i)、h(t)、h(c)分別表示了三個(gè)不同命題，它們有一個(gè)共同的共同的形式，即h(x

2、)nx取l時(shí)表示：李四能到達(dá)山頂 x取t時(shí)表示：老虎能到達(dá)山頂 x取c時(shí)表示：汽車能到達(dá)山頂同理，若l(x,y)表示“x小于y”,那么l(2,3)表示一個(gè)真命題：2小于3。而l(5,1)則表示假命題:5小于1又如a(x,y,z)表示“x+y=z”,則a(3,2,5)是一個(gè)真命題，而a(1,2,4)是一個(gè)假命題。4一、命題函數(shù)上述三例中h(x),l(x,y),a(x,y,z)（其中x,y,z為客體變?cè)┍旧聿皇且粋€(gè)命題，只有當(dāng)x,y,z取特定客體時(shí)，才確定了一個(gè)命題。定義定義2-2.1 由一個(gè)謂詞，一些客體變?cè)M成的表達(dá)式稱為簡(jiǎn)單命題函數(shù)簡(jiǎn)單命題函數(shù)。n由這個(gè)定義可知，n元謂詞就是有n個(gè)客體變?cè)?/p>

3、的命題函數(shù)。當(dāng)n=0時(shí)稱為0元謂詞元謂詞，它本身就是一個(gè)命題，所以命題是n元謂詞（命題函數(shù)）的一個(gè)特殊情況。5一、命題函數(shù)n因?yàn)槊}函數(shù)中包含客體變?cè)?，因此命題函數(shù)沒有確定的真值，它不是命題。只要用客體取代所有的個(gè)體變?cè)?，就得到了命題。 例如，用例如，用h(x,y)：x+y0，顯然此命題函數(shù)不是命題，顯然此命題函數(shù)不是命題，因?yàn)樗鼰o法判斷真假。令因?yàn)樗鼰o法判斷真假。令 a：5, b：-7 用用a,b分別取代分別取代x,y，就得到就得到h(a,b)，它表示它表示5+(7)0，這是個(gè)假命題，它的真值為假。這是個(gè)假命題，它的真值為假。n用個(gè)體常元取代命題函數(shù)的所有個(gè)體變?cè)玫降谋磉_(dá)式就是前面所說的

4、謂詞填式謂詞填式。也把謂詞填式叫做0元謂詞（含0個(gè)客體變?cè)?一、命題函數(shù)由一個(gè)或n個(gè)簡(jiǎn)單命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式稱復(fù)合命題函數(shù)復(fù)合命題函數(shù)。n邏輯聯(lián)結(jié)詞 、 的意義與命題演算中的解釋完全類同。例：將下列命題符號(hào)化，并討論它們的真值。例：將下列命題符號(hào)化，并討論它們的真值。 2與與3都是偶數(shù)。都是偶數(shù)。 如果如果5大于大于3，則，則2大于大于6。 解：解： 設(shè)設(shè)f(x)：x是偶數(shù)。是偶數(shù)。 a：2，b：3 該命題符號(hào)化為：該命題符號(hào)化為： f(a)f(b) f(b)表示表示3是偶數(shù)，它是個(gè)假命題。所以是偶數(shù)，它是個(gè)假命題。所以f(a)f(b)為假。為假。 設(shè)設(shè)g(x,y)： x

5、大于大于y a：5，b：3，c：2，d：6 該命題符號(hào)化為：該命題符號(hào)化為：g(a,b)g(c,d) g(a,b)表示表示5大于大于3，它是真命題。，它是真命題。g(c,d)表示表示2大于大于6，這是個(gè)，這是個(gè)假命題。所以假命題。所以g(a,b)g(c,d)為假。為假。書例見書例見p56 例例1-例例37二、個(gè)體域客體變?cè)娜≈捣秶鷮?duì)命題函數(shù)是否可成為命題及其真值極有影響例4 r(x)：x是大學(xué)生n如果x的討論范圍是某大學(xué)里班級(jí)中的學(xué)生，則r(x)是永真式n如果x的討論范圍是某中學(xué)班級(jí)里中的學(xué)生，則 r(x)是永假式。n而如果x的討論范圍是一個(gè)劇場(chǎng)中的觀眾，其中有一部分大學(xué)生，那么，對(duì)某些觀眾

6、，r(x)為真，對(duì)另一些觀眾r(x)為假。8二、個(gè)體域例5 (p(x,y) p(y,z) p(x,z)n若p(x,y) ：x小于y。當(dāng)x,y,z都在實(shí)數(shù)域中取值時(shí)，該式永真n若p(x,y) ：x為y的兒子。當(dāng)x,y,z都指人時(shí)，該式永假n若p(x,y) ：x距離y 10米。若x,y,z表示地面上的房子，則命題的真值將由x,y,z的具體位置而定，可能為真，也可能為假。9二、個(gè)體域可以看出命題函數(shù)確定為命題與客體變?cè)恼撌龇秶嘘P(guān)。n在命題函數(shù)中，客體變?cè)恼撌龇秶Q為個(gè)體個(gè)體域或論域域或論域。n個(gè)體域可以是有限的，也可以是無限的，包含任意個(gè)體域的個(gè)體域稱為全總個(gè)體域全總個(gè)體域，它是由宇宙間一切對(duì)

7、象組成的集合。10三、量詞有了客體變?cè)椭^詞之后，有些命題還是不能準(zhǔn)確的符號(hào)化，原因是還缺少表示客體（變?cè)┲g數(shù)量關(guān)系的詞。稱表示客體（變?cè)┲g數(shù)量關(guān)系的詞為量詞量詞。量詞可分兩種: 全稱量詞全稱量詞 日常生活和數(shù)學(xué)中常用的“一切的”，“所有的”，“每一個(gè)”，“任意的”，“凡”，“都”等詞統(tǒng)稱為全全稱量詞稱量詞，將它們符號(hào)化為“”。并用并用( ( x)x)，( ( y)y)等表示等表示個(gè)體域里的所有個(gè)體個(gè)體域里的所有個(gè)體，而用( ( x)f(x)x)f(x)和和( ( y)g(y)y)g(y)等分別等分別表示個(gè)體域中的所有個(gè)體都有性質(zhì)表示個(gè)體域中的所有個(gè)體都有性質(zhì)f f和都有性質(zhì)和都有性質(zhì)

8、g g。11三、量詞例 （a）所有人都是要呼吸的。 (b) 每個(gè)學(xué)生都要參加考試。 (c) 任何整數(shù)或是正的或是負(fù)的。 n若設(shè)m(x):x是人，h(x):x要呼吸。 p(x):x是學(xué)生，q(x):x要參加考試。 i(x):x是整數(shù), r(x):x是正數(shù)，n(x):x是負(fù)數(shù)。n則(a)記為（x）(m(x) h(x)n (b)記為（x）(p(x) q(x)n (c)記為（x）(i(x) (r(x)n(x) )12三、量詞 存在量詞存在量詞 “存在”，“有一個(gè)”，“有些”，“至少有一個(gè)”等詞統(tǒng)稱為存在量詞存在量詞，將它們符號(hào)化為“”。并用(x)，(y)等表示個(gè)體域里有些個(gè)體，而用(x)f(x)和(y

9、)g(y)等分別表示在個(gè)體域中存在個(gè)體具有性質(zhì)f和存在個(gè)體具有性質(zhì)g。例 (a)存在一個(gè)數(shù)是質(zhì)數(shù)。 (b)一些人是聰明的。 (c)有些人早飯吃面包。設(shè)p(x)：x是質(zhì)數(shù)。 m(x): x是人。 e(x): x早飯吃面包。則 (a)記為(x)(p(x) (b)記為(x)(m(x)r(x) (c) 記為(x)(m(x)e(x)13三、量詞全稱量詞與存在量詞統(tǒng)稱為量詞量詞。n每個(gè)由量詞確定的表達(dá)式，都與個(gè)體域有關(guān)，如前列中（x）(m(x) h(x)表示所有的人都要呼吸，若把個(gè)體域限制在“人類”這個(gè)范圍中，那么亦可簡(jiǎn)單的表示為（x）(h(x)n 指定論域不僅與表達(dá)形式有關(guān)，而且與命題的真值有關(guān)，如上例

10、中設(shè)論域?yàn)椤白匀粩?shù)”，則命題的真值為f f。為了方便，我們將所有命題函數(shù)的個(gè)體域全部統(tǒng)一，使用全總個(gè)體域。14三、量詞例：用謂詞表達(dá)式寫出下列命題。n（1）愛美之心人皆有之。設(shè)設(shè)f(x):x為人，為人，g(x):x愛美。愛美。 n（2）有人愛發(fā)脾氣。設(shè)設(shè)f(x):x為人，為人，g(x):x愛發(fā)脾氣。愛發(fā)脾氣。n（3）說所有人都愛吃面包是不對(duì)的。 f(x)：x為人，為人，g(x):x愛吃面包愛吃面包n（4）沒有不吃飯的人。 f(x):x為人，為人，g(x):x吃飯吃飯n（5）一切人都不一樣高。 f(x):x為人，為人，h(x,y):x與與y不同，不同，l(x,y):x與與y一樣高。一樣高。n（6

11、）并不是所有的汽車比所有的火車快。 f(x):x為汽車，為汽車，g(y):y為火車，為火車，h(x,y):x比比y快快 15三、量詞解：n(1)設(shè)f(x):x為人，g(x):x愛美。 x(f(x)g(x)x(f(x)g(x)。 *將公式翻譯自然語(yǔ)言可以這樣敘述“對(duì)于宇宙間一切事物x而言，如果x是人，則x是愛美的”，即“愛美之心人皆有之”，它反映了愛美是人的共性之一。 n (2)設(shè)f(x):x為人，g(x):x愛發(fā)脾氣。 x(f(x)g(x)x(f(x)g(x)。 *敘述為“宇宙中存在著一些事物x,x是人，而且x愛發(fā)脾氣。n 16三、量詞*從(1)(2)中可以看出，若個(gè)體域使用了全總個(gè)體域，需要

12、對(duì)每一個(gè)客體變?cè)淖兓秶弥^詞加以限制，這個(gè)謂詞表示了一個(gè)非全總個(gè)體域的個(gè)體域，稱為特性謂詞。n一般的，對(duì)全稱量詞，特性謂詞常作原命題公式的蘊(yùn)含前件。如： x(f(x)g(x)x(f(x)g(x)n一般的，對(duì)存在量詞，特性謂詞常作為原命題公式的合取項(xiàng)。如： x(f(x)g(x)x(f(x)g(x)17三、量詞n(3)本命題是對(duì)“所有人都愛吃面包”的否定，仿照第1）題，容易看出，它的符號(hào)化形式為 x(f(x)g(x)x(f(x)g(x) (其中，f(x)：x為人，g(x):x愛吃面包) 又容易看出，本命題與“有人不愛吃面包”是一回事， 所以還可以符號(hào)化為： x(f(x)g(x)x(f(x)g(

13、x) n(4)本題是對(duì)“有不吃飯的人”的否定，仿照（2），容易看出，它的符號(hào)化形式為： x(f(x) x(f(x) g(x)g(x) (其中，f(x):x為人，g(x):x吃飯)又不難看出，本命題與“所有人都吃飯”是一回事，因而有可以符號(hào)化為： x(f(x)g(x)x(f(x)g(x) 18三、量詞n(5)一切人都不一樣高。 令f(x):x為人，h(x,y):x與y不同，l(x,y):x與y一樣高。 命題符號(hào)化為： x(f(x) x(f(x) y(f(y)h(x,y)l(x,y)y(f(y)h(x,y)l(x,y) 又可以寫成： x x y(f(x)f(y)h(x,y)l(x,y) y(f(x)f(y