離散數(shù)學(xué)-謂詞邏輯

1、第二章 謂詞邏輯 （Predicate Logic）,歷史使人聰明，詩(shī)歌使人機(jī)智，數(shù)學(xué)使人精細(xì)，哲學(xué)使人深邃，道德使人嚴(yán)肅，邏輯與修辭使人善辯。 Bacon Francis,第二章 謂詞邏輯,2.1謂詞的概念與表示(Predicate and it

2、s expression)2.2謂詞公式與翻譯(Predicate formulae)2.3約束變?cè)c自由變?cè)?Free and Bound variable)2.4 謂詞的解釋與類型(Interpretation & types of predicate calculus) 2.5謂詞演算的等價(jià)式與蘊(yùn)含式(Equivalences & implications of predicat

3、e calculus)2.6前束范式(Prenex normal form)2.7謂詞演算的推理理論(Inference theory of predicate calculus),2.1 謂詞的概念與表示(Predicate and Its Expression),在Ls中，把命題分解到原子命題為止，認(rèn)為原子命題是不能再分解的，僅僅研究以原子命題為基本單位的復(fù)合命題之間的邏輯關(guān)系和推理。命題邏輯的局限性： （

4、1） 它不能揭示某些有效的論證； （2） 無(wú)法將具有某種共同屬性的命題顯示出來(lái)，甚至對(duì)于含有變量的判斷都無(wú)法用命題來(lái)描述。,例如，下列推理： 所有的人都是要死的。 蘇格拉底是人。 所以，蘇格拉底是要死的。 這是有效論證。但在命題邏輯中,如果用P,Q,R表示以上三個(gè)命題，則上述推理

5、過(guò)程為：（P∧Q）?R。借助命題演算的推理理論不能證明其為重言式。（P真Q真R假為成假賦值）,2.1 謂詞的概念與表示(Predicate and Its Expression),【例】設(shè) P 表示命題：張輝是工人。 Q 表示命題：李明是工人。 僅僅從命題符號(hào) P 和 Q 看不出張輝和李明都是工人這一特性?！纠?x=3 ? x+y=z ? f(

6、x)=0 ?,2.1 謂詞的概念與表示(Predicate and Its Expression),第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),原因：命題邏輯不能將命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系反映出來(lái)。解決辦法：將命題進(jìn)行分解，分析出個(gè)體詞，謂詞和量詞，以期達(dá)到表達(dá)出個(gè)體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系。,2.1 謂詞的概念與表示(

7、Predicate and Its Expression),2.1.1 個(gè)體和謂詞 在謂詞邏輯中，可將原子命題劃分為個(gè)體和謂詞兩部分。個(gè)體：可以獨(dú)立存在的具體事物的或抽象的概念。例如，電子計(jì)算機(jī)、李明、玫瑰花、黑板、實(shí)數(shù)、中國(guó)、思想、唯物主義等，個(gè)體也可稱之為主語(yǔ)。,2.1 謂詞的概念與表示(Predicate and Its Expression),謂詞：用來(lái)刻劃個(gè)體的性質(zhì)或個(gè)體之間的相互關(guān)系的詞。例如在

8、下面命題中： （1）張明是個(gè)勞動(dòng)模范。 （2）李華是個(gè)勞動(dòng)模范。 刻劃客體的性質(zhì) （3）王紅是個(gè)大學(xué)生。 （4）小李比小趙高2cm。 （5）點(diǎn)a在b與c之間。 刻劃客體之間的相互關(guān)系 （6）阿杜與阿寺同歲。 （7） x與y具有關(guān)系L。 “是個(gè)勞動(dòng)模范”、“是個(gè)大學(xué)生”、“…比…高2cm”、 “… 在…與…之間”、“…

9、與…具有關(guān)系L”都是謂詞。,2.1 謂詞的概念與表示(Predicate and Its Expression),刻劃一個(gè)個(gè)體性質(zhì)的詞稱之為一元謂詞,刻劃n個(gè)個(gè)體之間關(guān)系的詞稱之為n元謂詞.一般我們用大寫英文字母表示謂詞，用小寫英文字母表示個(gè)體名稱，例如，將上述謂詞分別記作大寫字母F、G、H、R，S，則上述命題可表示為： (1) F(a) a：張明 (2) F(b) b：李華 (3) G

10、(c) c：王紅 (4) H(s,t) s：小李 t：小趙 (5) R(a,b,c) (6) S(a,b) a:阿杜。b:阿寺。稱為命題的謂詞形式。,2.1 謂詞的概念與表示(Predicate and Its Expression),表示具體性質(zhì)或關(guān)系的謂詞稱為謂詞常元；表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞稱為謂詞變?cè)?一般的，用F(a)表示個(gè)體常元a具

11、有性質(zhì)F(F是謂詞常項(xiàng)或謂詞變項(xiàng))，用F(x)表示個(gè)體變?cè)獂具有性質(zhì)F，而用F(a，b)表示個(gè)體常元a，b具有關(guān)系F，用F(x,y)表示個(gè)體變?cè)獂，y具有關(guān)系F。,2.1 謂詞的概念與表示(Predicate and Its Expression),注：(1)單獨(dú)一個(gè)謂詞并不是命題，在謂詞字母后填上個(gè)體所得到的式子稱之為謂詞填式。(2)在謂詞填式中，若個(gè)體確定，則A(a1，a2...an)就變成了命題。 (3)在多元謂詞表達(dá)式中

12、，個(gè)體字母出現(xiàn)的先后次序與事先約定有關(guān)，一般不可以隨意交換位置(如，上例中H(s,t) 與H(t, s)代表兩個(gè)不同的命題) 。,2.1 謂詞的概念與表示(Predicate and Its Expression),定義2.1.3:由一個(gè)謂詞H和n個(gè)個(gè)體變?cè)M成的表達(dá)式H(x1, x2 , …, xn)稱為n元原子謂詞或n元簡(jiǎn)單命題函數(shù)，簡(jiǎn)稱n元謂詞。在命題函數(shù)中，個(gè)體變?cè)娜≈捣秶Q為個(gè)體域，又稱之為論域。個(gè)體域可以是有限事物的集

13、合，也可以是無(wú)限事物的集合。全總個(gè)體域：宇宙間一切事物組成的個(gè)體域稱為全總個(gè)體域。,2.1 謂詞的概念與表示(Predicate and Its Expression,有時(shí)候?qū)⒉粠€(gè)體變項(xiàng)的謂詞稱為0元謂詞，例如，F(xiàn)(a)，G(a,b)，P(a1,a2,…,an)等都是0元謂詞。當(dāng)F，G，P為謂詞常項(xiàng)時(shí)，0元謂詞為命題。這樣一來(lái)，命題邏輯中的命題均可以表示成0元謂詞，因而可以將命題看成特殊的謂詞。,2.1 謂詞的概念與表示(Pred

14、icate and Its Expression),命題的謂詞形式舉例。例1:若小明的學(xué)習(xí)好，則小明的工作好。 設(shè) S(x):x學(xué)習(xí)好；W(x):x工作好；a:小明。 則有 S(a) ? W(a),,例2:將下列命題用0元謂詞符號(hào)化，并討論它們的真值。(1) 2是素?cái)?shù)且是偶數(shù)。(2) 如果2大于3,則2大于4。(3) 如果張明比李民高, 李民比趙亮高,則張明比趙亮高。,2.1 謂詞的概念與表示(Predic

15、ate and Its Expression),解:(1) 設(shè)F(x): x是素?cái)?shù). G(x): x是偶數(shù). 則命題符號(hào)化為： F(2)∧G(2) （真） (2) 設(shè)L(x,y) ：x大于y. 則命題符號(hào)化為： L(2,3) ? L(2,4) （真） (3) 設(shè) H(x,y): x比y高. a:張明 b:李民 c：趙亮 則命題符號(hào)化為： H(a,

16、b)∧H(b ,c)?H(a,c) （真）,,實(shí)質(zhì)上，n元謂詞 H(x1, x2 , …, xn) 可以看成以個(gè)體域?yàn)槎x域，以{0,1}為值域的n元函數(shù)或關(guān)系。它不是命題。要想使它成為命題，必須用個(gè)體常項(xiàng)a1, a2 , …, an取代x1, x2 , …, xn ，得H(a1, a2 , …, an)是命題。注意:命題函數(shù)中，個(gè)體域選擇的不同對(duì)命題的真值極有影響。,例：若 R (x) 表示 “a 是大學(xué)生”，

17、如果 x 的討論范圍為某大學(xué)里的所有在校學(xué)生， 則 R(x) 是永真式。若 x 的討論范圍為某中學(xué)里的所有在校學(xué)生， 則 R(x) 是永假式。若 x 的討論范圍為一個(gè)劇場(chǎng)中的觀眾，觀眾中有大學(xué)生也有非大學(xué)生，那么，對(duì)某些觀眾而言，

18、R(x) 為真，對(duì)另一些觀眾而言，R(x) 為假。,例：試將 “所有的人都是要死的” 這一命題符號(hào)化。 在此例中，怎么表達(dá)“所有的”這一概念呢？顯然，僅僅用目前所討論的知識(shí)是不行的，在此引入量詞來(lái)刻劃 “所有的” 這一概念。,2.1 謂詞的概念與表示(Predicate and Its Expression),2.1.2 量詞(Quantifiers)量詞：有了個(gè)體詞和謂詞之后，有些命題還是不能準(zhǔn)確的符號(hào)化，原

19、因是還缺少表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞。稱表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞為量詞。分為全稱量詞(?)和存在量詞(?),2.1 謂詞的概念與表示(Predicate and Its Expression),1.全稱量詞(The Universal Quantifiers)對(duì)日常語(yǔ)言中的“一切”、“所有”、“凡”、“每一個(gè)”、“任意”等詞，用符號(hào)“?” 表示， ?ｘ表示對(duì)個(gè)體域里的所有個(gè)體， （?ｘ）Ｆ(ｘ)表示個(gè)體域里

20、的所有個(gè)體具有性質(zhì)F。符號(hào)“?”稱為全稱量詞。,2.1 謂詞的概念與表示(Predicate and Its Expression),例3：在謂詞邏輯中將下列命題符號(hào)化.（1）凡是人都呼吸。 （2）每個(gè)學(xué)生都要參加考試。（3）任何整數(shù)或是正的或是負(fù)的。解: (1) 當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)： 令F(x): x呼吸。則（1）符號(hào)化為（?x）F(x) 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令M(x): x

21、是人。則（1）符號(hào)化為 （?x）(M(x) ?F(x)).,2.1 謂詞的概念與表示(Predicate and Its Expression),(2) 當(dāng)個(gè)體域?yàn)槿w學(xué)生的集合時(shí)： 令P(x): x要參加考試。則（2）符號(hào)化為 （?x）P(x) 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令S(x): x是學(xué)生。則（2

22、）符號(hào)化為 （?x）(S(x) ?P(x)).,2.1 謂詞的概念與表示(Predicate and Its Expression),(3) 當(dāng)個(gè)體域?yàn)槿w整數(shù)的集合時(shí)： 令P(x): x是正的。N(x): x是負(fù)的。則（3）符號(hào)化為 （?x）(P(x)∨N(x)) 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：

23、 令I(lǐng)(x): x是整數(shù)。則（3）符號(hào)化為 （?x）(I(x)?(P(x)∨N(x))).,,全稱量詞的一些重要性質(zhì)：設(shè)P是任意的命題，F(xiàn)(x)與A(x,y)均為謂詞，則有：,2.1 謂詞的概念與表示(Predicate and Its Expression),2.存在量詞(The Existential Quantifiers)對(duì)日常語(yǔ)言中的“有一個(gè)”、“有的”、“存在著”、“

24、至少有一個(gè)”、 “存在一些”等詞，用符號(hào)“?” 表示， ?ｘ表示存在個(gè)體域里的個(gè)體， （?ｘ）Ｆ(ｘ)表示存在個(gè)體域里的個(gè)體具有性質(zhì)F。符號(hào)“?”稱為存在量詞.,2.1 謂詞的概念與表示(Predicate and Its Expression),例4：在謂詞邏輯中將下列命題符號(hào)化. （1）一些數(shù)是有理數(shù)。 （2）有些人活百歲以上。,2.1 謂詞的概念與表示(Predicate and Its

25、Expression),解: (1)當(dāng)個(gè)體域?yàn)閷?shí)數(shù)集合時(shí)： 令Q(x): x是有理數(shù)。則（1）符號(hào)化為 （ ?ｘ）Q(x) 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令P(x): x是數(shù)， Q(x): x是有理數(shù)。 則（1）符號(hào)化為 （ ?x） (P(x) ∧ Q(x)),2.1 謂詞的概念與表示(Predicate and Its

26、Expression),（2）當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)： 令G(x): x活百歲以上。則（2）符號(hào)化為 （ ?x）G(x) 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令M(x): x是人。則（2）符號(hào)化為 （?x） (M(x) ∧ G(x)),,存在量詞的一些重要性質(zhì)：設(shè)P是任意的命題，F(xiàn)(x)與A(x,y)均為謂詞，則

27、有：,2.1 謂詞的概念與表示(Predicate and Its Expression),有時(shí)需要同時(shí)使用多個(gè)量詞。例5. 命題“對(duì)任意的x,存在y, 使得x+y=5”, 取個(gè)體域?yàn)閷?shí)數(shù)集合,則該命題符號(hào)化為: （?x） （?y） H (x, y).其中H(x,y): x+y=5. 這是個(gè)真命題.,,例6.在個(gè)體域限制為(a)和(b)條件時(shí)，將下列命題符號(hào)化:  

28、;  (1) 對(duì)于任意的x，均有x2-3x+2=(x-1)(x-2).   (2) 存在x，使得x+5=3. 其中: (a)個(gè)體域D1=N(N為自然數(shù)集合)        (b)個(gè)體域D2=R(R為實(shí)數(shù)集合),,解： (a)令F(x): x2-3x+2=(x-1)(x-2)，

29、 G(x): x+5=3。 命題(1)的符號(hào)化形式為 （? x）F(x)               命題(2)的符號(hào)化形式為（? x）G(x)         &#

30、160;   顯然(1)為真命題；而(2)為假命題，因?yàn)镹不含負(fù)數(shù)。  (b) 在D2內(nèi)，(1)和(2)的符號(hào)化形式還是上兩式，(1)依然是真命題，而此時(shí)(2)也是真命題。,第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),3. 使用量詞時(shí)應(yīng)注意的問(wèn)題（1）在不同的個(gè)體域，同一命題的符號(hào)化形

31、式可能相同也可能不同。（2）在不同的個(gè)體域，同一命題的真值可能相同也可能不同。（3）以后如不指定個(gè)體域，默認(rèn)為全總個(gè)體域。對(duì)每個(gè)個(gè)體變?cè)淖兓秶?，用特性謂詞加以限制。,第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),特性謂詞:限定個(gè)體變?cè)兓秶闹^詞(如例3中的M（x）)。一般而言，對(duì)全稱量詞，特性謂詞常作蘊(yùn)含的前件，如（?x）

32、(M(x) ?F(x))；對(duì)存在量詞，特性謂詞常作合取項(xiàng)，如（? x）(M(x)∧ G(x))。,第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),(4)一般來(lái)說(shuō)，當(dāng)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，它們的順序不能隨意調(diào)換。如：在實(shí)數(shù)域上用H(x,y)表示x+y=5,則命題“對(duì)于任意的x,都存在y使得x+y=5”可符號(hào)化為： （?x）（?y）H(x,y)

33、 ,其真值為1.若調(diào)換量詞順序后為：（?y）（?x）H(x,y) , 其真值為0。,第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression),(5) 當(dāng)個(gè)體域?yàn)橛邢藜蠒r(shí),如D={a1, a2 …, an},對(duì)任意謂詞A(x),有 (?x) A(x)?A(a1)∧A(a2)∧…∧A(an ) （?x）A(x)?A(a1)∨A(a2)∨…∨A

34、(an ),,例7：在謂詞邏輯中將下列命題符號(hào)化.（1）所有的人都長(zhǎng)頭發(fā)。（2）有的人吸煙。（3）沒(méi)有人登上過(guò)木星。（4）清華大學(xué)的學(xué)生未必都是高素質(zhì)的。解：令　M(x): x是人。（特性謂詞）（1） 令F(x): x長(zhǎng)頭發(fā)。則符號(hào)化為：　　?。?x）(M(x) ?F(x)),第二章 謂詞邏輯（Predicate Logic） 2.1 謂詞的概念與表示(Predicate and Its Expression

35、),（2） 令S(x): x吸煙。則符號(hào)化為：　　　 （?x）(M(x)∧S(x))（3） 令D(x): x登上過(guò)木星。則符號(hào)化為：　　　 ┐(?x)(M(x)∧D(x))（4）令Q(x):x是清華大學(xué)的學(xué)生。H(x):x是高素質(zhì)的。則符號(hào)化為： 　 ┐(?x)(Q(x) ?H(x)),,例8. 將下列命題符號(hào)化:     (1) 兔子比烏龜跑得快。  &

36、#160;  (2) 有的兔子比所有的烏龜跑得快。     (3) 并不是所有的兔子都比烏龜跑得快。     (4) 不存在跑得同樣快的兩只兔子。,,解: 本題沒(méi)有指明個(gè)體域，因而采用全總個(gè)體域。因?yàn)楸纠谐霈F(xiàn)二元謂詞，因而引入兩個(gè)個(gè)體變項(xiàng)x與y。 令F(x):x是兔子，G(y):y是烏龜，H(x,y):x比y跑得快，L(x

37、,y):x與y跑得一樣快。這4個(gè)命題分別符號(hào)化為         (?x)(?y)(F(x)∧G(y)→H(x,y))           (?x)(F(x)∧(? y)(G(y)→H(x,y)))      &

38、#160; ┐(?x)(?y)(F(x)∧G(y)→H(x,y))           ┐(?x)(?y)(F(x)∧F(y)∧L(x,y)),2.2 謂詞公式與翻譯(Predicate formulae),定義2.2.1 項(xiàng)由下列規(guī)則形成：（1）個(gè)體常元和個(gè)體變?cè)琼?xiàng)；（2）若f是n元函數(shù)，且t1,t2,…,tn是項(xiàng)，則

39、 f(t1,t2,…,tn)是項(xiàng)；（3）所有項(xiàng)由（1）和（2）生成。定義2.2.2 若P(x1,x2,…,xn)是n元謂詞， t1,t2,…,tn是項(xiàng)，則稱P(t1,t2,…,tn)是Lp中原子謂詞公式，簡(jiǎn)稱原子公式。,有了項(xiàng)的定義，函數(shù)的概念就可用來(lái)表示個(gè)體常元和個(gè)體變?cè)?。例如，令f(x,y)表示x+y，謂詞N(x)表示x是自然數(shù)，那么f(2,3)表示個(gè)體自然數(shù)5，而N(f(2,3))表示5是自然數(shù)。這里函數(shù)是就廣義而言

40、的，例如P(x):x是教授，f(x):x的父親，c:張強(qiáng)，那么P(f(c))便是表示“張強(qiáng)的父親是教授”這一命題。,2.2 謂詞公式與翻譯(Predicate formulae),定義2.2.3謂詞演算的合式公式,可由下述各條組成:（1）原子公式是合式公式。（2）若A 是合式公式，則(┐A)也是合式公式。（3）若A，B是合式公式，則(A ∧ B)，(A ∨ B)， (A ? B)，(A ? B)也是合式公式。

41、（4）若A是合式公式，x是A中出現(xiàn)的任何變?cè)?則(?x)A , (?x)A，也是合式公式。 (5)只有有限次應(yīng)用(1)~(4)得到的公式是合式公式。,2.2 謂詞公式與翻譯(Predicate formulae),合式謂詞公式是按上述規(guī)則由原子公式、聯(lián)結(jié)詞、量詞、圓括號(hào)和逗號(hào)所組成的符號(hào)串，而且命題公式是它的特例。為使用方便，稱合式謂詞公式為謂詞公式，在不引起混淆時(shí)，可以將公式中有的括號(hào)進(jìn)行省略。,一般說(shuō)來(lái)，謂詞邏輯的翻譯或符號(hào)

42、化的步驟如下： ①正確理解給定命題。必要時(shí)把命題改敘，使其中每個(gè)原子命題、原子命題之間的關(guān)系能明顯表達(dá)出來(lái)。,2.2 謂詞公式與翻譯(Predicate formulae),②把每個(gè)原子命題分解成個(gè)體、謂詞和量詞；在全總論域討論時(shí)，要給出特性謂詞。③找出恰當(dāng)量詞。應(yīng)注意全稱量詞(?x)后跟條件式，存在量詞(?x)后跟合取式。④用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來(lái)。,2.2 謂詞公式與翻譯(Predicate formulae),2.

43、2 謂詞公式與翻譯(Predicate formulae),例1：在謂詞邏輯中將下列命題符號(hào)化.（1）凡正數(shù)都大于零。（2）存在小于2的素?cái)?shù)。（3）沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù)。（4）并不是所有參加考試的人都能取得好成績(jī)。解：（1） 令F(x): x是正數(shù)。M(x):x大于零。則符號(hào)化為：　（?x）(F(x)?M(x)),第二章 謂詞邏輯（Predicate Logic） 2.2 謂詞公式與翻譯(Predicate

44、formulae),（2）令E(x): x小于2。S(x):x是素?cái)?shù)。則符號(hào)化為：　　　 （?x)(E(x)∧S(x))　　　真值為0。 （3）令D(x): x是有理數(shù)。F(x):x能表示成分?jǐn)?shù)。則符號(hào)化為： (?x)(D(x) ?F(x)) 或 ┐(?x)(D(x)∧ ┐F(x))　　真值為１。 （4）令M(x)：x是人.Q(x):x參加考試。H(x):x取得好成績(jī)。則符號(hào)化為：

45、 　 ┐(?x)(M(x)∧Q(x)?H(x)) 或 (?x)(M(x)∧Q(x)∧┐H(x)),2.2 謂詞公式與翻譯(Predicate formulae),例2：在謂詞邏輯中將下列命題符號(hào)化. （1）所有運(yùn)動(dòng)員都?xì)J佩某些教練.（2）有些運(yùn)動(dòng)員不欽佩教練.設(shè)：L(x):x是運(yùn)動(dòng)員 J(y):y是教練 A(x,y):x欽佩y(1) (?x)(L(x) ?（?y)(J(

46、y)∧A(x,y)))(2)（?x)(L(x) ∧(?y)(J(y)? ┐A(x,y))),例3: 沒(méi)有不犯錯(cuò)誤的人。,設(shè) M(x)：x 是人。 F(x)：x犯錯(cuò)誤。命題符號(hào)化為 ：,此命題等價(jià)于“任何人都要犯錯(cuò)誤”或“所有人都要犯錯(cuò)誤”。所以此命題也可符號(hào)化為：,解：本語(yǔ)句即為“不存在不犯錯(cuò)誤的人?！?例2.2.2 將命題“沒(méi)有最大的自然數(shù)”符號(hào)化。解：命題可理解為“對(duì)所有的x，如果x是自然數(shù)，則一定還有比x大的自然數(shù)”，

47、再具體點(diǎn)，即“對(duì)所有的x如果x是自然數(shù)，則一定存在y，y也是自然數(shù)，并且y比x大”。 令N(x):x是自然數(shù)，G(x,y):x大于y，則原命題表示為：(?x) (N(x)?(?y)(N(y)?G(y,x)))。,2.2 謂詞公式與翻譯(Predicate formulae),例4：在謂詞邏輯中將下列命題符號(hào)化. （1）那位戴眼鏡的用功的大學(xué)生在看這本大而厚的巨著.（2）對(duì)于任意給定的ε>0，必存在著δ>0,使得對(duì)任

48、意的x,只要解: (1)設(shè)：S(x):x是大學(xué)生. A(x):x戴眼鏡. B(x):x用功. D(x):x是巨著. F(x,y):x看y. E(y):y是大的. G(y):y是厚的. a:那位 b:這本 則(1)符號(hào)化為: A(a)∧B(a)∧S(a)∧D(b)∧E(b)∧G(b)∧F(a,b),第二章 謂詞邏輯（Predicate Logic） 2.2 謂詞公式與翻譯(Predicate form

49、ulae),（2）符號(hào)化為: (?ε)((ε>0)?(?δ) ((δ>0)∧(?x) (( <δ)? ( <ε)))),例4: 盡管有人聰明，但未必一切人都聰明。,解: 設(shè) M(x)：x是人。 P(x)：x是聰明的。命題符號(hào)化為：,由于人們對(duì)命題的文字?jǐn)⑹龊饫斫獾牟煌?，?qiáng)調(diào)的重點(diǎn)不同，會(huì)影響到命題符號(hào)化的形式不同。見(jiàn)例題5。,例5:

50、這只大紅書柜擺滿了那些古書。,解法1 這只大紅書柜擺滿了那些古書。,x,y,設(shè) F(x,y)：x擺滿了y,再對(duì)x和y加以限制,R(x)：x是大紅書柜,Q(y)：y是古書,a：這只 b：哪些,此時(shí)可把命題符號(hào)化為：,解法2,設(shè) A(x)：x是書柜,B(x)：x是大的,C(x)：x是紅的,D(y)：y是古老的,E(y)：y是圖書,F(x,y)：x擺滿了y,a ：這只 b：那些,此時(shí)可把命題符號(hào)化為：,解法1中R(x)表示x

51、是大紅書柜,解法2中A(x) ∧B(x) ∧C(x)也可表示大紅書柜,但用A(x) ∧B(x) ∧C(x)將更方便于對(duì)書柜的大小顏色進(jìn)行討論,對(duì)個(gè)體刻劃深度的不同就可翻譯成不同的謂詞公式.,2.3 變?cè)募s束(Bound of variable),2.3 變?cè)募s束(Bound of variable)2.3.1 變?cè)募s束2.3.2 約束變?cè)膿Q名與自由變?cè)拇?2.3 變?cè)募s束(Bound of variable),2.3.

52、1變?cè)募s束 (Bound of variable)定義2.3.1:在謂詞公式中，形如(?x)P(x)和(?x)P(x)的部分，稱為謂詞公式的x約束部分。 (?x)P(x)或(?x)P(x)中的x叫做量詞的指導(dǎo)變?cè)蜃饔米冊(cè)?，P(x)稱為相應(yīng)量詞的作用域或轄域。,2.3 變?cè)募s束(Bound of variable),在?x和?x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，相應(yīng)的x稱為約束變?cè)? P(x)中除約束變?cè)酝獬霈F(xiàn)的變?cè)Q為

53、是自由變?cè)?,,量詞,指導(dǎo)變?cè)?轄域,約束變?cè)?自由變?cè)?,,通常，一個(gè)量詞的轄域是公式的子公式。因此，確定一個(gè)量詞的轄域即是找出位于該量詞之后的相鄰接的子公式，具體地講： （1）若量詞后有括號(hào)，則括號(hào)內(nèi)的子公式就是該量詞的轄域； （2）若量詞后無(wú)括號(hào)，則與量詞鄰接的子公式為該量詞的轄域。 判定給定公式中個(gè)體變?cè)羌s束變?cè)€是自由變?cè)?，關(guān)鍵是要看它在公式中是約束出現(xiàn)，還是自由出現(xiàn)。,例1. 指出下列各公式中的指導(dǎo)變?cè)?，各?/p>

54、詞的轄域，自由出現(xiàn)以及約束出現(xiàn)的個(gè)體變?cè)?    (1)( x)(F(x,y)→G(x,z))                      (2)( x)(F(x)→G(y))→( y)(

55、H(x)∧L(x,y,z)),解: (1)x是指導(dǎo)變?cè)?。量詞 ? 的轄域A=(F(x,y)→G(x,z))，在A中，x是約束出現(xiàn)的，而且約束出現(xiàn)兩次，y和z均為自由出現(xiàn)的，而且各自由出現(xiàn)一次。 (2)公式中含有兩個(gè)量詞，前件上的量詞? 的指導(dǎo)變?cè)獮閤， 轄域A=(F(x)→G(y))，其中x是約束出現(xiàn)的，y是自由出現(xiàn)的。后件中的量詞?的指導(dǎo)變?cè)獮閥， 轄域?yàn)?H(x)∧L(x,y,z))，其中y是約束出現(xiàn)的，x，z均為自由出現(xiàn)的

56、。在整個(gè)公式中，x約束出現(xiàn)一次，自由出現(xiàn)2次，y自由出現(xiàn)一次，約束出現(xiàn)一次，z只自由出現(xiàn)一次。,,2.3 變?cè)募s束(Bound of variable),說(shuō)明:(1)n元謂詞公式A(x1，x2...xn) 中有n個(gè)自由變?cè)?若對(duì)其中的k(k≤n)個(gè)進(jìn)行約束,則構(gòu)成了n-k元謂詞;如果一個(gè)公式中沒(méi)有自由變?cè)霈F(xiàn)，則該公式就變成了一個(gè)命題。(2)一個(gè)公式的約束變?cè)褂玫拿Q符號(hào)是無(wú)關(guān)緊要的，如(?x)M(x)與(?y)M(y)意義相

57、同。,定義2.3.2 設(shè)A為任意一個(gè)公式，若A中無(wú)自由出現(xiàn)的個(gè)體變?cè)?，則稱A為封閉的合式公式，簡(jiǎn)稱閉式。由閉式定義可知，閉式中所有個(gè)體變?cè)鶠榧s束出現(xiàn)。例如，(?x)(P(x)?Q(x))和(?x)(?y)(P(x)?Q(x,y))是閉式，而(?x)(P(x)?Q(x,y))和(?y)(?z)L(x,y,z)不是閉式。,2.3 變?cè)募s束(Bound of variable),2.3.2 約束變?cè)膿Q名與自由變?cè)拇胍?guī)則 一

58、個(gè)變?cè)赡茉谕粋€(gè)公式中既是自由出現(xiàn)又是約束出現(xiàn), 這樣在理解上容易發(fā)生混淆。為了避免這種混亂，可采取下面兩個(gè)規(guī)則。（1）換名規(guī)則: (對(duì)約束變?cè)裕?對(duì)約束變?cè)M(jìn)行換名，使得一個(gè)變?cè)谝粋€(gè)公式中只呈一種形式出現(xiàn)。,第二章 謂詞邏輯（Predicate Logic） 2.3 變?cè)募s束(Bound of variable),例1: (?x)( P(x)?R(x,y))∧ L(x,y)換名為(?t)( P(t)?R(t,

59、y))∧ L(x,y)(?x)( H(x,y)?(?y)(W(y) ∧ L(x,y,z)))換名為(?x)( H(x,y)?(?s)(W(s) ∧ L(x,s,z))),第二章 謂詞邏輯（Predicate Logic） 2.3 變?cè)募s束(Bound of variable),換名原則：(1)約束變?cè)梢該Q名,其更改的變?cè)Q范圍是量詞中的指導(dǎo)變?cè)约霸摿吭~作用域中所出現(xiàn)的該變?cè)?，公式的其余部分不變?2)換名時(shí)一定要更

60、改為作用域中沒(méi)有出現(xiàn)的變?cè)Q。,2.3 變?cè)募s束(Bound of variable),（2）代入規(guī)則（對(duì)自由變?cè)裕?duì)公式中自由變?cè)母姆Q為代入。例如，對(duì)例1中的公式(?x)( P(x)?R(x,y))∧ L(x,y) 自由變?cè)獃用z來(lái)代入,得 (?x)( P(x)?R(x,z))∧ L(x,z),2.3 變?cè)募s束(Bound of variable),代入原則：(1)對(duì)于謂詞公式中的自

61、由變?cè)梢宰鞔?代入時(shí)需要對(duì)公式中出現(xiàn)該自由變?cè)拿恳惶庍M(jìn)行;(2)用以代入的變?cè)c原公式中所有變?cè)拿Q不能相同。,改名規(guī)則與代入規(guī)則的共同點(diǎn)都是不能改變約束關(guān)系，而不同點(diǎn)是：① 施行的對(duì)象不同。改名是對(duì)約束變?cè)┬?，代入是?duì)自由變?cè)┬?。?施行的范圍不同。改名可以只對(duì)公式中一個(gè)量詞及其轄域內(nèi)施行，即只對(duì)公式的一個(gè)子公式施行；而代入必須對(duì)整個(gè)公式同一個(gè)自由變?cè)乃凶杂沙霈F(xiàn)同時(shí)施行，即必須對(duì)整個(gè)公式施行。,③ 施行后的結(jié)果不

62、同。改名后，公式含義不變，因?yàn)榧s束變?cè)桓拿麨榱硪粋€(gè)個(gè)體變?cè)?，約束關(guān)系不改變，約束變?cè)荒芨拿麨閭€(gè)體常元。代入，不僅可用另一個(gè)個(gè)體變?cè)M(jìn)行代入，并且也可用個(gè)體常元去代入，從而使公式由具有普遍意義變?yōu)閮H對(duì)該個(gè)體常元有意義，即公式的含義改變了。,2.4 公式解釋與類型,1．公式解釋 一般情況下，Lp中的公式含有：個(gè)體常元、個(gè)體變?cè)s束變?cè)蜃杂勺冊(cè)?、函?shù)變?cè)?、謂詞變?cè)?，?duì)各種變?cè)弥付ǖ奶厥獬Ｔゴ妫蜆?gòu)成了一個(gè)公式的解釋。當(dāng)

63、然在給定的解釋下，也可以對(duì)多個(gè)公式進(jìn)行翻譯。,,例：將下列兩個(gè)公式中的變項(xiàng)指定成常項(xiàng)使其成為命題: (1) (?x) (F(x)→G(x))                         

64、;        (2) (?x) (?y) (F(x)∧F(y)∧G(x,y) →H(f(x,y),g(x,y))),,解: (1)指定個(gè)體變項(xiàng)的變化范圍，并且指定謂詞F，G的含義，下面給出兩種指定法:   (a)令個(gè)體域D1為全總個(gè)體域，F(xiàn)(x)為x是人，G(x)為x是黃種人，則(1)表達(dá)的命題為“所有人都

65、是黃種人”，這是假命題。 (b)令個(gè)體域D2為實(shí)數(shù)集合R，F(xiàn)(x)為x是自然數(shù)，G(x)為x是整數(shù)，則(1)表達(dá)的命題為“自然數(shù)都是整數(shù)”，這是真命題。 我們還可以給出其他各種不同指定，使(1)表達(dá)各種不同形式的命題。,,(2)這里含有兩個(gè)2元函數(shù)變項(xiàng)，兩個(gè)1元謂詞變項(xiàng)，兩個(gè)2元謂詞變項(xiàng)。指定個(gè)體域?yàn)槿倐€(gè)體域，F(xiàn)(x)為x是實(shí)數(shù)，G(x,y)為x≠y，H(x,y)為x>y，f(x,y)=x2+y2，g(x,y)=2xy，則

66、(2)表達(dá)的命題為“對(duì)于任意的x，y，若x與y都是實(shí)數(shù)，且x≠y，則x2+y2 >2xy”，這是真命題。如果H(x,y)改為x<y，則所得命題就為假命題了。,,在上例中所談的對(duì)各種變項(xiàng)的指定也可以稱為對(duì)它們的解釋。在本例中是給出公式后再對(duì)它們進(jìn)行解釋，也可以先給出解釋，再用這個(gè)解釋去研究各種公式。由以上的討論不難看出，一個(gè)解釋不外乎指定個(gè)體域、個(gè)體域中一些特定的元素、特定的函數(shù)和謂詞等部分。,,定義2.4.1 謂詞邏輯中公

67、式的每一個(gè)解釋I 由下面四部分組成：① 非空個(gè)體域DI。② DI中一些特定元素的集合 ③ DI上特定函數(shù)集合 ④ DI上特定謂詞的集合,對(duì)解釋I 的幾點(diǎn)說(shuō)明:     1. 在解釋的定義中引進(jìn)了幾個(gè)元語(yǔ)言符號(hào)，如 。    2. 被解釋的公式A中的個(gè)體變項(xiàng)均取值于DI。    

68、3. 若A中含有個(gè)體常項(xiàng)ai，就解釋成 。,4. 為第i個(gè)n元函數(shù)。例如，i=1，n=2時(shí)， 表示第一個(gè)二元函數(shù)，它出現(xiàn)在解釋中，可能是 等，一旦公式中出現(xiàn)f1(x,y)就解釋成 ， 出現(xiàn)g1(x,y)就解釋成 。5. 為第i個(gè)n元謂詞，如i=2，n=3時(shí)， 表示第2個(gè)3元謂詞，

69、它可能以 的形式出現(xiàn)在解釋中，公式A若出現(xiàn)F2(x,y,z)就解釋成 。 6. 被解釋的公式不一定全部包含解釋中的四部分。,,,,例1:給定解釋 I 如下： (a) 個(gè)體域 D=R (b) (c) (d) 寫出下列公式在I下的解釋, 并指出它的真值。 (1) ?xF(f(x,a),g(x,a)),?x(x+0=x?0)

70、真,(2) ?x?y(F(f(x,y),g(x,y))?F(x,y)),?x?y(x+y=x?y?x=y) 假,(3) ?xF(g(x,y),a),?x(x?y=0) 真值不定, 不是命題,,例2： 給定解釋 I 如下: (a) 個(gè)體域D=N (b) =2 (c) (d) 說(shuō)明下列公式在 I 下的涵義,并討論真值。 (1) F(

71、f(x,y),g(x,y)) x+y=x·y， 不是命題    (2) F(f(x,a),y)→F(g(x,y),z) (x+2=y)→(x·y=z)，  不是命題    (3)┐F(g(x,y),g(y，z)) （x·y≠y·z） ，不是命題,(4) ?x ?y ?z

72、 F (f (x,y), z),,(6) ?x F (f (x,x),g (x,x)),(5) ?x ?y ?z F (f (y,z), x),?x ?y ?z (y+z=x) 假,?x ?y ?z (x+y=z) 真,?x(x+x=x?x) 真,(4), (5)說(shuō)明?與?不能隨意交換,(7) ?x ?y (F (f (x,a),y)?F (f (y,a),x)),?x ?y (x+